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