Applied Soft Computing 11(2011)5508–5518
Contents lists available at ScienceDirect
Applied Soft
Computing
j o u r n a l h o m e p a g e :w w w.e l s e v i e r.c o m /l o c a t e /a s o
c
Cuckoo Optimization Algorithm
Ramin Rajabioun ∗
Control and Intelligent Processing Centre of Excellence (CIPCE),School of Electrical and Computer Engineering,University of Tehran,Tehran,Iran
桂花是什么颜色的a r t i c l e
i n f o
Article history:
Received 17September 2009
Received in revid form 28August 2010Accepted 1May 2011
Available online 13May 2011作文提纲的格式
Keywords:
Cuckoo Optimization Algorithm (COA)Evolutionary algorithms Nonlinear optimization
a b s t r a c t
In this paper a novel evolutionary algorithm,suitable for continuous nonlinear optimization problems,is introduced.This optimization algorithm is inspired by the life of a bird family,called Cuckoo.Special lifestyle of the birds and their characteristics in egg laying and breeding has been the basic motivation for development of this new evolutionary optimization algorithm.Similar to other evolutionary methods,Cuckoo Optimization Algorithm (COA)starts with an initial population.The cuckoo population,in differ-ent societies,is in two types:mature cuckoos and eggs.The effort to survive among cuckoos constitutes the basis of Cuckoo Optimization Algorithm.During the survival competition some of the cuckoos or their eggs,demi.The survived cuckoo societies immigrate to a better environment and start reproducing and laying eggs.Cuckoos’survival effort hopefully converges to a state that there is only one cuckoo society,all with the same profit values.Application of the propod algorithm to some benchmark functions and a real problem has proven its capability
to deal with difficult optimization problems.
嘎达梅林教案©2011Elvier B.V.All rights rerved.
1.Introduction
Optimization is the process of making something better.In other words,optimization is the process of adjusting the inputs to or char-acteristics of a device,mathematical process,or experiment to find the minimum or maximum output or result.The input consists of variables:the process or function is known as the cost function,objective function,or fitness function;and the output is the cost or fitness [1].There are different methods for solving an optimiza-tion problem.Some of the methods are inspired from natural process.The methods usually start with an initial t of vari-ables and then evolve to obtain the global minimum or maximum of the objective function.Genetic Algorithm (GA)has been the most popular technique in evolutionary computation rearch.Genetic Algorithm us operators inspired by natural genetic variation and natural lection [2,3].Another example is Particle Swarm Opti-mization (PSO)which was developed by Eberhart and Kennedy in 1995.This stochastic optimization algorithm is inspired by social behavior of bird flocking or fish schooling [3–5].Ant Colony Opti-mization (ACO)is another evolutionary optimization algorithm which is inspired by
the pheromone trail laying behavior of real ant colonies [3,6,7].On the other hand Simulated Annealing sim-ulates the annealing process in which a substance is heated above its melting temperature and then gradually cools to produce the crystalline lattice,which minimizes its energy probability distribu-∗Correspondence address:Faculty of Engineering,Campus #2,University of Tehran,Kargar Shomali St.,P.O.Box 14395-515,Tehran,Iran.Tel.:+989144045713.
E-mail address:r.rajabioun@ece.ut.ac.ir ,
横过
tion [1,8,9].Besides the well known methods,the investigations on nature inspired optimization algorithms are still being done and new methods are being developed to continually solve some sort of nonlinear problems.In [10],making u of the ergodicity and internal randomness of chaos iterations,a novel immune evolu-tionary algorithm bad on the chaos optimization algorithm and immune evolutionary algorithm is prented to improve the con-vergence performance of the immune evolutionary algorithm.The novel algorithm integrates advantages of the immune evolution-ary algorithm and chaos optimization algorithm.[11]introduces a new optimization technique called Grenade Explosion Method (GEM)and its underlying ideas,including the concept of Optimal Search Direction (OSD),are elaborated.In [12]a new particle swarm optimization method bad on the clonal lection algorithm is pro-pod to avoid premature convergence and guarantee the diversity of the
population.
The main advantages of evolutionary algorithms are [3]:
(1)Being robust to dynamic changes :Traditional methods of opti-mization are not robust to dynamic changes in the environment and they require a complete restart for providing a solution.In contrary,evolutionary computation can be ud to adapt solutions to changing circumstances.
(2)Broad applicability :Evolutionary algorithms can be applied to
any problems that can be formulated as function optimization problems.
(3)Hybridization with other methods :Evolutionary algorithms can
be combined with more traditional optimization techniques.(4)Solves problems that have no solutions :The advantage of evolu-tionary algorithms includes the ability to address problems for
1568-4946/$–e front matter ©2011Elvier B.V.All rights rerved.doi:10.1016/j.asoc.2011.05.008
R.Rajabioun/Applied Soft Computing11(2011)5508–5518
5509
Fig.1.Flowchart of Cuckoo Optimization Algorithm.
which there is no human experti.Even though human exper-ti should be ud when it is needed and available;it often proves less adequate for automated problem-solving routines.
Considering the features,evolutionary algorithms can be applied to various applications including:Power Systems oper-ations and control[13,19,20],NP-Hard combinatorial problems [14,15],Chemical Process[16],Job Scheduling problems[17], Vehicle Routing Problems,Mobile Networking,Batch process scheduling,Multi-objective optimization problems[18],Modeling optimized parameters[21],Image processing and Pattern recogni-tion problems.
In this paper we introduce a new evolutionary optimization algorithm which is inspired by lifestyle of a bird family called cuckoo.Specific egg laying and breeding of cuckoos is the basis of this novel optimization algorithm.Cuckoos ud in this model-ing exist in two forms:mature cuckoos and eggs.Mature cuckoos lay eggs in some other birds’nest and if the eggs are not recog-nized and not killed by host birds,they grow and become a mature cuckoo.Environmental features and the immigration of societies (groups)of cuckoos hopefully lead them to converge andfind the best enviro
nment for breeding and reproduction.This best envi-ronment is the global maximum of objective functions.This paper illustrates how the life method of cuckoos is modeled and imple-mented.
Section2investigates the birds called cuckoo and reviews their amazing life characteristics.In Section3,the Cuckoo Optimization Algorithm(COA)is propod and its different parts are studied in details.The propod algorithm is tested with some benchmark functions and also with a controller design of a Multi-Input Multi-Output(MIMO)process as a real ca study in Section4.Finally the conclusions are prented in Section5.
2.Cuckoos and their special lifestyle for reproduction
All9000species of birds have the same approach to mother-hood:every one lays eggs.No bird gives birth to live young.Birds quickly form and lay an egg covered in a protective shell that is then incubated outside the body.The large size of an egg makes it difficult for the female to retain more than a single one egg at a time–carrying eggs would makeflying harder and require more energy.And becau the egg is such a protein-rich high-nutrition prize to all sorts of predators,birds mustfind a cure place to hatch their eggs.Finding a place to safely place and hatch their eggs,and rai their young to the point of independence,is a challenge birds have solved in many clever ways.
They u artistry,intricate design and complex engineering.The diversity of nest architecture has no equal in the animal kingdom.Many birds build isolated,inconspic-uous nests,hidden away inside the vegetation to avoid detection by predators.Some of them are so successful at hiding their nests that even the all-eing eyes of man has hardly ever looked on them.
There are other birds that dispen with every convention of home making and parenthood,and resort to cunning to rai their families.The are the“brood parasites,”birds which never build their own nests and instead lay their eggs in the nest of another species,leaving tho parents to care for its young.The cuckoo is the best known brood parasite,an expert in the art of cruel decep-tion.Its strategy involves stealth,surpri and speed.The mother removes one egg laid by the host mother,lays her own andflies off with the host egg in her bill.The whole process takes barely ten conds.Cuckoos parasitize the nests of a large variety of bird species and carefully mimic the color and pattern of their own eggs to match that of their hosts.Each female cuckoo specializes on one particular host species.How the cuckoo manages to lay eggs to imi-tate each host’s eggs so accurately is one of nature’s main mysteries. Many bird species learn to recognize a cuckoo egg dumped in their own nest and either throw out the strange egg or dert the nest to start afresh.So the cuckoo constantly tries to improve its mimicry of its hosts’eggs,while the hosts try tofind ways of
detecting the parasitic egg.The struggle between host and parasite is akin to an arms race,each trying to out-survive the other[22].
For the cuckoos suitable habitat provides a source of food(prin-cipally incts and especially caterpillars)and a place to breed,for brood parasites the need is for suitable habitat for the host species. Cuckoos occur in a wide variety of habitats.The majority of species occur in forests and woodland,principally in the evergreen rain-forests of the tropics.In addition to forests some species of cuckoo occupy more open environments;this can include even arid areas like derts.Temperate migratory species like the Common Cuckoo inhabit a wide range of habitats in order to make maximum u of the potential brood hosts,from reed beds to treeless moors.
Most species of cuckoo are dentary,but veral species of cuckoo undertake regular asonal migrations,and veral more undertake partial migrations over part of their range.The migration may be Diurnal,as in the Channel-billed Cuckoo,or nocturnal,as in the Yellow-billed Cuckoo.For species breeding at higher latitudes food availability dictates that they migrate to warmer climates dur-ing the winter,and all do so.The Long-tailed Koel which breeds in New Zealandflies migrates to its wintering grounds in Poly-nesia,Micronesia and Melanesia,a feat described as“perhaps the most remarkable over water migration of any land bird”[23];and the Yellow-billed Cuckoo and Black-billed Cuckoo bree
d in North America andfly across the Caribbean Sea,a non-stopflight of 4000km.Other long migrationflights include the Lesr Cuckoo,
5510R.Rajabioun/Applied Soft Computing11(2011)5508–5518
whichflies from India to Kenya across the Indian Ocean(3000km) and the Common Cuckoos of Europe whichfly non-stop over the Mediterranean Sea and Sahara Dert on their voyage to south-ern Africa.Within Africa10species make regular intra-continental migrations that are described as polarized,that is they spend the non-breeding ason in the tropical centre of the continent and move north and south to breed in the more arid and open savannah and derts[24].
About56of the Old World species and3of the New World species are brood parasites,laying their eggs in the nests of other birds[25].The species are obligate brood parasites,meaning that they only reproduce in this fashion.The cuckoo egg hatches earlier than the host’s,and the cuckoo chick grows faster;in most cas the chick evicts the eggs or young of the host species.The chick has no time to learn this behavior,so it must be an instinct pasd on genetically.The chick encourages the host to keep pace with its high growth rate with its rapid begging call[26]and the chick’s open mouth which rves as a sign stimulus[27].Female para-sitic cuckoos specialize and lay eggs that cloly r
微信昵称怎么改emble the eggs of their chon host.This has been produced by natural lection, as some birds are able to distinguish cuckoo eggs from their own, leading to tho eggs least like the host’s being thrown out of the nest[27].Host species may engage in more direct action to prevent cuckoos laying eggs in their nest in thefirst place–birds who nests are at high risk of cuckoo-contamination are known to mob cuckoos to drive them out of the area[28].Parasitic cuckoos are grouped into gents,with each gent specializing in a particular host. There is some evidence that the gents are genetically different from one another.Host specificity is enhanced by the need to imitate the eggs of the host.
3.The propod Cuckoo Optimization Algorithm(COA)
Fig.1shows aflowchart of the propod algorithm.Like other evolutionary algorithms,the propod algorithm starts with an ini-tial population of cuckoos.The initial cuckoos have some eggs to lay in some host birds’nests.Some of the eggs which are more similar to the host bird’s eggs have the opportunity to grow up and become a mature cuckoo.Other eggs are detected by host birds and are killed.The grown eggs reveal the suitability of the nests in that area.The more eggs survive in an area,the more profit is gained in that area.So the position in which more eggs survive will be the term that COA is going to optimize.
Cuckoos arch for the most suitable area to lay eggs in order to maximize their eggs survival rate.After remained eggs grow and turn into a mature cuckoo,they make some societies.Each soci-ety has its habitat region to live in.The best habitat of all societies will be the destination for the cuckoos in other societies.Then they immigrate toward this best habitat.They will inhabit somewhere near the best habitat.Considering the number of eggs each cuckoo has and also the cuckoo’s distance to the goal point(best habitat), some egg laying radii is dedicated to it.Then,cuckoo starts to lay eggs in some random nests inside her egg laying radius.This pro-cess continues until the best position with maximum profit value is obtained and most of the cuckoo population is gathered around the same position.
3.1.Generating initial cuckoo habitat
In order to solve an optimization problem,it’s necessary that the values of problem variables be formed as an array.In GA and PSO terminologies this array is called“Chromosome”and“Particle Position”,respectively.But here in Cuckoo Optimization Algorithm (COA)it is called“habitat”.In a N var-dimensional
optimization Fig.2.Random egg laying in ELR,central red star is the initial habitat of the cuckoo with5eggs;pink stars are the eggs’new nest.
problem,a habitat is an array of1×N var,reprenting current living position of cuckoo.This array is defined as follows:
habitat=[x1,x2,...,x N
var
](1)
自由至上主义
Each of the variable values(x1,x2,...,x N
var
)isfloating point num-ber.The profit of a habitat is obtained by evaluation of profit
function f p at a habitat of(x1,x2,...,x N
var
).So
Profit=f p(habitat)=f p(x1,x2,...,x N
var
)(2) As it is en COA is an algorithm that maximizes a profit function.To u COA in cost minimization problems,one can easily maximize the following profit function:
Profit=−Cost(habitat)=−f c(x1,x2,...,x N
var
)(3) To start the optimization algorithm,a candidate habitat matrix of size N pop×N var is generated.Then some randomly produced num-ber of eggs is suppod for each of the initial cuckoo habitats.In nature,each cuckoo lays from5to20eggs.The values are ud as the upper and lower limits of egg dedication to each cuckoo at different iterations.Another habit of real cuckoos is that they lay eggs within a maximum distance from their habitat.From now on, this maximum range will be called“Egg Laying Radius(ELR)”.In an optimization problem with upper limit of var hi and lower limit of var low for variables,each cuckoo has an egg laying radius(ELR) which is proportional t
o the total number of eggs,number of cur-rent cuckoo’s eggs and also variable limits of var hi and var low.So ELR is defined as:
ELR=˛×
Number of current cuckoo’s eggs
Total number of eggs
×(var hi−var low)(4)
where˛is an integer,suppod to handle the maximum value of ELR.
3.2.Cuckoos’style for egg laying
南北干货Each cuckoo starts laying eggs randomly in some other host birds’nests within her ELR.Fig.2gives a clear view of this concept.
After all cuckoos’eggs are laid in host birds’nests,some of them that are less similar to host birds’own eggs,are detected by host birds and though are thrown out of the nest.So after egg laying process,p%of all eggs(usually10%),with less profit values,will be
R.Rajabioun/Applied Soft Computing11(2011)5508–5518
5511
Fig.3.Immigration of a sample cuckoo toward goal habitat.
killed.The eggs have no chance to grow.Rest of the eggs grow in host nests,hatch and are fed by host birds.Another interesting point about laid cuckoo eggs is that only one egg in a nest has the chance to grow.This is becau when cuckoo egg hatches and the chicks come out,she throws the host bird’s own eggs out of the nest. In ca that host bird’s eggs hatch earlier and cuckoo egg hatches later,cuckoo’s chick eats most of the food host bird brings to the nest(becau of her3times bigger body,she pushes other chicks and eats more).After couple of days the host bird’s own chicks die from hunger and only cuckoo chick remains in the nest.
3.3.Immigration of cuckoos
When young cuckoos grow and become mature,they live in their own area and society for sometime.But when the time for egg laying approaches they immigrate to new and better habitats with more similarity of eggs to host birds and also with more food for new youngsters.After the cuckoo groups are formed in differ-ent areas,the society with best profit value is lected as the goal point for other cuckoos to immigrate.When mature cuckoos live in all over the environment it’s difficul
t to recognize which cuckoo belongs to which group.To solve this problem,the grouping of cuckoos is done with K-means clustering method(a k of3–5ems to be sufficient in simulations).Now that the cuckoo groups are con-stituted their mean profit value is calculated.Then the maximum value of the mean profits determines the goal group and con-quently that group’s best habitat is the new destination habitat for immigrant cuckoos.
When moving toward goal point,the cuckoos do notfly all the way to the destination habitat.They onlyfly a part of the way and also have a deviation.This movement is clearly shown in Fig.3.
As it is en in Fig.3,each cuckoo onlyflies %of all distance toward goal habitat and also has a deviation ofϕradians.The two parameters, andϕ,help cuckoos arch much more positions in all environment.For each cuckoo, andϕare defined as follows: ∼U(0,1)
ϕ∼U(−ω,ω)
(5)
where ∼U(0,1)means that is a random number(uniformly dis-tributed)between0and1.ωis a parameter that constrains the deviation from goal habitat.Anωof /6(rad)ems to be
enough Fig.4.Pudo-code for Cuckoo Optimization Algorithm.
5512R.Rajabioun/Applied Soft Computing11(2011)5508–5518 for good convergence of the cuckoo population to global maximum
profit.
When all cuckoos immigrated toward goal point and new habi-
tats were specified,each mature cuckoo is given some eggs.Then
considering the number of eggs dedicated to each bird,an ELR
is calculated for each cuckoo.Afterward new egg laying process
restarts.
3.4.Eliminating cuckoos in worst habitats
Due to the fact that there is always equilibrium in birds’pop-
ulation so a number of N max controls and limits the maximum
number of live cuckoos in the environment.This balance is becau
of food limitations,being killed by predators and also inability to
find proper nest for eggs.In the modeling propod here in this
paper,only tho N max number of cuckoos survive that have better
profit values,others demi.
3.5.Convergence
After some iterations,all the cuckoo population moves to one
best habitat with maximum similarity of eggs to the host birds and
also with the maximum food resources.This habitat will produce
the maximum profit ever.There will be least egg loss in this best
habitat.Convergence of more than95%of all cuckoos to the same
habitat puts an end to Cuckoo Optimization Algorithm(COA).The
main steps of COA are prented in Fig.4as a pudo-code.In the
next part,COA is applied to some benchmark optimization prob-
lems.
Theoretical proofs for convergence to asymptotic probability
laws in all stochastic optimization algorithms,considering the
Markovian nature of the underlying process,require some sort of
detailed balance or reversibility condition which means the algo-
rithm los much of its efficiency.Furthermore,if one insists on
eventual convergence to the global optima in the strong or even
小孩机票
weak n,very slow annealing is also called for.The strength of
stochastic algorithms stem from the fact that their very probabilis-
tic nature ensures that the algorithms will not necessarily get stuck
at local optima,and there is no need for using any information on
objective gradients,further requiring differentiability conditions.
4.Benchmarks on Cuckoo Optimization Algorithm
In this ction the propod Cuckoo Optimization Algorithm
(COA)is tested with4benchmark functions from Ref.[1],one10-
dimensional Rastrigin function and a real ca study.
4.1.Test cost functions
All the benchmark functions are minimization problems.The
functions are listed below:
Function F1:
f=x×sin(4x)+1.1y×sin(2y)
0<x,y<0,minimum:f(9.039,8.668)=−8.5547
(6)
Function F2:
f=0.5+sin2
x2+y2−0.5
1+0.1(x2+y2)
0<x,y<2,minimum:f(0,0.5)=0.5
(7)
Function F3:
f=(x2+y2)0.25×sin{30[(x+0.5)2+y2]0.1}+|x|+|y|
−∞<x,y<+∞,minimum:f(−0.2,0)=−0.2471
(8)
Fig.5.A3D plot of cost function F1.
Function F4:
f=J0(x2+y2)+0.1
1−x
+0.1
1−y
−∞<x,y<+∞,minimum:f(1,1.6606)=−0.3356
(9)
Function F5(10-dimensional Rastrigin function):
f=10n+
n
i=1
(x i2−10cos(2 x i)),n=9
−5.12≤x i≤5.12,f(0,0,...,0)=0
(10)
First function F1is studied.This function has the global minimum of−18.5547at(x,y)=(9.039,8.668)in interval0<x,y<10.Fig.5 shows the3D plot of this function.
The initial number of cuckoos is t only to20.Each cuckoo can lay between5and10eggs.Fig.6shows initial distribution of cuckoos in problem environment.
Figs.7–12show the cuckoo population habitats in conquent iterations.Convergence is gained at iteration7.The COA has obtained the global minimum just in7iterations.
As it is en in Figs.7–12,cuckoos have found2minima at iter-ation4.Then in iteration5it is en that one group of cuckoos is immigrating toward the global minimum.In iteration6most of cuckoos are in global minimum.Andfinally at iteration7nearly all of cuckoos are on the best habitat,which is the global minimum of the problem.This habitat is(9.0396,8.6706)with the cost value −18.5543.Fig.13depicts the cost minimization for test function
F1.
Fig.6.Initial habitats of cuckoos.
