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