Cuckoo-Host (Host-Parasite) Co-Evolutionary Algorithm for Global Optimization


Yang and Deb (2009) proposed a new method of global optimization based on the behavior of cuckoos that are parasitic in laying their eggs in the nests of other birds (such as crows) who serve as hosts to hatch their eggs to chicks. It was shown that the so-called "cuckoo search" algorithm may prove to be quite effective for global optimization. Subsequent investigations made by Yang and Deb, Civicioglu and Besdok, Rajabioun (2011) and Valian et al. further demonstrated that the "cuckoo search" algorithm, in its original or improved version, may be very effective. The method has been tested on a large battery of benchmark (test) functions of varied difficulty levels.

The original "cuckoo search algorithm" of Yang and Deb or its variants (or its improved versions) is based on the idea how cuckoos lay their eggs in the host nests, how, if not detected (and destroyed), the eggs are hatched by the hosts, how the cuckoo chicks later join the population of cuckoos and how a mathematical representation of all these can be used to search for the global optimum of a function. In brief, the algorithm may be conceptually summarized in the following four idealized rules:

1. Each cuckoo lays a single egg into a randomly chosen host-nest, while there are n nests;
2. The nests with better quality eggs (implying better fitness value of the optimand function), if not detected, would be hatched to be the cuckoo chicks, who would join the next generation;
3. The number of available host nests, n, is fixed. The host can detect the alien egg with a probability [0, 1] and, if detected, it will either destroy the egg or abandon the nest so as to build a new nest elsewhere;
4. When generating new solutions from the old one, Lévy flight is performed. The Lévy flight endows a cuckoo with a capability to take a random walk which has a power law step length distribution with a heavy tail. It has been found that Lévy flights characterize an appropriate type random walk in many real life situations.

The Cuckoo-Host Co-Evolution Algorithm (or Host-Parasite Coevolutionary Algorithm, HPC): This algorithm, which may be considered as a major improvement on the original Cockoo Search algorithm, was suggested by Mishra (2012, 2013). In the "Cuckoo Search" algorithm, it may be noted that it has nothing to say as to how the host birds will regenerate their nests in view of the parasitic intruders (cuckoos) and how the two (the cuckoos and the hosts) will co-evolve. Thus, the host birds are immune to the experience of invasion by the parasite cuckoos. However, Davies and Brooke and Lotem et al. observe that co-evolution does take place and the arms race theory would suggest that, in the long run, hosts should evolve good discrimination ability (and the probability of detection as high as 65%), forcing the cuckoos to switch to a new, non-discriminating host. In view of this, in a given area, where the cuckoos and the hosts interact, the rate of rejection would increase over time. On the other hand, cuckoos also would change their strategies.

For simplicity, let there be n invaders (cuckoos) and equally many hosts (crows, say). Each invader would be represented by a point (in m-dimensional space) and similarly each host would be represented by a point (in m-dimensions). These points will be randomly generated and would lie in the domain of the function to be optimized.

Each cuckoo will take a Lévy flight and if its post-flight fitness is better than its pre-flight fitness (failing which it would not make an attempt to lay any egg in the host nest), then it will randomly choose a host-nest that has not as yet been invaded by another cuckoo and the quality of the host eggs are inferior to the cuckoo egg. Its eggs, however, may be detected (with probability p) by the host and be destroyed. If not detected, however, the nestling, after being hatched in the host nest, will join the cuckoo population. Only the best cuckoos, however, will enter into the next generation. Each un-invaded host (crow) will take a Lévy flight and if its post-flight fitness is better than its pre-flight fitness, it will update itself (though the hosts' scheme of updating is different than that of the cuckoos), else it would retain its old status.

The performance of the Cuckoo-Host Co-Evolution (CHC) algorithm or its improvised version (Host-Parasite Coevolutionary algorithm or HPC) is comparable to the Differential Evolution algorithm, which is perhaps the most efficient algorithm for global optimization (of continuous valued non-convex functions). The CHC/HPC algorithm requires further investigation into its behavior as well as a study for making it more efficient.

Fortran Source Code: The program (host-parasite co-evolution source codes) provided here includes numerous test (benchmark) functions. The user may remove or retain them and add a specific subroutione to formulate the problem of interest. The user-written subroutine must be linked to the main program through SUBROUTINE FSELECT(KF,M,FTIT) and SUBROUTINE FUNC(X,M,F). The program may be compiled by a suitable FORTRAN compiler (e.g. Microsoft Fortran Compiler or force.lepsch.com or FORCE Fortran 77 compiler; note that FORCE Compilers are free downloadable), which, after compilation will yield cuckoohost.exe. An application of the host-parasite co-evolutionary algorithm has been made to re-estimate the Zellner-Revankar production function (Mishra, 2007). The codes are available in Fortran.

.

References :

  • Mishra, S.K. (2013) "Global Optimization of Some Difficult Benchmark Functions by Host-Parasite Coevolutionary Algorithm", Economics Bulletin, 33(1): 1-18. It is an improved version of the Cuckoo-Host Coevolutionary method in Mishra, S.K. (2012).
  • Mishra, S.K. (2012) "Global Optimization of Some Difficult Benchmark Functions by Cuckoo-Host Co-Evolution Meta-Heuristics", SSRN: Working Paper. http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2128079.
  • Mishra, SK, (2007) "Estimation of Zellner-Revankar Production Function Revisited.", Economics Bulletin, Vol. 3, No. 14 pp. 1-7 (download).
  • Rajabioun, R. (2011) "Cuckoo Optimization Algorithm", Applied Soft Computing, 11: 5508-5518.
  • Yang, X. S. and Deb, S. (2009) "Cuckoo Search via Lévy Flights", Proceeings of World Congress on Nature & Biologically Inspired Computing (NaBIC 2009, India), IEEE Publications, USA: 210-214.

 

Other Fortran Computer Programs

 

 

    E-JOURNAL
Journal of Alternative Economic Analysis

The Journal focuses on the research contributions to various upcoming approaches to analysis of the functioning of real-world economies in different countries. It welcomes original research articles/papers on agent-based computational, evolutionary, old (new) institutional, behavioral, ecological and environmental economics.

    E-BULLETIN
Quarterly Bulletin of the Department

The Department publishes a quarterly bulletin to publicize the research output of high quality emanating from the research work/activities of its faculty members and research scholars.
ONGOING RESEARCH
Current Research Work in the Department

A number of research topics, especially on the economy of the upland areas, are currently being investigated in the Department.
Design downloaded from free website templates.