多目標(biāo)優(yōu)化問題中往往存在多個(gè)彼此相互沖突的目標(biāo)。與單目標(biāo)優(yōu)化不同，在多目標(biāo)優(yōu)化中，提高一個(gè)目標(biāo)的性能會(huì)引起其它一個(gè)或多個(gè)目標(biāo)性能的下降。因此，多目標(biāo)優(yōu)化問題中不存在一個(gè)單獨(dú)的優(yōu)解，而是存在一組表示各個(gè)目標(biāo)間權(quán)衡和折中關(guān)系的解集，稱該解集為Pareto優(yōu)解集。Pareto優(yōu)解集在目標(biāo)域的投影被稱為Pareto前沿。
由于很多現(xiàn)實(shí)工程問題中的優(yōu)化問題是NP難，傳統(tǒng)的數(shù)學(xué)規(guī)劃方法將會(huì)變得異常困難。而具有自然界規(guī)律啟發(fā)式特征的求解方法往往適合近似求解這些困難問題，這些方法被稱為進(jìn)化計(jì)算[1]。進(jìn)化算法基于種群的特性使其十分適合多目標(biāo)優(yōu)化問題的求解。同時(shí)，進(jìn)化算法還具有魯棒性強(qiáng)的特點(diǎn)。因此，進(jìn)化算法被廣泛應(yīng)用在多目標(biāo)優(yōu)化問題的求解上。
1 多目標(biāo)進(jìn)化問題概述
多目標(biāo)優(yōu)化問題同時(shí)優(yōu)化多個(gè)目標(biāo)，這些待優(yōu)化的目標(biāo)包含大化、小化或者兩者都有的問題。在實(shí)際處理時(shí)，為了簡(jiǎn)化問題，可以將大化或小化問題取反，使所有優(yōu)化目標(biāo)全部轉(zhuǎn)化成小化或大化問題。本文中將討論小化問題。
2 多目標(biāo)進(jìn)化算法一般流程
生物進(jìn)化是一個(gè)不斷優(yōu)化的過程，在不斷的變化過程中增加自身的適應(yīng)性。進(jìn)化計(jì)算以生物進(jìn)化為啟發(fā)，對(duì)一個(gè)解進(jìn)行抽象編碼，模擬生物進(jìn)化中的基因。進(jìn)化算法以種群為基礎(chǔ)，是一個(gè)黑盒的搜索、優(yōu)化方法，進(jìn)化算法不需要優(yōu)化問題具備一定的前提條件，例如連續(xù)性、可微性等，且一次運(yùn)行能夠產(chǎn)生一組解。因此，進(jìn)化算法特別適合處理多目標(biāo)優(yōu)化問題。
生物的進(jìn)化過程主要包括繁殖、變異、競(jìng)爭(zhēng)和選擇。與之類似，一個(gè)典型的進(jìn)化算法主要包含以下步驟：①初始化：生成一個(gè)初始化種群，記為P，其中包含N個(gè)個(gè)體（解），并記當(dāng)前代數(shù)t=0；②適應(yīng)度評(píng)價(jià)：計(jì)算每個(gè)個(gè)體x∈P的適應(yīng)度值F（x）；③繁殖：從父代種群P繁殖出后代種群Q，具體包括交叉和變異過程；④選擇：使用選擇算子從P∪Q中選擇出N個(gè)精英個(gè)體，作為下一代的父代種群P；⑤下一代進(jìn)化：增加進(jìn)化代數(shù)t=t+1，如果滿足終止條件，則停止算法并輸出P，否則進(jìn)入下一代迭代過程，即轉(zhuǎn)入第2步。
一個(gè)典型的進(jìn)化算法流程如圖1所示。
3 多目標(biāo)進(jìn)化算法分類
從進(jìn)化算法誕生之初，由于其在多目標(biāo)優(yōu)化問題上的優(yōu)異表現(xiàn)，眾多研究人員提出了多種多目標(biāo)進(jìn)化算法。根據(jù)算法特性不同，具體可分為以下幾類：
3.1 基于Pareto支配關(guān)系的多目標(biāo)進(jìn)化算法
通過Pareto支配關(guān)系，可以對(duì)兩個(gè)解進(jìn)行對(duì)比，從而利用支配信息指導(dǎo)解集的選擇。基于Pareto支配關(guān)系的多目標(biāo)進(jìn)化算法一直以來都是一個(gè)熱門研究方向，研究人員提出了許多算法，例如SPEA[2]、SPEA2[3]、PESA[4]、PESA-II[5]、NSGA-II[6]等。
基于Pareto支配的多目標(biāo)進(jìn)化算法取得了令人矚目的成就，然而在處理超多目標(biāo)優(yōu)化問題時(shí)卻面臨許多挑戰(zhàn)。由于Pareto支配的特性，超多目標(biāo)空間中的大部分解均為非支配關(guān)系，從而失去了選擇壓力。研究人員通過改進(jìn)Pareto支配關(guān)系，提出了一系列方法。
Laummans等[7]定義了一種ε支配關(guān)系，增加了一個(gè)解的支配空間；Deb等[8]根據(jù)ε支配關(guān)系，提出了ε-MOEA算法，在超多目標(biāo)優(yōu)化問題中取得了較好效果。ε-MOEA算法將目標(biāo)空間劃分成?W格，不同網(wǎng)格中的解使用ε支配關(guān)系進(jìn)行比較，相同網(wǎng)格中的解則使用傳統(tǒng)的Pareto支配關(guān)系。
2001年，Ikeda等[9]也提出了一種新的支配關(guān)系，稱為α支配。在α支配關(guān)系中，比較一個(gè)目標(biāo)的同時(shí)會(huì)考慮其它目標(biāo)函數(shù)值。通過一個(gè)線性平衡函數(shù)重新計(jì)算對(duì)比時(shí)的目標(biāo)值，若一個(gè)解在一個(gè)目標(biāo)上顯著優(yōu)于另一個(gè)解，而在另一個(gè)目標(biāo)上則略微處于弱勢(shì)，則前者仍然能α支配后者，這樣的支配關(guān)系有利于選擇更好的解。
除此之外，還有多種算法建立在改進(jìn)的Pareto支配關(guān)系之上，例如基于網(wǎng)格支配的GrEA算法[10]、基于ε排序策略的εR-EMO算法[11]等。
3.2 基于分解的多目標(biāo)進(jìn)化算法
將一個(gè)多目標(biāo)優(yōu)化問題分解為一組單目標(biāo)的子問題進(jìn)行求解也是一個(gè)常見的解決方法。常見的分解方法包括加權(quán)和法、切比雪夫法以及基于懲罰值的邊界交叉法[12]。
2007年，Zhang等[13]結(jié)合了上述幾種分解方法提出了一種基于分解的多目標(biāo)進(jìn)化算法（MOEA/D），這是近年來的一個(gè)熱門算法框架。在MOEA/D算法中，通過傳統(tǒng)的分解方法將一個(gè)多目標(biāo)優(yōu)化問題分解為一組單目標(biāo)的子問題，然后使用進(jìn)化算法同時(shí)求解這些子問題。MOEA/D還通過權(quán)重向量之間的距離關(guān)系定義了子問題間的鄰居關(guān)系。在優(yōu)化一個(gè)子問題時(shí)，通過相鄰子問題間交叉變異的進(jìn)化過程生成新解，并使用新解來更新當(dāng)前子問題的解。MOEA/D中還引入了一種鄰居子問題間的信息共享方法，即一個(gè)新解在更新對(duì)應(yīng)子問題的同時(shí)還會(huì)更新其鄰居子問題。實(shí)驗(yàn)表明，MOEA/D算法相較于以往的一些基于分解的算法，效果更為突出。Li等[14]將差分進(jìn)化的思想引入到MOEA/D的進(jìn)化過程中，同時(shí)還限制了鄰居子問題的大更新數(shù)目，進(jìn)一步提高了算法性能。 與基于Pareto支配關(guān)系的算法在超多目標(biāo)優(yōu)化問題中的局限不同，基于分解的算法能夠直接適用于超多目標(biāo)優(yōu)化問題中。針對(duì)超多目標(biāo)優(yōu)化問題的特性，研究人員也提出了許多改進(jìn)方法。Asafuddoula等[15]將系統(tǒng)抽樣和自適應(yīng)的ε控制技術(shù)引入到基于分解的進(jìn)化算法中，在超多目標(biāo)空間中生成均勻的權(quán)重向量，平衡解集的收斂性與多樣性；?榱私餼齔?多目標(biāo)空間選擇壓力過大導(dǎo)致的多樣性丟失問題，F(xiàn)abre等[16]提出了一種并行的遺傳算法，將每個(gè)子問題都關(guān)聯(lián)到一個(gè)子種群，通過子種群的進(jìn)化實(shí)現(xiàn)整個(gè)種群的進(jìn)化，實(shí)驗(yàn)結(jié)果也驗(yàn)證了其在多樣性保持方面的優(yōu)勢(shì)。
3.3 基于指標(biāo)的多目標(biāo)進(jìn)化算法
多目標(biāo)進(jìn)化算法求得的解集可以通過許多評(píng)價(jià)指標(biāo)來衡量，基于指標(biāo)的多目標(biāo)進(jìn)化算法通過評(píng)價(jià)指標(biāo)來指引算法的搜索方向，指導(dǎo)進(jìn)化過程中新種群的選擇。
Zitzler等[17]首先將評(píng)價(jià)指標(biāo)引入到進(jìn)化算法的選擇策略中，提出一種基于評(píng)價(jià)指標(biāo)的進(jìn)化算法（IBEA），可以通過任意一種評(píng)價(jià)指標(biāo)來對(duì)比候選解。在IBEA中，不需要使用例如適應(yīng)值共享等多樣性保持策略，也不需要對(duì)整個(gè)近似Pareto優(yōu)解集進(jìn)行計(jì)算，只需對(duì)比其中的部分解即可。
IH指標(biāo)可以衡量一個(gè)解集的質(zhì)量，IH指標(biāo)值越大，表示解集質(zhì)量越好。為了能夠大化一個(gè)解集的IH指標(biāo)值，Emmerich等[18]提出了一種基于S-度量選擇的多目標(biāo)進(jìn)化算法（SMS-EMOA）。SMS-EMOA通過IH指標(biāo)的梯度信息來指導(dǎo)種群進(jìn)化過程。在處理低維的多目標(biāo)優(yōu)化問題時(shí)，SMS-EMOA求得的解集具有很好的收斂性和多樣性。但是，在面對(duì)超多目標(biāo)優(yōu)化問題時(shí)，SMS-EMOA的計(jì)算復(fù)雜度成指數(shù)上升，算法效果急劇下降。其每一代進(jìn)化的計(jì)算復(fù)雜度為O（Nm/2+1），其中N為種群大小，m為問題的目標(biāo)個(gè)數(shù)。
Brockhoff等[19]將目標(biāo)空間縮小技術(shù)與基于IH指標(biāo)的方法結(jié)合起來，提出一種新的算法，通過使用不同的目標(biāo)空間縮小方法提高基于IH指標(biāo)的算法性能。
IH指標(biāo)的計(jì)算是一個(gè)非常耗時(shí)的過程，對(duì)基于IH指標(biāo)的算法有很大影響。為了克服計(jì)算過于復(fù)雜的弊端，Bader等[20]提出了一種快速的近似計(jì)算方法，使用蒙特卡羅模擬近似計(jì)算解集的IH值，并提出了一種基于IH指標(biāo)近似的多目標(biāo)進(jìn)化算法，在處理超多目標(biāo)優(yōu)化問題上取得了令人滿意的成果。
通過將非支配排序和R2指標(biāo)結(jié)合起來，Manriquez等[21]提出了R2-MOGA和R2-MODE算法，在處理超多目標(biāo)優(yōu)化問題時(shí)有顯著優(yōu)勢(shì)；Gomez等[22]也提出了一種基于R2指標(biāo)的優(yōu)化算法MOMBI，同樣也取得了不錯(cuò)的優(yōu)化效果。
3.4 混合算法
在多目標(biāo)進(jìn)化算法中，研究人員提出了眾多優(yōu)化技術(shù)，不同技術(shù)均有其獨(dú)特優(yōu)勢(shì)，例如基于Pareto支配關(guān)系的算法能夠適應(yīng)各種形狀的Pareto前沿，但在處理超多目標(biāo)優(yōu)化問題時(shí)卻顯得不盡如人意；基于分解的算法通用性較好，但是常規(guī)的分解方法卻容易導(dǎo)致解集多樣性的丟失。其它的優(yōu)化技術(shù)也各有優(yōu)缺點(diǎn)。將這些技術(shù)混合起來，結(jié)合各種方法的優(yōu)點(diǎn)來處理復(fù)雜的優(yōu)化問題，也是一種非常有效的方法。
一種方法是將全局搜索與局部搜索結(jié)合起來，即多目標(biāo)模因算法。例如，在Adra等[23]的算法中，對(duì)每一代進(jìn)化中求得的優(yōu)解使用局部搜索策略在目標(biāo)空間進(jìn)一步優(yōu)化，隨后將優(yōu)化后的解映射到對(duì)應(yīng)的決策空間并預(yù)測(cè)其具體的決策向量；在Wang等[24]的算法中，則使用局部搜索來生成子代解。
另一種廣泛使用的方法是將不同方法中的搜索策略結(jié)合起來，例如將粒子群優(yōu)化和進(jìn)化算法結(jié)合起來[25]，在每一代中，由粒子群優(yōu)化產(chǎn)生的解再使用進(jìn)化算法進(jìn)行優(yōu)化。
另一方面，還可以根據(jù)進(jìn)化過程的不同特性將整個(gè)進(jìn)化過程劃分為多個(gè)階段，在不同階段使用不同的搜索策略。例如在Yang等[26]的算法中，進(jìn)化過程包含3個(gè)階段，分別側(cè)重于被支配的解、平衡支配解和非支配解，以及著重于非支配解3個(gè)部分，結(jié)合NSGA-II算法的思想和局部增強(qiáng)搜索策略來實(shí)現(xiàn)各個(gè)階段的進(jìn)化過程。
4 結(jié)語(yǔ)
多目標(biāo)進(jìn)化算法由于其基于種群的特性而成為處理多目標(biāo)優(yōu)化問題的一種熱門方法。本文進(jìn)行了多目標(biāo)優(yōu)化問題的相關(guān)數(shù)學(xué)描述，簡(jiǎn)要介紹了相關(guān)理論定義。根據(jù)多目標(biāo)進(jìn)化算法的特性，本文還將近年來的主流進(jìn)化算法分為4類進(jìn)行闡述，并分析了它們的優(yōu)缺點(diǎn)，以更好地應(yīng)用于多目標(biāo)優(yōu)化問題的求解。
上一篇：
明清如何疏解北京人口
簡(jiǎn)繁切換