主要參考書(shū)：MATLAB6.5輔助優(yōu)化計(jì)算與設(shè)計(jì)飛思科技產(chǎn)品研發(fā)中心編著電子工業(yè)出版社2003.1遺傳算法及其應(yīng)用陳國(guó)良主要參考書(shū)：MATLAB6.5輔助優(yōu)化計(jì)算與設(shè)計(jì)飛思科技產(chǎn)品研發(fā)中心編著電子工業(yè)出版社2003.1遺傳算法及其應(yīng)用陳國(guó)良等編著人民郵電出版社1996.6主要內(nèi)容：MMM遺傳算法簡(jiǎn)介遺傳算法的MATLAB實(shí)現(xiàn)應(yīng)用舉例在工業(yè)工程中，許多最優(yōu)化問(wèn)題性質(zhì)十分復(fù)雜,很難用傳統(tǒng)的優(yōu)化方法來(lái)求解.自I960年以來(lái)，人們對(duì)求解這類難解問(wèn)題日益增加.一種模仿生物自然進(jìn)化過(guò)程的、被稱為“進(jìn)化算法(evolutionaryalgorithm)”的隨機(jī)優(yōu)化技術(shù)在解這類優(yōu)化難題中顯示了優(yōu)于傳統(tǒng)優(yōu)化算法的性能。目前，進(jìn)化算法主要包括三個(gè)研究領(lǐng)域：遺傳算法、進(jìn)化規(guī)劃和進(jìn)化策略。其中遺傳算法是迄今為止進(jìn)化算法中應(yīng)用最多、比較成熟、廣為人知的算法。一、遺傳算法簡(jiǎn)介遺傳算法(GeneticAlgorithm,GA)最先是由美國(guó)Mic-hgan大學(xué)的JohnHolland于1975年提出的。遺傳算法是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過(guò)程的計(jì)算模型。它的思想源于生物遺傳學(xué)和適者生存的自然規(guī)律，是具有“生存+檢測(cè)”的迭代過(guò)程的搜索算法。遺傳算法以一種群體中的所有個(gè)體為對(duì)象，并利用隨機(jī)化技術(shù)指導(dǎo)對(duì)一個(gè)被編碼的參數(shù)空間進(jìn)行高效搜索。其中，選擇、交叉和變異構(gòu)成了遺傳算法的遺傳操作；參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作設(shè)計(jì)、控制參數(shù)設(shè)定等5個(gè)要素組成了遺傳算法的核心內(nèi)容。遺傳算法的基本步驟：遺傳算法是一種基于生物自然選擇與遺傳機(jī)理的隨機(jī)搜索算法，與傳統(tǒng)搜索算法不同，遺傳算法從一組隨機(jī)產(chǎn)生的稱為“種群(Population)"的初始解開(kāi)始搜索過(guò)程。種群中的每個(gè)個(gè)體是問(wèn)題的一個(gè)解，稱為“染色體(chromosome)”。染色體是一串符號(hào)，比如一個(gè)二進(jìn)制字符串。這些染色體在后續(xù)迭代中不斷進(jìn)化，稱為遺傳。在每一代中用“適值(fitness)”來(lái)測(cè)量染色體的好壞，生成的下一代染色體稱為后代(offspring)。后代是由前一代染色體通過(guò)交叉(crossover)或者變異(mutation)運(yùn)算形成的。在新一代形成過(guò)程中，根據(jù)適度的大小選擇部分后代，淘汰部分后代。從而保持種群大小是常數(shù)。適值高的染色體被選中的概率較高，這樣經(jīng)過(guò)若干代之后，算法收斂于最好的染色體，它很可能就是問(wèn)題的最優(yōu)解或次優(yōu)解。主要步驟如下所示：編碼：GA在進(jìn)行搜索之前先將解空間的解數(shù)據(jù)表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)，這些串結(jié)構(gòu)數(shù)據(jù)的不同組合便構(gòu)成了不同的點(diǎn)。初始群體的生成：隨機(jī)產(chǎn)生N個(gè)初始串結(jié)構(gòu)數(shù)據(jù)，每個(gè)串結(jié)構(gòu)數(shù)據(jù)稱為一個(gè)個(gè)體，N個(gè)個(gè)體構(gòu)成了一個(gè)群體。GA以這N個(gè)串結(jié)構(gòu)數(shù)據(jù)作為初始點(diǎn)開(kāi)始迭代。

（3）適應(yīng)性值評(píng)估檢測(cè)：適應(yīng)性函數(shù)表明個(gè)體或解的優(yōu)劣性。對(duì)于不同的問(wèn)題，話應(yīng)性函數(shù)的定義方式也不同。（4）選擇：選擇的目的是為了從當(dāng)前群體個(gè)選出優(yōu)良的個(gè)體，使它們有機(jī)會(huì)作為父代為下一代繁殖子孫。遺傳算法通過(guò)選擇過(guò)程體現(xiàn)這一思想，進(jìn)行選擇的原則是適應(yīng)性強(qiáng)的個(gè)體為下一代貢獻(xiàn)一個(gè)或多個(gè)后代的概率大。選擇實(shí)現(xiàn)了達(dá)爾文的適者生存原則。（5）交叉：交叉操作是遺傳算法中最主要的遺傳操作。通過(guò)交叉操作可以得到新一代個(gè)體，新個(gè)體組合了其父輩個(gè)體的特性。交叉體現(xiàn)了信息交換的思想。（6）變異：變異首先在群體中隨機(jī)選擇一個(gè)個(gè)體，對(duì)于選中的個(gè)體以一定的概率隨機(jī)地改變串結(jié)構(gòu)數(shù)據(jù)中某個(gè)串的值。同生物界一樣，GA中變異發(fā)生的概率很低，通常取值在0.001?0.01之間。變異為新個(gè)體的產(chǎn)中提供了機(jī)會(huì)。實(shí)際上，遺傳算法中有兩類運(yùn)算：?遺傳運(yùn)算：交叉和變異編碼和種群生成?進(jìn)化運(yùn)算：選擇GA的計(jì)算過(guò)程流程圖遺傳算法的特點(diǎn)GA是對(duì)問(wèn)題參數(shù)的編碼組進(jìn)行計(jì)算，而不是針對(duì)參數(shù)本身。編碼和種群生成GA的搜索是從問(wèn)題解的編碼組開(kāi)始搜素、而不是從單個(gè)解開(kāi)始。GA使用目標(biāo)函數(shù)值（適應(yīng)度）這一信息進(jìn)行搜索，而不需導(dǎo)數(shù)等其他信息。GA算法使用的選擇、交叉、變異這三個(gè)算子都是隨機(jī)操作，而不是確定規(guī)則舉例圖解說(shuō)明計(jì)算流程遺傳算法求3,31」極值的計(jì)算流程甲編號(hào)初始群體［隨機(jī)產(chǎn)生）（n—4）X值（無(wú)符號(hào)整數(shù)）適應(yīng)度心=選擇概率己=A/S/適應(yīng)度期望值/i/7實(shí)際計(jì)數(shù)（來(lái)自賭輪）復(fù)制后交配率（豎線表示交叉處）配對(duì)隨機(jī)選擇）交受位置（隨機(jī)選擇〉新??代群體X值（無(wú)符號(hào)蘑數(shù)）適應(yīng)度JCx）=1011011316901405810110J124011001214421100024576049197Z1100IC14U0D125625301000864006022011100。4211011277294100111936103112311QIQ11321000016256適應(yīng)度總和（Sn11701004004.04號(hào)V-平均適應(yīng)度)2930251001.0最大適應(yīng)度5760491972-0,'■<5<y門A二、遺傳算法的MATLAB實(shí)現(xiàn)需要如下主函數(shù)：編碼和種群生成function[pop]=initializega(num,bounds,evalFN,evalOps,options)%pop-theinitial,evaluated,randompopulation%num-thesizeofthepopulation,i.e.thenumbertocreate%bounds-thenumberofpermutationsinanindividual(e.g.,number%ofcitiesinatsp%evalFN-theevaluationfn,usuallythenameofthe.mfileforevaluation%evalOps-anyoptionstobepassedtotheevalfunctiondefaults[]%options-optionstotheinitializefunction,ie.[eps,float/binary,prec]%whereepsistheepsilonvalueandthesecondoptionis1for%orderOps,precistheprecisionofthevariablesdefaults[1e-61]交叉function[c1,c2]=arithXover(p1,p2,bounds,Ops)%ArithcrossovertakestwoparentsP1,P2andperformsaninterpolation%alongthelineformedbythetwoparents.%%function[c1,c2]=arithXover(p1,p2,bounds,Ops)%p1-thefirstparent([solutionstringfunctionvalue])%p2-thesecondparent([solutionstringfunctionvalue])%bounds-theboundsmatrixforthesolutionspace%Ops-Optionsmatrixforarithcrossover[gen#ArithXovers]選擇normGeomSelect：NormGeomSelectisarankingselectionfunctionbasedonthenormalizedgeometricdistribution.(基于正態(tài)分布的序列選擇函數(shù))變異fUnction[newPop]=normGeomSelect(oldPop,options)%NormGeomSelectisarankingselectionfunctionbasedonthenormalized%geometricdistribution.%%function[newPop]=normGeomSelect(oldPop,options)%newPop-thenewpopulationselectedfromtheoldPop%oldPop-thecurrentpopulation%options-optionstonormGeomSelect[genprobability_of_selecting_best]一些輔助函數(shù)：f2b:Returnthebinaryrepresentationofthefloatnumberfval(將浮點(diǎn)數(shù)轉(zhuǎn)化為二進(jìn)制數(shù))b2f：Returnthefloatnumbercorresponingtothebinaryrepresentationofbval.(將二進(jìn)制數(shù)轉(zhuǎn)化為浮點(diǎn)數(shù))nonUnifMutation：Nonuniformmutationchangesoneoftheparametersoftheparentbasedonanon-uniformprobabilitydistribution.ThisGaussiandistributionstartswide,andnarrowstoapointdistributionasthecurrentgenerationapproachesthemaximumgeneration.(基于非均一概率分布進(jìn)行非均一變異)maxGenTermReturns1,i.e.terminatestheGAwhenthemaximal_generationisreached.(當(dāng)?shù)螖?shù)大于最大迭代次數(shù)時(shí)，終止遺傳算法，返回為1，否則返回為0。)roulet：erouletteisthetraditionalselectionfunctionwiththeprobabilityofsurvivingequaltothefittnessofi/sumofthefittnessofallindividuals三、應(yīng)用舉例1.計(jì)算下列函數(shù)的最大值。f(x)=x+10*sin(5x)+7cos(4x),x￡[0,9]方式1>>gademo方式2step1編寫(xiě)目標(biāo)函數(shù)gademo1eval1.mfunction[sol,val]=gaDemo1Eval(sol,options)x=sol(1);val=x+10*sin(5*x)+7*cos(4*x);step2生成初始種群，大小為10initPop=initializega(10,[0,9],'gademo1eval1',[],[1e-6,1]);step325次遺傳迭代[x,endPop,bpop,trace]=ga([09],'gademo1eva1',[],initPop,...[1e-611],'maxGenTerm',25,...'normGeomSelect',[0.08],...['arithXover'],[2],...'nonUnifMutation',[2,25,3])%OutputArguments:%x-thebestsolutionfoundduringthecourseoftherun%endPop-thefinalpopulation%bPop-atraceofthebestpopulation(解的變化)%traceInfo-amatrixofbestandmeansofthegaforeachgeneration(種群平均值的變化)%%InputArguments:%bounds-amatrixofupperandlowerboundsonthevariables%evalFN-thenameoftheevaluation.mfunction%evalOps-optionstopasstotheevaluationfunction([NULL])%startPop-amatrixofsolutionsthatcanbeinitialized%frominitialize.m%opts-[epsilon,prob_ops,display]changerequiredtoconsidertwosolutionsdifferent,prob_ops0ifyouwanttoapplythe%geneticoperatorsprobabilisticlytoeachsolution,1ifyouaresupplyingadeterministicnumberofoperatorapplicationsanddisplayis1tooutputprogress0forquiet.([1e-610])%termFN-nameofthe.mterminationfunction(['maxGenTerm'])%termOps-optionsstringtobepassedtotheterminationfunction([100]).%selectFN-nameofthe.mselectionfunction(['normGeomSelect'])%selectOpts-optionsstringtobepassedtoselectafter%select(pop,#,opts)([0.08])%xOverFNS-astringcontainingblankseperatednamesofXover.mfiles(['arithXoverheuristicXoversimpleXover'])%xOverOps-AmatrixofoptionstopasstoXover.mfileswiththefirstcolumnbeingthenumberofthatxOvertoperformsimiliarlyformutation([20;23;20])%mutFNs-astringcontainingblankseperatednamesofmutation.mfiles(['boundaryMutationmultiNonUnifMutation...%nonUnifMutationunifMutation'])%mutOps-AmatrixofoptionstopasstoXover.mfileswiththefirstcolumnbeingthenumberofthatxOvertoperformsimiliarlyformutation([400;61003;41003;400])求sin(x)在0到3.14之間的最大值.function[sol,val]=sin1(sol,options)x=sol(1);val=sin(x);initPop=initializega(10,[0,3.14],'sin1',[],[1e-6,1]);[x,endPop,bpop,trace]=ga([03.14],'sin1',[],initPop,...[1e-611],'maxGenTerm',25,...'normGeomSelect',[0.08],...['arithXover'],[2],...'nonUnifMutation',[2,25,3])binaryExample.m二元函數(shù)例子二進(jìn)制編碼方式1>>binaryExample方式2function[sol,val]=gaMichEval(sol,options)val=21.5+sol(1)*sin(4*pi*sol(1))+sol(2)*sin(20*pi*sol(2));%%%%%%%%%%%%%%globalbounds%Settingtheseedbacktothebeginningforcomparisonsakerand('seed',0)%CrossoverOperatorsxFns='simpleXover';xOpts=[.4];%MutationOperatorsmFns='binaryMutation';mOpts=[0.005];%TerminationOperatorstermFns='maxGenTerm';termOps=[200];%200Generations%SelectionFunctionselectFn='roulette'selectOps=[];%EvaluationFunctionevalFn='gaMichEval';evalOps=[];%Boundsonthevariablesbounds=[-3,12.1;4.1,5.8];%GAOptions[epsilonfloat/binardisplay]gaOpts=[1e-601];%Generateanintializepopulationofsize20startPop=initializega(20,bounds,'gaMichEval',[],[1e-60]);[xendPopbestPoptrace]=ga(bounds,evalFn,evalOps,startPop,gaOpts,...termFns,termOps,selectFn,selectOps,xFns,xOpts,mFns,mOpts);%xisthebestsolutionfoundx%endPopistheendingpopulationendPop%traceisatraceofthebestvalueandaveragevalueofgenerationstraceclfplot(trace(:,1),trace(:,2));holdonplot(trace(:,1),trace(:,3));%Letsincreasethepopulationsizebyrunningthedefaults%rand('seed',0)termOps=[100];[xendPopbestPoptrace]=ga(bounds,evalFn,evalOps,[],gaOpts,termFns,termOps,...selectFn,selectOps);%xisthebestsolutionfoundx%endPopistheendingpopulation%endPop%traceisatraceofthebestvalueandaveragevalueofgenerations%trace%Plotthebestovertimeclfplot(trace(:,1),trace(:,2));%Addtheaveragetothegraphholdonplot(trace(:,1),trace(:,3));floatExample.m二元函數(shù)例子浮點(diǎn)編碼globalbounds%Settingtheseedtothesameforbinaryrand('seed',156789)%CrossoverOperatorsxFns='arithXoverheuristicXoversimpleXover';xOpts=[10;13;10];%MutationOperatorsmFns='boundaryMutationmultiNonUnifMutationnonUnifMutationunifMutation';mOpts=[200;32003;22003;200];%TerminationOperatorstermFns='maxGenTerm';termOps=[200];%200Generations%SelectionFunctionselectFn='normGeomSelect';selectOps=[0.08];%EvaluationFunctionevalFn='gaMichEval';evalOps=[];%Boundsonthevariablesbounds=[-312.1;4.15.8];%GAOptions[epsilonfloat/binardisplay]gaOpts=[1e-611];%Generateanintializepopulationofsize20startPop=initializega(20,bounds,'gaMichEval',[1e-61])[xendPopbestPoptrace]=ga(bounds,evalFn,evalOps,startPop,gaOpts,...termFns,termOps,selectFn,selectOps,xFns,xOpts,mFns,mOpts);%xisthebestsolutionfoundx%endPopistheendingpopulationendPop%bestPopisthebestsolutiontrackedovergenerationsbestPop%Plotthebestovertimeclfplot(trace(:,1),trace(:,2));%Addtheaveragetothegraphholdonplot(trace(:,1),trace(:,3));%Letsincreasethepopulationsizebyrunningthedefaults[xendPopbestPoptrace]=ga(bounds,evalFn,evalOps,[],gaOpts);%xisthebestsolutionfoundx%endPopistheendingpopulationendPop%bestPopisthebestsolutiontrackedovergenerationsbestPop%Plotthebestovertimeclfplot(trace(:,1),trace(:,2));%Addtheaveragetothegraphholdonplot(trace(:,1),trace(:,3));5,求解貨郎擔(dān)問(wèn)題(TSP)3.4貨郎擔(dān)問(wèn)題近幾年來(lái)，基于遺傳算法方法求解貨郎擔(dān)(TSP)問(wèn)題的研究相當(dāng)活躍。例如DavidB.Fogel[12j,Grefenstette-13-,Goldberg[u：,等。在遺傳算法研究中,TSP問(wèn)題已被廣泛弛用于評(píng)價(jià)不同的遺傳操作及選擇機(jī)制的性能?之所以如此，主要有以下幾個(gè)方面的原因：TSP問(wèn)題是一個(gè)典型的、易于描述卻難以處理的NP完全間題。有效地解決TSP問(wèn)題在可計(jì)算理論上有著重要的理論價(jià)值。TSP問(wèn)題是諸多領(lǐng)域內(nèi)出現(xiàn)的多種復(fù)雜問(wèn)題的集中概括和簡(jiǎn)化形式。因此，快速、有效地解決TSP問(wèn)題有著極高的實(shí)際應(yīng)用價(jià)值；O)TSP問(wèn)題因其典型性已成為各種啟發(fā)式的搜索、優(yōu)化算法的間接比較標(biāo)準(zhǔn)(如神經(jīng)網(wǎng)絡(luò)優(yōu)化法