Cuckoo search

This article is about the search algorithm. For the hashing algorithm, see cuckoo hashing.

Cuckoo search (CS) is an optimization algorithm developed by Xin-she Yang and Suash Deb in 2009.[1][2] It was inspired by the obligate brood parasitism of some cuckoo species by laying their eggs in the nests of other host birds (of other species). Some host birds can engage direct conflict with the intruding cuckoos. For example, if a host bird discovers the eggs are not their own, it will either throw these alien eggs away or simply abandon its nest and build a new nest elsewhere. Some cuckoo species such as the New World brood-parasitic Tapera have evolved in such a way that female parasitic cuckoos are often very specialized in the mimicry in colors and pattern of the eggs of a few chosen host species [3]

Cuckoo search idealized such breeding behavior, and thus can be applied for various optimization problems. It seems that it can outperform other metaheuristic algorithms in applications.[4]

Cuckoo search (CS) uses the following representations:

Each egg in a nest represents a solution, and a cuckoo egg represents a new solution. The aim is to use the new and potentially better solutions (cuckoos) to replace a not-so-good solution in the nests. In the simplest form, each nest has one egg. The algorithm can be extended to more complicated cases in which each nest has multiple eggs representing a set of solutions.

CS is based on three idealized rules:

  1. Each cuckoo lays one egg at a time, and dumps its egg in a randomly chosen nest;
  2. The best nests with high quality of eggs will carry over to the next generation;
  3. The number of available hosts nests is fixed, and the egg laid by a cuckoo is discovered by the host bird with a probability p_a \in (0,1). Discovering operate on some set of worst nests, and discovered solutions dumped from farther calculations.

In addition, Yang and Deb discovered that the random-walk style search is better performed by Lévy flights rather than simple random walk.

The pseudo-code can be summarized as:

Objective function: f(\mathbf{x}), \quad \mathbf{x}=(x_1,x_2,\dots,x_d); \, 
Generate an initial population of  n  host nests; 
While (t<MaxGeneration) or (stop criterion)
   Get a cuckoo randomly (say, i) and replace its solution by performing Lévy flights;
   Evaluate its quality/fitness F_i 
         [For maximization, F_i \propto f(\mathbf{x}_i) ];
   Choose a nest among n (say, j) randomly;
   if (F_i>F_j ),
          Replace j by the new solution;
   end if
   A fraction (p_a) of the worse nests are abandoned and new ones are built;
   Keep the best solutions/nests;
   Rank the solutions/nests and find the current best;
   Pass the current best solutions to the next generation;
end while

An important advantage of this algorithm is its simplicity. In fact, comparing with other population- or agent-based metaheuristic algorithms such as particle swarm optimization and harmony search, there is essentially only a single parameter p_a in CS (apart from the population size n). Therefore, it is very easy to implement.

Random walks and the step size

An important issue is the applications of Lévy flights and random walks in the generic equation for generating new solutions

\mathbf{x}_{t+1}=\mathbf{x}_t + s E_t,

where E_t is drawn from a standard normal distribution with zero mean and unity standard deviation for random walks, or drawn from Lévy distribution for Lévy flights. Obviously, the random walks can also be linked with the similarity between a cuckoo's egg and the host's egg which can be tricky in implementation. Here the step size s determines how far a random walker can go for a fixed number of iterations. The generation of Lévy step size is often tricky, and a comparison of three algorithms (including Mantegna's[5]) was performed by Leccardi[6] who found an implementation of Chambers et al's approach[7] to be the most computationally efficient due to the low number of random numbers required.

If s is too large, then the new solution generated will be too far away from the old solution (or even jump out side of the bounds). Then, such a move is unlikely to be accepted. If s is too small, the change is too small to be significant, and consequently such search is not efficient. So a proper step size is important to maintain the search as efficient as possible.

As an example, for simple isotropic random walks, we know that the average distance r traveled in the d-dimension space is

r^2=2 d D t,

where D=s^2/2\tau is the effective diffusion coefficient. Here s is the step size or distance traveled at each jump, and \tau is the time taken for each jump. The above equation implies that[8]

s^2=\frac{\tau \; r^2}{t \; d}.

For a typical length scale L of a dimension of interest, the local search is typically limited in a region of r=L/10 . For \tau=1 and t=100 to 1000, we have s\approx 0.01L for d=1, and s \approx 0.001L for d=10. Therefore, we can use s/L=0.001 to 0.01 for most problems. Though the exact derivation may require detailed analysis of the behaviour of Lévy flights.[9]

Algorithm and convergence analysis will be fruitful, because there are many open problems related to metaheuristics[10]

Implementation

The pseudo code was given in a sequential form, but Yang and Deb provides a vectorized implementation which is very efficient.[11] In the real world, if a cuckoo's egg is very similar to a host's eggs, then this cuckoo's egg is less likely to be discovered, thus the fitness should be related to the difference in solutions. Therefore, it is a good idea to do a random walk in a biased way with some random step sizes. For Matlab implementation, this biased random walk can partly be achieved by

stepsize=rand*(nest(randperm(n),:)-nest(randperm(n),:));
new_nest=nest+stepsize.*K;

where K=rand(size(nest))>pa and pa is the discovery rate.

A standard CS matlab can be found here http://www.mathworks.com/matlabcentral/fileexchange/29809-cuckoo-search-cs-algorithm.[12] However, there is some controversy on whether or not this implementation truly reflects the originally published cuckoo search algorithm. The biased walk described above closely resembles another optimization algorithm, differential evolution. It was shown that this biased walk has a larger impact on the performance of the algorithm than the cuckoo search algorithm itself.[13]

An object-oriented software implementation of cuckoo search was provided by Bacanin[14] On the other hand, a modified cuckoo search algorithm is also implemented for unconstrained optimization problems.[15]

An open source implementation of Modified Cuckoo Search can be found here https://code.google.com/p/modified-cs/

Modified cuckoo search

A modification of the standard Cuckoo Search was made by Walton et al.[16] with the aim to speed up convergence. The modification involves the additional step of information exchange between the top eggs. It was shown that Modified Cuckoo Search (MCS) outperforms the standard cuckoo search and other algorithms, in terms of convergence rates, when applied to a series of standard optimization benchmark objective functions.

Subsequently, the modified cuckoo search has been applied to optimize unstructured mesh which reduces computational cost significantly.[17][18] In addition, another interesting improvement to cuckoo search is the so-called quantum-inspired cuckoo search with convincing results [19]

Multiobjective cuckoo search (MOCS)

A multiobjective cuckoo search (MOCS) method has been formulated to deal with multi-criteria optimization problems.[20] This approach uses random weights to combine multiple objectives to a single objective. As the weights vary randomly, Pareto fronts can be found so the points can be distributed diversely over the fronts.

Hybridization

Though cuckoo search is a swarm-intelligence-based algorithm, it can be still hybridized with other swarm-based algorithms such as PSO. For example, a hybrid CS-PSO algorithm seems to remedy the defect of PSO.[21]

Applications

The applications of Cuckoo Search into engineering optimization problems[22] have shown its promising efficiency. For example, for both spring design and welded beam design problems, CS obtained better solutions than existing solutions in literature. A promising discrete cuckoo search algorithm is recently proposed to solve nurse scheduling problem.[23] An efficient computation approach based on cuckoo search has been proposed for data fusion in wireless sensor networks.[24][25] Cuckoo search is adapted to solve NP-hard combinatorial optimization problems like travelling salesman problem.[26] A new quantum-inspired cuckoo search was developed to solve Knapsack problems, which shows its effectiveness.[27] Cuckoo search can also be used to efficiently generate independent test paths for structural software testing [28] and test data generation.[29][30] Cuckoo search algorithm has been used for a nanoelectronic technology based operation-amplifier (OP-AMP) integrated circuit optimization which converged to optimal solutions very fast accurately.[31]

A conceptual comparison of the cuckoo search with Particle swarm optimization, Differential evolution and Artificial bee colony algorithm suggest that Cuckoo search and Differential evolution algorithms provide more robust results than Particle swarm optimization and Artificial bee colony algorithm.[32] An extensive detailed study of various structural optimization problems suggests that cuckoo search obtains better results than other algorithms.[33] In addition, a new software testing approach has been developed based on cuckoo search.[34] In addition, cuckoo search is particularly suitable for large scale problems, as shown in a recent study.[35] Cuckoo search has been applied to train neural networks with improved performance.[36] Furthermore, CS is successfully applied to train spiking neural models.[37] Cuckoo search has also been used to optimize web service composition process and planning graphs. [38]

Cuckoo search is a reliable approach for embedded system design[39] and design optimization[40] including optimum design of steel frames.[41]

More recent studies suggest that cuckoo search can outperform other algorithms in milling applications,[42] manufacturing scheduling,[43] and others.[44] An interesting application of cuckoo search is to solve boundary value problems.[45] More recently, cuckoo search algorithm is used for optimal parameter estimation of nonlinear Muskingum flood routing model.[46]

References

  1. ↑ X.-S. Yang; S. Deb (December 2009). Cuckoo search via Lévy flights. World Congress on Nature & Biologically Inspired Computing (NaBIC 2009). IEEE Publications. pp. 210–214. arXiv:1003.1594v1.
  2. ↑ Inderscience (27 May 2010). "Cuckoo designs spring". Alphagalileo.org. Retrieved 2010-05-27.
  3. ↑ R. B. Payne, M. D. Sorenson, and K. Klitz, The Cuckoos, Oxford University Press, (2005).
  4. ↑ http://www.scientificcomputing.com/news-DA-Novel-Cuckoo-Search-Algorithm-Beats-Particle-Swarm-Optimization-060110.aspx
  5. ↑ R. N. Mantegna, Fast, accurate algorithm for numerical simulation of Lévy stable stochastic processes, Physical Review E, Vol.49, 4677-4683 (1994).
  6. ↑ M. Leccardi, Comparison of three algorithms for Levy noise generation, Proceedings of fifth EUROMECH nonlinear dynamics conference (2005).
  7. ↑ J. M. Chambers, C. L. Mallows, and B. W. Stuck, A method for simulating stable random variables, Journal of the American Statistical Association, Vol.71, 340-344 (1976)
  8. ↑ X.-S. Yang, Nature-Inspired Metaheuristic Algorithms, 2nd Edition, Luniver Press, (2010).
  9. ↑ M. Gutowski, Lévy flights as an underlying mechanism for global optimization algorithms, ArXiv Mathematical Physics e-Prints, June, (2001).
  10. ↑ X. S. Yang, Metaheuristic optimization: algorithm analysis and open problems, in: Experimental Algorithms (SEA2011), Eds (P. M. Pardalos and S. Rebennack), LNCS 6630, pp.21-32 (2011).
  11. ↑ X.-S. Yang and S. Deb, "Engineering optimisation by cuckoo search", Int. J. Mathematical Modelling and Numerical Optimisation", Vol. 1, No. 4, 330-343 (2010). http://arxiv.org/abs/1005.2908
  12. ↑ Matlab demo code
  13. ↑ S. Walton; O. Hassan, M.R. Brown and K. Morgan (24 May 2013). "Comment on Paper by Bhargava, Fateen and Bonilla-Petriciolet". Fluid Phase Equilibria. doi:10.1016/j.fluid.2013.05.011.
  14. ↑ N. Bacanin, An object-oriented software implementation of a novel cuckoo search algorithm, Proc. of the 5th European Conference on European Computing Conference (ECC'11), pp. 245-250 (2011).
  15. ↑ M. Tuba, M. Subotic, and N. Stanarevic, Modified cuckoo search algorithm for unconstrained optimization problems, Proc. of the 5th European Conference on European Computing Conference (ECC'11), pp. 263-268 (2011).
  16. ↑ S. Walton; O. Hassan, K. Morgan and M.R. Brown (30 June 2011). "Modified cuckoo search: A new gradient free optimisation algorithm". Chaos, Solitons & Fractals. doi:10.1016/j.chaos.2011.06.004.
  17. ↑ S. Walton, O. Hassan, K. Morgan, Using proper orthogonal decomposition to reduce the order of optimization problems, in: Proc. 16th Int. Conf. on Finite Elrments in Flow Problems (Eds. Wall W.A. and Gvravemeier V.), Munich, p.90 (2011).
  18. ↑ Walton, S., Hassan, O. and Morgan, K. (2012), Reduced order mesh optimisation using proper orthogonal decomposition and a modified cuckoo search. Int. J. Numer. Meth. Engng.. doi: 10.1002/nme.4400
  19. ↑ A. Layeb, A novel quantum inspired cuckoo search for knapsack problems, Int. J. Bio-Inspired Computation, Vol. 3, 297-305 (2011).
  20. ↑ X. S. Yang and S. Deb, Multiobjective cuckoo search for design optimization, Computers and Operations Research, October (2011). doi:10.1016/j.cor.2011.09.026
  21. ↑ F. Wang, L. Lou, X. He, Y. Wang, Hybrid optimization algorithm of PSO and Cuckoo Search, in: Proc. of 2nd Int. Conference on Artificial Intelligence, Management Science and Electronic Commerce (AIMSEC'11), pp. 1172-1175 (2011).
  22. ↑ Sean Walton, Oubay Hassan, Kenneth Morgan, Selected Engineering Applications of Gradient Free Optimisation Using Cuckoo Search and Proper Orthogonal Decomposition, Archives of Computational Methods in EngineeringJune 2013, Volume 20, Issue 2, pp 123-154, http://link.springer.com/article/10.1007/s11831-013-9083-7
  23. ↑ Tein L. H. and Ramli R., Recent advancements of nurse scheduling models and a potential path, in: Proc. 6th IMT-GT Conference on Mathematics, Statistics and its Applications (ICMSA 2010), pp. 395-409 (2010). http://research.utar.edu.my/CMS/ICMSA2010/ICMSA2010_Proceedings/files/statistics/ST-Lim.pdf
  24. ↑ M. Dhivya, M. Sundarambal, L. N. Anand, Energy Efficient Computation of Data Fusion in Wireless Sensor Networks Using Cuckoo Based Particle Approach (CBPA), Int. J. of Communications, Network and System Sciences, Vol. 4, No. 4, 249-255 (2011).
  25. ↑ M. Dhivya and M. Sundarambal, Cuckoo search for data gathering in wireless sensor networks,Int. J. Mobile Communications, Vol. 9, pp. 642-656 (2011).
  26. ↑ A. Ouaarab, B. Ahiod, and X.-S. Yang, Discrete cuckoo search algorithm for the travelling salesman problem, Neural Computing and Applications, (2013). doi:10.1007/s00521-013-1402-2.
  27. ↑ A. Layeb, A novel quantum-inspired cuckoo search for Knapsack problems, Int. J. Bio-inspired Computation, Vol. 4, (2011).
  28. ↑ P. R. Srivastava, M. Chis, S. Deb and X. S. Yang, An efficient optimization algorithm for structural software testing, Int. J. Artificial Intelligence, Vol. 9 (S12), 68-77(2012)
  29. ↑ K. Perumal, J. M. Ungati, G. Kumar, N. Jain, R. Gaurav and P. R. Srivastava, Test data generation: a hybrid approach using cuckoo and tabu search, Swarm, Evolutionary, and Memetic Computing (SEMCCO2011), Lecture Notes in Computer Sciences, Vol. 7077, 46-54 (2011)
  30. ↑ Jeya Mala Dharmalingam, K. Sabari Nathan, S. Balamurugan: A hybrid test optimization framework using memetic algorithm with cuckoo flocking based search approach.SBST 2014 Proceedings of the 7th International Workshop on Search-Based Software Testing,37-38, ACM, doi:10.1145/2593833.2593843
  31. ↑ G. Zheng, S. P. Mohanty, and E. Kougianos, “Metamodel-Assisted Fast and Accurate Optimization of an OP-AMP for Biomedical Applications”, in Proceedings of the 11th IEEE Computer Society Annual Symposium on VLSI (ISVLSI), pp. 273--278, 2012.
  32. ↑ P. Civicioglu and E. Besdok, A conception comparison of the cuckoo search, particle swarm optimization, differential evolution and artificial bee colony algorithms, Artificial Intelligence Review, doi:10.1007/s10462-011-92760, 6 July (2011).
  33. ↑ A. H. Gandomi, X. S. Yang, A. H. Alavi, Cuckoo search algorithm: a metaheuristic approach to solve structural optimization problems,Engineering with Computers, Vol. 27, July (2011).
  34. ↑ K. Choudhary and G. N. Purohit, A new testing approach using cuckoo search to achieve multi-objective genetic algorithm, J. of Computing, Vol. 3, No. 4, 117-119 (2011).
  35. ↑ E. R. Speed, Evolving a Mario agent using cuckoo search and softmax heuristics, Games Innovations Conference (ICE-GIC), pp. 1-7 (2010). doi:10.1109/ICEGIC.2010.5716893
  36. ↑ E. Valian, S. Mohanna and S. Tavakoli, Improved cuckoo search algorithm for feedforward neural network training, Int. J. Artificial Intelligence and Applications, Vol. 2, No. 3, 36-43(2011).
  37. ↑ R. A. Vazquez, Training spiking neural models using cuckoo search algorithm, 2011 IEEE Congress on Evolutionary Computation (CEC'11), pp.679-686 (2011).
  38. ↑ V. R. Chifu, C. B. Pop, I. Salomie, D> S. Suia and A. N. Niculici, Optimizing the semantic web service composition process using cuckoo search, in: Intelligent Distributed Computing V, Studies in Computational Intelligence, Vol. 382, pp. 93-102 (2012).
  39. ↑ A. Kumar and S. Chakarverty, Design optimization for reliable embedded system using Cuckoo Search,in: Proc. of 3rd Int. Conference on Electronics Computer Technology (ICECT2011), pp. 564-268 (2011).
  40. ↑ A. Kumar and S. Chakarverty, Design optimization using genetic algorithm and Cuckoo Search, in: Proc. of IEEE Int. Conference on Electro/Information Technology (EIT), pp. 1-5 (2011).
  41. ↑ A. Kaveh, T. Bakhshpoori, Optimum design of steel frames using cuckoo search algorithm with Lévy flights,Structural Design of Tall and Special Buildings, Vol. 21, online first 28 Nov 2011.http://onlinelibrary.wiley.com/doi/10.1002/tal.754/abstract
  42. ↑ A. R. Yildiz, Cuckoo search algorithm for the selection of optimal machine parameters in milling operations, Int. J. Adv. Manuf. Technol., (2012). doi:10.1007/s00170-012-4013-7
  43. ↑ S. Burnwal, S. Deb, Scheduling optimization of flexible manufacturing system using cuckoo search-based approach, Int. J. Adv Manuf Technol, (2012).
  44. ↑ H. Q. Zheng and Y. Zhou, A novel cuckoo search optimization algorithm based on Gauss distribution, J. Computational Information Systems, Vol. 8, 4193-4200 (2012).
  45. ↑ A. Noghrehabadi, M. Ghalambaz and A. Vosough, A hybrid power series -- Cuckoo search optimization algorithm to electrostatic deflection of micro fixed-fixed actuators, Int. J. Multidisciplinary Science and Engineering, Vol. 2, No. 4,22-26 (2011).
  46. ↑ H. Karahan, G. Gurarslan, Z.W. Geem (2014): A new nonlinear Muskingum flood routing model incorporating lateral flow, Engineering Optimization, DOI: 10.1080/0305215X.2014.918115

47. Sivakumar, L &Kotteeswaran, R 2014, ‘Soft computing based partial-retuning of decentralised PI Controller of nonlinear multivariable process’, Advances in Intelligent Systems and Computing (AISC), Springer International Publishing, Switzerland, Vol.248, pp. 117–124.

48. Bulatović R., Đorđević S., Đorđević V.,. (2013) CUCKOO SEARCH ALGORITHM: A METAHEURISTIC APPROACH TO SOLVING THE PROBLEM OF OPTIMUM SYNTHESIS OF A SIX-BAR DOUBLE DWELL LINKAGE. Mechanism and Machine Theory (2013)61:1–13.