【正文】 ，在保證一定指標(biāo)要求的前提下，使總耗費最??；如何安排庫存儲量，既能保證供應(yīng)，又使儲存費用最低；如何組織貨源，既能滿足顧客需要，又使資金周轉(zhuǎn)最快等。 ② 制約函數(shù)法 ：又稱系列無約束最小化方法，簡稱 SUMT 法 。這是早期的解析法，收斂速度較慢。 無約束最優(yōu)化方法 大多是逐次一維搜索的迭代算法。 ② 切線法 ，又稱牛頓法。如果 ? ?*xf 優(yōu)于一切可行解處的目標(biāo)函數(shù)值 ， 則稱 x*為問題的整體最優(yōu)解（簡稱整體解）。建立數(shù)學(xué)模型首先要選定適當(dāng)?shù)哪繕?biāo)變量和決策變量 ， 并建立起目標(biāo)變量與決策變量之間的函數(shù)關(guān)系 ， 稱之為 目標(biāo)函數(shù) 。 而遺傳算法是一種魯棒性很強的 種全局搜索算法，理論上可以克服傳統(tǒng) 非線性規(guī)劃 算法的缺陷。在非線性規(guī)劃理論研究的 基礎(chǔ)上，人們?nèi)找嬷匾暦蔷€性規(guī)劃問題求解方法的研究。 Geic Algorithm。 傳統(tǒng)的解決非線性規(guī)劃問題的方法，如 梯度法、罰函數(shù)法、拉格朗日乘子法 等， 穩(wěn)定性差， 對函數(shù)初值和函數(shù)性態(tài)要求較高， 且容易陷入局部最優(yōu)解 。與傳統(tǒng)的非線性規(guī)劃算法 —— 外點罰函數(shù)法的比較結(jié)果表明該算法在一定程度上有效地克服了傳統(tǒng)的非線性規(guī)劃算法 穩(wěn)定性差， 對函數(shù)初值和函數(shù)性態(tài)要求較高， 且容易陷入局部最優(yōu)解 的缺陷，收斂更合理，性能更穩(wěn)定。 50 年代末到 60 年代末出現(xiàn)了許多解非線性規(guī)劃問題的有效的算法 ， 70 年代又得到進一步的發(fā)展。 遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域 ， 對問題的種類有很強的魯棒性，所以廣泛應(yīng)用于很多領(lǐng)域，如函數(shù)優(yōu)化 、 組合優(yōu)化 、生產(chǎn)調(diào)度問題 、 自動控制 、 機器人智能控制 、 圖像處理，人工生命 、 遺傳編程 、 機器學(xué)習(xí)等。非線性規(guī)劃研究一個 n 元實函數(shù)在一組等式或不等式的約束條件下的極值問題，且目標(biāo)函數(shù)和約束條件至少有一個是未知量的非線性函數(shù)。 定義域 D 中滿足約束條件的點稱為問題的可行解。 ① 黃金分割法 ，又稱 法。 此外，還有斐波那契法、割線法、有理插值法、分批搜索法等。然后對新點施行同樣手續(xù) ， 如此反復(fù)迭代，直到滿足預(yù)定的精度要求為止。 屬于直接型的算法有交替方向法（又稱坐標(biāo)輪換法）、模式搜索法、旋 轉(zhuǎn)方向法、鮑威爾共軛方向法和單純形加速法等。 ④ 近似型算法 ：這類算法包括序貫線性規(guī)劃法和 序貫 二次規(guī)劃法。 外 點 罰函數(shù)法是從非可行解出發(fā)逐漸移動到可行區(qū)域的方法。但是研究 DX? 時， ),( kMXF 的最優(yōu)解不是我們所需要的。 算法性能分析 通過長期的理論研究和實驗結(jié)果，人們總結(jié)出懲罰函數(shù)的優(yōu)點有： （ 1） 罰函數(shù)法 是解決非線性規(guī)劃問題的一種經(jīng)典算法，這種算法簡單易行、熟練數(shù)度快，在很多實際問題的求解中得到了應(yīng)用 。 8 外點 罰函數(shù) 法的程序設(shè)計 為 了能和 求解非線性規(guī)劃問題的遺傳算法 進行比較，我們同時實現(xiàn)最經(jīng)典的，也是得到最廣泛應(yīng)用的 傳統(tǒng)的非線性規(guī)劃算法 —— 外點罰函數(shù) 法，通過對二者的結(jié)果，比較二者性能的差別。 9 圖 31 外點罰函數(shù)法 程序流程圖 10 4 遺傳 算法 遺傳算法概述 遺傳算法的生物學(xué)基礎(chǔ) 遺傳算法的生物學(xué)基礎(chǔ)是達爾文的自然選擇學(xué)說。種群中的每個個體是問題的一個解，稱為“染色體”。這樣，經(jīng)過若干代之后，算法收斂于最好的染色體，它很可能就是問題的最優(yōu)解或者次優(yōu)解。 （ 3） 遺傳算法使用多個點的搜索信息，具有隱含并行性。實踐證明，遺傳算法對于組合優(yōu)化中的 NP 完全問題非常有效。 （ 6）圖像處理。 Koza 發(fā)展了遺傳編程的概念，他使用了以 LISP 語言所表示的編碼方法，基于對一種樹型結(jié)構(gòu)所進行的遺傳操作來自動生成計算機程序。它所使用的是決策變量的真實值。 （ 3）根據(jù)最優(yōu)化問題的類型，由目標(biāo)函數(shù)值按一定的轉(zhuǎn)換規(guī)則求出個體的適應(yīng)度。 （ 3）排序選擇：對群體中的所有個體按其適應(yīng)度大小進行排序，基于這個排序來分配各個個體被選中的概率。 變異算子 遺傳算法中的變異運算是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個新的個體。 遺傳算法的運行參數(shù) （ 1）編碼串長度 L。建議取值范圍是 ～ 。 而遺傳算法是一種全局搜索算法，可以克服傳統(tǒng)的非線性規(guī)劃算法 容易陷入局部最優(yōu)解的缺陷。如果采用固定長度的二進制編碼，不僅會造成存儲空間的極大浪費，而且在進行交叉和變異等遺傳操作時，由于實際值不等長而很難確定交叉點和變異點，而且很容易產(chǎn)生無效解，降低了算法的效率；如果采用不定長二進制編碼，則在進行交叉和變異等遺傳操作時很難確定交叉點和變異點，而且容易產(chǎn)生無效解。然而，這是很嚴(yán)格的限制。對于某些問題，修復(fù)過程甚至比原問題的求解更復(fù)雜。但是，該方法的遺傳搜索收到了可行域的限制。在遺傳算法中，懲罰技術(shù)用來在每代的 種群中保持部分不可行解，使遺傳搜索可以從可行域和不可行域兩邊來達到最優(yōu)解。不可行染色體和解空間可行部分的關(guān)系在懲罰不可行染色體中起了關(guān)鍵作用：不可行染色體的懲罰值相應(yīng)于某種測試下的不可行性的“測量”。 本文中選擇的懲罰函數(shù)為： ??xp =1*( ??xg 0).* ??xg *1e+3。 多數(shù)情況下采用 轉(zhuǎn)輪法作為 選擇方法。 例如：現(xiàn)在依據(jù)選擇算子選擇了兩條配對染色體： Chromosome1=[1， 2， 3， 4， 5]，Chromosome2=[6， 7， 8， 9， 10]。本文中有 7個決策變量，因 此染色體長度，也就是編碼長度取 7。我們?yōu)榱双@得較大的種群多樣性，產(chǎn)生較多的新個體， Pc 值取為 。 求解非線性規(guī)劃問題的遺傳算法 程序設(shè)計 算法過程描述 由前面 遺傳算法的算法描述再結(jié)合本次畢業(yè)設(shè)計的實際情況，我們設(shè)計了以下的具體算法流程 [3][9][16]。 （ 8） 用轉(zhuǎn)輪法進行選擇運算 。滿足轉(zhuǎn)（ 13），不滿足轉(zhuǎn) （ 3） ，繼續(xù)迭代。程序中計算累積概 率部分，可以使用循環(huán)運算實現(xiàn)，但我們使用 MATLAB 中更便捷的函數(shù) cumsum 直接計算元素累加，如 a=[1 2 3 4]，則 cumsum(a)=[1 3 6 10]。我們采用 轉(zhuǎn)輪法 （ Roulette Wheel） 來選擇染色體。 我們通過統(tǒng)計兩種算法所得 最優(yōu)值的變化，來比較兩種算法的 收斂 效果。 同時 我們比較兩種算法的運行時間，如下表。通過比較兩種算法的實際運行結(jié)果，分析兩者之間的性能差異。 首先，我要衷心地感謝導(dǎo)師厙向陽教 授幾年來在學(xué)習(xí)和生活中給予的諄諄教誨和悉心的關(guān)懷。 謝謝！ 30 參考文獻 [1] 汪定偉 ,王俊偉 ,王洪峰 ,張瑞友等編著 .智能優(yōu)化方法 [M].北京 :高等教育出版 社 ,～ 57 [2] 李敏強 ,寇紀(jì)淞 ,林丹等 .遺傳算法的基本理論與應(yīng)用 [M].北京 :科學(xué)出版社 ,～112 [3] [日 ]玄光男 ,程潤偉著 .遺傳算法與工程設(shè)計 [M].汪定偉 ,唐加福 ,黃敏譯 .北京 :科學(xué)出版社 ,～ 40 [4] 運籌學(xué)編寫組編 .運籌學(xué) [M].北京 :清華大學(xué)出版社 ,～ 189 [5] 葉家成 ,彭宏 .解全局優(yōu)化問題的遺傳算法的一些新進展 .吉首大學(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] 楊曉華 ,楊志峰 ,酈建強 .解非線性優(yōu)化問題的混合加速遺傳算法 [J].北京師范大學(xué)學(xué)報(自然科學(xué)版 ),2021,(04):551～ 556 [11] 韋凌云 ,柴躍廷 ,趙玫 .不等式約束的非線性規(guī)劃混合遺傳算法 [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].東北大學(xué)學(xué)報 (自然科學(xué)版 ),1997,(05):490～ 493 [15] 唐加福 ,汪定偉 ,許寶棟 ,李露 .基于評價函數(shù)的遺傳算法求解非線性規(guī)劃問題 [J].控制與決策 ,2021,(05):。導(dǎo)師嚴(yán)謹(jǐn)求實和一絲不茍的學(xué)風(fēng)、扎實勤勉和孜孜不倦的工作態(tài)度時刻激勵著我努力學(xué)習(xí)，并將鞭策我在未來的工作中銳意進取、奮發(fā)努力。但遺傳算法程序設(shè)計復(fù)雜，算 法耗費大量存儲空間和運行時間。 下圖即為 求解非線性規(guī)劃問題的遺傳算法最優(yōu) 適值 變化曲線： 27 圖 64 求解非線性規(guī)劃問題的遺傳算法最優(yōu) 適 值變化曲線 28 7 總 結(jié) 本文詳細介紹了 非線性規(guī)劃、 外點 罰函數(shù) 法、 遺傳算法的基本理論。 表 61 最優(yōu) 適 值 表 遺傳算法 懲罰函數(shù)法 執(zhí)行 序號 種群 300 種群 200 初始懲罰因子 M=10 初始懲罰因子 M=1 1 2 3 4 5 6 7 8 9 10 25 我們統(tǒng)計兩種算法之間的最大值、最小值、均值和方差。 ② 從第一條染色體起，將當(dāng)前種群中各染色體的選擇概率進行累加，當(dāng)選擇概率總和大于等于 rand 時停止。 ceil()是向正無窮大舍入，如 ceil()=3，配合 rand 函數(shù)可以隨機生成一定范圍內(nèi)的整數(shù)。 （ 14）輸出最小適值 Min，即為所求全局最優(yōu)。 （ 9） 雙點交叉實現(xiàn)交叉運算 。 （ 2）根據(jù)所給 x 的范圍，種群大小，染色體長度，隨機生成符合條件的初始種群 A。變異操作是為了保證遺傳算法具有局部搜索能力， 同時也能保證群體多樣性，抑制早熟現(xiàn)象。 種群 大小 pop_size 表示種群 中所含個體的數(shù)量。 變異算子設(shè)計 由于染色體基因較少，我們采用均勻變異：對每一個基因以一個指定的變異概率進行變異，若符合變異條件，則用一個隨機產(chǎn)生的值替換原有的基因值。轉(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)生一個均勻分布的偽隨機數(shù) r； 步驟二：若 1qr? ，則選第一個染色體 1v ；否則，選擇第 k 個染色體 kv（ )_2 sizepopk ?? ），使得 kk qrq ???1 成立。當(dāng) ??xg 滿足約束時， 大于等于 0，此時括號里的結(jié)果為 0， ??xp也為 0， 即不對其進行懲罰。 懲罰技術(shù)通過懲罰不可行解將約束問題轉(zhuǎn)化為無約束問題。我們不能對這些子空間作任何假設(shè)，特別是當(dāng)它們是非凸或非連通時，如圖 51 所示。對于約束嚴(yán)的問題，不可行解在種群中的比例很大。 Liepins 等采用永不替代法，即不讓修復(fù)過的染色體進入種群；而 Nakano 和 Yamada 采用了始終替代法。對于某些系統(tǒng)（特別是可行搜索空間非凸時），允許跨過不可行域修復(fù)往往更容易達到最優(yōu)解。所以我們直接采用實數(shù)編碼，即染色體基因串中基因座的值直接是 每組解中各 分量 ix 的實數(shù)值，不再對其進行其他任何形式的編碼。本章就是介紹遺傳算法在非線性規(guī)劃中的具體應(yīng)用，設(shè)計并實現(xiàn)求解非線性規(guī)劃問題的遺傳算法。 Pm取值過大，雖然能夠產(chǎn)生較多的新個體，但也可能破壞掉很多較好的模式，使得遺傳算法的性能近似于隨機搜索算法的性能；若 Pm 過小，則變異操作產(chǎn)生新個體的能力和抑制早熟現(xiàn)象的能力就會較差。 （ 2）群體大小 pop_size。二是使遺傳算法可維持群體多樣性，以防止出現(xiàn)未成熟收斂現(xiàn)象。它是產(chǎn)生新個體的主要方法。遺傳算法中的選擇操作就是確定如何 從父代群體中按某種方法選取哪些個體遺傳到下一代群體中的一種遺傳運算。這個符號集可以是一個字母表，如 {A,B,C,D,…} ；也可以是一個數(shù)字序號表，如