【正文】 ........ 3 非線性規(guī)劃的概念 ............................................................................................... 3 非線性規(guī)劃的數(shù)學模型 ....................................................................................... 3 非線性規(guī)劃的求解方法 ....................................................................................... 4 一維最優(yōu)化方法 ........................................................................................ 4 無約束最優(yōu)化方法 .................................................................................... 4 約束最優(yōu)化方法 ........................................................................................ 5 非線性規(guī)劃的應用 ............................................................................................... 5 3 傳統(tǒng)非線性規(guī)劃算法 —— 外點罰函數(shù)法 ...................................................................... 6 算法概述 ............................................................................................................... 6 算法描述 ............................................................................................................... 6 算法性能分析 ....................................................................................................... 7 外點 罰函數(shù) 法的程序設計 ................................................................................... 8 程序步驟 ..................................................................................................... 8 程序流程圖 ................................................................................................. 8 4 遺傳算法 ........................................................................................................................ 10 遺傳算法概述 ..................................................................................................... 10 遺傳算法的生物學基礎 .......................................................................... 10 遺傳算法的一般結構 .............................................................................. 10 遺傳算法的特點 ...................................................................................... 12 II 遺傳算法的應用 ...................................................................................... 12 遺傳算法實現(xiàn)的關鍵技術 ................................................................................. 13 5 求解非線性規(guī)劃問題的遺傳算法設計 ........................................................................ 16 實用遺傳算法設計 ............................................................................................. 16 求解非線性規(guī)劃問題的遺傳算法程序設計 ..................................................... 21 算法過程描述 .......................................................................................... 21 遺傳算法程序流程圖 .............................................................................. 22 遺傳算法中所設計的輔助算法的設計 .................................................. 23 6 算法的結果分析 ............................................................................................................ 24 概述 ..................................................................................................................... 24 結果比較 ............................................................................................................. 24 7 總結 ................................................................................................................................ 28 致謝 .................................................................................................................................... 29 參考文獻 ............................................................................................................................ 30 1 1 概 論 背景介紹 非線性規(guī)劃簡介 具有非線性約束條件或目標函數(shù)的 數(shù)學規(guī)劃 ，稱為非線性規(guī)劃。 50 年代末到 60 年代末出現(xiàn)了許多解非線性規(guī)劃問題的有效的算法 ， 70 年代又得到進一步的發(fā)展。傳統(tǒng)的解決非線性規(guī)劃問題的方法有多種，如 搜索法、梯度法、變尺度法、罰函數(shù)法、拉格朗日乘子法 、 可行方向法等， 雖然解法很多 ， 非線性規(guī)劃目前還沒有能適用于各種問題的算法 ， 各個方法都有自己特定的適用范圍。 遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領域 ， 對問題的種類有很強的魯棒性，所以廣泛應用于很多領域，如函數(shù)優(yōu)化 、 組合優(yōu)化 、生產(chǎn)調(diào)度問題 、 自動控制 、 機器人智能控制 、 圖像處理，人工生命 、 遺傳編程 、 機器學習等。 本文的主要 內(nèi)容 就是應用 遺傳算法的基本思想，結合本次實驗的實際情況，對基本遺傳算法 加以改進，將遺傳算法應用于求解非線 性規(guī)劃問題，形成 求解非線性規(guī)劃問題的遺傳算法 。非線性規(guī)劃研究一個 n 元實函數(shù)在一組等式或不等式的約束條件下的極值問題，且目標函數(shù)和約束條件至少有一個是未知量的非線性函數(shù)。然后將各種限制條件加以抽象 ， 得出決策變量應滿足的一些等式或 不等式，稱之為約束條件 [4]。 定義域 D 中滿足約束條件的點稱為問題的可行解。實用非線性規(guī)劃問題要求整體解，而現(xiàn)有解法大多只是求出局部解。 ① 黃金分割法 ，又稱 法。它也是針對單峰 函數(shù)的。 此外，還有斐波那契法、割線法、有理插值法、分批搜索法等。這類迭代算法可分為兩類。然后對新點施行同樣手續(xù) ， 如此反復迭代，直到滿足預定的精度要求為止。 ② 牛頓法 ：收斂速度快，但不穩(wěn)定，計算也較困難。 屬于直接型的算法有交替方向法（又稱坐標輪換法）、模式搜索法、旋 轉(zhuǎn)方向法、鮑威爾共軛方向法和單純形加速法等。它又分兩類，一類叫懲罰函數(shù)法，或稱外點法；另一類叫障礙函數(shù)法，或稱內(nèi)點法。 ④ 近似型算法 ：這類算法包括序貫線性規(guī)劃法和 序貫 二次規(guī)劃法。對于靜態(tài)的最優(yōu)化問題，當目標函數(shù)或約束條件出現(xiàn)未知量的非線性函 數(shù)，且不便于線性化，或勉強線性化后會招致較大誤差時，就可應用非線性規(guī)劃的方法去處理。 外 點 罰函數(shù)法是從非可行解出發(fā)逐漸移動到可行區(qū)域的方法。 對于問題 （ ） ，構造一函數(shù)為 )()(),( XMXfMXF kk ??? （ ） 其中， ? ? ? ? ))(()()()( 2121 XguXgXhX ili imj j ?? ?? ??? （ ） 在 （ ） 中， )(X? 又稱為懲罰函數(shù)， ??? ?? ??? .,0 ,0)( 時當 時，當 DX DXX? （ ） .,2,10)(,1 0)(,0))(( liXg XgXgu i ii ????? ??? 時，當 時，當 （ ） 7 0?kM 是一個逐漸增大的參數(shù)，稱為懲罰因子。但是研究 DX? 時， ),( kMXF 的最優(yōu)解不是我們所需要的。簡言之，外點罰函數(shù)法的思想是：當點 DX? 時，設法加大不可行點處的函數(shù)值，使不可行點不能成為 ),( kMXF 在 nR 中的最優(yōu)解。 算法性能分析 通過長期的理論研究和實驗結果，人們總結出懲罰函數(shù)的優(yōu)點有： （ 1） 罰函數(shù)法 是解決非線性規(guī)劃問題的一種經(jīng)典算法，這種算法簡單易行、熟練數(shù)度快，在很多實際問題的求解中得到了應用 。 （ 3） 罰函數(shù)法在實際計算中的缺點是罰因子 M 的取值難于把握 ， 太小起不到懲罰作用 ； 太大則由于誤差的影響會導致錯誤 。 8 外點 罰函數(shù) 法的程序設計 為 了能和 求解非線性規(guī)劃問題的遺傳算法 進行比較，我們同時實現(xiàn)最經(jīng)典的，也是得到最廣泛應用的 傳統(tǒng)的非線性規(guī)劃算法 —— 外點罰函數(shù) 法，通過對二者的結果，比較二者性能的差別。 （ 2） 假設已獲得迭代點 1?kX ，以 1?kX 為初始點，求解無約束問題 ),(min kMXF （ ） 設其最優(yōu)點為 kX 。 9 圖 31 外點罰函數(shù)法 程序流程圖 10 4 遺傳 算法 遺傳算法概述 遺傳算法的生物學基礎 遺傳算法的生物學基礎是達爾文的自然選擇學說。達爾文的自然選擇學說表明，遺傳和變異是決定生物進化的內(nèi)在因素。種群中的每個個體是問題的一個解，稱為“染色體”。生成的下一代染色體稱為后代。這樣，經(jīng)過若干代之后，算法收斂于最好的染色體，它很可能就是問題的最優(yōu)解或者次優(yōu)解。 遺傳運算模擬了基因在每一代中創(chuàng)造新后代的繁殖過程，進化運算則是種群逐代更新的過程。 （ 3） 遺傳算法使用多個點的搜索信息，具有隱含并行性。函數(shù)優(yōu)化是遺傳算法的經(jīng)典應用領域，也是對遺傳算法進行性能評價的常用算例。實踐證明，遺傳算法對于組合優(yōu)化中的 NP 完全問題非常有效。 （ 4）自動控制。 （ 6）圖像處理。 13 （ 7）人工生命。