【正文】 over和Greenberg建議的約束管理技術(shù)允許在搜索空間里的不可行域中進行搜索，這比將搜索限制在可行域內(nèi)的方法能更快地活的最優(yōu)解或獲得更好的最終解。對于約束嚴的問題，不可行解在種群中的比例很大。但是，該方法的遺傳搜索收到了可行域的限制。Michalewicz等指出這種方法通常比基于懲罰的遺傳算法更可靠。Michalewicz等則認為對有非線性約束的優(yōu)化問題，15%的替代率為最好。Liepins等采用永不替代法，即不讓修復過的染色體進入種群；而Nakano和Yamada采用了始終替代法。對于某些問題，修復過程甚至比原問題的求解更復雜。修復策略取決于是否存在一個可將不可行后代轉(zhuǎn)化為可行的修復程序。對于許多組合優(yōu)化問題，構(gòu)造修復程序相對比較容易。對于某些系統(tǒng)（特別是可行搜索空間非凸時），允許跨過不可行域修復往往更容易達到最優(yōu)解。然而，這是很嚴格的限制。這是遺傳算法中普遍的作法。適應度函數(shù)設計1）滿足約束由于對染色體作遺傳運算時通常獲得不可行的后代，因此運用遺傳算法解非線性規(guī)劃問題的核心問題是如何滿足約束的問題。所以我們直接采用實數(shù)編碼，即染色體基因串中基因座的值直接是每組解中各分量的實數(shù)值，不再對其進行其他任何形式的編碼。如果采用固定長度的二進制編碼，不僅會造成存儲空間的極大浪費，而且在進行交叉和變異等遺傳操作時，由于實際值不等長而很難確定交叉點和變異點，而且很容易產(chǎn)生無效解，降低了算法的效率；如果采用不定長二進制編碼，則在進行交叉和變異等遺傳操作時很難確定交叉點和變異點，而且容易產(chǎn)生無效解。之后的選擇，交叉，變異就是對編碼后的染色體基因進行運算。從非線性規(guī)劃的數(shù)學模型可知，我們最終要求解的是一組解，其滿足約束條件，并使目標函數(shù)達到最小值(或最大值)。本章就是介紹遺傳算法在非線性規(guī)劃中的具體應用，設計并實現(xiàn)求解非線性規(guī)劃問題的遺傳算法。而遺傳算法是一種全局搜索算法，可以克服傳統(tǒng)的非線性規(guī)劃算法容易陷入局部最優(yōu)解的缺陷。一般建議取值范圍是100～1000。（5）終止代數(shù)T。Pm取值過大，雖然能夠產(chǎn)生較多的新個體，但也可能破壞掉很多較好的模式，使得遺傳算法的性能近似于隨機搜索算法的性能；若Pm過小，則變異操作產(chǎn)生新個體的能力和抑制早熟現(xiàn)象的能力就會較差?！?。交叉操作是遺傳算法中產(chǎn)生新個體的主要方法，所以Pc取值較大。當pop_size取值較小時，可提高遺傳算法的運算速度，卻降低了群體的多樣性，有可能會引起遺傳算法的早熟現(xiàn)象；當pop_size取值較大時，又會使遺傳算法的運行效率降低。（2）群體大小pop_size。遺傳算法的運行參數(shù)（1）編碼串長度L。（2）均勻變異（Uniform Mutation）是指分別用符合某一范圍內(nèi)均勻分布的隨機數(shù)，以某一較小的概率來替換個體編碼串中各個基因座上的原有基因值。以事先設定的變異概率Pm來對這些基因座的基因值進行變異。二是使遺傳算法可維持群體多樣性，以防止出現(xiàn)未成熟收斂現(xiàn)象。變異算子遺傳算法中的變異運算是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個新的個體。（2）雙點交叉（Twopoint Crossover）：在個體編碼串中隨機設置了二個交叉點，進行交叉時，將兩個交叉點之間的部分基因進行互換。常用的配對策略是隨機配對，即將群體中的M個個體以隨機的方式組成對配對個體組，交叉操作是在這些配對個體組中的兩個個體之間進行的。它是產(chǎn)生新個體的主要方法。（3）排序選擇：對群體中的所有個體按其適應度大小進行排序，基于這個排序來分配各個個體被選中的概率。設群體大小為pop_size，個體的適應度為，則個體被選中的概率為： （k=1，2，…，pop_size） （）（2）隨機聯(lián)賽選擇：每次選取幾個個體之中適應度最高的一個個體遺傳到下一代群體中。選擇操作的主要目的是為了避免基因缺失、提高全局收斂性和計算效率。遺傳算法中的選擇操作就是確定如何從父代群體中按某種方法選取哪些個體遺傳到下一代群體中的一種遺傳運算。（3）根據(jù)最優(yōu)化問題的類型，由目標函數(shù)值按一定的轉(zhuǎn)換規(guī)則求出個體的適應度。評價個體適應度的一般過程是：（1）對個體編碼串進行解碼處理后，可得到個體的表現(xiàn)型。遺傳算法的一個特點是它僅使用所求問題的目標函數(shù)值就可得到下一步的有關(guān)搜索信息。這個符號集可以是一個字母表，如{A,B,C,D,…}；也可以是一個數(shù)字序號表，如{1，2，3，4，5，…}；還可以是一個代碼表，如{A1,A2,A3,A4,…}等等。它所使用的是決策變量的真實值。它是將可行解用固定長度的二進制串表示，串的長度與問題所要求的求解精度有關(guān)。在遺傳算法中把一個問題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法稱為編碼?；谶z傳算法的機器學習，在很多領(lǐng)域中都得到了應用。Koza發(fā)展了遺傳編程的概念，他使用了以LISP語言所表示的編碼方法，基于對一種樹型結(jié)構(gòu)所進行的遺傳操作來自動生成計算機程序。遺傳算法已在進化模型、學習模型、行為模型、自組織模型等方面顯示出了初步的應用能力，并且必將得到更為深入的應用和發(fā)展。（7）人工生命。如何使這些誤差最小是使計算機視覺達到實用化的重要要求。（6）圖像處理。（5）機器人智能控制。（4）自動控制。生產(chǎn)調(diào)度問題在許多情況下所建立起來的數(shù)學模型難以精確求解，即使經(jīng)過一些簡化之后可以進行求解，也會因簡化得太多而使得求解結(jié)果與實際相差甚遠。實踐證明，遺傳算法對于組合優(yōu)化中的NP完全問題非常有效。隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴大，有時在目前的計算機上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。函數(shù)優(yōu)化是遺傳算法的經(jīng)典應用領(lǐng)域，也是對遺傳算法進行性能評價的常用算例。 遺傳算法的應用遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域，對問題的種類有很強的魯棒性，所以廣泛應用于很多學科。（3）遺傳算法使用多個點的搜索信息，具有隱含并行性。傳統(tǒng)的優(yōu)化算法往往直接決策變量的實際植本身，而遺傳算法處理決策變量的某種編碼形式，使得我們可以借鑒生物學中的染色體和基因的概念，可以模仿自然界生物的遺傳和進化機理，也使得我們能夠方便的應用遺傳操作算子。遺傳運算模擬了基因在每一代中創(chuàng)造新后代的繁殖過程，進化運算則是種群逐代更新的過程。重組包括交叉和變異來獲得后代。這樣，經(jīng)過若干代之后，算法收斂于最好的染色體，它很可能就是問題的最優(yōu)解或者次優(yōu)解。新一代形成中，根據(jù)適值的大小選擇部分后代，淘汰部分之后，從而保持種群大小是常數(shù)。生成的下一代染色體稱為后代。這些染色體在后續(xù)迭代中不斷進化，稱為遺傳。種群中的每個個體是問題的一個解，稱為“染色體”。 遺傳算法的一般結(jié)構(gòu)遺傳算法是一種基于生物自然選擇與遺傳機理的隨機搜索算法。達爾文的自然選擇學說表明，遺傳和變異是決定生物進化的內(nèi)在因素。在生存斗爭中，具有有利變異（mutation）的個體容易存活下來，并且有更多的機會將有利的變異傳給后代；具有不利變異的個體就容易被淘汰，產(chǎn)生后代的機會也少得多。圖31 外點罰函數(shù)法程序流程圖4 遺傳算法 遺傳算法概述 遺傳算法的生物學基礎遺傳算法的生物學基礎是達爾文的自然選擇學說。（4）置，轉(zhuǎn)（2）。（2）假設已獲得迭代點，以為初始點，求解無約束問題 （）設其最優(yōu)點為。具體過程描述如下：（1）選定初始點，初始懲罰因子（可?。?。 外點罰函數(shù)法的程序設計為了能和求解非線性規(guī)劃問題的遺傳算法進行比較，我們同時實現(xiàn)最經(jīng)典的，也是得到最廣泛應用的傳統(tǒng)的非線性規(guī)劃算法——外點罰函數(shù)法，通過對二者的結(jié)果，比較二者性能的差別。另一方面，如果罰因子太小，這樣相對于目標函數(shù)罰函數(shù)項是可以忽略的，則大量的搜索時間將花費在非可行域。（3）罰函數(shù)法在實際計算中的缺點是罰因子的取值難于把握，太小起不到懲罰作用；太大則由于誤差的影響會導致錯誤。缺點有：（1）罰函數(shù)法對于有些問題只能求出局部最優(yōu)解，而不能求出全局最優(yōu)。 算法性能分析通過長期的理論研究和實驗結(jié)果，人們總結(jié)出懲罰函數(shù)的優(yōu)點有：（1）罰函數(shù)法是解決非線性規(guī)劃問題的一種經(jīng)典算法，這種算法簡單易行、熟練數(shù)度快，在很多實際問題的求解中得到了應用。如果求出的最優(yōu)解為，則判斷是否屬于。簡言之，外點罰函數(shù)法的思想是：當點時，設法加大不可行點處的函數(shù)值，使不可行點不能成為在中的最優(yōu)解。此時要求在中的最優(yōu)解，只能讓點回到內(nèi)才有可能，然而一旦點回到內(nèi)，即，此時就與問題（）有相同的最優(yōu)解。但是研究時，的最優(yōu)解不是我們所需要的。顯然，增廣目標函數(shù)是定義在上的一個無約束函數(shù)。對于問題（），構(gòu)造一函數(shù)為 （）其中， （）在（）中，又稱為懲罰函數(shù)， （） （）是一個逐漸增大的參數(shù)，稱為懲罰因子。 算法描述對于問題（），本文所述的基本策略是，根據(jù)約束特點（等式或不等式）構(gòu)造某種“罰函數(shù)”，然后把它加到目標函數(shù)中去，使得對約束最優(yōu)化問題的求解轉(zhuǎn)化為一系列無約束問題。外點罰函數(shù)法是從非可行解出發(fā)逐漸移動到可行區(qū)域的方法。利用罰函數(shù)法，可將非線性規(guī)劃問題的求解，轉(zhuǎn)化為求解一系列無約束極值問題，因而也稱這種方法為序列無約束最小化技術(shù)，簡記為SUMT(Sequential Unconstrained Minimization Technique)。對于靜態(tài)的最優(yōu)化問題，當目標函數(shù)或約束條件出現(xiàn)未知量的非線性函數(shù)，且不便于線性化，或勉強線性化后會招致較大誤差時，就可應用非線性規(guī)劃的方法去處理。 非線性規(guī)劃的應用在經(jīng)營管理、工程設計、科學研究、軍事指揮等方面普遍地存在著最優(yōu)化問題。④近似型算法：這類算法包括序貫線性規(guī)劃法和序貫二次規(guī)劃法。③可行方向法：這是一類通過逐次選取可行下降方向去逼近最優(yōu)點的迭代算法。它又分兩類，一類叫懲罰函數(shù)法，或稱外點法；另一類叫障礙函數(shù)法，或稱內(nèi)點法。常用的約束最優(yōu)化方法有4種[1]：①