词条 | Cuckoo search |
释义 |
In operations research, cuckoo search 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. MetaphorCuckoo 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:
In addition, Yang and Deb discovered that the random-walk style search is better performed by Lévy flights rather than simple random walk. AlgorithmThe pseudo-code can be summarized as: Objective function: Generate an initial population of host nests; While (t 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 in CS (apart from the population size ). Therefore, it is very easy to implement. Random walks and the step sizeAn important issue is the applications of Lévy flights and random walks in the generic equation for generating new solutions where 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 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[4]) was performed by Leccardi[5] who found an implementation of Chambers et al.'s approach[6] 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 outside 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 traveled in the d-dimension space is where is the effective diffusion coefficient. Here is the step size or distance traveled at each jump, and is the time taken for each jump. The above equation implies that[7] For a typical length scale L of a dimension of interest, the local search is typically limited in a region of . For and t=100 to 1000, we have for d=1, and 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.[8] Algorithm and convergence analysis will be fruitful, because there are many open problems related to metaheuristics[9] Improved Cuckoo Search AlgorithmsConvergence of Cuckoo Search algorithm can be substantially improved by genetically replacing abandoned nests (instead of using the random replacements from the original method)[10]. References1. ^{{cite conference| title =Cuckoo search via Lévy flights| author =X.-S. Yang|author2=S. Deb|date=December 2009| conference =World Congress on Nature & Biologically Inspired Computing (NaBIC 2009)| publisher =IEEE Publications| pages =210–214| arxiv =1003.1594v1 }} {{collective animal behaviour}}{{Optimization algorithms}}2. ^{{cite web|author=Inderscience |url=http://www.alphagalileo.org/ViewItem.aspx?ItemId=76985&CultureCode=en |title=Cuckoo designs spring |publisher=Alphagalileo.org |date=27 May 2010 |accessdate=2010-05-27}} 3. ^R. B. Payne, M. D. Sorenson, and K. Klitz, The Cuckoos, Oxford University Press, (2005). 4. ^R. N. Mantegna, Fast, accurate algorithm for numerical simulation of Lévy stable stochastic processes, Physical Review E, Vol.49, 4677-4683 (1994). 5. ^M. Leccardi, Comparison of three algorithms for Levy noise generation, Proceedings of fifth EUROMECH nonlinear dynamics conference (2005). 6. ^{{cite journal | last1 = Chambers | first1 = J. M. | last2 = Mallows | first2 = C. L. | last3 = Stuck | first3 = B. W. | year = 1976 | title = A method for simulating stable random variables | url = | journal = Journal of the American Statistical Association | volume = 71 | issue = | pages = 340–344 | doi=10.1080/01621459.1976.10480344}} 7. ^X.-S. Yang, Nature-Inspired Metaheuristic Algorithms, 2nd Edition, Luniver Press, (2010). 8. ^M. Gutowski, Lévy flights as an underlying mechanism for global optimization algorithms, ArXiv Mathematical Physics e-Prints, June, (2001). 9. ^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). 10. ^{{Cite journal|last=de Oliveira|first=Victoria Y.M.|last2=de Oliveira|first2=Rodrigo M.S.|last3=Affonso|first3=Carolina M.|date=2018-07-31|title=Cuckoo Search approach enhanced with genetic replacement of abandoned nests applied to optimal allocation of distributed generation units|url=http://mr.crossref.org/iPage?doi=10.1049%2Fiet-gtd.2017.1992|journal=IET Generation, Transmission & Distribution|volume=12|issue=13|pages=3353–3362|doi=10.1049/iet-gtd.2017.1992|issn=1751-8687}} 1 : Nature-inspired metaheuristics |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。