【正文】 基因座上的基因值用該基因座的其他等位基因來(lái)替換，從而形成一個(gè)新的個(gè)體。遺傳算法的運(yùn)行參數(shù)（1）編碼串長(zhǎng)度L?！?。而遺傳算法是一種全局搜索算法，可以克服傳統(tǒng)的非線性規(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ù)為：=1*(0).* *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è)體。 求解非線性規(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)算。滿足轉(zhuǎn)（13），不滿足轉(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)懷。謝謝！參考文獻(xiàn)[1] 汪定偉,王俊偉,王洪峰,[M].北京:高等教育出版 社,～57 [2] 李敏強(qiáng),寇紀(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é)報(bào)(自然科學(xué)版),2006,(06):78～81[9] 張晶,翟鵬程,[J].武漢理工大學(xué)學(xué)報(bào),2002,(02):56～59[10] 楊曉華,楊志峰,[J].北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2003,(04):551～556[11] 韋凌云,柴躍廷,[J].計(jì)算機(jī)工程與應(yīng)用,2006,(22):46～49[12] 劉淳安,[J].運(yùn)籌與管理,2006,(05):35～38[13] 朱國(guó)會(huì),[J].長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2004,(04):64～66[14] 唐加福,[J].東北大學(xué)學(xué)報(bào)(自然科學(xué)版),1997,(05):490～493[15] 唐加福,汪定偉,許寶棟,[J].控制與決策,2000,(05):573～576[16] 宋松柏,蔡煥杰,[J].西北農(nóng)林科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2005,(01):150～154[17] [J].大學(xué)數(shù)學(xué),2005,(01):91～95[18] 陳崚,[J].計(jì)算機(jī)工程,2004,(18):41～42[19] 王登剛,劉迎曦,[J].上海交通大學(xué)學(xué)報(bào),2003（12）:1953～1956[20] 謝曉鋒,張文俊,阮駿,[J].計(jì)算機(jī)工程與應(yīng)用,2002,(21):64～6731。導(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í)間。下圖即為求解非線性規(guī)劃問(wèn)題的遺傳算法最優(yōu)適值變化曲線：圖64 求解非線性規(guī)劃問(wèn)題的遺傳算法最優(yōu)適值變化曲線7 總 結(jié)本文詳細(xì)介紹了非線性規(guī)劃、外點(diǎn)罰函數(shù)法、遺傳算法的基本理論。表61 最優(yōu)適值表遺傳算法懲罰函數(shù)法執(zhí)行序號(hào)種群300種群200初始懲罰因子M=10初始懲罰因子M=112345678910我們統(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è)染色體計(jì)算適值=；k=1,2,…,pop_size （）（2）計(jì)算種群中所有染色體的適值和 （）（3）對(duì)各染色體，計(jì)算選擇概率；k=1,2,…,pop_size （）（4）對(duì)各染色體，計(jì)算累積概率；k=1,2,…,pop_size （）選擇過(guò)程就是旋轉(zhuǎn)轉(zhuǎn)輪pop_size次，每次按如下方式選出一個(gè)染色體來(lái)構(gòu)造新的種群：選擇步驟：步驟一：在[0,1]區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的偽隨機(jī)數(shù)r；步驟二：若，則選第一個(gè)染色體；否則，選擇第k個(gè)染色體（），使得成立。當(dāng)滿足約束時(shí)，大于等于0，此時(shí)括號(hào)里的結(jié)果為0，也為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ù)編碼，即染色體基因串中基因座的值直接是每組解中各分量的實(shí)數(shù)值，不再對(duì)其進(jìn)行其他任何形式的編碼。本章就是介紹遺傳算法在非線性規(guī)劃中的具體應(yīng)用，設(shè)計(jì)并實(shí)現(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)表，如{1，2，3，4，5，…}；還可以是一個(gè)代碼表，如{A1,A2,A3,A4,…}等等。基于遺傳算法的機(jī)器學(xué)習(xí)，在很多領(lǐng)域中都得到了應(yīng)用。如何使這些誤差最小是使計(jì)算機(jī)視覺(jué)達(dá)到實(shí)用化的重要要求。生產(chǎn)調(diào)度問(wèn)題在許多情況下所建立起來(lái)的數(shù)學(xué)模型難以精確求解，即使經(jīng)過(guò)一些簡(jiǎn)化之后可以進(jìn)行求解，也會(huì)因簡(jiǎn)化得太多而使得求解結(jié)果與實(shí)際相差甚遠(yuǎn)。 遺傳算法的應(yīng)用遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架，它不依賴于問(wèn)題的具體領(lǐng)域，對(duì)問(wèn)題的種類(lèi)有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科。重組包括交叉和變異來(lái)獲得后代。這些染色體在后續(xù)迭代中不斷進(jìn)化，稱(chēng)為遺傳。在生存斗爭(zhēng)中，具有有利變異（mutation）的個(gè)體容易存活下來(lái)，并且有更多的機(jī)會(huì)將有利的變異傳給后代；具有不利變異的個(gè)體就容易被淘汰，產(chǎn)生后代的機(jī)會(huì)也少得多。具體過(guò)程描述如下：（1）選定初始點(diǎn)，初始懲罰因子（可?。Ｈ秉c(diǎn)有：（1）罰函數(shù)法對(duì)于有些問(wèn)題只能求出局部最優(yōu)解，而不能求出全局最優(yōu)。此時(shí)要求在中的最優(yōu)解，只能讓點(diǎn)回到內(nèi)才有可能，然而一旦點(diǎn)回到內(nèi)，即，此時(shí)就與問(wèn)題（）有相同的最優(yōu)解。 算法描述對(duì)于問(wèn)題（），本文所述的基本策略是，根據(jù)約束特點(diǎn)（等式或不等式）構(gòu)造某種“罰函數(shù)”，然后把它加到目標(biāo)函數(shù)中去，使得對(duì)約束最優(yōu)化問(wèn)題的求解轉(zhuǎn)化為一系列無(wú)約束問(wèn)題。 非線性規(guī)劃的應(yīng)用在經(jīng)營(yíng)管理、工程設(shè)計(jì)、科學(xué)研究、軍事指揮等方面普遍地存在著最優(yōu)化問(wèn)題。常用的約束最優(yōu)化方法有4種[1]：①拉格朗日乘子法：它是將原問(wèn)題轉(zhuǎn)化為求拉格朗日函數(shù)的駐點(diǎn)。屬于解析型的算法有：①梯度法：又稱(chēng)最速下降法。這類(lèi)方法的意義在于：雖然實(shí)用規(guī)劃問(wèn)題大多是有約束的，但許多約束最優(yōu)化方法可將有約束問(wèn)題轉(zhuǎn)化為若干無(wú)約束問(wèn)題來(lái)求解[1]。其基本思想是：在初始尋查區(qū)間中設(shè)計(jì)一列點(diǎn)，通過(guò)逐次比較其函數(shù)值，逐步縮小尋查區(qū)間，以得出近似最優(yōu)值點(diǎn)。對(duì)于一個(gè)可行解，如果存在的一個(gè)鄰域，使目標(biāo)函數(shù)在處的值優(yōu)于(指不大于或不小于)該鄰域中任何其他可行解處的函數(shù)值，則稱(chēng)為問(wèn)題的局部最優(yōu)解（簡(jiǎn)稱(chēng)局部解）。 非線性規(guī)