求解非線性規(guī)劃問(wèn)題的遺傳算法設(shè)計(jì)實(shí)現(xiàn)分析范文

./摘要非線性規(guī)劃在工程、管理、經(jīng)濟(jì)、科研、軍事等方面都有廣泛的應(yīng)用。傳統(tǒng)的解決非線性規(guī)劃問(wèn)題的方法,如梯度法、罰函數(shù)法、拉格朗日乘子法等,穩(wěn)定性差,對(duì)函數(shù)初值和函數(shù)性態(tài)要求較高,且容易陷入局部最優(yōu)解。遺傳算法是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過(guò)程的計(jì)算模型。遺傳算法是一種全局搜索算法,簡(jiǎn)單、通用、魯棒性強(qiáng),對(duì)目標(biāo)函數(shù)既不要求連續(xù),也不要求可導(dǎo),適用于并行分布處理,應(yīng)用范圍廣。本文在分析傳統(tǒng)的非線性規(guī)劃算法的不足和遺傳算法的優(yōu)越性的基礎(chǔ)上,將遺傳算法應(yīng)用于非線性規(guī)劃。算法引進(jìn)懲罰函數(shù)的概念,構(gòu)造帶有懲罰項(xiàng)的適應(yīng)度函數(shù)；通過(guò)實(shí)數(shù)編碼,轉(zhuǎn)輪法選擇,雙點(diǎn)交叉,均勻變異,形成了求解非線性規(guī)劃問(wèn)題的遺傳算法。與傳統(tǒng)的非線性規(guī)劃算法——外點(diǎn)罰函數(shù)法的比較結(jié)果表明該算法在一定程度上有效地克服了傳統(tǒng)的非線性規(guī)劃算法穩(wěn)定性差,對(duì)函數(shù)初值和函數(shù)性態(tài)要求較高,且容易陷入局部最優(yōu)解的缺陷,收斂更合理,性能更穩(wěn)定。關(guān)鍵詞：非線性規(guī)劃；遺傳算法；罰函數(shù)法ABSTRACTNon-linearprogramminghasawiderangeofapplicationsinengineering,management,economic,scientific,andmilitaryaspects.Traditionalmethodstosolvethenon-linearprogrammingproblem,suchasthegradientmethod,penaltymethod,Lagrangemultipliermethod,havepoorstability.Theyaresensitivetothefunctioninitialvalueandrequesttheobjectivefunctiontobecontinuousanddifferential.Theresultsarealsoeasilytrappedintolocaloptimalsolution.GeneticalgorithmisakindofcalculatemodelwhichsimulatesDarwin'sgeneticselectionandbiologicalevolutionofnaturalselection.Geneticalgorithmisaglobalsearchalgorithm.Ithassimple,universal,robustfeatures,anddoesnotrequesttheobjectivefunctiontobecontinuousanddifferential,andissuitableinparalleldistributionprocessing.Geneticalgorithmiswidelyappliedinmanyareas.Basedontheanalysisofthedisadvantageoftraditionalnon-linearprogrammingalgorithmandtheadvantageofgeneticalgorithm,geneticalgorithmisappliedtonon-linearprogramminginthispaper.Theintroductionoftheconceptofpenaltyfunctionisusedtoconstructthefitnessfunctionwithpunishment.Byusingreal-coded,RouletteWheelselectionmethod,two-pointcrossover,uniformmutation,weformedageneticalgorithmtosolvethenon-linearprogrammingproblem.Comparedwiththemostclassicalandwidelyusedtraditionalnon-linearprogrammingproblemalgorithm–SUMTalgorithm,theresultsshowthatthenewalgorithmcouldeffectivelyovercomethedefectofthetraditionalalgorithminacertainextent.Thenewalgorithmismorestable,lesssensitivetothefunctioninitialvalueandconditions,andalwayscouldreceivetheoptimalsolutionorapproximateoptimalsolution.Itsconvergenceresultsaremorereasonable,theperformanceismorestable.KeyWords:Non-linearProgramming;GeneticAlgorithm;SUMTAlgorithm.目錄1概論11.1背景介紹11.1.1非線性規(guī)劃簡(jiǎn)介11.1.2遺傳算法簡(jiǎn)介11.2研究?jī)?nèi)容22非線性規(guī)劃32.1非線性規(guī)劃的概念32.2非線性規(guī)劃的數(shù)學(xué)模型32.3非線性規(guī)劃的求解方法42.3.1一維最優(yōu)化方法42.3.2無(wú)約束最優(yōu)化方法42.3.3約束最優(yōu)化方法52.4非線性規(guī)劃的應(yīng)用53傳統(tǒng)非線性規(guī)劃算法——外點(diǎn)罰函數(shù)法63.1算法概述63.2算法描述63.3算法性能分析73.4外點(diǎn)罰函數(shù)法的程序設(shè)計(jì)8程序步驟8程序流程圖84遺傳算法104.1遺傳算法概述104.1.1遺傳算法的生物學(xué)基礎(chǔ)104.1.2遺傳算法的一般結(jié)構(gòu)104.1.3遺傳算法的特點(diǎn)124.1.4遺傳算法的應(yīng)用124.2遺傳算法實(shí)現(xiàn)的關(guān)鍵技術(shù)135求解非線性規(guī)劃問(wèn)題的遺傳算法設(shè)計(jì)165.1實(shí)用遺傳算法設(shè)計(jì)165.2求解非線性規(guī)劃問(wèn)題的遺傳算法程序設(shè)計(jì)215.2.1算法過(guò)程描述215.2.2遺傳算法程序流程圖225.2.3遺傳算法中所設(shè)計(jì)的輔助算法的設(shè)計(jì)226算法的結(jié)果分析246.1概述246.2結(jié)果比較247總結(jié)28致謝29參考文獻(xiàn)30.1概論1.1背景介紹非線性規(guī)劃簡(jiǎn)介具有非線性約束條件或目標(biāo)函數(shù)的數(shù)學(xué)規(guī)劃,稱為非線性規(guī)劃。非線性規(guī)劃是20世紀(jì)50年代才開(kāi)始形成的一門新興學(xué)科。1951年H.W.庫(kù)恩和A.W.塔克發(fā)表的關(guān)于最優(yōu)性條件<后來(lái)稱為庫(kù)恩－塔克條件>的論文是非線性規(guī)劃正式誕生的一個(gè)重要標(biāo)志。在50年代還得出了可分離規(guī)劃和二次規(guī)劃的n種解法,它們大都是以G.B.丹齊克提出的解線性規(guī)劃的單純形法為基礎(chǔ)的。50年代末到60年代末出現(xiàn)了許多解非線性規(guī)劃問(wèn)題的有效的算法,70年代又得到進(jìn)一步的發(fā)展。非線性規(guī)劃在工程、管理、經(jīng)濟(jì)、科研、軍事等方面都有廣泛的應(yīng)用,為最優(yōu)化設(shè)計(jì)提供了有力的工具。隨著計(jì)算機(jī)的產(chǎn)生與發(fā)展,非線性規(guī)劃作為一門獨(dú)立的學(xué)科越來(lái)越受到人們的重視。在非線性規(guī)劃理論研究的基礎(chǔ)上,人們?nèi)找嬷匾暦蔷€性規(guī)劃問(wèn)題求解方法的研究。傳統(tǒng)的解決非線性規(guī)劃問(wèn)題的方法有多種,如搜索法、梯度法、變尺度法、罰函數(shù)法、拉格朗日乘子法、可行方向法等,雖然解法很多,非線性規(guī)劃目前還沒(méi)有能適用于各種問(wèn)題的算法,各個(gè)方法都有自己特定的適用范圍。遺傳算法簡(jiǎn)介遺傳算法〔GeneticAlgorithm,是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過(guò)程的計(jì)算模型,是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法,它是由美國(guó)Michigan大學(xué)J.Holland教授于1975年首先提出來(lái)的,并出版了頗有影響的專著《AdaptationinNaturalandArtificialSystems》,GA這個(gè)名稱才逐漸為人所知,J.Holland教授所提出的GA通常為簡(jiǎn)單遺傳算法〔SGA。遺傳算法是一種特別有效的算法,它能在搜索過(guò)程中自動(dòng)獲取和積累有關(guān)搜索空間的知識(shí),并自適應(yīng)地控制搜索過(guò)程,從而得到最優(yōu)解或準(zhǔn)最優(yōu)解。它的主要特點(diǎn)是簡(jiǎn)單、通用、魯棒性強(qiáng),對(duì)目標(biāo)函數(shù)既不要求連續(xù),也不要求可導(dǎo),適用于并行分布處理,應(yīng)用范圍廣。遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架,它不依賴于問(wèn)題的具體領(lǐng)域,對(duì)問(wèn)題的種類有很強(qiáng)的魯棒性,所以廣泛應(yīng)用于很多領(lǐng)域,如函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調(diào)度問(wèn)題、自動(dòng)控制、機(jī)器人智能控制、圖像處理,人工生命、遺傳編程、機(jī)器學(xué)習(xí)等。并且取得了令人矚目的成果。1.2研究?jī)?nèi)容傳統(tǒng)的非線性規(guī)劃算法的缺陷是計(jì)算煩瑣且精度不高,穩(wěn)定性差,對(duì)函數(shù)初值和函數(shù)性態(tài)要求較高,且容易陷入局部最優(yōu)解。而遺傳算法是一種魯棒性很強(qiáng)的種全局搜索算法,理論上可以克服傳統(tǒng)非線性規(guī)劃算法的缺陷。本文的主要內(nèi)容就是應(yīng)用遺傳算法的基本思想,結(jié)合本次實(shí)驗(yàn)的實(shí)際情況,對(duì)基本遺傳算法加以改進(jìn),將遺傳算法應(yīng)用于求解非線性規(guī)劃問(wèn)題,形成求解非線性規(guī)劃問(wèn)題的遺傳算法。具體內(nèi)容包括編碼方法設(shè)計(jì),適應(yīng)度函數(shù)設(shè)計(jì),選擇算子、交叉算子、變異算子等遺傳算子設(shè)計(jì),算法流程設(shè)計(jì),并在設(shè)計(jì)的基礎(chǔ)上用MATLAB語(yǔ)言實(shí)現(xiàn)該算法的程序,運(yùn)行并調(diào)試程序,直至得到正確的結(jié)果。并對(duì)實(shí)驗(yàn)所得結(jié)果進(jìn)行分析,比較求解非線性規(guī)劃問(wèn)題的遺傳算法與傳統(tǒng)的非線性規(guī)劃算法的優(yōu)缺點(diǎn)。2非線性規(guī)劃2.1非線性規(guī)劃的概念具有非線性約束條件或目標(biāo)函數(shù)的數(shù)學(xué)規(guī)劃,稱為非線性規(guī)劃。非線性規(guī)劃研究一個(gè)n元實(shí)函數(shù)在一組等式或不等式的約束條件下的極值問(wèn)題,且目標(biāo)函數(shù)和約束條件至少有一個(gè)是未知量的非線性函數(shù)。目標(biāo)函數(shù)和約束條件都是線性函數(shù)的情形則屬于線性規(guī)劃。2.2非線性規(guī)劃的數(shù)學(xué)模型對(duì)實(shí)際規(guī)劃問(wèn)題作定量分析,必須建立數(shù)學(xué)模型。建立數(shù)學(xué)模型首先要選定適當(dāng)?shù)哪繕?biāo)變量和決策變量,并建立起目標(biāo)變量與決策變量之間的函數(shù)關(guān)系,稱之為目標(biāo)函數(shù)。然后將各種限制條件加以抽象,得出決策變量應(yīng)滿足的一些等式或不等式,稱之為約束條件[4]。非線性規(guī)劃問(wèn)題的一般數(shù)學(xué)模型可表述為求未知量,使?jié)M足約束條件：〔2.1并使目標(biāo)函數(shù)達(dá)到最小值<或最大值>。其中,諸和諸都是定義在n維向量空間的某子集<定義域>上的實(shí)值函數(shù),且至少有一個(gè)是非線性函數(shù)。

上述模型可簡(jiǎn)記為：〔2.2〔2.3其中屬于定義域,符號(hào)min表示"求最小值",符號(hào)s.t.表示"受約束于"。定義域中滿足約束條件的點(diǎn)稱為問(wèn)題的可行解。全體可行解所成的集合稱為問(wèn)題的可行集。對(duì)于一個(gè)可行解,如果存在的一個(gè)鄰域,使目標(biāo)函數(shù)在處的值優(yōu)于<指不大于或不小于>該鄰域中任何其他可行解處的函數(shù)值,則稱為問(wèn)題的局部最優(yōu)解〔簡(jiǎn)稱局部解。如果優(yōu)于一切可行解處的目標(biāo)函數(shù)值,則稱x*為問(wèn)題的整體最優(yōu)解〔簡(jiǎn)稱整體解。實(shí)用非線性規(guī)劃問(wèn)題要求整體解,而現(xiàn)有解法大多只是求出局部解。2.3非線性規(guī)劃的求解方法一維最優(yōu)化方法指尋求一元函數(shù)在某區(qū)間上的最優(yōu)值點(diǎn)的方法。這類方法不僅有實(shí)用價(jià)值,而且大量多維最優(yōu)化方法都依賴于一系列的一維最優(yōu)化。常用的一維最優(yōu)化方法有黃金分割法、切線法和插值法[1]。①黃金分割法,又稱0.618法。它適用于單峰函數(shù)。其基本思想是：在初始尋查區(qū)間中設(shè)計(jì)一列點(diǎn),通過(guò)逐次比較其函數(shù)值,逐步縮小尋查區(qū)間,以得出近似最優(yōu)值點(diǎn)。②切線法,又稱牛頓法。它也是針對(duì)單峰函數(shù)的。其基本思想是：在一個(gè)猜測(cè)點(diǎn)附近將目標(biāo)函數(shù)的導(dǎo)函數(shù)線性化,用此線性函數(shù)的零點(diǎn)作為新的猜測(cè)點(diǎn),逐步迭代去逼近最優(yōu)點(diǎn)。③插值法,又稱多項(xiàng)式逼近法。其基本思想是用多項(xiàng)式〔通常用二次或三次多項(xiàng)式去擬合目標(biāo)函數(shù)。此外,還有斐波那契法、割線法、有理插值法、分批搜索法等。無(wú)約束最優(yōu)化方法指尋求n元實(shí)函數(shù)在整個(gè)n維向量空間上的最優(yōu)值點(diǎn)的方法。這類方法的意義在于：雖然實(shí)用規(guī)劃問(wèn)題大多是有約束的,但許多約束最優(yōu)化方法可將有約束問(wèn)題轉(zhuǎn)化為若干無(wú)約束問(wèn)題來(lái)求解[1]。無(wú)約束最優(yōu)化方法大多是逐次一維搜索的迭代算法。這類迭代算法可分為兩類。一類需要用目標(biāo)函數(shù)的導(dǎo)函數(shù),稱為解析法。另一類不涉及導(dǎo)數(shù),只用到函數(shù)值,稱為直接法。這些迭代算法的基本思想是：在一個(gè)近似點(diǎn)處選定一個(gè)有利搜索方向,沿這個(gè)方向進(jìn)行一維尋查,得出新的近似點(diǎn)。然后對(duì)新點(diǎn)施行同樣手續(xù),如此反復(fù)迭代,直到滿足預(yù)定的精度要求為止。根據(jù)搜索方向的取法不同,可以有各種算法。屬于解析型的算法有：=1\*GB3①梯度法：又稱最速下降法。這是早期的解析法,收斂速度較慢。②牛頓法：收斂速度快,但不穩(wěn)定,計(jì)算也較困難。③共軛梯度法：收斂較快,效果較好。④變尺度法：這是一類效率較高的方法。其中達(dá)維登-弗萊徹-鮑威爾變尺度法,簡(jiǎn)稱DFP法,是最常用的方法。屬于直接型的算法有交替方向法〔又稱坐標(biāo)輪換法、模式搜索法、旋轉(zhuǎn)方向法、鮑威爾共軛方向法和單純形加速法等。約束最優(yōu)化方法指前述一般非線性規(guī)劃模型的求解方法。常用的約束最優(yōu)化方法有4種[1]：=1\*GB3①拉格朗日乘子法：它是將原問(wèn)題轉(zhuǎn)化為求拉格朗日函數(shù)的駐點(diǎn)。②制約函數(shù)法：又稱系列無(wú)約束最小化方法,簡(jiǎn)稱SUMT法。它又分兩類,一類叫懲罰函數(shù)法,或稱外點(diǎn)法；另一類叫障礙函數(shù)法,或稱內(nèi)點(diǎn)法。它們都是將原問(wèn)題轉(zhuǎn)化為一系列無(wú)約束問(wèn)題來(lái)求解。③可行方向法：這是一類通過(guò)逐次選取可行下降方向去逼近最優(yōu)點(diǎn)的迭代算法。如佐坦迪克法、弗蘭克－沃爾夫法、投影梯度法和簡(jiǎn)約梯度法都屬于此類算法。④近似型算法：這類算法包括序貫線性規(guī)劃法和序貫二次規(guī)劃法。前者將原問(wèn)題化為一系列線性規(guī)劃問(wèn)題求解,后者將原問(wèn)題化為一系列二次規(guī)劃問(wèn)題求解。2.4非線性規(guī)劃的應(yīng)用在經(jīng)營(yíng)管理、工程設(shè)計(jì)、科學(xué)研究、軍事指揮等方面普遍地存在著最優(yōu)化問(wèn)題。例如：如何在現(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)最快等。對(duì)于靜態(tài)的最優(yōu)化問(wèn)題,當(dāng)目標(biāo)函數(shù)或約束條件出現(xiàn)未知量的非線性函數(shù),且不便于線性化,或勉強(qiáng)線性化后會(huì)招致較大誤差時(shí),就可應(yīng)用非線性規(guī)劃的方法去處理。3傳統(tǒng)非線性規(guī)劃算法——外點(diǎn)罰函數(shù)法3.1算法概述罰函數(shù)法求解非線性規(guī)劃問(wèn)題的思想是,利用問(wèn)題中的約束函數(shù)做出適當(dāng)?shù)牧P函數(shù),由此構(gòu)造出帶參數(shù)的增廣目標(biāo)函數(shù),把問(wèn)題轉(zhuǎn)化為無(wú)約束非線性規(guī)劃問(wèn)題。利用罰函數(shù)法,可將非線性規(guī)劃問(wèn)題的求解,轉(zhuǎn)化為求解一系列無(wú)約束極值問(wèn)題,因而也稱這種方法為序列無(wú)約束最小化技術(shù),簡(jiǎn)記為SUMT<SequentialUnconstrainedMinimizationTechnique>。主要有兩種形式,一種叫外點(diǎn)罰函數(shù)法,另一種叫內(nèi)點(diǎn)罰函數(shù)法。外點(diǎn)罰函數(shù)法是從非可行解出發(fā)逐漸移動(dòng)到可行區(qū)域的方法。內(nèi)點(diǎn)罰函數(shù)法也稱為障礙罰函數(shù)法,這種方法是在可行域內(nèi)部進(jìn)行搜索,約束邊界起到類似圍墻的作用,如果當(dāng)前解遠(yuǎn)離約束邊界時(shí),則罰函數(shù)值是非常小的,否則罰函數(shù)值接近無(wú)窮大的方法。3.2算法描述對(duì)于問(wèn)題〔2.2,本文所述的基本策略是,根據(jù)約束特點(diǎn)〔等式或不等式構(gòu)造某種"罰函數(shù)",然后把它加到目標(biāo)函數(shù)中去,使得對(duì)約束最優(yōu)化問(wèn)題的求解轉(zhuǎn)化為一系列無(wú)約束問(wèn)題。極小點(diǎn)或者無(wú)限地向可行域靠近,或者一直保持在可行集內(nèi)移動(dòng),直到收斂于原來(lái)約束最優(yōu)化問(wèn)題極小點(diǎn)。對(duì)于問(wèn)題〔2.2,構(gòu)造一函數(shù)為〔3.1其中,〔3.2在〔3.2中,又稱為懲罰函數(shù),〔3.3〔3.4是一個(gè)逐漸增大的參數(shù),稱為懲罰因子。又稱為問(wèn)題〔2.2的增廣目標(biāo)函數(shù)。顯然,增廣目標(biāo)函數(shù)是定義在上的一個(gè)無(wú)約束函數(shù)。由增廣目標(biāo)函數(shù)的構(gòu)造知當(dāng)時(shí)〔3.5此時(shí)的最優(yōu)解就是問(wèn)題〔2.2的最優(yōu)解；而當(dāng)時(shí),的最優(yōu)解就不一定是問(wèn)題〔2.2的最優(yōu)解。但是研究時(shí),的最優(yōu)解不是我們所需要的。為此規(guī)定,當(dāng)時(shí),在點(diǎn)處的函數(shù)值迅速變大,換而言之,可行域外的任一點(diǎn)處的函數(shù)值都相當(dāng)大。此時(shí)要求在中的最優(yōu)解,只能讓點(diǎn)回到內(nèi)才有可能,然而一旦點(diǎn)回到內(nèi),即,此時(shí)就與問(wèn)題〔2.2有相同的最優(yōu)解。當(dāng)時(shí),迅速變大的原因是通過(guò)懲罰因子來(lái)實(shí)現(xiàn)。簡(jiǎn)言之,外點(diǎn)罰函數(shù)法的思想是：當(dāng)點(diǎn)時(shí),設(shè)法加大不可行點(diǎn)處的函數(shù)值,使不可行點(diǎn)不能成為在中的最優(yōu)解。在用外點(diǎn)罰函數(shù)法求解問(wèn)題〔2.2時(shí),首先構(gòu)造增廣目標(biāo)函數(shù),然后按照無(wú)約束優(yōu)化方法求解。如果求出的最優(yōu)解為,則判斷是否屬于。如果,則是問(wèn)題〔2.2的最優(yōu)解；如果,則不是問(wèn)題〔2.2的最優(yōu)解,此時(shí)說(shuō)明原來(lái)的懲罰因子給的太小了,需要加大懲罰因子,使得,然后再重新計(jì)算的最優(yōu)值。3.3算法性能分析通過(guò)長(zhǎng)期的理論研究和實(shí)驗(yàn)結(jié)果,人們總結(jié)出懲罰函數(shù)的優(yōu)點(diǎn)有：〔1罰函數(shù)法是解決非線性規(guī)劃問(wèn)題的一種經(jīng)典算法,這種算法簡(jiǎn)單易行、熟練數(shù)度快,在很多實(shí)際問(wèn)題的求解中得到了應(yīng)用?！?計(jì)算效率高,穩(wěn)定性較好。缺點(diǎn)有：〔1罰函數(shù)法對(duì)于有些問(wèn)題只能求出局部最優(yōu)解,而不能求出全局最優(yōu)。〔2對(duì)函數(shù)初值和函數(shù)性態(tài)要求較高。〔3罰函數(shù)法在實(shí)際計(jì)算中的缺點(diǎn)是罰因子的取值難于把握,太小起不到懲罰作用；太大則由于誤差的影響會(huì)導(dǎo)致錯(cuò)誤。在搜索過(guò)程開(kāi)始的時(shí)候,一個(gè)較大的罰因子將會(huì)阻礙非可行域的搜索。另一方面,如果罰因子太小,這樣相對(duì)于目標(biāo)函數(shù)罰函數(shù)項(xiàng)是可以忽略的,則大量的搜索時(shí)間將花費(fèi)在非可行域。這對(duì)于進(jìn)化算法來(lái)說(shuō)非常致命的。3.4外點(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é)果,比較二者性能的差別。3.4.1程序步驟對(duì)于問(wèn)題〔2.2,構(gòu)造一函數(shù)為〔3.6其中,懲罰函數(shù)按照式〔3.2構(gòu)造,給定終止限〔可取。具體過(guò)程描述如下：〔1選定初始點(diǎn),初始懲罰因子〔可取。懲罰因子放大系數(shù),置?！?假設(shè)已獲得迭代點(diǎn),以為初始點(diǎn),求解無(wú)約束問(wèn)題〔3.7設(shè)其最優(yōu)點(diǎn)為?！?若,則就是所要求問(wèn)題的最優(yōu)解,打印,結(jié)束；否則轉(zhuǎn)〔4?！?置,,轉(zhuǎn)〔2。3.4.2程序流程圖外點(diǎn)罰函數(shù)法程序流程圖如圖3-1所示。圖3-1外點(diǎn)罰函數(shù)法程序流程圖4遺傳算法4.1遺傳算法概述遺傳算法的生物學(xué)基礎(chǔ)遺傳算法的生物學(xué)基礎(chǔ)是達(dá)爾文的自然選擇學(xué)說(shuō)。自然選擇學(xué)說(shuō)認(rèn)為,生物要生存下去,就必須進(jìn)行生存斗爭(zhēng)。在生存斗爭(zhēng)中,具有有利變異〔mutation的個(gè)體容易存活下來(lái),并且有更多的機(jī)會(huì)將有利的變異傳給后代；具有不利變異的個(gè)體就容易被淘汰,產(chǎn)生后代的機(jī)會(huì)也少得多。達(dá)爾文把這種在生存斗爭(zhēng)中適者生存,不適者淘汰的過(guò)程叫做自然選擇。達(dá)爾文的自然選擇學(xué)說(shuō)表明,遺傳和變異是決定生物進(jìn)化的內(nèi)在因素。遺傳能使生物的性狀不斷地傳遞給后代,因而保持了物種的特性,變異能夠使生物的性狀發(fā)生改變,從而適應(yīng)新的環(huán)境而不斷地向前發(fā)展[2]。4.1.2遺傳算法的一般結(jié)構(gòu)遺傳算法是一種基于生物自然選擇與遺傳機(jī)理的隨機(jī)搜索算法。和傳統(tǒng)算法不同,遺傳算法從一組隨機(jī)產(chǎn)生的初始解,稱為"種群",開(kāi)始搜索過(guò)程。種群中的每個(gè)個(gè)體是問(wèn)題的一個(gè)解,稱為"染色體"。染色體是一串符號(hào),比如一個(gè)二進(jìn)制字符串。這些染色體在后續(xù)迭代中不斷進(jìn)化,稱為遺傳。在每一代中用"適值"來(lái)測(cè)量染色體的好壞。生成的下一代染色體稱為后代。后代是由前一代染色體通過(guò)交叉或變異運(yùn)算形成的。新一代形成中,根據(jù)適值的大小選擇部分后代,淘汰部分之后,從而保持種群大小是常數(shù)。適值高的染色體被選中的概率較高。這樣,經(jīng)過(guò)若干代之后,算法收斂于最好的染色體,它很可能就是問(wèn)題的最優(yōu)解或者次優(yōu)解。設(shè)和分別表示第t代的雙親和后代,遺傳算法的一般結(jié)構(gòu)可描述如下[3]：遺傳算法過(guò)程：begin；初始化；評(píng)估；while不滿足終止條件dobegin重組獲得；評(píng)估；從和中選擇；；endend圖4-1遺傳算法的一般結(jié)構(gòu)通常初始化是隨機(jī)產(chǎn)生的。重組包括交叉和變異來(lái)獲得后代。實(shí)際上,遺傳算法中有兩類運(yùn)算：〔1遺傳運(yùn)算：交叉和變異；〔2進(jìn)化運(yùn)算：選擇。遺傳運(yùn)算模擬了基因在每一代中創(chuàng)造新后代的繁殖過(guò)程,進(jìn)化運(yùn)算則是種群逐代更新的過(guò)程。4.1.3遺傳算法的特點(diǎn)遺傳算法是一類可用于復(fù)雜系統(tǒng)優(yōu)化的具有魯棒性的搜索算法,與傳統(tǒng)的優(yōu)化算法相比,主要有以下特點(diǎn)[3]：〔1遺傳算法以決策變量的編碼作為運(yùn)算對(duì)象。傳統(tǒng)的優(yōu)化算法往往直接決策變量的實(shí)際植本身,而遺傳算法處理決策變量的某種編碼形式,使得我們可以借鑒生物學(xué)中的染色體和基因的概念,可以模仿自然界生物的遺傳和進(jìn)化機(jī)理,也使得我們能夠方便的應(yīng)用遺傳操作算子?！?遺傳算法直接以適應(yīng)度作為搜索信息,無(wú)需導(dǎo)數(shù)等其它輔助信息。〔3遺傳算法使用多個(gè)點(diǎn)的搜索信息,具有隱含并行性?！?遺傳算法使用概率搜索技術(shù),而非確定性規(guī)則。4.1.4遺傳算法的應(yīng)用遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架,它不依賴于問(wèn)題的具體領(lǐng)域,對(duì)問(wèn)題的種類有很強(qiáng)的魯棒性,所以廣泛應(yīng)用于很多學(xué)科。下面是遺傳算法的一些主要應(yīng)用領(lǐng)域[2][5]：〔1函數(shù)優(yōu)化。函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域,也是對(duì)遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例?！?組合優(yōu)化。隨著問(wèn)題規(guī)模的增大,組合優(yōu)化問(wèn)題的搜索空間也急劇擴(kuò)大,有時(shí)在目前的計(jì)算機(jī)上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。遺傳算法是解決這類問(wèn)題的最佳工具之一。實(shí)踐證明,遺傳算法對(duì)于組合優(yōu)化中的NP完全問(wèn)題非常有效?！?生產(chǎn)調(diào)度問(wèn)題。生產(chǎn)調(diào)度問(wèn)題在許多情況下所建立起來(lái)的數(shù)學(xué)模型難以精確求解,即使經(jīng)過(guò)一些簡(jiǎn)化之后可以進(jìn)行求解,也會(huì)因簡(jiǎn)化得太多而使得求解結(jié)果與實(shí)際相差甚遠(yuǎn)。現(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度問(wèn)題的有效工具,在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用?！?自動(dòng)控制。在自動(dòng)控制領(lǐng)域中有許多與優(yōu)化相關(guān)的問(wèn)題需要求解,遺傳算法已在其中得到了初步的應(yīng)用,并顯示出了良好的效果?！?機(jī)器人智能控制。機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng),而遺傳算法的起源就來(lái)自于對(duì)人工自適應(yīng)系統(tǒng)的研究,所以機(jī)器人智能控制理所當(dāng)然地成為遺傳算法的一個(gè)重要應(yīng)用領(lǐng)域。〔6圖像處理。在圖像處理過(guò)程中,不可避免地會(huì)產(chǎn)生一些誤差,這些誤差會(huì)影響圖像處理的效果。如何使這些誤差最小是使計(jì)算機(jī)視覺(jué)達(dá)到實(shí)用化的重要要求。目前遺傳算法已在模式識(shí)別、圖像恢復(fù)、圖像邊緣特征提取等方面得到了應(yīng)用。〔7人工生命。人工生命與遺傳算法有著密切的關(guān)系,基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要基礎(chǔ)理論。遺傳算法已在進(jìn)化模型、學(xué)習(xí)模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力,并且必將得到更為深入的應(yīng)用和發(fā)展?！?遺傳編程。Koza發(fā)展了遺傳編程的概念,他使用了以LISP語(yǔ)言所表示的編碼方法,基于對(duì)一種樹(shù)型結(jié)構(gòu)所進(jìn)行的遺傳操作來(lái)自動(dòng)生成計(jì)算機(jī)程序?！?機(jī)器學(xué)習(xí)?；谶z傳算法的機(jī)器學(xué)習(xí),在很多領(lǐng)域中都得到了應(yīng)用。4.2遺傳算法實(shí)現(xiàn)的關(guān)鍵技術(shù)1、編碼方法在遺傳算法的運(yùn)行過(guò)程中,它不對(duì)所求解問(wèn)題的實(shí)際決策變量直接進(jìn)行操作,而是對(duì)表示可行解的個(gè)體編碼施加選擇、交叉、變異等遺傳運(yùn)算,通過(guò)這種遺傳操作來(lái)達(dá)到優(yōu)化的目的,這是遺傳算法的特點(diǎn)之一。在遺傳算法中把一個(gè)問(wèn)題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法稱為編碼。常用的編碼方法有：〔1二進(jìn)制編碼：使用由二進(jìn)制符號(hào)0和1所組成的二值符號(hào)集{0,1}進(jìn)行編碼,它所構(gòu)成的個(gè)體基因型是一個(gè)二進(jìn)制編碼符號(hào)串。它是將可行解用固定長(zhǎng)度的二進(jìn)制串表示,串的長(zhǎng)度與問(wèn)題所要求的求解精度有關(guān)。〔2浮點(diǎn)數(shù)編碼：個(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來(lái)表示,個(gè)體的編碼長(zhǎng)度等于其決策變量的個(gè)數(shù)。它所使用的是決策變量的真實(shí)值?！?符號(hào)編碼：個(gè)體染色體編碼串中的基因值取自一個(gè)無(wú)數(shù)值含義、而只有代碼含義的符號(hào)集。這個(gè)符號(hào)集可以是一個(gè)字母表,如{A,B,C,D,…}；也可以是一個(gè)數(shù)字序號(hào)表,如{1,2,3,4,5,…}；還可以是一個(gè)代碼表,如{A1,A2,A3,A4,…}等等。2、適應(yīng)度函數(shù)適應(yīng)度是度量群體中各個(gè)個(gè)體在優(yōu)化計(jì)算中有可能達(dá)到或接近于或有助于找到最優(yōu)解的優(yōu)良程度[2]。遺傳算法的一個(gè)特點(diǎn)是它僅使用所求問(wèn)題的目標(biāo)函數(shù)值就可得到下一步的有關(guān)搜索信息。而對(duì)目標(biāo)函數(shù)值的使用是通過(guò)評(píng)價(jià)個(gè)體的適應(yīng)度來(lái)體現(xiàn)的。評(píng)價(jià)個(gè)體適應(yīng)度的一般過(guò)程是：〔1對(duì)個(gè)體編碼串進(jìn)行解碼處理后,可得到個(gè)體的表現(xiàn)型?！?由個(gè)體的表現(xiàn)型可計(jì)算出對(duì)應(yīng)個(gè)體的目標(biāo)函數(shù)值?！?根據(jù)最優(yōu)化問(wèn)題的類型,由目標(biāo)函數(shù)值按一定的轉(zhuǎn)換規(guī)則求出個(gè)體的適應(yīng)度。3、選擇算子遺傳算法使用遺傳算子〔或稱為復(fù)制算子,ReproductionOperator來(lái)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度較高的個(gè)體被遺傳到下一代群體中的概率較大；適應(yīng)度較低的個(gè)體被遺傳到下一代群體中的概率較小。遺傳算法中的選擇操作就是確定如何從父代群體中按某種方法選取哪些個(gè)體遺傳到下一代群體中的一種遺傳運(yùn)算。遺傳操作建立在對(duì)個(gè)體的適應(yīng)度進(jìn)行評(píng)價(jià)的基礎(chǔ)之上。選擇操作的主要目的是為了避免基因缺失、提高全局收斂性和計(jì)算效率。常見(jiàn)選擇算子：〔1比例選擇：各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。設(shè)群體大小為pop_size,個(gè)體的適應(yīng)度為,則個(gè)體被選中的概率為：〔k=1,2,…,pop_size〔4.1〔2隨機(jī)聯(lián)賽選擇：每次選取幾個(gè)個(gè)體之中適應(yīng)度最高的一個(gè)個(gè)體遺傳到下一代群體中。在聯(lián)賽選擇操作中,只有個(gè)體適應(yīng)度之間的大小比較運(yùn)算,而無(wú)個(gè)體適應(yīng)度之間的算術(shù)運(yùn)算,故它對(duì)個(gè)體適應(yīng)度是取正值還是負(fù)值無(wú)特別要求?！?排序選擇：對(duì)群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行排序,基于這個(gè)排序來(lái)分配各個(gè)個(gè)體被選中的概率。4、交叉算子遺傳算法中的交叉運(yùn)算是指對(duì)兩個(gè)相互配對(duì)的染色體按某種方式相互交換其部分基因,從而形成兩個(gè)新的個(gè)體。它是產(chǎn)生新個(gè)體的主要方法。遺傳算法中,在交叉運(yùn)算之前必須對(duì)群體中的個(gè)體進(jìn)行配對(duì)。常用的配對(duì)策略是隨機(jī)配對(duì),即將群體中的M個(gè)個(gè)體以隨機(jī)的方式組成對(duì)配對(duì)個(gè)體組,交叉操作是在這些配對(duì)個(gè)體組中的兩個(gè)個(gè)體之間進(jìn)行的。常見(jiàn)交叉算子：〔1單點(diǎn)交叉〔One-pointCrossover：在個(gè)體編碼串中只隨機(jī)設(shè)置一個(gè)交叉點(diǎn),實(shí)行交叉時(shí),該點(diǎn)前或后的兩個(gè)個(gè)體的部分結(jié)構(gòu)進(jìn)行互換,并生成兩個(gè)新個(gè)體。〔2雙點(diǎn)交叉〔Two-pointCrossover：在個(gè)體編碼串中隨機(jī)設(shè)置了二個(gè)交叉點(diǎn),進(jìn)行交叉時(shí),將兩個(gè)交叉點(diǎn)之間的部分基因進(jìn)行互換?！?均勻交叉〔UniformCrossover：兩個(gè)配對(duì)個(gè)體的每一個(gè)基因座上的基因以相同的交叉概率進(jìn)行交換,從而形成兩個(gè)新的個(gè)體。5、變異算子遺傳算法中的變異運(yùn)算是指將個(gè)體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來(lái)替換,從而形成一個(gè)新的個(gè)體。遺傳算法導(dǎo)入變異的目的有兩個(gè)：一是使遺傳算法具有局部的隨機(jī)搜索能力。二是使遺傳算法可維持群體多樣性,以防止出現(xiàn)未成熟收斂現(xiàn)象。變異算子的操作步驟：在群體中所有個(gè)體的碼串范圍內(nèi)隨機(jī)地確定基因座。以事先設(shè)定的變異概率Pm來(lái)對(duì)這些基因座的基因值進(jìn)行變異。常見(jiàn)變異算子：〔1基本位變異〔SimpleMutation是指對(duì)個(gè)體編碼串中以變異概率Pm隨機(jī)指定的某一位基因座上的基因值作變異運(yùn)算?！?均勻變異〔UniformMutation是指分別用符合某一范圍內(nèi)均勻分布的隨機(jī)數(shù),以某一較小的概率來(lái)替換個(gè)體編碼串中各個(gè)基因座上的原有基因值?！?逆轉(zhuǎn)算子〔InversionOperator在個(gè)體碼串中隨機(jī)挑選二個(gè)逆轉(zhuǎn)點(diǎn),然后將兩個(gè)逆轉(zhuǎn)點(diǎn)間的基因值以逆轉(zhuǎn)概率Pi逆向排序。6、遺傳算法的運(yùn)行參數(shù)〔1編碼串長(zhǎng)度L。使用二進(jìn)制編碼時(shí),L與問(wèn)題所要求的求解精度有關(guān)；使用浮點(diǎn)數(shù)編碼時(shí),L與決策變量的個(gè)數(shù)n相等；使用符號(hào)編碼是,L由問(wèn)題的編碼方式確定?！?群體大小pop_size。pop_size表示群體中所含個(gè)體的數(shù)量。當(dāng)pop_size取值較小時(shí),可提高遺傳算法的運(yùn)算速度,卻降低了群體的多樣性,有可能會(huì)引起遺傳算法的早熟現(xiàn)象；當(dāng)pop_size取值較大時(shí),又會(huì)使遺傳算法的運(yùn)行效率降低?！?交叉概率Pc。交叉操作是遺傳算法中產(chǎn)生新個(gè)體的主要方法,所以Pc取值較大。但若過(guò)大的話,又會(huì)破壞群體中的優(yōu)良模式,對(duì)進(jìn)化運(yùn)算產(chǎn)生不利影響；若過(guò)小的話,產(chǎn)生新個(gè)體的速度又較慢。建議取值范圍是0.4～0.99。〔4變異概率Pm。Pm取值過(guò)大,雖然能夠產(chǎn)生較多的新個(gè)體,但也可能破壞掉很多較好的模式,使得遺傳算法的性能近似于隨機(jī)搜索算法的性能；若Pm過(guò)小,則變異操作產(chǎn)生新個(gè)體的能力和抑制早熟現(xiàn)象的能力就會(huì)較差。一般建議取值范圍是0.0001～0.2?！?終止代數(shù)T。T表示遺傳算法運(yùn)行到指定的進(jìn)化代數(shù)之后就停止運(yùn)行,并將當(dāng)前群體中的最佳個(gè)體作為所求問(wèn)題的最優(yōu)解輸出。一般建議取值范圍是100～1000。5求解非線性規(guī)劃問(wèn)題的遺傳算法設(shè)計(jì)傳統(tǒng)的非線性規(guī)劃算法的缺陷是計(jì)算煩瑣且精度不高,穩(wěn)定性差,對(duì)函數(shù)初值和函數(shù)性態(tài)要求較高,且容易陷入局部最優(yōu)解。而遺傳算法是一種全局搜索算法,可以克服傳統(tǒng)的非線性規(guī)劃算法容易陷入局部最優(yōu)解的缺陷。因此,將遺傳算法應(yīng)用于非線性規(guī)劃,是改善收斂效果,提高最優(yōu)化質(zhì)量的有效途徑。本章就是介紹遺傳算法在非線性規(guī)劃中的具體應(yīng)用,設(shè)計(jì)并實(shí)現(xiàn)求解非線性規(guī)劃問(wèn)題的遺傳算法。5.1實(shí)用遺傳算法設(shè)計(jì)1、編碼方法設(shè)計(jì)非線性規(guī)劃屬于最優(yōu)化設(shè)計(jì)的一種,屬于約束優(yōu)化問(wèn)題,其最終目的是選擇一種方法,使目標(biāo)函數(shù)在滿足約束的條件下達(dá)到最優(yōu)。從非線性規(guī)劃的數(shù)學(xué)模型可知,我們最終要求解的是一組解,其滿足約束條件,并使目標(biāo)函數(shù)達(dá)到最小值<或最大值>。我們將這組解作為染色體,其中每個(gè)相當(dāng)于染色體上的基因,這也就是編碼對(duì)象。之后的選擇,交叉,變異就是對(duì)編碼后的染色體基因進(jìn)行運(yùn)算。我們最終所求的解是n維向量空間的某子集〔定義域上的一個(gè)實(shí)數(shù),若采用傳統(tǒng)的二進(jìn)制編碼,則編碼串長(zhǎng)度不固定。如果采用固定長(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ú)效解。而且采用二進(jìn)制編碼,又要牽涉到十進(jìn)制與二進(jìn)制的轉(zhuǎn)換,在實(shí)際操作過(guò)程中要頻繁進(jìn)行編碼和解碼操作,費(fèi)時(shí)費(fèi)力。所以我們直接采用實(shí)數(shù)編碼,即染色體基因串中基因座的值直接是每組解中各分量的實(shí)數(shù)值,不再對(duì)其進(jìn)行其他任何形式的編碼。每個(gè)染色體編碼為一個(gè)和解向量維數(shù)相同的實(shí)向量[2]。2、適應(yīng)度函數(shù)設(shè)計(jì)1滿足約束由于對(duì)染色體作遺傳運(yùn)算時(shí)通常獲得不可行的后代,因此運(yùn)用遺傳算法解非線性規(guī)劃問(wèn)題的核心問(wèn)題是如何滿足約束的問(wèn)題。今年來(lái),已經(jīng)提出了幾種運(yùn)用遺傳算法滿足約束的技術(shù),這些技術(shù)大致可以分為以下幾類[3][16]：〔1拒絕策略拒絕策略拋棄所有進(jìn)化過(guò)程中產(chǎn)生的不可行的染色體。這是遺傳算法中普遍的作法。當(dāng)可行的搜索空間是凸的,且為整個(gè)搜索空間的適當(dāng)?shù)囊徊糠謺r(shí),這種方法應(yīng)該是有效的。然而,這是很嚴(yán)格的限制。例如,對(duì)許多約束優(yōu)化問(wèn)題初始種群可能全由非可行染色體構(gòu)成,這就需要對(duì)他們進(jìn)行修補(bǔ)。對(duì)于某些系統(tǒng)〔特別是可行搜索空間非凸時(shí),允許跨過(guò)不可行域修復(fù)往往更容易達(dá)到最優(yōu)解?！?修復(fù)策略修補(bǔ)染色體是對(duì)不可行染色體采用修復(fù)程序使之變?yōu)榭尚械?。?duì)于許多組合優(yōu)化問(wèn)題,構(gòu)造修復(fù)程序相對(duì)比較容易。Liepins和他的合作者通過(guò)對(duì)遺傳算法的性能試驗(yàn)測(cè)試證明,對(duì)于一個(gè)有多個(gè)不連通可行集的約束組合優(yōu)化問(wèn)題,修復(fù)策略在速度和計(jì)算性能上都遠(yuǎn)勝過(guò)其他策略。修復(fù)策略取決于是否存在一個(gè)可將不可行后代轉(zhuǎn)化為可行的修復(fù)程序。該方法的缺點(diǎn)是它對(duì)問(wèn)題本身的依賴性,對(duì)于每個(gè)具體問(wèn)題必須設(shè)計(jì)專門的修復(fù)程序。對(duì)于某些問(wèn)題,修復(fù)過(guò)程甚至比原問(wèn)題的求解更復(fù)雜。修復(fù)后的染色體可以只用來(lái)作評(píng)估,也可用來(lái)替代原染色體進(jìn)入種群。Liepins等采用永不替代法,即不讓修復(fù)過(guò)的染色體進(jìn)入種群；而Nakano和Yamada采用了始終替代法。最近,Orvosh和Davis提出了所謂的5%規(guī)則：該規(guī)則對(duì)于多數(shù)組合優(yōu)化問(wèn)題,若令5%的修復(fù)過(guò)的染色體替代原染色體,則帶有修復(fù)程序的遺傳算法可取得最好的效果。Michalewicz等則認(rèn)為對(duì)有非線性約束的優(yōu)化問(wèn)題,15%的替代率為最好?！?改進(jìn)遺傳算子策略解決可行性問(wèn)題的一個(gè)合理辦法是設(shè)計(jì)針對(duì)問(wèn)題的表達(dá)方式以及專門的遺傳算子來(lái)維持染色體的可行性。Michalewicz等指出這種方法通常比基于懲罰的遺傳算法更可靠。許多領(lǐng)域中的實(shí)際工作者采用專門的問(wèn)題表達(dá)方式和遺傳算子構(gòu)造了非常成功的遺傳算法,這已是一個(gè)普遍的趨勢(shì)。但是,該方法的遺傳搜索收到了可行域的限制?！?懲罰策略上面三種策略的共同優(yōu)點(diǎn)是都不會(huì)產(chǎn)生不可行解,缺點(diǎn)則是無(wú)法考慮可行域外的點(diǎn)。對(duì)于約束嚴(yán)的問(wèn)題,不可行解在種群中的比例很大。這樣,將搜索限制在可行域內(nèi)就很難找到可行解。Glover和Greenberg建議的約束管理技術(shù)允許在搜索空間里的不可行域中進(jìn)行搜索,這比將搜索限制在可行域內(nèi)的方法能更快地活的最優(yōu)解或獲得更好的最終解。懲罰策略就是這類在遺傳搜索中考慮不可行解的技術(shù)。2懲罰函數(shù)懲罰函數(shù)大概是用遺傳算法解約束優(yōu)化問(wèn)題中最常用的技術(shù)。本質(zhì)上它是通過(guò)懲罰不可行解將約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題。在遺傳算法中,懲罰技術(shù)用來(lái)在每代的種群中保持部分不可行解,使遺傳搜索可以從可行域和不可行域兩邊來(lái)達(dá)到最優(yōu)解。一般,解空間包含兩部分：可行域和不可行域。我們不能對(duì)這些子空間作任何假設(shè),特別是當(dāng)它們是非凸或非連通時(shí),如圖5-1所示?？刂品强尚械娜旧w遠(yuǎn)不是一件容易事,從圖5-1可知,不可行解b與最優(yōu)解a的距離比不可行解d和可行解c都近。我們希望給b較小懲罰。可以相信,盡管b是不可行解,但它比c含有更多的有關(guān)最優(yōu)點(diǎn)的信息。然而,我們對(duì)最優(yōu)點(diǎn)沒(méi)有任何先驗(yàn)知識(shí),所以一般很難判斷哪一點(diǎn)更好。圖5-1解空間：可行域與不可行域懲罰策略的主要問(wèn)題是如何設(shè)計(jì)一個(gè)懲罰函數(shù),從而能有效地引導(dǎo)遺傳搜索達(dá)到解空間的最好區(qū)域。不可行染色體和解空間可行部分的關(guān)系在懲罰不可行染色體中起了關(guān)鍵作用：不可行染色體的懲罰值相應(yīng)于某種測(cè)試下的不可行性的"測(cè)量"。設(shè)計(jì)懲罰函數(shù)沒(méi)有一般規(guī)則,這仍要依賴于待解的問(wèn)題。懲罰技術(shù)通過(guò)懲罰不可行解將約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題。構(gòu)造帶有懲罰項(xiàng)的適應(yīng)度函數(shù)的方法一般有兩種[3][9]用加法形式：〔5.1其中,x代表染色體；是問(wèn)題的目標(biāo)函數(shù)；是懲罰項(xiàng)。對(duì)于極大化問(wèn)題,取〔5.2令和分別為現(xiàn)行種群中的的最大值和的最小值。并要求≤以避免出現(xiàn)負(fù)的適值。對(duì)于極小化問(wèn)題,則取〔5.3另一種方法是采用乘法形式：〔5.4這時(shí),極大化問(wèn)題可取為〔5.5求極小化問(wèn)題則取〔5.6本文中我們采用的是加法形式的懲罰。由于目標(biāo)函數(shù)是求最小,較好的染色體具有較低的適值,因此我們?nèi)≥^大的數(shù)作為懲罰項(xiàng),降低其被選中的概率。本文中選擇的懲罰函數(shù)為：=-1*<<0>.**1e+3。當(dāng)不滿足約束時(shí),也就是小于0時(shí),括號(hào)里的邏輯運(yùn)算結(jié)果為1,由于約束是要求大于等于0,則要對(duì)其進(jìn)行懲罰,乘以-1相當(dāng)于對(duì)取絕對(duì)值,再乘以一個(gè)較大的數(shù)1e+3,則此時(shí)為一個(gè)較大的實(shí)數(shù),實(shí)現(xiàn)了其懲罰作用。當(dāng)滿足約束時(shí),大于等于0,此時(shí)括號(hào)里的結(jié)果為0,也為0,即不對(duì)其進(jìn)行懲罰。滿足公式〔5.4。然后再根據(jù)公式〔5.1,將懲罰函數(shù)加入目標(biāo)函數(shù),也就是將約束條件加入目標(biāo)函數(shù),確定適應(yīng)度函數(shù)[3][8]。3、選擇算子設(shè)計(jì)遺傳算法使用遺傳算子來(lái)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作。我們采用最常見(jiàn)的比例選擇算子,這是一種回放式隨機(jī)采樣的方法。其基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。多數(shù)情況下采用轉(zhuǎn)輪法作為選擇方法。它是一種正比選擇策略,能夠根據(jù)與適值成正比的概率選擇出新的種群。轉(zhuǎn)輪法由以下步驟構(gòu)成：〔1對(duì)各個(gè)染色體計(jì)算適值=；k=1,2,…,pop_size〔5.7〔2計(jì)算種群中所有染色體的適值和〔5.8〔3對(duì)各染色體,計(jì)算選擇概率；k=1,2,…,pop_size〔5.9〔4對(duì)各染色體,計(jì)算累積概率；k=1,2,…,pop_size〔5.10選擇過(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è)染色體〔,使得成立。4、交叉算子設(shè)計(jì)雖然是實(shí)數(shù)編碼,不過(guò)也可以模仿二進(jìn)制表達(dá)的交叉。常用的交叉有單點(diǎn)交叉,雙點(diǎn)、多點(diǎn)交叉等。考慮到算法效率和實(shí)現(xiàn)便捷程度,我們采用雙點(diǎn)交叉。令雙親為和,隨機(jī)生成1到n之間的兩個(gè)數(shù)i和j,若兩數(shù)不相等,則可作為交叉點(diǎn)。將產(chǎn)生的兩個(gè)隨機(jī)數(shù)之間的部分交叉,產(chǎn)生的后代為和。例如：現(xiàn)在依據(jù)選擇算子選擇了兩條配對(duì)染色體：Chromosome1=[1,2,3,4,5],Chromosome2=[6,7,8,9,10]。若隨機(jī)生成的交叉點(diǎn)為2和5,則將第2號(hào)和第5號(hào)位置之間的基因值互換,交叉后產(chǎn)生的新染色體為：NewChromosome1=[1,2,8,9,5],NewChromosome2=[6,7,3,4,10]。5、變異算子設(shè)計(jì)由于染色體基因較少,我們采用均勻變異：對(duì)每一個(gè)基因以一個(gè)指定的變異概率進(jìn)行變異,若符合變異條件,則用一個(gè)隨機(jī)產(chǎn)生的值替換原有的基因值。由于我們進(jìn)行變異的粒度較小,為了增大變異力度,所以我們指定的變異概率較大,Pm=0.2。例如：對(duì)染色體Chromosome=[1,2,3,4,5]進(jìn)行變異,從1號(hào)位基因開(kāi)始,每次隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)x,若這個(gè)隨機(jī)數(shù)x<Pm,則進(jìn)行變異,在指定范圍內(nèi)隨機(jī)產(chǎn)生一個(gè)實(shí)數(shù),來(lái)替換掉1號(hào)基因位的值；若x>Pm,則本次不進(jìn)行變異,繼續(xù)對(duì)2號(hào)位基因值進(jìn)行變異操作,直到5號(hào)位結(jié)束。由此就產(chǎn)生了新的染色體。6、遺傳算子運(yùn)行參數(shù)設(shè)計(jì)〔1編碼長(zhǎng)度。由于我們采用實(shí)數(shù)編碼,即染色體基因串中基因座的值直接是每組解中各分量的實(shí)數(shù)值,每個(gè)染色體編碼為一個(gè)和解向量維數(shù)相同的實(shí)向量。本文中有7個(gè)決策變量,因此染色體長(zhǎng)度,也就是編碼長(zhǎng)度取7?！?種群大小pop_size。種群大小pop_size表示種群中所含個(gè)體的數(shù)量。pop_size取值的大小與遺傳算法運(yùn)行速度,種群多樣性有關(guān)。一般根據(jù)問(wèn)題規(guī)模而定,這里我們?nèi)?00?！?交叉概率Pc。交叉操作是遺傳算法中產(chǎn)生新個(gè)體的主要方法。若Pc過(guò)大,會(huì)破壞群體中的優(yōu)良模式,對(duì)進(jìn)化運(yùn)算產(chǎn)生不利影響；若Pc過(guò)小,產(chǎn)生新個(gè)體的速度又較慢。我們?yōu)榱双@得較大的種群多樣性,產(chǎn)生較多的新個(gè)體,Pc值取為0.8。〔4變異概率Pm。變異操作是為了保證遺傳算法具有局部搜索能力,同時(shí)也能保證群體多樣性,抑制早熟現(xiàn)象。若Pm取值過(guò)大,雖然能夠產(chǎn)生較多的新個(gè)體,但也可能破壞掉很多較好的模式,使得遺傳算法的性能近似于隨機(jī)搜索算法的性能；若Pm取值過(guò)小,則變異操作產(chǎn)生新個(gè)體的能力和抑制早熟現(xiàn)象的能力就會(huì)較差。這里由于是對(duì)每個(gè)基因座進(jìn)行變異操作,為了保證變異效果,Pm取值較大,為0.2?！?終止代數(shù)T。為保證遺傳算法能獲得近似最優(yōu)解,T取值為150。即遺傳算法迭代150次停止,將得到的最佳個(gè)體作為最優(yōu)解輸出。5.2求解非線性規(guī)劃問(wèn)題的遺傳算法程序設(shè)計(jì)算法過(guò)程描述由前面遺傳算法的算法描述再結(jié)合本次畢業(yè)設(shè)計(jì)的實(shí)際情況,我們?cè)O(shè)計(jì)了以下的具體算法流程[3][9][16]。步驟如下：〔1初始化遺傳算法的運(yùn)行參數(shù)：種群大小pop_size,每條染色體基因串長(zhǎng)度length,交叉概率Pc,變異概率Pm,算法迭代次數(shù)T,當(dāng)前迭代次數(shù)t?！?根據(jù)所給x的范圍,種群大小,染色體長(zhǎng)度,隨機(jī)生成符合條件的初始種群A?！?將約束條件加入目標(biāo)函數(shù),確定適應(yīng)度函數(shù),計(jì)算適值e?！?對(duì)適值e從小到大排序,排序后的適值記為s,并記錄變動(dòng)情況l?！?根據(jù)排序結(jié)果把每一代最小適值賦給M,并記錄局部最優(yōu)值對(duì)應(yīng)的位置〔行,用的行向量B表示?！?輸出每次迭代t對(duì)應(yīng)的局部極值位置B和局部最優(yōu)值s<1>?！?計(jì)算累積概率。〔8用轉(zhuǎn)輪法進(jìn)行選擇運(yùn)算。種群由A進(jìn)化為A1?！?雙點(diǎn)交叉實(shí)現(xiàn)交叉運(yùn)算。實(shí)現(xiàn)遺傳算法的第一次遺傳運(yùn)算,種群更新為A2?！?0均勻變異實(shí)現(xiàn)變異過(guò)程。實(shí)現(xiàn)第二次遺傳運(yùn)算,種群更新為A3?！?1更新種群,將A3賦給A?！?2判斷是否滿足迭代結(jié)束條件。滿足轉(zhuǎn)〔13,不滿足轉(zhuǎn)〔3,繼續(xù)迭代?！?3對(duì)每代最小適值M排序,me為排序后的向量?！?4輸出最小適值Min,即為所求全局最優(yōu)。遺傳算法程序流程圖圖5-2求解非線性規(guī)劃問(wèn)題的遺傳算法程序流程圖5.2.3遺傳算法中所設(shè)計(jì)的輔助算法的設(shè)計(jì)〔1隨機(jī)數(shù)生成。程序中多處涉及到隨機(jī)數(shù)的生成,像一開(kāi)始初始種群的生成,后面的選擇、交叉、變異的循環(huán)條件判斷,都有用到。這里我們使用常用的rand函數(shù)。rand函數(shù)的作用是生成0～1之間的浮點(diǎn)型矩陣,通過(guò)對(duì)函數(shù)的簡(jiǎn)單運(yùn)算可以生成我們想要的確定范圍內(nèi)的矩陣?！?累加函數(shù)cunsum。程序中計(jì)算累積概率部分,可以使用循環(huán)運(yùn)算實(shí)現(xiàn),但我們使用MATLAB中更便捷的函數(shù)cumsum直接計(jì)算元素累加,如a=[1234],則cumsum<a>=[13610]?！?上取整函數(shù)ceil。ceil<>是向正無(wú)窮大舍入,如ceil<2.5>=3,配合rand函數(shù)可以隨機(jī)生成一定范圍內(nèi)的整數(shù)。〔4排序函數(shù)。因?yàn)槲覀兯笫亲钚』瘑?wèn)題,在龐大的種群和多次迭代過(guò)程中為方便找出局部最小值和全局最優(yōu)值,我們可以對(duì)每次結(jié)果進(jìn)行排序。sort函數(shù)實(shí)現(xiàn)按升序排序,如[s,l]=sort<e>,對(duì)e從小到大進(jìn)行排序,s為排序后的矩陣,l為變動(dòng)情況。〔5選擇函數(shù)。選擇函數(shù)是為交叉操作從當(dāng)前種群中選擇兩條染色體來(lái)進(jìn)行交叉操作。我們采用轉(zhuǎn)輪法〔RouletteWheel來(lái)選擇染色體。具體過(guò)程如下：=1\*GB3①利用rand函數(shù)產(chǎn)生一個(gè)0～1之間的隨機(jī)數(shù)r。=2\*GB3②從第一條染色體起,將當(dāng)前種群中各染色體的選擇概率進(jìn)行累加,當(dāng)選擇概率總和大于等于rand時(shí)停止。=3\*GB3③累加結(jié)束時(shí)的染色體〔即概率之和剛好大于隨機(jī)數(shù)rand的那條染色體即為被選中的染色體。6算法的結(jié)果分析6.1概述在以上算法分析設(shè)計(jì)的基礎(chǔ)上,我們用MATLAB語(yǔ)言分別實(shí)現(xiàn)了求解非線性規(guī)劃問(wèn)題的遺傳算法和外點(diǎn)罰函數(shù)法。本章我們通過(guò)運(yùn)行實(shí)際的算法程序,通過(guò)對(duì)運(yùn)行結(jié)果進(jìn)行統(tǒng)計(jì)分析,比較兩種算法各自的優(yōu)越性。6.2結(jié)果比較為了能直觀地表現(xiàn)兩種算法的實(shí)際執(zhí)行結(jié)果,我們將兩種算法的執(zhí)行結(jié)果以圖表的形式直觀地表達(dá)出來(lái)。兩種算法的計(jì)算結(jié)果如表6-1,6-2所示。我們通過(guò)統(tǒng)計(jì)兩種算法所得最優(yōu)值的變化,來(lái)比較兩種算法的收斂效果。為了充分比較兩種算法收斂效果,我們對(duì)遺傳算法分別采用大小為300和200的兩個(gè)種群,懲罰函數(shù)法分別取初始懲罰因子M為10和1,兩種算法分別執(zhí)行算法10次,得到結(jié)果如表6-1所示。表6-1最優(yōu)適值表遺傳算法懲罰函數(shù)法執(zhí)行序號(hào)種群300種群200初始懲罰因子M=10初始懲罰因子M=11703.678340689.693431711.150702737.2106052701.530725724.697202817.991629685.3209413702.253432707.968223762.156619749.3026324703.625196713.398107682.4467671497.2846835698.693085717.147253784.342585691.9136556705.082156703.719043685.732024711.1507027714.335545704.113105736.895652817.9916298690.639063719.278202681.898495762.1566199694.401838692.633396684.731999682.44676710704.034177697.344160791.385667784.342585我們統(tǒng)計(jì)兩種算法之間的最大值、最小值、均值和方差。得到表6-2。表6-2均值和方差表遺傳算法懲罰函數(shù)法種群300種群200初始懲罰因子M=10初始懲罰因子M=1最大值714.335545724.697202817.9916291497.284683最小值690.639063689.693431681.898495682.446767均值701.83706.9992733.87811.9121方差40.9985136.33732703.859983.06我們將表6-1中的數(shù)據(jù)以圖的形式進(jìn)行表示,得到兩種算法取得最優(yōu)適應(yīng)度值的變化曲線,如下圖所示。圖6-1遺傳算法最優(yōu)值變化曲線圖6-2懲罰函數(shù)法最優(yōu)值變化曲線圖6-3綜合比較曲線從表6-2可以看出,遺傳算法所得最優(yōu)適值的最大值、平均值、方差要比懲罰函數(shù)法小得多,說(shuō)明遺傳算法收斂效果更好,結(jié)果更合理；圖6-1和圖6-2說(shuō)明兩個(gè)算法對(duì)自身參數(shù)設(shè)定的敏感性,可以看出相對(duì)于懲罰函數(shù)法,遺傳算法受初始參數(shù)影響要小很多；圖6-3綜合比較曲線將兩個(gè)算法結(jié)果放在一個(gè)圖中比較,可以看出,遺傳算法的變化曲線非常平穩(wěn),波動(dòng)較小,而懲罰函數(shù)法對(duì)初始參數(shù)特別敏感,出現(xiàn)了大的波動(dòng)。這充分體現(xiàn)了遺傳算法的優(yōu)越性,遺傳算法的全局搜索能力使其能夠不受初始點(diǎn)的影響而找到近似全局最優(yōu)解。通過(guò)以上分析可以看出,求解非線性規(guī)劃問(wèn)題的遺傳算法能夠克服傳統(tǒng)算法對(duì)初始值敏感,容易陷入局部最優(yōu)解的缺陷,收斂效果更好,性能更穩(wěn)定,結(jié)果更合理。同時(shí)我們比較兩種算法的運(yùn)行時(shí)間,如下表。表6-3運(yùn)行時(shí)間比較表遺傳算法懲罰函數(shù)法種群300種群200初始懲罰因子M=10初始懲罰因子M=1最大值3.0310002.0470000.2340000.203000最小值2.9060001.8910000.1250000.140000均值2.951501.96120.172000.156100從表中可以看出,懲罰函數(shù)法在運(yùn)行時(shí)間上明顯優(yōu)于遺傳算法,說(shuō)明傳統(tǒng)算法也有其可取優(yōu)勢(shì),不可能被完全取代。下圖即為求解非線性規(guī)劃問(wèn)題的遺傳算法最優(yōu)適值變化曲線：圖6-4求解非線性規(guī)劃問(wèn)題的遺傳算法最優(yōu)適值變化曲線7總