多目標優(yōu)化問題

1、多目標優(yōu)化問題第1頁，共16頁，2022年，5月20日，14點9分，星期二多目標優(yōu)化的國內外研究現狀1.傳統(tǒng)的方法：權重法，約束法，混合法，目標規(guī)劃法，最大最小法等。特點：將多個目標聚合成一個函數。缺點：各目標加權值的分配帶有較大的主觀性；優(yōu)化過程中各目標的優(yōu)度進展不可操作等；在處理高維數、多模態(tài)、非線性等復雜問題上存在許多不足。 第2頁，共16頁，2022年，5月20日，14點9分，星期二多目標優(yōu)化的國內外研究現狀 遺傳算法是模擬自然界生物進化過程與機制，求解優(yōu)化與搜索問題的一類自組織、自適應的人工智能技術。由于遺傳算法是對整個群體進行的進化運算操作，它著眼于個體的集合，而多目標優(yōu)化問題的非

2、劣解一般也是一個集合，遺傳算法的這個特性表明遺傳算法非常適合求解多目標優(yōu)化問題。近年來，遺傳算法應用于多目標優(yōu)化領域 。第3頁，共16頁，2022年，5月20日，14點9分，星期二多目標優(yōu)化的國內外研究現狀2.多目標優(yōu)化遺傳算法：VEGA，HLGA，FFGA，MOGA，NPGA，NSGA，SPEA，NSGA-II，SPEA2，PAES 缺點： 1.多目標遺傳算法的局部搜索能力較差 2.求解過程依賴于染色體的表示形式，即與個體 編碼方式的關系很密切 3.非劣最優(yōu)解域收斂性分析困難 4.參數較多，如果設置不恰當會導致算法運行的性能下降第4頁，共16頁，2022年，5月20日，14點9分，星期二多目

3、標問題的定義多目標優(yōu)化問題的定義為：在可行域中確定由決策變量組成的向量，使得一組相互沖突的目標函數值盡量同時達到極小。設有 q 個優(yōu)化目標，且這 q個優(yōu)化目標可能是相互沖突的。其數學表達式為： 其中， 為不等式約束條件?？尚杏?S 為：目標空間 Z 為：第5頁，共16頁，2022年，5月20日，14點9分，星期二支配關系 設p和q是Pop中的任意二個個體，我們稱p支配 （dominated）q，則必須滿足下列二個條件：（1）對所有的子目標，p不比q差。 即 ，其中r為子目標的數量（求極小值） 。（2）至少存在一個子目標，使p比q好。 即 此時稱p為非支配的，q為被支配的。 第6頁，共16頁，2

4、022年，5月20日，14點9分，星期二 支配關系其中1、2、3、4代表四個可行解，點4表示的解支配點1、2、3所表示的解，點2、3所表示的解均支配點1表示的解；點2與點3所表示的解彼此不相關。 第7頁，共16頁，2022年，5月20日，14點9分，星期二Pareto 邊界非劣解又稱為Pareto最優(yōu)解，多目標優(yōu)化問題有很多個Pareto最優(yōu)解，解決多目標優(yōu)化問題的關鍵在于獲得有這些Pareto最優(yōu)解組成的集合。Pareto 最優(yōu)解集在解空間中往往會形成一條邊界線（面）。 第8頁，共16頁，2022年，5月20日，14點9分，星期二NSGA 非支配排序遺傳算法NSGA（Non-dominate

5、d Sorting Genetic Algorithm）是由Srinivas和Deb于1995年提出的，這是一種基于Pareto最優(yōu)概念的遺傳算法。優(yōu)點：優(yōu)化目標個數任選，非劣最優(yōu)解分布均勻，并允許存在多個不同的等價解。缺點：a）計算復雜度較高，算法復雜度是 (其中N為種群大小，M為目標函數的個數)，當種群較大時，計算相當耗時；b）沒有精英策略，精英策略能加速算法的執(zhí)行速度，而且也能在一定程度上確保已經找到的滿意解不被丟失；c）需要指定共享半徑 第9頁，共16頁，2022年，5月20日，14點9分，星期二NSGA-II2000年，Deb等人針對NSGA的不足之處，提出NSGA的改進算法帶精英策

6、略的非支配集排序遺傳算法（NSGA-II）。1.提出了非支配集排序的方法，以降低算法的計算復雜度。2.采用擁擠度距離，代替了需要指定共享半徑的適應度共享策略，并在快速排序后的同級比較中作為勝出標準，使Pareto域中的個體能擴展到整個Pareto域，并均勻分布。3. 它采用了新的選擇操作：在包含父種群和子種群的交配池中，依照適應度和分布度選擇最好的N（種群大小）個個體，從而使解有較好的收斂性。第10頁，共16頁，2022年，5月20日，14點9分，星期二NSGA-II1.快速的非劣解分類方法： 為了根據個體的非劣解水平將種群分類，必須將每一個體與其他個體進行比較。NSGA-II算法采用快速的非

7、劣解分類方法，計算速度提高。 首先，對每一個解計算兩個屬性： （1）ni，支配解i的解數目； （2）si，解i所支配解的集合。 找到所有ni=0的解并將其放入F1，稱F1是當前非劣解，其等級為 1。對當前非劣解中的每一個解i，考察其支配集中si的每一點j并將nj減少一個，如果某一個體j其nj成為零，我們把它放入單獨的類H。如此反復考察所有的點，得到當前非劣解H。依次類推，直至所有解被分類。第11頁，共16頁，2022年，5月20日，14點9分，星期二NSGA-II2. 擁擠距離的計算 : 為了保持個體分布均勻，防止個體在局部堆積，NSGA-II算法首次提出了擁擠距離的概念。它指目標空間上的每一

8、點與同等級相鄰兩點之間的局部擁擠距離。使用這一方法可自動調整小生境，使計算結果在目標空間比較均勻地散布，具有較好的魯棒性。第12頁，共16頁，2022年，5月20日，14點9分，星期二NSGA-II第13頁，共16頁，2022年，5月20日，14點9分，星期二NSGA-II3.選擇運算: 選擇過程使優(yōu)化朝Pareto最優(yōu)解的方向進行并使解均勻散布。比較兩個個體，如果非劣等級不同，則取等級高（級數值?。┑狞c。否則，如果兩點在同一等級上，則取比較稀疏區(qū)域內的點，以使進化朝非劣解和均勻散布的方向進行。第14頁，共16頁，2022年，5月20日，14點9分，星期二NSGA-II4.精英保留策略: 首先，將父體和子代全部個體合并成一個統(tǒng)一的種群放入進化池中，種群的個體數成為2N。然后種群按非劣解等級分類并計算每一個體的局部擁擠距離。依據等級的高低逐一選取個體直到個體總數達到N，從而