【導讀】非線性規(guī)劃在工程、管理、經濟、科研、軍事等方面都有廣泛的應用。函數(shù)初值和函數(shù)性態(tài)要求較高，且容易陷入局部最優(yōu)解。遺傳算法是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型。要求可導，適用于并行分布處理，應用范圍廣。法應用于非線性規(guī)劃。算法引進懲罰函數(shù)的概念，構造帶有懲罰項的適應度函數(shù)；通過。實數(shù)編碼，轉輪法選擇，雙點交叉，均勻變異，形成了求解非線性規(guī)劃問題的遺傳算法。入局部最優(yōu)解的缺陷，收斂更合理，性能更穩(wěn)定。

　　

【正文】 ，在指定范圍內隨機產生一個實數(shù) ，來替換掉 1 號基因位的值；若 xPm，則本次不進行變異，繼續(xù)對 2 號位基因值進行變異操作，直到 5 號位結束。由此就產生了新的染色體 。 遺傳算子運行參數(shù)設計 （ 1）編碼長度。由于 我們采用實數(shù)編碼，即染色體基因串中基因座的值直接是每組解中各分量 ix 的實數(shù)值，每個染色體編碼為一個和解向量維數(shù)相同的實向量。本文中有 7個決策變量，因 此染色體長度，也就是編碼長度取 7。 （ 2） 種群 大小 pop_size。 種群 大小 pop_size 表示種群 中所含個體的數(shù)量。 pop_size取值的大小與遺傳算法運行速度， 種群 多樣性有關。一般 根據(jù)問題規(guī)模而定，這里 我們取 300。 （ 3）交叉概率 Pc。交叉操作是遺傳算法中產生新個體的主要方法。若 Pc 過大，會 21 破壞群體中的優(yōu)良模式，對進化運算產生不利影響；若 Pc 過小，產生新個體的速度又較慢。我們?yōu)榱双@得較大的種群多樣性，產生較多的新個體， Pc 值取為 。 （ 4）變異概率 Pm。變異操作是為了保證遺傳算法具有局部搜索能力， 同時也能保證群體多樣性，抑制早熟現(xiàn)象。若 Pm 取值過大，雖然能夠產生較多的新個體，但也可能破壞掉很多較好的模式，使得遺傳算法的性能近似于隨機搜索算法的性能；若 Pm 取值過小，則變異操作產生新個體 的能力和抑制早熟現(xiàn)象的能力就會較差。這里由于是對每個基因座 進行變異操作，為了保證變異效果， Pm取值較大，為 。 （ 5）終止代數(shù) T。為保證遺傳算法能獲得近似最優(yōu)解， T 取值為 150。即遺傳算法迭代 150 次停止，將得到的最佳個體作為最優(yōu)解輸出。 求解非線性規(guī)劃問題的遺傳算法 程序設計 算法過程描述 由前面 遺傳算法的算法描述再結合本次畢業(yè)設計的實際情況，我們設計了以下的具體算法流程 [3][9][16]。步驟如下： （ 1）初始化遺傳算法的運行參數(shù)：種群大小 pop_size，每條染色體基因串長度 length，交叉概率 Pc，變異概率 Pm，算法迭代次數(shù) T，當前迭代次數(shù) t。 （ 2）根據(jù)所給 x 的范圍，種群大小，染色體長度，隨機生成符合條件的初始種群 A。 （ 3）將約束條件加入目標函數(shù)，確定適應度函數(shù) ，計算適值 e。 （ 4）對 適值 e 從小到大排序，排序后的適值 記為 s， 并記錄變動情況 l。 （ 5） 根據(jù)排序結果把每一代最小適值賦給 M， 并記錄局部最優(yōu)值對應的位置（行），用 length?1 的行向量 B 表示。 （ 6）輸出每次迭代 t 對應的 局部極值位置 B 和局部最優(yōu)值 s(1)。 （ 7）計算累積概率 。 （ 8） 用轉輪法進行選擇運算 。 種群由 A 進化為 A1。 （ 9） 雙點交叉實現(xiàn)交叉運算 。 實現(xiàn) 遺傳算法的 第一次遺傳運算，種群更新為 A2。 （ 10） 均勻變異實現(xiàn)變異過程。實現(xiàn)第二次遺傳運算，種群更新為 A3。 （ 11）更新種群 ， 將 A3 賦給 A。 （ 12） 判斷是否滿足迭代結束條件。滿足轉（ 13），不滿足轉 （ 3） ，繼續(xù)迭代。 （ 13） 對每代最小適值 M 排序， me 為排序后的向量。 （ 14）輸出最小適值 Min，即為所求全局最優(yōu)。 22 遺傳算法程序流程圖 23 圖 52 求解非線性規(guī)劃問題的遺傳算法程序流程圖 遺傳算法中所設計的輔助算法的設計 （ 1） 隨機數(shù)生成。程序中多處涉及到隨機數(shù)的生成，像一開始初始種群的生成，后面的選擇、交叉、變異的循環(huán)條件判斷，都有用到。這里我們使用常用的 rand 函數(shù)。 rand函數(shù)的作用是生成 0～ 1 之間的浮點型矩陣，通過對函數(shù)的簡單運算可以生成我們想要的確定范圍內的矩陣。 （ 2）累加函數(shù) cunsum。程序中計算累積概 率部分，可以使用循環(huán)運算實現(xiàn)，但我們使用 MATLAB 中更便捷的函數(shù) cumsum 直接計算元素累加，如 a=[1 2 3 4]，則 cumsum(a)=[1 3 6 10]。 （ 3）上取整函數(shù) ceil。 ceil()是向正無窮大舍入，如 ceil()=3，配合 rand 函數(shù)可以隨機生成一定范圍內的整數(shù)。 （ 4）排序函數(shù)。因為我們所求是最小化問題，在龐大的種群和多次迭代過程中為方便找出局部最小值和全局最優(yōu)值，我們可以對每次結果進行排序。 sort 函數(shù)實現(xiàn)按升序排序，如 [s,l]=sort(e)，對 e 從小到大進行排序， s 為排序后的矩陣， l 為變動情況。 （ 5） 選擇函數(shù)。選擇函數(shù)是為交叉操作從當前種群中選擇兩條染色體來進行交叉操作。我們采用 轉輪法 （ Roulette Wheel） 來選擇染色體。具體過程如下： ① 利用 rand 函數(shù)產生一個 0～ 1 之間的隨機數(shù) r。 ② 從第一條染色體起，將當前種群中各染色體的選擇概率進行累加，當選擇概率總和大于等于 rand 時停止。 ③ 累加結束時的染色體（即概率之和剛好大于隨機數(shù) rand 的那條染色體）即為被選 中的染色體。 24 6 算法的 結果 分析 概述 在以上算法分析設計的基礎上，我們用 MATLAB 語言分別實現(xiàn)了求解非線性規(guī)劃問題的遺傳算法和 外點 罰函數(shù)法 。本章我們通過運行實際的算法程序，通過對運行結果進行統(tǒng)計分析，比較兩種算法各自的優(yōu)越性。 結果 比較 為了能 直觀地表現(xiàn)兩種算法的實際執(zhí)行結果，我們將兩種算法的執(zhí)行結果以圖表 的形式直觀地表達出來。兩種算法的計算結果如 表 61， 62 所示。 我們通過統(tǒng)計兩種算法所得 最優(yōu)值的變化，來比較兩種算法的 收斂 效果。 為了充分比較兩種算法收斂效果，我們 對遺傳算法 分別采用 大小為 300 和 200 的兩個種群 ，懲罰函數(shù)法分別取初始懲罰因子 M 為 10 和 1，兩種算法分別 執(zhí)行算法 10 次 ，得到結果如表61 所示。 表 61 最優(yōu) 適 值 表 遺傳算法 懲罰函數(shù)法 執(zhí)行 序號 種群 300 種群 200 初始懲罰因子 M=10 初始懲罰因子 M=1 1 2 3 4 5 6 7 8 9 10 25 我們統(tǒng)計兩種算法之間的最大值、最小值、均值和方差。得到表 62。 表 62 均值和方差表 遺傳算法 懲罰函數(shù)法 種群 300 種群 200 初始懲罰因子 M=10 初始懲罰因子 M=1 最大值 最小值 均 值 方 差 我們將表 61 中的數(shù)據(jù)以圖的形式進行表示，得到兩種算法取得最優(yōu)適應度值的變化曲線，如下圖所示。 圖 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)了大的波動。 這充分體現(xiàn)了遺傳算法的優(yōu)越性，遺傳算法的全局搜索能力使其能夠不受初始點的影響而找到近似全局最優(yōu)解。 通過以上分析可以看出， 求解非線性規(guī)劃問題的遺傳算法 能夠克服傳統(tǒng)算法對初始值敏感， 容易陷入局部最 優(yōu)解的缺陷， 收斂效果更好，性能更穩(wěn)定，結果更合理。 同時 我們比較兩種算法的運行時間，如下表。 表 63 運行時間比較 表 遺傳算法 懲罰函數(shù)法 種群 300 種群 200 初始懲罰因子 M=10 初始懲罰因子 M=1 最大值 最小值 均 值 從表中可以看出，懲罰函數(shù)法在運行時間上明顯優(yōu)于遺傳算法，說 明 傳統(tǒng)算法也有其 可取 優(yōu)勢，不可能被完全取代。 下圖即為 求解非線性規(guī)劃問題的遺傳算法最優(yōu) 適值 變化曲線： 27 圖 64 求解非線性規(guī)劃問題的遺傳算法最優(yōu) 適 值變化曲線 28 7 總 結 本文詳細介紹了 非線性規(guī)劃、 外點 罰函數(shù) 法、 遺傳算法的基本理論。分析了 傳統(tǒng)的非線性規(guī)劃算法 計算煩瑣且精度不高，穩(wěn)定性差， 對函數(shù)初值和函數(shù)性態(tài)要求較高，且容易陷入局部最優(yōu)解的缺陷 。 詳細介紹了遺傳算法的優(yōu)點：簡單，通用，魯棒性強，不要求目標函數(shù)可導，是一種全局搜索算法。由此我們意識到 用 遺傳算法 求解非線性規(guī)劃問題 是提高 收斂 效果的有效途徑。 在 充分理解遺傳算法基本理論，算法思想，關鍵技術的基礎上，結合實際情況，設計并最終實現(xiàn)了 求解非線性規(guī)劃問題的遺傳算法 。同時我們也設計并實現(xiàn)了 傳統(tǒng)的非線性規(guī)劃算法 ——外點罰函數(shù)法 。通過比較兩種算法的實際運行結果，分析兩者之間的性能差異。 通過理論分析以及對測試數(shù)據(jù)的統(tǒng)計分析，我們可以看到 求解非線性規(guī)劃問題的遺傳算法 與 傳統(tǒng)的非線性規(guī)劃算法 相比， 收斂 結果更 優(yōu) ，性能更穩(wěn)定，魯棒性強， 對目標函數(shù)既不要求連續(xù)，也不要求可 導，有效地克服了傳統(tǒng)算法對函數(shù)初值和函數(shù)性態(tài)要求高 ，容易陷入局部最優(yōu)解的缺陷。但遺傳算法程序設計復雜，算 法耗費大量存儲空間和運行時間。但在硬件成本大幅下降的今天，用空間和時間換取最佳結果是值得的。同時我們也看到，有時候傳統(tǒng)算法所得結果比遺傳算法要好，這說明傳統(tǒng)算法也有其可取之處，遺傳算法無法完全取代傳統(tǒng)算法。 通過幾個月的努 力，即將完成論文，由于本人能力有限，本論文中或多或少 會存在一些缺點，所設計的程序難免有一些不足，還懇請各位老師和同學給予批評和指正。 29 致 謝 在論文完成之際，我的心情萬分激動。從論文的選題、資料的收集到論文的撰寫編排整個過程中，我得到了許多的熱情幫助。 首先，我要衷心地感謝導師厙向陽教 授幾年來在學習和生活中給予的諄諄教誨和悉心的關懷。在論文的選題、研究以及撰寫過程中，自始至終得到了導師的精心指導和熱情幫助，其中無不凝聚著導師的心血和汗水。導師嚴謹求實和一絲不茍的學風、扎實勤勉和孜孜不倦的工作態(tài)度時刻激勵著我努力學習，并將鞭策我在未來的工作中銳意進取、奮發(fā)努力。導師的指導將使我終生受益。 還要感謝我的學長和組員，他們在畢業(yè)設計的過程中給了我很多啟發(fā)和幫助。在我的學習和生活中 給予 了我很大的幫助和支持。對他們也表示我衷心的感謝！ 還要感謝我的 爸爸媽媽， 幾十年的 養(yǎng)育之恩 我 無以回報， 在這里祝愿 你們 永遠健康快樂。 最后， 再一次 感謝所有在我論文完成過程中給予 我 幫助和關心的 良師益友們 。 謝謝！ 30 參考文獻 [1] 汪定偉 ,王俊偉 ,王洪峰 ,張瑞友等編著 .智能優(yōu)化方法 [M].北京 :高等教育出版 社 ,～ 57 [2] 李敏強 ,寇紀淞 ,林丹等 .遺傳算法的基本理論與應用 [M].北京 :科學出版社 ,～112 [3] [日 ]玄光男 ,程潤偉著 .遺傳算法與工程設計 [M].汪定偉 ,唐加福 ,黃敏譯 .北京 :科學出版社 ,～ 40 [4] 運籌學編寫組編 .運籌學 [M].北京 :清華大學出版社 ,～ 189 [5] 葉家成 ,彭宏 .解全局優(yōu)化問題的遺傳算法的一些新進展 .吉首大學學報 (自然科學版 ),1997,(01):68～ 70 [6] 敖 友云 , 遲洪欽 . 一種 求 解約 束函 數(shù)優(yōu) 化 問題 的遺 傳 算法 . 燕 山大 學 學報 ,2021,(04):294～ 297 [7] 胡能發(fā) ,潘清芳 ,康立山 .一個新的求解多峰函數(shù)的遺傳算法 .荊州師范學院學報 ,2021,(05):21～ 23 [8] 劉瓊蓀 ,周聲華 .基于自適應懲罰函數(shù)法的混合遺傳算法 [J].重慶大學學報 (自然科學版 ),2021,(06):78～ 81 [9] 張晶 ,翟鵬程 ,張本源 .懲罰函數(shù)法在遺傳算法處理約束問題中的應用 [J].武漢理工大學學報 ,2021,(02):56～ 59 [10] 楊曉華 ,楊志峰 ,酈建強 .解非線性優(yōu)化問題的混合加速遺傳算法 [J].北京師范大學學報(自然科學版 ),2021,(04):551～ 556 [11] 韋凌云 ,柴躍廷 ,趙玫 .不等式約束的非線性規(guī)劃混合遺傳算法 [J].計算機工程與應用 ,2021,(22):46～ 49 [12] 劉淳安 ,王宇平 .解非線性規(guī)劃問題的非參數(shù)罰函數(shù)多目標正交遺傳算法 [J].運籌與管理 ,2021,(05):35～ 38 [13] 朱國會 ,沈渝路 .求解一類非線性規(guī)劃問題的新途徑 [J].長春工業(yè)大學學報 (自然科學版 ),2021,(04):64～ 66 [14] 唐加福 ,汪定偉 .一種求解非線性規(guī)劃問題的改進遺傳算法 [J].東北大學學報 (自然科學版 ),1997,(05):490～ 493 [15] 唐加福 ,汪定偉 ,許寶棟 ,李露 .基于評價函數(shù)的遺傳算法求解非線性規(guī)劃問題 [J].控制與決策 ,2021,(