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

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

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

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

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

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

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

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

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

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

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

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

%求解結果非全局最優[x,f]=fmincon(problem)%采用fmincon進行最小值尋優

%%使用遺傳算法尋找全局最優解problem.solver='ga';problem.fitnessfcn=problem.objective;problem.nvars=2;problem.options=gaoptimset('PopInitRange',[-3;3],...'OutputFcn',@peaksPlotIterates,...'Display','iter')第十六章MATLAB優化算法案例分析與應用16.5基于GA的3D曲面極值尋優圖16-4GA算法尋優過程圖第十六章MATLAB優化算法案例分析與應用16.6基于GA_PSO算法的尋優PSO算法計算函數極值時，常常出現早熟現象，導致求解函數極值存在較大的偏差，然而遺傳算法對于函數尋優采用選擇、交叉、變異算子操作，直接以目標函數作為搜索信息，以一種概率的方式來進行，因此增強了粒子群優化算法的全局尋優能力，加快了算法的進化速度，提高了收斂精度。相應的約束為：選取如下所示的目標函數（最小值）：第十六章MATLAB優化算法案例分析與應用16.6基于GA_PSO算法的尋優%速度更新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優化算法案例分析與應用16.6基于GA_PSO算法的尋優圖16-5GA_PSO適應度曲線第十六章MATLAB優化算法案例分析與應用16.7遺傳算法討論遺傳算法在TSP問題求解上，能夠實現TSP問題的快速求解，然而遺傳算法在二進制編碼以及適應度函數選擇、算子運算、控制策略方面存在一些問題，導致求解結果早熟，收斂誤差較大，因此，遺傳算法在編碼表示、適應度函數、選擇策略和控制參數方面應根據實際問題背景加以改進。16.7.1編碼表示Holland在運用模式定理分析編碼機制時建議使用二進制編碼，但二進制編碼不能直接反映問題的固有結構、精度不高、個體長度大和占用計算機內存多。解決這個問題的措施有：（1）動態編碼即在保持串長不變的前提下減小搜索區域，當算法收斂到某局部最優時增加搜索的精度，從而使得在全局最優