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

多目標(biāo)優(yōu)化問題第1頁，課件共16頁，創(chuàng)作于2023年2月多目標(biāo)優(yōu)化的國內(nèi)外研究現(xiàn)狀1.傳統(tǒng)的方法：權(quán)重法，約束法，混合法，目標(biāo)規(guī)劃法，最大最小法等。特點(diǎn)：將多個(gè)目標(biāo)聚合成一個(gè)函數(shù)。缺點(diǎn)：各目標(biāo)加權(quán)值的分配帶有較大的主觀性；優(yōu)化過程中各目標(biāo)的優(yōu)度進(jìn)展不可操作等；在處理高維數(shù)、多模態(tài)、非線性等復(fù)雜問題上存在許多不足。

第2頁，課件共16頁，創(chuàng)作于2023年2月多目標(biāo)優(yōu)化的國內(nèi)外研究現(xiàn)狀遺傳算法是模擬自然界生物進(jìn)化過程與機(jī)制，求解優(yōu)化與搜索問題的一類自組織、自適應(yīng)的人工智能技術(shù)。由于遺傳算法是對(duì)整個(gè)群體進(jìn)行的進(jìn)化運(yùn)算操作，它著眼于個(gè)體的集合，而多目標(biāo)優(yōu)化問題的非劣解一般也是一個(gè)集合，遺傳算法的這個(gè)特性表明遺傳算法非常適合求解多目標(biāo)優(yōu)化問題。近年來，遺傳算法應(yīng)用于多目標(biāo)優(yōu)化領(lǐng)域。第3頁，課件共16頁，創(chuàng)作于2023年2月多目標(biāo)優(yōu)化的國內(nèi)外研究現(xiàn)狀2.多目標(biāo)優(yōu)化遺傳算法：VEGA，HLGA，F(xiàn)FGA，MOGA，NPGA，NSGA，SPEA，NSGA-II，SPEA2，PAES

缺點(diǎn)：

1.多目標(biāo)遺傳算法的局部搜索能力較差

2.求解過程依賴于染色體的表示形式，即與個(gè)體編碼方式的關(guān)系很密切

3.非劣最優(yōu)解域收斂性分析困難

4.參數(shù)較多，如果設(shè)置不恰當(dāng)會(huì)導(dǎo)致算法運(yùn)行的性能下降第4頁，課件共16頁，創(chuàng)作于2023年2月多目標(biāo)問題的定義多目標(biāo)優(yōu)化問題的定義為：在可行域中確定由決策變量組成的向量，使得一組相互沖突的目標(biāo)函數(shù)值盡量同時(shí)達(dá)到極小。設(shè)有q個(gè)優(yōu)化目標(biāo)，且這q個(gè)優(yōu)化目標(biāo)可能是相互沖突的。其數(shù)學(xué)表達(dá)式為：

其中，為不等式約束條件。可行域S為：目標(biāo)空間Z為：第5頁，課件共16頁，創(chuàng)作于2023年2月支配關(guān)系

設(shè)p和q是Pop中的任意二個(gè)個(gè)體，我們稱p支配（dominated）q，則必須滿足下列二個(gè)條件：（1）對(duì)所有的子目標(biāo)，p不比q差。即，其中r為子目標(biāo)的數(shù)量（求極小值）

。（2）至少存在一個(gè)子目標(biāo)，使p比q好。即此時(shí)稱p為非支配的，q為被支配的。第6頁，課件共16頁，創(chuàng)作于2023年2月

支配關(guān)系其中1、2、3、4代表四個(gè)可行解，點(diǎn)4表示的解支配點(diǎn)1、2、3所表示的解，點(diǎn)2、3所表示的解均支配點(diǎn)1表示的解；點(diǎn)2與點(diǎn)3所表示的解彼此不相關(guān)。

第7頁，課件共16頁，創(chuàng)作于2023年2月Pareto邊界非劣解又稱為Pareto最優(yōu)解，多目標(biāo)優(yōu)化問題有很多個(gè)Pareto最優(yōu)解，解決多目標(biāo)優(yōu)化問題的關(guān)鍵在于獲得有這些Pareto最優(yōu)解組成的集合。Pareto最優(yōu)解集在解空間中往往會(huì)形成一條邊界線（面）。

第8頁，課件共16頁，創(chuàng)作于2023年2月NSGA

非支配排序遺傳算法NSGA（Non-dominatedSortingGeneticAlgorithm）是由Srinivas和Deb于1995年提出的，這是一種基于Pareto最優(yōu)概念的遺傳算法。優(yōu)點(diǎn)：優(yōu)化目標(biāo)個(gè)數(shù)任選，非劣最優(yōu)解分布均勻，并允許存在多個(gè)不同的等價(jià)解。缺點(diǎn)：a）計(jì)算復(fù)雜度較高，算法復(fù)雜度是(其中N為種群大小，M為目標(biāo)函數(shù)的個(gè)數(shù))，當(dāng)種群較大時(shí)，計(jì)算相當(dāng)耗時(shí)；b）沒有精英策略，精英策略能加速算法的執(zhí)行速度，而且也能在一定程度上確保已經(jīng)找到的滿意解不被丟失；c）需要指定共享半徑

第9頁，課件共16頁，創(chuàng)作于2023年2月NSGA-II2000年，Deb等人針對(duì)NSGA的不足之處，提出NSGA的改進(jìn)算法—帶精英策略的非支配集排序遺傳算法（NSGA-II）。1.提出了非支配集排序的方法，以降低算法的計(jì)算復(fù)雜度。2.采用擁擠度距離，代替了需要指定共享半徑的適應(yīng)度共享策略，并在快速排序后的同級(jí)比較中作為勝出標(biāo)準(zhǔn)，使Pareto域中的個(gè)體能擴(kuò)展到整個(gè)Pareto域，并均勻分布。3.它采用了新的選擇操作：在包含父種群和子種群的交配池中，依照適應(yīng)度和分布度選擇最好的N（種群大小）個(gè)個(gè)體，從而使解有較好的收斂性。第10頁，課件共16頁，創(chuàng)作于2023年2月NSGA-II1.快速的非劣解分類方法：為了根據(jù)個(gè)體的非劣解水平將種群分類，必須將每一個(gè)體與其他個(gè)體進(jìn)行比較。NSGA-II算法采用快速的非劣解分類方法，計(jì)算速度提高。首先，對(duì)每一個(gè)解計(jì)算兩個(gè)屬性：（1）ni，支配解i的解數(shù)目；（2）si，解i所支配解的集合。找到所有ni=0的解并將其放入F1，稱F1是當(dāng)前非劣解，其等級(jí)為1。對(duì)當(dāng)前非劣解中的每一個(gè)解i，考察其支配集中si的每一點(diǎn)j并將nj減少一個(gè)，如果某一個(gè)體j其nj成為零，我們把它放入單獨(dú)的類H。如此反復(fù)考察所有的點(diǎn)，得到當(dāng)前非劣解H。依次類推，直至所有解被分類。第11頁，課件共16頁，創(chuàng)作于2023年2月NSGA-II2.擁擠距離的計(jì)算:

為了保持個(gè)體分布均勻，防止個(gè)體在局部堆積，NSGA-II算法首次提出了擁擠距離的概念。它指目標(biāo)空間上的每一點(diǎn)與同等級(jí)相鄰兩點(diǎn)之間的局部擁擠距離。使用這一方法可自動(dòng)調(diào)整小生境，使計(jì)算結(jié)果在目標(biāo)空間比較均勻地散布，具有較好的魯棒性。第12頁，課件共16頁，創(chuàng)作于2023年2月NSGA-II第13頁，課件共16頁，創(chuàng)作于2023年2月NSGA-II3.選擇運(yùn)算:

選擇過程使優(yōu)化朝Pareto最優(yōu)解的方向進(jìn)行并使解均勻散布。比較兩個(gè)個(gè)體，如果非劣等級(jí)不同，則取等級(jí)高（級(jí)數(shù)值?。┑狞c(diǎn)。否則，如果兩點(diǎn)在同一等級(jí)上，則取比較稀疏區(qū)域內(nèi)的點(diǎn)，以使進(jìn)化朝非劣解和均勻散布的方向進(jìn)行。第14頁，課件共16頁，創(chuàng)作于2023年2月NSGA-II4.精英保留策略:

首先，將父體和子代全部個(gè)體合并成一個(gè)統(tǒng)一的種群放入進(jìn)化池中，種群的個(gè)體數(shù)成為2N。然后種群按非劣解等級(jí)分類并計(jì)算每一個(gè)體的局部擁擠距離。依