Algorithm models/Grey Wolf Optimizer

Howling wolf

Wolf pack in Yellowstone National Park

The GWO algorithm mimics the leadership hierarchy and hunting mechanism of gray wolves in nature. Four types of grey wolves such as alpha, beta, delta, and omega are employed for simulating the leadership hierarchy. In addition, three main steps of hunting, searching for prey, encircling prey, and attacking prey, are implemented to perform optimization.

Inspiration

Grey wolf (Canis lupus) belongs to Canidae family. Grey wolves are considered as apex predators, meaning that they are at the top of the food chain. Grey wolves mostly prefer to live in a pack. The group size is 5-12 on average. Of particular interest is that they have a very strict social dominant hierarchy.

The leaders are a male and a female, called alphas. The alpha is mostly responsible for making decisions about hunting, sleeping place, time to wake, and so on. The alpha’s decisions are dictated to the pack. However, some kind of democratic behavior has also been observed, in which an alpha follows the other wolves in the pack. In gatherings, the entire pack acknowledges the alpha by holding their tails down. The alpha wolf is also called the dominant wolf since his/her orders should be followed by the pack. The alpha wolves are only allowed to mate in the pack. Interestingly, the alpha is not necessarily the strongest member of the pack but the best in terms of managing the pack. This shows that the organization and discipline of a pack is much more important than its strength.

The second level in the hierarchy of grey wolves is beta. The betas are subordinate wolves that help the alpha in decision-making or other pack activities. The beta wolf can be either male or female, and he/she is probably the best candidate to be the alpha in case one of the alpha wolves passes away or becomes very old. The beta wolf should respect the alpha, but commands the other lower-level wolves as well. It plays the role of an adviser to the alpha and discipliner for the pack. The beta reinforces the alpha's commands throughout the pack and gives feedback to the alpha.

The lowest ranking grey wolf is omega. The omega plays the role of scapegoat. Omega wolves always have to submit to all the other dominant wolves. They are the last wolves that are allowed to eat. It may seem the omega is not an important individual in the pack, but it has been observed that the whole pack face internal fighting and problems in case of losing the omega. This is due to the venting of violence and frustration of all wolves by the omega(s). This assists in satisfying the entire pack and maintaining the dominance structure. In some cases, the omega is also the babysitters in the pack.

If a wolf is not an alpha, beta, or omega, he/she is called subordinate (or delta in some references). Delta wolves have to submit to alphas and betas, but they dominate the omega. Scouts, sentinels, elders, hunters, and caretakers belong to this category. Scouts are responsible for watching the boundaries of the territory and warning the pack in case of any danger. Sentinels protect and guarantee the safety of the pack. Elders are the experienced wolves who used to be alpha or beta. Hunters help the alphas and betas when hunting prey and providing food for the pack. Finally, the caretakers are responsible for caring for the weak, ill, and wounded wolves in the pack.

In addition to the social hierarchy of wolves, group hunting is another interesting social behavior of grey wolves. According to Muro et al. the main phases of gray wolf hunting are as follows:

• Tracking, chasing, and approaching the prey
• Pursuing, encircling, and harassing the prey until it stops moving
• Attack towards the prey

Mathematical model

The hunting technique and the social hierarchy of grey wolves are mathematically modelled in order to design GWO and perform optimization. The proposed mathematical models of the social hierarchy, tracking, encircling, and attacking prey are as follows:

Social hierarchy

Gray wolf social hierarchy

In order to mathematically model the social hierarchy of wolves when designing GWO, we consider the fittest solution as the alpha (α). Consequently, the second and third best solutions are named beta (β) and delta (δ) respectively. The rest of the candidate solutions are assumed to be omega (ω). In the GWO algorithm the hunting (optimization) is guided by α, β, and δ. The ω wolves follow these three wolves.

Encircling prey

As mentioned above, grey wolves encircle prey during the hunt. In order to mathematically model encircling behavior the following equations are proposed:

${\vec {D}}=|{\vec {C}}.{\vec {X_{p}}}(t)-{\vec {X}}(t)|$

${\vec {X}}(t+1)={\vec {X_{p}}}(t)-{\vec {A}}.{\vec {D}}$

where $t$ indicates the current iteration, ${\vec {A}}$ and ${\vec {C}}$ are coefficient vectors , ${\vec {X_{p}}}$ is the position vector of the prey, and ${\vec {X}}$ indicates the position vector of a grey wolf.

The vectors ${\vec {A}}$ and ${\vec {C}}$ are calculated as follows:

${\vec {A}}=2{\vec {a}}.{\vec {r_{1}}}-{\vec {a}}$

${\vec {C}}=2.{\vec {r_{2}}}$

Where components of ${\vec {a}}$ are linearly decreased from 2 to 0 over the course of iterations and $r_{1}$, $r_{2}$ are random vectors in [0,1].

With the above equations, a grey wolf in the position of (X,Y) can update its position according to the position of the prey (X*,Y*). Different places around the best agent can be reached with respect to the current position by adjusting the value of ${\vec {A}}$ and ${\vec {C}}$ vectors. For instance, (X*-X,Y*) can be reached by setting ${\vec {A}}=(1,0)$ and ${\vec {C}}=(1,1)$. Note that the random vectors $r_{1}$ and $r_{2}$ allow wolves to reach any position between the two particular points. So a grey wolf can update its position inside the space around the prey in any random location by the above-mentioned equations.

The same concept can be extended to a search space with n dimensions, and the grey wolves will move in hyper-cubes (or hyper-spheres) around the best solution obtained so far.

Hunting

Updating position of gray wolves in GWO

Grey wolves have the ability to recognize the location of prey and encircle them. The hunt is usually guided by the alpha. The beta and delta might also participate in hunting occasionally. However, in an abstract search space, we have no idea about the location of the optimum (prey). In order to mathematically simulate the hunting behavior of grey wolves, we suppose that the alpha (best candidate solution) beta and delta have better knowledge about the potential location of prey. Therefore, we save the first three best solutions obtained so far and oblige the other search agents (including the omegas) to update their positions according to the position of the best search agent. The following formulas are proposed in this regard.

${\vec {D_{\alpha }}}=|{\vec {C_{1}}}.{\vec {X_{\alpha }}}-{\vec {X}}|$

${\vec {D_{\beta }}}=|{\vec {C_{2}}}.{\vec {X_{\beta }}}-{\vec {X}}|$

${\vec {D_{\delta }}}=|{\vec {C_{3}}}.{\vec {X_{\delta }}}-{\vec {X}}|$

${\vec {X_{1}}}={\vec {X_{\alpha }}}-{\vec {A_{1}}}.({\vec {D_{\alpha }}})$

${\vec {X_{2}}}={\vec {X_{\beta }}}-{\vec {A_{2}}}.({\vec {D_{\beta }}})$

${\vec {X_{3}}}={\vec {X_{\delta }}}-{\vec {A_{3}}}.({\vec {D_{\delta }}})$

${\vec {X}}(t+1)={\frac {{\vec {X_{1}}}+{\vec {X_{2}}}+{\vec {X_{3}}}}{3}}$

With these equations, a search agent updates its position according to alpha, beta, and delta in an n-dimensional search space. In addition, the final position would be in a random place within a circle which is defined by the positions of alpha, beta, and delta in the search space. In other words, alpha, beta, and delta estimate the position of the prey, and other wolves update their positions randomly around the prey.

Attacking prey (exploitation)

American Bison standing its ground, thereby increasing its chance of survival

As mentioned above the grey wolves finish the hunt by attacking the prey when it stops moving. In order to mathematically model approaching the prey we decrease the value of ${\vec {a}}$. Note that the fluctuation range of ${\vec {A}}$ is also decreased by ${\vec {a}}$. In other words ${\vec {A}}$ is a random value in the interval [-2a,2a] where a is decreased from 2 to 0 over the course of iterations. When random values of ${\vec {A}}$ are in [-1,1], the next position of a search agent can be in any position between its current position and the position of the prey.

With the operators proposed so far, the GWO algorithm allows its search agents to update their position based on the location of the alpha, beta, and delta; and attack towards the prey. However, the GWO algorithm is prone to stagnation in local solutions with these operators. It is true that the encircling mechanism proposed shows exploration to some extent, but GWO needs more operators to emphasize exploration.

Search for prey (exploration)

Grey wolves mostly search according to the position of the alpha, beta, and delta. They diverge from each other to search for prey and converge to attack prey. In order to mathematically model divergence, we utilize ${\vec {A}}$ with random values greater than 1 or less than -1 to oblige the search agent to diverge from the prey. This emphasizes exploration and allows the GWO algorithm to search globally. |A|>1 forces the grey wolves to diverge from the prey to hopefully find a fitter prey. Another component of GWO that favors exploration is ${\vec {C}}$, which contains random values in [0, 2]. This component provides random weights for prey in order to stochastically emphasize (C>1) or de-emphasize (C<1) the effect of prey in defining the distance in Equation (3.1). This assists GWO to show more random behavior throughout optimization, favouring exploration and local optima avoidance. It is worth mentioning here that C is not linearly decreased in contrast to A. We deliberately require C to provide random values at all times in order to emphasize exploration not only during initial iterations but also final iterations. This component is very helpful in case of local optima stagnation, especially in the final iterations.

The C vector can be also considered as the effect of obstacles to approaching prey in nature. Generally speaking, the obstacles in nature appear in the hunting paths of wolves and in fact prevent them from quickly and conveniently approaching prey. This is exactly what the vector C does. Depending on the position of a wolf, it can randomly give the prey a weight and make it harder and farther to reach for wolves or vice versa.

To sum up, the search process starts with creating a random population of grey wolves (candidate solutions) in the GWO algorithm. Over the course of iterations, alpha, beta, and delta wolves estimate the probable position of the prey. Each candidate solution updates its distance from the prey. The parameter is decreased from 2 to 0 in order to emphasize exploration and exploitation, respectively. Candidate solutions tend to diverge from the prey when $|{\vec {A}}|>1$ and converge towards the prey when $|{\vec {A}}|<1$. Finally, the GWO algorithm is terminated by the satisfaction of an end criterion.

The GWO algorithm

Effects of A on the exploration and exploitation of GWO

Model of updating position of gray wolves in GWO

• Initialize the grey wolf population Xi (i = 1, 2, ..., n)
• Initialize a, A, and C
• Calculate the fitness of each search agent
• $X_{\alpha }$ =the best search agent
• $X_{\beta }$ =the second best search agent
• $X_{\delta }$ =the third best search agent
  • while ($t$ < Max number of iterations)
    • for each search agent
      • Update the position of the current search agent by above equations
    • end for
    • Update $a$, $A$, and $C$
    • Calculate the fitness of all search agents
    • Update $X_{\alpha }$, $X_{\beta }$, and $X_{\delta }$
    • t=t+1
  • end while
• return $X_{\alpha }$

To see how GWO is theoretically able to solve optimization problems, some points may be noted:

• The proposed social hierarchy assists GWO to save the best solutions obtained so far over the course of the iteration
• The proposed encircling mechanism defines a circle-shaped neighbourhood around the solutions which can be extended to higher dimensions as a hyper-sphere
• The random parameters A and C assist candidate solutions to have hyper-spheres with different random radii
• The proposed hunting method allows candidate solutions to locate the probable position of the prey
• Exploration and exploitation are guaranteed by the adaptive values of a and A
• The adaptive values of parameters a and A allow GWO to smoothly transition between exploration and exploitation
• With decreasing A, half of the iterations are devoted to exploration (|A|≥1) and the other half are dedicated to exploitation (|A|<1)
• The GWO has only two main parameters to be adjusted (a and C)

Applications

The GWO algorithm was employed as a training algorithm for Multi-layer perceptron (Feedforward Neural Networks) in 2015.

An improved grey wolf optimizer for training q-Gaussian Radial Basis Functional-link nets was proposed by Muangkote.

The grey wolf optimizer was utilized for solving economic dispatch problems as well. An Application of Grey Wolf Optimizer for Solving Combined Economic Emission Dispatch Problems was done by Song et al. as well.

Feature Subset Selection Approach by Gray-Wolf Optimization was done by Emary et al.

The GWO algorithm was used for optimum allocation of STATCOM devices on power system grid to minimized load buses voltage deviations and system power losses.

An improved version of GWO using evolutionary population dynamics was also proposed recently.

The GWO algorithm was utilized to optimizing key values in the cryptography algorithms..

External links

• Grey Wolf Algorithm in Matlab or Octave

• Matlab toolbox for Grey Wolf Algorithm