Abstract
In recent years, various heuristic algorithms based on natural phenomena and swarm behaviors were introduced to solve innumerable optimization problems. These optimization algorithms show better performance than conventional algorithms. Recently, the gravitational search algorithm (GSA) is proposed for optimization which is based on Newton's law of universal gravitation and laws of motion. Within a few years, GSA became popular among the research community and has been applied to various fields such as electrical science, power systems, computer science, civil and mechanical engineering, etc. This chapter shows the importance of GSA, its hybridization, and applications in solving clustering and classification problems. In clustering, GSA is hybridized with other optimization algorithms to overcome the drawbacks such as curse of dimensionality, trapping in local optima, and limited search space of conventional data clustering algorithms. GSA is also applied to classification problems for pattern recognition, feature extraction, and increasing classification accuracy.
TopIntroduction
With the advancement of computing technology, the researchers can easily solve complex real-world problems in the domain of optimization. Further, the researchers are inspired by nature to solve complicated computational problems. They are classified into evolutionary algorithms (EA) and Swarm Intelligence (SI) based algorithms as shown in figure 1. The EAs are based on Darwinian Theory of natural selection. The examples include Genetic Algorithms (GA) (Holland, 1975), Differential Evolution (Storm et al., 1995), etc. Furthermore, SI based algorithms mimic the physical and natural processes for mathematical modeling of the optimization algorithm. They have the properties of information interchange and non-centralized control structure. Some examples of SI based algorithms are Particle Swarm Optimization (PSO) (Kennedy et al., 1995), Ant Colony Optimization (ACO) (Dorigo et al., 1991), Bees Algorithm (Jung, 2003; Karaboga, 2005) and Gravitational Search Algorithm (GSA) (Rashedi et al., 2009).
Gravitational search algorithm (GSA) is a physics-based optimization algorithm inspired by Newton’s laws of motion and gravity. It is a powerful heuristic optimization method which shows good results for non-linear optimization problems. The conceptual and theoretical foundation of GSA is based on the concept of mass interactions which states that “A particle in the universe attracts every other particle with a force that is directly proportional to the product of their masses and inversely proportional to the square of the distance between them”. The masses are considered as objects that interact and cooperate with each other through the gravitational force. The position of the heavy mass gives the global optimum solution as it has the highest fitness value.
Figure 1. Classification of nature inspired computational algorithms
GSA is good at finding the global optima but has the drawbacks of slow convergence speed and getting stuck in local minima in the last few iterations. In order to overcome these problems, GSA is hybridized with other swarm based optimization algorithms such as PSO, ACO, DE, etc. The GSA has been used to solve various optimization problems in different domains of study such as clustering, classification, feature selection, routing, image processing, etc.
Clustering is the technique of grouping similar data samples based on similarity index and distance measure. It is also a popular data analysis technique. On the other hand, Classification is the process of categorizing the data into groups based on mathematical information and is useful for obtaining potential features from the complex dataset. Today, the most part of the world is interconnected by social media such as Facebook, Twitter, etc. It results in the generation of the voluminous and huge amount of data. This raw data is multidimensional in nature and has large complexity. The branch of artificial intelligence that deals with the analysis and processing of complex data is called as data science and the data items that are present in variety of formats can be efficiently handled using Big data. It is a hot topic in computer science community today (Chira et al., 2014). The clustering and classification are the fundamental techniques for finding potential patterns in the big data.
The GSA is hybridized with classical clustering algorithms and searching methods such as K-means clustering (MacQueen, 1967), K-harmonic (K-H) means clustering (Zhang et al., 2000), Heuristic Search (Hatamlou et al., 2011), GSA-Data Clustering algorithm (Hatamlou et al., 2012), and GSA-Kernel Clustering (C. Li et al., 2014). They are combined with GSA to overcome the high dimensionality and limited search space problems. Furthermore, GSA is also applied to classification problems and combined with the famous classifiers such as Support Vector Machines (SVM) (Ghang, 2015), Neural Network classifier (Ahmadlou, 2010), and K-Nearest Neighbor (Jamshidi et al., 2014) for increasing the precision and accuracy.
Key Terms in this Chapter
Optimization: It is the technique of selecting the most feasible solution for the given problem. The nature-inspired algorithms such as GSA, PSO, GA, etc. are the best examples of optimization.
Heuristic Algorithms: The techniques that are used for finding the optimal solution around the feasible solutions are called Heuristics. The algorithms which mimic the natural systems are called as Heuristic Algorithms. These algorithms have the properties of working in a parallel manner and information interchange among the agents. They are probabilistic in nature and do not have central control.
Exploitation: It is the process of finding the feasible solution around the candidate solutions in the search space. This step is used by all the optimization algorithms in order to find the local optima. The high exploitation power of an algorithm indicates its effectiveness and high convergence rate.
Particle Swarm Optimization (PSO): It is a nature-inspired algorithm which mimics the behavior of a flock of birds or fishes. It uses the concepts of local best and global best in getting the optimal solution. The iteration procedure is used to improve the quality of candidate solutions.
Exploration: It is the ability of the optimization algorithm to randomly initialize the search space. Basically, it is the first step in every optimization algorithm because it shows the range i.e. the lower and upper limits of the algorithm. The high exploration power of an algorithm indicates its fewer chances of getting trapped in the local optima.
Clustering: Clustering is the technique of grouping similar data samples based on distance and similarity criterion. Clustering is a statistical data analysis task which has been employed in many areas such as information retrieval, data mining, bioinformatics, data compression, etc.
Swarm Intelligence (SI): It is the field of artificial intelligence in which the population is in the form of agents which search in a parallel fashion with multiple initialization points. The swarm intelligence-based algorithms mimic the physical and natural processes for mathematical modeling of the optimization algorithm. They have the properties of information interchange and non-centralized control structure.
Classification: Classification is the process of categorizing the data into groups based on mathematical information. It is a pattern recognition technique (i.e., finding the meaningful informational patterns from the outlier and noisy data).
Hybridization: It is the technique of modifying the mathematical structure of the parent algorithm by using another optimization algorithm(s) so that the limitations of the parent algorithm can be removed.
Gravitational Search Algorithm (GSA): It is a meta-heuristic algorithm for global optimization based on the law of interaction of masses.