進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用.ppt

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、代初始值和終止值，一般取值為 或 效果較好。 稱為平均最優(yōu)位置，是所有粒子自 身最優(yōu)位置的中心點(diǎn)，由下式計(jì)算得到：,進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用,進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用,pNum=1000; %粒子數(shù) pDim=4; %粒子維數(shù) gen=300; %迭代次數(shù) X1min=-100;X2min=-100;X3min=-100;X4min=-100; X1max=100;X2max=100;X3max=100;X4max=100; %變量范圍 %粒子初始化 am=rand(pNum,pDim); %隨機(jī)數(shù)輔助變量 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);,進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用,%計(jì)算適應(yīng)度 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)值(適應(yīng)度) gBestp=Pc(index,:); %全局最優(yōu)值(個體) Best=zeros(gen+1,pDim+1); %記錄最優(yōu)值變化 Best(1,1)=gBestf; Best(1,2:pDim+1)=gBestp;,進(jìn)化算法及

22、其在數(shù)值計(jì)算中的應(yīng)用,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 %適應(yīng)度 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,進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用,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