【正文】 ....... 16 實(shí)用遺傳算法設(shè)計(jì) ............................................................................................. 16 求解非線性規(guī)劃問(wèn)題的遺傳算法程序設(shè)計(jì) ..................................................... 21 算法過(guò)程描述 .......................................................................................... 21 遺傳算法程序流程圖 .............................................................................. 22 遺傳算法中所設(shè)計(jì)的輔助算法的設(shè)計(jì) .................................................. 23 6 算法的結(jié)果分析 ............................................................................................................ 24 概述 ..................................................................................................................... 24 結(jié)果比較 ............................................................................................................. 24 7 總結(jié) ................................................................................................................................ 28 致謝 .................................................................................................................................... 29 參考文獻(xiàn) ............................................................................................................................ 30 1 1 概 論 背景介紹 非線性規(guī)劃簡(jiǎn)介 具有非線性約束條件或目標(biāo)函數(shù)的 數(shù)學(xué)規(guī)劃 ，稱為非線性規(guī)劃。 遺傳算法 是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過(guò)程的計(jì)算模型 。算法引進(jìn)懲罰函數(shù)的概念，構(gòu) 造帶有懲罰項(xiàng)的適應(yīng)度函數(shù)；通過(guò)實(shí)數(shù)編碼，轉(zhuǎn)輪法選擇，雙點(diǎn)交叉，均勻變異，形成了求解非線性規(guī)劃問(wèn)題的遺傳算法。在 50 年代還得出了可分離規(guī)劃和二次規(guī)劃的 n 種解法 ， 它們大都是以 .丹齊克提出的解線性規(guī)劃的單純形法為基礎(chǔ)的。它的主要特點(diǎn)是簡(jiǎn)單、通用、魯棒性強(qiáng)，對(duì)目標(biāo)函數(shù)既不要求連續(xù)，也不要求可 導(dǎo) ，適用于并行分布處理，應(yīng)用范圍廣。 3 2 非線性規(guī)劃 非線性規(guī)劃的概念 具有非線性約束條件或目標(biāo)函數(shù)的 數(shù)學(xué)規(guī)劃 ， 稱為非線性規(guī)劃 。 上述模型可簡(jiǎn)記為： ? ?xfmin （ ） ? ?? ???? ?? ?? pjxh mixgts ,...,1,0 ,...,1,0.. （ ） 其中 ? ?nxx ,...,x 1? 屬于定義域 D ，符號(hào) min 表示“求最小值”，符號(hào) “受約束于”。常用的一維最優(yōu)化方法有黃金分割法、切線法和插值法 [1]。其基本思想是用多項(xiàng)式（通常用二次或三次多項(xiàng)式）去擬合目標(biāo)函數(shù)。這些迭代算法的基本思想是：在一個(gè)近似點(diǎn)處選定一個(gè)有利搜索方向 ， 沿這個(gè)方向進(jìn)行一維尋查 ， 得出新的近似點(diǎn)。其中達(dá)維登 弗萊徹 鮑威爾變尺度法，簡(jiǎn)稱DFP 法，是最常用的方法。如佐坦迪克法、弗蘭克－沃爾夫法、投影梯度法和簡(jiǎn)約梯度法都屬于此類算法。 主要有兩種形式，一種叫 外 點(diǎn) 罰函數(shù)法 ，另一種叫 內(nèi) 點(diǎn) 罰函數(shù)法 。由增廣目標(biāo)函數(shù)),( kMXF 的構(gòu)造知當(dāng) DX? 時(shí) )(),( XfMXF k ? （ ） 此時(shí) ),( kMXF 的最優(yōu)解就是問(wèn)題 （ ） 的最優(yōu)解；而當(dāng) DX? 時(shí)， ),( kMXF 的最優(yōu)解就不一定是問(wèn)題 （ ） 的最優(yōu)解。如果 DXM? ，則 MX 是問(wèn)題 （ ） 的最優(yōu)解 ；如果 DXM? ，則 MX 不 是問(wèn)題 （ ） 的最優(yōu)解，此時(shí)說(shuō)明原來(lái)的懲罰因子給的太小了，需要加大懲罰因子，使得 kk MM ??1 ，然后再重新計(jì)算 ),( 1?kMXF 的最優(yōu)值。這對(duì)于進(jìn)化算法來(lái)說(shuō)非常致命的。 程序流程圖 外點(diǎn)罰函數(shù)法 程序流程圖如 圖 31 所示。和傳統(tǒng)算法不同，遺傳算法從一組隨機(jī)產(chǎn)生的初始解，稱為“種群”，開(kāi)始搜索過(guò)程。適值高的染色體被選中的概率較高。 （ 2） 遺傳算法直接以適應(yīng)度作為搜索信息，無(wú)需導(dǎo)數(shù)等其它輔助信息。遺傳算法是解決這類問(wèn)題的最佳工具之一。機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來(lái)自于對(duì)人工自適應(yīng)系統(tǒng)的研究，所以機(jī)器人智能控制理所當(dāng)然地成為遺傳算法的一個(gè)重要應(yīng)用領(lǐng)域。 （ 8）遺傳編程。 （ 2） 浮點(diǎn)數(shù)編碼：個(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來(lái)表示，個(gè)體的編碼長(zhǎng)度等于其決策變量的個(gè)數(shù)。 （ 2）由個(gè)體的表現(xiàn)型可計(jì)算出對(duì)應(yīng)個(gè)體的目標(biāo)函數(shù)值。在聯(lián)賽選擇操作中，只有個(gè)體適應(yīng)度之間的大小比較運(yùn)算，而無(wú)個(gè)體適應(yīng)度之間的算術(shù)運(yùn)算，故它對(duì)個(gè)體適應(yīng)度是取正值還是負(fù)值無(wú)特別要求。 （ 3）均勻交叉（ Uniform Crossover）：兩個(gè)配對(duì)個(gè)體的每一個(gè)基因座上的基因以相同的交叉概率進(jìn)行交換，從而形成兩個(gè)新的個(gè)體。 （ 3）逆轉(zhuǎn)算子（ Inversion Operator）在個(gè)體碼串中隨機(jī)挑選二個(gè)逆轉(zhuǎn)點(diǎn)，然后將兩個(gè)逆轉(zhuǎn)點(diǎn)間的基 因值以逆轉(zhuǎn)概率 Pi 逆向排序。但若過(guò)大的話，又會(huì)破壞群體中的優(yōu)良模式，對(duì)進(jìn)化運(yùn)算產(chǎn)生不利影響；若過(guò)小的話，產(chǎn)生新個(gè)體的速度又較慢。 16 5 求解非線性規(guī)劃問(wèn)題的遺傳算法 設(shè)計(jì) 傳統(tǒng)的非線性規(guī)劃算法的缺陷是 計(jì)算煩瑣且精度不高，穩(wěn)定性差， 對(duì)函數(shù)初值和函數(shù)性態(tài)要求較高， 且容易陷入局部最優(yōu)解 。 我們最終所求的解是 n 維向量空間 nR 的某子集 D （ 定義域 ） 上的一個(gè)實(shí)數(shù) ， 若采用傳統(tǒng)的二進(jìn)制編碼，則編碼串長(zhǎng)度不固定。 17 當(dāng)可行的搜索空間是凸的，且 為整個(gè)搜索空間的適當(dāng)?shù)囊徊糠謺r(shí)，這種方法應(yīng)該是有效的。該方法的缺點(diǎn)是它對(duì)問(wèn)題本身的依賴性，對(duì)于每個(gè)具體問(wèn)題必須設(shè)計(jì)專門的修復(fù)程序。許多領(lǐng)域中的實(shí)際工作者采用專門的問(wèn)題表達(dá)方式和遺傳算子構(gòu)造了非常成功的遺傳算法，這已是一個(gè)普遍的趨勢(shì)。 本質(zhì)上它是通過(guò)懲罰不可行解將約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題。 圖 51 解空間：可行域與不可行域 懲罰策略的主要問(wèn)題 是如何設(shè)計(jì)一個(gè)懲罰函數(shù) ??xp ，從而能有效地引導(dǎo)遺傳搜索達(dá)到解空間的最好區(qū)域。 由于目標(biāo)函數(shù)是求最小，較好的染色體具有較低的適值，因此我們?nèi)≥^大的數(shù)作為懲罰項(xiàng)，降低其被選中的概率。其基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。將產(chǎn)生的兩個(gè)隨機(jī)數(shù)之間的部分交叉，產(chǎn)生的后代為],. .. ,. .. ,. .. ,[ 21 nji xyyxxX ?? 和 ],. .. ,. .. ,. .. ,[ 21 nji yxxyyY ?? 。由于 我們采用實(shí)數(shù)編碼，即染色體基因串中基因座的值直接是每組解中各分量 ix 的實(shí)數(shù)值，每個(gè)染色體編碼為一個(gè)和解向量維數(shù)相同的實(shí)向量。若 Pc 過(guò)大，會(huì) 21 破壞群體中的優(yōu)良模式，對(duì)進(jìn)化運(yùn)算產(chǎn)生不利影響；若 Pc 過(guò)小，產(chǎn)生新個(gè)體的速度又較慢。即遺傳算法迭代 150 次停止，將得到的最佳個(gè)體作為最優(yōu)解輸出。 （ 7）計(jì)算累積概率 。 （ 12） 判斷是否滿足迭代結(jié)束條件。 （ 2）累加函數(shù) cunsum。選擇函數(shù)是為交叉操作從當(dāng)前種群中選擇兩條染色體來(lái)進(jìn)行交叉操作。兩種算法的計(jì)算結(jié)果如 表 61， 62 所示。 通過(guò)以上分析可以看出， 求解非線性規(guī)劃問(wèn)題的遺傳算法 能夠克服傳統(tǒng)算法對(duì)初始值敏感， 容易陷入局部最 優(yōu)解的缺陷， 收斂效果更好，性能更穩(wěn)定，結(jié)果更合理。同時(shí)我們也設(shè)計(jì)并實(shí)現(xiàn)了 傳統(tǒng)的非線性規(guī)劃算法 ——外點(diǎn)罰函數(shù)法 。從論文的選題、資料的收集到論文的撰寫(xiě)編排整個(gè)過(guò)程中，我得到了許多的熱情幫助。 最后， 再一次 感謝所有在我論文完成過(guò)程中給予 我 幫助和關(guān)心的 良師益友們 。導(dǎo)師的指導(dǎo)將使我終生受益。但在硬件成本大幅下降的今天，用空間和時(shí)間換取最佳結(jié)果是值得的。分析了 傳統(tǒng)的非線性規(guī)劃算法 計(jì)算煩瑣且精度不高，穩(wěn)定性差， 對(duì)函數(shù)初值和函數(shù)性態(tài)要求較高，且容易陷入局部最優(yōu)解的缺陷 。得到表 62。 ③ 累加結(jié)束時(shí)的染色體（即概率之和剛好大于隨機(jī)數(shù) rand 的那條染色體）即為被選 中的染色體。 （ 4）排序函數(shù)。 22 遺傳算法程序流程圖 23 圖 52 求解非線性規(guī)劃問(wèn)題的遺傳算法程序流程圖 遺傳算法中所設(shè)計(jì)的輔助算法的設(shè)計(jì) （ 1） 隨機(jī)數(shù)生成。 實(shí)現(xiàn) 遺傳算法的 第一次遺傳運(yùn)算，種群更新為 A2。 （ 3）將約束條件加入目標(biāo)函數(shù)，確定適應(yīng)度函數(shù) ，計(jì)算適值 e。若 Pm 取值過(guò)大，雖然能夠產(chǎn)生較多的新個(gè)體，但也可能破壞掉很多較好的模式，使得遺傳算法的性能近似于隨機(jī)搜索算法的性能；若 Pm 取值過(guò)小，則變異操作產(chǎn)生新個(gè)體 的能力和抑制早熟現(xiàn)象的能力就會(huì)較差。 pop_size取值的大小與遺傳算法運(yùn)行速度， 種群 多樣性有關(guān)。由于我們進(jìn)行變異的粒度較小，為了增大變異力度，所以我們指定的變異概率較大， Pm=。 交叉算子設(shè)計(jì) 雖然是實(shí)數(shù)編碼，不過(guò)也可以模仿 二進(jìn)制表達(dá)的交叉。滿足公式（ ）。構(gòu)造帶有懲罰項(xiàng)的適應(yīng)度函數(shù)的方法一般有兩種 [3][9]用加法形式： ? ? ? ? ? ?xpxfxeva l ?? （ ） 其中， x 代表染色體； ??xf 是問(wèn)題的目標(biāo)函數(shù)； ??xp 是懲罰項(xiàng)。控制非可行的染色體遠(yuǎn)不是一件容易事，從圖 51 可知，不可行解 b 與最優(yōu)解 a 的距離比不可行解 d 和可行解 c 都近。這樣，將搜索限制在可行域內(nèi)就很難找到可行解。最近， Orvosh 和 Davis 提出了所謂的 5%規(guī)則：該規(guī)則對(duì)于多數(shù)組合優(yōu)化問(wèn)題，若令5%的修復(fù)過(guò)的染色體替代原染色體，則帶有修復(fù) 程序的遺傳算法可取得最好的效果。 （ 2）修復(fù)策略 修補(bǔ)染色體是對(duì)不可行染色體采用修復(fù)程序使之變?yōu)榭尚械摹Ｃ總€(gè)染色體編碼為一個(gè)和解向量維數(shù)相同的實(shí)向量 [2]。 實(shí)用遺傳算法設(shè)計(jì) 編碼方法設(shè)計(jì) 非線性規(guī)劃 屬于最優(yōu)化設(shè)計(jì)的 一種， 屬于約束優(yōu)化問(wèn)題， 其最終目的是選擇一種方法，使目標(biāo)函數(shù) 在滿足約束的條件下 達(dá)到最優(yōu)。一般建議取值范圍是 ～。 pop_size 表示群體中所含個(gè)體的數(shù)量。 15 變異算子的操作步驟： 在群體中所有個(gè)體的碼串范圍內(nèi)隨機(jī)地確定基因座。 遺傳算法中，在交叉運(yùn)算之前必須對(duì)群體中的個(gè)體進(jìn)行配對(duì)。遺傳操作建立在對(duì)個(gè)體的適應(yīng)度進(jìn)行評(píng)價(jià)的基礎(chǔ)之上。 適應(yīng)度函數(shù) 適應(yīng)度是度量群體中各個(gè)個(gè)體在優(yōu)化計(jì)算中有可能達(dá)到或接近于或有助于找到最優(yōu)解的優(yōu)良程度 [2]。 遺傳算法實(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)之一。目前遺傳算法已在模式識(shí)別、圖像恢復(fù)、圖像邊緣特征提取等方面得到了應(yīng)用?，F(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度問(wèn)題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。下面是遺傳算法的一些主要應(yīng)用領(lǐng)域 [2][5]： （ 1）函數(shù)優(yōu)化。實(shí)際上，遺傳算法中有兩類運(yùn)算： （ 1）遺傳運(yùn)算：交叉和變異； （ 2）進(jìn)化運(yùn)算：選擇。在每一代中用“適值”來(lái)測(cè)量染色體的好壞。達(dá)爾文把這種在生存斗爭(zhēng)中適者生存，不適者淘汰的過(guò)程叫做自然選擇。懲罰因子放大系數(shù) 10?C ，置 1?k 。 （ 2） 對(duì)函數(shù)初值和函數(shù)性態(tài)要求較高。 當(dāng) DX? 時(shí)， ),( kMXF 迅速變大的原因是通過(guò)懲罰因子 kM 來(lái)實(shí)現(xiàn)。 極小點(diǎn)或者無(wú)限地向可行域靠近，或者一直保持 在可行集內(nèi)移動(dòng)，直到收斂于原來(lái)約束最優(yōu)化問(wèn)題極小點(diǎn)。例如：如何在現(xiàn)有人力、物力、財(cái)力條件下合理安排產(chǎn)品生產(chǎn)，以取得最高的利潤(rùn)；如何設(shè)計(jì)某種產(chǎn)品，在滿足規(guī)格、性能要求的前提下，達(dá)到最低的成本；如何確定一個(gè)自動(dòng)控制系統(tǒng)的某些參數(shù)，使系統(tǒng)的工作狀態(tài)最佳；如何分配一個(gè)動(dòng)力系統(tǒng)中各電站的負(fù)荷