第16章 基于GA尋優(yōu)計(jì)算

第十六章MATLAB優(yōu)化算法案例分析與應(yīng)用第16章基于GA的尋優(yōu)計(jì)算第十六章MATLAB優(yōu)化算法案例分析與應(yīng)用16.1遺傳算法簡(jiǎn)介

遺傳算法（GeneticAlgorithm）是一類借鑒生物界的進(jìn)化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機(jī)制）演化而來的隨機(jī)優(yōu)化搜索方法。它是由美國(guó)的J.Holland教授1975年首先提出，其主要特點(diǎn)是直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。遺傳算法的這些性質(zhì)，已被人們廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號(hào)處理、自適應(yīng)控制和人工生命等領(lǐng)域。它是現(xiàn)代有關(guān)智能計(jì)算中的關(guān)鍵技術(shù)。

由于遺傳算法的整體搜索策略和優(yōu)化搜索方法在計(jì)算時(shí)不依賴于梯度信息或其它輔助知識(shí)，而只需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù)，所以遺傳算法提供了一種求解復(fù)雜系統(tǒng)問題的通用框架，它不依賴于問題的具體領(lǐng)域，所以廣泛應(yīng)用于許多科學(xué)。第十六章MATLAB優(yōu)化算法案例分析與應(yīng)用16.1遺傳算法簡(jiǎn)介隨著應(yīng)用領(lǐng)域的擴(kuò)展，遺傳算法的研究出現(xiàn)了幾個(gè)引人注目的新動(dòng)向：一是基于遺傳算法的機(jī)器學(xué)習(xí)，這一新的研究課題把遺傳算法從歷來離散的搜索空間的優(yōu)化搜索算法擴(kuò)展到具有獨(dú)特的規(guī)則生成功能的嶄新的機(jī)器學(xué)習(xí)算法。這一新的學(xué)習(xí)機(jī)制對(duì)于解決人工智能中知識(shí)獲取和知識(shí)優(yōu)化精煉的瓶頸難題帶來了希望。二是遺傳算法正日益和神經(jīng)網(wǎng)絡(luò)、模糊推理以及混沌理論等其它智能計(jì)算方法相互滲透和結(jié)合，這對(duì)開拓21世紀(jì)中新的智能計(jì)算技術(shù)將具有重要的意義。三是并行處理的遺傳算法的研究十分活躍。這一研究不僅對(duì)遺傳算法本身的發(fā)展，而且對(duì)于新一代智能計(jì)算機(jī)體系結(jié)構(gòu)的研究都是十分重要的。四是遺傳算法和另一個(gè)稱為人工生命的嶄新研究領(lǐng)域正不斷滲透。所謂人工生命即是用計(jì)算機(jī)模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應(yīng)、進(jìn)化和免疫等現(xiàn)象是人工生命的重要研究對(duì)象，而遺傳算法在這方面將會(huì)發(fā)揮一定的作用。五是遺傳算法和進(jìn)化規(guī)劃（EvolutionProgramming，EP）以及進(jìn)化策略（EvolutionStrategy，ES）等進(jìn)化計(jì)算理論日益結(jié)合。EP和ES幾乎是和遺傳算法同時(shí)獨(dú)立發(fā)展起來的，同遺傳算法一樣，它們也是模擬自然界生物進(jìn)化機(jī)制的智能計(jì)算方法，即同遺傳算法具有相同之處，也有各自的特點(diǎn)。目前，這三者之間的比較研究和彼此結(jié)合的探討正形成熱點(diǎn)。第十六章MATLAB優(yōu)化算法案例分析與應(yīng)用16.2遺傳算法特點(diǎn)（1）遺傳算法從問題解的串集開始嫂索，而不是從單個(gè)解開始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個(gè)初始值迭代求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)。（2）許多傳統(tǒng)搜索算法都是單點(diǎn)搜索算法，容易陷入局部的最優(yōu)解。遺傳算法同時(shí)處理群體中的多個(gè)個(gè)體，即對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估，減少了陷入局部最優(yōu)解的風(fēng)險(xiǎn)，同時(shí)算法本身易于實(shí)現(xiàn)并行化。（3）遺傳算法基本上不用搜索空間的知識(shí)或其它輔助信息，而僅用適應(yīng)度函數(shù)值來評(píng)估個(gè)體，在此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點(diǎn)使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。（4）遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo)他的搜索方向。（5）具有自組織、自適應(yīng)和自學(xué)習(xí)性。遺傳算法利用進(jìn)化過程獲得的信息自行組織搜索時(shí)，適應(yīng)度大的個(gè)體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。第十六章MATLAB優(yōu)化算法案例分析與應(yīng)用16.3遺傳算法的基本步驟第十六章MATLAB優(yōu)化算法案例分析與應(yīng)用16.3遺傳算法的基本步驟16.3.1編碼（1）完備性（completeness）：?jiǎn)栴}空間中的所有點(diǎn)（候選解）都能作為GA空間中的點(diǎn)（染色體）表現(xiàn)。（2）健全性（soundness）：GA空間中的染色體能對(duì)應(yīng)所有問題空間中的候選解。（3）非冗余性（nonredundancy）：染色體和候選解一一對(duì)應(yīng)。16.3.2初始群體的生成

隨機(jī)產(chǎn)生N個(gè)初始串結(jié)構(gòu)數(shù)據(jù)，每個(gè)串結(jié)構(gòu)數(shù)據(jù)稱為一個(gè)個(gè)體。N個(gè)個(gè)體構(gòu)成一個(gè)群體。遺傳算法以這N個(gè)初始串結(jié)構(gòu)數(shù)據(jù)作為初始點(diǎn)開始迭代。這個(gè)參數(shù)N需要根據(jù)問題的規(guī)模而確定。進(jìn)化論中的適應(yīng)度，是表示某一個(gè)體對(duì)環(huán)境的適應(yīng)能力，也表示該個(gè)體繁殖后代的能力。遺傳算法的適應(yīng)度函數(shù)也叫評(píng)價(jià)函數(shù)，是用來判斷群體中的個(gè)體的優(yōu)劣程度的指標(biāo)，它是根據(jù)所求問題的目標(biāo)函數(shù)來進(jìn)行評(píng)估的。遺傳算法中初始群體中的個(gè)體是隨機(jī)產(chǎn)生的。第十六章MATLAB優(yōu)化算法案例分析與應(yīng)用16.3遺傳算法的基本步驟16.3.3雜交

雜交操作是遺傳算法中最主要的遺傳操作。由交換概率挑選的每?jī)蓚€(gè)父代通過將相異的部分基因進(jìn)行交換，從而產(chǎn)生新的個(gè)體?？梢缘玫叫乱淮鷤€(gè)體，新個(gè)體組合了其父輩個(gè)體的特征。雜交體現(xiàn)了信息交換的思想。16.3.4適應(yīng)度值評(píng)估檢測(cè)

計(jì)算交換產(chǎn)生的新個(gè)體的適應(yīng)度。適應(yīng)度是用來度量種群中個(gè)體優(yōu)劣的指標(biāo)，這里的適應(yīng)度就是特征組合的判據(jù)的值。這個(gè)判據(jù)的選取是遺傳算法的關(guān)鍵。

遺傳算法在搜索進(jìn)化過程中一般不需要其他外部信息，僅用評(píng)估函數(shù)來評(píng)估個(gè)體或解的優(yōu)劣，并作為以后遺傳操作的依據(jù)。由于遺傳算法中，適應(yīng)度函數(shù)要比較排序并在此基礎(chǔ)上計(jì)算選擇概率，所以適應(yīng)度函數(shù)的值要取正值。由此可見，在不少場(chǎng)合，將目標(biāo)函數(shù)映射成求最大值形式且函數(shù)值非負(fù)的適應(yīng)度函數(shù)是必要的。第十六章MATLAB優(yōu)化算法案例分析與應(yīng)用16.3遺傳算法的基本步驟16.3.5選擇

選擇的目的是為了從交換后的群體中選出優(yōu)良的個(gè)體，使它們有機(jī)會(huì)作為父代為下一代繁衍子孫。進(jìn)行選擇的原則是適應(yīng)性強(qiáng)的個(gè)體為下一代貢獻(xiàn)的概率大，體現(xiàn)了達(dá)爾文的適者生存原則。16.3.6變異

變異首先在群體中隨機(jī)選擇一定數(shù)量個(gè)體，對(duì)于選中的個(gè)體以一定的概率隨機(jī)地改變串結(jié)構(gòu)數(shù)據(jù)中某個(gè)基因的值。同生物界一樣，遺傳算法中變異發(fā)生的概率很低，通常取值在0.001到0.01之間。變異為新個(gè)體的產(chǎn)生提供了機(jī)會(huì)。16.3.7中止中止的條件一般有三種情況：（1）給定一個(gè)最大的遺傳代數(shù)，算法迭代到最大代數(shù)時(shí)停止。（2）給定問題一個(gè)下界的計(jì)算方法，當(dāng)進(jìn)化中達(dá)到要求的偏差時(shí)，算法終止。（3）當(dāng)監(jiān)控得到的算法再進(jìn)化已無法改進(jìn)解的性能時(shí)停止。第十六章MATLAB優(yōu)化算法案例分析與應(yīng)用16.4遺傳算法的尋優(yōu)計(jì)算選取如下所示的目標(biāo)函數(shù)（最小值）：對(duì)于該目標(biāo)函數(shù)，相應(yīng)的約束為：%種群更新GAGApop=Select2(GApop,fitness,popsize);

%交叉操作GAGApop=Cross(pc,lenchrom,GApop,popsize,bound);

%變異操作GAGApop=Mutation(pm,lenchrom,GApop,popsize,[imaxgen],bound);

pop=GApop;第十六章MATLAB優(yōu)化算法案例分析與應(yīng)用16.4遺傳算法的尋優(yōu)計(jì)算圖16-2GA適應(yīng)度曲線第十六章MATLAB優(yōu)化算法案例分析與應(yīng)用16.5基于GA的3D曲面極值尋優(yōu)下列函數(shù)對(duì)象%%定義最有問題problem=createOptimProblem('fmincon',...'objective',@(x)peaks(x(:,1),x(:,2)),...'nonlcon',@circularConstraint,...'x0',[-1-1],.'lb',[-3-3],'ub',[33],...'options',optimset('OutputFcn',@peaksPlotIterates))

%求解結(jié)果非全局最優(yōu)[x,f]=fmincon(problem)%采用fmincon進(jìn)行最小值尋優(yōu)

%%使用遺傳算法尋找全局最優(yōu)解problem.solver='ga';problem.fitnessfcn=problem.objective;problem.nvars=2;problem.options=gaoptimset('PopInitRange',[-3;3],...'OutputFcn',@peaksPlotIterates,...'Display','iter')第十六章MATLAB優(yōu)化算法案例分析與應(yīng)用16.5基于GA的3D曲面極值尋優(yōu)圖16-4GA算法尋優(yōu)過程圖第十六章MATLAB優(yōu)化算法案例分析與應(yīng)用16.6基于GA_PSO算法的尋優(yōu)PSO算法計(jì)算函數(shù)極值時(shí)，常常出現(xiàn)早熟現(xiàn)象，導(dǎo)致求解函數(shù)極值存在較大的偏差，然而遺傳算法對(duì)于函數(shù)尋優(yōu)采用選擇、交叉、變異算子操作，直接以目標(biāo)函數(shù)作為搜索信息，以一種概率的方式來進(jìn)行，因此增強(qiáng)了粒子群優(yōu)化算法的全局尋優(yōu)能力，加快了算法的進(jìn)化速度，提高了收斂精度。相應(yīng)的約束為：選取如下所示的目標(biāo)函數(shù)（最小值）：第十六章MATLAB優(yōu)化算法案例分析與應(yīng)用16.6基于GA_PSO算法的尋優(yōu)%速度更新PSO選擇更新V(j,:)=V(j,:)+c1*rand*(gbest(j,:)-pop(j,:))+c2*rand*(zbest-pop(j,:));V(j,find(V(j,:)>Vmax))=Vmax;V(j,find(V(j,:)<Vmin))=Vmin;

%種群更新PSO選擇更新pop(j,:)=pop(j,:)+0.5*V(j,:);pop(j,find(pop(j,:)>popmax))=popmax;pop(j,find(pop(j,:)<popmin))=popmin;

%交叉操作GAGApop=Cross(pc,lenchrom,pop,popsize,bound);

%變異操作GA變異GApop=Mutation(pm,lenchrom,GApop,popsize,[imaxgen],bound);

pop=GApop;%GApop-->PSOpop第十六章MATLAB優(yōu)化算法案例分析與應(yīng)用16.6基于GA_PSO算法的尋優(yōu)圖16-5GA_PSO適應(yīng)度曲線第十六章MATLAB優(yōu)化算法案例分析與應(yīng)用16.7遺傳算法討論遺傳算法在TSP問題求解上，能夠?qū)崿F(xiàn)TSP問題的快速求解，然而遺傳算法在二進(jìn)制編碼以及適應(yīng)度函數(shù)選擇、算子運(yùn)算、控制策略方面存在一些問題，導(dǎo)致求解結(jié)果早熟，收斂誤差較大，因此，遺傳算法在編碼表示、適應(yīng)度函數(shù)、選擇策略和控制參數(shù)方面應(yīng)根據(jù)實(shí)際問題背景加以改進(jìn)。16.7.1編碼表示Holland在運(yùn)用模式定理分析編碼機(jī)制時(shí)建議使用二進(jìn)制編碼，但二進(jìn)制編碼不能直接反映問題的固有結(jié)構(gòu)、精度不高、個(gè)體長(zhǎng)度大和占用計(jì)算機(jī)內(nèi)存多。解決這個(gè)問題的措施有：（1）動(dòng)態(tài)編碼即在保持串長(zhǎng)不變的前提下減小搜索區(qū)域，當(dāng)算法收斂到某局部最優(yōu)時(shí)增加搜索的精度，從而使得在全局最優(yōu)