The Whale Optimization Algorithm for Solving Constrained Problems in C++
Nature-inspired metaheuristic algorithms, here the whale algorithms solve optimization problems by mimicking biological or physical phenomena.
There were pioneered a considerable number of algorithms, which are frequently used to solve optimization problems. Often metaheuristic algorithm use s relatively simple concepts. There are simple while accommodating for problem specific, they can bypass local optima, and finally can be applied to a wide range of problems spanning various disciplines.
In this article, I will describe the whale optimization algorithm, which I used to solve some benchmark-constrained optimization problems. In addition, I will apply discussed algorithm to solve the robot path planner in 3D.
The source code for this article you will find on my GitHub.
Whale Optimization Algorithm (WOA)
Whales are elegant animals. They are regarded as the world’s largest animals. A mature whale may grow up to 30 meters long and 180 tons in weight. This huge mammal has seven primary species, including the killer, Minke, Sei, humpback, right, finback, and blue. Most people think of whales as predators. Since they must breathe ocean surface air, they are unable to sleep. Actually, the other half of the brain is asleep. The fascinating thing about whales is that they are thought to be very intelligent, feeling animals (like humans).
One of the most exciting things, which is the scope of this article is their
special hunting method. The method is called the bubble-net feeding method. Humpback whales hunt fish by creating distinctive bubbles along a circle, see the figure below.
Whales’ maneuvers associated with bubbles and named them ‘upward-spirals’ and ‘double-loops’. As you can see in the figure bobbles generated by whales cut the way for the fish. As time goes the circle (spirals) becomes smaller (radius) so finally allows accumulating fish in one place.
Here is a YouTube video where these extraordinary animals can inspire you.
Bubble-net feeding is a unique behavior that can be observed in humpback whales only.
The following mathematical model (set of equations) has been invented in order to resemble the behavior of whales and solve optimization problems.
The optimization problem can be multi-dimensional. In this case, each whale is considered as a search agent holding a variable specific (number of variables equals the problem dimension space).
A. Encircling prey
When hunting, humpback whales may spot their prey and circle around them. The WOA method makes the assumption that the current best candidate solution is the target prey or is very near to the optimum since the location of the optimal design in the search space is not known a priori. The other search agents will attempt to adjust their locations toward the best search agent after the greatest search agent has been identified. The following equations illustrate this behavior (Eq1):
where A, C are coefficient vectors, X is considered a position. Vector a is initialized to 2 and decreased while optimization runs. Vector r is a random vector [ 0,1].
B. Bubble-net attacking method (exploitation phase)
In this phase, we can distinguish two behaviors. One shrinking encircling mechanism, where the hunting circle is decreasing (while we run the algorithm the decreasing process occurs each iteration). And second spiral updating position, where the distance between the whale located
at ( X, Y ) and the prey located at ( X*, Y* ) is updated.
Humpback whales swim simultaneously in a spiraling pattern around the prey and in a circle that is getting smaller. We use the assumption that there is a 50% chance of selecting either the spiral model or the shrinking encircling mechanism to update the position of whales throughout optimization in order to mimic this simultaneous behavior (Eq2).
where (as Eq1) and b is a constant for defining the shape of the logarithmic spiral, l is a random number in [ −1,1]
C. Search for prey (exploration phase)
To find prey, the whales use the same strategy based on the A vector (exploration). In actuality, humpback whales randomly seek based on one another’s positions. We use the below update position equation if A>1 (Eq3)
where p is a random number in [0,1]. X_rand is a random position vector (a random whale) chosen from the whole population.
Pseudo-code can be depicted as follows,
As it was mentioned above I used deployed WOA in C++ to solve three different optimizations problem. The simple one is the ordinary quadratic function I used for my personal debugging purpose.
The second problem is connected (benchmark optimization problem) with tension/compression spring where the objective of the problem is to minimize the weight. There are three design variables: wire diameter ( d ), mean coil diameter ( D ), and the number of active coils ( N ). This is a three-dimensional problem (each variable is considered as a dimension).
The optimization problem can be formulated as follows :
The existing constraints have been included in the objective function as penalties. I modeled penalties as a quadratic loss function (see here and here).
The implemented method solves the problem (computes the minimum weight of the spring). The solution I received was equal (almost) to the article I was inspired by.
The last problem I used the WAO is the robot path planner case (the problem is known from my previous articles). The WAO algorithm optimizes the position of the robot in order to find collision-free (I used the WOA for 3D space path planner) between the start and the goal. As I mentioned in my previous article, path planning for 3D space is applicable mainly for drones or other robots “without” kinematics. Generally, for manipulators, we are looking solutions in joint space.
The objective function of the robot path planner
Similarly to my previous article, I applied the same objective (cost) function. The cost function that the algorithm is trying to optimize (compute minimum) can be defined as follows,
where,
distance firefly — obstacle,
- for 2D path planner
- for 3D path planner
distance firefly — goal,
- for 2D path planner
- for 3D path planner
K1 and K2 are coefficients taken from the article.
The optimal values of all constants depicted in the above formulas are taken from the article I refer to.
Below I plot an example while running the path planner.
Plotting requires incorporating the header file which has to be in the same folder as your cpp (a file you can clone from my repository).
Your program can be compiled as follows,
//compile
g++ my_prog.cpp -o my_prog -I/usr/include/python3.8 -lpython3.8//
//run
./my_prog
//folder tree
├── my_prog
├── my_prog.cpp
├── matplotlibcpp.hThank you for reading.
