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

1、進(jìn)化算法及其在數(shù)值計(jì)算、優(yōu)化問題中的應(yīng)用：在一定的約束條件下，找到一組參數(shù)值，這樣即使系統(tǒng)的某些性能指標(biāo)達(dá)到最大或最小，一些最優(yōu)性措施也能得到滿足。優(yōu)化問題的應(yīng)用涉及工業(yè)技術(shù)、社會、經(jīng)濟(jì)和管理等多個領(lǐng)域，具有重要意義。優(yōu)化問題的一般形式是：其中，它被稱為目標(biāo)函數(shù)和約束函數(shù)。數(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ī)劃是尋求并使世界上的最大值(或最小值)，它被稱為最佳點(diǎn)(最優(yōu)解)和最優(yōu)值。受生物進(jìn)化和遺傳學(xué)理論的啟發(fā)，進(jìn)化計(jì)算是一種模擬生物進(jìn)化過程和機(jī)制，以自組織和自適應(yīng)方式解決問題的人工智能技術(shù)。進(jìn)化計(jì)算的具體實(shí)現(xiàn)方法和形式稱為進(jìn)化算法。進(jìn)化算法是一種具有“生成-測試”迭代過程的搜索算法。該算法體現(xiàn)了兩種策略：群體搜索和群體中個體之間的信息交換，為每個個體提供了一個優(yōu)化的機(jī)會，使整個群體能

3、夠在優(yōu)勝劣汰的選擇機(jī)制下保證進(jìn)化趨勢。進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用。進(jìn)化算法以代碼的形式表達(dá)復(fù)雜的結(jié)構(gòu)，并將每個代碼稱為一個個體。該算法維護(hù)一定數(shù)量的代碼集，稱為種群或種群。通過對種群中的個體進(jìn)行相應(yīng)的運(yùn)算，最終得到一些性能指標(biāo)較高的個體。進(jìn)化算法的研究始于20世紀(jì)60年代。霍蘭德提出了用于機(jī)器學(xué)習(xí)問題的遺傳算法，福格爾提出了用于優(yōu)化模型系統(tǒng)的進(jìn)化規(guī)劃，施韋費(fèi)爾提出了用于數(shù)值優(yōu)化問題的進(jìn)化策略。進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用。遺傳算法是宏觀意義上的仿生算法，其模仿機(jī)制是生命和智能的生成和進(jìn)化過程。遺傳算法通過模擬達(dá)爾文的“適者生存”原則來刺激良好的結(jié)構(gòu)；通過模擬孟德爾的遺傳變異理論，我們可以

4、在迭代過程中保持現(xiàn)有的結(jié)構(gòu)，同時(shí)找到更好的結(jié)構(gòu)。適應(yīng)度：適應(yīng)度的概念在遺傳算法中被用來衡量種群中的每個個體在優(yōu)化計(jì)算中達(dá)到或接近最優(yōu)解的程度。體能較高的個體更有可能遺傳給下一代，而體能較低的個體不太可能遺傳給下一代。測量個體健康的函數(shù)稱為健康函數(shù)。進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用。遺傳操作是遺傳算法的核心，它直接影響和決定著遺傳算法的優(yōu)化能力，是生物進(jìn)化機(jī)制在遺傳算法中的主要體現(xiàn)。遺傳算法的遺傳操作包括選擇、變異和交叉。選擇：選擇操作類似于生物的自然選擇機(jī)制，體現(xiàn)了“適者生存，適者生存”的生物進(jìn)化機(jī)制。根據(jù)適合度的大小，具有良好品質(zhì)的個體有更大的機(jī)會被選擇并產(chǎn)生后代。比例選擇：一個人被選中的概率

5、與他的健康狀況成正比。假設(shè)種群規(guī)模為m，個體I的適應(yīng)度為0，個體I被選擇的概率為：進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用、交叉：交叉操作是指在兩對染色體之間以某種方式交換某些基因，從而形成兩個新的個體。交叉操作是遺傳算法區(qū)別于其他進(jìn)化算法的一個重要特征。它在遺傳算法中起著關(guān)鍵作用，是產(chǎn)生新個體的主要方法，決定了遺傳算法的全局搜索能力。進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用，單點(diǎn)雜交，算術(shù)雜交，變異，變異操作是指用一個個體染色體編碼串中某些位點(diǎn)上的基因值替換該位點(diǎn)上的其他等位基因，形成一個新的個體。變異操作只是產(chǎn)生新個體的一種輔助方法，但也是一個必不可少的操作步驟，它決定了遺傳算法的局部搜索能力。通過變異操作，

6、可以保持種群多樣性，防止早熟現(xiàn)象，提高遺傳算法的局部搜索能力?；疚恢米儺悾簩蝹€編碼串中由變異概率隨機(jī)指定的一個或幾個基因座的基因值進(jìn)行變異操作。在二進(jìn)制系統(tǒng)中，基因值被反轉(zhuǎn)，即0變成1，1變成0。在浮點(diǎn)編碼中，第一個被選擇的個體是反向的。如果浮點(diǎn)數(shù)的變化范圍是，那么進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用，遺傳算法是一個迭代過程，它模擬自然界中生物的遺傳和進(jìn)化機(jī)制，并對種群反復(fù)應(yīng)用選擇算子、交叉算子和變異算子，最終獲得問題的最優(yōu)解或近似最優(yōu)解。遺傳算法為解決復(fù)雜系統(tǒng)優(yōu)化問題提供了一個通用框架，它不依賴于問題的領(lǐng)域和類型。對于需要優(yōu)化的實(shí)際應(yīng)用問題，求解該問題的遺傳算法：可以構(gòu)造如下：第一步是確定決策

7、變量及其各種約束，即確定問題的個體表型和解空間；第二步：建立優(yōu)化模型，即確定目標(biāo)函數(shù)的類型(求解目標(biāo)函數(shù)的最大值或最小值)，其數(shù)學(xué)描述形式或量化方法，進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用；步驟3:確定代表可行解的染色體編碼方法，即確定個體基因型和遺傳算法的搜索空間；步驟4:確定解碼方法，即確定個體基因型到個體表達(dá)的對應(yīng)關(guān)系或轉(zhuǎn)換方法；第五步：確定個體適應(yīng)度的量化評價(jià)方法，即確定目標(biāo)函數(shù)值到個體適應(yīng)度值的轉(zhuǎn)換規(guī)則；第六步：設(shè)計(jì)遺傳算法，即確定遺傳算子的具體操作方法，如選擇、交叉和變異；第七步：確定遺傳算法的運(yùn)行參數(shù)，包括個體數(shù)量、進(jìn)化代數(shù)、變異概率、交叉概率等。進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用，進(jìn)化算法

8、及其在數(shù)值計(jì)算中的應(yīng)用，具體操作步驟：步驟1:初始化，設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器，設(shè)置最大漸進(jìn)代數(shù)t，隨機(jī)生成m個個體作為初始種群；步驟2:個體評估，計(jì)算群體中每個個體的適應(yīng)度步驟3:選擇操作；第四步：交叉操作；第五步：變異操作，對種群進(jìn)行選擇、雜交和變異，得到下一代種群；步驟6:終止條件判斷，如果是，轉(zhuǎn)到步驟2；如果是，則將進(jìn)化過程中獲得最大適應(yīng)度的個體作為最優(yōu)解輸出，并終止計(jì)算。進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用群體智能算法的研究始于20世紀(jì)90年代，其基本思想是模擬自然生物的群體行為來構(gòu)造隨機(jī)優(yōu)化粒子群優(yōu)化算法是由美國社會心理學(xué)家詹姆斯肯尼迪和電氣工程師埃伯哈特提出的。

9、這個基本想法是受鳥類和魚類群體覓食行為的研究結(jié)果的啟發(fā)。不同于達(dá)爾文的“適者生存，適者生存”的進(jìn)化思想，粒子群優(yōu)化算法通過個體間的合作來尋找最優(yōu)解。粒子群優(yōu)化算法作為一種新的并行優(yōu)化進(jìn)化算法，具有很強(qiáng)的普適性，能夠解決大量非線性、不可微和多峰值的復(fù)雜問題，在科學(xué)和工程領(lǐng)域得到了廣泛的應(yīng)用。進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用，自然界中的各種生物都有一定的群體行為，而人工生命的主要研究領(lǐng)域之一就是探索自然生物的群體行為，從而在計(jì)算機(jī)上建立它們的群體模型。通常，群體行為可以用幾個簡單的規(guī)則來建模，但是群體行為是非常復(fù)雜的。當(dāng)模擬鳥類的行為時(shí)，可以采用以下三個簡單的規(guī)則：(1)遠(yuǎn)離最近的個體以避免碰撞。(

10、2)飛向目標(biāo)。(3)飛到小組的中心。種群中每個個體的行為都可以用上述規(guī)則來描述，這是粒子群優(yōu)化的基本概念之一。進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用。在研究人類決策的過程中，人們提出了個體學(xué)習(xí)和文化傳播的概念。一個人在決策過程中會用到兩種重要的信息：一種是自己的經(jīng)驗(yàn)，另一種是自己的經(jīng)驗(yàn)。也就是說，人們根據(jù)自己和他人的經(jīng)驗(yàn)做出自己的決定。這是粒子群優(yōu)化的另一個基本概念。粒子群優(yōu)化算法類似于其他進(jìn)化算法，也采用了“群體”和“進(jìn)化”的概念，并根據(jù)個體(粒子)的適應(yīng)度進(jìn)行操作。粒子群優(yōu)化算法將每個個體視為一個沒有重量和體積的粒子，并在搜索空間中以一定的速度飛行。飛行速度由個人飛行經(jīng)驗(yàn)和集體飛行經(jīng)驗(yàn)動態(tài)調(diào)整。進(jìn)

11、化算法及其在數(shù)值計(jì)算中的應(yīng)用被假定為粒子的當(dāng)前位置、粒子的當(dāng)前飛行速度、粒子已經(jīng)飛行的最佳位置，即粒子以最佳適應(yīng)度經(jīng)歷的位置，這被稱為個體的最佳位置。對于最小化問題，目標(biāo)函數(shù)值越小，相應(yīng)的適應(yīng)度越好。為了便于討論，將其設(shè)為最小化目標(biāo)函數(shù)，那么粒子的當(dāng)前最佳位置由以下公式確定：進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用，假設(shè)種群中粒子的數(shù)量為0，并且種群中所有粒子飛行的最佳位置被稱為全局最佳位置，那么，根據(jù)上述定義，基本粒子群優(yōu)化的進(jìn)化方程可以描述為：其中，下標(biāo)表示第一個粒子；代表代數(shù)；所述加速度常數(shù)，通常在0和2之間；是兩個獨(dú)立且均勻分布的隨機(jī)函數(shù)。進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用、從上面的粒子進(jìn)化方程可以

12、看出，粒子飛向其最佳位置方向的步長和粒子飛向全局最佳位置的步長是可以調(diào)整的。為了減少粒子在進(jìn)化過程中離開搜索空間的可能性，它通常被限制在一定的范圍內(nèi)，即。粒子的最大速度取決于當(dāng)前位置和最佳位置之間區(qū)域的分辨率。如果太高，粒子可能會飛過最佳解決方案；如果太小，會導(dǎo)致粒子移動速度慢，影響搜索效率；此外，當(dāng)粒子聚集在更好的解附近時(shí)，它們太小而不能跳出局部最優(yōu)解。通常將其設(shè)置為每個決策變量變化范圍的10%，即如果問題的搜索空間有限，可以設(shè)置進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用?；玖Ｗ尤簝?yōu)化算法的初始化過程如下：(1)設(shè)定種群規(guī)模m，即個體數(shù)；(2)對于任何I，J，它服從均勻分布；(3)對于任何I，J，它服

13、從均勻分布；(4)對于任何I，設(shè)置。該算法的操作過程是：(1)根據(jù)上述初始化過程，初步設(shè)定粒子群的隨機(jī)位置和速度；(2)計(jì)算每個粒子的適應(yīng)度；(3)對于每個粒子，將它的適合度與它飛過的最佳位置的適合度進(jìn)行比較，如果它更好，則將其作為當(dāng)前的最佳位置；進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用、(4)對于每個粒子，將其適應(yīng)度與全局經(jīng)驗(yàn)最佳位置的適應(yīng)度進(jìn)行比較，如果比較好，將其作為當(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)用基本粒子群優(yōu)化：速度進(jìn)化方程分為三個

14、部分，第一部分是粒子的原始速度；第二部分分為認(rèn)知部分，只考慮粒子本身的經(jīng)驗(yàn)，表達(dá)粒子本身的思想。如果速度演化方程只包含認(rèn)知部分，算法的性能會變差。由于不同粒子之間缺乏信息交流，粒子之間沒有相互作用和社會信息共享，使得具有N個尺度的群體相當(dāng)于運(yùn)行N個單粒子，獲得最優(yōu)解的概率很小。進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用速度進(jìn)化方程的第三部分是社會部分，它代表了粒子間的社會信息共享。如果方程只包含社會部分，粒子就沒有認(rèn)知能力，因此粒子可以在相互作用下到達(dá)一個新的搜索空間。雖然收斂速度比基本粒子群優(yōu)化算法快，但對于復(fù)雜問題，容易陷入局部最優(yōu)。進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用量子粒子群優(yōu)化算法：通過對粒子收斂行為

15、的研究，從量子力學(xué)的角度提出了一種基于粒子群優(yōu)化算法的新算法模型。在量子粒子群算法中，由于滿足聚集態(tài)的粒子性質(zhì)完全不同，粒子在整個可行解空間中搜索尋找最優(yōu)解，量子粒子群算法在搜索能力上遠(yuǎn)遠(yuǎn)優(yōu)于所有已有的粒子群算法。理論分析證明，量子粒子群算法是一種全局收斂算法。同時(shí)，量子粒子群算法具有參數(shù)少、易于編碼的特點(diǎn)。進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用，量子粒子群算法中粒子的位置更新方程如下：其中t為算法當(dāng)前迭代次數(shù)，d為粒子維數(shù)，n為粒子數(shù)，是均勻分布在(0，1)上的隨機(jī)數(shù)。如果是這樣，在上面的公式前取一個負(fù)號，否則取一個正號。它由以下公式確定：其中隨機(jī)數(shù)均勻分布在(0，1)上，這是ith粒子的當(dāng)前最優(yōu)位置和當(dāng)前種群的全局最優(yōu)位置。進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用，稱為壓縮-膨脹因子，是量子粒子群算法中唯一的參數(shù)。調(diào)整其值可以控制算法的收斂速度。一般來說，算法的值是線性減小的，也就是說，它的值隨著迭代次數(shù)的增加而線性減小。方程如下：迭代的初值和終值分別為，數(shù)值一般為或效果較好。平均最優(yōu)位置是所有粒子的最優(yōu)位置的中心點(diǎn)，由以下公式計(jì)算：進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用，進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用，pNum=1000%粒