Krill Herd (KH) Algorithm to solve Numerical Optimization Problem

1. Introduction

      Based on the simulation of the herding behavior of krill individuals, Gandomi and Alavi proposed the krill herd algorithm (KH) in 2012. And KH algorithm is a novel biologically inspired algorithm to solve the optimization problems [1]. In KH algorithm, the objective function for the krill movement is determined by the minimum distances of each individual krill from food and from highest density of the herd. A novel biologically-inspired algorithm, namely krill herd (KH) is proposed for solving optimization tasks. The krill herd algorithm (KHA) is a novel swarm algorithm that is based on the simulation of the herding behavior of krill individuals and the minimum distances of each individual krill from food and from the highest density of the herd, which are considered as the objective functions for krill movement. Although proposed recently, KHA has quickly been applied to multiple scenarios. All of feasible values are available solutions and the extreme value is optimal solution. In general, optimization algorithms are applied to solve optimization problems [2]. A simple classification way for optimization algorithms is considering the nature of the algorithms, and optimization algorithms can be divided into two main categories: deterministic algorithms and stochastic algorithms. Deterministic algorithms using gradient such as hill-climbing have a rigorous move and will generate the same set of solutions if the iterations commence with the same initial starting point. On the other hand, stochastic algorithms without using gradient often generate different solutions even with the same initial value. In order to increase the diversity of the population for KH, a main improvement of adding HS serving as mutation operator is made to the KH with the aim of speeding up convergence, thus making the approach more feasible for a wider range of practical applications while preserving the attractive characteristics of the basic KH [3].

    A new hybrid meta-heuristic algorithm according to the principle of HS and KH, and then an improved KH method is used to search the optimal objective function value. The branch of numerical analysis and applied mathematics that investigates deterministic algorithms that can guarantee convergence in limited time to the true optimal solution of a non-convex problem is called global numerical optimization problems [4]. A variety of algorithms have been proposed to solve non-convex problems. Among them, heuristics algorithms can evaluate approximate solutions to some optimization problems, as described in introduction [5].

2. Life cycle of Krill Herd Algorithm

Fig 1: Life Cycle of Krill

      Krill are small crustaceans of the order Euphausiacea, and are found in all the world’s oceans. The name “krill” comes from the Norwegian word krill, meaning “small fry of fish”, which is also often attributed to species of fish. Krill are considered an important trophic level connection – near the bottom of the food chain – because they feed on phytoplankton and (to a lesser extent) zooplankton, converting these into a form suitable for many larger animals for which krill make up the largest part of their diets [6]. In the Southern Ocean, one species, the Antarctic krill, Euphausia superba, makes up an estimated biomass of around 379,000,000 tones, making it among the species with the largest total biomass. Of this, over half is eaten by whales, seals, penguins, squid, and fish each year, and is replaced by growth and reproduction. Most krill species display large daily vertical migrations, thus providing food for predators near the surface at night and in deeper waters during the day [7].

Fig 2: Krill with label

3. Krill Herd (KH) Algorithm                                  

     Krill herd (KH) is a novel meta-heuristic swarm intelligence optimization method for solving optimization problems, which is based on the simulation of the herding of the krill swarms in response to specific biological and environmental processes [8]. The time-dependent position of an individual krill in two-dimensional surface is determined by three main actions described as follows:

  • Movement induced by other krill individuals
  • Foraging action
  • Random diffusion

     Krill are considered an important trophic level connection  near the bottom of the food chain because they feed on phytoplankton and (to a lesser extent) zooplankton, converting these into a form suitable for many larger animals for which krill make up the largest part of their diets [9].

      The described information exchange concept is introduced to the KH algorithm to develop an improved KH (IKH) method. The main goal is to speed up the algorithm convergence and therefore to provide a more efficient tool for a wider range of practical applications while preserving the attractive characteristics of the basic KH method. Besides, IKH adopts a new Lévy flight distribution and elitism scheme to update the KH motion calculation []10\. The proposed approach is evaluated on 14 standard benchmark functions. Experimental results show that IKH performs better than the basic KH, GA, BA, CS, DE, HS, PSO, probability-based incremental learning (PBIL), and artificial bee colony (ABC) optimization methods. In order to better KH in optimization problems, two methods have been proposed, which introduces mutation scheme into KH to add the diversity of population. The formation of groupings of various species of marine animals is under-dispersed and non-random. Many studies have focused on capturing the underlying mechanisms governing the development of these formations [11]. The major mechanisms identified are related to the feeding ability, enhanced reproduction, and protection from predators, and environmental conditions. Some mathematical models have been developed to evaluate the relative contribution of these mechanisms based on experimental observations.

      Antarctic krill is one of the best-studied species of marine animal. The krill herds are aggregations with no parallel orientation existing on time scales of hours to days and space scales of 10 s to 100 s of meters. One of the main characteristics of this specie is its ability to form large swarms. Over the last three decades, several studies have been conducted to understand the ecology and distribution of krill [12]. Although there are yet notable uncertainties about the forces determining the distribution of the krill herd, conceptual models have been proposed to explain the observed formation of the krill herds. The results obtained by such conceptual frameworks revealed that the krill swarms form the basic unit of organization for this species [13]. In order to better understand the formation of the krill swarms, the proximate causes and the factors that are adaptive advantages of aggregation formation (ultimate effects) should be distinguished. When predators, such as seals, penguins or seabirds, attack krill, they remove individual krill. This results in reducing the krill density. The formation of the krill herd after predation depends on many parameters. The herding of the krill individuals is a multi-objective process including two main goals: (1) increasing krill density, and (2) reaching food. In the present study, this process is taken into account to propose a new metaheuristic algorithm for solving global optimization problems. Density-dependent attraction of krill (increasing density) and finding food (areas of high food concentration) are used as objectives which finally lead the krill to herd around the global minima. In this process, an individual krill moves toward the best solution when it searches for the highest density and food [14]. That is, the closer the distance to the high density and food, the less the objective function. Generally, some coefficients should be determined for using multi-objective herding behavior for a single objective one.

Fig 3: Krill Herd Algorithm

3.1. Steps for Krill Herd Algorithm

  • Motion induced by other krill individuals
  • Foraging Motion
  • Physical diffusion
  • Main procedure of the KH algorithm

3.1.1. Motion Induced by other Krill Individuals

      The direction of motion induced, is approximately evaluated by the target swarm density (target effect), a local swarm density (local effect), and a repulsive swarm density (repulsive effect) [15].  According to theoretical arguments, the krill individuals try to maintain a high density and move due to their mutual effects.

3.1.2. Foraging Motion

     The foraging motion is formulated in terms of two main effective parameters. The first one is the food location and the second one is the previous experience about the food location. The food effect is defined in terms of its location. The center of food should be found at first and then try to formulate food attraction [16]. This cannot be determined but can be estimated. In this study, the virtual center of food concentration is estimated according to the fitness distribution of the krill individuals, which is inspired from ‘‘center of mass’’.

3.1.3. Physical Diffusion

     The physical diffusion of the krill individuals is considered to be a random process. This motion can be express in terms of a maximum diffusion speed and a random directional vector. The better the position of the krill is, the less random the motion is. Thus, another term is added to the physical diffusion formula to consider this effect [17]. The effects of the motion induced by other krill individuals and foraging motion gradually decrease with increasing the time (iterations). The physical diffusion is a random vector and does not steadily reduce with the increases of the iteration number [18].

3.1.4. Main procedure of the KH algorithm

     In general, the defined motions frequently change the position of a krill individual toward the best fitness. The foraging motion and the motion induced by other krill individuals contain two global and two local strategies [19]. These are working in parallel which make KH a powerful algorithm.

3.2. Flow Chart of KH Algorithm

Fig 4: Flowchart of KH Algorithm

3.3. Methodology of the KH algorithm

      Various krill-inspired algorithms can be developed by idealizing the motion characteristics of the krill individuals [20]. Generally, the KH algorithm can be introduced by the following steps:

1) Data Structures: Define the simple bounds, determination of algorithm parameter(s) and etc.

2) Initialization: Randomly create the initial population in the search space.

3) Fitness evaluation: Evaluation of each krill individual according to its position.

4) Motion calculation:

  • Motion induced by the presence of other individuals,
  • Foraging motion
  • Physical diffusion

5) Implement the genetic operators

6) Updating: updating the krill individual position in the search space.

7) Repeating: go to step III until the stop criteria is reached.

8) End

4. Numerical methods of KH Algorithm

      Numerical Example of Krill Herd Algorithm is given by [21],

5. Applications of KH Algorithm

  • Power Economic Dispatch [22]
  • ELD problems
  • Radiative enclosure
  •  Fuzzy controller [23]
  • Position clamping
  • Neural network
Fig 5: Applications of Krill Herd Algorithm

6. Advantages of KH Algorithm

  • The main advantage is higher local optima avoidance capability, making meta-heuristics well-suited for real problems with a huge number of local solutions [24].
  • The other benefits of meta-heuristics are simplicity, flexibility, and derivation free structure.
  • The best krill, the Stud, provides its optimal information for all the other individuals in the population using general genetic operators instead of stochastic selection [25].
  • The improvement involves adding a new hybrid differential evolution (HDE) operator into the krill, updating process for the purpose of dealing with optimization problems more efficiently [26].
  • The main improvement pertains to the exchange of information between top krill during motion calculation process to generate better candidate solutions [27].

Reference

[1] Gandomi, A. and Alavi, A. (2012). Krill herd: A new bio-inspired optimization algorithm. Communications in Nonlinear Science and Numerical Simulation, 17(12), pp.4831-4845.

[2] Wang, G., Guo, L., Wang, H., Duan, H., Liu, L. and Li, J. (2013). Erratum to: Incorporating mutation scheme into krill herd algorithm for global numerical optimization. Neural Computing and Applications, 24(5), pp.1231-1231.

[3] Wang, G., Gandomi, A. and Alavi, A. (2014). An effective krill herd algorithm with migration operator in biogeography-based optimization. Applied Mathematical Modelling, 38(9-10), pp.2454-2462.

[4] Saremi, S., Mirjalili, S. and Mirjalili, S. (2014). Chaotic Krill Herd Optimization Algorithm. Procedia Technology, 12, pp.180-185.

[5] Wang, G., Gandomi, A. and Alavi, A. (2014). Stud krill herd algorithm. Neurocomputing, 128, pp.363-370.

[6] Wang, G., Gandomi, A., Alavi, A. and Hao, G. (2013). Hybrid krill herd algorithm with differential evolution for global numerical optimization. Neural Computing and Applications, 25(2), pp.297-308.

[7] Guo, L., Wang, G., H. Gandomi, A., H. Alavi, A. and Duan, H. (2014). A new improved krill herd algorithm for global numerical optimization. Neurocomputing, 138, pp.392-402.

[8] Mandal, B., Roy, P. and Mandal, S. (2014). Economic load dispatch using krill herd algorithm. International Journal of Electrical Power & Energy Systems, 57, pp.1-10.

[9] Wang, G., Gandomi, A., Alavi, A. and Deb, S. (2015). A hybrid method based on krill herd and quantum-behaved particle swarm optimization. Neural Computing and Applications, 27(4), pp.989-1006.

[10] Sun, S., Qi, H., Zhao, F., Ruan, L. and Li, B. (2016). Inverse geometry design of two-dimensional complex radiative enclosures using krill herd optimization algorithm. Applied Thermal Engineering, 98, pp.1104-1115.

[11] Fattahi, E., Bidar, M. and Kanan, H. (2016). Fuzzy Krill Herd (FKH): An improved optimization algorithm. Intelligent Data Analysis, 20(1), pp.153-165.

[12] Bolaji, A., Al-Betar, M., Awadallah, M., Khader, A. and Abualigah, L. (2016). A comprehensive review: Krill Herd algorithm (KH) and its applications. Applied Soft Computing, 49, pp.437-446.

[13] Li, J., Tang, Y., Hua, C. and Guan, X. (2014). An improved krill herd algorithm: Krill herd with linear decreasing step. Applied Mathematics and Computation, 234, pp.356-367.

[14] Wang, G., Deb, S., Gandomi, A. and Alavi, A. (2016). Opposition-based krill herd algorithm with Cauchy mutation and position clamping. Neurocomputing, 177, pp.147-157.

[15] Mukherjee, A. and Mukherjee, V. (2015). Solution of optimal power flow using chaotic krill herd algorithm. Chaos, Solitons & Fractals, 78, pp.10-21.

[16] Kowalski, P. and Łukasik, S. (2015). Training Neural Networks with Krill Herd Algorithm. Neural Processing Letters, 44(1), pp.5-17.

[17] Abualigah, L., Khader, A., Hanandeh, E. and Gandomi, A. (2017). A novel hybridization strategy for krill herd algorithm applied to clustering techniques. Applied Soft Computing, 60, pp.423-435.

[18] Abualigah, L., Khader, A. and Hanandeh, E. (2018). A combination of objective functions and hybrid Krill herd algorithm for text document clustering analysis. Engineering Applications of Artificial Intelligence, 73, pp.111-125.

[19] Beevi K., S., Nair, M. and Bindu, G. (2016). Automatic segmentation of cell nuclei using Krill Herd optimization based multi-thresholding and Localized Active Contour Model. Biocybernetics and Biomedical Engineering, 36(4), pp.584-596.

[20] Moodley, K., Rarey, J. and Ramjugernath, D. (2015). Application of the bio-inspired Krill Herd optimization technique to phase equilibrium calculations. Computers & Chemical Engineering, 74, pp.75-88.

[21] Rodan, A., Faris, H. and Alqatawna, J. (2016). Optimizing Feedforward Neural Networks Using Biogeography Based Optimization for E-Mail Spam Identification. International Journal of Communications, Network and System Sciences, 09(01), pp.19-28.

[22] Wang, H. and Yi, J. (2017). An improved optimization method based on krill herd and artificial bee colony with information exchange. Memetic Computing, 10(2), pp.177-198.

[23] Sultana, S. and Roy, P. (2016). Krill herd algorithm for optimal location of distributed generator in radial distribution system. Applied Soft Computing, 40, pp.391-404.

[24] Abualigah, L., Khader, A. and Hanandeh, E. (2018). Hybrid clustering analysis using improved krill herd algorithm. Applied Intelligence, 48(11), pp.4047-4071.

[25] Ayala, H., Segundo, E., Mariani, V. and dos S. Coelho, L. (2016). Multiobjective Krill Herd Algorithm for Electromagnetic Optimization. IEEE Transactions on Magnetics, 52(3), pp.1-4.

[26] Fard, A., Zadeh, M., Dehghan, B. and Fard, F. (2014). A novel sufficient bio-inspired optimisation method based on modified krill herd algorithm to solve the economic load dispatch. International Journal of Bio-Inspired Computation, 6(6), p.416.

[27] ChithraDevi, S., Lakshminarasimman, L. and Balamurugan, R. (2017). Stud Krill herd Algorithm for multiple DG placement and sizing in a radial distribution system. Engineering Science and Technology, an International Journal, 20(2), pp.748-759.

Leave a Reply

%d bloggers like this: