An improved gravitational search algorithm for global optimization

Abstract

Gravitational search algorithm (GSA) is inspired by swarm behaviors in nature and physical law based on Newtonian gravity and the laws of motion. There are two key parameters including the number of applied agents (Kbest) and gravitational coefficient (G) to control the search progress in the algorithm. In the conventional GSA, the acceleration of the agents is mainly determined by Kbest and G. Kbest and G are calculated by a monotonically decreasing function, which is not a good schedule for solving complex problems. In order to solve the problem and accelerate the convergence of algorithm, an adaptive GSA is proposed, in which Kbest and G calculation method for strengthening exploitation capability are implemented to achieve better optimization results. Extensive experimental results based on benchmark functions are provided to show the effectiveness of the proposed method. The obtained results have been compared with the results of the original GSA, CGSA, and CLPSO. The comparison results have revealed that the proposed method has good performances.

Keywords

Heuristic optimization algorithm gravitational search algorithm gravitational coefficient global optimization

1 Introduction

Today, as optimization problems become more and more complicated, traditional methods cannot deal with many problems in the high-dimensional search space. Hence, heuristic search algorithms have come into being. Heuristic optimization methods are developed based on nature and physical processes. In the past few decades, algorithms inspired by the behaviors of natural phenomena have received a lot of attentions [1 –4].

Gravitational search algorithm (GSA) was proposed by Esmat Rashedi in 2009, which is based on the law of gravity [5]. GSA is different from traditional heuristic algorithms which provide a simple solution. It can effectively solve high-dimensional space optimization problems. As a newly optimization algorithm based on the law of gravity and motion, GSA includes the operators of mass, a multi-dimensional search space, calculation of the force applied to the objects and movement under the influence of gravitation. In GSA, mass is considered as the weight of the object, which can be divided into three specifications: active gravitational mass, pass gravitational mass, and inertial mass. According to Newton’s physics laws and the above-mentioned mass, the gravitational force that acts on one particle by another particle is proportional to the product of the active gravitational mass and passive gravitational mass and inversely proportional to the square distance. After applying force, this force combines the inertial mass to produce acceleration.

The combination of gravity and mass is the staple idea of GSA. In GSA, agents are considered as objects with a specific mass while gravity is the medium of interaction between each object in the search space. The position of each agent corresponds to a solution and the performances of agents are measured by their masses, which are determined by using a fitness function. Eventually, a global movement of all objects will appear and tend to be heavier masses, which means the sub-optimum solutions [5].

The parameters of an evolutionary algorithm have a very important influence on adjusting the algorithm to the problem [6]. There are some important parameters in GSA such as the number of effective objects and the gravitational coefficient. These parameters have a great impact on the performance of the algorithm, such as convergence rate, exploration, and exploitation. If the setting of important parameters is not perfect, the algorithm will prematurely converge and fall into the local optimum. Since the search process is randomized and the problems are becoming more and more complicated, it is debatable to use only a linear function that decreases over time and an exponentially decreasing model for G in all iterations [7].

In this paper, in order to strengthen the GSA’s exploitation capabilities, some improvements are applied to the calculation rules of Kbest and G. When the fitness value of the objects is getting better and better, the exploration should be weakened accordingly. The larger the value of Kbest is, the more objects that interact with each other under gravitation are. It will result in more motion of the objects in the search space, which will make the acceleration of the object faster. At the same time, G determines the amount of mutual attraction between each object by their positions, which means that the increase of G can be combined with Kbest to strengthen the exploitation ability of the algorithm during optimization.

In the next section, gravitational search algorithm is reviewed. Section 3 introduces the main improvement directions and results of GSA today. The proposed improved GSA is described in detail in Section 4. In Section 5, the experimental results are presented. Finally, the paper is concluded in Section 6.

2 Related works

In recent years, many modified versions of GSA have been proposed. The most famous are four types, namely real GSA introduced for real-valued variables, binary GSA which has variables with two values of 0 and 1 [8], discrete GSA [9] possessing variables with discrete values, and mixed GSA [10] containing both continuous and binary variables. To control the exploitation and exploration efficiently, some new GSA operators are designed, including disruption [11], chaotic [12], mutation [13], crossover [14], and so on.

In the basic GSA, parameters mainly consist of the following aspects: masses of objects (M) , number of agents (N) , gravitational constant (G) , distance between agents in search space (R), power between distance (P) and number of sets of force applied (Kbest) .

The values of masses in the basic GSA, including passive mass, active mass, and inertia mass, are set to the same. Sepehr Ebrahimi Mood & et al. suggested that mass calculation should be improved through defining opportune functions named sigma scaling and Boltzmann functions. These functions try to balance the exploration and exploitation and prevent the algorithm from falling into local optimum [15]. Fatemeh Khajooei and Esmat Rashedi proposed a function about the concept of antigravity, which utilizes both positive and negative masses. The algorithm has the ability to explore the search space [16].

The number of agents is generally set in the beginning of algorithm and fixed during operation [17]. The value of N is set according to the requirements of different algorithms. Distance between agents is calculated by the function of the Euclidian distance and power between distances is set to one in all GSA and its variants.

In the most of GSA versions, G and Kbest all follow a rule and decrease as the number of iterations increases [18]. In the basic GSA, G is controlled by an exponential function as Equation (1) [5]. $G (t) = G_{o} e^{- α \frac{t}{τ}}$ (1)

Where G_o is the initial value of gravitational constant and α is the damping factor.

Fatemeh and Esmat use a fuzzy rule to control parameters setting of GSA. In their opinions, distance between agents (R) can be rewritten into a new parameter ED calculated as Equation (2), which detects the ability of algorithms in terms of diversity, where R^ave, R^maxandR^min stand for average, maximum and minimum distance. Then, another new parameter CM as Equation (3) is introduced to measure the progress of the algorithm, where fitave (t) is average agents’ finesses at time t. The combination of ED and CM can be expressed by fuzzy logic controller to prevent the algorithm from falling into local optimum and early convergence. During the operation of the algorithm, G is increased by these fuzzy rules when the algorithm stops running. At the end of the iteration, G is decreased so that the exploitation capabilities of the algorithm can be enhanced. This is in line with the rules of strengthening exploration ability in the early stage and increasing exploitation capability in the later stage [19]. $ED = \frac{R^{ave} - R^{min}}{R^{{max}^{min}}}$ (2) $CM = \frac{{fit}^{ave} (t - 1) - {fit}^{ave} (t)}{{fit}^{ave} (t)}$ (3)

In the basic GSA, G is considered as a linear decreasing function as Equation (4). E. Rashedi & et al. examine the effect of different values of G₀ and kbest . The results of their experiments have shown that the optimal value of G₀ is different with different functions and G₀ is a parameter determined by the problem. Furthermore, the value of kbest has been experimentally proven to change with time t. $G (t) = G_{0} (1 - \frac{t}{T})$ (4)

In another study, the authors deem that kbest should be increased to escape trapping local optima when best fitness can’t be improved during iterations. For parameter G, they suggest that a simple exponential decreasing function is unreasonable to solve complicated optimization problems among all iterations. Eight fuzzy rules are adopted to update G and Kbest [7].

3 GSA

In GSA, the objective function of an optimization problem is based on many variables which can be set to m decision variables. Each variable has an upper and lower bound as shown in Equation (5), represented by $x_{u}^{d}$ and $x_{l}^{d}$ respectively. In the dimension of m, a search field is set up using these boundaries. $x_{l}^{d} \leq x^{d} \leq x_{u}^{d}, d = 1, 2, . . ., m$ (5)

Suppose there are now k objects, the position of the ith object is defined as Equation (6): $X_{i} = (x_{i}^{1}, . . ., x_{i}^{d}, . . ., x_{i}^{n}), i = 1, 2, . . ., k$ (6) where $x_{i}^{d}$ is the position of ith object in the dth direction. At the time t, total forces applied to the object i from a set of heavier objects should be defined as Equation (7):

$\begin{matrix} F_{i}^{d} (t) & = \sum_{j \in best, j \neq i}^{k} {rand}_{j} F_{ij}^{d} \\ = \sum_{j \in kbest, j \neq i} {rand}_{j} G (t) \\ \frac{M_{aj} (t) M_{pi} (t)}{R_{ij} (t) + ɛ} (x_{j}^{d} (t) - x_{i}^{d} (t)) \end{matrix}$ (7) where M_aj is the active mass related to object j, M_pi is the passive mass related to object i, G (t) is gravitational constant at time t, ɛ is a small value, R_ij (t) is the distance between the two agents iandj, and rand_j is a uniform variable in the interval [0, 1]. Kbest is a function of time, initialized to k₀ at the beginning and is decreased with time t.

Then, combine the law of motion to calculate the acceleration of the object i at time t and in the dth direction, which is given as Equation (8): $a_{i}^{d} (t) = \frac{F_{i}^{d}}{M_{ii} (t)}$ (8) where M_ii is the inertia mass related to the object i. Afterward, the next velocity and its next position are calculated as Equation (9) and Equation (10): $v_{i}^{d} (t + 1) = {rand}_{i} \times v_{i}^{d} (t) + a_{i}^{d} (t)$ (9) $x_{i}^{d} (t + 1) = x_{i}^{d} (t) + v_{i}^{d} (t + 1)$ (10) where rand_i is a uniform random variable in the interval [0, 1].

The gravitational constant G is a function of time as Equation (11) that takes an initial value (G₀) and will be reduced with time to control the search accuracy. $G (t) = G (G_{o}, t) .$ (11)

The masses of objects are calculated by the fitness function. Supposing that the gravitational mass is numerically equal to the inertia mass, the mass M_i(t) is acquired by Equations (12)–(15):M_iM_ii, i = 1, 2, . . . , k, $m_{i} (t) = \frac{{fit}_{i} (t) - worst (t)}{best (t) - worst (t)}$ (12) $M_{i} (t) = \frac{m_{i} (t)}{\sum_{j = 1}^{k} m_{j} (t)}$ (13) $best (t) = min_{j \in {1, . . ., k}} {fit}_{j} (t)$ (14) $worst (t) = max_{j \in {1, . . ., k}} {fit}_{j} (t)$ (15) where fit_i (t) is the fitness value of object i at time t. The better function value is, the bigger the value of mass will be. A heavier mass represents a more efficient object, which has greater attractions and run more slowly.

4 Improved GSA (IGSA)

In the conventional GSA, the parameters Kbest and G are very influential to the performance of the algorithm. It is not very reasonable to simply calculate Kbest and G by a decreasing function when iterations increase. Therefore, Kbest and G should be adjusted based on the effect of the algorithm’ operation [19].

4.1 Number of agents of force applied

The number of effective agents (Kbest) is considered to measure the search progress of GSA. The value of Kbest is greater, which means that there are more objects interacting with each other due to the gravitational force. It causes objects in the search space having more motion, which in turn leads to a lower convergence speed. In the search process of GSA, Kbest should be increased to prevent falling into local optimum, especially when the search process has stalled. Finally, the power of exploitation has been strengthened.

In the basic GSA, Kbest is obtained by a decreasing function as Equation (16).

$\begin{matrix} Kbest & = 0.01 \times N \times (final_per + (1 - \frac{t}{Max_t}) \\ \times (100 - final_per)) \end{matrix}$ (16) where N is the number of agents, final_per is a control parameter making only just one agent applying force to others, t is the number of iterations, and Max_t is maximum number of iterations.

In this paper, with regards to Kbest, a new coefficient β is defined to adjust the value of Kbest. The specific formula is as Equation (17). $\begin{matrix} Kbest & = 0.01 \times β \times N \times (final_per + (1 - \frac{t}{Max_t}) \\ \times (100 - final_per)) \end{matrix}$ (17)

The value of β has a significant effect on increasing or decreasing the ability of exploration and exploitation. Our goal is to achieve better results by changing β through operational feedback. In order to strengthen the exploitation of the algorithm, the following formula is designed to make a decision in the Equation (18). $FD = {fit}^{best} (t - 1) - {fit}^{best} (t)$ (18) where fit^best (t) is the optimal value of the objective function at iteration t. If FD is equal to zero, the algorithm does not get good results at the current iteration. At this point, we firstly expand the agents of applied forces. Then, through the following function as Equation (19), it is judged how the value of β changes when FD is not equal to zero in the minimization problems. $KM = \frac{{fit}^{ave} (t - 1) - {fit}^{ave} (t)}{{fit}^{ave} (t)}$ (19) where fit^ave (t) is the average fitness at iteration t. If KM tends to zero, it means that the optimal value has not been improved, and it can be said that the whole level of optimization progress is low.

4.2 Gravitational coefficient

In the velocity calculation rule, gravitational constant has a huge impact on the movement of the agents in the search space. The ability of exploitation can be enhanced by adjusting the speed of the objects movement. When the fitness value becomes better and better, G should be decreased to strengthen local search capabilities. In the basic GSA, G is obtained purely from the beginning to the end by an exponential function. It is unreasonable and should be changed to solve complex problems. Thus, it is revised as follows: $G = G_{0} e^{1 α θ \frac{t}{τ}}$ (20) where θ is a new control parameter. It is used to adjust the value of G. Through this parameter, faster convergence speed can be obtained.

4.3 Pseudocode of IGSA

Pseudocode of IGSA

Input: N: the number of agents

max_it: maximum number of iterations

F_index: the index of the test function

Min_flag: [min_flag = 1,minimization] and [min_flag = 0,maximization]

(1) Rnorm = 2 (norm in the Euclidian distance);

(2) Generate the initial position of the i th agent $X_{i} = (x_{i}^{1}, . . ., x_{i}^{d}, . . ., x_{i}^{n})$ by randomly forming from the d-dimensional search space;

(3) for iteration = 1: $\max_{i} t$

(4) Checks the search boundaries for agents;

(5) Evaluate the objective function values of agents;

(6) If min_flag = 1

(7) Select the minimum value in the calculation result;

(8) else

(9) Select the maximum value in the calculation result;

(10) end if

(11) Calculate the values of masses (M) of each agent by Equation (13);

(12) Calculate gravitational constant(G) by Equation (20);

(13) Calculate the value of KM by Equation (19);

(14) If KM tends to 0

(15) Increase the value of β=β(1 +N (0, 1));

(16) Increase the value of θ = θ (1 - N (0, 1))

(17) else

(18) β= 1

(19) θ = 1;

(20) Calculate the number of effective objects (Kbest) by Equation (17);

(21) Calculate acceleration and velocity by Equations (9)–(15);

(22) Update agents’ position;

(23) end for

Output: Fbest: the best result of the objective function values;

Lbest: the best solution(the location of Fbest in search space);

BestChart: the best so far Chart over iterations.

Computational complexity should be discussed. Given the number of agents to be N, the computational complexity for one generation is analyzed as follows. Calculation the values of masses of each agent need O (N) computations. The parameter KM evaluation requires O (N) . Calculation acceleration and velocity need O (N²) computations. Therefore, the total computational complexity for one generation is O (N²).

5 Experimental results

The performance of the proposed algorithm can be tested by ten standard benchmark functions including some unimodal and some multimodal criterion, which are listed in Table 1. Functions f₁ to f₇ are unimodal and functions f₈ to f₁₂ are multimodal. The former pays more attention to the convergence rate, while the latter pays more attention to the final results.

IGSA is applied to minimize these functions and the results are compared with the basic GSA, chaotic GSA [20], and comprehensive learning particle swarm optimizer [21]. Among these algorithms, number of agents is set to 50 (N = 50). The dimensions of test function are set to 30 and 50 respectively. Maximum iteration is 1000.

The results are averaged over 25 runs and the mean values and variance are presented in Table 2, in which the best values have been highlighted in bold.

Table 1
12 standard benchmark functions

Test function Bounds

$f_{1} (X) = \sum_{i = 1}^{n} x_{i}^{2}$ [–100,100]ⁿ

$f_{2} (X) = \sum_{i = 1}^{n} | x_{i} | + \prod_{i = 1}^{n} | x_{i} |$ [–10,10]ⁿ

$f_{3} (X) = \sum_{i = 1}^{n} (\sum_{j = 1}^{i} x_{j})^{2}$ [–100,100]ⁿ

f₄ (X) = max i {|x_i|, 1 ≤ i ≤ n} [–100,100]ⁿ

$f_{5} (X) = \sum_{i = 1}^{n - 1} [100 (x_{i + 1} - x_{i}^{2})^{2} + (x_{i} - 1)^{2}]$ [–30,30]ⁿ

$f_{6} (X) = \sum_{i = 1}^{n} ([x_{i} + 0.5])^{2}$ [–100,100]ⁿ

$f_{7} (X) = \sum_{i = 1}^{n} {ix}_{i}^{4} + random [0, 1)$ [–1.28,1.28]ⁿ

$f_{8} (X) = \sum_{i = 1}^{n} - x_{i} sin (\sqrt{| x_{i} |})$ [–500,500]ⁿ

$f_{9} (X) = \sum_{i = 1}^{n} [x_{i}^{2} - 10 cos (2 π x_{i}) + 10]$ [–5.12,5.12]ⁿ

$f_{10} (X) = - 20 exp (- 0.2 \sqrt{\frac{1}{n} \sum_{i = 1}^{n} x_{i}^{2}}) - exp \sqrt{\frac{1}{n} \sum_{i = 1}^{n} cos (2 π x_{i})}) + 20 + e$ [–32,32]ⁿ

Test function	Bounds
$f_{1} (X) = \sum_{i = 1}^{n} x_{i}^{2}$	[–100,100]ⁿ
$f_{2} (X) = \sum_{i = 1}^{n} \| x_{i} \| + \prod_{i = 1}^{n} \| x_{i} \|$	[–10,10]ⁿ
$f_{3} (X) = \sum_{i = 1}^{n} (\sum_{j = 1}^{i} x_{j})^{2}$	[–100,100]ⁿ
f₄ (X) = max i {\|x_i\|, 1 ≤ i ≤ n}	[–100,100]ⁿ
$f_{5} (X) = \sum_{i = 1}^{n - 1} [100 (x_{i + 1} - x_{i}^{2})^{2} + (x_{i} - 1)^{2}]$	[–30,30]ⁿ
$f_{6} (X) = \sum_{i = 1}^{n} ([x_{i} + 0.5])^{2}$	[–100,100]ⁿ
$f_{7} (X) = \sum_{i = 1}^{n} {ix}_{i}^{4} + random [0, 1)$	[–1.28,1.28]ⁿ
$f_{8} (X) = \sum_{i = 1}^{n} - x_{i} sin (\sqrt{\| x_{i} \|})$	[–500,500]ⁿ
$f_{9} (X) = \sum_{i = 1}^{n} [x_{i}^{2} - 10 cos (2 π x_{i}) + 10]$	[–5.12,5.12]ⁿ
$f_{10} (X) = - 20 exp (- 0.2 \sqrt{\frac{1}{n} \sum_{i = 1}^{n} x_{i}^{2}}) - exp \sqrt{\frac{1}{n} \sum_{i = 1}^{n} cos (2 π x_{i})}) + 20 + e$	[–32,32]ⁿ

Table 2

The results of four algorithms

Dimension	Function s	IGSA	GSA	CGSA	CLPSO
	f ₁	Mean	4.12E-20	2.07E-17	1.62E-5	5.50E-2
		Std	1.14E-40	2.85E-35	2.09E-11	7.25E-3
30		t Test		+	+	+
	f ₂	Mean	9.746E-10	2.272E-8	2.014E-2	4.612E-2
		Std	2.667E-20	1.687E-17	7.659E-6	8.210E-5
		t Test		+	+	+
	$\begin{matrix} f_{3} \end{matrix}$	Mean	2.382E+02	2.546E+02	1.53E-3	8.59E+1
		Std	5.553E+03	6.670E+03	6.76E-7	1.64E+2
		t Test		+	–	+
	f ₄	Mean	1.48E-10	3.19E-9	4.27E-03	2.51E+1
		Std	1.39E-21	3.66E-19	4.56E-07	3.37E+0
		t Test		+	+	+
	f₅	Mean	2.62E+1	2.86E+1	2.51E+1	4.02E+2
		Std	5.05E-2	1.58E+2	9.23E-2	7.38E+3
		t Test		+	–	+
	f ₆	Mean	0	0	0	4.72E-2
		Std	0	0	0	1.38E-4
		t Test		=	=	+
	f ₇	Mean	1.79E-2	1.80E-2	4.92E-2	3.12E-2
		Std	7.12E-5	3.84E-5	7.18E-5	5.64E-5
		t Test		=	+	+
	f ₈	Mean	–2.84E+3	–2.84E+3	–2.79E+3	–1.25E+4
		Std	1.72E+5	3.77E+5	9.14E+4	1.13E+3
		t Test		=	=	+
	f ₉	Mean	1.473E+01	1.496E+01	2.080E+01	1.001E+01
		Std	1.336E+01	1.068E+01	1.054E+01	2.805E+00
		t Test		=	+	–
	f ₁₀	Mean	1.51E-10	3.73E-9	3.04E-3	1.58E-1
		Std	4.35E-22	1.99E-19	3.01E-7	1.05E-3
		t Test		+	+	+
	f ₁	Mean	1.32E-19	6.88E-17	1.67E-5	1.86E+1
50		Std	6.05E-40	3.51E-34	2.82E-11	2.11E+1
		t Test		+	+	+
	f ₂	Mean	2.44E-9	1.88E-2	1.98E-2	1.53E+0
		Std	2.43E-19	8.80E-3	1.31E-5	4.60E-2
		t Test		+	+	+
	f ₃	Mean	3.79E+0	1.02E+3	1.34E+1‘	3.95E+2
		Std	1.52E+0	6.97E+4	6.05E+2	2.76E+3
		t Test		+	+	+
	f ₄	Mean	4.11E+0	4.15E+0	2.47E+1	3.94E+1
		Std	1.78E+0	1.42E+0	6.75E+0	4.16E+0
		t Test		=	+	+
	f ₅	Mean	5.10E+1	6.39E+1	2.60E+1	7.18E+3
		Std	3.61E+2	1.40E+3	1.17E-1	3.41E+6
		t Test		+	–	+
	f ₆	Mean	1.12E+0	6.80E-1	1.50E-5	1.75E+1
		Std	3.03E+0	8.10E-1	2.43E-11	2.26E+1
		t Test		–	–	+
	f ₇	Mean	7.05E-2	5.51E-2	4.53E-2	1.18E-1
		Std	9.27E-4	9.08E-4	1.39E-4	5.24E-4
		t Test		–	–	+
	f ₈	Mean	–3.59E+3	–3.64E+3	–8.98E+3	–1.95E+4
		Std	2.67E+5	4.36E+5	1.73E+4	7.24E+4
		t Test		=	–	–
	f ₉	Mean	3.03E+1	3.30E+1	2.60E+1	6.49E+1
		Std	4.65E+1	3.52E+1	8.54E+1	5.54E+1
		t Test		+	–	+
	f₁0	Mean	2.14E-10	4.71E-9	2.9E-3	3.25E+0
		Std	1.62E-21	3.09E-19	2.39E-7	6.67E-2
		t Test		+	+	+
		+		12	11	18
		–		2	7	2
		=		6	2	0
		Score		10	9	16

From unimodal function f₁ to f₅, all results from IGSA are better than the basic GSA, the variance of the 25 runs is smaller and the convergence rate is faster. Among them, the results of functions f₁, f₂, and f₄ have shown that IGSA has better convergence rate and running results as well as smaller variance than CGSA and CLPSO. CGSA has achieved the best results on function f₃ when the dimension is 30. Also, the good performance of IGSA could be concluded in Fig. 1. The convergence speed is significantly faster and better results are achieved. The differences between them have shown that IGSA is faster to find global optimal solutions than other algorithms, the result is more stable, and the convergence speed is higher.

Fig. 1

Comparison of performance f1–f4 (D=50).

The multimodal functions f₈ to f₁₀ are very difficult to optimize because there are many local optimal solutions increasing exponentially as the dimension increases, the capabilities of optimization algorithm has greater impact on final results. It is extra important to avoid falling into local optimum and locate a near-global optimum. In the functions f₁₀, IGSA has achieved better performance than the original GSA, CGSA, and CLPSO. IGSA has better results than GSA and CGSA in f₈ and f₉. However, the results are worse than the performance of CLPSO. According to the no free lunch theorem, we can’t expect the best performances on all the test functions.

For a thorough comparison, the t test has also been carried out. Table 2 presents the t values on every function of this two-tailed test with a significance level of 0.05 between the proposed algorithm and other algorithms. Rows “+(Better)”, “=(Same)” and “–(Worse)” give the number of functions that the proposed algorithm performs significantly better than, almost the same as, and significantly worse than the compared algorithm, respectively. Row “Score” shows the difference between the number of 1s and the number of – 1s, which is adopted to give an overall comparison between the two algorithms. For instance, comparing the proposed algorithm with GSA, the former significantly outperforms the latter on 12 functions, does the same as the latter on two functions, and does worse on six functions, yielding a “Score” figure of merit of 12-2 = 10, which demonstrates that the proposed algorithm generally outperforms the conventional GSA. Although it performs slightly weaker on some functions, the proposed algorithm in general offers much improved performance than all the above algorithms compared.

5.1 Discussions

In order to further validate the performance of the proposed method, additional experiments have been made. We optimize Kbest separately, optimize G separately, and combine Kbest and G for optimization under same conditions. f1, f₂, f₄, f₈, and f₁₀ are selected to make testing. The comparison results are listed in Table 3.

Table 3
Comparison result of parameter setting

Best values Kbest+G Kbest G

f ₁ 4.12429E-20 2.44041E-17 4.39785E-20

f ₂ 9.74574E-10 2.52784E-08 1.02309E-09

f ₄ 1.48088E-10 2.89776E-09 1.73757E-10

f ₈ –2840.300292 –2792.514269 –2758.609129

f ₁₀ 1.50952E-10 3.95154E-09 1.5322E-10

Best values	Kbest+G	Kbest	G
f ₁	4.12429E-20	2.44041E-17	4.39785E-20
f ₂	9.74574E-10	2.52784E-08	1.02309E-09
f ₄	1.48088E-10	2.89776E-09	1.73757E-10
f ₈	–2840.300292	–2792.514269	–2758.609129
f ₁₀	1.50952E-10	3.95154E-09	1.5322E-10

Among f1, f₂, f₄, f₈, and f₁₀, the results of optimizing Kbest alone are the worst, and are similar to the results of the original GSA. The results of optimizing G alone are much better than the original GSA. However, the combination of Kbest and G has achieved superior performances, which are the best among the three experiments. The experimental results have demonstrated that the optimization of Kbest and G together is very reasonable and effective.

In addition, sensitivity is also tested. Two experiments are implemented. For the first experiment, the parameter β is kept same during the experiment. The parameter θ is set three different values, 1, 1.5 and 2 respectively. For the second experiment, the parameter θis maintained same during the experiment. The parameter β is with three different values, 1, 1.5 and 2 respectively.

The experiment is under same conditions. f₁, f₂, f₄, f₈, and f₁₀ are selected to make testing. The comparison results are listed in Tables 4 and 5. From the Tables 4 and 5, it can be found that these two parameters have little influence on the final results when the initial ranges are set between 1 and 2.

Table 4

Result of sensitive testing with different θ

Best values	θ =1	θ=1.5	θ=2
f ₁	4.12E-20	5.04E-20	3.95E-20
f ₂	9.75E-10	6.92E-10	8.03E-10
f ₄	1.48E-10	2.01E-10	1.95E-10
f ₈	–2840.30	–2845.32	–2841.32
f ₁₀	1.51E-10	1.75E-10	2.01E-10

Table 5

Result of sensitive testing with different β

Best values	β = 1	β=1.5	β=2
f ₁	4.12E-20	6.07E-20	6.54E-20
f ₂	9.75E-10	8.79E-10	8.90E-10
f ₄	1.48E-10	1.66E-10	1.87E-10
f ₈	–2840.30	–2842.39	–2843.56
f ₁₀	1.51E-10	2.11E-10	1.98E-10

6 Conclusion

Gravitational search algorithm is one of the power metaheuristic algorithms at present. It is based on the law of gravity and mass interactions. In order to achieve better performances, a new idea of controlling the late search process of gravitational search algorithm is proposed, which represents a post-improvement of parameter Kbest and parameter G. The new strategy makes GSA have higher convergence rate and can escape from the local minimum. The purpose of strengthening the exploitation ability of later iterations is also realized. The combination of Kbest and G has achieved better results for global optimization problems. The performance of improved GSA is tested in well-known standard functions. The influences of Kbest and G are also discussed and sensitivity testing is finished. The proposed algorithm has got superior performances in the most unimodal and multimodal functions. The experimental results are compared with other algorithms. These results have demonstrated that IGSA has merit in solving the problems of optimization.

Optimization problems have become more and more complicated. Some of them contain several constraints while some of them have discrete variables. It is more difficulty to optimize these problems. In the coming research, we will improve GSA to solve these problems and use the algorithm to solve real application problems.

Footnotes

Acknowledgments

This research was funded by the China Natural Science Foundation (No. 71974100, No. 41501555), Natural Science Foundation in Jiangsu Province (No. BK20191402), Major Project of Philosophy and Social Science Research in Colleges and Universities in Jiangsu province (2019SJZDA039), Qing Lan project (R2019Q05) and Postgraduate research and innovation plan project (SJKY19_0983) in Jiangsu Province.

References

Goldberg

D.E.

, et al., Genetic Algorithm is Search Optimization and Machine Learning xiii(7) (1989), 2104–2116.

Formato

R.A.

, Central Force Optimization: A New Nature Inspired Computational Framework for Multidimensional Search and Optimization (2008), 221–238.

Kennedy

, Particle Swarm Optimization, Proc of 1995 IEEE Int Conf Neural Networks, (Perth, Australia) 4(8) (2011), 1942–1948.

Pedersen

B.K.

and Hoffman-Goetz

, Exercise and the immune system: Regulation, integration, and adaptation, Physiological Reviews 80(3) (2000), 1055–1081.

Rashedi

, Nezamabadi-pour

and Saryazdi

, GSA: A Gravitational Search Algorithm, Information Sciences 179(13) (2009), 2232–2248.

Eiben

A.E.

, et al., Parameter Control in Evolutionary Algorithms, Evolutionary Computation IEEE Transactions on 19(2) (2007), 167–187.

Askari

and Zahiri

S-H.

, Decision function estimation using intelligent gravitational search algorithm, International Journal of Machine Learning and Cybernetics 3(2) (2011), 163–172.

Rashedi

, Nezamabadi-pour

and Saryazdi

, BGSA: Binary gravitational search algorithm, Natural Computing 9(3) (2009), 727–745.

Shamsudin

H.C.

, et al., A Fast Discrete Gravitational Search Algorithm. in International Conference on Computational Intelligence. 2012.

10.

Sarafrazi

and Nezamabadi-Pour

, Facing the classification of binary problems with a GSA-SVM hybrid system, Mathematical & Computer Modelling 57(1–2) (2013), 270–278.

11.

Sarafrazi

, Nezamabadi-pour

and Saryazdi

, Disruption: A new operator in gravitational search algorithm, Scientia Iranica 18(3) (2011), 539–548.

12.

Han

and Chang

, A chaotic digital secure communication based on a modified gravitational search algorithm filter, Information Sciences 208 (2012), 14–27.

13.

Nobahari

, Nikusokhan

and Siarry

, A MultiObjective Gravitational Search Algorithm Based on Non-Dominated Sorting. 2012: IGI Global. 32–49.

14.

Khatibinia

and Khosravi

, A hybrid approach based on an improved gravitational search algorithm and orthogonal crossover for optimal shape design of concrete gravity dams, Applied Soft Computing Journal 16(3) (2014), 223–233.

15.

Mood

S.E.

, Rashedi

and Javidi

M.M.

, New Functions for Mass Calculation in Gravitational Search Algorithm. 2016.

16.

Khajooei

and Rashedi

, A new version of Gravitational Search Algorithm with negative mass. in Conference on Swarm Intelligence and Evolutionary Computation 2016.

17.

Fister

, et al., Adaptation and Hybridization in Nature-Inspired Algorithms 18 (2015), 3–50.

18.

Rashedi

, Rashedi

and Nezamabadi-pour

, A comprehensive survey on gravitational search algorithm, Swarm and Evolutionary Computation 41 (2018), 141–158.

19.

Saeidi-Khabisi

F.S.

and Rashedi

, Fuzzy gravitational search algorithm. in International Econference on Computer and Knowledge Engineering 2012.

20.

Mirjalili

and Gandomi

A.H.

, Chaotic gravitational constants for the gravitational search algorithm, Applied Soft Computing 53 (2017), 407–419.

21.

Liang

J.J.

, et al., Comprehensive learning particle swarm optimizer for global optimization of multimodal functions, IEEE Transactions on Evolutionary Computation 10(3) (2006), 281–295.

An improved gravitational search algorithm for global optimization

Abstract

Keywords

1 Introduction

2 Related works

4.1 Number of agents of force applied

5 Experimental results

Table 3 Comparison result of parameter setting Best values Kbest+G Kbest G f 1 4.12429E-20 2.44041E-17 4.39785E-20 f 2 9.74574E-10 2.52784E-08 1.02309E-09 f 4 1.48088E-10 2.89776E-09 1.73757E-10 f 8 –2840.300292 –2792.514269 –2758.609129 f 10 1.50952E-10 3.95154E-09 1.5322E-10

Footnotes

Acknowledgments

References