Enhanced Black Widow Algorithm for Numerical Functions Optimization

Over the last decade, optimization theory and methods have grown rapidly and widely been applied in different engineering fields [1]. The complexity of the real-world optimization problems increases so that optimization algorithms especially those that are inspired from nature have received growing attention regarding their efficiency potential and ability to give the desired results [2].

Evolutionary algorithms are biologically inspired population-based approaches that mimic the Darwinian evolutionary in nature. Although, such efforts date back to the 1950s, so far, they have become popular tools for search, machine learning, and design problems [3]. These algorithms employ simulated evolution such as selection and procreation to find solutions for complicated problems. Within this paradigm achieving the best solution is seen as a survival duty, where all the possible solutions compete with each other to survive and this competition is the power of the evolutionary algorithms [4]. Several evolutionary algorithms have been proposed in the literature, historically the first proposition was the Genetic Algorithms (GAs) [5] then the Evolutionary strategies (ES) [6], Evolutionary programming (EP) [7] and Differential Evolution (DE) [8] popped out, the proposed approaches did not stop here, in the early nineties researchers have proposed other EAs, Genetic programming (GP) [9], Evolutionary Computation (EC) [10], Neuroevolution Algorithms (NAs) [11], etc. A brief review on the evolutionary algorithms can be found in research [12].

The Black Widow Optimization algorithm (BWO) is a recent metaheuristic, proposed by Hayyolalam and Kazem [13], inspired from the black spider’s unique behaviour mating. The working principle of this evolutionary algorithm is the same as that of the genetic algorithms (GAs) in procreation and mutation processes, however the mating of spiders involves an exclusive stage known as cannibalism, where the female black widow consumes its husband and the children consume each other and sometimes they consume their mother, due to this stage, individuals with insufficient fitness are excluded from the competition.

The trend of published papers utilizing BWO algorithm is growing rapidly. Houssein et al. [14] have proposed a novel Black Widow Optimization Algorithm for Multilevel Thresh-olding image segmentation named BWO-MT. The proposed algorithm is about to explore the search space for the aim of finding the optimal configuration of thresholds that maximize the Otsu’s and Kapur’s method using the crossover mutation and cannibalism operators, in which the widow is encoded a set of thresholds and tested each generation using Otsu or Kapur fitness functions. The BWO-MT was tested on a set of images with different degrees of complexity, and compared with six metaheuristics in which the results of the novel algorithm were the best in all metrics. However, when the Kapur’s entropy is used, the BWO’s fitness values are not the best. This fact occurs due to the randomness of the algorithm. Nanjappan et al. [15] presented an adaptive neuro fuzzy inference system and Black Widow Optimization approach (ANFIS-BWO) for optimal resource utilization and task scheduling in a cloud environment. The aim of the algorithm is to minimize computational time, cost, and energy consumptions of the tasks with useful resource utilization. Kumar [16] have developed an Energy Efficient Black Widow Optimization based Scheduling algorithm (EEBWOSA), for solving the problem of the increased demand of services of cloud computing that leads to increase in demand of energy consumption by data-center, and this by minimizing the consumption of power, energy costs and rising the profit. Micev et al. [17] proposed a hybrid method for identification of synchronous generator parameters using an adaptive BWO algorithm, where the aim was to minimize the normalized sum of squared errors (NSSE) between simulation and experimental results. The proposed algorithm ensures a balance between exploration and exploitation of the search space because of the adaptive change of the procreation and mutation probabilities. The obtained results show the superior performance of the ABWO in comparison with other algorithms also its ability in escaping the local optima trap. However, their proposed approach is just a tuning of the basic BWOA parameters without any modifications in procreation and mutation processes. Munirah et al. [18] presented a development of parameter estimation method for Chinese hamster ovary model (CHO) using the BWO algorithm, in order to define the best value for a particular parameter. The BWO algorithm tends to get the fittest graph model, correct the data that is used to be not fit, and estimate the value based on the behaviour of data. The proposed algorithm has obtained better results in comparison with other meta-heuristics, but it would be limited in terms of the metabolic field. Other related works of BWO can be found in works [19-24].

This paper presents a modified black widow optimization algorithm (MBWO) with an efficient initialization technique that provides a high-quality initial population and avoids low convergence speed, saving the good fathers each generation by modifying the sexual cannibalism, and an adaptive adjustment of crossover and mutation rates for the purpose of keeping the balance between exploration and exploitation and maintaining population diversity to jump out of the potential local optima.

The remainder of this paper is organized as follows: Section 2 presents the traditional BWO algorithm; Section 3 introduces the proposed MBWO algorithm; the computational experiments and results are presented in Section 4 and finally Section 5 concludes the paper.

It is well known that the quality of the initial individuals is critical to the time taken in the execution, keeping hold of the fit candidates throughout the course of a run affects the final results, and the compromise between the exploration and the exploitation is the key to the success of any metaheuristic. Our proposed approach is to focus on all of them.

3.1 Population initialization

In general, bio-inspired algorithms start with initializing a random population, and try to improve its performance until a predefined criteria are satisfied. The random initialization includes no priori information about the population, this means that the search may start with poor quality individuals which affects the final results. To solve this problem, we propose the use of the opposite-based learning concept that was introduced by Tizhoosh [25].

First, we initialize our population randomly Pop(N), where N is the number of individuals. Second, we compute the opposite population OppPop(N) according to Eq. (2).

$O p p P o p_{n m}=u b+l b-P o p_{n m}$                   (2)

n=1, 2, ..., N; m=1, 2, ..., n_Var

where, ub and lb are the upper and lower bound respectively of the variables, nVar is the problem dimensions. Finally, we select the fittest individuals from the union of the population and its opposite $(\operatorname{Pop}(N) \cup O p p \operatorname{Pop}(N))$ as the initial population for the problem [26].

Figure 1 show the fitness of a population initialized randomly in comparison with an opposite based population using three different benchmark functions with 100 individuals in a space of [-5, +10], [-32.768, +32.768], [-5.12, +5.12] respectively, where the individuals of the opposite-based initialization are fitter than those of the random-based.

3.2 Saving the father

The BWO differs from other evolutionary algorithms with the step of cannibalism. The latter divides into three types where the famous one is the sexual cannibalism, in which the female consumes the male either before, during or after mating [13].

Generally, in spider’s society, the mother is fitter than the father. However, he can be fitter than his children so, destroying the male at the beginning of the procreation process leads to a loss of one of the best solutions which may influence the global results. To avoid this loss, we propose to remove the sexual cannibalism and delay destroying the father in the siblings cannibalism, which means at each generation if the father is fitter than his children, we save him for the next generation, otherwise we destroy him.

To get an idea of how many fit fathers are surviving each generation after sexual cannibalism, we have applied a test on the BWO algorithm with 100 individuals and the results are presented in Figure 2. We notice that in each generation at least 7% high-quality spiders survive, and in some cases, up to 35%.

1.png

2.png

3.png

Figure 1. Random population vs Opposite based population

a2.png

Figure 2. Number of survived fit fathers

3.3 Adaptive procreation and mutation rates

BWOA distinguishes itself with parameters that are important for exploring the search space and avoiding the local optima trap. These parameters are procreation, mutation, and cannibalism rates. Procreation rate (Pc) is responsible for introducing new solutions into the population which means exploring the search space, mutation rate (Pm) helps the search process to escape from any local optima trap and keep the balance between exploration and exploitation, cannibalism rate (Cr) ensures high performance for the exploitation stage by transferring the search agents from local to the global stage and vice versa [13]. The values of these rates are determined statically prior to the execution of the algorithm, which critically affects its performance. To solve this problem and inspired by the work of Li and Sang [27], we propose an adaptive change of crossover and mutation probabilities, that ensures a high value of Pc at the beginning of the search and a low value in the last iterations, the same with mutation rate where its value is expected to rise as the number of generations increases. This process guarantees a balance between the exploration and exploitation. The adaptive description of the crossover and mutation probabilities is the following:

$P c=P c_{\max }-\left(P c_{\max }-P c_{\min }\right) \times e^{-\left(\frac{\text { MaxIter }}{\text { iter }} \quad\right)}$                  (3)

$P m=P m_{\max }+\left(P m_{\max }-P m_{\min }\right) \times e^{-\left(\frac{\text { MaxIter }}{\text { iter }} \quad\right)}$                    (4)

where, Pm_max, Pm_min are the upper and the lower bounds of mutation rate, the recommended parameters for these two mutation probabilities are 0.5 and 0.25 respectively. Pc_max, Pc_min are the upper and the lower bounds of crossover rate and the recommended parameters for these two crossover probabilities are 0.83 and 0.6. The parameter iter is the current iteration and MaxIter is the maximum number of iterations.

Algorithm 1: Modified Black Widow Algorithm

Input: MaxIter, Cannibalism rate, ub, lb, P m_max; P m_min; P c_max; P c_min;

Output: Near optimal solution to the objective function;

//Initialization

1. Initialize the random population of black widow spiders Pop(N);
2. Calculate the opposite population OppPop(N) according to Eq. (2).
3. Select the fittest individuals from $(\operatorname{Pop}(N) \cup \operatorname{OppPop}(N))$ as the initial population;
4. t = 0;

while (t<Maxiter) do

5. Based on Eq. (3) and Eq. (4), calculate Pc and Pm;
6. Based on the procreation rate, calculate the number of reproduction "nr";
7. Select the best nr solution in pop and save them in pop1;

//Procreating and cannibalism;

8. for i=1 to nr do

Randomly select two solutions as parent from pop1;

Generate D children using Eq. (1) and Eq. (2).

Save the father if he is fitter than his children; Based on cannibalism rate destroy some of the children;

Save the remain solution into pop2;

end

//Mutation

9. Based on the mutation rate, calculate the number of mutation children "nm";
10. for i=1 to nm do

Select a solution from pop1;

Randomly mutate one chromosome of the solution and generate a new solution;

ave the new one in pop3;

end

//Update

11. Update pop = pop2 + pop3;
12. Returning the best solution;
13. Return the best solution from pop;
14. t = t + 1;

end

3a.png

Figure 3. The flowchart of the proposed algorithm

Both of procreation rate and mutation rate change exponentially, which guarantees a constant Pc and Pm at the beginning of the search because of the high value of $\left(\frac{\text { MaxIter }}{\text { iter }}\right)$ in the first generations which means exploring the space first then, after performing the exploration the adaptation of the parameters starts where the Pc decreases and Pm increases hence the process of exploitation starts.

The flowchart of the Modified Black Widow Optimization MBWO is presented in Figure 3 and the pseudo-code is shown in Algorithm 1.

This paper proposed a Modified Black Widow Optimization algorithm. The first modification was the use of the opposite-based initialization instead of the random one. The second was modifying the cannibalism process, where we suggested removing the sexual cannibalism and delaying destroying the father to the sibling cannibalism for the aim of avoiding the loss of fit solutions. Finally, an adaptive change of crossover and mutation probabilities is added for the purpose of keeping the balance between the exploration and exploitation. The validation is carried out after comparing the results of the MBWO algorithm with a set of bio-inspired approaches (BWO, ABWO, BBO, GA and IWO) using 19 benchmark functions in different dimensions. The MBWO has outperformed the algorithms in both achieving the best global optima and convergence speed. Despite all the results achieved by the proposed approach, this does not mean that it is the best algorithm developed, however it can be considered relevant and useful in solving various optimization problems.