進化算法及其在數值計算中的應用.ppt

1、進化算法及其在數值計算中的應用,最優(yōu)化問題：在滿足一定的約束條件下，尋找一組參數值， 使某些最優(yōu)性度量得到滿足，即使系統(tǒng)的某些性能指標達到 最大或最小。最優(yōu)化問題的應用涉及工業(yè)技術、社會、經濟、 管理等各個領域，具有重要意義。 最優(yōu)化問題的一般形式為： 式中， 稱為目標函數， 稱為約束函數。 極大極小的轉換：,數學規(guī)劃：在一些等式或不等式約束條件下，求一個目標函 數的極大（或極?。┑膬?yōu)化模型稱為數學規(guī)劃。根據有、無 約束條件可以分為約束數學規(guī)劃和無約束數學規(guī)劃；根據目 標函數 和約束函數 是否為線性函數，分為 線性規(guī)劃和非線性規(guī)劃；根據問題中是否只有一個目標函數， 分為單目標規(guī)劃和多目標規(guī)劃。

2、 很多非常重要的問題是線性的（或者用線性函數能夠很好地 近似表示），因此線性規(guī)劃的研究具有重要意義。與非線性 規(guī)劃相比，線性規(guī)劃的研究更加成熟。,進化算法及其在數值計算中的應用,在數學規(guī)劃中，把滿足所有約束條件的點 稱為可行點 （或可行解），所有可行點組成的點集稱為可行域，記為 于是數學規(guī)劃即為求 ，并且使得 在 上達到 最大（或最小），把 稱為最優(yōu)點（最優(yōu)解），稱 為最優(yōu)值。,進化算法及其在數值計算中的應用,進化計算（Evolutionary Computation，EC）受生物進化論 和遺傳學等理論的啟發(fā)，是一類模擬生物進化過程與機制，自 組織、自適應的對問題進行求解的人工智能技術。進化計

3、算的 具體實現方法與形式稱為進化算法（Evolutionary Algorithm， EA）。 進化算法是一種具有“生成+檢測”（generate-and-test）迭代 過程的搜索算法，算法體現群體搜索和群體中個體之間信息 交換兩大策略，為每個個體提供了優(yōu)化的機會，使得整個群體 在優(yōu)勝劣汰（survival of the fittest）的選擇機制下保證進化的 趨勢。,進化算法及其在數值計算中的應用,進化算法采用編碼的形式來表示復雜結構，并將每個編碼稱 為一個個體（individual），算法維持一定數目的編碼集合， 稱為種群或群體（population）。通過對群體中個體進行相應 的操作，

4、最終獲得一些具有較高性能指標的個體。 進化算法的研究始于20世紀60年代，Holland針對機器學習問 題發(fā)展了遺傳算法（genetic algorithm，GA），Fogel對于優(yōu) 化模型系統(tǒng)提出了進化規(guī)劃（evolutionary programming，EP） Rechenberg和Schwefel對于數值優(yōu)化問題提出了進化策略 （evolutionary strategy，ES）。,進化算法及其在數值計算中的應用,遺傳算法是一種宏觀意義下的仿生算法，它模仿的機制是一 切生命與智能的產生與進化過程。遺傳算法通過模擬達爾文 “優(yōu)勝劣汰、適者生存”的原理，激勵好的結構；通過模擬孟 德爾遺傳變

5、異理論，在迭代過程中保持已有的結構，同時尋 找更好的結構。 適應度：遺傳算法中使用適應度這個概念來度量群體中的每 個個體在優(yōu)化計算中可能達到或接近最優(yōu)解的程度。適應度 較高的個體遺傳到下一代的概率較大，而適應度較低的個體 遺傳到下一代的概率相對較小。度量個體適應度的函數稱為 適應度函數（Fitness Function）。,進化算法及其在數值計算中的應用,遺傳操作是遺傳算法的核心，它直接影響和決定遺傳算法的 優(yōu)化能力，是生物進化機理在遺傳算法中的最主要體現，遺 傳算法的遺傳操作包括選擇、變異和交叉。 選擇（selection）：選擇操作與生物的自然選擇機制相類似 ，體現了“適者生存，優(yōu)勝劣汰”

6、的生物進化機理。根據適應 度的大小來判斷個體的優(yōu)良，性狀優(yōu)良的個體有更大的機會 被選擇，產生后代。 比例選擇：個體被選中的概率與其適應度大小成正比。 假設群體規(guī)模為M，個體i的適應度為 ，則個體i被選中的 概率為,進化算法及其在數值計算中的應用,交叉（crossover）：交叉操作是指對兩個相互配對的染色體 按某種方式相互交換其部分基因，從而形成兩個新的個體。 交叉運算是遺傳算法區(qū)別于其它進化算法的重要特征，它在 遺傳算法中起著關鍵作用，是產生新個體的主要方法，決定 了遺傳算法的全局搜索能力。,進化算法及其在數值計算中的應用,單點交叉：,算術交叉：,變異（mutation）：變異運算是指將個體

7、染色體編碼串中的 某些基因座上的基因值用該基因座上的其它等位基因來替換 從而形成一個新的個體。變異運算只是產生新個體的輔助方 法，但也是一個必不可少的運算步驟，它決定了遺傳算法的 局部搜索能力。通過變異操作可以維持群體多樣性，防止出 現早熟現象，改善遺傳算法的局部搜索能力。 基本位變異：對個體編碼串中以變異概率隨機指定的某一位 或某幾位基因座上的基因值做變異運算。二進制中，把基因 值取反，即0變1，1變0。浮點數編碼中對選定的第i個個體 進行逆轉操作，如果浮點數變化范圍是 ，則,進化算法及其在數值計算中的應用,遺傳算法是一個迭代過程，它模擬生物在自然環(huán)境中的遺傳 和進化機理，反復將選擇算子、交

8、叉算子、變異算子作用于 群體，最終可得到問題的最優(yōu)解或近似最優(yōu)解。遺傳算法提 供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問 題的領域和種類。 對于一個需要進行優(yōu)化計算的實際應用問題，可按下述步驟 構造求解該問題的遺傳算法: 第一步：確定決策變量及其各種約束條件，即確定出個體的 表現型和問題的解空間； 第二步：建立優(yōu)化模型，即確定出目標函數的類型（求解目 標函數的最大值還是最小值）及其數學描述形式或量化方法,進化算法及其在數值計算中的應用,第三步：確定表示可行解的染色體編碼方法，即確定出個體 的基因型及遺傳算法的搜索空間； 第四步：確定解碼方法，即確定出由個體基因型到個體表現 型的對應關

9、系或轉換方法； 第五步：確定個體適應度的量化評價方法，即確定出由目標 函數值 到個體適應度值 的轉換規(guī)則； 第六步：設計遺傳算法，即確定出選擇、交叉、變異等遺傳 算子的具體操作方法； 第七步：確定遺傳算法的有關運行參數，包括個體數、進化 代數、變異概率、交叉概率等。,進化算法及其在數值計算中的應用,進化算法及其在數值計算中的應用,具體的運算步驟： 第一步：初始化，設置進化代數記數器 ，設置最大進 化代數T，隨機生成M個個體作為初始群體 ； 第二步：個體評價，計算群體 中每個個體的適應度 第三步：選擇運算； 第四步：交叉運算； 第五步：變異運算，群體 經過選擇、交叉、變異運算得到 下一代群體 ；

10、 第六步：終止條件判斷，若 ，則 ，轉到第二 步；若 ，則以進化過程中所得到的具有最大適應度的 個體作為最優(yōu)解輸出，終止計算。,進化算法及其在數值計算中的應用,進化算法及其在數值計算中的應用,群體智能算法（Swarm Intelligence Algorithm）的研究開始 于20世紀90年代，其基本思想是模擬自然界生物的群體行為 來構造隨機優(yōu)化算法。典型的有蟻群算法、粒子群算法、人 工魚群算法等。 粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法由 美國社會心理學家James Kennedy和電氣工程師Eberhart共 同提出?；舅枷胧鞘艿进B群和魚群群體覓

11、食行為研究結果 的啟發(fā)，與基于達爾文“適者生存，優(yōu)勝劣汰”進化思想不同， 粒子群優(yōu)化算法是通過個體間的協(xié)作來尋找最優(yōu)解的。作為 一種新的并行優(yōu)化進化算法，粒子群優(yōu)化算法具有很強的通 用性，可用于解決大量非線性、不可微和多峰值的復雜問題 優(yōu)化，并已廣泛應用于科學和工程領域。,進化算法及其在數值計算中的應用,自然界中各種生物體均具有一定的群體行為，人工生命的主 要研究領域之一就是探索自然界生物的群體行為，從而在計 算機上構建其群體模型。通常，群體行為可以由幾條簡單的 規(guī)則進行建模，但群體表現出的行為卻非常復雜。在對鳥群 行為進行仿真時，可以采用下面三條簡單規(guī)則： （1）飛離最近的個體，避免碰撞。

12、（2）飛向目標。 （3）飛向群體的中心。 群體內的每一個體的行為可采用上述規(guī)則描述，這是粒子群 算法的基本概念之一。,進化算法及其在數值計算中的應用,在研究人類的決策過程中，人們提出了個體學習和文化傳遞 的概念。一個人在決策過程中，會使用兩類重要的信息： 一是自身的經驗，二是其他人的經驗。也就是說，人們根據 自身的經驗和他人的經驗進行自己的決策。這是粒子群算法 的另一基本概念。 粒子群（PSO）算法與其它進化類算法相類似，也采用“群體” 與“進化”的概念，同樣也是依據個體（粒子）的適應度大小進 行操作。粒子群算法將每個個體看作是在N維搜索空間中的一 個沒有重量和體積的粒子，并在搜索空間中以一定

13、的速度飛行。 飛行速度由個體的飛行經驗和群體的飛行經驗進行動態(tài)調整。,進化算法及其在數值計算中的應用,假設 為粒子 的當前位置， 為粒子 的當前飛行速度， 為粒子 所飛 過的最好位置，也就是粒子 所經歷過的具有最好適應度的位 置，稱為個體最好位置。對于最小化問題，目標函數值越小 ，對應的適應度越好。為了討論方便，設 為最小化的目 標函數，則粒子 的當前最好位置由下式確定：,進化算法及其在數值計算中的應用,假設群體中的粒子數為 ，群體中所有的粒子所飛過的最好 位置為 ，稱為全局最好位置，則： 有了上面的定義，基本粒子群算法的進化方程可描述為： 式中，下標 表示粒子的第 維，即第 個決策變量； 表

14、示 第 個粒子； 表示代數； 表示加速常數，通常在0 2之間取值； 為兩個相互獨立均勻分 布的隨機函數。,進化算法及其在數值計算中的應用,從上述粒子進化方程可以看出， 調節(jié)粒子飛向自身最好位 置方向的步長， 調節(jié)粒子向全局最好位置飛行的步長。為 了減少在進化過程中，粒子離開搜索空間的可能性， 通常 限定于一定范圍內，即 。微粒的最大速度 取決于當前位置與最好位置間區(qū)域的分辨率。若 太高， 則微粒可能會飛過最好解；若 太小，則又將導致微粒移 動速度過慢而影響搜索效率；而且當微粒聚集到某個較好解 附近時，由于 過小而不利于微粒跳出局部最優(yōu)解。通常 設定為每個決策變量變化范圍的10%20%，即如果問

15、題的 搜索空間限定在內 ，則可設定,進化算法及其在數值計算中的應用,基本粒子群算法的初始化過程為： （1）設定群體規(guī)模M，即個體的數量； （2）對任意i、j，在 內服從均勻分布產生 ； （3）對任意i、j，在 內服從均勻分布產生 ； （4）對任意i，設定 。 算法的運算過程： （1）依照上述初始化過程，對粒子群的隨機位置和速度進 行初始設定； （2）計算每個粒子的適應度； （3）對于每個粒子，將其適應度與所飛過的最好位置 的 適應度進行比較，若較好，則將其作為當前的最好位置；,進化算法及其在數值計算中的應用,（4）對于每個粒子，將其適應度與全局所經歷的最好位置 的適應度進行比較，若較好，則將其

16、作為當前的全局最好位置 （5）根據公式對粒子的速度和位置進行進化計算； （6）如果沒有達到結束條件，即適應度不夠好或沒有達到預先設定的最大進化代數，則返回步驟（2）。,進化算法及其在數值計算中的應用,基本粒子群算法的社會行為分析： 速度進化方程分為三部分，第一部分為粒子原速度；第二部 分為認知部分，僅考慮了粒子自身的經驗，表示的是粒子自 身的思考。如果速度進化方程只包含認知部分，即 則算法性能變差。因為不同粒子之間缺乏信息交流，粒子間 沒有交互和社會信息共享，使得規(guī)模為N的群體等價于運行 了N個單個粒子，得到最優(yōu)解的概率非常小。,進化算法及其在數值計算中的應用,速度進化方程中第三部分為社會部分

17、，表示粒子間的社會信 息共享。如果方程只包含社會部分，則 粒子沒有認知能力，這樣粒子在相互作用下，有能力達到新 的搜索空間，雖然收斂速度比基本粒子群算法更快，但對于 復雜問題，容易陷入局部最優(yōu)點。,進化算法及其在數值計算中的應用,量子粒子群優(yōu)化（Quantum-behaved Particle Swarm Optimization，QPSO）算法：從量子力學的角度，通過 對粒子收斂行為的研究，基于粒子群優(yōu)化算法提出的一種新 的算法模型。在QPSO中，由于粒子滿足聚集態(tài)的性質完全 不同，使粒子在整個可行解空間中進行搜索尋求最優(yōu)解，因 而QPSO在搜索能力上遠遠優(yōu)于所有已開發(fā)的PSO，通過理 論分

18、析證明QPSO是一個全局收斂算法。同時，QPSO具有 參數少、易于編碼實現等特點。,進化算法及其在數值計算中的應用,QPSO中粒子的位置更新方程為： 式中t是算法的當前迭代次數，D為粒子的維數，N為粒子個 數， 是均勻分布在（0,1）上的隨機數，當 時，上式 前面取負號，否則取正號。 由下式確定： 式中 為在（0,1）上均勻分布的隨機數， 為第i個粒 子的當前最優(yōu)位置， 為當前群體的全局最優(yōu)位置。,進化算法及其在數值計算中的應用,稱為壓縮-擴張因子，是QPSO中的唯一參數，調節(jié)其值 能控制算法的收斂速度，一般采用線性減小的取值策略，即 的值隨迭代次數的增加而線性減小，方程如下： 式中 分別是迭

19、代初始值和終止值，一般取值為 或 效果較好。 稱為平均最優(yōu)位置，是所有粒子自 身最優(yōu)位置的中心點，由下式計算得到：,進化算法及其在數值計算中的應用,進化算法及其在數值計算中的應用,pNum=1000; %粒子數 pDim=4; %粒子維數 gen=300; %迭代次數 X1min=-100;X2min=-100;X3min=-100;X4min=-100; X1max=100;X2max=100;X3max=100;X4max=100; %變量范圍 %粒子初始化 am=rand(pNum,pDim); %隨機數輔助變量 Pc(:,1)=X1min+(X1max-X1min)*am(:,1);

20、Pc(:,2)=X2min+(X2max-X2min)*am(:,2); Pc(:,3)=X3min+(X3max-X3min)*am(:,3); Pc(:,4)=X4min+(X4max-X4min)*am(:,4);,進化算法及其在數值計算中的應用,%計算適應度 fitness=zeros(pNum,1); for kk=1:pNum a1=abs(5*Pc(kk,1)+Pc(kk,2)-Pc(kk,3)-2*Pc(kk,4)+2); a2=abs(2*Pc(kk,1)+8*Pc(kk,2)+Pc(kk,3)+3*Pc(kk,4)+6); a3=abs(Pc(kk,1)-2*Pc(kk,2

21、)-4*Pc(kk,3)-Pc(kk,4)-6); a4=abs(-Pc(kk,1)+3*Pc(kk,2)+2*Pc(kk,3)+7*Pc(kk,4)-12); fitness(kk,1)=(a1+a2+a3+a4);endpBestp=Pc; %粒子局部最優(yōu) pBestf=fitness; gBestf index=max(fitness); %全局最優(yōu)值(適應度) gBestp=Pc(index,:); %全局最優(yōu)值(個體) Best=zeros(gen+1,pDim+1); %記錄最優(yōu)值變化 Best(1,1)=gBestf; Best(1,2:pDim+1)=gBestp;,進化算法及

22、其在數值計算中的應用,for gm=1:gen gm mbest=mean(pBestp); %中值最優(yōu)位置 c=rand(pNum,1); pp=c c c c.*pBestp+(1-c)*gBestp; u=rand; beita=1.2-0.8*gm/gen; if u0.5 Pc=pp-beita*abs(ones(pNum,1)*mbest-Pc)*log(1/u); else Pc=pp+beita*abs(ones(pNum,1)*mbest-Pc)*log(1/u); end %適應度 for kk=1:pNum a1=abs(5*Pc(kk,1)+Pc(kk,2)-Pc(kk

23、,3)-2*Pc(kk,4)+2); a2=abs(2*Pc(kk,1)+8*Pc(kk,2)+Pc(kk,3)+3*Pc(kk,4)+6); a3=abs(Pc(kk,1)-2*Pc(kk,2)-4*Pc(kk,3)-Pc(kk,4)-6); a4=abs(-Pc(kk,1)+3*Pc(kk,2)+2*Pc(kk,3)+7*Pc(kk,4)-12); fitness(kk,1)=(a1+a2+a3+a4); end,進化算法及其在數值計算中的應用,for gn=1:pNum %限定范圍 if Pc(gn,1)X1max Pc(gn,1)=2*X1max-Pc(gn,1); end ,%選擇個體局部最優(yōu)和全局最優(yōu) if fitness(gn,1)pBestf(gn,1) pBestp(gn,:)=Pc(gn,:); pBestf(gn,1)=fitness(gn,1); end if fitness(gn,1)gBestf gBestf=fitness(gn,1); gBestp=P