【正文】 謝謝！ 30 參考文獻(xiàn) [1] 汪定偉 ,王俊偉 ,王洪峰 ,張瑞友等編著 .智能優(yōu)化方法 [M].北京 :高等教育出版 社 ,～ 57 [2] 李敏強(qiáng) ,寇紀(jì)淞 ,林丹等 .遺傳算法的基本理論與應(yīng)用 [M].北京 :科學(xué)出版社 ,～112 [3] [日 ]玄光男 ,程潤偉著 .遺傳算法與工程設(shè)計 [M].汪定偉 ,唐加福 ,黃敏譯 .北京 :科學(xué)出版社 ,～ 40 [4] 運籌學(xué)編寫組編 .運籌學(xué) [M].北京 :清華大學(xué)出版社 ,～ 189 [5] 葉家成 ,彭宏 .解全局優(yōu)化問題的遺傳算法的一些新進(jìn)展 .吉首大學(xué)學(xué)報 (自然科學(xué)版 ),1997,(01):68～ 70 [6] 敖 友云 , 遲洪欽 . 一種 求 解約 束函 數(shù)優(yōu) 化 問題 的遺 傳 算法 . 燕 山大 學(xué) 學(xué)報 ,2021,(04):294～ 297 [7] 胡能發(fā) ,潘清芳 ,康立山 .一個新的求解多峰函數(shù)的遺傳算法 .荊州師范學(xué)院學(xué)報 ,2021,(05):21～ 23 [8] 劉瓊蓀 ,周聲華 .基于自適應(yīng)懲罰函數(shù)法的混合遺傳算法 [J].重慶大學(xué)學(xué)報 (自然科學(xué)版 ),2021,(06):78～ 81 [9] 張晶 ,翟鵬程 ,張本源 .懲罰函數(shù)法在遺傳算法處理約束問題中的應(yīng)用 [J].武漢理工大學(xué)學(xué)報 ,2021,(02):56～ 59 [10] 楊曉華 ,楊志峰 ,酈建強(qiáng) .解非線性優(yōu)化問題的混合加速遺傳算法 [J].北京師范大學(xué)學(xué)報(自然科學(xué)版 ),2021,(04):551～ 556 [11] 韋凌云 ,柴躍廷 ,趙玫 .不等式約束的非線性規(guī)劃混合遺傳算法 [J].計算機(jī)工程與應(yīng)用 ,2021,(22):46～ 49 [12] 劉淳安 ,王宇平 .解非線性規(guī)劃問題的非參數(shù)罰函數(shù)多目標(biāo)正交遺傳算法 [J].運籌與管理 ,2021,(05):35～ 38 [13] 朱國會 ,沈渝路 .求解一類非線性規(guī)劃問題的新途徑 [J].長春工業(yè)大學(xué)學(xué)報 (自然科學(xué)版 ),2021,(04):64～ 66 [14] 唐加福 ,汪定偉 .一種求解非線性規(guī)劃問題的改進(jìn)遺傳算法 [J].東北大學(xué)學(xué)報 (自然科學(xué)版 ),1997,(05):490～ 493 [15] 唐加福 ,汪定偉 ,許寶棟 ,李露 .基于評價函數(shù)的遺傳算法求解非線性規(guī)劃問題 [J].控制與決策 ,2021,(05):。對他們也表示我衷心的感謝！ 還要感謝我的 爸爸媽媽， 幾十年的 養(yǎng)育之恩 我 無以回報， 在這里祝愿 你們 永遠(yuǎn)健康快樂。 還要感謝我的學(xué)長和組員，他們在畢業(yè)設(shè)計的過程中給了我很多啟發(fā)和幫助。導(dǎo)師嚴(yán)謹(jǐn)求實和一絲不茍的學(xué)風(fēng)、扎實勤勉和孜孜不倦的工作態(tài)度時刻激勵著我努力學(xué)習(xí)，并將鞭策我在未來的工作中銳意進(jìn)取、奮發(fā)努力。 首先，我要衷心地感謝導(dǎo)師厙向陽教 授幾年來在學(xué)習(xí)和生活中給予的諄諄教誨和悉心的關(guān)懷。 29 致 謝 在論文完成之際，我的心情萬分激動。同時我們也看到，有時候傳統(tǒng)算法所得結(jié)果比遺傳算法要好，這說明傳統(tǒng)算法也有其可取之處，遺傳算法無法完全取代傳統(tǒng)算法。但遺傳算法程序設(shè)計復(fù)雜，算 法耗費大量存儲空間和運行時間。通過比較兩種算法的實際運行結(jié)果，分析兩者之間的性能差異。 在 充分理解遺傳算法基本理論，算法思想，關(guān)鍵技術(shù)的基礎(chǔ)上，結(jié)合實際情況，設(shè)計并最終實現(xiàn)了 求解非線性規(guī)劃問題的遺傳算法 。 詳細(xì)介紹了遺傳算法的優(yōu)點：簡單，通用，魯棒性強(qiáng)，不要求目標(biāo)函數(shù)可導(dǎo)，是一種全局搜索算法。 下圖即為 求解非線性規(guī)劃問題的遺傳算法最優(yōu) 適值 變化曲線： 27 圖 64 求解非線性規(guī)劃問題的遺傳算法最優(yōu) 適 值變化曲線 28 7 總 結(jié) 本文詳細(xì)介紹了 非線性規(guī)劃、 外點 罰函數(shù) 法、 遺傳算法的基本理論。 同時 我們比較兩種算法的運行時間，如下表。 這充分體現(xiàn)了遺傳算法的優(yōu)越性，遺傳算法的全局搜索能力使其能夠不受初始點的影響而找到近似全局最優(yōu)解。 表 62 均值和方差表 遺傳算法 懲罰函數(shù)法 種群 300 種群 200 初始懲罰因子 M=10 初始懲罰因子 M=1 最大值 最小值 均 值 方 差 我們將表 61 中的數(shù)據(jù)以圖的形式進(jìn)行表示，得到兩種算法取得最優(yōu)適應(yīng)度值的變化曲線，如下圖所示。 表 61 最優(yōu) 適 值 表 遺傳算法 懲罰函數(shù)法 執(zhí)行 序號 種群 300 種群 200 初始懲罰因子 M=10 初始懲罰因子 M=1 1 2 3 4 5 6 7 8 9 10 25 我們統(tǒng)計兩種算法之間的最大值、最小值、均值和方差。 我們通過統(tǒng)計兩種算法所得 最優(yōu)值的變化，來比較兩種算法的 收斂 效果。 結(jié)果 比較 為了能 直觀地表現(xiàn)兩種算法的實際執(zhí)行結(jié)果，我們將兩種算法的執(zhí)行結(jié)果以圖表 的形式直觀地表達(dá)出來。 24 6 算法的 結(jié)果 分析 概述 在以上算法分析設(shè)計的基礎(chǔ)上，我們用 MATLAB 語言分別實現(xiàn)了求解非線性規(guī)劃問題的遺傳算法和 外點 罰函數(shù)法 。 ② 從第一條染色體起，將當(dāng)前種群中各染色體的選擇概率進(jìn)行累加，當(dāng)選擇概率總和大于等于 rand 時停止。我們采用 轉(zhuǎn)輪法 （ Roulette Wheel） 來選擇染色體。 （ 5） 選擇函數(shù)。因為我們所求是最小化問題，在龐大的種群和多次迭代過程中為方便找出局部最小值和全局最優(yōu)值，我們可以對每次結(jié)果進(jìn)行排序。 ceil()是向正無窮大舍入，如 ceil()=3，配合 rand 函數(shù)可以隨機(jī)生成一定范圍內(nèi)的整數(shù)。程序中計算累積概 率部分，可以使用循環(huán)運算實現(xiàn)，但我們使用 MATLAB 中更便捷的函數(shù) cumsum 直接計算元素累加，如 a=[1 2 3 4]，則 cumsum(a)=[1 3 6 10]。 rand函數(shù)的作用是生成 0～ 1 之間的浮點型矩陣，通過對函數(shù)的簡單運算可以生成我們想要的確定范圍內(nèi)的矩陣。程序中多處涉及到隨機(jī)數(shù)的生成，像一開始初始種群的生成，后面的選擇、交叉、變異的循環(huán)條件判斷，都有用到。 （ 14）輸出最小適值 Min，即為所求全局最優(yōu)。滿足轉(zhuǎn)（ 13），不滿足轉(zhuǎn) （ 3） ，繼續(xù)迭代。 （ 11）更新種群 ， 將 A3 賦給 A。 （ 10） 均勻變異實現(xiàn)變異過程。 （ 9） 雙點交叉實現(xiàn)交叉運算 。 （ 8） 用轉(zhuǎn)輪法進(jìn)行選擇運算 。 （ 6）輸出每次迭代 t 對應(yīng)的 局部極值位置 B 和局部最優(yōu)值 s(1)。 （ 4）對 適值 e 從小到大排序，排序后的適值 記為 s， 并記錄變動情況 l。 （ 2）根據(jù)所給 x 的范圍，種群大小，染色體長度，隨機(jī)生成符合條件的初始種群 A。 求解非線性規(guī)劃問題的遺傳算法 程序設(shè)計 算法過程描述 由前面 遺傳算法的算法描述再結(jié)合本次畢業(yè)設(shè)計的實際情況，我們設(shè)計了以下的具體算法流程 [3][9][16]。為保證遺傳算法能獲得近似最優(yōu)解， T 取值為 150。這里由于是對每個基因座 進(jìn)行變異操作，為了保證變異效果， Pm取值較大，為 。變異操作是為了保證遺傳算法具有局部搜索能力， 同時也能保證群體多樣性，抑制早熟現(xiàn)象。我們?yōu)榱双@得較大的種群多樣性，產(chǎn)生較多的新個體， Pc 值取為 。交叉操作是遺傳算法中產(chǎn)生新個體的主要方法。一般 根據(jù)問題規(guī)模而定，這里 我們?nèi)?300。 種群 大小 pop_size 表示種群 中所含個體的數(shù)量。本文中有 7個決策變量，因 此染色體長度，也就是編碼長度取 7。 遺傳算子運行參數(shù)設(shè)計 （ 1）編碼長度。 例如：對染色體 Chromosome=[1， 2， 3， 4， 5]進(jìn)行變異，從 1 號位基因開始，每次隨機(jī)產(chǎn)生一個隨機(jī)數(shù) x，若這個隨機(jī)數(shù) xPm，則進(jìn)行變異，在指定范圍內(nèi)隨機(jī)產(chǎn)生一個實數(shù) ，來替換掉 1 號基因位的值；若 xPm，則本次不進(jìn)行變異，繼續(xù)對 2 號位基因值進(jìn)行變異操作，直到 5 號位結(jié)束。 變異算子設(shè)計 由于染色體基因較少，我們采用均勻變異：對每一個基因以一個指定的變異概率進(jìn)行變異，若符合變異條件，則用一個隨機(jī)產(chǎn)生的值替換原有的基因值。 例如：現(xiàn)在依據(jù)選擇算子選擇了兩條配對染色體： Chromosome1=[1， 2， 3， 4， 5]，Chromosome2=[6， 7， 8， 9， 10]。令雙親為],...,[ 21 nxxxX ? 和 ],...,[ 21 nyyyY ? ，隨機(jī)生成 1 到 n 之間的兩個數(shù) i 和 j，若兩數(shù)不相等，則可作為交叉點。常用的交叉有單點交叉，雙點、多點交叉等。轉(zhuǎn)輪法由以下步驟構(gòu)成： （ 1）對各個染色體 kv 計算適值 ? ?kveval ? ?kveval = ??xf ； k=1,2,… ,pop_size （ ） （ 2）計算種群中所有染色體的適值 和 ? ???? sizepopk kvevalF _1 （ ） （ 3）對各染色體 kv ，計算選擇概率 kp ? ?Fvevalp kk ? ； k=1,2,… ,pop_size （ ） （ 4）對各染色體 kv ，計算累積概率 kq ??? kj jk pq 1 ； k=1,2,… ,pop_size （ ） 20 選擇過程就是旋轉(zhuǎn)轉(zhuǎn)輪 pop_size 次，每次按如下方式選出一個染色體來構(gòu)造新的種群： 選擇步驟： 步驟一：在 [0,1]區(qū)間內(nèi)產(chǎn)生一個均勻分布的偽隨機(jī)數(shù) r； 步驟二：若 1qr? ，則選第一個染色體 1v ；否則，選擇第 k 個染色體 kv（ )_2 sizepopk ?? ），使得 kk qrq ???1 成立。 多數(shù)情況下采用 轉(zhuǎn)輪法作為 選擇方法。我們采用最常見的比例選擇算子，這是一種回放式隨機(jī)采樣的方法。 然后再 根據(jù)公式 （ ） ， 將 懲罰函數(shù) ??xp加入目標(biāo)函數(shù) ??xf ，也就是將 約束條件加入目標(biāo)函數(shù)，確定適應(yīng)度函數(shù) ??xeval [3][8]。當(dāng) ??xg 滿足約束時， 大于等于 0，此時括號里的結(jié)果為 0， ??xp也為 0， 即不對其進(jìn)行懲罰。 本文中選擇的懲罰函數(shù)為： ??xp =1*( ??xg 0).* ??xg *1e+3。 對于極小化問題，則取 ? ?? ???? ?? ，其他 可行，若 0 x0xpxp （ ） 另一種方法是采用乘法形式： ? ? ? ? ? ?xpxfxeval ? （ ） 19 這時，極大化問題可取為 ? ? ? ???? ?? ? ，其他 可行，若 10 x1xpxp （ ） 求極小化問題則取 ? ?? ???? ?? ，其他 可行，若 1 x1xpxp （ ） 本文中我們采用的是加法形式的懲罰。對于極大化問題，取 ? ?? ???? ?? ，其他 可行，若 0 x0xpxp （ ） 令 ? ?maxxp和 ? ?minxf分別為現(xiàn)行種群中的 ??xp 的最大值和 ??xf 的最小值。 懲罰技術(shù)通過懲罰不可行解將約束問題轉(zhuǎn)化為無約束問題。不可行染色體和解空間可行部分的關(guān)系在懲罰不可行染色體中起了關(guān)鍵作用：不可行染色體的懲罰值相應(yīng)于某種測試下的不可行性的“測量”。然而，我們對最優(yōu)點沒有任何先驗知識，所以一般很難判斷哪一點更好。我們希望給 b 較小懲罰。我們不能對這些子空間作任何假設(shè)，特別是當(dāng)它們是非凸或非連通時，如圖 51 所示。在遺傳算法中，懲罰技術(shù)用來在每代的 種群中保持部分不可行解，使遺傳搜索可以從可行域和不可行域兩邊來達(dá)到最優(yōu)解。 2）懲罰函數(shù) 懲罰函數(shù)大概是用遺傳算法解約束優(yōu)化問題中最常用的技術(shù)。 Glover 和 Greenberg 建議的約束管理技術(shù)允許在搜索空間里的不可行 域中進(jìn)行搜索，這比將搜索限制在可行域內(nèi)的方法能更快地活的最優(yōu)解或獲得更好的最終解。對于約束嚴(yán)的問題，不可行解在種群中的比例很大。但是，該方法的遺傳搜索收到了可行域的限制。 Michalewicz 等指出這種方法通常比基于懲罰的遺傳算法更可靠。Michalewicz 等則認(rèn)為對有非線性約束的優(yōu)化問題， 15%的替代率為最好。 Liepins 等采用永不替代法，即不讓修復(fù)過的染色體進(jìn)入種群；而 Nakano 和 Yamada 采用了始終替代法。對于某些問題，修復(fù)過程甚至比原問題的求解更復(fù)雜。 修復(fù)策略取決于是否存在一個可將不可行后代轉(zhuǎn)化為可行的修復(fù)程序。 對于許多組合優(yōu)化問題，構(gòu)造修復(fù)程序相對比較容易。對于某些系統(tǒng)（特別是可行搜索空間非凸時），允許跨過不可行域修復(fù)往往更容易達(dá)到最優(yōu)解。然而，這是很嚴(yán)格的限制。這是遺傳算法中普遍的作法。 適應(yīng)度函數(shù)設(shè)計 1）滿足約束 由于對染色體作遺傳運算時通常獲得不可行的后代，因此運用遺傳算法解非線性規(guī)劃問題的核心問題是如何滿足約束的問題。