Whale Optimization Algorithm

Whale Optimization Algorithm (WOA) [1] is a recently proposed (2016) optimization algorithm mimicking the hunting mechanism of humpback whales in nature.

Humpback whales

Inspiration

edit
 
A group of 15 whales bubble net fishing near Juneau, Alaska
 
Humpback whale lunging in the center of a bubble net spiral.

Whales are fancy creatures. They are considered as the biggest mammals in the world. An adult whale can grow up to 30 meters long and 180 tons weight. There are seven different main species of this giant mammal such as Killer, Minke, Sei, Humpback, Right, Finback, and Blue whales. Whales are mostly considered as predators. They never sleep because they have to breathe from the surface of oceans. In fact, half of the brain only sleeps. The interesting thing about the whales is that they are considered as highly intelligent animals with emotion.

According to Hof and Van Der Gucht [2], whales have common cells in certain areas of their brains similar to those of human called spindle cells. These cells are responsible for judgment, emotions, and social behaviors in humans. In other words the spindle cells make us distinct from other creatures. Whales have twice number of these cells than an adult human which is the main cause of their smartness. It has been proven that whale can think, learn, judge, communicate, and become even emotional as a human does, but obviously with a much lower level of smartness. It has been observed that whales (mostly killer whales) are able to develop their own dialect as well.

Another interesting point is the social behavior of whales. They live alone or in groups. However, they are mostly observed in groups. Some of their species (killer whales for instance) can live in a family over their entire life period. One of the biggest baleen whales is humpback whales (Megaptera novaeangliae). An adult humpback whale is almost as size of a school bus. Their favorite prey are krill and small fish herds.

The most interesting thing about the humpback whales is their special hunting method. This foraging behavior is called bubble-net feeding method [3]. Humpback whales prefer to hunt school of krill or small fishes close to the surface. It has been observed that this foraging is done by creating distinctive bubbles along a circle or ‘9’-shaped path. Before 2011, this behavior was only investigated based on the observation from surface. However, Goldbogen et al. [4] investigated this behavior utilizing tag sensors. They captured 300 tag-derived bubble-net feeding events of 9 individual humpback whales. They found two maneuvers associated with bubble and named them ‘upward-spirals’ and ‘double-loops’. In the former maneuver, humpback whales dive around 12 meters down and then start to create bubble in a spiral shape around the prey and swim up toward the surface. The later maneuver includes three different stages: coral loop, lobtail, and capture loop. Detailed information about these behavior can be found in [5] .

It is worth mentioning here that bubble-net feeding is a unique behavior that can only be observed in humpback whales. In this work the spiral bubble-net feeding maneuver is mathematically modeled in order to perform optimization.

Mathematical model and optimization algorithm

edit

Encircling prey

edit

Humpback whales can recognize the location of prey and encircle them. Since the position of the optimum design in the search space is not known a priori, the WOA algorithm assumes that the current best candidate solution is the target prey or is close to the optimum. After the best search agent is defined, the other search agents will hence try to update their positions towards the best search agent. This behaviour is represented by the following equations:

 

  (1)

where   indicates the current iteration,   and   are coefficient vectors ,   is the position vector of the prey, and   indicates the position vector of a whale.

The vectors   and   are calculated as follows:

 

 

Where components of   are linearly decreased from 2 to 0 over the course of iterations and  ,   are random vectors in [0,1].

Bubble-net attacking method (exploitation phase)

edit

In order to mathematically model the bubble-net behavior of humpback whales, two approaches are designed as follows:

1- Shrinking encircling mechanism: This behavior is achieved by decreasing the value of  . Note that the fluctuation range of   is also decreased by  . In other words,   is a random value in the interval [-a,a] where a is decreased from 2 to 0 over the course of iterations. Setting random values for   in [-1,1], the new position of a search agent can be defined anywhere in between the original position of the agent and the position of the current best agent.

2- Spiral updating position: This approach first calculates the distance between the whale located at (X,Y) and prey located at (X*,Y*). A spiral equation is then created between the position of whale and prey to mimic the helix-shaped movement of humpback whales as follows:

  (2)

where   and indicates the distance of the i-th whale the prey (best solution obtained so far), b is a constant for defining the shape of the logarithmic spiral, and t is a random number in [-1,1].

Note that humpback whales swim around the prey within a shrinking circle and along a spiral-shaped path simultaneously. To model this simultaneous behaviour, we assume that there is a probability of 50% to choose between either the shrinking encircling mechanism or the spiral model to update the position of whales during optimization. The mathematical model is as follows:

 

where p is a random number in [0,1].

In addition to the bubble-net method, the humpback whales search for prey randomly. The mathematical model of the search is as follows:

Search for prey (exploration phase)

edit

The same approach based on the variation of the   vector can be utilized to search for prey (exploration). In fact, humpback whales search randomly according to the position of each other. Therefore, we use  with the random values greater than 1 or less than -1 to force search agent to move far away from a reference whale. In contrast to the exploitation phase, we update the position of a search agent in the exploration phase according to a randomly chosen search agent instead of the best search agent. This mechanism and |A ⃗|>1 emphasize exploration and allow the WOA algorithm to perform a global search. The mathematical model is as follows:

 

  (3)

where   is a random position vector (a random whale).

The WOA algorithm

edit

The WOA algorithm starts with a set of random solutions. At each iteration, search agents update their positions with respect to either a randomly chosen search agent or the best solution obtained so far. The a parameter is decreased from 2 to 0 in order to provide exploration and exploitation, respectively. A random search agent is chosen when  , while the best solution is selected when   for updating the position of the search agents. Finally, the WOA algorithm is terminated by the satisfaction of a termination criterion.

The pseudo code of the WOA algorithm is presented below:

Input data, Number of maxiter and Population etc 
Initialize the whales population  Xi (i = 1, 2, ..., n) 
Initialize a, A, C, l and p
Calculate the fitness of each search agent
X*= the best search agent
while (it < Maxiter)
      for each search agent
             if (p < 0.5)  
                      if (|A| < 1)
                                Update the position of the current search agent by the equation (1)
                      else if (|A|  1)
                                Select a random search agent (X_rand)
                                Update the position of the current search agent by the equation (3)
                      end 
             else if (p  0.5) 
                   Update the position of the current search agent by the equation (2) 
             end 
      end
Calculate the fitness of each search agent
Update X* if there is a better solution 
it=it+1
Update a, A, C, l and p
end while
return X*

Application

edit

Economic Dispatch Problem [6]

Global MPP Tracking of Photovoltaic System [7]

Skeletal structures [8]

Workflow planning of construction sites [9]

Breast Cancer Diagnosis [10]

Arabic Handwritten Characters [11]

Unit Commitment Problem Solution [12]

Multi-Objective Optimal Vehicle Fuel Consumption [13]

Multi-objective optimal mobile robot path planning [14]

Optimal siting of capacitors in radial distribution network [15]

Multilevel Thresholding Image Segmentation [16]

Optimal power flow problem [17]

Neural Network training [18]

Historic handwritten manuscript binarisation [19]

Combined Emission Constrained Economic Dispatch with Valve Point Effect Loading Problem [20]

Emission constraint environment dispatch problem [21]

Feature Selection [22]

Liver segmentation in MRI images [23]

Multi-Objective Virtual Machine Scheduling in Cloud Computing Environment [24]

References

edit
  1. Mirjalili, Seyedali, and Andrew Lewis. "The whale optimization algorithm." Advances in Engineering Software 95 (2016): 51-67.
  2. P. R. Hof and E. Van Der Gucht, "Structure of the cerebral cortex of the humpback whale, Megaptera novaeangliae (Cetacea, Mysticeti, Balaenopteridae)," The Anatomical Record, vol. 290, pp. 1-31, 2007.
  3. W. A. Watkins and W. E. Schevill, "Aerial observation of feeding behavior in four baleen whales: Eubalaena glacialis, Balaenoptera borealis, Megaptera novaeangliae, and Balaenoptera physalus," Journal of Mammalogy, pp. 155-163, 1979.
  4. J. A. Goldbogen, A. S. Friedlaender, J. Calambokidis, M. F. Mckenna, M. Simon, and D. P. Nowacek, "Integrative Approaches to the Study of Baleen Whale Diving Behavior, Feeding Performance, and Foraging Ecology," BioScience, vol. 63, pp. 90-100, 2013.
  5. J. A. Goldbogen, A. S. Friedlaender, J. Calambokidis, M. F. Mckenna, M. Simon, and D. P. Nowacek, "Integrative Approaches to the Study of Baleen Whale Diving Behavior, Feeding Performance, and Foraging Ecology," BioScience, vol. 63, pp. 90-100, 2013.
  6. Touma, Haider J. "Study of The Economic Dispatch Problem on IEEE 30-Bus System using Whale Optimization Algorithm." International Journal of Engineering Technology and Sciences (IJETS) 5.1 (2016): 11-18.
  7. Cherukuri, Santhan Kumar, and Srinivasa Rao Rayapudi. "A Novel Global MPP Tracking of Photovoltaic System based on Whale Optimization Algorithm." International Journal of Renewable Energy Development 5.3 (2016): 225.
  8. Kaveh, A., and M. Ilchi Ghazaan. "Enhanced whale optimization algorithm for sizing optimization of skeletal structures." Mechanics Based Design of Structures and Machines (2016): 1-18.
  9. Rohani, Mohammad, et al. "THE WORKFLOW PLANNING OF CONSTRUCTION SITES USING WHALE OPTIMIZATION ALGORITHM (WOA)." TURKISH ONLINE JOURNAL OF DESIGN ART AND COMMUNICATION 6 (2016): 2938-2950.
  10. Sayed, Gehad Ismail, et al. "Breast Cancer Diagnosis Approach Based on Meta-Heuristic Optimization Algorithm Inspired by the Bubble-Net Hunting Strategy of Whales." International Conference on Genetic and Evolutionary Computing. Springer International Publishing, 2016.
  11. Sahlol, Ahmed T., and Aboul Ella Hassanien. "Bio-Inspired Optimization Algorithms for Arabic Handwritten Characters." Handbook of Research on Machine Learning Innovations and Trends. IGI Global, 2017. 897-914.
  12. Ladumor, Dilip P., et al. "A Whale Optimization Algorithm approach for Unit Commitment Problem Solution."
  13. Horng, Mong-Fong, et al. "A Multi-Objective Optimal Vehicle Fuel Consumption Based on Whale Optimization Algorithm." Advances in Intelligent Information Hiding and Multimedia Signal Processing: Proceeding of the Twelfth International Conference on Intelligent Information Hiding and Multimedia Signal Processing, Nov., 21-23, 2016, Kaohsiung, Taiwan, Volume 2. Springer International Publishing, 2017.
  14. Dao, Thi-Kien, Tien-Szu Pan, and Jeng-Shyang Pan. "A multi-objective optimal mobile robot path planning based on whale optimization algorithm." Signal Processing (ICSP), 2016 IEEE 13th International Conference on. IEEE, 2016.
  15. Prakash, D. B., and C. Lakshminarayana. "Optimal siting of capacitors in radial distribution network using Whale Optimization Algorithm." Alexandria Engineering Journal (2016).
  16. El Aziz, Mohamed Abd, Ahmed A. Ewees, and Aboul Ella Hassanien. "Whale Optimization Algorithm and Moth-Flame Optimization for Multilevel Thresholding Image Segmentation." Expert Systems with Applications (2017).
  17. Bentouati, B., L. Chaib, and S. Chettih. "A hybrid whale algorithm and pattern search technique for optimal power flow problem." Modelling, Identification and Control (ICMIC), 2016 8th International Conference on. IEEE, 2016.
  18. Aljarah, Ibrahim, Hossam Faris, and Seyedali Mirjalili. "Optimizing connection weights in neural networks using the whale optimization algorithm." Soft Computing (2016): 1-15.
  19. Hassanien, Aboul Ella, et al. "Historic handwritten manuscript binarisation using whale optimisation." Systems, Man, and Cybernetics (SMC), 2016 IEEE International Conference on. IEEE, 2016.
  20. Buch, Hitartch, et al. "Combined Emission Constrained Economic Dispatch with Valve Point Effect Loading Problem Solution using Whale Optimization Algorithm."
  21. Trivedi, Indrajit N., et al. "An emission constraint environment dispatch problem solution with microgrid using Whale Optimization Algorithm." Power Systems Conference (NPSC), 2016 National. IEEE, 2016.
  22. Zamani, Hoda, and Mohammad-Hossein Nadimi-Shahraki. "Feature Selection Based on Whale Optimization Algorithm for Diseases Diagnosis." International Journal of Computer Science and Information Security 14.9 (2016): 1243.
  23. Mostafa, Abdalla, et al. "Liver segmentation in MRI images based on whale optimization algorithm." Multimedia Tools and Applications (2017): 1-24.
  24. Nadim Rana, Muhammad Shafie Abd Latiff & Shafi'i Muhammad Abdulhamid "A Cloud-based Conceptual Framework for Multi-Objective Virtual Machine Scheduling using Whale Optimization Algorithm" International Journal of Innovative Computing 8.3 (2018): 53-58.