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

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

2、線性函數(shù)來(lái)近似)，所以研究線性規(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)化過(guò)程和機(jī)制，以自組織和自適應(yīng)方式解決問(wèn)題的人工智能技術(shù)。進(jìn)化計(jì)算的具體實(shí)現(xiàn)方法和形式稱為進(jìn)化算法。進(jìn)化算法是一種具有“生成-測(cè)試”迭代過(guò)程的搜索算法。該算法體現(xiàn)了兩種策略：群體搜索和群體中個(gè)體之間的信息交換，為每個(gè)個(gè)體提供了一個(gè)優(yōu)化的機(jī)會(huì)，使整個(gè)群體能

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

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

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

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

7、變量及其各種約束，即確定問(wèn)題的個(gè)體表型和解空間；第二步：建立優(yōu)化模型，即確定目標(biāo)函數(shù)的類型(求解目標(biāo)函數(shù)的最大值或最小值)，其數(shù)學(xué)描述形式或量化方法，進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用；步驟3:確定代表可行解的染色體編碼方法，即確定個(gè)體基因型和遺傳算法的搜索空間；步驟4:確定解碼方法，即確定個(gè)體基因型到個(gè)體表達(dá)的對(duì)應(yīng)關(guān)系或轉(zhuǎn)換方法；第五步：確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法，即確定目標(biāo)函數(shù)值到個(gè)體適應(yīng)度值的轉(zhuǎn)換規(guī)則；第六步：設(shè)計(jì)遺傳算法，即確定遺傳算子的具體操作方法，如選擇、交叉和變異；第七步：確定遺傳算法的運(yùn)行參數(shù)，包括個(gè)體數(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個(gè)個(gè)體作為初始種群；步驟2:個(gè)體評(píng)估，計(jì)算群體中每個(gè)個(gè)體的適應(yīng)度步驟3:選擇操作；第四步：交叉操作；第五步：變異操作，對(duì)種群進(jìn)行選擇、雜交和變異，得到下一代種群；步驟6:終止條件判斷，如果是，轉(zhuǎn)到步驟2；如果是，則將進(jìn)化過(guò)程中獲得最大適應(yīng)度的個(gè)體作為最優(yōu)解輸出，并終止計(jì)算。進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用群體智能算法的研究始于20世紀(jì)90年代，其基本思想是模擬自然生物的群體行為來(lái)構(gòu)造隨機(jī)優(yōu)化粒子群優(yōu)化算法是由美國(guó)社會(huì)心理學(xué)家詹姆斯肯尼迪和電氣工程師埃伯哈特提出的。

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

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

11、化算法及其在數(shù)值計(jì)算中的應(yīng)用被假定為粒子的當(dāng)前位置、粒子的當(dāng)前飛行速度、粒子已經(jīng)飛行的最佳位置，即粒子以最佳適應(yīng)度經(jīng)歷的位置，這被稱為個(gè)體的最佳位置。對(duì)于最小化問(wèn)題，目標(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)表示第一個(gè)粒子；代表代數(shù)；所述加速度常數(shù)，通常在0和2之間；是兩個(gè)獨(dú)立且均勻分布的隨機(jī)函數(shù)。進(jìn)化算法及其在數(shù)值計(jì)算中的應(yīng)用、從上面的粒子進(jìn)化方程可以

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

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

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

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