Online Cuckoo Search Algorithm Parameter Control: Review, Taxonomy and Future Research Direction

Online Cuckoo Search Algorithm Parameter Control: Review, Taxonomy and future research direction

 

Previous survey on cuckoo search algorithm

The cuckoo search algorithm (CSA) was developed by (X.-S. Yang & Suash Deb, 2009) and is an intelligent swarm-based algorithm that mimics the obligate parasitic reproduction of some species of cuckoos. This is accomplished by laying their eggs in the nest of host birds. The maiden CSA subtly balances local search space strategy and exploration of the search space and deploys a duo of control parameters; population size n and probability p_a which checks elitism and balances the strategy for the search space.

In furtherance, a trio of components were discovered for the cuckoo search algorithm; selection of the best nests/solutions, exploitative random walk and explorative Lévy Flights by randomization (X. S. Yang & Deb, 2010).  Cuckoo search is applied to obtain superior solutions in spring design optimization. Ditto in welded beam design the authors have obtained optimal solutions that are also superior or the same (X. S. Yang & Deb, 2010).

A multiobjective cuckoo search algorithm (MoCSA) was proposed to solve multiobjective optimization problems where multiobjective needs were incorporated in the original CSA (X.-S. Yang & Deb, 2013). An advanced study into MoCSA was also purposed to solve multiobjective scheduling problems by (Chandrasekaran & Simon, 2012) which evidence the transcendence of the methodology.

A duo of modifications was proposed to escalate the convergence rate of cuckoo search to make it robust (Walton, Hassan, Morgan, & Brown, 2011):

1. The value of the scaling factor  is abbreviated while there are additions in the number of generations to improve exploitative searching to the solution.
2. To enhance the rate of convergence to a minimum through information exchange between the eggs. This was absent in the original CS and therefore, the execution of the searches was independent.

An enrichment of the original CS through coalescence of an inertia weight w via a scaling factor  makes it adaptive and an increment in performance of the algorithm is observed as a result of the inclusion of Roulette wheel selection operator. The efficiency of the enriched algorithm is validated on an array of geometric synthesis problems (Abdul Rani et al., 2012; Chiroma et al., 2017).

The incorporation of two operators-annexing and cooperating- in the original CS lead to the heterogeneous enhancement and efficiency of the algorithm. To achieve this, the population is dynamically set. Simulated analysis results after evaluation on 15 benchmark function depict that the modified CS surpass the efficiency of M-elite

Co-evolutionary algorithm for numerical optimization (MECA) and organizational evolutionary algorithm for numerical optimization (OEA) (Zheng & Zhou, 2013).

Original cuckoo search algorithm

Cuckoos are becharming birds’ species not only owing to their melodious sounds, but because of their reproduction strategy. Their reproduction strategy is known to be aggressive. Many species of the cuckoo exist. However, the species ani and Guira are ill-famed for removing eggs of host birds and laying their eggs in communal nests to facilitate their hatching ability. Basically, three types of brood parasitism exist among the cuckoos: intraspecific brood parasitism, cooperative breeding, and nest takeover.  Some host birds engross in fight to prevent their nest from being taken over by conquering cuckoos. Through evolution, some cuckoo species have incremented the probability of their reproduction and lessen the abandonment of their eggs by imitating the colour and pattern of some host species. (X.-S. Yang & Suash Deb, 2009)

The cuckoo search optimization is conceptualized from the behavioral description of the cuckoo. The concept is itemized as follows:

1. Each cuckoo lays one egg at any given time and egg is ditched in a randomly selected nest;
2. Nests that house the eggs of optimal quality progress to the nest generation;
3. Host nest count is fixed and the egg laid by a cuckoo is discovered by the host bird with a probability pa ∈ [0, 1].

Within the purview of maximization problem in cuckoo search algorithm, the fitness or quality of a solution is proportional to the objective function. Therefore, in cuckoo search, it is simple to arrive at optimal solutions without undertaking a comprehensive search. For the sake of simplicity, for each egg in the nest it maps to a solution and for each cuckoo egg in the nest stands for a new solution. The objective is to use the new and potentially superior solution to do away with substandard solution in the nest (X.-S. Yang & Suash Deb, 2009).

A pseudo code is generated in figure 1 below to summarize the three (3) canonical steps of the cuckoo search.

Lévy Flights

Nature makes it such that animals seek food in a stochastic or quasi-stochastic manner. The path sought by animals to forage is a random walk. This random walk describes a Markov chain where two factors determine the succeeding position for foraging: the current state and the transition probability. Whatever the direction is chosen inexplicitly depends on the probability that can be modelled mathematically (X. S. Yang & Deb, 2010).

An illustration of the preceding paragraph has demonstrated that assorted studies have been carried out to highlight flight behavior of many animals and insects. This is characteristic of lévyflight. (Reynolds & Frye, 2007) penned that fruit flies (Drosophila melanogaster) employ a series of straight flight itinerary punctuated by 90° spasmodic turn. This lévy-flight like behavior exhibited form a foraging pattern that is periodically scale-free. (Brown, Liebovitch, & Glendon, 2007)  indited that human foragers in their foraging pattern is characteristic of lévy-flight. Light waves can perform lévy flights in an optical material in a controlled way (Barthelemy, Bertolotti, & Wiersma, 2008). Sequently, in optimization and optimal search the application of lévy flight patterns have rendered bright performance (Pavlyukevich, 2007).

Cuckoo is one bird that uses Lévy Flight in foraging. A Lévy Flight is performed by a cuckoo i to beget new solutions X^t+1:

X_i^t+1 = X^t_i + α ⊕ Lévy (λ)

Where α > 0 is the step size which is related to the scales of the problem at stake. Most of the time, α=0 is used. The X_i^t+1 is a next location which is a derivative of X^t_i the current location. The product ⊕ is the entry-wise multiplication. Lévy Flight provides the random walk as it is efficient in exploring search space owing to its long step length. The random steps which are large are derived from a Lévy distribution:

Lévy ∼ u = t^–λ, (1 < λ ≤ 3)

Where λ is a parameter which is the mean or expectation of the occurrence of the event during a unit interval.(Shehab, Khader, & Al-Betar, 2017; X. S. Yang & Deb, 2010)

Figure 1: Cuckoo Search (CS) Pseudocode. Adapted from (X.-S. Yang & Suash Deb, 2009).

 

Offline and online parameter settings

Many literatures have discussed different classifications of parameter settings. Angeline (1995) presented a classification of two variants: one on adaptation levels and the other type rooted in update rules. The classification by (Hinterding, Michalewicz, & Eiben, 1997) expanded the work by (Angeline, 1995) by adding another level of adaptation (environment level). However, the work by (X.-S. Yang & Suash Deb, 2009) made a clearer classification. Eiben et al. (1999) presented a duo of parameter settings; parameter tuning and parameter control. Parameter tuning sets the values of the algorithm parameter prior to the run of an algorithm, while parameter control allows the alteration of the values of the parameters as the algorithm is being run. The terms offline parameter and online parameter are used alternatively to describe parameter tuning and parameter control respectively.

Original cuckoo search algorithm parameter control – offline

 

Types of online parameter control

Eiben, Hinterding and Michalewicz (1999) presented three types of online parameter control techniques: deterministic, adaptive and self-adaptive parameter controls. The presentation of the control techniques was rooted in the work of Angeline (1995).

Deterministic parameter control technique modifies the values of parameters of a running algorithm using deterministic rules. Time-varying schedule is commonly used as the rule. This happens without employing any information about the search.

Adaptive parameter control determines the magnitude and direction of the value change of parameters using information about the search process.

Self-adaptive parameter control can be applied in the concept of evolution. Parameters are encoded into chromosomes, adapted and thereafter go through mutation and recombination. Better individuals are generated from the best values of the encoded parameters. These individuals have high survival rate and thence, have the potential to produce offspring that will propagate these improved values of parameters (Eiben et al., 1999).

Original cuckoo offline

Advantage of online parameter over manual or offline

(Karafotias, Hoogendoorn, & Eiben, 2015)discussed the advantages of online parameter has over offline parameter and these are:

1. It enables the algorithm to acquire suitable parameter values to be utilized in the search process.
2. The algorithm adapts the changing fitness landscape owing to the dynamic nature of the problems.
3. It enables (algorithm) for the collection and subsequent usage of information to enhance performance in later stages of the search.
4. The online parameter mechanism emancipates the user from job of the preferring the values of the parameter.

Discussion about exploitation and exploration of the cuckoo search

Any search space used for exploration and exploitation has to be probed by a search algorithm. The discovery of new neighborhoods in a search space is termed exploration. Exploitation describes the examination of the discovered new neighborhoods in the search space (Črepinšek, Liu, & Mernik, 2013). The search algorithm therefore, implements the exploration and exploitation of the search space. And a prosperous search algorithm provides an equilibrium between exploration and exploitation.

Cuckoo search algorithm, being metaheuristic, is used to explore search spaces using high strategy methods. Blum & Roli (2003) opined the existence of a commixture of criteria for the taxonomy of metaheuristics algorithms. They used diversification and intensification to dissertate about search spaces. They noted that exploration and exploitation are referenced to short-term schemes bounded with randomness, whilst diversification and intensification are schemes of medium to long-term durations that are rooted on memory usage. Simply put, diversification is the exploration of a search space, while the exploitation of accrued search space is referred to as intensification.

Therefore, cuckoo search algorithm has to equilibrate amongst sound solutions derived from exploration with new areas in search space that require investigation with aim of obviating from being entrap in local minima, i.e. exploration. These exploration and exploitation based on Lévy flight is specific to cuckoo search algorithm (Tuba, n.d.). Hakli (2013) reckoned that exploration autonomously searches for global optimum for any optimization problem, i.e., and exploitation applies existent noesis in inquest for a complete solution.

A harmonious composition of global random walk and local random walk is deployed by the cuckoo search algorithm in a search space, which are managed by a switching parameter p_a.

Lévy Flights provide the global random walk in the form:

X_i^t+1 = x^t_i + L(s,

where

L(s,sin (/S^1+s  s₀ > 0).

> 0 is the step size scaling factor which related to the scales of the problem of interest. Usually, one use  = O(L/10), where L is the characteristic scale of the problem of interest, while in some cases  = O(L/100) can be more effective and  to avoid flying too far. The preceding equation stochastic equation for a random walk.

Equation that depicts the local random walk is given below:

X_i^t+1 = X^t_i + s  H (p_a – )  (X^t_j – X^t_k),

Where X^t_j and X^t_k are two different solutions selected stochastically by random permutation, H(u) is a Heaviside function,  is a random number drawn from a uniform distribution and s is the step size. (X.-S. Yang & Deb, 2014)

Reference	Type of parameter control

 

Taxonomy

Previous taxonomy

The propose cuckoo search algorithm online parameter taxonomy

Online modification to the control parameter of cuckoo search algorithm

2017 and 2018

Reference	Proposed parameter modification	comparison	Result	Weakness

Table

Reference	Type of parameter control modification	Number
Yang (2017)	Self-adaptive
(Peng et al., 2018)	Adaptive	3
(Salgotra, Singh, & Saha, 2018)	Adaptive	1
(Sarangi, Panda, Das, & Abraham, 2018)	Adaptive	1
(B. Yang, Miao, Fan, Long, & Liu, 2018)	Adaptive	1

 

 

 

References

• Abdul Rani, K. N., Hoon, W. F., Abd Malek, M. F., Mohd Affendi, N. A., Mohamed, L., Saudin, N., … Neoh, S. C. (2012). Modified cuckoo search algorithm in weighted sum optimization for linear antenna array synthesis. 2012 IEEE Symposium on Wireless Technology and Applications (ISWTA), 210–215. https://doi.org/10.1109/ISWTA.2012.6373845
• Barthelemy, P., Bertolotti, J., & Wiersma, D. S. (2008). A Lévy flight for light. Nature, 453(7194), 495–498. https://doi.org/10.1038/nature06948
• BLUM, C. (n.d.). Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison. ACM Computing Surveys, 35(3), 41.
• Brown, C. T., Liebovitch, L. S., & Glendon, R. (2007). Lévy Flights in Dobe Ju/’hoansi Foraging Patterns. Human Ecology, 35(1), 129–138. https://doi.org/10.1007/s10745-006-9083-4
• Chandrasekaran, K., & Simon, S. P. (2012). Multi-objective scheduling problem: Hybrid approach using fuzzy assisted cuckoo search algorithm. Swarm and Evolutionary Computation, 5, 1–16. https://doi.org/10.1016/j.swevo.2012.01.001
• Chiroma, H., Herawan, T., Fister, I., Fister, I., Abdulkareem, S., Shuib, L., … Abubakar, A. (2017). Bio-inspired computation: Recent development on the modifications of the cuckoo search algorithm. Applied Soft Computing, 61, 149–173. https://doi.org/10.1016/j.asoc.2017.07.053
• Črepinšek, M., Liu, S.-H., & Mernik, M. (2013). Exploration and exploitation in evolutionary algorithms: A survey. ACM Computing Surveys, 45(3), 1–33. https://doi.org/10.1145/2480741.2480752
• HAKLI, H. (2013). A modified cuckoo search using different search strategies. 5.
• Hinterding, R., Michalewicz, Z., & Eiben, A. E. (1997). Adaptation in evolutionary computation: A survey. 65–69. https://doi.org/10.1109/ICEC.1997.592270
• Karafotias, G., Hoogendoorn, M., & Eiben, A. E. (2015). Parameter Control in Evolutionary Algorithms: Trends and Challenges. IEEE Transactions on Evolutionary Computation, 19(2), 167–187. https://doi.org/10.1109/TEVC.2014.2308294
• Pavlyukevich, I. (2007). Lévy flights, non-local search and simulated annealing. Journal of Computational Physics, 226(2), 1830–1844. https://doi.org/10.1016/j.jcp.2007.06.008
• Peng, H., Deng, C., Wang, H., Wang, W., Zhou, X., & Wu, Z. (2018). Gaussian bare-bones cuckoo search algorithm. Proceedings of the Genetic and Evolutionary Computation Conference Companion on   – GECCO ’18, 93–94. https://doi.org/10.1145/3205651.3205666
• Reynolds, A. M., & Frye, M. A. (2007). Free-Flight Odor Tracking in Drosophila Is Consistent with an Optimal Intermittent Scale-Free Search. PLoS ONE, 2(4), e354. https://doi.org/10.1371/journal.pone.0000354
• Salgotra, R., Singh, U., & Saha, S. (2018). New cuckoo search algorithms with enhanced exploration and exploitation properties. Expert Systems with Applications, 95, 384–420. https://doi.org/10.1016/j.eswa.2017.11.044
• Sarangi, S. K., Panda, R., Das, P. K., & Abraham, A. (2018). Design of optimal high pass and band stop FIR filters using adaptive Cuckoo search algorithm. Engineering Applications of Artificial Intelligence, 70, 67–80. https://doi.org/10.1016/j.engappai.2018.01.005
• Shehab, M., Khader, A. T., & Al-Betar, M. A. (2017). A survey on applications and variants of the cuckoo search algorithm. Applied Soft Computing, 61, 1041–1059. https://doi.org/10.1016/j.asoc.2017.02.034
• TUBA, M. (n.d.). Cuckoo Search Optimization Metaheuristic Adjustment. 6.
• Walton, S., Hassan, O., Morgan, K., & Brown, M. R. (2011). Modified cuckoo search: A new gradient free optimisation algorithm. Chaos, Solitons & Fractals, 44(9), 710–718. https://doi.org/10.1016/j.chaos.2011.06.004
• Yang, B., Miao, J., Fan, Z., Long, J., & Liu, X. (2018). Modified cuckoo search algorithm for the optimal placement of actuators problem. Applied Soft Computing, 67, 48–60. https://doi.org/10.1016/j.asoc.2018.03.004
• Yang, X. S., & Deb, S. (2010). Engineering optimisation by cuckoo search. International Journal of Mathematical Modelling and Numerical Optimisation, 1(4), 330. https://doi.org/10.1504/IJMMNO.2010.035430
• Yang, X.-S., & Deb, S. (2013). Multiobjective cuckoo search for design optimization. Computers & Operations Research, 40(6), 1616–1624. https://doi.org/10.1016/j.cor.2011.09.026
• Yang, X.-S., & Deb, S. (2014). Cuckoo search: Recent advances and applications. Neural Computing and Applications, 24(1), 169–174. https://doi.org/10.1007/s00521-013-1367-1
• Yang, X.-S., & Suash Deb. (2009). Cuckoo Search via Lévy flights. 210–214. https://doi.org/10.1109/NABIC.2009.5393690
• Zheng, H., & Zhou, Y. (2013). A Cooperative Coevolutionary Cuckoo Search Algorithm for Optimization Problem. Journal of Applied Mathematics, 2013, 1–9. https://doi.org/10.1155/2013/912056