Gravitational Search Algorithm (GSA) in view of Newton’s Law of Gravitation

1. Introduction

         Gravitational Search Algorithm (GSA) is a population search algorithm proposed by Rashedi et al. in 2009. A gravitational search algorithm is based on the law of gravity and the notion of mass interactions. The GSA algorithm uses the theory of Newtonian physics and its searcher agents are the collection of masses. In GSA, there is an isolated system of masses. Using the gravitational force, every mass in the system can see the situation of other masses. The gravitational force is therefore a way of transferring information between different masses (Rashedi, Nezamabadi-pour and Saryazdi 2009). In GSA, agents are considered as objects and their performance is measured by their masses [1]. All these objects attract each other by a gravity force, and this force causes movement of all objects towards the objects with heavier masses. Heavier masses correspond to better solutions of the problem. The position of the agent corresponds to a solution of the problem, and its mass is determined using a fitness function. By lapse of time, masses are attracted by the heaviest mass, which would ideally present an optimum solution in the search space [2]. The GSA could be considered as an isolated system of masses. It is like a small artificial world of masses obeying the Newtonian laws of gravitation and motion. A multi-objective variant of GSA, called MOGSA, was first proposed by Hassanzadeh et al. in 2010 [3].

2. Gravitational Search Algorithm

          GSA is based on the low of gravity and mass interactions. The solutions in the GSA population are called agents, these agents interact with each other through the gravity force. The performance of each agent in the population is measured by its mass. Each agent is considered as object and all object move towards other object with heavier mass due to the gravity force. This step represents a global movements (exploration step) of the object, While the agent with a heavy mass moves slowly, which represents the exploitation step of the algorithm. The best solution is the solution with the heavier mass [4]. Gravitational Search Algorithm (GSA) is one of the recent nature inspired algorithms which is capable to solve optimization problems. GSA is inspired by the Newtonian’s law of gravity and the law of motion. The aim of the paper is to investigate GSA utilization in various optimization problems. The paper provides a brief explanation on GSA and also presents the previous optimization works based on GSA. Based on the literature, GSA is capable of providing more accurate, effective and robust high-quality solution for most of the optimization problems [5]. The algorithm has been applied in various applications and has solved various optimization problems such as in power system, controller design, network routing, sensor networks, software design and many more. GSA has been adapted in the optimization of parameters, settings, strategies, cost, voltage control and also power dispatch. The algorithm also has been adapted to optimize the design of controllers, software, antenna and micro grids [7]. Based on previous works, GSA has showed better performance in solving the optimization problems compared to other previous algorithms such as PSO, ACO and ABC. It is expected that more studies are to be done based on GSA in future as the algorithm has a high potential to solve various optimization problems in different areas [8].

2.1. Inspiration of GSA

Newton’s law of universal gravitation states that every particle attracts every other particle in the universe with a force which is directly proportional to the product of their masses and inversely proportional to the square of the distance between their centers. This is a general physical law derived from empirical observations by what Isaac Newton called inductive reasoning. It is a part of classical mechanics and was formulated in Newton’s work Philosophiæ Naturalis Principia Mathematica (“the Principia”), first published on 5 July 1687. When Newton presented Book 1 of the unpublished text in April 1686 to the Royal Society, Robert Hooke made a claim that Newton had obtained the inverse square law from him [9]. In today’s language, the law states that every point mass attracts every other point mass by a force acting along the line intersecting the two points. The force is proportional to the product of the two masses, and inversely proportional to the square of the distance between them [10].

The equation for universal gravitation thus takes the form:

2.2 Process of GSA

           The gravitational search algorithm should make the moving particle in space into an object with a certain mass. These objects are attracted through gravitational interaction between each other, and each particle in the space will be attracted by the mutual attraction of particles to produce accelerations. Each particle is attracted by the other particles and moves in the direction of the force [11]. The particles with small mass move to the particles with great mass, so the optimal solution is obtained by using the large particles. The gravitation search algorithm can realize the information transmission through the interaction between particles. Then M₁, M₂, M₃ and M₄ are mass values, F₁, F₂, F₃ and F₄ are forces [12].

2.3. Steps for GSA

• Agents  Initialization
• Fitness evolution & Best fitness computation
• Gravitational constant computation
• Masses of the agents calculation

2.3.1. Agents Initialization

         All agents are randomly initialized. Each agent is considered as a candidate solution. In order for a stability analysis to be meaningful and reliable, it is of paramount importance that one can specify equilibrium initial conditions. After all, if the initial disc is not in equilibrium, its relaxation during the first time-steps of the simulation may trigger instabilities that are of little relevance for our understanding of the stability of disc galaxies [13]. Unfortunately, no analytical solution is known for the density, velocity field and temperature of a three-dimensional gas disc in hydrostatic equilibrium in the external potential of a dark matter halo and/or a stellar disc. Consequently, previous   simulations have either started from non-equilibrium initial conditions, or have resorted to iterative techniques to set up the initial conditions, at the cost of having little control over the resulting equilibrium configuration [14].

2.3.2. Fitness evolution & Best fitness computation

          The robustness and effectiveness of a swarm based meta-heuristic algorithms depend upon the balance between exploration and exploitation capabilities. In the initial iterations of the solution search process, exploration of search space is preferred. This can be obtained by allowing to attain large step sizes by agents during early iterations. In the later iterations, exploitation of search space is required to avoid the situation of skipping the global optima. Thus the candidate solutions should have small step sizes for exploitation in later iterations [15].

2.3.3. Gravitational constant computation

          The gravitational constant (also known as the “universal gravitational constant”, the “Newtonian constant of gravitation”, or the “Cavendish gravitational constant”),[a] denoted by the letter G, is an empirical physical constant involved in the calculation of gravitational effects in Sir Isaac Newton’s law of universal gravitation and in Albert Einstein’s general theory of relativity. In Newton’s law, it is the proportionality constant connecting the gravitational force between two bodies with the product of their masses and the inverse square of their distance. In the Einstein field equations, it quantifies the relation between the geometry of space time and the energy–momentum tensor [16].

2.3.4. Masses of the agent’s calculation

             Mass (m) is the amount of matter present in a substance. The value is constant and, unlike weight, is not affected by gravity [17]. Mass, molar concentration, volume, and formula weight are related to each other as follows:

  Mass (g) = Concentration (mol/L) * Volume (L) * Formula Weight (g/mol)

2.4. Flow Chart

2.5. Numerical Example for GSA

Step1: Initialize

        Firstly, randomly generate the positions x1i,x2i,…,xk_i,…xd_i of N objects, and then the positions of N objects are brought into the function, where the position of the _ith object are defined as follows.

Step2: Calculate the inertia mass

          Each particle with certain mass has inertia. The greater the mass, the greater the inertia. The inertia mass of the particles is related to the self-adaptation degree according to its position. So the inertia mass can be calculated according to the self-adaptation degree. The bigger the inertial mass, the greater the attraction. This point means that the optimal solution can be obtained. At the moment t, the mass of the particle Xi is represented as Mi(t). Mass Mi(t) can be calculated by the followed equation [18].

3. Applications of GSA

• Inverse square law [19]
• Binary Orbits
• Circular Orbits
• Jupiter  effect
• Sun Tidal effect
• Gene regulating network
• Communication satellite link optimization [20]
• Reactive power  dispatch
• Acceleration of Gravity
• Producing the Tides
• Potential energy
• Determine Escape velocity

4. Advantages of GSA

1. Earth’s gravity we are able to stay on the top of it and other creatures as well.

2. Gravity there is a waterfall by which we can use it to produce energy [21].

3. Gravity there is rain that pours on our land.

4. Gravity is a “constant force” which keeps things in place.

5. Gravity keeps our muscles and bones, up and working.

6. Gravity allows earth to retain its atmosphere.

7. Gravity, being able to store its energy as “potential energy”, allows us to harness it. E.g.: water dams [22].

Reference

[1] B. ., “Gravitational Search Algorithm With Chaotic Map (Gsa-Cm) For Solving Optimization Problems”, International Journal of Research in Engineering and Technology, vol. 05, no. 02, pp. 204-212, 2016.

[2] K. Ing, H. Mokhlis, H. Illias, M. Aman and J. Jamian, “Gravitational Search Algorithm and Selection Approach for Optimal Distribution Network Configuration Based on Daily Photovoltaic and Loading Variation”, Journal of Applied Mathematics, vol. 2015, pp. 1-11, 2015.

[3] S. Smith, “Algorithm to search for gravitational radiation from coalescing binaries”, Physical Review D, vol. 36, no. 10, pp. 2901-2904, 1987.

[4] T. Eldos and R. Al, “On The Performance of the Gravitational Search Algorithm”, International Journal of Advanced Computer Science and Applications, vol. 4, no. 8, 2013.

[5] N. Siddique and H. Adeli, “Gravitational Search Algorithm and Its Variants”, International Journal of Pattern Recognition and Artificial Intelligence, vol. 30, no. 08, p. 1639001, 2016.

[6] Y. kumar and G. Sahoo, “A Review on Gravitational Search Algorithm and its Applications to Data Clustering & Classification”, International Journal of Intelligent Systems and Applications, vol. 6, no. 6, pp. 79-93, 2014.

[7] A. Gandomi, A. Kashani and F. Zeighami, “Retaining wall optimization using interior search algorithm with different bound constraint handling”, International Journal for Numerical and Analytical Methods in Geomechanics, vol. 41, no. 11, pp. 1304-1331, 2017.

[8] K. Ing, H. Mokhlis, H. Illias, J. Jamian and M. Aman, “Optimal Daily Configuration of a Distribution Network Based on Photovoltaic Generation and System Loading Using Imperialist Competitive Algorithm and Selection Approach”, Applied Mechanics and Materials, vol. 785, pp. 541-545, 2015.

[9] B. Dogan, “A Modified Vortex Search Algorithm for Numerical Function Optimization”, International Journal of Artificial Intelligence & Applications, vol. 7, no. 3, pp. 37-54, 2016.

[10] E. Rashedi, H. Nezamabadi-pour and S. Saryazdi, “GSA: A Gravitational Search Algorithm”, Information Sciences, vol. 179, no. 13, pp. 2232-2248, 2009.

[11] D. Pelusi, R. Mascella and L. Tallini, “A Fuzzy Gravitational Search Algorithm to Design Optimal IIR Filters”, Energies, vol. 11, no. 4, p. 736, 2018.

[12] P. P and S. Ratnoo, “Gravitational Search Algorithms in Data Mining: A Survey”, IJARCCE, vol. 6, no. 6, pp. 168-173, 2017.

[13] S. Darzi, M. Islam, S. Tiong, S. Kibria and M. Singh, “Stochastic Leader Gravitational Search Algorithm for Enhanced Adaptive Beam forming Technique”, PLOS ONE, vol. 10, no. 11, p. e0140526, 2015.

[14] E. Rashedi, H. Nezamabadi-pour and S. Saryazdi, “Filter modeling using gravitational search algorithm”, Engineering Applications of Artificial Intelligence, vol. 24, no. 1, pp. 117-122, 2011.

[15] U. Güvenç, Y. Sönmez, S. Duman and N. Yörükeren, “Combined economic and emission dispatch solution using gravitational search algorithm”, Scientia Iranica, vol. 19, no. 6, pp. 1754-1762, 2012.

[16] B. Shaw, V. Mukherjee and S. Ghoshal, “Solution of reactive power dispatch of power systems by an opposition-based gravitational search algorithm”, International Journal of Electrical Power & Energy Systems, vol. 55, pp. 29-40, 2014

[17] P. Jeyanthy and D. Devaraj, “Optimal Reactive Power Dispatch for Voltage Stability Enhancement Using Real Coded Genetic Algorithm”, International Journal of Computer and Electrical Engineering, pp. 734-740, 2010. Available:

[18] M. Dowlatshahi, H. Nezamabadi-pour and M. Mashinchi, “A discrete gravitational search algorithm for solving combinatorial optimization problems”, Information Sciences, vol. 258, pp. 94-107, 2014.

[19] F. Ju and W. Hong, “Application of seasonal SVR with chaotic gravitational search algorithm in electricity forecasting”, Applied Mathematical Modelling, vol. 37, no. 23, pp. 9643-9651, 2013.

[20] F. Barani, M. Mirhosseini and H. Nezamabadi-pour, “Application of binary quantum-inspired gravitational search algorithm in feature subset selection”, Applied Intelligence, vol. 47, no. 2, pp. 304-318, 2017.

[21] S. Golzari, M. Zardehsavar, A. Mousavi, M. Saybani, A. Khalili and S. Shamshirband, “KGSA: A Gravitational Search Algorithm for Multimodal Optimization based on K-Means Niching Technique and a Novel Elitism Strategy”, Open Mathematics, vol. 16, no. 1, pp. 1582-1606, 2018.

[22] J. Wang and J. Song, “Function Optimization and Parameter Performance Analysis Based on Gravitation Search Algorithm”, Algorithms, vol. 9, no. 1, p. 3, 2015.