【文章內(nèi)容簡(jiǎn)介】 ；評(píng)估；while不滿足終止條件dobegin重組獲得； 評(píng)估；從和中選擇；；endend圖41 遺傳算法的一般結(jié)構(gòu)通常初始化是隨機(jī)產(chǎn)生的。重組包括交叉和變異來獲得后代。實(shí)際上，遺傳算法中有兩類運(yùn)算：（1）遺傳運(yùn)算：交叉和變異；（2）進(jìn)化運(yùn)算：選擇。遺傳運(yùn)算模擬了基因在每一代中創(chuàng)造新后代的繁殖過程，進(jìn)化運(yùn)算則是種群逐代更新的過程。 遺傳算法的特點(diǎn)遺傳算法是一類可用于復(fù)雜系統(tǒng)優(yōu)化的具有魯棒性的搜索算法，與傳統(tǒng)的優(yōu)化算法相比，主要有以下特點(diǎn)[3]：（1）遺傳算法以決策變量的編碼作為運(yùn)算對(duì)象。傳統(tǒng)的優(yōu)化算法往往直接決策變量的實(shí)際植本身，而遺傳算法處理決策變量的某種編碼形式，使得我們可以借鑒生物學(xué)中的染色體和基因的概念，可以模仿自然界生物的遺傳和進(jìn)化機(jī)理，也使得我們能夠方便的應(yīng)用遺傳操作算子。（2）遺傳算法直接以適應(yīng)度作為搜索信息，無需導(dǎo)數(shù)等其它輔助信息。（3）遺傳算法使用多個(gè)點(diǎn)的搜索信息，具有隱含并行性。（4）遺傳算法使用概率搜索技術(shù)，而非確定性規(guī)則。 遺傳算法的應(yīng)用遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域，對(duì)問題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科。下面是遺傳算法的一些主要應(yīng)用領(lǐng)域[2][5]：（1）函數(shù)優(yōu)化。函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對(duì)遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例。（2）組合優(yōu)化。隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴(kuò)大，有時(shí)在目前的計(jì)算機(jī)上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。遺傳算法是解決這類問題的最佳工具之一。實(shí)踐證明，遺傳算法對(duì)于組合優(yōu)化中的NP完全問題非常有效。（3）生產(chǎn)調(diào)度問題。生產(chǎn)調(diào)度問題在許多情況下所建立起來的數(shù)學(xué)模型難以精確求解，即使經(jīng)過一些簡(jiǎn)化之后可以進(jìn)行求解，也會(huì)因簡(jiǎn)化得太多而使得求解結(jié)果與實(shí)際相差甚遠(yuǎn)?，F(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。（4）自動(dòng)控制。在自動(dòng)控制領(lǐng)域中有許多與優(yōu)化相關(guān)的問題需要求解，遺傳算法已在其中得到了初步的應(yīng)用，并顯示出了良好的效果。（5）機(jī)器人智能控制。機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于對(duì)人工自適應(yīng)系統(tǒng)的研究，所以機(jī)器人智能控制理所當(dāng)然地成為遺傳算法的一個(gè)重要應(yīng)用領(lǐng)域。（6）圖像處理。在圖像處理過程中，不可避免地會(huì)產(chǎn)生一些誤差，這些誤差會(huì)影響圖像處理的效果。如何使這些誤差最小是使計(jì)算機(jī)視覺達(dá)到實(shí)用化的重要要求。目前遺傳算法已在模式識(shí)別、圖像恢復(fù)、圖像邊緣特征提取等方面得到了應(yīng)用。（7）人工生命。人工生命與遺傳算法有著密切的關(guān)系，基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要基礎(chǔ)理論。遺傳算法已在進(jìn)化模型、學(xué)習(xí)模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力，并且必將得到更為深入的應(yīng)用和發(fā)展。（8）遺傳編程。Koza發(fā)展了遺傳編程的概念，他使用了以LISP語(yǔ)言所表示的編碼方法，基于對(duì)一種樹型結(jié)構(gòu)所進(jìn)行的遺傳操作來自動(dòng)生成計(jì)算機(jī)程序。（9）機(jī)器學(xué)習(xí)。基于遺傳算法的機(jī)器學(xué)習(xí)，在很多領(lǐng)域中都得到了應(yīng)用。 遺傳算法實(shí)現(xiàn)的關(guān)鍵技術(shù)編碼方法在遺傳算法的運(yùn)行過程中，它不對(duì)所求解問題的實(shí)際決策變量直接進(jìn)行操作，而是對(duì)表示可行解的個(gè)體編碼施加選擇、交叉、變異等遺傳運(yùn)算，通過這種遺傳操作來達(dá)到優(yōu)化的目的，這是遺傳算法的特點(diǎn)之一。在遺傳算法中把一個(gè)問題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法稱為編碼。常用的編碼方法有：（1）二進(jìn)制編碼：使用由二進(jìn)制符號(hào)0和1所組成的二值符號(hào)集{0，1}進(jìn)行編碼，它所構(gòu)成的個(gè)體基因型是一個(gè)二進(jìn)制編碼符號(hào)串。它是將可行解用固定長(zhǎng)度的二進(jìn)制串表示，串的長(zhǎng)度與問題所要求的求解精度有關(guān)。（2）浮點(diǎn)數(shù)編碼：個(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來表示，個(gè)體的編碼長(zhǎng)度等于其決策變量的個(gè)數(shù)。它所使用的是決策變量的真實(shí)值。（3）符號(hào)編碼：個(gè)體染色體編碼串中的基因值取自一個(gè)無數(shù)值含義、而只有代碼含義的符號(hào)集。這個(gè)符號(hào)集可以是一個(gè)字母表，如{A,B,C,D,…}；也可以是一個(gè)數(shù)字序號(hào)表，如{1，2，3，4，5，…}；還可以是一個(gè)代碼表，如{A1,A2,A3,A4,…}等等。適應(yīng)度函數(shù)適應(yīng)度是度量群體中各個(gè)個(gè)體在優(yōu)化計(jì)算中有可能達(dá)到或接近于或有助于找到最優(yōu)解的優(yōu)良程度[2]。遺傳算法的一個(gè)特點(diǎn)是它僅使用所求問題的目標(biāo)函數(shù)值就可得到下一步的有關(guān)搜索信息。而對(duì)目標(biāo)函數(shù)值的使用是通過評(píng)價(jià)個(gè)體的適應(yīng)度來體現(xiàn)的。評(píng)價(jià)個(gè)體適應(yīng)度的一般過程是：（1）對(duì)個(gè)體編碼串進(jìn)行解碼處理后，可得到個(gè)體的表現(xiàn)型。（2）由個(gè)體的表現(xiàn)型可計(jì)算出對(duì)應(yīng)個(gè)體的目標(biāo)函數(shù)值。（3）根據(jù)最優(yōu)化問題的類型，由目標(biāo)函數(shù)值按一定的轉(zhuǎn)換規(guī)則求出個(gè)體的適應(yīng)度。選擇算子遺傳算法使用遺傳算子（或稱為復(fù)制算子，Reproduction Operator）來對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度較高的個(gè)體被遺傳到下一代群體中的概率較大；適應(yīng)度較低的個(gè)體被遺傳到下一代群體中的概率較小。遺傳算法中的選擇操作就是確定如何從父代群體中按某種方法選取哪些個(gè)體遺傳到下一代群體中的一種遺傳運(yùn)算。遺傳操作建立在對(duì)個(gè)體的適應(yīng)度進(jìn)行評(píng)價(jià)的基礎(chǔ)之上。選擇操作的主要目的是為了避免基因缺失、提高全局收斂性和計(jì)算效率。常見選擇算子：（1）比例選擇：各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。設(shè)群體大小為pop_size，個(gè)體的適應(yīng)度為，則個(gè)體被選中的概率為： （k=1，2，…，pop_size） （）（2）隨機(jī)聯(lián)賽選擇：每次選取幾個(gè)個(gè)體之中適應(yīng)度最高的一個(gè)個(gè)體遺傳到下一代群體中。在聯(lián)賽選擇操作中，只有個(gè)體適應(yīng)度之間的大小比較運(yùn)算，而無個(gè)體適應(yīng)度之間的算術(shù)運(yùn)算，故它對(duì)個(gè)體適應(yīng)度是取正值還是負(fù)值無特別要求。（3）排序選擇：對(duì)群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行排序，基于這個(gè)排序來分配各個(gè)個(gè)體被選中的概率。交叉算子遺傳算法中的交叉運(yùn)算是指對(duì)兩個(gè)相互配對(duì)的染色體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。它是產(chǎn)生新個(gè)體的主要方法。遺傳算法中，在交叉運(yùn)算之前必須對(duì)群體中的個(gè)體進(jìn)行配對(duì)。常用的配對(duì)策略是隨機(jī)配對(duì)，即將群體中的M個(gè)個(gè)體以隨機(jī)的方式組成對(duì)配對(duì)個(gè)體組，交叉操作是在這些配對(duì)個(gè)體組中的兩個(gè)個(gè)體之間進(jìn)行的。常見交叉算子：（1）單點(diǎn)交叉（Onepoint Crossover）：在個(gè)體編碼串中只隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，實(shí)行交叉時(shí)，該點(diǎn)前或后的兩個(gè)個(gè)體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個(gè)新個(gè)體。（2）雙點(diǎn)交叉（Twopoint Crossover）：在個(gè)體編碼串中隨機(jī)設(shè)置了二個(gè)交叉點(diǎn)，進(jìn)行交叉時(shí)，將兩個(gè)交叉點(diǎn)之間的部分基因進(jìn)行互換。（3）均勻交叉（Uniform Crossover）：兩個(gè)配對(duì)個(gè)體的每一個(gè)基因座上的基因以相同的交叉概率進(jìn)行交換，從而形成兩個(gè)新的個(gè)體。變異算子遺傳算法中的變異運(yùn)算是指將個(gè)體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個(gè)新的個(gè)體。遺傳算法導(dǎo)入變異的目的有兩個(gè)：一是使遺傳算法具有局部的隨機(jī)搜索能力。二是使遺傳算法可維持群體多樣性，以防止出現(xiàn)未成熟收斂現(xiàn)象。變異算子的操作步驟：在群體中所有個(gè)體的碼串范圍內(nèi)隨機(jī)地確定基因座。以事先設(shè)定的變異概率Pm來對(duì)這些基因座的基因值進(jìn)行變異。常見變異算子：（1）基本位變異（Simple Mutation）是指對(duì)個(gè)體編碼串中以變異概率Pm隨機(jī)指定的某一位基因座上的基因值作變異運(yùn)算。（2）均勻變異（Uniform Mutation）是指分別用符合某一范圍內(nèi)均勻分布的隨機(jī)數(shù)，以某一較小的概率來替換個(gè)體編碼串中各個(gè)基因座上的原有基因值。（3）逆轉(zhuǎn)算子（Inversion Operator）在個(gè)體碼串中隨機(jī)挑選二個(gè)逆轉(zhuǎn)點(diǎn)，然后將兩個(gè)逆轉(zhuǎn)點(diǎn)間的基因值以逆轉(zhuǎn)概率Pi逆向排序。遺傳算法的運(yùn)行參數(shù)（1）編碼串長(zhǎng)度L。使用二進(jìn)制編碼時(shí)，L與問題所要求的求解精度有關(guān)；使用浮點(diǎn)數(shù)編碼時(shí)，L與決策變量的個(gè)數(shù)n相等；使用符號(hào)編碼是，L由問題的編碼方式確定。（2）群體大小pop_size。pop_size表示群體中所含個(gè)體的數(shù)量。當(dāng)pop_size取值較小時(shí)，可提高遺傳算法的運(yùn)算速度，卻降低了群體的多樣性，有可能會(huì)引起遺傳算法的早熟現(xiàn)象；當(dāng)pop_size取值較大時(shí)，又會(huì)使遺傳算法的運(yùn)行效率降低。（3）交叉概率Pc。交叉操作是遺傳算法中產(chǎn)生新個(gè)體的主要方法，所以Pc取值較大。但若過大的話，又會(huì)破壞群體中的優(yōu)良模式，對(duì)進(jìn)化運(yùn)算產(chǎn)生不利影響；若過小的話，產(chǎn)生新個(gè)體的速度又較慢。～。（4）變異概率Pm。Pm取值過大，雖然能夠產(chǎn)生較多的新個(gè)體，但也可能破壞掉很多較好的模式，使得遺傳算法的性能近似于隨機(jī)搜索算法的性能；若Pm過小，則變異操作產(chǎn)生新個(gè)體的能力和抑制早熟現(xiàn)象的能力就會(huì)較差。～。（5）終止代數(shù)T。T表示遺傳算法運(yùn)行到指定的進(jìn)化代數(shù)之后就停止運(yùn)行，并將當(dāng)前群體中的最佳個(gè)體作為所求問題的最優(yōu)解輸出。一般建議取值范圍是100～1000。5 求解非線性規(guī)劃問題的遺傳算法設(shè)計(jì)傳統(tǒng)的非線性規(guī)劃算法的缺陷是計(jì)算煩瑣且精度不高，穩(wěn)定性差，對(duì)函數(shù)初值和函數(shù)性態(tài)要求較高，且容易陷入局部最優(yōu)解。而遺傳算法是一種全局搜索算法，可以克服傳統(tǒng)的非線性規(guī)劃算法容易陷入局部最優(yōu)解的缺陷。因此，將遺傳算法應(yīng)用于非線性規(guī)劃，是改善收斂效果，提高最優(yōu)化質(zhì)量的有效途徑。本章就是介紹遺傳算法在非線性規(guī)劃中的具體應(yīng)用，設(shè)計(jì)并實(shí)現(xiàn)求解非線性規(guī)劃問題的遺傳算法。 實(shí)用遺傳算法設(shè)計(jì)編碼方法設(shè)計(jì)非線性規(guī)劃屬于最優(yōu)化設(shè)計(jì)的一種，屬于約束優(yōu)化問題，其最終目的是選擇一種方法，使目標(biāo)函數(shù)在滿足約束的條件下達(dá)到最優(yōu)。從非線性規(guī)劃的數(shù)學(xué)模型可知，我們最終要求解的是一組解，其滿足約束條件，并使目標(biāo)函數(shù)達(dá)到最小值(或最大值)。我們將這組解作為染色體，其中每個(gè)相當(dāng)于染色體上的基因，這也就是編碼對(duì)象。之后的選擇，交叉，變異就是對(duì)編碼后的染色體基因進(jìn)行運(yùn)算。我們最終所求的解是n維向量空間的某子集（定義域）上的一個(gè)實(shí)數(shù)，若采用傳統(tǒng)的二進(jìn)制編