4.1. Standard Gravitational Search Algorithm
Inspired by the law of universal gravity, Rashedi et al. proposed a new swarm intelligence optimization algorithm—the gravitational search algorithm (GSA) in 2009 [
30]. The law of gravity is a law that explains the relationship between objects interacting with each other. In the gravitational search algorithm, gravity is equivalent to an information transfer tool that enables information sharing among individuals and optimal search by the group under the effect of gravity.
Assuming that there are N particles, the position and velocity of the ith individual in the D-dimensional space are denoted as
and
, where
and
, respectively, denote the position and velocity components of individual
in the d-dimensions, and the position denotes the solution of the problem. The position and velocity are first initialized in the solution space and velocity space, the objective function values of each individual are calculated and evaluated, the mass, gravitational force and acceleration of each individual are calculated, and finally the velocity and position of the individual are updated [
41].
According to Newton’s gravitation theory, in the
dimensions, the gravitational force of individual j on
is expressed as:
where
,
, respectively, are the universal gravitational constants at the tth iteration and the Euclidean distances of individuals
and j, with the following expressions:
where
,
and
are constants,
is the current number of iterations and
is the maximum number of iterations,
,
and
.
In the
dimensions, the combined force on individual
is:
where
is a random variable obeying a uniform distribution between
, and
is the collection of the top
individuals with the optimal fitness value and maximum quality.
The updated velocity and position can be obtained as:
4.2. Improved Gravitational Search Algorithm (IGSA)
In order to improve the global search capability of GSA and avoid falling into a local optimum, the following four improvement strategies are incorporated in this paper:
Chaos operator.
Chaos [
42] is a seemingly random movement that cannot be repeated precisely that occurs in nature. Chaotic motion is a complex state of motion unique to deterministic nonlinear dynamical systems, it has characteristics such as class randomness, initial value sensitivity, and ergodicity.
Chaos mapping is a mapping (evolutionary function) that exhibits some chaotic behavior, some common chaos mappings include Logistic map, Sinusoidal map, Tent map, Sine map and Bernoulli map.
In this paper, we introduce the chaos operator to improve the GSA by choosing the ergodic logistic mapping, namely:
where control parameters
,
and
,
is the number of chaos generated in the tth iteration.
In the position update phase, chaos sequences are introduced to improve the convergence of the algorithm, while chaos perturbations can help individuals escape from their current position when they fall into a local optimum. The steps are as follows:
(1) A d-dimensional random vector is generated, and the control parameter , that is a fully chaos state is reached by Equation (20): , , generating a chaos vector with denoting the number of individuals;
(2) The generated chaos vector is added to the search space, at which point the speed update equation in the improved algorithm is:
where
is the factor that controls the range of chaos;
(3) Using the improved velocity update equation to calculate the position at the next moment:
Adaptive universal gravitational constant decay factor.
From the gravitational force calculation Equation (16), we can see that the universal gravitational constant
is positively related to the gravitational force value, and its value plays an important role in the calculation of the gravitational force. When
takes a larger value, the search range of the algorithm is wider to avoid falling into the local optimum, while when
takes a smaller value, the algorithm can better converge to the global optimum. From Equation (17), it can be seen that the universal gravitational constant decay factor
in the standard GSA is taken as a constant, which limits the performance of the algorithm. Therefore, an adaptive universal gravitational constant decay factor is proposed:
where
is the initial value of the gravitational decay factor,
and
are scaling factors,
,
,
is the shift factor, which is taken in this paper as
,
,
0,
.
As the number of iterations increases, the universal gravitational constant shows a nonlinear decrease, then the improved algorithm has a large gravitational constant at the beginning to enhance the search ability, and the algorithm reduces the gravitational constant at the later stage to accelerate the convergence of the algorithm.
Elastic ball boundary treatment.
Boundary constraints are added when initializing individuals, but as the iteration proceeds, there may be individuals that cross the boundary after the position update, and for the individuals that cross the boundary, the elastic ball boundary is handled by:
It can be seen from Equation (24) that the elastic ball boundary treatment increases the individual positions, enhances the search capability of the algorithm, and reduces the risk of the algorithm falling into a local optimum.
Elite Guidance.
The velocity update formula of GSA only considers the effect of acceleration, while the velocity update in the particle swarm seeking algorithm takes into account the individual memory and group information exchange, it is more convergent for particle seeking. Therefore, the velocity update of IGSA combined with the chaos arithmetic and PSO velocity update mechanism is obtained:
where
,
are the adaptive learning factors that vary with the number of iterations,
and
denote the individual optimal position and the global optimal position in the d-dimensions, respectively.
Because the addition of the optimal position in the velocity update equation will reduce the search capability of the algorithm, the adaptive learning factor is added to balance the global search capability and local optimization capability of the algorithm.
,
update equations [
43] are:
Based on the above improvement strategies, a new improved gravitational search algorithm (IGSA) is proposed in this paper with the following steps:
Step 1: Random initialization of the population and setting parameters. The setup parameters include the population size N, the maximum number of iterations T, the boundary of the position , the initial value of the universal gravitational force and the initial value of the gravitational decay factor . The population individual positions are randomly initialized.
Step 2: It is determined whether the updated individual position is out of bounds. The transgression uses the elastic ball boundary strategy of Equation (24) to assign a new position.
Step 3: Calculate the fitness value of all individuals in the population, and determine whether the fitness value is NaN (Not A Number) or not, if it is, then randomly initialize the position of the individual and calculate the fitness value again, and repeat this step until the fitness value is an output table value.
Step 4: Update global optimal position and individual optimal position , if < , then = , = .
Step 5: Calculating the individual mass , the gravitational parameter is calculated according to Equations (17) and (23), the gravitational force is calculated according to Equations (16) and (18), finally calculating the acceleration .
Step 6: The adaptive learning factor is calculated according to Equations (26), and the speed and position are updated according to Equations (25) and (19).
Step 7: The number of iterations , if , go to step 2, otherwise end the loop and obtain the optimal objective function value and the optimal position vector .
The algorithm flow chart of IGSA is indicated in
Figure 4: