多目標優(yōu)化問題國內(nèi)外研究現(xiàn)狀

多目標優(yōu)化問題1幾乎現(xiàn)實世界中的所有問題都存在多個目標，而這些目標通常是相互沖突，相互競爭的。一個目標的改善往往同時引起其他目標性能的降低。也就是說，不存在使各目標函數(shù)同時達到最優(yōu)的解，而只能對他們進行協(xié)調(diào)和折衷處理。多目標優(yōu)化問題，就是尋找滿足約束條件和所有目標函數(shù)的一組決策變量和相應各目標函數(shù)值的集合（Pareto最優(yōu)解），并將其提供給決策者。由決策者根據(jù)偏好或效用函數(shù)確定可接受的各目標函數(shù)值及相應的決策狀態(tài)。多目標優(yōu)化的國內(nèi)外研究現(xiàn)狀21.傳統(tǒng)的方法：權(quán)重法，約束法，混合法，目標規(guī)劃法，最大最小法等。特點：將多個目標聚合成一個函數(shù)。缺點：各目標加權(quán)值的分配帶有較大的主觀性；優(yōu)化過程中各目標的優(yōu)度進展不可操作等；在處理高維數(shù)、多模態(tài)、非線性等復雜問題上存在許多不足。多目標優(yōu)化的國內(nèi)外研究現(xiàn)狀3遺傳算法是模擬自然界生物進化過程與機制，求解優(yōu)化與搜索問題的一類自組織、自適應的人工智能技術(shù)由于遺傳算法是對整個群體進行的進化運算操作，它著眼于個體的集合，而多目標優(yōu)化問題的非劣解一般也是一個集合，遺傳算法的這個特性表明遺傳算法非常適合求解多目標優(yōu)化問題。近年來，遺傳算法應用于多目標優(yōu)化領(lǐng)域。多目標優(yōu)化的國內(nèi)外研究現(xiàn)狀4多目標優(yōu)化遺傳算法：VEGA，HLGA，F(xiàn)FGA，MOGA，NPGA，NSGA，SPEA，NSGA-II，SPEA2，PAES缺點：多目標遺傳算法的局部搜索能力較差求解過程依賴于染色體的表示形式，即與個體編碼方式的關(guān)系很密切非劣最優(yōu)解域收斂性分析困難參數(shù)較多，如果設置不恰當會導致算法運行的性能下降多目標問題的定義多目標優(yōu)化問題的定義為：在可行域中確定由決策變量組成的向量，使得一組相互沖突的目標函數(shù)值盡量同時達到極小。設有

q個優(yōu)化目標，且這

q個優(yōu)化目標可能是相互沖突的。其數(shù)學表達式為：其中，為不等式約束條件?？尚杏?/p>

S為：目標空間

Z為：5支配關(guān)系設p和q是Pop中的任意二個個體，我們稱p支配（dominated）q，則必須滿足下列二個條件：對所有的子目標，p不比q差。即 ，其中r為子目標的數(shù)量（求極小值）。至少存在一個子目標，使p比q好。即此時稱p為非支配的，q為被支配的。6支配關(guān)系其中1、2、3、4代表四個可行解，點4表示的解支配點

1、2、3所表示的解，點2、3所表示的解均支配點1表示的解；點2與點3所表示的解彼此不相關(guān)。7Pareto

邊界非劣解又稱為Pareto最優(yōu)解，多目標優(yōu)化問題有很多個Pareto最優(yōu)解，解決多目標優(yōu)化問題的關(guān)鍵在于獲得有這些Pareto最優(yōu)解組成的集合。Pareto最優(yōu)解集在解空間中往往會形成一條邊界線（面）。8NSGA非支配排序遺傳算法NSGA（Non-dominated

SortingGeneticAlgorithm）是由Srinivas和Deb于1995年提出的，這是一種基于Pareto最優(yōu)概念的遺傳算法。優(yōu)點：優(yōu)化目標個數(shù)任選，非劣最優(yōu)解分布均勻，并允許存在多個不同的等價解。缺點：計算復雜度較高，算法復雜度是(其中N為種群大小，M為目標函數(shù)的個數(shù))，當種群較大時，計算相當耗時；沒有精英策略，精英策略能加速算法的執(zhí)行速度，而且也能在一定程度上確保已經(jīng)找到的滿意解不被丟失；需要指定共享半徑9NSGA-II102000年，Deb等人針對NSGA的不足之處，提出NSGA的改進算法—帶精英策略的非支配集排序遺傳算法（NSGA-II）。提出了非支配集排序的方法，以降低算法的計算復雜度。采用擁擠度距離，代替了需要指定共享半徑的適應度共享策略，并在快速排序后的同級比較中作為勝出標準，使Pareto域中的個體能擴展到整個Pareto域，并均勻分布。它采用了新的選擇操作：在包含父種群和子種群的交配池中，依照適應度和分布度選擇最好的N（種群大?。﹤€個體，從而使解有較好的收斂性。NSGA-II11快速的非劣解分類方法：為了根據(jù)個體的非劣解水平將種群分類，必須將每一個體與其他個體進行比較。NSGA-II算法采用快速的非劣解分類方法，計算速度提高。首先，對每一個解計算兩個屬性：ni，支配解i的解數(shù)目；si，解i所支配解的集合。找到所有ni=0的解并將其放入F1，稱F1是當前非劣解，其等級為

1。對當前非劣解中的每一個解i，考察其支配集中si的每一點j并將nj減少一個，如果某一個體j其nj成為零，我們把它放入單獨的類H。如此反復考察所有的點，得到當前非劣解H。依次類推，直至所有解被分類。NSGA-II122.擁擠距離的計算:為了保持個體分布均勻，防止個體在局部堆積，

NSGA-II算法首次提出了擁擠距離的概念。它指目標空間上的每一點與同等級相鄰兩點之間的局部擁擠

距離。使用這一方法可自動調(diào)整小生境，使計算結(jié)

果在目標空間比較均勻地散布，具有較好的魯棒性。NSGA-II13NSGA-II143.選擇運算:選擇過程使優(yōu)化朝Pareto最優(yōu)解的方向進行并

使解均勻散布。比較兩個個體，如果非劣等級不同，則取等級高（級數(shù)值?。┑狞c。否則，如果兩點在

同一等級上，則取比較稀疏區(qū)域內(nèi)的點，以使進化

朝非劣解和均勻散布的方向進行。NSGA-II154.精英保留策略:首先，將父體和子代全部個體合并成一個統(tǒng)一的種群放入進化池中，種群的個體數(shù)成為2N。然后種群按