Grasshopper Optimization Algorithm (GOA): Propelled from Swarming Behavior of Grasshoppers for Solving Optimization Problems

1. Introduction

     Grasshopper Optimization Algorithm (GOA) is an optimization technique introduced by Saremi, Mirjalili and Lewis in 2017. It includes both social interaction between ordinary agents (grasshoppers) and the attraction of the best individual. Initial experiments performed by authors demonstrated promising exploration abilities of the GOA and they will be further examined in the course of our study [1]. The goal of this contribution is to evaluate clustering method which uses GOA as the optimization strategy aimed at minimizing the value of Calinski-Harabasz index one of internal clustering validity measures. Cluster analysis constitutes a data mining problem of identifying homogeneous groups in data. Clustering can be perceived as combinatorial optimization problem which is known to be NP-hard. It is the reason why diverse heuristic approaches have been already used to tackle it. As a point of reference classic K-means algorithm can be named. It is founded on minimizing the within cluster sum of squares (WCSS) and its main drawback is a convergence to a local minimum of WCSS value  without a guarantee of obtaining the global one [2]. That is why more up-to-date approaches are based on using metaheuristic techniques to solve clustering problem in the alternative way. Previous work in this area involve the use of for instance Flower Pollination Algorithm [9] and Krill Herd Algorithm. The importance of clustering manifests itself through a variety of disciplines where its instances appear, e.g. in agriculture, automatic control, marketing or text mining [3].

2. Life Cycle of Grasshopper Optimization Algorithm

The grasshopper is a flying animal belonging to order Orthoptera and class Insecta. About 11,000 species exist. They are herbivorous and commonly seen in autumn; a few appear in summer and spring. During mating the male grasshopper deposits sperm into the female’s vagina, which finds its way to the eggs through canals known as micropyles [4]. An adult grasshopper goes through the stages egg, nymph and adult, and has a lifespan of approximately one year. This is the initial stage of a grasshopper’s life cycle. The mother grasshopper lays fertilized eggs in midsummer, and they remain 1 or 2 inches under the sand or in leaf litter. She sprinkles them with a sticky semisolid substance that sets to form an egg pod. Each egg pod contains 15 to 150 eggs, depending on the species. Normally a female grasshopper can lay up to 25 pods. The eggs remain underneath for about 10 months in autumn and winter before hatching into nymphs during spring or in the initial days of summer. This is the second stage of the grasshopper’s life cycle and the initial stage during which a young grasshopper sees the outside world [5]. Nymphs look like adult grasshoppers, called molts, apart from the fact that they are wingless and lack reproductive organs. They undergo five substages known as instars before fully developing into adult grasshoppers; each instar is characterized by shedding of the cuticle skin and gradual growth of wings. Molting takes place during the nymph stage. The locust sheds its exoskeleton before maturing into an adult. While the exoskeleton covers the nymph’s body, providing it with protection against external injuries, it inhibits its growth because of its rigidity and inability to give room for expansion. The nymph has to shed it in order to achieve growth. It undergoes five to six molts in which it changes its structure and form before reaching adulthood [6].

This is a fully grown grasshopper. It takes about one month before the wings are fully developed. The mature grasshopper is more mobile than the nymph, a characteristic that helps them to hunt and flee from predators. The reproductive organs are fully grown, so the females can lay eggs and the males can fertilize. However, female grasshoppers do not lay eggs until they are 1 or 2 weeks old, to allow them to gain enough weight before they start laying eggs. Once she starts laying eggs, the female continues to lay eggs at intervals of three to four days until she dies. Adult grasshoppers live for about two months, depending on the weather [7].

3. Grasshopper Optimization Algorithm

         Grasshopper are considered a pest due to their damage to crop production and agriculture. Although grasshoppers are usually seen individually in nature, they join in one of the largest swarm of all creatures. The size of the swarm may be of continen- tal scale and a nightmare for farmers. The unique aspect of the grasshopper swarm is that the swarming behaviour is found in both nymph and adulthood. Millions of nymph grasshoppers jump and move like rolling cylinders. In their path, they eat almost all vegetation [8]. After this behaviour, when they become adult, they form a swarm in the air. This is how grasshoppers migrate over large distances. The main characteristic of the swarm in the larval phase is slow movement and small steps of the grasshoppers. In contrast, long range and abrupt movement is the essential feature of the swarm in adulthood. Food source seeking is another important characteristic of the swarming of grasshoppers [9]. As discussed in the intro duction, nature-inspired algorithms logically divide the search process into two tendencies: exploration and exploitation. In explo- ration, the search agents are encouraged to move abruptly, while they tend to move locally during exploitation. These two functions, as well as target seeking, are performed by grasshoppers naturally. Therefore, if we find a way to mathematically model this be- haviour, we can design a new nature-inspired algorithm [10].

4. Steps for GOA

• Initialization
• Initial population and evaluation
• Assigning the overall beat solution
• Updating the decreasing coefficient parameter
• Mapping the distance of grasshoppers
• Updating solution
• Solution bounderies violation
• Visiting all the solutions in population
• Solutions evaluations
• Termination criteria
• Returning the best solution

4.1. Initialization

     The  algorithm starts by setting the initial values of the maximum and minimum values of the decreasing coefficient parameter, cmax, cmin respectively, the parameters and the maximum number of iterations matrix [11].

4.2. Initial population and evaluation

      The initial population is generated randomly and each solutions in the population is evaluated by calculating its value by using the objective function.

4.3. Assigning the overall best solution

     After evaluating all the solutions in the initial population, the overall (global) best solution is assigned according to its value [12].

4.4. Updating the decreasing coefficient parameter

      At each iteration, the coefficient parameter is updating in order to shrink the comfort, repulsion and attraction zones.

4.5. Mapping the distance of grasshoppers

      The function is responsible for dividing the search space into comfort, repulsion and attraction zones, however its ability decreases to zero when the distance between two grasshoppers is greater than 10.

       Inorder to solve this problem the distance between the grasshopper mapped to the interval [13].

4.6. Updating solution

      Each solution in the population is updated based on the distance between it and the solutions, the decreasing coefficient parameter and the global best solution in the population [14].

4.7. Solution bounderies violation

       After updating the solution, if it violates its upper and lower boundaries, it rests to its domain.

4.8. Visiting all the solutions in population

       The previous three steps are repeated for all the solutions in the populations

4.9. Solutions evaluations

       The solutions in the population are updated and evaluated and the best global solution is assigned.

4.10. Termination criteria

        The overall operations are repeated until reaching to the maximum number of iterations matrix which is the termination criterion in our work [15].

4.11. Returning the best solution

       The best global solution is returned when the algorithm reaches to its maximum number of iteration.

5. Flowchart of GOA

6. Numerical method for GOA

  This structural design problem is one of the most widely-used case studies in the literature [16]. This problem is formulated as follows:

7. Applications of GOA

• Solving structural design problem[17]
• Bar truss design
• Military reconnaissance for street fighting[18]
• Feature selection
• Tracking mission

8. Advantages of GOA

• While grasshoppers can do significant damage to a farmer’s crops, without these insects the ecosystem would be a much different place [19].
• They play a critical role in the environment, making it a safer and more efficient place for plants and other animals to thrive.
• The grasshopper benefits humans and the ecosystem in general by facilitating plant decomposition and regrowth, creating a balance between the types of plants that thrive.
• The grasshopper benefits the ecosystem by facilitating plant growth, as evidenced by his ability to noticeably change the types of plants that thrive in his environment [20].
• The reduced size of the waste allows microbes to break it down more efficiently, fertilizing the soil faster [21].
• While the grasshopper may not appreciate this particular role that he plays in the ecosystem, he is a vital source of food for predators in the wild.
• While the insect’s appetite can wreak havoc on farm crops, in general, it also benefits the environment by maintaining optimal levels of plant growth.

Reference

[1] Mirjalili, S., Saremi, S., Faris, H. and Aljarah, I. (2017). Grasshopper optimization algorithm for multi-objective optimization problems. Applied Intelligence, 48(4), pp.805-820.

[2] Wu, J., Wang, H., Li, N., Yao, P., Huang, Y., Su, Z. and Yu, Y. (2017). Distributed trajectory optimization for multiple solar-powered UAVs target tracking in urban environment by Adaptive Grasshopper Optimization Algorithm. Aerospace Science and Technology, 70, pp.497-510.

[3] Aljarah, I., Al-Zoubi, A., Faris, H., Hassonah, M., Mirjalili, S. and Saadeh, H. (2018). Simultaneous Feature Selection and Support Vector Machine Optimization Using the Grasshopper Optimization Algorithm. Cognitive Computation, 10(3), pp.478-495.

[4] Zhang, X., Miao, Q., Zhang, H. and Wang, L. (2018). A parameter-adaptive VMD method based on grasshopper optimization algorithm to analyze vibration signals from rotating machinery. Mechanical Systems and Signal Processing, 108, pp.58-72.

[5] Saremi, S., Mirjalili, S. and Lewis, A. (2017). Grasshopper Optimisation Algorithm: Theory and application. Advances in Engineering Software, 105, pp.30-47.

[6] Mafarja, M., Aljarah, I., Heidari, A., Hammouri, A., Faris, H., Al-Zoubi, A. and Mirjalili, S. (2018). Evolutionary Population Dynamics and Grasshopper Optimization approaches for feature selection problems. Knowledge-Based Systems, 145, pp.25-45.

[7] Heidari, A., Faris, H., Aljarah, I. and Mirjalili, S. (2018). An efficient hybrid multilayer perceptron neural network with grasshopper optimization. Soft Computing.

[8] Arora, S. and Anand, P. (2018). Chaotic grasshopper optimization algorithm for global optimization. Neural Computing and Applications.

[9] Hekimoğlu, B. (2018). Sine-cosine algorithm-based optimization for automatic voltage regulator system. Transactions of the Institute of Measurement and Control, 41(6), pp.1761-1771.

[10] Liu, J., Wang, A., Qu, Y. and Wang, W. (2018). Coordinated Operation of Multi-Integrated Energy System Based on Linear Weighted Sum and Grasshopper Optimization Algorithm. IEEE Access, 6, pp.42186-42195.

[11] Fathy, A. (2018). Recent meta-heuristic grasshopper optimization algorithm for optimal reconfiguration of partially shaded PV array. Solar Energy, 171, pp.638-651.

[12] Liang, H., Jia, H., Xing, Z., Ma, J. and Peng, X. (2019). Modified Grasshopper Algorithm-Based Multilevel Thresholding for Color Image Segmentation. IEEE Access, 7, pp.11258-11295.

[13] Sultana, U., Khairuddin, A., Sultana, B., Rasheed, N., Qazi, S. and Malik, N. (2018). Placement and sizing of multiple distributed generation and battery swapping stations using grasshopper optimizer algorithm. Energy, 165, pp.408-421.

[14] Kim, D. (2018). Active Sonar Target Classification Using Multi-aspect based Sensing and Deep Belief Network. The Asia-Pacific Journal of Neural Networks and Its Applications, 2(2), pp.1-6.

[15] Bandic, L., Nalo, N. and Kevric, J. (2019). Optimal Network Reconfiguration of the Distribution Network for Minimization of Power Loss and Voltage Deviation using NSGA-II Algorithm. Journal of Natural Sciences and Engineering, 1(1).

[16] Zakeri, A. and Hokmabadi, A. (2019). Efficient feature selection method using real-valued grasshopper optimization algorithm. Expert Systems with Applications, 119, pp.61-72.

[17] Amaireh, A., Al-Zoubi, A. and Dib, N. (2019). Sidelobe-Level Suppression For Circular Antenna Array Via New Hybrid Optimization Algorithm Based On Antlion And Grasshopper Optimization Algorithms. Progress In Electromagnetics Research C, 93, pp.49-63.

[18] Thabit, S. and Mohades, A. (2019). Multi-Robot Path Planning Based on Multi-Objective Grasshopper Optimization Algorithm. IEEE Access, 7, pp.2138-2147.

[19] Bhadoria, A. and Kamboj, V. (2018). Optimal generation scheduling and dispatch of thermal generating units considering impact of wind penetration using Grasshopper Optimization algorithm. Applied Intelligence, 49(4), pp.1517-1547.

[20] Mozaffari Legha, M., Javaheri, H. and Mozaffari Legha, M. (2013). Optimal Conductor Selection in Radial Distribution Systems for Productivity Improvement Using Grasshopper Optimization Algorithm. Iraqi Journal for Electrical And Electronic Engineering, 9(1), pp.29-35.

[21] Nosratabadi, S., Bornapour, M. and Gharaei, M. (2019). Grasshopper optimization algorithm for optimal load frequency control considering Predictive Functional Modified PID controller in restructured multi-resource multi-area power system with Redox Flow Battery units. Control Engineering Practice, 89, pp.204-227.