【正文】 在論文的選題、研究以及撰寫(xiě)過(guò)程中，自始至終得到了導(dǎo)師的精心指導(dǎo)和熱情幫助，其中無(wú)不凝聚著導(dǎo)師的心血和汗水。 表 63 運(yùn)行時(shí)間比較 表 遺傳算法 懲罰函數(shù)法 種群 300 種群 200 初始懲罰因子 M=10 初始懲罰因子 M=1 最大值 最小值 均 值 從表中可以看出，懲罰函數(shù)法在運(yùn)行時(shí)間上明顯優(yōu)于遺傳算法，說(shuō) 明 傳統(tǒng)算法也有其 可取 優(yōu)勢(shì)，不可能被完全取代。具體過(guò)程如下： ① 利用 rand 函數(shù)產(chǎn)生一個(gè) 0～ 1 之間的隨機(jī)數(shù) r。 （ 13） 對(duì)每代最小適值 M 排序， me 為排序后的向量。步驟如下： （ 1）初始化遺傳算法的運(yùn)行參數(shù)：種群大小 pop_size，每條染色體基因串長(zhǎng)度 length，交叉概率 Pc，變異概率 Pm，算法迭代次數(shù) T，當(dāng)前迭代次數(shù) t。 （ 2） 種群 大小 pop_size。 它是一種 正比選擇策略，能夠根據(jù)與適值成正比的概率選擇出新的種群。設(shè)計(jì)懲罰函數(shù)沒(méi)有一般規(guī)則，這仍要依賴(lài)于待解的問(wèn)題。 （ 4）懲罰策略 上面三種策略的 共同優(yōu)點(diǎn)是都不會(huì)產(chǎn)生不可行解，缺點(diǎn)則是無(wú)法考慮可行域外的點(diǎn)。例如，對(duì)許多約束優(yōu)化問(wèn)題初始種群可能全由非可行染色體構(gòu)成，這就需要對(duì)他們進(jìn)行修補(bǔ)。因此，將遺傳算法應(yīng)用于非線性規(guī)劃，是改善收斂效果，提高最優(yōu)化質(zhì)量的有效途徑。使用二進(jìn)制編碼時(shí)， L 與問(wèn)題所要求的求解精度有關(guān)；使用浮點(diǎn)數(shù)編碼時(shí)， L 與決策變量的個(gè)數(shù) n 相等；使用符號(hào)編碼是， L 由問(wèn)題的編碼方式確定。 交叉算子 遺傳算法中的交叉運(yùn)算是指對(duì)兩個(gè)相互配對(duì)的染色體按某種方式相互交換其部分基因， 從而形成兩個(gè)新的個(gè)體。 （ 3） 符號(hào)編碼：個(gè)體染色體編碼串中的基因值取自一個(gè)無(wú)數(shù)值含義、而只有代碼含義的符號(hào)集。在圖像處理過(guò)程中，不可避免地會(huì)產(chǎn)生一些誤差，這些誤差會(huì)影響圖像處理的效果。 （ 4） 遺傳算法使用概率搜索技術(shù)，而非確定性規(guī)則。染色體是一串符號(hào)，比如一個(gè)二進(jìn)制字符串。 程序步驟 對(duì)于問(wèn)題 （ ） ，構(gòu)造一函數(shù)為 )()(),( XMXfMXF kk ??? （ ） 其中，懲罰函數(shù) )(X? 按照式 （ ） 構(gòu)造，給定終止限 ? （ 可取 610??? ）。為此規(guī)定，當(dāng) DX? 時(shí)， ),( kMXF 在 X 點(diǎn)處的函數(shù)值迅速變大，換而言之，可行域外的任一點(diǎn) X 處的函數(shù)值 ),( kMXF 都相當(dāng)大。前者將原問(wèn)題化為一系列線性規(guī)劃問(wèn)題求解，后者將原問(wèn)題化為一系列二次規(guī)劃問(wèn)題求解。根據(jù)搜索方向的取法不同 ， 可以有各種算法。它適用于單峰函數(shù)。目標(biāo)函數(shù)和約束條件都是線性函數(shù)的情形則屬于 線性規(guī)劃 。 非線性規(guī)劃在工程、管理、經(jīng)濟(jì)、科研、軍事等方面都有廣泛的應(yīng)用，為最優(yōu)化設(shè)計(jì)提供了有力的工具。 摘 要 非線性規(guī)劃在工程、管理、經(jīng)濟(jì)、科研、軍事等方面都有廣泛的應(yīng)用。 隨著計(jì)算機(jī)的產(chǎn)生與發(fā)展，非線性規(guī)劃作為一門(mén)獨(dú)立的學(xué)科越來(lái)越受到人們的重視。 非線性 規(guī)劃的數(shù)學(xué)模型 對(duì)實(shí)際 規(guī)劃問(wèn)題 作 定量分析 ，必須建立 數(shù)學(xué)模型 。其基本思想是：在初始尋查區(qū)間中設(shè)計(jì)一列點(diǎn)，通過(guò)逐次比較其函數(shù)值，逐步縮小尋查區(qū)間，以得出近似最優(yōu)值點(diǎn)。 屬于解析型的算法有： ① 梯度法 ：又稱(chēng)最速下降法。 非線性規(guī)劃的應(yīng)用 在 經(jīng)營(yíng)管理 、 工程設(shè)計(jì) 、 科學(xué)研究 、 軍事指揮 等方面普遍地存在著最優(yōu)化問(wèn)題。此時(shí)要求 ),( kMXF 在 nR 中的最優(yōu)解，只能讓點(diǎn) X 回到 D 內(nèi)才 有 可能，然而一旦點(diǎn) X 回到 D 內(nèi)，即 DX? ，此時(shí) ),( kMXF就與問(wèn)題 （ ） 有相同的最優(yōu)解。 具體過(guò) 程描述如下： （ 1） 選定初始點(diǎn) 0X ， 初始懲罰因子 01?M （ 可取 11?M ） 。這些染色體在后續(xù)迭代中不斷進(jìn)化，稱(chēng)為遺傳。 遺傳算法的應(yīng)用 遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架，它不依賴(lài)于問(wèn)題的具體領(lǐng)域，對(duì)問(wèn)題的種類(lèi)有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科。如何使這些誤差最小是使計(jì)算機(jī)視覺(jué)達(dá)到實(shí)用化的重要要求。這個(gè)符號(hào)集可以是一個(gè)字母表，如 {A,B,C,D,…} ；也可以是一個(gè)數(shù)字序號(hào)表，如 {1， 2， 3， 4， 5， …} ；還可以是一個(gè)代碼表，如 {A1,A2,A3,A4,…} 等等。它是產(chǎn)生新個(gè)體的主要方法。 （ 2）群體大小 pop_size。本章就是介紹遺傳算法在非線性規(guī)劃中的具體應(yīng)用，設(shè)計(jì)并實(shí)現(xiàn)求解非線性規(guī)劃問(wèn)題的遺傳算法。對(duì)于某些系統(tǒng)（特別是可行搜索空間非凸時(shí)），允許跨過(guò)不可行域修復(fù)往往更容易達(dá)到最優(yōu)解。對(duì)于約束嚴(yán)的問(wèn)題，不可行解在種群中的比例很大。 懲罰技術(shù)通過(guò)懲罰不可行解將約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wè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 成立。 種群 大小 pop_size 表示種群 中所含個(gè)體的數(shù)量。 （ 2）根據(jù)所給 x 的范圍，種群大小，染色體長(zhǎng)度，隨機(jī)生成符合條件的初始種群 A。 （ 14）輸出最小適值 Min，即為所求全局最優(yōu)。 ② 從第一條染色體起，將當(dāng)前種群中各染色體的選擇概率進(jìn)行累加，當(dāng)選擇概率總和大于等于 rand 時(shí)停止。 下圖即為 求解非線性規(guī)劃問(wèn)題的遺傳算法最優(yōu) 適值 變化曲線： 27 圖 64 求解非線性規(guī)劃問(wèn)題的遺傳算法最優(yōu) 適 值變化曲線 28 7 總 結(jié) 本文詳細(xì)介紹了 非線性規(guī)劃、 外點(diǎn) 罰函數(shù) 法、 遺傳算法的基本理論。導(dǎo)師嚴(yán)謹(jǐn)求實(shí)和一絲不茍的學(xué)風(fēng)、扎實(shí)勤勉和孜孜不倦的工作態(tài)度時(shí)刻激勵(lì)著我努力學(xué)習(xí)，并將鞭策我在未來(lái)的工作中銳意進(jìn)取、奮發(fā)努力。 首先，我要衷心地感謝導(dǎo)師厙向陽(yáng)教 授幾年來(lái)在學(xué)習(xí)和生活中給予的諄諄教誨和悉心的關(guān)懷。 同時(shí) 我們比較兩種算法的運(yùn)行時(shí)間，如下表。我們采用 轉(zhuǎn)輪法 （ Roulette Wheel） 來(lái)選擇染色體。滿足轉(zhuǎn)（ 13），不滿足轉(zhuǎn) （ 3） ，繼續(xù)迭代。 求解非線性規(guī)劃問(wèn)題的遺傳算法 程序設(shè)計(jì) 算法過(guò)程描述 由前面 遺傳算法的算法描述再結(jié)合本次畢業(yè)設(shè)計(jì)的實(shí)際情況，我們?cè)O(shè)計(jì)了以下的具體算法流程 [3][9][16]。本文中有 7個(gè)決策變量，因 此染色體長(zhǎng)度，也就是編碼長(zhǎng)度取 7。 多數(shù)情況下采用 轉(zhuǎn)輪法作為 選擇方法。不可行染色體和解空間可行部分的關(guān)系在懲罰不可行染色體中起了關(guān)鍵作用：不可行染色體的懲罰值相應(yīng)于某種測(cè)試下的不可行性的“測(cè)量”。但是，該方法的遺傳搜索收到了可行域的限制。然而，這是很?chē)?yán)格的限制。 而遺傳算法是一種全局搜索算法，可以克服傳統(tǒng)的非線性規(guī)劃算法 容易陷入局部最優(yōu)解的缺陷。 遺傳算法的運(yùn)行參數(shù) （ 1）編碼串長(zhǎng)度 L。 （ 3）排序選擇：對(duì)群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行排序，基于這個(gè)排序來(lái)分配各個(gè)個(gè)體被選中的概率。它所使用的是決策變量的真實(shí)值。 （ 6）圖像處理。 （ 3） 遺傳算法使用多個(gè)點(diǎn)的搜索信息，具有隱含并行性。種群中的每個(gè)個(gè)體是問(wèn)題的一個(gè)解，稱(chēng)為“染色體”。 8 外點(diǎn) 罰函數(shù) 法的程序設(shè)計(jì) 為 了能和 求解非線性規(guī)劃問(wèn)題的遺傳算法 進(jìn)行比較，我們同時(shí)實(shí)現(xiàn)最經(jīng)典的，也是得到最廣泛應(yīng)用的 傳統(tǒng)的非線性規(guī)劃算法 —— 外點(diǎn)罰函數(shù) 法，通過(guò)對(duì)二者的結(jié)果，比較二者性能的差別。但是研究 DX? 時(shí)， ),( kMXF 的最優(yōu)解不是我們所需要的。 ④ 近似型算法 ：這類(lèi)算法包括序貫線性規(guī)劃法和 序貫 二次規(guī)劃法。然后對(duì)新點(diǎn)施行同樣手續(xù) ， 如此反復(fù)迭代，直到滿足預(yù)定的精度要求為止。 ① 黃金分割法 ，又稱(chēng) 法。非線性規(guī)劃研究一個(gè) n 元實(shí)函數(shù)在一組等式或不等式的約束條件下的極值問(wèn)題，且目標(biāo)函數(shù)和約束條件至少有一個(gè)是未知量的非線性函數(shù)。 50 年代末到 60 年代末出現(xiàn)了許多解非線性規(guī)劃問(wèn)題的有效的算法 ， 70 年代又得到進(jìn)一步的發(fā)展。 傳統(tǒng)的解決非線性規(guī)劃問(wèn)題的方法，如 梯度法、罰函數(shù)法、拉格朗日乘子法 等， 穩(wěn)定性差， 對(duì)函數(shù)初值和函數(shù)性態(tài)要求較高， 且容易陷入局部最優(yōu)解 。在非線性規(guī)劃理論研究的 基礎(chǔ)上，人們?nèi)找嬷匾暦蔷€性規(guī)劃問(wèn)題求解方法的研究。建立數(shù)學(xué)模型首先要選定適當(dāng)?shù)哪繕?biāo)變量和決策變量 ， 并建立起目標(biāo)變量與決策變量之間的函數(shù)關(guān)系 ， 稱(chēng)之為 目標(biāo)函數(shù) 。 ② 切線法 ，又稱(chēng)牛頓法。這是早期的解析法，收斂速度較慢。例如：如何在現(xiàn)有人力、物力、財(cái)力條件下合理安排產(chǎn)品生產(chǎn)，以取得最高的利潤(rùn)；如何設(shè)計(jì)某種產(chǎn)品，在滿足規(guī)格、性能要求的前提下，達(dá)到最低的成本；如何確定一個(gè)自動(dòng)控制系統(tǒng)的某些參數(shù)，使系統(tǒng)的工作狀態(tài)最佳；如何分配一個(gè)動(dòng)力系統(tǒng)中各電站的負(fù)荷，在保證一定指標(biāo)要求的前提下，使總耗費(fèi)最??；如何安排庫(kù)存儲(chǔ)量，既能保證供應(yīng)，又使儲(chǔ)存費(fèi)用最低；如何組織貨源，既能滿足顧客需要，又使資金周轉(zhuǎn)最快等。 當(dāng) DX? 時(shí)， ),( kMXF 迅速變大的原因是通過(guò)懲罰因子 kM 來(lái)實(shí)現(xiàn)。懲罰因子放大系數(shù) 10?C ，置 1?k 。在每一代中用“適值”來(lái)測(cè)量染色體的好壞。下面是遺傳算法的一些主要應(yīng)用領(lǐng)域 [2][5]： （ 1）函數(shù)優(yōu)化。目前遺傳算法已在模式識(shí)別、圖像恢復(fù)、圖像邊緣特征提取等方面得到了應(yīng)用。 適應(yīng)度函數(shù) 適應(yīng)度是度量群體中各個(gè)個(gè)體在優(yōu)化計(jì)算中有可能達(dá)到或接近于或有助于找到最優(yōu)解的優(yōu)良程度 [2]。 遺傳算法中，在交叉運(yùn)算之前必須對(duì)群體中的個(gè)體進(jìn)行配對(duì)。 pop_size 表示群體中所含個(gè)體的數(shù)量。 實(shí)用遺傳算法設(shè)計(jì) 編碼方法設(shè)計(jì) 非線性規(guī)劃 屬于最優(yōu)化設(shè)計(jì)的 一種， 屬于約束優(yōu)化問(wèn)題， 其最終目的是選擇一種方法，使目標(biāo)函數(shù) 在滿足約束的條件下 達(dá)到最優(yōu)。 （ 2）修復(fù)策略 修補(bǔ)染色體是對(duì)不可行染色體采用修復(fù)程序使之變?yōu)榭尚械?。這樣，將搜索限制在可行域內(nèi)就很難找到可行解。構(gòu)造帶有懲罰項(xiàng)的適應(yīng)度函數(shù)的方法一般有兩種 [3][9]用加法形式： ? ? ? ? ? ?xpxfxeva l ?? （ ） 其中， x 代表染色體； ??xf 是問(wèn)題的目標(biāo)函數(shù)； ??xp 是懲罰項(xiàng)。 交叉算子設(shè)計(jì) 雖然是實(shí)數(shù)編碼，不過(guò)也可以模仿 二進(jìn)制表達(dá)的交叉。 pop_size取值的大小與遺傳算法運(yùn)行速度， 種群 多樣性有關(guān)。 （ 3）將約束條件加入目標(biāo)函數(shù)，確定適應(yīng)度函數(shù) ，計(jì)算適值 e。 22 遺傳算法程序流程圖 23 圖 52 求解非線性規(guī)劃問(wèn)題的遺傳算法程序流程圖 遺傳算法中所設(shè)計(jì)的輔助算法的設(shè)計(jì) （ 1） 隨機(jī)數(shù)生成。 ③ 累加結(jié)束時(shí)的染色體（即概率之和剛好大于隨機(jī)數(shù) rand 的那條染色體）即為被選 中的染色體。分析了 傳統(tǒng)的非線性規(guī)劃算法 計(jì)算煩瑣且精度不高，穩(wěn)定性差， 對(duì)函數(shù)初值和函數(shù)性態(tài)要求較高，且容易陷入局部最優(yōu)解的缺陷 。導(dǎo)師的指導(dǎo)將使我終生受益。從論文的選題、資料的收集到論文的撰寫(xiě)編排整個(gè)過(guò)程中，我得到了許多的熱情幫助。 通過(guò)以上分析可以看出， 求解非線性規(guī)劃問(wèn)題的遺傳算法 能夠克服傳統(tǒng)算法對(duì)初始值敏感， 容易陷入局部最 優(yōu)解的缺陷， 收斂效果更好，性能更穩(wěn)定，結(jié)果更合理。選擇函數(shù)是為交叉操作從當(dāng)前種群中選擇兩條染色體來(lái)進(jìn)行交叉操作。 （ 12） 判斷是否滿足迭代結(jié)束條件。即遺傳算法迭代 150 次停止，將得到的最佳個(gè)體作為最優(yōu)解輸出。由于 我們采用實(shí)數(shù)編碼，即染色體基因串中基因座的值直接是每組解中各分量 ix 的實(shí)數(shù)值，每個(gè)染色體編碼為一個(gè)和解向量維數(shù)相同的實(shí)向量。其基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。 圖 51 解空間：可行域與不可行域 懲罰策略的主要問(wèn)題 是如何設(shè)計(jì)一個(gè)懲罰函數(shù) ??xp ，從而能有效地引導(dǎo)遺傳搜索達(dá)到解空間的最好區(qū)域。許多領(lǐng)域中的實(shí)際工作者采用專(zhuān)門(mén)的問(wèn)題表達(dá)方式和遺傳算子構(gòu)造了非常成功的遺傳算法，這已是一個(gè)普遍的趨勢(shì)。 17 當(dāng)可行的搜索空間是凸的，且 為整個(gè)搜索空間的適當(dāng)?shù)囊徊糠謺r(shí)，這種方法應(yīng)該是有效的。 16 5 求解非線性規(guī)劃問(wèn)題的遺傳算法 設(shè)計(jì) 傳統(tǒng)的非線性規(guī)劃算法的缺陷是 計(jì)算煩瑣且精度不高，穩(wěn)定性差， 對(duì)函數(shù)初值和函數(shù)性態(tài)要求較高， 且容易陷入局部最優(yōu)解 。 （ 3）逆轉(zhuǎn)算子（ Inversion Operator）在個(gè)體碼串中隨機(jī)挑選二個(gè)逆轉(zhuǎn)點(diǎn)，然后將兩