A Fast Discrete Gravitational Search Algorithm

Hasrul Che Shamsudin, Addie Irawan, Zuwairie Ibrahim

Faculty of Electrical and Electronics Engineering Universiti Malaysia Pahang

26600 Pekan, Malaysia hasrulcheshamsudin@yahoo.com,

addieirawan@ump.edu.my, zuwairie@ump.edu.my

Amar Faiz Zainal Abidin, Sophan Wahyudi, Muhammad Arif Abdul Rahim, Kamal Khalil

Faculty of Electrical Engineering Universiti Teknologi Malaysia

81310 UTM Skudai, Johor amarfaiz@fke.utm.my, sophan@fke.utm.my,

arif@fke.utm.my, kamal@fke.utm.my

Abstract—This study introduces a variant of Gravitational Search Algorithm (GSA) for discrete optimization problems, namely, Fast Discrete Gravitational Search Algorithm (FDGSA). The main difference between the proposed FDGSA and the existing Binary Gravitational Search Algorithm (BGSA) is that an agent’s position is updated based on its direction and velocity. Both the direction and velocity determine the candidates of integer values for the position update of an agent and then the selection is done randomly. Unimodal test functions, such as De Jong’s function, Scwefel’s function and Rosenbrock’s valley are used to evaluate the performance of the proposed FDGSA. Comparison with BGSA is done to benchmark the proposed FDGSA in terms of speed of convergence and quality of solution. The experimental result shows that the proposed FDGSA converges faster compared to the BGSA.

Keywords-GSA; discrete optimization; FGSA

I. INTRODUCTION Gravitational Search Algorithm (GSA) has been

originally proposed by Rashedi et al. in 2009 [1]. The idea of GSA came from the Newtonian laws of gravitation and motion where all objects move as a result of attraction with each other by gravitational forces. Objects with heavier mass have stronger attraction and move slower than the objects with relatively smaller mass. Results in [1] showed that GSA performed considerably better compared to Particle Swarm Optimization (PSO) [2] and Central Force Optimization (CFO) [3].

However, the potentials of GSA in solving discrete optimization problems have not been fully explored. Therefore, in this study, a new Fast Discrete Gravitational Search Algorithm (FDGSA) is proposed to solve discrete optimization problems. In FDGSA, an agent’s position is updated based on its direction and velocity. The information related to the direction and velocity of an agent is used to determine the candidates of integer values for the position update. After that, the selection is done randomly.

The rest of this paper is organized as follows; Section 2 describes the original GSA and binary GSA algorithms. Then, the proposed FDGSA is explained in Section 3. Section 4 introduces the benchmark test functions, presents

the experimental results and discussions. Finally, Section 5 summarizes this paper.

II. GRAVITATIONAL BASED ALGORITHMS FOR OPTIMIZATION PROBLEMS

A. Gravitational Searh Algorithm Assume each agent’s position in the searching space can

be represented by

( )niiiii xxxxX ...,,, 321= for i = 1, 2, 3,…. , N (1)

where N presents the number of agents and the position of ith agents in the dth dimension can be represented as d

ix . The value of agent is calculated for updating each ith

agent with reference to the equality of gravitational and inertia mass assumption ( )iiipiai MMMM === as follows:

( ) ( )( )� =

= N

j j

ii

tmtmtM

1

(2)

( ) ( ) ( )( ) ( )tworsttbest

tworsttfittm ii −

−= (3)

For minimization problem, the definition of best(t) and worst(t) are as follows:

( ) { } ( )tfittbest jNj ,....,1min ∈= (4)

( ) { } ( )tfittworst jNj ,....,1max ∈= (5) The fitness value, fiti(t) affects the mass value of ith agents, which corresponds to the position of the particle in a search space.

The general principle of GSA is shown in Figure 1. The optimization process started with positioning the agents randomly with random velocity values and initialization of gravitational constant.

2012 Fourth International Conference on Computational Intelligence, Modelling and Simulation

2166-8531/12 $26.00 © 2012 IEEE

DOI 10.1109/CIMSim.2012.28

24

Figure 1. Flowchart of Gravitational Searh Algorithm [1].

The next step is to evaluate the fitness, fiti(t), of each agent according to the objective function. Then, the gravitational constant, G(t), is updated based on (6) due to the effect of decreasing gravity. The best and the worst values of the population are calculated using (4) and (5).

( ) ( ) 1, <��

���

�×= ββ

tt

tGtG oo

(6)

Mass, M, for each agent is calculated using (2) and (3), and acceleration, α , is calculated using ( ) ( )tFt d

idi =α ,

where the force acting is calculated as follows:

( ) ( )� ≠== N

ijjd

ijjd

i tFrandtF,1

(7)

( ) ( ) ( )( ) ( ) ( )( )txtxtR

tMtGtF d

idj

ij

ajdij −

+=

ε (8)

where ajM is the active gravitational mass related to agent

j, ε is a small constant, ijR is the distance between agent i and j and randj is a uniform random variable in the interval [0,1]. Then, the velocity, i

dv , and position, idx , of ith agents

is calculated as follows:

( ) ( ) ( )ttvrandtv di

dii

di α+×=+1 (9)

TABLE I. EIGHT BITS BINARY MODELING

Bit Sign

07 +/-

06 26 =64

05 25 = 32

04 24 = 16

03 23 = 8

02 22 = 4

01 21 = 2

00 20 = 1

( ) ( ) ( )11 ++=+ tvtxtx di

di

di (10)

where irand is a uniform random variable in the interval [0,1]. This updating process is repeated as long as the stopping criterion is not satisfied.

B. Binary Gravitational Search Algorithm In BGSA [4], the position update is modified to

accommodate with binary search space. Bit exchanged is based on (11), as for small d

iv the probability of changes of an agent’s position must be near zero or vice versa.

( )( ) ( )( )tvtvS di

di tanh1 =+ (11)

Moreover, the agent’s velocity is normalized as follows:

if ( )( )1=< tvSrand di (12)

then ( ) =+1txdi complement ( )( )tx d

i

else ( ) ( )txtx di

di =+1

In [4], eight bits binary representation is used to represent

discrete values, where the 7th bit is used to indicate the sign of a number. The modeling used to implement BGSA is shown in Table I. The velocity is limited to maxvvd

i < , where vmax value is 6 and the distance between agents is calculated based on the Hamming distance.

III. THE PROPOSED FAST DISCRETE GRAVITATIONAL SEARCH ALGORITHM (FDGSA)

In FDGSA, all the steps in GSA are similar but new approach is proposed to update agent’s position, as in the following:

• The direction and velocity of an agent will determine the candidate of the next position.

25

• Agent moves in the positive direction if the velocity value is positive or negative direction if the velocity is negative.

• Position update is done randomly based on the candidate of the next position.

Consider an ith agent, which current position in dth dimension, xi

d t( ) = 120, as shown in Figure 2. Let say the

velocity vid t +1( ) = 160. The candidates of the next

position, xid t +1( ) are 120, 121, 122, ….., and 280. The

next position will be an integer, randomly chosen between 120 and 280.

Based on these new concepts, while the velocity update is still the same, which is shown in (9), the position update can be formulated as follows:

if ( )( ) 01 >+tvd

i (13)

( ) ( ) ( ) ( ) ( ) ( )( )1,....,2,1,1 ++++=+ tvtxtxtxtxrandomtx di

di

di

di

di

di

if ( )( ) 01 <+tvd

i (14) xi

d t +1( ) = random xid t( ), xi

d t( ) −1, xid t( ) − 2,...., xi

d t( ) − vid t +1( )( )

Equation (13) is used if the velocity is positive and (14) is used is the velocity is negative.

IV. EXPERIMENTS, RESULTS AND DISCUSSIONS The benchmark functions are taken from [4]. Six

functions were selected in this study, is shown in Table II. For the simple unimodal functions, the convergence rates analysis is more important that the results of optimization. F5 is chosen to evaluate the performance of the proposed algorithm for a function in which the next agent’s position affecting the fitness value. F6 is the benchmark function with 0.5 decimal value that used to seek the best solution can be found by FDGSA.

The results of the proposed FDGSA is compared against the existing BGSA. Initial setting parameters used for both FDGSA and BGSA are shown in Table III. The population size is set to 50 (N = 50) and dimension is five (i = 5) for all benchmark functions. Table IV shows the the solution produced by the proposed algorithm. At the first run, even though the number of iterations is 500, the best so far solution is found before 100 iterations. In particular, iteration 31st for F1, iteration 73th for F2, iteration 48th for F3, iteration 34th for F4, iteration 86th for F5 and iteration 23rd for F6. Accurate solutions have been found for F1, F2, F3 and F4.

Figure 2. Identification of the Candidates of the Next Position.

TABLE II. UNIMODAL TEST FUNCTIONS

Test Function S

( ) �=

=m

iixxF

1

21

[-100, 100]m

( ) ∏�==

+=m

ii

m

ii xxxF

112

[-10, 10]m

( ) � �= =

���

����

�=

m

i

i

jjxxF

1

2

13

[-100, 100]m

( ) { }mixxF ii

≤≤= 1,max4 [-100, 100]m

( ) ( ) ( )[ ]�−

=+ −+−=

1

1

22215 1100

m

iiii xxxxF

[-30, 30]m

( ) [ ]( )�=

+=m

iixxF

1

26 5.0 [-100, 100]m

TABLE III. INITIAL PARAMETERS FOR FDGSA AND BGSA

Number of agents, N 50

Number of dimensions, i 5

Gravitational constant, G(t0) 100

Bheta, 0.7

Epsilon, 10

Number of iteration 500

TABLE IV. THE QUALITY OF SOLUTION FOR FDGSA FOUND AT FIRST RUN

Benchmark BSF x1 x2 x3 x4 x5

F1 0 0 0 0 0 0

F2 0 0 0 0 0 0

F3 0 0 0 0 0 0

F4 0 0 0 0 0 0

F5 4 -1 1 1 1 1

F6 1.25 -1 -1 0 -1 0

26

The average convergence rate of FDGSA and BGSA is shown in Table V, based on the results obtained after 30 runs. It is found that both algorithms have successfully obtained accurate solutions for all functions but in average, the proposed FDGSA converges considerably faster than BGSA. The standard deviations for F1, F4, F5 and F6 demostrate that FDGSA provides more consistent convergence while BGSA is more consistent for other two benchmark functions. Figure 3 shows some examples of convergence curves of both FDGSA and BGSA.

V. CONCLUSION The proposed FDGSA that can accelerate the

optimization process had been successfully validated and analyzed. According to the overall results, the proposed algorithm enables to speed up the searching process faster than BGSA on decay discrete optimization solution via proposed agent’s position updating technique based on the velocity value and polarity for the existing GSA. Therefore on the future works, the proposed FDGSA method will be implemented on solving a deficiency of existing BGSA which is involving a high dimensional bit.

ACKNOWLEDGMENT The authors are grateful to the Ministry of Higher

Education (MOHE) and Universiti Teknologi Malaysia (UTM) for the financial support through the Fundamental Research Grant Scheme (FGRS) (Vote 4F032). The first author is thankful to Universiti Malaysia Pahang (UMP) for granting him an opportunity to further his study in PhD degree.

REFERENCES [1] Esmat Rashedi, Hossien Nezamabadi-pour, and Saied Saryazdi,

“GSA: A Gravitational Search Algorithm,” Information Sciences, vol. 179, pp. 2232-2248, 2009.

[2] Kennedy, J., and Eberhart, R.C., “Particle Swarm Optimization,” In: Proceedings of IEEE International Conference on Neural Networks, vol. 4, pp. 1942-1948,1995.

[3] R. A. Formato, “Central force optimization: a new nature inspired computational framework for multidimensional search and optimization,” Studies in Computational Intelligence, vol. 129, pp. 221-238, 2008.

[4] Esmat Rashedi, Hossien Nezamabadi-pour, and Saied Saryazdi, “BGSA: binary gravitational search algorithm,” Nat Comput, vol. 9, pp. 727-745, 2010.

TABLE V. COMPARISON BASED ON THE SPEED OF CONVERGENCE

Benchmark Performance Measure FDGSA BGSA F1 Mean 30.3667 274.1667

Median 30 277

Min 21 254

Max 38 293

Standard Deviation 3.6811 9.8579 F2 Mean 61.9333 303.8667

Median 59.5 307

Min 29 278

Max 106 320

Standard Deviation 20.902 9.8462 F3 Mean 57.5 262.8333

Median 56 262

Min 25 247

Max 99 262

Standard Deviation 19.7095 6.5024 F4 Mean 32.9333 273.4

Median 32 272

Min 25 253

Max 43 296

Standard Deviation 5.1256 10.1696 F5 Mean 76.2667 300.8

Median 78 298.5

Min 35 274

Max 106 358

Standard Deviation 16.1094 19.897 F6 Mean 27.5 263.5333

Median 27 263.5

Min 20 239

Max 36 278

Standard Deviation 3.4815 8.8268

27

Figure 3. Examples of Convergence Curves: FDGSA vs BGSA (a) F1, (b) F2, (c) F3, (d) F4, (e) F5, (f) F6.

(a)

(c)

(e)

(b)

(d)

(f)

28