There is a soaring growth in the amount of research being done in the field of metaheuristic optimization algorithms and new algorithms with different purposes are being proposed frequently. Some might say that the field has reached its limit as the upgrades to the final optimum value or the computational effort to reach that point is not being improved considerably. However, mentioning two points is crucial here. One, the famous No Free Lunch (NFL) Theorem that logically proves the fact that the is no algorithm that can outperform all other algorithms in all of the problems, and two, these little, and sometimes negligible improvements can eventually lead to a significant improvement.
One of the recently developed algorithms that have gained considerable attention by researchers in multiple fields of science and engineering is the Gray Wolf Optimizer (GWO) introduced by Mirjalili et al. in 2014. The algorithm mimics the hunting process of the gray wolves by considering the population as a wolf pack with the 3 best answers being the α, β, and δ wolves that essentially lead the pack at each iteration. The algorithm has proven superior to some of the well-known algorithms such as Differential Evolution (DE), Particle Swarm Optimization (PSO), Gravitational Search Algorithm (GSA), etc. Another feature of this algorithm that in my opinion played an important role in its prevalence in academia was its simplicity. However, according to NFL, there is a possibility that this algorithm is outperformed by other algorithms in some other problems.
At the Hydroinformatics Lab at the University of Mohaghegh Ardebili, our team was working on several projects. I was involved in two projects that were concentrated on solving two optimization problems. Reservoir operation and gravitational sanitary sewer networks design optimization. It seemed very justified to assess the performance of the famous GWO on these complex and large-scale problems. The reservoir operation optimization was the first class to be solved by this algorithm. We observed that in consecutive runs, the GWO got trapped in local optima frequently. No matter how it was adjusted the problem was still present. The sanitary sewer networks design project was going on well using the Shuffled Frog Leaping Algorithm (SFLA). It was then that it popped to my mind that what if we introduced a little complexity into the GWO by using the population division procedure that is used in SFLA?
I thought that as in the GWO no matter how large the population size was, everything depended heavily on the three best solutions. Even if the fourth member was a good one it was not still good enough. So, there is little information exchange between the population members. The procedure of population division that was first used in the Shuffled Complex Evolution (SCE-UA) and was also used in the SFLA seemed suitable for our goal and thus the shuffled gray wolf optimizer (SGWO) was developed that used the SCE-UA’s population division method and GWO’s population updating procedure. (With some tweaks of course!)
The division creates two scales in which the population is evaluated and updated; we have called these scales global and local. The global scale is exactly the same as the original GWO algorithm, meaning the 3 best answers are chosen as the α, β, and δ wolves (called “global superiors”) and the updating parameter is calculated according to them. This population division results in the creation of “sub-packs”, smaller packs of wolves. The hierarchy of wolves is replicated in each sub-pack; in other words, each sub-pack of wolves has its own α, β, and δ wolves which are called “local superiors”. Each wolf of the population updates its position using an updating parameter specific to that sub-pack which is essentially a weighted average of global and local updating parameters.
This type of division might not be a realistic hunting procedure of gray wolves, but if it was realistic, it would have meant that the pack will not encircle the prey as a whole and instead they create smaller groups to better exchange the information with each other and increase the efficiency of the hunt. The population division has been depicted in Fig. 1 and Fig. 2. In Fig. 2, the α, β, and δ are denoted with green, blue and red respectively. In SGWO these colors show the local superiors with the same hierarchy and the encircled wolves are global superiors with the coloring order being the same as the locals (the green circle is the global α, the blue circle global β, and the red circle is global δ wolf).
It was intuitive that increasing the amount of information exchanged will improve the performance of the GWO and it was! The SGWO algorithm was employed on a number of benchmark functions with different characteristics, and it outperformed well-known algorithms such as PSO, Genetic Algorithm (GA), and also its parent algorithms SCE-UA and GWO. Several criteria enable us to compare performances of different optimization algorithms to each other such as computational time requirement, function evaluations required to reach the global optimum, reliability, etc. Among all these criteria, the number of function evaluations (NFE) is considered pervasively in literature as a comparison criterion, which corresponds to the objective function's computational effort. In other words, the less NFE required, the more efficient the algorithm performs. To this end, and to conduct a fair comparison, the NFE for each algorithm was limited to 15000 to observe how each of the algorithms performs given this limited condition. Each optimization problem was solved 20 times by each algorithm. Alongside the smaller global minimum, the average and standard deviation of the results obtained by the SGWO show that this algorithm tends to reach a better optimum point more often and has acceptable reliability.
The SGWO was employed on Reservoir Operation Optimization and Gravitational Sewer Network Design Optimization problems. A summary of these projects, more details, and results can be found in their corresponding posts (Link to the journal papers will be shared immediately after the papers get published).
Comments