畢業(yè)設計---nsga—ii的改進算法研究(含外文翻譯）

1、<p>　本科畢業(yè)設計（論文）</p><p><b>　　摘要</b></p><p>　　在實際工程中領域中，不可避免地存在著與材料性質(zhì)、幾何特性、邊界條件、測量偏差等有關的誤差或不確定性，這些誤差或不確定性使得目標函數(shù)或者約束函數(shù)也具有不確定性，所以傳統(tǒng)的優(yōu)化方法已經(jīng)不能適用。為此，本文將針對多目標區(qū)間數(shù)優(yōu)化展開系統(tǒng)的研究，力求通過改進多目標確定數(shù)優(yōu)化

2、問題來解決多目標區(qū)間數(shù)優(yōu)化問題。</p><p>　　首先，對于區(qū)間數(shù)多目標優(yōu)化問題，本文給出了一種利用區(qū)間數(shù)學來把不確定多目標優(yōu)化轉(zhuǎn)化為確定性多目標優(yōu)化的數(shù)學模型。具體來講就是利用區(qū)間序關系，將不確定的目標函數(shù)轉(zhuǎn)化成為確定性的目標函數(shù)；利用區(qū)間可能度將不確定的約束函數(shù)轉(zhuǎn)化成為確定性的約束函數(shù)；最后，利用線性加權(quán)法和罰函數(shù)分別處理目標函數(shù)和約束函數(shù)，將帶約束的不確定多目標優(yōu)化問題轉(zhuǎn)化成為無約束的確定性多目標優(yōu)化問

3、題。</p><p>　　其次，在多目標確定數(shù)優(yōu)化問題中，不可能存在一個使每個目標都達到最優(yōu)的解，所以多目標優(yōu)化問題的解往往是一個非劣解的集合——Pareto解集。在存在多個Pateto解集的情況下，如果沒有更多的說明，很難決定哪個解更重要，因此，找到盡可能多的Pateto最優(yōu)解至關重要。本文采用的帶精英策略的快速非支配排序遺傳算法(NSGS-II)是一種多目標遺傳算法，該算法求得的Pareto最優(yōu)解分布均勻，收

4、斂性和魯棒性好，對多目標優(yōu)化問題具有良好的優(yōu)化效果。</p><p>　　最后，本論文給出利用MATLAB仿真程序求解區(qū)間數(shù)多目標優(yōu)化問題的最終結(jié)果，并利用二個區(qū)間數(shù)多目標函數(shù)來調(diào)試程序中的關鍵參數(shù)（如約束可能度水平，多目標權(quán)系數(shù)，正則化因子等），根據(jù)參數(shù)在不同取值下的仿真結(jié)果，分析并說明參數(shù)設置對最后優(yōu)化結(jié)果的影響。</p><p>　　關鍵詞　多目標區(qū)間數(shù)優(yōu)化；NSGA-II；Pare

5、to解集；區(qū)間序關系；區(qū)間可能度</p><p><b>　　Abstract</b></p><p>　　In the actual project, there is inevitably material properties, geometry, boundary conditions, initial conditions, measurement erro

6、r and other related errors or uncertainty, these errors or uncertainties on the objective or constraints function also has uncertainty. Therefore, the conventional optimization methods have not apply for that. This artic

7、le will focus on multi-objective interval number optimization and carry out a systematic study, and solve multi-objective interval number optimizatio</p><p>　　Firstly, in terms of multi-objective interval nu

8、mber optimization problem, this paper presents a mathematical model where take advantage of interval mathematics to transfer uncertain multi-objective optimization into certain multi-objective optimization. Specifically,

9、 transfer the uncertain objective function into the certain objective function by using interval order relation, and transfer the uncertain constraint functions into certain constraint functions by using interval possibl

10、e degree. At</p><p>　　Secondly, in multi-objective exact number optimization problem, it is impossible to make each goal has an optimal solution, so the solutions of multi-objective optimization is often a s

11、et of non-dominated solutions-- Pareto set. Because of the presence of multiple Pareto solution set, and there is if no more further explanation, it is difficult to decide which solution is more important. Thus, finding

12、the Pateto optimal solution as much as possible is crucial. A fast Elitist Non-dominated Sortin</p><p>　　Finally, the paper presents the final result of multi-objective interval number optimization through t

13、he MATLAB simulation program. And using </p><p>　　multi-objective interval number functions debug the key parameters.(such as constraints possible degree level, multi-objective weights, regularization factor

14、, etc.) .According to the different values about the parameters in the simulation results, analyze and explain optimal parameter settings that how to impcet on the final results.</p><p>　　Keywords　 multi-obj

15、ective interval number optimization, NSGA-II, Pareto set, interval order relation, interval possible degree</p><p><b>　　目 錄</b></p><p><b>　　摘要I</b></p><p>　

16、　AbstractII</p><p><b>　　第1章 緒論1</b></p><p>　　1.1多目標區(qū)間數(shù)優(yōu)化研究的目的和意義1</p><p>　　1.2 多目標區(qū)間數(shù)優(yōu)化國內(nèi)外研究現(xiàn)狀及分析2</p><p>　　1.3 多目標區(qū)間數(shù)優(yōu)化發(fā)展趨勢和存在問題3</p><p>

17、　　1.4 本文的研究目標和主要研究內(nèi)容3</p><p>　　第2章 多目標區(qū)間數(shù)優(yōu)化的數(shù)學轉(zhuǎn)換模型5</p><p>　　2.1 多目標優(yōu)化的基本概念5</p><p>　　2.1.1 多目標優(yōu)化的數(shù)學描述5</p><p>　　2.1.2 多目標優(yōu)化的目標占優(yōu)和Pareto占優(yōu)7</p><p>　　2

18、.1.3 多目標優(yōu)化問題的解7</p><p>　　2.2區(qū)間數(shù)介紹8</p><p>　　2.3 不確定性區(qū)間結(jié)構(gòu)分析10</p><p>　　2.4 區(qū)間可能度和不確定約束的轉(zhuǎn)換10</p><p>　　2.4.1 改進的區(qū)間可能度方法11</p><p>　　2.4.2 基于區(qū)間可能度的不確定約束的轉(zhuǎn)換

19、16</p><p>　　2.5 區(qū)間序關系轉(zhuǎn)換模型17</p><p>　　2.5.1 區(qū)間序關系17</p><p>　　2.5.2 不確定目標函數(shù)的轉(zhuǎn)換19</p><p>　　2.5.3 轉(zhuǎn)換后的確定性優(yōu)化問題20</p><p>　　2.6 本章小結(jié)21</p><p>　

20、　第3章 NSGA-II算法22</p><p>　　3.1 NSGA-II算法的簡介22</p><p>　　3.2 快速非支配排序法23</p><p>　　3.3 擁擠度25</p><p>　　3.4精英策略26</p><p>　　3.5 NSGA-II算法的擁擠度距離公式改進27</p&g

21、t;<p>　　3.6 NSGA-II算法流程30</p><p>　　3.7 本章小結(jié)30</p><p>　　第4章 仿真結(jié)果和相關參數(shù)分析32</p><p>　　4.1 測試函數(shù)和仿真結(jié)果32</p><p>　　4.2 相關參數(shù)的分析33</p><p>　　4.2.1約束可能度水平λ

22、的影響33</p><p>　　4.2.2 多目標權(quán)系數(shù)β的選取34</p><p>　　4.2.3 正則化因子Φ和Ψ的選取35</p><p>　　4.2.4 交叉參數(shù)mu與變異參數(shù)mum的影響36</p><p>　　4.3 本章小結(jié)37</p><p><b>　　結(jié)論39</b>

23、;</p><p><b>　　參考文獻40</b></p><p><b>　　致謝42</b></p><p><b>　　附錄143</b></p><p><b>　　附錄251</b></p><p><b&

24、gt;　　附錄356</b></p><p><b>　　附錄463</b></p><p><b>　　附錄570</b></p><p><b>　　第1章 緒論</b></p><p>　　1.1多目標區(qū)間數(shù)優(yōu)化研究的目的和意義</p>&

25、lt;p>　　優(yōu)化是一種用于在多種決策當中選出最好決策的方法，它被廣泛地應用在工業(yè)、農(nóng)業(yè)、交通、國防等許多領域，對于合理利用資源、提高系統(tǒng)性能、降低能源消耗以及經(jīng)濟效益的增長均有非常顯著的作用[1]。一般來說，對實際工程領域中問題的分析和優(yōu)化設計通?；诖_定性的系統(tǒng)參數(shù)和優(yōu)化模型，并且借助傳統(tǒng)的確定性優(yōu)化方法[2]來進行求解。然而，在大多數(shù)實際工程中，不可避免地存在著與材料性質(zhì)、溫度變化、工程邊界、噪音影響、測量偏差等有關的誤差或

26、不確定性，這些誤差或不確定性雖然在大多數(shù)情況下都比較小，但耦合在一起可能使整個工程系統(tǒng)產(chǎn)生較大的誤差或偏差。</p><p>　　在實際的工程系統(tǒng)中，由于系統(tǒng)經(jīng)常工作在不同環(huán)境下，使得系統(tǒng)的參數(shù)也經(jīng)常發(fā)生變化，不能維持在一個恒定的值上；參數(shù)在一定的區(qū)域內(nèi)變化，使得參數(shù)無法精確測定等。事實上，在絕大多數(shù)實際工程中，都或多或少地存在著一些不確定因素，只是由于對這些工程系統(tǒng)從數(shù)學角度上處理困難，所以在很多情況下不得不做

27、出簡化，將多目標轉(zhuǎn)化為單目標以及將不確定性轉(zhuǎn)化為確定性[3]。從辯證法的角度來看，確定性是相對的，而不確定性卻是絕對的。對于不確定性系統(tǒng)的優(yōu)化問題，經(jīng)典的優(yōu)化理論和方法無法完成，必須通過不確定性優(yōu)化(uncertain optimization)進行建模和求解，在求解的過程中必須充分考慮參數(shù)的不確定性對系統(tǒng)的影響，并對不確定變量解耦后建立新的優(yōu)化模型。不確定優(yōu)化理論是傳統(tǒng)的確定性優(yōu)化理論的發(fā)展與延伸，利用不確定性優(yōu)化方法進行優(yōu)化設計時，

28、無需做出很多假設和簡化，可以建立更為真實客觀的優(yōu)化模型，從而獲得更可靠、更貼近實際的設計方案。不確定性優(yōu)化理論的發(fā)展和應用，給社會帶來了巨大的效益。以實際工業(yè)生產(chǎn)為例，企業(yè)可以借助不確定性優(yōu)化技術(shù)來提高產(chǎn)品安全性和可靠性，以滿足生產(chǎn)安全規(guī)范，減少對環(huán)境破壞以及不必要的能耗，</p><p>　　1.2 多目標區(qū)間數(shù)優(yōu)化國內(nèi)外研究現(xiàn)狀及分析</p><p>　　由于不確定性問題的普遍存在，并

29、且表現(xiàn)形式多種多樣，如隨機性、模糊性等，經(jīng)典的優(yōu)化理論和方法對于這些不確定性的優(yōu)化問題已不再適用，處理起來往往會遇到很大的困難和不便。為此，用以專門處理不確定性優(yōu)化問題的理論應運而生。這些理論的產(chǎn)生，為解決實際工程中不確定性優(yōu)化問題的研究提供了理論基礎。</p><p>　　目前，人們研究的多目標優(yōu)化問題大部分針對確定性問題，而在實際的工程領域中往往存在材料、測量、載荷等多方面的不確定性。對于不確定優(yōu)化問題的處理

30、，總體來說，其主要思路是一般是先通過數(shù)學轉(zhuǎn)換模型將不確定性優(yōu)化問題轉(zhuǎn)換為確定性優(yōu)化問題，繼而利用傳統(tǒng)的確定性多目標優(yōu)化方法進行求解。對于不確定性優(yōu)化問題的研究，具體來說，目前國內(nèi)外主要有三種方法來處理多目標區(qū)間數(shù)優(yōu)化：即隨機規(guī)劃方法、模糊規(guī)劃方法和區(qū)間數(shù)優(yōu)化方法。隨機規(guī)劃方法[4]和模糊規(guī)劃方法[5]是兩類比較傳統(tǒng)的不確定性優(yōu)化方法。在這兩種方法中，分別是基于概率統(tǒng)計理論[4]和模糊統(tǒng)計理論[5]來進行轉(zhuǎn)換的。其中，采用隨機規(guī)劃方法的不

31、確定優(yōu)化問題，其不確定參數(shù)是隨機變量，并且需要知道該隨機變量滿足的分布。許多專家學者對這種方法進行了深入的探討和研究。如在1984年，Stancu-Minasian在他編著的《隨機多目標規(guī)劃》一書中，對隨機規(guī)劃的方法進行了詳細深入的說明，給出了一些隨機多目標規(guī)劃問題的求解方法。Teghem等人提出了一種線性隨機多目標規(guī)劃(MOSLP)的求解方法，這種方法被人們稱為Strange方法，其特點是將隨機多目標規(guī)劃問題轉(zhuǎn)化為</p>

32、<p>　　1.3 多目標區(qū)間數(shù)優(yōu)化發(fā)展趨勢和存在問題</p><p>　　近五十多年來，不確定性優(yōu)化的理論和方法已經(jīng)得到廣泛的研究，并吸引越來越的關注，目前已被應用于諸多實際工程領域，如：生產(chǎn)過程、存儲系統(tǒng)、網(wǎng)絡優(yōu)化、車輛調(diào)度、系統(tǒng)可靠性、設備選址、結(jié)構(gòu)優(yōu)化等。這些課題的研究和發(fā)展，一方面反映了不確定性優(yōu)化在實際應用中的作用，對實際工程的優(yōu)化確實行之有效。另一方面也給出了許多不確定性優(yōu)化的研究背景

33、和應用前景，并為其后續(xù)的研究和發(fā)展提供不竭的動力和源泉。</p><p>　　但是，就目前看來多目標區(qū)間數(shù)優(yōu)化所研究的問題缺乏一般性，在為數(shù)不多的關于非線性區(qū)間數(shù)優(yōu)化問題的研究中，還沒有總結(jié)出針對一般非線性區(qū)間數(shù)優(yōu)化問題的數(shù)學轉(zhuǎn)換模型，這一定程度上阻礙了區(qū)間數(shù)優(yōu)化的研究進展。</p><p>　　1.4 本文的研究目標和主要研究內(nèi)容</p><p>　　綜上所述，在

34、目前的區(qū)間數(shù)優(yōu)化研究方面，特別是在非線性區(qū)間數(shù)優(yōu)化的研究方面，還存在著一些難點和技術(shù)問題。為此，本文將針對其中的一些問題展開深入的研究。本文的整個研究內(nèi)容和研究思路將按三個方面展開：首先，從區(qū)間序規(guī)劃的理論層面上找出一種能處理一般非線性區(qū)間數(shù)優(yōu)化的數(shù)學轉(zhuǎn)換模型；其次，基于數(shù)學轉(zhuǎn)換模型，將不確定性優(yōu)化問題轉(zhuǎn)化為確定性優(yōu)化問題，繼而利用帶精英策略的非支配排序遺傳算法(NSGA-II)，對多目標優(yōu)化問題進行優(yōu)化和求解；最后，本文將利用區(qū)間數(shù)多

35、目標函數(shù)來測試算法的有效性，以及對算法中的重要算子進行研究，通過對比各個不同參數(shù)下的最終仿真結(jié)果，分析并說明參數(shù)的取值對最終優(yōu)化結(jié)果的影響。</p><p>　　第2章 多目標區(qū)間數(shù)優(yōu)化的數(shù)學轉(zhuǎn)換模型</p><p>　　2.1 多目標優(yōu)化的基本概念</p><p>　　多目標優(yōu)化是在現(xiàn)實各個領域中都普遍存在的問題，每個目標不可能都同時達到最優(yōu)，必須各有權(quán)重。但是，

36、究竟要怎樣分配這樣的權(quán)重，這已經(jīng)成為人們研究的熱點問題。同時，根據(jù)生物進化論發(fā)展起來的遺傳算法，也得到了人們的關注。將這兩者結(jié)合起來，能夠利用遺傳算法的全局搜索能力，避免傳統(tǒng)的多目標優(yōu)化方法在尋優(yōu)過程中陷入局部最優(yōu)解，可以使解個體保持多樣性。所以，基于遺傳算法的多目標尋優(yōu)策略已經(jīng)被應用于各個領域中。</p><p>　　2.1.1 多目標優(yōu)化的數(shù)學描述</p><p>　　一般來講，多目標

37、優(yōu)化問題是由多個目標函數(shù)與有關的一些等式以及不等式約束組成，從數(shù)學角度可以做如下描述[8]：</p><p><b>　　（2-1）</b></p><p>　　式中，函數(shù)稱為目標函數(shù)；和稱為約束函數(shù)；是維的設計變量。</p><p>　　稱為(2-1)的可行域。在這個多目標優(yōu)化問題中有個目標函數(shù)(個極小化目標函數(shù)，個極大化目標函數(shù))和個約束函

38、數(shù)(其中有個不等式約束和個等式約束)。</p><p>　　如果上述多目標優(yōu)化問題式(2-1)的目標函數(shù)全部是極小化目標函數(shù)，約束函數(shù)全都是不等式約束，則可以得到一個標準多目標優(yōu)化模型：</p><p><b>　?。?-2）</b></p><p>　　設計變量是一組確定的向量，對應維歐氏設計變量空間上的一點，而相應的目標函數(shù)則對應一個維的歐

39、氏目標函數(shù)空間的一點。也就是說，目標函數(shù)對應的是由n維設計變量空間到m維目標函數(shù)空間的一個映射[3]：</p><p><b>　　f：→</b></p><p>　　由此可知，設計變量、目標函數(shù)以及約束函數(shù)是構(gòu)成多目標優(yōu)化問題的三要素。</p><p>　　設計變量是在實際工程設計中可以人為指定控制的，并且能對工程系統(tǒng)的屬性、性能產(chǎn)生影響的一

40、組向量，不同取值的設計變量便意味著對應不同的工程系統(tǒng)設計方案，一組設計變量通?？梢杂孟蛄勘硎荆阉Q之為優(yōu)化問題的一個解。</p><p>　　目標函數(shù)可以看作是評價設計系統(tǒng)性能指標的數(shù)學表達式，在實際工程設計中，設計者（決策者）希望能同時使這些性能指標達到最優(yōu)化。所有的目標函數(shù)構(gòu)成了多目標優(yōu)化問題(2-2)的目標函數(shù)向量。</p><p>　　約束給出了設計變量需要滿足的限制條件，用含

41、有等式和不等式的約束函數(shù)來表示。滿足所有約束函數(shù)（約束條件）的一組設計變量可以稱之為一個可行解，優(yōu)化問題中所有的可行解構(gòu)成了整個優(yōu)化問題的可行域。</p><p>　　根據(jù)目標函數(shù)、約束函數(shù)以及設計變量的特點，多目標優(yōu)化問題可以分成以下幾種類型[9]：</p><p>　　如果在多目標優(yōu)化問題中，所有的目標函數(shù)和約束函數(shù)都是線性的，則稱此類優(yōu)化問題為線性多目標優(yōu)化問題；如果至少有一個目標函

42、數(shù)或約束函數(shù)是非線性的，則稱此類優(yōu)化問題為非線性多目標優(yōu)化問題；如果系統(tǒng)模型中設計變量是連續(xù)的，則此類優(yōu)化問題是連續(xù)多目標優(yōu)化問題；反之，就稱之為離散問題。</p><p>　　由于在實際工程應用中，我們遇到的問題大多都是非線性的。然而，非線性優(yōu)化問題的解決難度要遠遠大于線性優(yōu)化問題。另外，在大多數(shù)的工程設計問題中，設計變量通常是連續(xù)的，所以多目標優(yōu)化主要的研究方向就是怎樣解決連續(xù)非線性多目標的優(yōu)化問題。<

43、/p><p>　　2.1.2 多目標優(yōu)化的目標占優(yōu)和Pareto占優(yōu)</p><p>　　在多目標優(yōu)化算法的搜索中，普遍使用了占優(yōu)(dominate)的概念。在這里將給出占優(yōu)的概念以及相關術(shù)語的定義[10]。</p><p>　　定義2.1（向量序） 設是維歐氏空間中的兩個向量。</p><p>　　1)若，則稱向量A等于向量B，記作A=B。

44、</p><p>　　2)若，則稱向量A小于等于向量B，記作 。</p><p>　　3)若，并且至少有一個是嚴格不等式，則稱向量A小于向量B，即向量A優(yōu)于向量B，記作AB。</p><p>　　4)若，則稱向量A嚴格小于向量B，記作A<B。</p><p>　　定義2.2（絕對最優(yōu)解、非劣解） S為多目標優(yōu)化的可行域，為

45、多目標優(yōu)化的向量目標函數(shù)。</p><p>　　若，則稱是多目標優(yōu)化的絕對最優(yōu)解。</p><p>　　若，則稱是多目標優(yōu)化問題的非劣解，即Pareto最優(yōu)解。</p><p>　　非劣解也成為有效解(Efficient Solution)、非支配解(Non-dominated Solution)、Pareto最優(yōu)解(Pareto Optimal Solution)

46、或Pareto解，它是多目標優(yōu)化中的一個最基本的概念。從其中的定義中可以看出，在可行域中找不到比非劣解更好的解，如果要改善問題的一個目標，必須會導致其他目標的損失。</p><p>　　多目標優(yōu)化問題的非劣解一般不止一個，由所有非劣解構(gòu)成的集合稱為非劣解集(Non-inferior Set)。所有非劣解對應的目標函數(shù)構(gòu)成了多目標優(yōu)化問題的非劣最優(yōu)目標域，也成為Pareto前緣(Pareto Front)，再不引起

47、混淆的情況下也可以稱為非劣解集。</p><p>　　2.1.3 多目標優(yōu)化問題的解</p><p>　　在單目標優(yōu)化問題中，通常最優(yōu)解只有一個，而且能用比較簡單和常用的數(shù)學方法求出其最優(yōu)解。然而在多目標優(yōu)化問題中，各個目標之間相互制約，可能使得一個目標性能的改善往往是以損失其它目標性能為代價，不可能存在一個使所有目標性能都達到最優(yōu)的解，所以對于多目標優(yōu)化問題，其解通常是一個非劣解的集合—

48、—Pareto解集。</p><p>　　在存在多個Pareto最優(yōu)解的情況下[11]，如果沒有關于問題的更多的信息，那么很難選擇哪個解更可取，因此所有的Pareto最優(yōu)解都可以被認為是同等重要的。由此可知，對于多目標優(yōu)化問題，最重要的任務是找到盡可能多的關于該優(yōu)化問題的Pareto最優(yōu)解。因而，在多目標優(yōu)化中主要完成以下兩個任務：</p><p>　　找到一組盡可能接近Pareto最優(yōu)域

49、的解。</p><p>　　找到一組盡可能不同的解。</p><p>　　第一個任務是在任何優(yōu)化工作中都必須的做到的，收斂不到接近真正Pareto最優(yōu)解集的解是不可取的，只有當一組解收斂到接近真正Pareto最優(yōu)解，才能確保該組解近似最優(yōu)的這一特性。</p><p>　　除了要求優(yōu)化問題的解要收斂到近似Pareto最優(yōu)域，求得的解也必須均勻稀疏地分布在Pareto最

50、優(yōu)域上。一組在多個目標之間好的協(xié)議解是建立在一組多樣解的基礎之上。因為在多目標進化算法中，決策者一般需要處理兩個空間——決策變量空間和目標空間，所以解(個體)之間的多樣性可以分別在這兩個空間定義[12]。例如，若兩個個體在決策變量空間中的歐拉距離大，那么就說這兩個解在決策變量空間中互異；同理，若兩個個體在目標空間中的歐拉距離大，則說它們在目標空間中互異。盡管對于大多數(shù)問題而言，在一個空間中的多樣性通常意味著在另一個空間中的多樣性，但是此

51、結(jié)論并不是對所有的問題都是成立的。對于這樣復雜的非線性優(yōu)化問題，要找到在要求的空間中有好的多樣性的一組解也是一項非常重要的任務。</p><p><b>　　2.2區(qū)間數(shù)介紹</b></p><p>　　根據(jù)區(qū)間數(shù)學[12]，區(qū)間數(shù)被定義為一對有序的實數(shù)：</p><p><b>　?。?-3）</b></p>

52、<p>　　式中，上、、分別表示區(qū)間、區(qū)間的下界和區(qū)間的上界。當=時，區(qū)間退化為一實數(shù)。</p><p>　　同時，區(qū)間還可以定義為如下：</p><p><b>　?。?-4）</b></p><p>　　式中，和分別表示區(qū)間的中點和半寬：即</p><p><b>　?。?-5）</b&

53、gt;</p><p><b>　　（2-6）</b></p><p>　　圖2-1給出了對于區(qū)間的幾何描述：</p><p>　　圖2-1 區(qū)間的幾何描述</p><p>　　區(qū)間的不確定性水平(uncertainty level)被定義為</p><p><b>　?。?-7）<

54、;/b></p><p>　　所以，利用區(qū)間描述優(yōu)化問題中參數(shù)的不確定性，其一般形式的非線性區(qū)間數(shù)優(yōu)化問題可以描述為：</p><p><b>　?。?-8）</b></p><p>　　式中，是維設計向量，其取值范圍為。為維不確定向量，其不確定性用一維區(qū)間向量描述。和分別為多目標優(yōu)化問題的目標函數(shù)和約束函數(shù)，它們都是關于和的非線性連續(xù)函

55、數(shù)。為第個不確定約束函數(shù)的允許區(qū)間，在實際問題中可以是一個實數(shù)。</p><p>　　因為是目標函數(shù)和約束函數(shù)是關于的連續(xù)函數(shù)，并且的波動范圍是在一個區(qū)間矢量之內(nèi)，所以對于任一確定的設計變量，其目標函數(shù)或第個約束函數(shù)，由不確定參數(shù)區(qū)間引起的函數(shù)可能值都將構(gòu)成一區(qū)間。所以，上述問題無法通過傳統(tǒng)的確定性優(yōu)化方法來進行求解，因為在傳統(tǒng)的確定性優(yōu)化方法中，決策的選擇和判斷都是建立在目標函數(shù)和約束函數(shù)在各個設計變量處的具體

56、數(shù)值的基礎上進行的。下面本文將給出不確定約束的和不確定目標函數(shù)的處理方法，然后根據(jù)多目標權(quán)值和罰函數(shù)等得出非線性區(qū)間數(shù)優(yōu)化的數(shù)學轉(zhuǎn)換模型。</p><p>　　2.3 不確定性區(qū)間結(jié)構(gòu)分析</p><p>　　假設對于多目標優(yōu)化中目標函數(shù)和約束函數(shù)的不確定參數(shù)，有，。又可以寫成：</p><p>　　， （2-9）</p><p>　

57、　式中 ，，</p><p><b>　　，，</b></p><p>　　基于上述兩式，不確定水平可以寫成：</p><p><b>　　其中，，</b></p><p>　　假設中所有變量的不確定水平都比較小，則可對不確定參數(shù)在其中點處進行一階泰勒展開[13]：</p>

58、<p><b>　　（2-10）</b></p><p>　　屬于式中定義的區(qū)間向量，對上式進行自然區(qū)間擴展：</p><p><b>　?。?-11）</b></p><p>　　由此可知，的上界、下界分別分別為：</p><p><b>　?。?-12）</b>

59、</p><p><b>　?。?-13）</b></p><p>　　2.4 區(qū)間可能度和不確定約束的轉(zhuǎn)換</p><p>　　對于兩個實數(shù)，可以通過它們的具體數(shù)值來比較其大小關系，但是對于區(qū)間數(shù)來說，因為它表示的是一個實數(shù)的集合，所以無法通過使用單個的實數(shù)值來判斷一個區(qū)間是否大于（優(yōu)于）另一個區(qū)間。所以人們必須構(gòu)造和使用新的數(shù)學工具來比較區(qū)

60、間數(shù)的大?。ɑ騼?yōu)劣），這也是建立區(qū)間數(shù)優(yōu)化問題的數(shù)學轉(zhuǎn)換模型的基礎。為了將區(qū)間數(shù)比較的概念表達清晰，本文把區(qū)間數(shù)比較的數(shù)學方法歸納成兩類[14]：一類稱為“區(qū)間序關系”(order relation of interval number)，常用于定性地判斷一個區(qū)間是否大于（或優(yōu)于）另一區(qū)間；另一類稱為“區(qū)間可能度”(possibility degree of interval number)，常用于定量地描述一個區(qū)間大于（優(yōu)于）另一區(qū)間

61、的具體程度。</p><p>　　2.4.1 改進的區(qū)間可能度方法</p><p>　　為了給區(qū)間可能度的構(gòu)造提供一個較為客觀和嚴格的數(shù)學解釋，張全[14]等引入了概率的方法，提出了一種新的區(qū)間可能度的構(gòu)造方法。針對如圖2-2所示的三種位置情況，區(qū)間大于等于的可能度構(gòu)造如下[14]：</p><p><b>　?。?-14）</b></p

62、><p>　　上式中，假設區(qū)間和在各自的區(qū)間內(nèi)都服從均勻分布的隨機變量和，通過計算隨機變量大于等于的概率獲得可能度。</p><p>　　如對于圖2-2中的第二種情況，在和之間的概率為，而此</p><p>　　時不管取值多少的概率都為l；在和間的概率，</p><p>　　在和之間的概率為，此時的概率為50%。在和</p><

63、;p>　　之間的概率為，在和之間的概率為，最終可</p><p>　　得在此情況，的概率為：</p><p>　　相應地，的可能度為[14]：</p><p><b>　?。?-15）</b></p><p>　　圖2-2 區(qū)間和三種位置關系</p><p>　　在上述構(gòu)造方法中，通過引入

64、概率的方法，使得區(qū)間可能度本身的數(shù)學含義更具直觀性，而且其客觀性得到了進一步的加強，這對于決策者的理解和使用都有很大的幫助。然而此方法卻也具有兩方面的局限性：</p><p>　　1)以上可能度是基于圖2-2中的三種位置關系而構(gòu)造的，而此三種位置關系只是區(qū)間和所有可能情況的一部分，因此需要用兩個可能度公式，即(2-14)式和(2-15)式來進行對同樣區(qū)間對的比較，影響了可能度使用的方便性。</p>

65、<p>　　2)并未考慮有一區(qū)間退化為實數(shù)的可能情況，而此情況在實際的區(qū)間數(shù)優(yōu)化中是十分常見的問題，所以這種方法的實用性在一定程度上也因此受到了影響。</p><p>　　針對上述方法的局限和不足，姜潮[3]等在其基礎上提出了一種改進的區(qū)間可能度的構(gòu)造模型?？紤]區(qū)間和的所有可能的情況，可以歸納為6種不同的位置關系，如圖2-3所示。基于此6種位置關系，應用上述的概率方法，改進的區(qū)間可能度構(gòu)造如下所示：

66、</p><p>　　圖2-3 區(qū)間和所有可能的六種位置關系</p><p><b>　?。?-16）</b></p><p>　　上述的區(qū)間可能度有如下性質(zhì)：</p><p>　　若，則表示區(qū)間不可能小于區(qū)間，即區(qū)間絕對大于區(qū)間。</p><p>　　若，則表示區(qū)間小于等于區(qū)間。</p&g

67、t;<p>　　若，則區(qū)間等于區(qū)間，即=。</p><p><b>　　若，則。</b></p><p>　　對于區(qū)間退化成一實數(shù)b的情況，區(qū)間和實數(shù)b之間可能的位置關系如圖2-4所示。根據(jù)以下的位置關系，區(qū)間可能度構(gòu)造如下：</p><p><b>　?。?-17）</b></p><p

68、>　　在上式可能度的構(gòu)造中，只有區(qū)間被假設為服從均勻分布的隨機變量，的概率被視為可能度。類似地，當區(qū)間退化為實數(shù)口時，基于圖2-5中的三種位置關系，區(qū)間可能度可構(gòu)造如下：</p><p><b>　?。?-18）</b></p><p>　　圖2-6給出了和的幾何描述，兩種可能度的值在0和1之間時，分別與b和a成線性關系。</p><p>

69、;　　圖2-4 區(qū)間和實數(shù)的三種位置關系</p><p>　　圖2-5 區(qū)間和實數(shù)的三種位置關系</p><p>　　圖2-6 區(qū)間可能度和的幾何描述</p><p>　　2.4.2 基于區(qū)間可能度的不確定約束的轉(zhuǎn)換</p><p>　　在區(qū)間數(shù)優(yōu)化問題中，一般使區(qū)間不確定約束滿足一定的可能度水平，這種方法常在線性區(qū)間數(shù)的優(yōu)化中，被用來處理不

70、等式約束，此處將其擴展至非線性的區(qū)間數(shù)優(yōu)化問題[3]。對于(2-8)式中型的不等式約束函數(shù)，如，可以轉(zhuǎn)成為如下確定性不等式約束：</p><p><b>　?。?-19）</b></p><p>　　上式中，為預先給定的可能度水平。為不確定性在X處由不確定參數(shù)而造成的可能取值的區(qū)間：</p><p><b>　?。?-20）</

71、b></p><p>　　其中，、分別約束區(qū)間的下界和上界，即：</p><p><b>　　， </b></p><p><b>　　（2-21）</b></p><p>　　對式(2-21)進行自然區(qū)間擴展，可獲得約束函數(shù)的上下界：</p><p><b&g

72、t;　?。?-22）</b></p><p>　　一旦求出的區(qū)間值，即可通過公式(2-16)或公式(2-17)來求解約束可能度（依據(jù)是區(qū)間還是實數(shù)的具體情況），并判斷約束可能度是否滿足提前給定的可能水平。</p><p>　　對于型的不等式約束函數(shù)，如，可以簡單地將其轉(zhuǎn)換為型約束來進行處理：</p><p><b>　?。?-23）</b

73、></p><p>　　上式中，通過公式(2-16)或公式(2-18)進行求解。</p><p>　　對于含不確定參數(shù)的等式約束的處理方法，本文提出了一種將其轉(zhuǎn)換為不等式約束進行處理的方法。例如，對于帶有不確定參數(shù)的等式約束函數(shù)，可以將其轉(zhuǎn)化為如下形式：</p><p><b>　　（2-24）</b></p><p&

74、gt;　　進而，可以將其表示成兩個不等式約束：</p><p><b>　?。?-25）</b></p><p>　　利用前面敘述的對于不等式約束的轉(zhuǎn)換方法處理上式，可得：</p><p><b>　?。?-26）</b></p><p>　　上式中的可能度和可以通過公式(2-18)和公式(2-17

75、)進行求解。</p><p>　　通過以上對可能度的處理，可以將式(2-8)中的不確定約束被轉(zhuǎn)換成為確定性約束，并可以用如下的統(tǒng)一形式表示：</p><p><b>　?。?-27）</b></p><p>　　在上式中，因為不確定等式約束的存在，使得要預先給定兩個可能度水平，故k>l。此外，和的具體形式是區(qū)間還是實數(shù)應該根據(jù)以上不確定約

76、束的轉(zhuǎn)換過程而定，另外也跟的形式有關。</p><p>　　2.5 區(qū)間序關系轉(zhuǎn)換模型</p><p>　　2.5.1 區(qū)間序關系</p><p>　　區(qū)間序關系用于定性地判斷一區(qū)間是否優(yōu)于或者劣于另一區(qū)間，通常在區(qū)間數(shù)優(yōu)化問題中用于處理帶有不確定參數(shù)的目標函數(shù)。對于任一的設計變量，由于有不確定參數(shù)的存在，使得目標函數(shù)可能的取值是一區(qū)間而非確定的實數(shù)值。由于在區(qū)間數(shù)

77、優(yōu)化問題中，需要比較在不同的設計變量下目標函數(shù)取值區(qū)間的優(yōu)劣，進而評價相應設計變量的優(yōu)劣，以尋找到最優(yōu)的設計變量。對于最大化和最小化的優(yōu)化問題，同一區(qū)間序關系可以具有不同的表述形式，因為在這兩種問題中它們的評價指標并不相同，例如在最大化問題中目標函數(shù)的函數(shù)值大的決策變量為優(yōu)，而在最小化問題中剛好相反，目標函數(shù)的函數(shù)值小的決策變量為優(yōu)。文獻[16]總結(jié)了目前常用的幾種區(qū)間序關系，對于最大化和最小化優(yōu)化問題它們具有如下形式[16]：<

78、/p><p>　　區(qū)間序關系：該序關系表達了決策者對區(qū)間上、下邊界的偏好。</p><p>　　，并且僅當， （最大化優(yōu)化問題）</p><p>　　，并且僅當， （2-28）</p><p>　　，并且僅當， （最小化優(yōu)化問題）</p><p>　　，并且僅當，

79、 （2-29）</p><p>　　2）區(qū)間序關系：該序關系表達了決策者對區(qū)間中點和半徑的偏好。</p><p>　　，并且僅當， （最大化優(yōu)化問題）</p><p>　　，并且僅當， （2-30）</p><p>　　，并且僅當， （最小化優(yōu)化問題）</p><p>　　，并且僅當

80、， （2-31）</p><p>　　3）區(qū)間序關系：該序關系表達了決策者對區(qū)間下界和中點的偏好。</p><p>　　，并且僅當， （最大化優(yōu)化問題）</p><p>　　，并且僅當， （2-32）</p><p>　　，并且僅當， （最小化優(yōu)化問題）</p>&l

81、t;p>　　，并且僅當， （2-33）</p><p>　　4）區(qū)間序關系：該序關系表達了決策者對區(qū)間下界的偏好。</p><p>　　，并且僅當 （最大化優(yōu)化問題）</p><p>　　，并且僅當， （2-34）</p><p>　　，并且僅當

82、 （最小化優(yōu)化問題）</p><p>　　，并且僅當， （2-35）</p><p>　　5）區(qū)間序關系：該序關系表達了決策者對區(qū)間上界的偏好。</p><p>　　，并且僅當 （最大化優(yōu)化問題）</p><p>　　，并且僅當， （2-36）</p&

83、gt;<p>　　，并且僅當 （最小化優(yōu)化問題）</p><p>　　，并且僅當， （2-37）</p><p>　　2.5.2 不確定目標函數(shù)的轉(zhuǎn)換</p><p>　　在本文的數(shù)學轉(zhuǎn)換模型中，我們選用區(qū)間序關系來處理式(2-8)中的不確定目標函數(shù)。因為從工程的角度來看，相比其它幾種區(qū)間序關系而言，具有更加

84、直觀的工程意義和更好的工程實用性，所以在本文的數(shù)學轉(zhuǎn)換模型中選用來處理不確定性目標函數(shù)。</p><p>　　針對任一設計變量，因為不確定參數(shù)的存在，并且目標函數(shù)為的連續(xù)函數(shù)，所以的可能取值是在一定范圍內(nèi)的區(qū)間：</p><p><b>　?。?-38）</b></p><p>　　式中，

85、 （2-39）</p><p><b>　?。?-40）</b></p><p>　　基于(2-31)式表述的區(qū)間序關系，可以通過目標函數(shù)區(qū)間的中點和半寬來判斷不同的設計變量之間的優(yōu)劣：設計變量優(yōu)于，則處的目標函數(shù)的區(qū)間優(yōu)于處的目標函數(shù)的區(qū)間，即并且。因此，我們希望找到一個最優(yōu)的設計變量，使得不確定目標函數(shù)的區(qū)間具有最小的中點值和最小的半寬值，則式(2-8)中的

86、不確定性目標函數(shù)可以轉(zhuǎn)換成為如下確定性目標函數(shù)：</p><p><b>　?。?-41）</b></p><p>　　上式中，對于任一設計變量，需要根據(jù)在不確定目標函數(shù)的區(qū)間的基礎上計算其中點和半寬。此處，仍采用文獻[22]的方法，通過兩次優(yōu)化來求解不確定目標函數(shù)的區(qū)間范圍：</p><p><b>　　（2-42）</b&g

87、t;</p><p>　　對公式(2-42)進行自然區(qū)間的擴展，可獲得目標函數(shù)的上下界：</p><p><b>　　（2-43）</b></p><p>　　(2-41)式中的兩個目標函數(shù)類似于統(tǒng)計數(shù)學中的期望值和標準偏差。通過優(yōu)化，表示在某種意義上是提高目標函數(shù)在不確定性下的“平均設計性能”；而的最小化可以降低目標函數(shù)對于不確定性的敏感程度

88、，從而保證系統(tǒng)設計的魯棒性。</p><p>　　2.5.3 轉(zhuǎn)換后的確定性優(yōu)化問題</p><p>　　通過對以上不確定性地處理，式(2-8)所表示的不確定性優(yōu)化問題可以轉(zhuǎn)化為以下確定性優(yōu)化問題：</p><p><b>　?。?-44）</b></p><p>　　式中， </p>&

89、lt;p><b>　?。?-45）</b></p><p>　　至此，通過區(qū)間序關系建立數(shù)學轉(zhuǎn)換模型的工作已經(jīng)完成，通過此數(shù)學轉(zhuǎn)換模型可以將一個不確定性優(yōu)化問題轉(zhuǎn)換成確定性優(yōu)化問題。但為方便后續(xù)傳統(tǒng)優(yōu)化算法對其進行求解，此處采用線性加權(quán)法[3]將上式進一步轉(zhuǎn)換成一個單目標的優(yōu)化問題：</p><p><b>　　（2-46）</b><

90、/p><p>　　上式中，函數(shù)是多目標評價函數(shù)，是多目標權(quán)系數(shù)，ξ是為了使和這兩個式子全都是非負數(shù)的參數(shù)，和叫做正則化因子，理論上可通過如下優(yōu)化過程獲得：</p><p><b>　　（2-47）</b></p><p>　　在實際工程系統(tǒng)的應用中，上述兩個參數(shù)可以根據(jù)具體問題，大致取與各自目標同一量級的值即可，以防止“大數(shù)吃小數(shù)”現(xiàn)象的發(fā)生[3]

91、。采用罰函數(shù)法[3]處理約束函數(shù)，(2-46)式可進一步轉(zhuǎn)換為如下以罰函數(shù)表示的無約束的單一目標優(yōu)化問題：</p><p><b>　　（2-48）</b></p><p>　　上式中，在實質(zhì)上也是一組約束，它通常以設計變量的邊界形式描述。因為在本文中，我們將采用遺傳算法來求解此類問題，而在遺傳算法的求解過程中可以直接在算法中設定而并不需要把它們當做約束來處理。所以在

92、本文中，一律把類似于式(2-48)的問題稱為無約束優(yōu)化問題。在上式中，σ為罰因子，一般要取較大的數(shù)值，θ為罰函數(shù)，可表示如下：</p><p><b>　?。?-49）</b></p><p><b>　　2.6 本章小結(jié)</b></p><p>　　本章針對一般的區(qū)間數(shù)多目標優(yōu)化問題，提出了一種區(qū)間數(shù)優(yōu)化的數(shù)學轉(zhuǎn)換模型，

93、將不確定優(yōu)化問題轉(zhuǎn)換成確定性優(yōu)化，進而可以利用傳統(tǒng)的優(yōu)化方法來求解。具體來講，即利用區(qū)間序關系處理含不確定參數(shù)的目標函數(shù)，利用可能度水平處理含不確定參數(shù)的約束函數(shù)，最后利用多目標權(quán)系數(shù)、罰函數(shù)和罰因子，將帶有不確定性約束的區(qū)間數(shù)多目標優(yōu)化轉(zhuǎn)化成為不含約束的單目標優(yōu)化問題，從而可以利用傳統(tǒng)的多目標優(yōu)化方法來求得其Pareto解集。</p><p>　　第3章 NSGA-II算法</p><p&g

94、t;　　3.1 NSGA-II算法的簡介</p><p>　　多目標遺傳算法是用來分析和解決多目標優(yōu)化問題的一種進化算法，其核心就是協(xié)調(diào)各個目標函數(shù)之間的關系，找出使得各個目標函數(shù)都盡可能達到比較大的（或比較小的）函數(shù)值的最優(yōu)解集。在眾多多目標優(yōu)化的遺傳算法中，NSGA-II算法是影響最大和應用范圍最廣的一種多目標遺傳算法。在其出現(xiàn)以后，由于它簡單有效以及比較明顯的優(yōu)越性，使得該算法已經(jīng)成為多目標優(yōu)化問題中的基本

95、算法之一。</p><p>　　1989年Goldberg提出了基于Pareto最優(yōu)解的概念和計算個體適應度的方法，借助非劣解的等級和相應的選擇算子使種群在優(yōu)化過程中朝著Pareto最優(yōu)解方向進化。這種思想已經(jīng)產(chǎn)生了多種基于Pareto最優(yōu)解的多目標遺傳算法，其中非支配排序遺傳算法（Non-dominated Sorting Genetic Algorithm）——NSGA算法是最能體現(xiàn)Goldberg思想的一種

96、方法。</p><p>　　NSGA算法是在上世紀90年代初期由Srinivas和Deb教授首先提出的，該算法是基于對種群中所有的個體按照不同的層次進行分類的。NSGA算法的高效性在于運用了一個非支配分類的程序，使得多目標簡化至一個適應度函數(shù)的方式。這種方法能夠解決任意數(shù)目的多目標優(yōu)化問題，并且能夠分析和解決最大化和最小化的優(yōu)化問題。</p><p>　　NSGA通過基于非支配排序的方法保

97、留了種群中的優(yōu)良個體，并且利用適應度共享函數(shù)保持了群體的多樣性，取得了非常良好的效果。但是實際工程領域中發(fā)現(xiàn)NSGA算法還是存在著明顯的不足，這主要體現(xiàn)在如下三個方面[13]：</p><p>　　1)非支配排序的高計算復雜性。非支配排序算法一般要進行次搜索(是目標函數(shù)的數(shù)目，是種群的大小)，搜索的次數(shù)隨著目標函數(shù)數(shù)量和種群大小的增加而增多。</p><p>　　2)缺少精英策略。研究

98、結(jié)果表明，引用精英策略可以加快遺傳算法(GA)的執(zhí)行，并且還助于防止優(yōu)秀的個體丟失。</p><p>　　3)需要指定共享參數(shù)，在NSGA算法中保持種群和解的多樣性方法都是依賴于共享的概念，共享的主要問題之一就是需要人為指定一個共享參數(shù)。正是因為要對共享參數(shù)要作額外的工作，所以就需要一種不依賴共享參數(shù)的方法。</p><p>　　為了克服非支配排序遺傳算法(NSGA)的上述不足，印度科學

99、家Deb于2002年在NSGA算法的基礎上進行了改進，提出了帶精英策略的非支配排序遺傳算法(Elitist Non-Dominated Sorting Genetic Algorithm，NSGA-II)，NSGA-II 算法針對NSGA的缺陷通過以下三個方面進行了改進[16]：</p><p>　　1)提出了快速非支配的排序算法，降低了計算非支配序的復雜度，使得優(yōu)化算法的復雜度由原來的降為（為目標函數(shù)的個數(shù)，

100、為種群的大?。?lt;/p><p>　　2)引入了精英策略，擴大了采樣空間。將父代種群與其產(chǎn)生的子代種群組合在一起，共同通過競爭來產(chǎn)生下一代種群，這有利于是父代中的優(yōu)良個體得以保持，保證那些優(yōu)良的個體在進化過程中不被丟棄，從而提高優(yōu)化結(jié)果的準確度。并且通過對種群所有個體分層存放，使得最佳個體不會丟失，能夠迅速提高種群水平。</p><p>　　3)引入擁擠度和擁擠度比較算子，這不但克服了

101、NSGA算法中需要人為指定共享參數(shù)的缺陷，而且將擁擠度作為種群中個體之間的比較準則，使得準Pareto域中的種群個體能均勻擴展到整個Pareto域，從而保證了種群的多樣性。</p><p>　　3.2 快速非支配排序法</p><p>　　在NSGA算法中采用的是非支配排序方法，該方法的計算復雜度是O（），而在NSGA-II算法中采用快速非支配排序的方法，其計算復雜度僅為O（）。下面，簡要

102、說明二者計算復雜度的由來：</p><p>　?。?） 非支配排序算法的計算復雜度：</p><p>　　為了對優(yōu)化對象的個數(shù)為m，種群規(guī)模大小為N的種群進行非支配排序，每一個個體都必須和種群中其它的個體進行比較，從而得出該個體是否被支配，這樣每個個體就總共需要次的比較，需要O（）的計算復雜度。當這一步驟完成之后，繼續(xù)找出第一個非支配層上的所有個體，這需要遍歷整個種群，其總的計算復雜度就是

103、O（）。在這一步中，所有在第一個非支配層中的個體都被尋找到，為了找到隨后各個等級中的個體，重復前面的操作。可以看到，在最壞的情況下(每一層級上只有一個個體)，完成對整個種群所有個體的分級，這種算法的計算復雜度為O（）。</p><p>　?。?） 快速非支配排序算法的計算復雜度：</p><p>　　對于種群中每一個個體，都設有兩個參數(shù)和，是種群中支配個體的解的個體數(shù)量，是被個體支配的解的

104、個體的集合。</p><p>　　找出種群中所有的個體，將它們存入當前非支配集合中；</p><p>　　對于當前非支配集合中的每一個個體，遍歷它所支配的個體集合，將集合中每一個個體的都減去1，即支配個體的解的個體數(shù)量減1(因為支配個體的個體j已經(jīng)存入當前非支配集中)，如果，則將個體存入另一個集H；</p><p>　　把作為第一級非支配個體的集合，所以在中的解個體

105、是最優(yōu)的。它只支配個體，而不受其他任何個體所支配，對該集合內(nèi)所有個體都賦予相同的非支配序，然后繼續(xù)對集合H作上述分級操作，并也賦予相應的非支配序，直到所有的個體都被分級，即都被賦予賦予相應的非支配序。</p><p>　　每一次迭代操作，即上述快速非支配排序算法步驟的1)和2)需要N次計算。于是，整個迭代過程的計算復雜度最大是。這樣，整個快速非支配排序算法的計算復雜度就是：</p><p>

106、;　　根據(jù)上述快速非支配排序算法的步驟，相應的偽代碼為[16]： </p><p><b>　　對于種群P：</b></p><p>　　fast non-dominated sort(P)</p><p>　　for each pP</p><p>　　for each qP</p><p>　

107、　if pq then</p><p><b>　　=</b></p><p>　　elseif pq then</p><p><b>　　=+1</b></p><p><b>　　=</b></p><p><b>　　i=1</b

108、></p><p><b>　　while </b></p><p>　　for each p</p><p>　　for each q</p><p><b>　　=-1</b></p><p>　　if =0 then H=H</p><p>

109、;<b>　　i=i+1</b></p><p><b>　　=H</b></p><p><b>　　3.3 擁擠度</b></p><p>　　(1) 擁擠度的確定</p><p>　　在原來的NSGA算法中，采用共享的小生境技術(shù)確保證種群的多樣性，但這需要由決策者指定共享

110、參數(shù)的值[16]。為了克服NSGA算法中的這種不足，NSGA-II中引用了擁擠度的概念[16]：擁擠度表示在種群中給定點的周圍個體的密度，用表示，直觀上用個體周圍包含個體但不包含其余個體的最大長方形的長來表示，具體如圖3-1所示。</p><p>　　圖3-1 個體的擁擠度</p><p>　　在帶精英策略的非支配排序遺傳算法（NSGA-II）中，擁擠度的計算是確保種群多樣性的一個重要因素

111、，其計算步驟如下：</p><p>　　1)每個點的擁擠度置為0；</p><p>　　2)針對每個優(yōu)化目標，對種群進行非支配排序，令邊界上的兩個個體的擁擠度為無窮大，即；</p><p>　　3)對種群中其他個體的擁擠度進行計算：</p><p><b>　?。?-1） </b></p><p

112、>　　在上式中，表示點的擁擠度，表示點第個目標函數(shù)的函數(shù)值，表示點的第個目標函數(shù)的函數(shù)值。</p><p>　　(2) 擁擠度比較算子</p><p>　　經(jīng)過前面的快速非支配排序以及擁擠度計算之后，種群中的每個個體i都擁有如下兩個屬性：</p><p>　　非支配排序決定的非支配序()</p><p><b>　　擁擠度()

113、</b></p><p>　　根據(jù)這兩個屬性，可以定義擁擠度比較算子：個體與另一個個體進行比較，只要下面任意一個條件成立，則個體獲勝。</p><p>　　1)若個體所處的非支配層優(yōu)于個體所處的非支配層，即<。</p><p>　　若種群中兩個個體有相同的等級（處在相同的非支配層），且個體i的擁擠2)距離大于個體的擁擠距離，即且。</p&

114、gt;<p>　　條件1用來確保被選擇的個體屬于在種群中比較優(yōu)秀的非劣等級。條件2是根據(jù)它們的擁擠距離來選擇處在相同的非支配層的兩個個體，位于較不擁擠區(qū)域的個體（有較大的擁擠度）會被選擇。根據(jù)這兩個條件，選出種群中勝出的個體進入下一個操作。</p><p><b>　　3.4精英策略</b></p><p>　　NSGA-II算法引入了精英策略，以防止在