【正文】 因串長度length，交叉概率Pc，變異概率Pm，算法迭代次數(shù)T，當(dāng)前迭代次數(shù)t。（2）根據(jù)所給x的范圍，種群大小，染色體長度，隨機生成符合條件的初始種群A。（3）將約束條件加入目標(biāo)函數(shù)，確定適應(yīng)度函數(shù)，計算適值e。（4）對適值e從小到大排序，排序后的適值記為s，并記錄變動情況l。（5）根據(jù)排序結(jié)果把每一代最小適值賦給M，并記錄局部最優(yōu)值對應(yīng)的位置（行），用的行向量B表示。（6）輸出每次迭代t對應(yīng)的局部極值位置B和局部最優(yōu)值s(1)。（7）計算累積概率。（8）用轉(zhuǎn)輪法進(jìn)行選擇運算。種群由A進(jìn)化為A1。（9）雙點交叉實現(xiàn)交叉運算。實現(xiàn)遺傳算法的第一次遺傳運算，種群更新為A2。（10）均勻變異實現(xiàn)變異過程。實現(xiàn)第二次遺傳運算，種群更新為A3。（11）更新種群，將A3賦給A。（12）判斷是否滿足迭代結(jié)束條件。滿足轉(zhuǎn)（13），不滿足轉(zhuǎn)（3），繼續(xù)迭代。（13）對每代最小適值M排序，me為排序后的向量。（14）輸出最小適值Min，即為所求全局最優(yōu)。 遺傳算法程序流程圖圖52 求解非線性規(guī)劃問題的遺傳算法程序流程圖 遺傳算法中所設(shè)計的輔助算法的設(shè)計（1）隨機數(shù)生成。程序中多處涉及到隨機數(shù)的生成，像一開始初始種群的生成，后面的選擇、交叉、變異的循環(huán)條件判斷，都有用到。這里我們使用常用的rand函數(shù)。rand函數(shù)的作用是生成0～1之間的浮點型矩陣，通過對函數(shù)的簡單運算可以生成我們想要的確定范圍內(nèi)的矩陣。（2）累加函數(shù)cunsum。程序中計算累積概率部分，可以使用循環(huán)運算實現(xiàn)，但我們使用MATLAB中更便捷的函數(shù)cumsum直接計算元素累加，如a=[1 2 3 4]，則 cumsum(a)=[1 3 6 10]。（3）上取整函數(shù)ceil。ceil()是向正無窮大舍入，如ceil()=3，配合rand函數(shù)可以隨機生成一定范圍內(nèi)的整數(shù)。（4）排序函數(shù)。因為我們所求是最小化問題，在龐大的種群和多次迭代過程中為方便找出局部最小值和全局最優(yōu)值，我們可以對每次結(jié)果進(jìn)行排序。sort函數(shù)實現(xiàn)按升序排序，如[s,l]=sort(e)，對e從小到大進(jìn)行排序，s為排序后的矩陣，l為變動情況。（5）選擇函數(shù)。選擇函數(shù)是為交叉操作從當(dāng)前種群中選擇兩條染色體來進(jìn)行交叉操作。我們采用轉(zhuǎn)輪法（Roulette Wheel）來選擇染色體。具體過程如下： ① 利用rand函數(shù)產(chǎn)生一個0～1之間的隨機數(shù)r。② 從第一條染色體起，將當(dāng)前種群中各染色體的選擇概率進(jìn)行累加，當(dāng)選擇概率總和大于等于rand時停止。③ 累加結(jié)束時的染色體（即概率之和剛好大于隨機數(shù)rand的那條染色體）即為被選中的染色體。6 算法的結(jié)果分析 概述在以上算法分析設(shè)計的基礎(chǔ)上，我們用MATLAB語言分別實現(xiàn)了求解非線性規(guī)劃問題的遺傳算法和外點罰函數(shù)法。本章我們通過運行實際的算法程序，通過對運行結(jié)果進(jìn)行統(tǒng)計分析，比較兩種算法各自的優(yōu)越性。 結(jié)果比較為了能直觀地表現(xiàn)兩種算法的實際執(zhí)行結(jié)果，我們將兩種算法的執(zhí)行結(jié)果以圖表的形式直觀地表達(dá)出來。兩種算法的計算結(jié)果如表61，62所示。我們通過統(tǒng)計兩種算法所得最優(yōu)值的變化，來比較兩種算法的收斂效果。為了充分比較兩種算法收斂效果，我們對遺傳算法分別采用大小為300和200的兩個種群，懲罰函數(shù)法分別取初始懲罰因子M為10和1，兩種算法分別執(zhí)行算法10次，得到結(jié)果如表61所示。表61 最優(yōu)適值表遺傳算法懲罰函數(shù)法執(zhí)行序號種群300種群200初始懲罰因子M=10初始懲罰因子M=112345678910我們統(tǒng)計兩種算法之間的最大值、最小值、均值和方差。得到表62。表62 均值和方差表遺傳算法懲罰函數(shù)法種群300種群200初始懲罰因子M=10初始懲罰因子M=1最大值最小值均 值方 差我們將表61中的數(shù)據(jù)以圖的形式進(jìn)行表示，得到兩種算法取得最優(yōu)適應(yīng)度值的變化曲線，如下圖所示。圖61 遺傳算法最優(yōu)值變化曲線圖62 懲罰函數(shù)法最優(yōu)值變化曲線圖63 綜合比較曲線從表62可以看出，遺傳算法所得最優(yōu)適值的最大值、平均值、方差要比懲罰函數(shù)法小得多，說明遺傳算法收斂效果更好，結(jié)果更合理；圖61和圖62說明兩個算法對自身參數(shù)設(shè)定的敏感性，可以看出相對于懲罰函數(shù)法，遺傳算法受初始參數(shù)影響要小很多；圖63綜合比較曲線將兩個算法結(jié)果放在一個圖中比較，可以看出，遺傳算法的變化曲線非常平穩(wěn)，波動較小，而懲罰函數(shù)法對初始參數(shù)特別敏感，出現(xiàn)了大的波動。這充分體現(xiàn)了遺傳算法的優(yōu)越性，遺傳算法的全局搜索能力使其能夠不受初始點的影響而找到近似全局最優(yōu)解。通過以上分析可以看出，求解非線性規(guī)劃問題的遺傳算法能夠克服傳統(tǒng)算法對初始值敏感，容易陷入局部最優(yōu)解的缺陷，收斂效果更好，性能更穩(wěn)定，結(jié)果更合理。同時我們比較兩種算法的運行時間，如下表。表63 運行時間比較表遺傳算法懲罰函數(shù)法種群300種群200初始懲罰因子M=10初始懲罰因子M=1最大值最小值均 值從表中可以看出，懲罰函數(shù)法在運行時間上明顯優(yōu)于遺傳算法，說明傳統(tǒng)算法也有其可取優(yōu)勢，不可能被完全取代。下圖即為求解非線性規(guī)劃問題的遺傳算法最優(yōu)適值變化曲線：圖64 求解非線性規(guī)劃問題的遺傳算法最優(yōu)適值變化曲線7 總 結(jié)本文詳細(xì)介紹了非線性規(guī)劃、外點罰函數(shù)法、遺傳算法的基本理論。分析了傳統(tǒng)的非線性規(guī)劃算法計算煩瑣且精度不高，穩(wěn)定性差，對函數(shù)初值和函數(shù)性態(tài)要求較高，且容易陷入局部最優(yōu)解的缺陷。詳細(xì)介紹了遺傳算法的優(yōu)點：簡單，通用，魯棒性強，不要求目標(biāo)函數(shù)可導(dǎo)，是一種全局搜索算法。由此我們意識到用遺傳算法求解非線性規(guī)劃問題是提高收斂效果的有效途徑。在充分理解遺傳算法基本理論，算法思想，關(guān)鍵技術(shù)的基礎(chǔ)上，結(jié)合實際情況，設(shè)計并最終實現(xiàn)了求解非線性規(guī)劃問題的遺傳算法。同時我們也設(shè)計并實現(xiàn)了傳統(tǒng)的非線性規(guī)劃算法——外點罰函數(shù)法。通過比較兩種算法的實際運行結(jié)果，分析兩者之間的性能差異。通過理論分析以及對測試數(shù)據(jù)的統(tǒng)計分析，我們可以看到求解非線性規(guī)劃問題的遺傳算法與傳統(tǒng)的非線性規(guī)劃算法相比，收斂結(jié)果更優(yōu)，性能更穩(wěn)定，魯棒性強，對目標(biāo)函數(shù)既不要求連續(xù)，也不要求可導(dǎo)，有效地克服了傳統(tǒng)算法對函數(shù)初值和函數(shù)性態(tài)要求高，容易陷入局部最優(yōu)解的缺陷。但遺傳算法程序設(shè)計復(fù)雜，算法耗費大量存儲空間和運行時間。但在硬件成本大幅下降的今天，用空間和時間換取最佳結(jié)果是值得的。同時我們也看到，有時候傳統(tǒng)算法所得結(jié)果比遺傳算法要好，這說明傳統(tǒng)算法也有其可取之處，遺傳算法無法完全取代傳統(tǒng)算法。通過幾個月的努力，即將完成論文，由于本人能力有限，本論文中或多或少會存在一些缺點，所設(shè)計的程序難免有一些不足，還懇請各位老師和同學(xué)給予批評和指正。致 謝在論文完成之際，我的心情萬分激動。從論文的選題、資料的收集到論文的撰寫編排整個過程中，我得到了許多的熱情幫助。首先，我要衷心地感謝導(dǎo)師厙向陽教授幾年來在學(xué)習(xí)和生活中給予的諄諄教誨和悉心的關(guān)懷。在論文的選題、研究以及撰寫過程中，自始至終得到了導(dǎo)師的精心指導(dǎo)和熱情幫助，其中無不凝聚著導(dǎo)師的心血和汗水。導(dǎo)師嚴(yán)謹(jǐn)求實和一絲不茍的學(xué)風(fēng)、扎實勤勉和孜孜不倦的工作態(tài)度時刻激勵著我努力學(xué)習(xí)，并將鞭策我在未來的工作中銳意進(jìn)取、奮發(fā)努力。導(dǎo)師的指導(dǎo)將使我終生受益。還要感謝我的學(xué)長和組員，他們在畢業(yè)設(shè)計的過程中給了我很多啟發(fā)和幫助。在我的學(xué)習(xí)和生活中給予了我很大的幫助和支持。對他們也表示我衷心的感謝！還要感謝我的爸爸媽媽，幾十年的養(yǎng)育之恩我無以回報，在這里祝愿你們永遠(yuǎn)健康快樂。最后，再一次感謝所有在我論文完成過程中給予我?guī)椭完P(guān)心的良師益友們。謝謝！參考文獻(xiàn)[1] 汪定偉,王俊偉,王洪峰,[M].北京:高等教育出版 社,～57 [2] 李敏強,寇紀(jì)淞,[M].北京:科學(xué)出版社,～112[3] [日]玄光男,[M].汪定偉,唐加福,:科學(xué)出版社,～40[4] [M].北京:清華大學(xué)出版社,～189[5] 葉家成,(自然科學(xué)版),1997,(01):68～70[6] 敖友云,2005,(04):294～297 [7] 胡能發(fā),潘清芳,2002,(05):21～23[8] 劉瓊蓀,[J].重慶大學(xué)學(xué)報(自然科學(xué)版),2006,(06):78～81[9] 張晶,翟鵬程,[J].武漢理工大學(xué)學(xué)報,2002,(02):56～59[10] 楊曉華,楊志峰,[J].北京師范大學(xué)學(xué)報(自然科學(xué)版),2003,(04):551～556[11] 韋凌云,柴躍廷,[J].計算機工程與應(yīng)用,2006,(22):46～49[12] 劉淳安,[J].運籌與管理,2006,(05):35～38[13] 朱國會,[J].長春工業(yè)大學(xué)學(xué)報(自然科學(xué)版),2004,(04):64～66[14] 唐加福,[J].東北大學(xué)學(xué)報(自然科學(xué)版),1997,(05):490～493[15] 唐加福,汪定偉,許寶棟,[J].控制與決策,2000,(05):573～576[16] 宋松柏,蔡煥杰,[J].西北農(nóng)林科技大學(xué)學(xué)報(自然科學(xué)版),2005,(01):150～154[17] [J].大學(xué)數(shù)學(xué),2005,(01):91～95[18] 陳崚,[J].計算機工程,2004,(18):41～42[19] 王登剛,劉迎曦,[J].上海交通大學(xué)學(xué)報,2003（12）:1953～1956[20] 謝曉鋒,張文俊,阮駿,[J].計算機工程與應(yīng)用,2002,(21):64～673