【正文】 ）輸出每次迭代t對(duì)應(yīng)的局部極值位置B和局部最優(yōu)值s(1)。（11）更新種群，將A3賦給A。rand函數(shù)的作用是生成0～1之間的浮點(diǎn)型矩陣，通過(guò)對(duì)函數(shù)的簡(jiǎn)單運(yùn)算可以生成我們想要的確定范圍內(nèi)的矩陣。（5）選擇函數(shù)。 結(jié)果比較為了能直觀地表現(xiàn)兩種算法的實(shí)際執(zhí)行結(jié)果，我們將兩種算法的執(zhí)行結(jié)果以圖表的形式直觀地表達(dá)出來(lái)。這充分體現(xiàn)了遺傳算法的優(yōu)越性，遺傳算法的全局搜索能力使其能夠不受初始點(diǎn)的影響而找到近似全局最優(yōu)解。在充分理解遺傳算法基本理論，算法思想，關(guān)鍵技術(shù)的基礎(chǔ)上，結(jié)合實(shí)際情況，設(shè)計(jì)并最終實(shí)現(xiàn)了求解非線性規(guī)劃問(wèn)題的遺傳算法。致 謝在論文完成之際，我的心情萬(wàn)分激動(dòng)。對(duì)他們也表示我衷心的感謝！還要感謝我的爸爸媽媽?zhuān)瑤资甑酿B(yǎng)育之恩我無(wú)以回報(bào)，在這里祝愿你們永遠(yuǎn)健康快樂(lè)。還要感謝我的學(xué)長(zhǎng)和組員，他們?cè)诋厴I(yè)設(shè)計(jì)的過(guò)程中給了我很多啟發(fā)和幫助。同時(shí)我們也看到，有時(shí)候傳統(tǒng)算法所得結(jié)果比遺傳算法要好，這說(shuō)明傳統(tǒng)算法也有其可取之處，遺傳算法無(wú)法完全取代傳統(tǒng)算法。詳細(xì)介紹了遺傳算法的優(yōu)點(diǎn)：簡(jiǎn)單，通用，魯棒性強(qiáng)，不要求目標(biāo)函數(shù)可導(dǎo)，是一種全局搜索算法。表62 均值和方差表遺傳算法懲罰函數(shù)法種群300種群200初始懲罰因子M=10初始懲罰因子M=1最大值最小值均 值方 差我們將表61中的數(shù)據(jù)以圖的形式進(jìn)行表示，得到兩種算法取得最優(yōu)適應(yīng)度值的變化曲線，如下圖所示。6 算法的結(jié)果分析 概述在以上算法分析設(shè)計(jì)的基礎(chǔ)上，我們用MATLAB語(yǔ)言分別實(shí)現(xiàn)了求解非線性規(guī)劃問(wèn)題的遺傳算法和外點(diǎn)罰函數(shù)法。因?yàn)槲覀兯笫亲钚』瘑?wèn)題，在龐大的種群和多次迭代過(guò)程中為方便找出局部最小值和全局最優(yōu)值，我們可以對(duì)每次結(jié)果進(jìn)行排序。程序中多處涉及到隨機(jī)數(shù)的生成，像一開(kāi)始初始種群的生成，后面的選擇、交叉、變異的循環(huán)條件判斷，都有用到。（10）均勻變異實(shí)現(xiàn)變異過(guò)程。（4）對(duì)適值e從小到大排序，排序后的適值記為s，并記錄變動(dòng)情況l。這里由于是對(duì)每個(gè)基因座進(jìn)行變異操作，為了保證變異效果，Pm取值較大。一般根據(jù)問(wèn)題規(guī)模而定，這里我們?nèi)?00。例如：對(duì)染色體Chromosome=[1，2，3，4，5]進(jìn)行變異，從1號(hào)位基因開(kāi)始，每次隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)x，若這個(gè)隨機(jī)數(shù)xPm，則進(jìn)行變異，在指定范圍內(nèi)隨機(jī)產(chǎn)生一個(gè)實(shí)數(shù)，來(lái)替換掉1號(hào)基因位的值；若xPm，則本次不進(jìn)行變異，繼續(xù)對(duì)2號(hào)位基因值進(jìn)行變異操作，直到5號(hào)位結(jié)束。常用的交叉有單點(diǎn)交叉，雙點(diǎn)、多點(diǎn)交叉等。然后再根據(jù)公式（），將懲罰函數(shù)加入目標(biāo)函數(shù)，也就是將約束條件加入目標(biāo)函數(shù)，確定適應(yīng)度函數(shù)[3][8]。對(duì)于極大化問(wèn)題，取 （）令和分別為現(xiàn)行種群中的的最大值和的最小值。我們希望給b較小懲罰。Glover和Greenberg建議的約束管理技術(shù)允許在搜索空間里的不可行域中進(jìn)行搜索，這比將搜索限制在可行域內(nèi)的方法能更快地活的最優(yōu)解或獲得更好的最終解。Michalewicz等則認(rèn)為對(duì)有非線性約束的優(yōu)化問(wèn)題，15%的替代率為最好。對(duì)于許多組合優(yōu)化問(wèn)題，構(gòu)造修復(fù)程序相對(duì)比較容易。適應(yīng)度函數(shù)設(shè)計(jì)1）滿足約束由于對(duì)染色體作遺傳運(yùn)算時(shí)通常獲得不可行的后代，因此運(yùn)用遺傳算法解非線性規(guī)劃問(wèn)題的核心問(wèn)題是如何滿足約束的問(wèn)題。從非線性規(guī)劃的數(shù)學(xué)模型可知，我們最終要求解的是一組解，其滿足約束條件，并使目標(biāo)函數(shù)達(dá)到最小值(或最大值)。（5）終止代數(shù)T。當(dāng)pop_size取值較小時(shí)，可提高遺傳算法的運(yùn)算速度，卻降低了群體的多樣性，有可能會(huì)引起遺傳算法的早熟現(xiàn)象；當(dāng)pop_size取值較大時(shí)，又會(huì)使遺傳算法的運(yùn)行效率降低。以事先設(shè)定的變異概率Pm來(lái)對(duì)這些基因座的基因值進(jìn)行變異。常用的配對(duì)策略是隨機(jī)配對(duì)，即將群體中的M個(gè)個(gè)體以隨機(jī)的方式組成對(duì)配對(duì)個(gè)體組，交叉操作是在這些配對(duì)個(gè)體組中的兩個(gè)個(gè)體之間進(jìn)行的。選擇操作的主要目的是為了避免基因缺失、提高全局收斂性和計(jì)算效率。遺傳算法的一個(gè)特點(diǎn)是它僅使用所求問(wèn)題的目標(biāo)函數(shù)值就可得到下一步的有關(guān)搜索信息。在遺傳算法中把一個(gè)問(wèn)題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法稱(chēng)為編碼。（7）人工生命。（4）自動(dòng)控制。函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對(duì)遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例。遺傳運(yùn)算模擬了基因在每一代中創(chuàng)造新后代的繁殖過(guò)程，進(jìn)化運(yùn)算則是種群逐代更新的過(guò)程。生成的下一代染色體稱(chēng)為后代。達(dá)爾文的自然選擇學(xué)說(shuō)表明，遺傳和變異是決定生物進(jìn)化的內(nèi)在因素。（2）假設(shè)已獲得迭代點(diǎn)，以為初始點(diǎn)，求解無(wú)約束問(wèn)題 （）設(shè)其最優(yōu)點(diǎn)為。（3）罰函數(shù)法在實(shí)際計(jì)算中的缺點(diǎn)是罰因子的取值難于把握，太小起不到懲罰作用；太大則由于誤差的影響會(huì)導(dǎo)致錯(cuò)誤。簡(jiǎn)言之，外點(diǎn)罰函數(shù)法的思想是：當(dāng)點(diǎn)時(shí)，設(shè)法加大不可行點(diǎn)處的函數(shù)值，使不可行點(diǎn)不能成為在中的最優(yōu)解。對(duì)于問(wèn)題（），構(gòu)造一函數(shù)為 （）其中， （）在（）中，又稱(chēng)為懲罰函數(shù)， （） （）是一個(gè)逐漸增大的參數(shù)，稱(chēng)為懲罰因子。對(duì)于靜態(tài)的最優(yōu)化問(wèn)題，當(dāng)目標(biāo)函數(shù)或約束條件出現(xiàn)未知量的非線性函數(shù)，且不便于線性化，或勉強(qiáng)線性化后會(huì)招致較大誤差時(shí)，就可應(yīng)用非線性規(guī)劃的方法去處理。它又分兩類(lèi)，一類(lèi)叫懲罰函數(shù)法，或稱(chēng)外點(diǎn)法；另一類(lèi)叫障礙函數(shù)法，或稱(chēng)內(nèi)點(diǎn)法。②牛頓法：收斂速度快，但不穩(wěn)定，計(jì)算也較困難。這類(lèi)迭代算法可分為兩類(lèi)。它也是針對(duì)單峰函數(shù)的。實(shí)用非線性規(guī)劃問(wèn)題要求整體解，而現(xiàn)有解法大多只是求出局部解。然后將各種限制條件加以抽象，得出決策變量應(yīng)滿足的一些等式或不等式，稱(chēng)之為約束條件[4]。本文的主要內(nèi)容就是應(yīng)用遺傳算法的基本思想，結(jié)合本次實(shí)驗(yàn)的實(shí)際情況，對(duì)基本遺傳算法加以改進(jìn)，將遺傳算法應(yīng)用于求解非線性規(guī)劃問(wèn)題，形成求解非線性規(guī)劃問(wèn)題的遺傳算法。傳統(tǒng)的解決非線性規(guī)劃問(wèn)題的方法有多種，如搜索法、梯度法、變尺度法、罰函數(shù)法、拉格朗日乘子法、可行方向法等，雖然解法很多，非線性規(guī)劃目前還沒(méi)有能適用于各種問(wèn)題的算法，各個(gè)方法都有自己特定的適用范圍。 SUMT Algorithm 目 錄1 概論 1 背景介紹 1 非線性規(guī)劃簡(jiǎn)介 1 遺傳算法簡(jiǎn)介 1 研究?jī)?nèi)容 22 非線性規(guī)劃 3 非線性規(guī)劃的概念 3 非線性規(guī)劃的數(shù)學(xué)模型 3 非線性規(guī)劃的求解方法 4 一維最優(yōu)化方法 4 無(wú)約束最優(yōu)化方法 4 約束最優(yōu)化方法 5 非線性規(guī)劃的應(yīng)用 53 傳統(tǒng)非線性規(guī)劃算法——外點(diǎn)罰函數(shù)法 6 算法概述 6 算法描述 6 算法性能分析 7 外點(diǎn)罰函數(shù)法的程序設(shè)計(jì) 8 8 84 遺傳算法 10 遺傳算法概述 10 遺傳算法的生物學(xué)基礎(chǔ) 10 遺傳算法的一般結(jié)構(gòu) 10 遺傳算法的特點(diǎn) 12 遺傳算法的應(yīng)用 12 遺傳算法實(shí)現(xiàn)的關(guān)鍵技術(shù) 135 求解非線性規(guī)劃問(wèn)題的遺傳算法設(shè)計(jì) 16 實(shí)用遺傳算法設(shè)計(jì) 16 求解非線性規(guī)劃問(wèn)題的遺傳算法程序設(shè)計(jì) 21 算法過(guò)程描述 21 遺傳算法程序流程圖 22 遺傳算法中所設(shè)計(jì)的輔助算法的設(shè)計(jì) 226 算法的結(jié)果分析 24 概述 24 結(jié)果比較 247 總結(jié) 28致謝 29參考文獻(xiàn) 30II1 概 論 背景介紹 非線性規(guī)劃簡(jiǎn)介具有非線性約束條件或目標(biāo)函數(shù)的數(shù)學(xué)規(guī)劃，稱(chēng)為非線性規(guī)劃。遺傳算法是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過(guò)程的計(jì)算模型。算法引進(jìn)懲罰函數(shù)的概念，構(gòu)造帶有懲罰項(xiàng)的適應(yīng)度函數(shù)；通過(guò)實(shí)數(shù)編碼，轉(zhuǎn)輪法選擇，雙點(diǎn)交叉，均勻變異，形成了求解非線性規(guī)劃問(wèn)題的遺傳算法。在50年代還得出了可分離規(guī)劃和二次規(guī)劃的n種解法。它的主要特點(diǎn)是簡(jiǎn)單、通用、魯棒性強(qiáng)，對(duì)目標(biāo)函數(shù)既不要求連續(xù)，也不要求可導(dǎo)，適用于并行分布處理，應(yīng)用范圍廣。2 非線性規(guī)劃 非線性規(guī)劃的概念具有非線性約束條件或目標(biāo)函數(shù)的數(shù)學(xué)規(guī)劃，稱(chēng)為非線性規(guī)劃。 上述模型可簡(jiǎn)記為： （） （）其中屬于定義域，符號(hào)min表示“求最小值”，“受約束于”。常用的一維最優(yōu)化方法有黃金分割法、切線法和插值法[1]。其基本思想是用多項(xiàng)式（通常用二次或三次多項(xiàng)式）去擬合目標(biāo)函數(shù)。這些迭代算法的基本思想是：在一個(gè)近似點(diǎn)處選定一個(gè)有利搜索方向，沿這個(gè)方向進(jìn)行一維尋查，得出新的近似點(diǎn)。其中達(dá)維登弗萊徹鮑威爾變尺度法，簡(jiǎn)稱(chēng)DFP法，是最常用的方法。如佐坦迪克法、弗蘭克－沃爾夫法、投影梯度法和簡(jiǎn)約梯度法都屬于此類(lèi)算法。主要有兩種形式，一種叫外點(diǎn)罰函數(shù)法，另一種叫內(nèi)點(diǎn)罰函數(shù)法。由增廣目標(biāo)函數(shù)的構(gòu)造知當(dāng)時(shí) （）此時(shí)的最優(yōu)解就是問(wèn)題（）的最優(yōu)解；而當(dāng)時(shí)，的最優(yōu)解就不一定是問(wèn)題（）的最優(yōu)解。如果，則是問(wèn)題（）的最優(yōu)解；如果，則不是問(wèn)題（）的最優(yōu)解，此時(shí)說(shuō)明原來(lái)的懲罰因子給的太小了，需要加大懲罰因子，使得，然后再重新計(jì)算的最優(yōu)值。這對(duì)于進(jìn)化算法來(lái)說(shuō)非常致命的。外點(diǎn)罰函數(shù)法程序流程圖如圖31所示。和傳統(tǒng)算法不同，遺傳算法從一組隨機(jī)產(chǎn)生的初始解，稱(chēng)為“種群”，開(kāi)始搜索過(guò)程。適值高的染色體被選中的概率較高。（2）遺傳算法直接以適應(yīng)度作為搜索信息，無(wú)需導(dǎo)數(shù)等其它輔助信息。遺傳算法是解決這類(lèi)問(wèn)題的最佳工具之一。機(jī)器人是一類(lèi)復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來(lái)自于對(duì)人工自適應(yīng)系統(tǒng)的研究，所以機(jī)器人智能控制理所當(dāng)然地成為遺傳算法的一個(gè)重要應(yīng)用領(lǐng)域。（8）遺傳編程。（2）浮點(diǎn)數(shù)編碼：個(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來(lái)表示，個(gè)體的編碼長(zhǎng)度等于其決策變量的個(gè)數(shù)。（2）由個(gè)體的表現(xiàn)型可計(jì)算出對(duì)應(yīng)個(gè)體的目標(biāo)函數(shù)值。在聯(lián)賽選擇操作中，只