【文章內(nèi)容簡(jiǎn)介】 XfMXF k ? （ ） 此時(shí) ),( kMXF 的最優(yōu)解就是問(wèn)題 （ ） 的最優(yōu)解；而當(dāng) DX? 時(shí)， ),( kMXF 的最優(yōu)解就不一定是問(wèn)題 （ ） 的最優(yōu)解。但是研究 DX? 時(shí)， ),( kMXF 的最優(yōu)解不是我們所需要的。為此規(guī)定，當(dāng) DX? 時(shí)， ),( kMXF 在 X 點(diǎn)處的函數(shù)值迅速變大，換而言之，可行域外的任一點(diǎn) X 處的函數(shù)值 ),( kMXF 都相當(dāng)大。此時(shí)要求 ),( kMXF 在 nR 中的最優(yōu)解，只能讓點(diǎn) X 回到 D 內(nèi)才 有 可能，然而一旦點(diǎn) X 回到 D 內(nèi)，即 DX? ，此時(shí) ),( kMXF就與問(wèn)題 （ ） 有相同的最優(yōu)解。 當(dāng) DX? 時(shí)， ),( kMXF 迅速變大的原因是通過(guò)懲罰因子 kM 來(lái)實(shí)現(xiàn)。簡(jiǎn)言之，外點(diǎn)罰函數(shù)法的思想是：當(dāng)點(diǎn) DX? 時(shí)，設(shè)法加大不可行點(diǎn)處的函數(shù)值，使不可行點(diǎn)不能成為 ),( kMXF 在 nR 中的最優(yōu)解。 在用外點(diǎn)罰函數(shù)法求解問(wèn)題 （ ） 時(shí)，首先構(gòu)造增廣目標(biāo)函數(shù) ),( kMXF ，然后按照無(wú)約束優(yōu)化方法求解。如果求出 ),( kMXF 的最優(yōu)解為 MX ，則判斷 MX 是否屬于 D 。如果 DXM? ，則 MX 是問(wèn)題 （ ） 的最優(yōu)解 ；如果 DXM? ，則 MX 不 是問(wèn)題 （ ） 的最優(yōu)解，此時(shí)說(shuō)明原來(lái)的懲罰因子給的太小了，需要加大懲罰因子，使得 kk MM ??1 ，然后再重新計(jì)算 ),( 1?kMXF 的最優(yōu)值。 算法性能分析 通過(guò)長(zhǎng)期的理論研究和實(shí)驗(yàn)結(jié)果，人們總結(jié)出懲罰函數(shù)的優(yōu)點(diǎn)有： （ 1） 罰函數(shù)法 是解決非線性規(guī)劃問(wèn)題的一種經(jīng)典算法，這種算法簡(jiǎn)單易行、熟練數(shù)度快，在很多實(shí)際問(wèn)題的求解中得到了應(yīng)用 。 （ 2） 計(jì)算效率高 ，穩(wěn)定性較好。 缺點(diǎn)有： （ 1） 罰函數(shù)法對(duì)于有些問(wèn)題只能求出局部最優(yōu)解，而不能求出全局最優(yōu)。 （ 2） 對(duì)函數(shù)初值和函數(shù)性態(tài)要求較高。 （ 3） 罰函數(shù)法在實(shí)際計(jì)算中的缺點(diǎn)是罰因子 M 的取值難于把握 ， 太小起不到懲罰作用 ； 太大則由于誤差的影響會(huì)導(dǎo)致錯(cuò)誤 。 在搜索過(guò)程開(kāi)始的時(shí)候 ， 一個(gè)較大的罰因子將會(huì)阻礙非可行域的搜索 。 另一方面，如果罰因子太小，這樣相對(duì)于目標(biāo)函數(shù)罰函數(shù)項(xiàng)是可以忽略的，則大量的搜索時(shí)間將花費(fèi)在非可行域。這對(duì)于進(jìn)化算法來(lái)說(shuō)非常致命的。 8 外點(diǎn) 罰函數(shù) 法的程序設(shè)計(jì) 為 了能和 求解非線性規(guī)劃問(wèn)題的遺傳算法 進(jìn)行比較，我們同時(shí)實(shí)現(xiàn)最經(jīng)典的，也是得到最廣泛應(yīng)用的 傳統(tǒng)的非線性規(guī)劃算法 —— 外點(diǎn)罰函數(shù) 法，通過(guò)對(duì)二者的結(jié)果，比較二者性能的差別。 程序步驟 對(duì)于問(wèn)題 （ ） ，構(gòu)造一函數(shù)為 )()(),( XMXfMXF kk ??? （ ） 其中，懲罰函數(shù) )(X? 按照式 （ ） 構(gòu)造，給定終止限 ? （ 可取 610??? ）。 具體過(guò) 程描述如下： （ 1） 選定初始點(diǎn) 0X ， 初始懲罰因子 01?M （ 可取 11?M ） 。懲罰因子放大系數(shù) 10?C ，置 1?k 。 （ 2） 假設(shè)已獲得迭代點(diǎn) 1?kX ，以 1?kX 為初始點(diǎn)，求解無(wú)約束問(wèn)題 ),(min kMXF （ ） 設(shè)其最優(yōu)點(diǎn)為 kX 。 （ 3） 若 ?? ?)(XMk ，則 kX 就是所要求問(wèn)題的最優(yōu)解，打印 ? ?)(, kk XfX ， 結(jié)束；否則轉(zhuǎn) （ 4）。 （ 4） 置 kk CMM ??1 ， 1??kk ，轉(zhuǎn) （ 2）。 程序流程圖 外點(diǎn)罰函數(shù)法 程序流程圖如 圖 31 所示。 9 圖 31 外點(diǎn)罰函數(shù)法 程序流程圖 10 4 遺傳 算法 遺傳算法概述 遺傳算法的生物學(xué)基礎(chǔ) 遺傳算法的生物學(xué)基礎(chǔ)是達(dá)爾文的自然選擇學(xué)說(shuō)。自然選擇學(xué)說(shuō)認(rèn)為，生物要生存下去，就必須進(jìn)行生存斗爭(zhēng)。在生存斗爭(zhēng)中，具有有利變異 （ mutation） 的個(gè)體容易存活下來(lái)，并且有更多的機(jī)會(huì)將有利的變異傳給后代；具有不利變異的個(gè)體就容易被淘汰，產(chǎn)生后代的機(jī)會(huì)也少得多。達(dá)爾文把這種在生存斗爭(zhēng)中適者生存，不適者淘汰的過(guò)程叫做自然選擇。達(dá)爾文的自然選擇學(xué)說(shuō)表明，遺傳和變異是決定生物進(jìn)化的內(nèi)在因素。遺傳能使生物的性狀不斷地傳遞給后代，因而保持了物種的特性，變異 能夠使生物的性狀發(fā)生改變，從而適應(yīng)新的環(huán)境而不斷地向前發(fā)展 [2]。 遺傳算法的一般結(jié)構(gòu) 遺傳算法 是一種基于生物自然選擇與遺傳機(jī)理的隨機(jī)搜索算法。和傳統(tǒng)算法不同，遺傳算法從一組隨機(jī)產(chǎn)生的初始解，稱(chēng)為“種群”，開(kāi)始搜索過(guò)程。種群中的每個(gè)個(gè)體是問(wèn)題的一個(gè)解，稱(chēng)為“染色體”。染色體是一串符號(hào)，比如一個(gè)二進(jìn)制字符串。這些染色體在后續(xù)迭代中不斷進(jìn)化，稱(chēng)為遺傳。在每一代中用“適值”來(lái)測(cè)量染色體的好壞。生成的下一代染色體稱(chēng)為后代。后代是由前一代染色體通過(guò)交叉或變異運(yùn)算形成的。新一代形成中，根據(jù)適值的大小選擇部分 后代，淘汰部分之后，從而保持種群大小是常數(shù)。適值高的染色體被選中的概率較高。這樣，經(jīng)過(guò)若干代之后，算法收斂于最好的染色體，它很可能就是問(wèn)題的最優(yōu)解或者次優(yōu)解。 設(shè) ??tP 和 ??tC 分別表示第 t 代的雙親和后代，遺傳算法的一般結(jié)構(gòu)可描述如下 [3]： 遺傳算法過(guò)程 ： begin 0?t ； 初始化 ??tP ； 評(píng)估 ??tP ； while 不 滿足終止條件 do begin 重組 ??tp 獲得 ??tC ； 評(píng)估 ??tC ； 11 從 ??tP 和 ??tC 中選擇 ? ?1?tP ； 1??tt ； end end 圖 41 遺傳算法的一般結(jié)構(gòu) 通常初始化是隨機(jī)產(chǎn)生的。重組包括交叉和變異來(lái)獲得后代。實(shí)際上，遺傳算法中有兩類(lèi)運(yùn)算： （ 1）遺傳運(yùn)算：交叉和變異； （ 2）進(jìn)化運(yùn)算：選擇。 遺傳運(yùn)算模擬了基因在每一代中創(chuàng)造新后代的繁殖過(guò)程，進(jìn)化運(yùn)算則是種群逐代更新的過(guò)程。 12 遺傳算法的特點(diǎn) 遺傳算法是一類(lèi)可用于復(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)度作為搜索信息，無(wú)需導(dǎo)數(shù)等其它輔助信息。 （ 3） 遺傳算法使用多個(gè)點(diǎn)的搜索信息，具有隱含并行性。 （ 4） 遺傳算法使用概率搜索技術(shù)，而非確定性規(guī)則。 遺傳算法的應(yīng)用 遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架，它不依賴(lài)于問(wèn)題的具體領(lǐng)域，對(duì)問(wèn)題的種類(lèi)有很強(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)化。隨著問(wèn)題規(guī)模的增大，組合優(yōu) 化問(wèn)題的搜索空間也急劇擴(kuò)大，有時(shí)在目前的計(jì)算機(jī)上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。遺傳算法是解決這類(lèi)問(wèn)題的最佳工具之一。實(shí)踐證明，遺傳算法對(duì)于組合優(yōu)化中的 NP 完全問(wèn)題非常有效。 （ 3）生產(chǎn)調(diào)度問(wèn)題。生產(chǎn)調(diào)度問(wèn)題在許多情況下所建立起來(lái)的數(shù)學(xué)模型難以精確求解，即使經(jīng)過(guò)一些簡(jiǎn)化之后可以進(jìn)行求解，也會(huì)因簡(jiǎn)化得太多而使得求解結(jié)果與實(shí)際相差甚遠(yuǎn)。現(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度問(wèn)題的有效工具，在單件生產(chǎn)車(chē)間調(diào)度、流水線生產(chǎn)車(chē)間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。 （ 4）自動(dòng)控制。在自動(dòng)控制領(lǐng) 域中有許多與優(yōu)化相關(guān)的問(wèn)題需要求解，遺傳算法已在其中得到了初步的應(yīng)用，并顯示出了良好的效果。 （ 5）機(jī)器人智能控制。機(jī)器人是一類(lèi)復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來(lái)自于對(duì)人工自適應(yīng)系統(tǒng)的研究，所以機(jī)器人智能控制理所當(dāng)然地成為遺傳算法的一個(gè)重要應(yīng)用領(lǐng)域。 （ 6）圖像處理。在圖像處理過(guò)程中，不可避免地會(huì)產(chǎn)生一些誤差，這些誤差會(huì)影響圖像處理的效果。如何使這些誤差最小是使計(jì)算機(jī)視覺(jué)達(dá)到實(shí)用化的重要要求。目前遺傳算法已在模式識(shí)別、圖像恢復(fù)、圖像邊緣特征提取等方面得到了應(yīng)用。 13 （ 7）人工生命。人工生命與遺 傳算法有著密切的關(guān)系，基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要基礎(chǔ)理論。遺傳算法已在進(jìn)化模型、學(xué)習(xí)模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力，并且必將得到更為深入的應(yīng)用和發(fā)展。 （ 8）遺傳編程。 Koza 發(fā)展了遺傳編程的概念，他使用了以 LISP 語(yǔ)言所表示的編碼方法，基于對(duì)一種樹(shù)型結(jié)構(gòu)所進(jìn)行的遺傳操作來(lái)自動(dòng)生成計(jì)算機(jī)程序。 （ 9）機(jī)器學(xué)習(xí)?；谶z傳算法的機(jī)器學(xué)習(xí)，在很多領(lǐng)域中都得到了應(yīng)用。 遺傳算法實(shí)現(xiàn)的關(guān)鍵技術(shù) 編碼方法 在遺傳算法的運(yùn)行過(guò)程中，它不對(duì)所求解問(wèn)題的實(shí)際決策變量直接 進(jìn)行操作，而是對(duì)表示可行解的個(gè)體編碼施加選擇、交叉、變異等遺傳運(yùn)算，通過(guò)這種遺傳操作來(lái)達(dá)到優(yōu)化的目的，這是遺傳算法的特點(diǎn)之一。在遺傳算法中把一個(gè)問(wèn)題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間 的轉(zhuǎn)換方法 稱(chēng)為編碼。 常用 的 編碼方法 有 ： （ 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)度與問(wèn)題所要求的求解精度有關(guān)。 （ 2） 浮點(diǎn)數(shù)編碼：個(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來(lái)表示，個(gè)體的編碼長(zhǎng)度等于其決策變量的個(gè)數(shù)。它所使用的是決策變量的真實(shí)值。 （ 3） 符號(hào)編碼：個(gè)體染色體編碼串中的基因值取自一個(gè)無(wú)數(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)是它僅使用所求問(wèn)題的目標(biāo)函數(shù)值就可得到下一步的有關(guān)搜索信息。而對(duì)目標(biāo)函數(shù) 值的使用是通過(guò)評(píng)價(jià)個(gè)體的適應(yīng)度來(lái)體現(xiàn)的。評(píng)價(jià)個(gè)體適應(yīng)度的一般過(guò)程是： （ 1） 對(duì)個(gè)體編碼串進(jìn)行解碼處理后，可得到個(gè)體的表現(xiàn)型。 （ 2）由個(gè)體的表現(xiàn)型可計(jì)算出對(duì)應(yīng)個(gè)體的目標(biāo)函數(shù)值。 （ 3）根據(jù)最優(yōu)化問(wèn)題的類(lèi)型，由目標(biāo)函數(shù)值按一定的轉(zhuǎn)換規(guī)則求出個(gè)體的適應(yīng)度。 選擇算子 遺傳算法使用遺傳算子（或稱(chēng)為復(fù)制算子， Reproduction Operator）來(lái)對(duì)群體中的個(gè) 14 體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度較高的個(gè)體被遺傳到下一代群體中的概率較大；適應(yīng)度較低的個(gè)體被遺傳到下一代群體中的概率較小。遺傳算法中的選擇操作就是確定如何 從父代群體中按某種方法選取哪些個(gè)體遺傳到下一代群體中的一種遺傳運(yùn)算。遺傳操作建立在對(duì)個(gè)體的適應(yīng)度進(jìn)行評(píng)價(jià)的基礎(chǔ)之上。選擇操作的主要目的是為了避免基因缺失、提高全局收斂性和計(jì)算效率。 常見(jiàn)選擇算子： （ 1）比例選擇：各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。 設(shè)群體大小為 pop_size，個(gè)體 kv 的適應(yīng)度為 ? ?kveval ，則個(gè)體 kv 被選中的概率 kp 為： ? ?Fvevalp kk ? （ k=1， 2， … ， pop_size） （ ） （ 2）隨機(jī)聯(lián)賽選擇：每次選取幾個(gè)個(gè)體之中適應(yīng)度最高的一個(gè)個(gè)體遺傳到下一代群體中。在聯(lián)賽選擇操作中，只有個(gè)體適應(yīng)度之間的大小比較運(yùn)算，而無(wú)個(gè)體適應(yīng)度之間的算術(shù)運(yùn)算，故它對(duì)個(gè)體適應(yīng)度是取正值還是負(fù)值無(wú)特別要求。 （ 3）排序選擇：對(duì)群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行排序，基于這個(gè)排序來(lái)分配各個(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ī)的方式組成 ? ?2/M 對(duì)配對(duì)個(gè)體組，交叉操作是在這些配對(duì)個(gè)體組中的兩個(gè)個(gè)體之間進(jìn)行的。 常見(jià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è)體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來(lái)替換，從而形成一個(gè)新的個(gè)體。遺傳算法導(dǎo)入變異的目的有兩個(gè)：一是使遺傳算法具有局部的隨機(jī)搜索能力。二是使遺傳算法可維持群體多樣性，以防止出現(xiàn)未成熟收斂現(xiàn)象。 15 變異算子的操作步驟： 在群體中所有個(gè)體的碼串范圍內(nèi)隨機(jī)地確定基因座。 以事先設(shè)定的變異概率