【正文】 itial value and request the objective function to be continuous and differential. The results are also easily trapped into local optimal solution. Geic algorithm is a kind of calculate model which simulates Darwin39。 非線性規(guī)劃是 20世紀 50 年代才開始形成的一門新興學科。 非線性規(guī)劃在工程、管理、經濟、科研、軍事等方面都有廣泛的應用，為最優(yōu)化設計提供了有力的工具。 遺傳算法簡介 遺傳算法（ Geic Algorithm） ， 是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法 ， 它是 由 美國 Michigan大學 教授于 1975 年首先提出來的，并出版了頗 有影響的專著《 Adaptation in Natural and Artificial Systems》， GA 這個名稱才逐漸為人所知 ， 教授所提出的GA 通常為簡單遺傳算法（ SGA）。并且取得了令人矚目的成果。具體內容包括編碼方法設計，適應度函數(shù)設計，選擇算子、交叉算子、變異算子等遺傳算子設計，算法流程設計，并在設計的基礎上用 MATLAB 語言實現(xiàn)該算法的程序，運行并調試程序，直至得到正確的結果。目標函數(shù)和約束條件都是線性函數(shù)的情形則屬于 線性規(guī)劃 。 非線性規(guī)劃問題的一般數(shù)學模型可表述為求未知量 nxxx ,..., 21 ， 使?jié)M足約束條件： ? ?? ???? ?? ?? pjxxh mixxgnjni ,...,1,0,..., ,...,1,0,...,11 （ ） 并使目標函數(shù) ? ?nxxf ,...,1 達到最小值 (或最大值 )。全體可行解所成的集合稱為問題的可行集。 4 非線性規(guī)劃的求解方法 一維最優(yōu)化方法 指尋求一元函數(shù)在某區(qū)間上的最優(yōu)值點的方法。它適用于單峰函數(shù)。其基本思想是：在一個猜測點附近將目標函數(shù)的導函數(shù)線性化，用此線性函數(shù)的零點作為新的猜測點，逐步迭代去逼近最優(yōu)點。 無約束最優(yōu)化方法 指尋求 n 元實函數(shù) f 在整個 n 維向量空間 nR 上的最優(yōu)值點的方法。一類需要用目標函數(shù)的導函數(shù) ， 稱為解析法。根據(jù)搜索方向的取法不同 ， 可以有各種算法。 ③ 共軛梯度法 ：收斂較快，效果較好。 5 約束最優(yōu)化方法 指前述一般非線性規(guī)劃模型的求解方法。它們都是將原問題轉化為一系列無約束問題來求解。前者將原問題化為一系列線性規(guī)劃問題求解，后者將原問題化為一系列二次規(guī)劃問題求解。 6 3 傳統(tǒng)非線性規(guī)劃算法 —— 外點罰函數(shù)法 算法概述 罰函數(shù)法求解非線性規(guī)劃問題的思想是，利用問題中的約束函數(shù) 做 出適當?shù)牧P函數(shù)，由此構造出帶參數(shù)的增廣目標函數(shù)，把問題轉化為無約束非線性規(guī)劃問題。內 點 罰函數(shù)法也稱為障礙罰函數(shù)法，這種方法是在可行域內部進行搜索，約束邊界起到類似圍墻的作用，如果當前解遠離約束邊界時，則罰函數(shù)值是非常小的，否則罰函數(shù)值接近無窮大的方法。 ),( kMXF 又稱為 問題 （ ） 的增廣目標函數(shù)。為此規(guī)定，當 DX? 時， ),( kMXF 在 X 點處的函數(shù)值迅速變大，換而言之，可行域外的任一點 X 處的函數(shù)值 ),( kMXF 都相當大。 在用外點罰函數(shù)法求解問題 （ ） 時，首先構造增廣目標函數(shù) ),( kMXF ，然后按照無約束優(yōu)化方法求解。 （ 2） 計算效率高 ，穩(wěn)定性較好。 在搜索過程開始的時候 ， 一個較大的罰因子將會阻礙非可行域的搜索 。 程序步驟 對于問題 （ ） ，構造一函數(shù)為 )()(),( XMXfMXF kk ??? （ ） 其中，懲罰函數(shù) )(X? 按照式 （ ） 構造，給定終止限 ? （ 可取 610??? ）。 （ 3） 若 ?? ?)(XMk ，則 kX 就是所要求問題的最優(yōu)解，打印 ? ?)(, kk XfX ， 結束；否則轉 （ 4）。自然選擇學說認為，生物要生存下去，就必須進行生存斗爭。遺傳能使生物的性狀不斷地傳遞給后代，因而保持了物種的特性，變異 能夠使生物的性狀發(fā)生改變，從而適應新的環(huán)境而不斷地向前發(fā)展 [2]。染色體是一串符號，比如一個二進制字符串。后代是由前一代染色體通過交叉或變異運算形成的。 設 ??tP 和 ??tC 分別表示第 t 代的雙親和后代，遺傳算法的一般結構可描述如下 [3]： 遺傳算法過程 ： begin 0?t ； 初始化 ??tP ； 評估 ??tP ； while 不 滿足終止條件 do begin 重組 ??tp 獲得 ??tC ； 評估 ??tC ； 11 從 ??tP 和 ??tC 中選擇 ? ?1?tP ； 1??tt ； end end 圖 41 遺傳算法的一般結構 通常初始化是隨機產生的。 12 遺傳算法的特點 遺傳算法是一類可用于復雜系統(tǒng)優(yōu)化的具有魯棒性的搜索算法，與傳統(tǒng)的優(yōu)化算法相比 ， 主要有以下特點 [3]： （ 1） 遺傳算法以決策變量的編碼作為運算對象。 （ 4） 遺傳算法使用概率搜索技術，而非確定性規(guī)則。 （ 2）組合優(yōu)化。 （ 3）生產調度問題。在自動控制領 域中有許多與優(yōu)化相關的問題需要求解，遺傳算法已在其中得到了初步的應用，并顯示出了良好的效果。在圖像處理過程中，不可避免地會產生一些誤差，這些誤差會影響圖像處理的效果。人工生命與遺 傳算法有著密切的關系，基于遺傳算法的進化模型是研究人工生命現(xiàn)象的重要基礎理論。 （ 9）機器學習。 常用 的 編碼方法 有 ： （ 1） 二進制編碼：使用由二進制符號 0 和 1 所組成的二值符號集 {0， 1}進行編碼，它所構成的個體基因型是一個二進制編碼符號串。 （ 3） 符號編碼：個體染色體編碼串中的基因值取自一個無數(shù)值含義、而只有代碼含義的符號集。而對目標函數(shù) 值的使用是通過評價個體的適應度來體現(xiàn)的。 選擇算子 遺傳算法使用遺傳算子（或稱為復制算子， Reproduction Operator）來對群體中的個 14 體進行優(yōu)勝劣汰操作：適應度較高的個體被遺傳到下一代群體中的概率較大；適應度較低的個體被遺傳到下一代群體中的概率較小。 常見選擇算子： （ 1）比例選擇：各個個體被選中的概率與其適應度大小成正比。 交叉算子 遺傳算法中的交叉運算是指對兩個相互配對的染色體按某種方式相互交換其部分基因， 從而形成兩個新的個體。 常見交叉算子： （ 1）單點交叉（ Onepoint Crossover）：在個體編碼串中只隨機設置一個交叉點，實行交叉時，該點前或后的兩個個體的部分結構進行互換，并生成兩個新個體。遺傳算法導入變異的目的有兩個：一是使遺傳算法具有局部的隨機搜索能力。 常見變異算子： （ 1）基本位變異（ Simple Mutation） 是指對個體編碼串中以變異概率 Pm隨機指定的某一位基因座上的基因值作變異運算。使用二進制編碼時， L 與問題所要求的求解精度有關；使用浮點數(shù)編碼時， L 與決策變量的個數(shù) n 相等；使用符號編碼是， L 由問題的編碼方式確定。 （ 3）交叉概率 Pc。 （ 4）變異概率 Pm。 T 表示遺傳算法運行到指定的進化代數(shù)之后就停止運行，并將當前群體中的最佳個體作為所求問題的最優(yōu)解 輸出。因此，將遺傳算法應用于非線性規(guī)劃，是改善收斂效果，提高最優(yōu)化質量的有效途徑。 我們將這組解作為染色體， 其 中每個 ix 相當于染色體上的基因， 這也就是編碼對象。而且采用二進制編碼，又要牽涉到 十進制與二進制的轉換， 在實際操作過程中要頻繁進行編碼和解碼操作，費時 費力。今年來，已經提出了幾種運用遺傳算法滿足約束的技術，這些技術大致可以分為以下幾類 [3][16]： （ 1）拒絕策略 拒絕策略拋棄所有進化過程中產生的不可行 的染色體。例如，對許多約束優(yōu)化問題初始種群可能全由非可行染色體構成，這就需要對他們進行修補。 Liepins 和他的合作者通過對遺傳算法的性能試驗測試證明，對于一個有多個不連通可行集 的約束組合優(yōu)化問題，修復策略在速度和計算性能上都遠勝過其他策略。 修復后的染色體可以只用來作評估，也可用來替代原染色體進入種群。 （ 3）改進遺傳算子策略 解決可行性問題的一個合理辦法是設計針對問題的表達方式以及專門的遺傳算子來維持染色體的可行性。 （ 4）懲罰策略 上面三種策略的 共同優(yōu)點是都不會產生不可行解，缺點則是無法考慮可行域外的點。懲罰策略就是這類在遺傳搜索中考慮不可行解的技術。 18 一般，解空間包含兩部分：可行域和不可行域。可以相信，盡管 b 是不可行解，但它比 c 含有更多的有關最優(yōu)點的信息。設計懲罰函數(shù)沒有一般規(guī)則，這仍要依賴于待解的問題。并要求? ?maxxp ≤ ? ?minxf 以避免出現(xiàn)負的適值。 當 ??xg 不滿 足約束時，也就是 ??xg 小于 0時，括號里的邏輯運算結果為 1，由于約束是要求 ??xg 大于等于 0，則要對其進行懲罰，乘以 1 相當于對 ??xg 取絕對值，再乘以一個較大的數(shù) 1e+3， 則此時 ??xp 為一個較大的實數(shù)，實現(xiàn)了其懲罰作用。 選擇算子設計 遺傳算法使用遺傳算子來對群體中的個體進行優(yōu)勝劣汰操作。 它是一種 正比選擇策略，能夠根據(jù)與適值成正比的概率選擇出新的種群?？紤]到算法效率和實現(xiàn)便捷程度，我們采用雙點交叉。 若隨機生成 的 交叉點為 2 和 5， 則將 第 2 號 和第 5 號位置 之間 的基因值互換，交叉后產生的新染色體為： NewChromosome1=[1， 2， 8， 9， 5]，NewChromosome2=[6， 7， 3， 4， 10]。由此就產生了新的染色體 。 （ 2） 種群 大小 pop_size。 （ 3）交叉概率 Pc。 （ 4）變異概率 Pm。 （ 5）終止代數(shù) T。步驟如下： （ 1）初始化遺傳算法的運行參數(shù)：種群大小 pop_size，每條染色體基因串長度 length，交叉概率 Pc，變異概率 Pm，算法迭代次數(shù) T，當前迭代次數(shù) t。 （ 5） 根據(jù)排序結果把每一代最小適值賦給 M， 并記錄局部最優(yōu)值對應的位置（行），用 length?1 的行向量 B 表示。 種群由 A 進化為 A1。實現(xiàn)第二次遺傳運算，種群更新為 A3。 （ 13） 對每代最小適值 M 排序， me 為排序后的向量。這里我們使用常用的 rand 函數(shù)。 （ 3）上取整函數(shù) ceil。 sort 函數(shù)實現(xiàn)按升序排序，如 [s,l]=sort(e)，對 e 從小到大進行排序， s 為排序后的矩陣， l 為變動情況。具體過程如下： ① 利用 rand 函數(shù)產生一個 0～ 1 之間的隨機數(shù) r。本章我們通過運行實際的算法程序，通過對運行結果進行統(tǒng)計分析，比較兩種算法各自的優(yōu)越性。 為了充分比較兩種算法收斂效果，我們 對遺傳算法 分別采用 大小為 300 和 200 的兩個種群 ，懲罰函數(shù)法分別取初始懲罰因子 M 為 10 和 1，兩種算法分別 執(zhí)行算法 10 次 ，得到結果如表61 所示。 圖 61 遺傳算法最優(yōu)值變化曲線 圖 62 懲罰函數(shù)法最優(yōu)值變化曲線 26 圖 63 綜合比較曲線 從表 62 可以看出， 遺傳算法所得最優(yōu)適值的最大值、平均值、方差要 比懲罰函數(shù)法小得多 ，說明遺傳算法收斂效果更好，結果更合理；圖 61 和圖 62 說明兩個算法對自身參數(shù)設定的敏感性，可以看出 相對于懲罰函數(shù)法， 遺傳算法受初始參數(shù)影響 要小很多 ；圖 63 綜合比較曲線將兩個算法結果放在一個圖中比較，可以看出，遺傳算法的變化曲線非常平穩(wěn)，波動較小，而懲罰函數(shù)法對初始參數(shù)特別敏感，出現(xiàn)了大的波動。 表 63 運行時間比較 表 遺傳算法 懲罰函數(shù)法 種群 300 種群 200 初始懲罰因子 M=10 初始懲罰因子 M=1 最大值 最小值 均 值 從表中可以看出，懲罰函數(shù)法在運行時間上明顯優(yōu)于遺傳算法，說 明 傳統(tǒng)算法也有其 可取 優(yōu)勢，不可能被完全取代。由此我們意識到 用 遺傳算法 求解非線性規(guī)劃問題 是提高 收斂 效果的有效途徑。 通過理論分析以及對測試數(shù)據(jù)的統(tǒng)計分析，我們可以看到 求解非線性規(guī)劃問題的遺傳算法 與 傳統(tǒng)的非線性規(guī)劃算法 相比， 收斂 結果更 優(yōu) ，性能更穩(wěn)定，魯棒性強， 對目標函數(shù)既不要求連續(xù)，也不要求可 導，有效地克服了傳統(tǒng)算法對函數(shù)初值和函數(shù)性態(tài)要求高 ，容易陷入局部最優(yōu)解的缺陷。 通過幾個月的努 力，即將完成論文，由于本人能力有限，本論文中或多或少 會存在一些缺點，所設計的程序難免有一些不足，還懇請各位老師和同學給予批評和指正。在論文的選題、研究以及撰寫過程中，自始至終得到了導師的精心指導和熱情幫助，其中無不凝聚著導師的心血和汗水。在我的學習和生活中 給予 了我很大的幫助和支持