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

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

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

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

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

雜交操作是遺傳算法中最主要的遺傳操作。由交換概率挑選的每兩個父代通過將相異的部分基因進行交換，從而產(chǎn)生新的個體。可以得到新一代個體，新個體組合了其父輩個體的特征。雜交體現(xiàn)了信息交換的思想。16.3.4適應度值評估檢測

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

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

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

變異首先在群體中隨機選擇一定數(shù)量個體，對于選中的個體以一定的概率隨機地改變串結(jié)構(gòu)數(shù)據(jù)中某個基因的值。同生物界一樣，遺傳算法中變異發(fā)生的概率很低，通常取值在0.001到0.01之間。變異為新個體的產(chǎn)生提供了機會。16.3.7中止中止的條件一般有三種情況：（1）給定一個最大的遺傳代數(shù)，算法迭代到最大代數(shù)時停止。（2）給定問題一個下界的計算方法，當進化中達到要求的偏差時，算法終止。（3）當監(jiān)控得到的算法再進化已無法改進解的性能時停止。第十六章MATLAB優(yōu)化算法案例分析與應用16.4遺傳算法的尋優(yōu)計算選取如下所示的目標函數(shù)（最小值）：對于該目標函數(shù)，相應的約束為：%種群更新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)化算法案例分析與應用16.4遺傳算法的尋優(yōu)計算圖16-2GA適應度曲線第十六章MATLAB優(yōu)化算法案例分析與應用16.5基于GA的3D曲面極值尋優(yōu)下列函數(shù)對象%%定義最有問題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進行最小值尋優(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)化算法案例分析與應用16.5基于GA的3D曲面極值尋優(yōu)圖16-4GA算法尋優(yōu)過程圖第十六章MATLAB優(yōu)化算法案例分析與應用16.6基于GA_PSO算法的尋優(yōu)PSO算法計算函數(shù)極值時，常常出現(xiàn)早熟現(xiàn)象，導致求解函數(shù)極值存在較大的偏差，然而遺傳算法對于函數(shù)尋優(yōu)采用選擇、交叉、變異算子操作，直接以目標函數(shù)作為搜索信息，以一種概率的方式來進行，因此增強了粒子群優(yōu)化算法的全局尋優(yōu)能力，加快了算法的進化速度，提高了收斂精度。相應的約束為：選取如下所示的目標函數(shù)（最小值）：第十六章MATLAB優(yōu)化算法案例分析與應用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)化算法案例分析與應用16.6基于GA_PSO算法的尋優(yōu)圖16-5GA_PSO適應度曲線第十六章MATLAB優(yōu)化算法案例分析與應用16.7遺傳算法討論遺傳算法在TSP問題求解上，能夠?qū)崿F(xiàn)TSP問題的快速求解，然而遺傳算法在二進制編碼以及適應度函數(shù)選擇、算子運算、控制策略方面存在一些問題，導致求解結(jié)果早熟，收斂誤差較大，因此，遺傳算法在編碼表示、適應度函數(shù)、選擇策略和控制參數(shù)方面應根據(jù)實際問題背景加以改進。16.7.1編碼表示Holland在運用模式定理分析編碼機制時建議使用二進制編碼，但二進制編碼不能直接反映問題的固有結(jié)構(gòu)、精度不高、個體長度大和占用計算機內(nèi)存多。解決這個問題的措施有：（1）動態(tài)編碼即在保持串長不變的前提下減小搜索區(qū)域，當算法收斂到某局部最優(yōu)時增加搜索的精度，從而使得在全局最優(yōu)