nsga—ii的改進(jìn)算法研究畢業(yè)論文(存儲(chǔ)版)

　　

【正文】 雜度由原來(lái)的降為（為目標(biāo)函數(shù)的個(gè)數(shù)，為種群的大小）。在這一步中，所有在第一個(gè)非支配層中的個(gè)體都被尋找到，為了找到隨后各個(gè)等級(jí)中的個(gè)體，重復(fù)前面的操作。為了克服NSGA算法中的這種不足，NSGAII中引用了擁擠度的概念[16]：擁擠度表示在種群中給定點(diǎn)的周?chē)鷤€(gè)體的密度，用表示，直觀上用個(gè)體周?chē)瑐€(gè)體但不包含其余個(gè)體的最大長(zhǎng)方形的長(zhǎng)來(lái)表示，具體如圖31所示。NSGAII算法引入了精英策略，以防止在種群的進(jìn)化過(guò)程中優(yōu)秀個(gè)體的流失，通過(guò)將父代種群與其產(chǎn)生的子代種群混合后進(jìn)行非支配排序的方法，能夠有較好地避免父代種群中優(yōu)秀個(gè)體的流失。 NSGAII算法的擁擠度距離公式改進(jìn)在傳統(tǒng)的NSGAII算法中，如果種群規(guī)模大小為N，當(dāng)前非支配集大小為M，并且有MN。也就是說(shuō)，在一次種群維護(hù)中，種群中個(gè)體的擁擠度距離只計(jì)算一次。2) 對(duì)中的個(gè)體按新?lián)頂D度距離進(jìn)行升序排序。 NSGAII算法流程N(yùn)SGAII算法的基本流程是：首先，隨機(jī)產(chǎn)生種群規(guī)模大小為的父代種群，然后由父代種群產(chǎn)生子代種群，其種群規(guī)模大小同樣為。（41）在式（41）中，和分別是目標(biāo)函數(shù)和約束函數(shù)，它們?yōu)殛P(guān)于設(shè)計(jì)變量x與不確定參數(shù)u的非線性連續(xù)函數(shù)。由圖可知，在4種不同的可能度水平下，獲得不同的Pareto解集。圖43 不同多目標(biāo)權(quán)系數(shù)β下的Pareto前沿在不同的β值下，可以獲得到不同的目標(biāo)函數(shù)和約束函數(shù)的區(qū)間。 交叉參數(shù)mu與變異參數(shù)mum的影響在遺傳算法中，交叉和變異是最重要的兩個(gè)算子。 本章小結(jié)本章首先給出了區(qū)間數(shù)多目標(biāo)優(yōu)化的matlab仿真代碼的最終優(yōu)化結(jié)果，然后便對(duì)算法中的重要算子進(jìn)行分析，通過(guò)給出各個(gè)不同參數(shù)下的仿真結(jié)果，分析每個(gè)參數(shù)取值對(duì)最終優(yōu)化結(jié)果的影響。 接下來(lái)，分析在給定變異參數(shù)mum=20，交叉參數(shù)mu作不同取值（mu=0，20，5000）時(shí)的最終結(jié)果。下面列出當(dāng)λ=0，β=1時(shí)，正則化因子取值分別是，和時(shí)的最終優(yōu)化結(jié)果。 多目標(biāo)權(quán)系數(shù)β的選取本節(jié)將討論相同目標(biāo)函數(shù)在不同多目標(biāo)權(quán)系數(shù)β取值下的優(yōu)化結(jié)果，進(jìn)而得出多目標(biāo)權(quán)系數(shù)β對(duì)最終優(yōu)化結(jié)果的影響。下面是在權(quán)系數(shù)β=1下，可能度水平取值分別為λ=0，λ=，λ=，λ=。最后，文章介紹了NSGAII算法的基本流程后，給出算法的程序流程圖。2) 由于使用式(32)來(lái)計(jì)算個(gè)體的，在式中不僅考慮了種群個(gè)體之間的擁擠情況，而且還考慮了種群個(gè)體在不同維目標(biāo)上擁擠度距離的差異情況。下面討論基于新?lián)頂D度距離保持解的多樣性策略的具體描述。而對(duì)于個(gè)體F，由于其在各個(gè)維目標(biāo)上的差值都相差不是很大，使得F的擁擠度距離也比較大，此時(shí)傳統(tǒng)NSGAII算法會(huì)誤認(rèn)為F的分布性比B要好，但事實(shí)上，B的分布性要比F好。在NSGAII算法中，通過(guò)引入擁擠度比較算子來(lái)確保非劣解的多樣性。條件2是根據(jù)它們的擁擠距離來(lái)選擇處在相同的非支配層的兩個(gè)個(gè)體，位于較不擁擠區(qū)域的個(gè)體（有較大的擁擠度）會(huì)被選擇。于是，整個(gè)迭代過(guò)程的計(jì)算復(fù)雜度最大是。下面，簡(jiǎn)要說(shuō)明二者計(jì)算復(fù)雜度的由來(lái)：（1） 非支配排序算法的計(jì)算復(fù)雜度：為了對(duì)優(yōu)化對(duì)象的個(gè)數(shù)為m，種群規(guī)模大小為N的種群進(jìn)行非支配排序，每一個(gè)個(gè)體都必須和種群中其它的個(gè)體進(jìn)行比較，從而得出該個(gè)體是否被支配，這樣每個(gè)個(gè)體就總共需要次的比較，需要O（）的計(jì)算復(fù)雜度。3) 需要指定共享參數(shù)，在NSGA算法中保持種群和解的多樣性方法都是依賴于共享的概念，共享的主要問(wèn)題之一就是需要人為指定一個(gè)共享參數(shù)。NSGA算法是在上世紀(jì)90年代初期由Srinivas和Deb教授首先提出的，該算法是基于對(duì)種群中所有的個(gè)體按照不同的層次進(jìn)行分類(lèi)的。所以在本文中，一律把類(lèi)似于式(248)的問(wèn)題稱為無(wú)約束優(yōu)化問(wèn)題。針對(duì)任一設(shè)計(jì)變量，因?yàn)椴淮_定參數(shù)的存在，并且目標(biāo)函數(shù)為的連續(xù)函數(shù)，所以的可能取值是在一定范圍內(nèi)的區(qū)間： （238）式中， （239） （240）基于(231)式表述的區(qū)間序關(guān)系，可以通過(guò)目標(biāo)函數(shù)區(qū)間的中點(diǎn)和半寬來(lái)判斷不同的設(shè)計(jì)變量之間的優(yōu)劣：設(shè)計(jì)變量?jī)?yōu)于，則處的目標(biāo)函數(shù)的區(qū)間優(yōu)于處的目標(biāo)函數(shù)的區(qū)間，即并且。對(duì)于最大化和最小化的優(yōu)化問(wèn)題，同一區(qū)間序關(guān)系可以具有不同的表述形式，因?yàn)樵谶@兩種問(wèn)題中它們的評(píng)價(jià)指標(biāo)并不相同，例如在最大化問(wèn)題中目標(biāo)函數(shù)的函數(shù)值大的決策變量為優(yōu)，而在最小化問(wèn)題中剛好相反，目標(biāo)函數(shù)的函數(shù)值小的決策變量為優(yōu)。對(duì)于型的不等式約束函數(shù)，如，可以簡(jiǎn)單地將其轉(zhuǎn)換為型約束來(lái)進(jìn)行處理： （223）上式中，通過(guò)公式(216)或公式(218)進(jìn)行求解。4) 若，則區(qū)間等于區(qū)間，即=。如對(duì)于圖22中的第二種情況，在和之間的概率為，而此時(shí)不管取值多少的概率都為l；在和間的概率，在和之間的概率為，此時(shí)的概率為50%。所以，上述問(wèn)題無(wú)法通過(guò)傳統(tǒng)的確定性優(yōu)化方法來(lái)進(jìn)行求解，因?yàn)樵趥鹘y(tǒng)的確定性優(yōu)化方法中，決策的選擇和判斷都是建立在目標(biāo)函數(shù)和約束函數(shù)在各個(gè)設(shè)計(jì)變量處的具體數(shù)值的基礎(chǔ)上進(jìn)行的。對(duì)于這樣復(fù)雜的非線性優(yōu)化問(wèn)題，要找到在要求的空間中有好的多樣性的一組解也是一項(xiàng)非常重要的任務(wù)。因而，在多目標(biāo)優(yōu)化中主要完成以下兩個(gè)任務(wù)：1) 找到一組盡可能接近Pareto最優(yōu)域的解。非劣解也成為有效解(Efficient Solution)、非支配解(Nondominated Solution)、Pareto最優(yōu)解(Pareto Optimal Solution)或Pareto解，它是多目標(biāo)優(yōu)化中的一個(gè)最基本的概念。（向量序） 設(shè)是維歐氏空間中的兩個(gè)向量。約束給出了設(shè)計(jì)變量需要滿足的限制條件，用含有等式和不等式的約束函數(shù)來(lái)表示。 多目標(biāo)優(yōu)化的數(shù)學(xué)描述一般來(lái)講，多目標(biāo)優(yōu)化問(wèn)題是由多個(gè)目標(biāo)函數(shù)與有關(guān)的一些等式以及不等式約束組成，從數(shù)學(xué)角度可以做如下描述[8]： （21）式中，函數(shù)稱為目標(biāo)函數(shù)；和稱為約束函數(shù)；是維的設(shè)計(jì)變量。 本文的研究目標(biāo)和主要研究?jī)?nèi)容綜上所述，在目前的區(qū)間數(shù)優(yōu)化研究方面，特別是在非線性區(qū)間數(shù)優(yōu)化的研究方面，還存在著一些難點(diǎn)和技術(shù)問(wèn)題。第三種方法叫做區(qū)間數(shù)優(yōu)化方法，在區(qū)間數(shù)優(yōu)化中，往往是基于區(qū)間序關(guān)系[6]或者最大最小后悔準(zhǔn)則[7]。在這兩種方法中，分別是基于概率統(tǒng)計(jì)理論[4]和模糊統(tǒng)計(jì)理論[5]來(lái)進(jìn)行轉(zhuǎn)換的。為此，不確定性優(yōu)化理論方法的研究具有非常重要的現(xiàn)實(shí)意義。然而，在大多數(shù)實(shí)際工程中，不可避免地存在著與材料性質(zhì)、溫度變化、工程邊界、噪音影響、測(cè)量偏差等有關(guān)的誤差或不確定性，這些誤差或不確定性雖然在大多數(shù)情況下都比較小，但耦合在一起可能使整個(gè)工程系統(tǒng)產(chǎn)生較大的誤差或偏差。從辯證法的角度來(lái)看，確定性是相對(duì)的，而不確定性卻是絕對(duì)的。這些理論的產(chǎn)生，為解決實(shí)際工程中不確定性優(yōu)化問(wèn)題的研究提供了理論基礎(chǔ)。如在1984年，StancuMinasian在他編著的《隨機(jī)多目標(biāo)規(guī)劃》一書(shū)中，對(duì)隨機(jī)規(guī)劃的方法進(jìn)行了詳細(xì)深入的說(shuō)明，給出了一些隨機(jī)多目標(biāo)規(guī)劃問(wèn)題的求解方法。每個(gè)目標(biāo)函數(shù)的罰函數(shù)表示是由該目標(biāo)函數(shù)的中值和半寬以及約束函數(shù)的罰函數(shù)組成的，最終得到的是基于區(qū)間不確定參數(shù)的Pareto解集。第2章 多目標(biāo)區(qū)間數(shù)優(yōu)化的數(shù)學(xué)轉(zhuǎn)換模型第2章 多目標(biāo)區(qū)間數(shù)優(yōu)化的數(shù)學(xué)轉(zhuǎn)換模型 多目標(biāo)優(yōu)化的基本概念多目標(biāo)優(yōu)化是在現(xiàn)實(shí)各個(gè)領(lǐng)域中都普遍存在的問(wèn)題，每個(gè)目標(biāo)不可能都同時(shí)達(dá)到最優(yōu)，必須各有權(quán)重。如果上述多目標(biāo)優(yōu)化問(wèn)題式(21)的目標(biāo)函數(shù)全部是極小化目標(biāo)函數(shù)，約束函數(shù)全都是不等式約束，則可以得到一個(gè)標(biāo)準(zhǔn)多目標(biāo)優(yōu)化模型： （22）設(shè)計(jì)變量是一組確定的向量，對(duì)應(yīng)維歐氏設(shè)計(jì)變量空間上的一點(diǎn)，而相應(yīng)的目標(biāo)函數(shù)則對(duì)應(yīng)一個(gè)維的歐氏目標(biāo)函數(shù)空間的一點(diǎn)。由于在實(shí)際工程應(yīng)用中，我們遇到的問(wèn)題大多都是非線性的。3) 若，并且至少有一個(gè)是嚴(yán)格不等式，則稱向量A小于向量B，即向量A優(yōu)于向量B，記作AB。所有非劣解對(duì)應(yīng)的目標(biāo)函數(shù)構(gòu)成了多目標(biāo)優(yōu)化問(wèn)題的非劣最優(yōu)目標(biāo)域，也成為Pareto前緣(Pareto Front)，再不引起混淆的情況下也可以稱為非劣解集。除了要求優(yōu)化問(wèn)題的解要收斂到近似Pareto最優(yōu)域，求得的解也必須均勻稀疏地分布在Pareto最優(yōu)域上。同時(shí)，區(qū)間還可以定義為如下： （24）式中，和分別表示區(qū)間的中點(diǎn)和半寬：即 （25） （26）圖21給出了對(duì)于區(qū)間的幾何描述：圖21 區(qū)間的幾何描述區(qū)間的不確定性水平(uncertainty level)被定義為 （27）所以，利用區(qū)間描述優(yōu)化問(wèn)題中參數(shù)的不確定性，其一般形式的非線性區(qū)間數(shù)優(yōu)化問(wèn)題可以描述為： （28）式中，是維設(shè)計(jì)向量，其取值范圍為。又可以寫(xiě)成：， （29）式中 ，基于上述兩式，不確定水平可以寫(xiě)成：其中，假設(shè)中所有變量的不確定水平都比較小，則可對(duì)不確定參數(shù)在其中點(diǎn)處進(jìn)行一階泰勒展開(kāi)[13]： （210）屬于式中定義的區(qū)間向量，對(duì)上式進(jìn)行自然區(qū)間擴(kuò)展： （211）由此可知，的上界、下界分別分別為： （212） （213） 區(qū)間可能度和不確定約束的轉(zhuǎn)換對(duì)于兩個(gè)實(shí)數(shù)，可以通過(guò)它們的具體數(shù)值來(lái)比較其大小關(guān)系，但是對(duì)于區(qū)間數(shù)來(lái)說(shuō)，因?yàn)樗硎镜氖且粋€(gè)實(shí)數(shù)的集合，所以無(wú)法通過(guò)使用單個(gè)的實(shí)數(shù)值來(lái)判斷一個(gè)區(qū)間是否大于（優(yōu)于）另一個(gè)區(qū)間。2) 并未考慮有一區(qū)間退化為實(shí)數(shù)的可能情況，而此情況在實(shí)際的區(qū)間數(shù)優(yōu)化中是十分常見(jiàn)的問(wèn)題，所以這種方法的實(shí)用性在一定程度上也因此受到了影響。根據(jù)以下的位置關(guān)系，區(qū)間可能度構(gòu)造如下： （217）