布谷鸟算法

今天我要讲的内容是布谷鸟算法，英文叫做Cuckoosearch(CSalgorithm)。首先还是同样，介绍一下这个算法的英文含义，Cuckoo是布谷鸟的意思，啥是布谷鸟呢，是一种叫做布谷的鸟，o(∩_∩)o，这种鸟她妈很懒，自己生蛋自己不养，一般把它的宝宝扔到别的种类鸟的鸟巢去。但是呢，当孵化后，遇到聪明的鸟妈妈，一看就知道不是亲生的，直接就被鸟妈妈给杀了。于是这群布谷鸟宝宝为了保命，它们就模仿别的种类的鸟叫，让智商或者情商极低的鸟妈妈误认为是自己的亲宝宝，这样它就活下来了。Search指的是搜索，这搜索可不是谷歌一下，你就知道。而是搜索最优值，举个简单的例子，y=(x-0.5)^2+1，它的最小值是1，位置是(0.5,1)，我们要搜索的就是这个位置。现在我们应该清楚它是干嘛的了吧，它就是为了寻找最小值而产生的一种算法，有些好装X的人会说，你傻X啊，最小值不是-2a/b吗，用你找啊?说的不错，确实是，但是要是我们的函数变成y=sin(x^3+x^2)+e^cos(x^3)+log(tan(x)+10，你怎么办吶？你解不了，就算你求导数，但是你知道怎么解导数等于0吗？所以我们就得引入先进的东西来求最小值。为了使大家容易理解，我还是用y=(x-0.5)^2+1来举例子，例如我们有4个布谷鸟蛋（也就是4个x坐标），鸟妈妈发现不是自己的宝宝的概率是0.25，我们x的取值范围是[0,1]之间，于是我们就可以开始计算了。目标：求x在[0,1]之内的函数y=(x-0.5)^2+1最小值（1）初始化x的位置，随机生成4个x坐标，x1=0.4，x2=0.6，x3=0.8，x4=0.3——X=[0.4,0.6,0.8,0.3]（2）求出y1~y4，把x1~x4带入函数，求得Y=[1,31,1.46,1.69,1.265]，并选取当前最小值ymin=y4=1.265（3）开始定出一个y的最大值为Y_global=INF（无穷大），然后与ymin比较，把Y中最小的位置和值保留，例如Y_global=INFymin=1.265，所以令Y_global=1.265（4）记录Y_global的位置，（0.3，1.265）。（5）按概率0.25，随机地把X中的值过塞子，选出被发现的蛋。例如第二个蛋被发现x2=0.6，那么他就要随机地变换位子，生成一个随机数，例如0.02，然后把x2=x2+0.02=0.62，之后求出y2=1.4794。那么X就变为了X=[0.4,0.62,0.8,0.3]，Y=[1,31,1.4794,1.69,1.265]。（6）进行莱维飞行，这名字听起来挺高大上，说白了，就是把X的位置给随机地改变了。怎么变？有一个公式x=x+alpha*L。L=S*(X-Y_global)*rand3S=[rand1*sigma/|rand2|]^(1/beta)sigma=0.6966beta=1.5alpha=0.01rand1~rand3为正态分布的随机数然后我们把X=[0.4,0.6,0.8,0.3]中的x1带入公式，首先随机生成rand1=-1.2371，rand2=-2.1935，rand3=-0.3209，接下来带入公式中，获得x1=0.3985之后同理计算:x2=0.6172x3=0.7889x4=0.3030（7）更新矩阵X，X=[0.3985,0.6172,0.7889,0.3030]（8）计算Y=[1.3092,1.4766,1.6751,1.2661]，并选取当前最小值ymin=y4=1.2661，然后与ymin比较，把Y中最小的位置和值保留，例如Y_global=1.265ymin=1.2661，所以令Y_global=1.265（9）返回步骤（5）用更新的X去循环执行，经过多次计算即可获得y的最优值和的最值位置(x,y)1.%-----------------------------------------------------------------2.%CuckooSearch(CS)algorithmbyXin-SheYangandSuashDeb%3.%ProgrammedbyXin-SheYangatCambridgeUniversity%4.%Programmingdates:Nov2008toJune2009%5.%Lastrevised:Dec2009(simplifiedversionfordemoonly)%6.%-----------------------------------------------------------------7.%Papers--CitationDetails:8.%1)X.-S.Yang,S.Deb,CuckoosearchviaLevyflights,9.%in:Proc.ofWorldCongressonNature&BiologicallyInspired10.%Computing(NaBIC2009),December2009,India,11.%IEEEPublications,USA,pp.210-214(2009).12.%)X.-S.Yang,S.Deb,Engineeringoptimizationbycuckoosearch,14.%Int.J.MathematicalModellingandNumericalOptimisation,15.%Vol.1,No.4,330-343(2010).16.%(CS),astheLevyflightsandgenerationof%20.%newsolutionsmayuseslightlydifferentmethods.%21.%Thepseudocodewasgivensequentially(selectacuckooetc),%22.%buttheimplementationhereusesMatlab'svectorcapability,%23.%whichresultsinneater/bettercodesandshorterrunningtime.%24.%Thisimplementationisdifferentandmoreefficientthanthe%25.%thedemocodeprovidedinthebookby26.%YangX.S.,Nature-InspiredMetaheuristicAlgoirthms,%27.%2ndEdition,LuniverPress,(2010).%28.%---------------------------------------------------------------%29.30.%===============================================================%31.%Notes:%32.%Differentimplementationsmayleadtoslightlydifferent%33.%behavourand/orresults,butthereisnothingwrongwithit,%34.%asthisisthenatureofrandomwalksandallmetaheuristics.%35.%-----------------------------------------------------------------36.37.%AdditionalNote:Thisversionusesafixednumberofgeneration%38.%(notagiventolerance)becausemanyreadersaskedmetoadd%39.%orimplementthisoption.Thanks.%40.function[bestnest,fmin]=cuckoo_search_new(n)41.ifnargin1,42.%Numberofnests(ordifferentsolutions)43.n=25;44.end45.46.%Discoveryrateofalieneggs/solutions47.pa=0.25;48.49.%%Changethisifyouwanttogetbetterresults50.N_IterTotal=1000;51.%%Simpleboundsofthesearchdomain52.%Lowerbounds53.nd=15;54.Lb=-5*ones(1,nd);55.%Upperbounds56.Ub=5*ones(1,nd);57.58.%Randominitialsolutions59.fori=1:n,60.nest(i,:)=Lb+(Ub-Lb).*rand(size(Lb));61.end62.63.%Getthecurrentbest64.fitness=10^10*ones(n,1);65.[fmin,bestnest,nest,fitness]=get_best_nest(nest,nest,fitness);66.67.N_iter=0;68.%%Startingiterations69.foriter=1:N_IterTotal,70.%Generatenewsolutions(butkeepthecurrentbest)71.new_nest=get_cuckoos(nest,bestnest,Lb,Ub);72.[fnew,best,nest,fitness]=get_best_nest(nest,new_nest,fitness);73.%Updatethecounter74.N_iter=N_iter+n;75.%Discoveryandrandomization76.new_nest=empty_nests(nest,Lb,Ub,pa);77.78.%Evaluatethissetofsolutions79.[fnew,best,nest,fitness]=get_best_nest(nest,new_nest,fitness);80.%Updatethecounteragain81.N_iter=N_iter+n;82.%Findthebestobjectivesofar83.iffnewfmin,84.fmin=fnew;85.bestnest=best;86.end87.end%%Endofiterations88.89.%%Post-optimizationprocessing90.%%Displayallthenests91.disp(strcat('Totalnumberofiterations=',num2str(N_iter)));92.fmin93.bestnest94.95.%%---------------Allsubfunctionsarelistbelow------------------96.%%Getcuckoosbyramdomwalk97.functionnest=get_cuckoos(nest,best,Lb,Ub)98.%Levyflights99.n=size(nest,1);100.%Levyexponentandcoefficient101.%Fordetails,seeequation