Online Cuckoo Search Algorithm Parameter Control

Review, Taxonomy and future research direction

Previous survey on cuckoo search algorithm

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).

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, and 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).

Figure 1: Cuckoo Search (CS) pseudocode (IEEE, 2010).

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 (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 and 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.

Taxonomy

Previous taxonomy

The propose cuckoo search algorithm online parameter taxonomy

Online modification to the control parameter of cuckoo search algorithm

2017 and 2018

Table

References

• 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
• Č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 (pp. 65–69). IEEE. 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
• 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
• TUBA, M. (n.d.). Cuckoo Search Optimization Metaheuristic Adjustment, 6.
• 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., & Suash Deb. (2009). Cuckoo Search via Lévy flights (pp. 210–214). IEEE. https://doi.org/10.1109/NABIC.2009.5393690