【正文】 算法進(jìn)化模式單一、局部搜索性能欠佳，之所以存在這些不足，主要是因?yàn)檫@類算法大多由第二類算法改進(jìn)得到，因此進(jìn)化模式不可能完全擺脫先前的算法框架，并且遺傳算法的進(jìn)化原理決定了它不可能具有性能較高的局部搜索能力。代表算法有NPGAII、NSGAII、PAES和SPEA等[9]。第四類算法是采用其他搜索算法策略改進(jìn)的MOEA。這類算法由于采用的進(jìn)化策略是基于模擬退火搜索、禁忌搜索、粒子群優(yōu)化、小生境策略等不以傳統(tǒng)遺傳算法進(jìn)化結(jié)構(gòu)為主導(dǎo)的優(yōu)化策略，因此在早期的多目標(biāo)進(jìn)化算法研究中并未受到廣泛重視，只是在近年隨著多目標(biāo)遺傳算法局部搜索性能欠佳的不足逐漸呈現(xiàn)，以及其他進(jìn)化策略單目標(biāo)進(jìn)化算法的迅速發(fā)展才開(kāi)始活躍起來(lái)。這類算法由于群體規(guī)模適中，因此算法復(fù)雜性相對(duì)較低，而且由于算法局部搜索性能優(yōu)越，因此常?？梢耘c現(xiàn)有的MOGA結(jié)合，形成新的精英算法。其不足是，由于算法的全局搜索性能不象遺傳算法那樣既能保證全局尋優(yōu)、又能維持群體多樣性，因此，在算法設(shè)計(jì)時(shí)往往設(shè)置了許多控制參數(shù)對(duì)算法性能進(jìn)行調(diào)整，這又導(dǎo)致在求解問(wèn)題時(shí)常常需要借助大量試驗(yàn)計(jì)算分析確定進(jìn)化參數(shù)，因此算法性能不夠穩(wěn)健。代表算法有MOSE、MOPSO等[10]。除了上述四類算法外，一些學(xué)者在演化策略中引入偏好分級(jí)或適應(yīng)值分享機(jī)制獲取滿意解。但由于這些方法不能通過(guò)幾次運(yùn)行獲得穩(wěn)定的非劣解集，且算法復(fù)雜性較高，因此這類研究不是多目標(biāo)進(jìn)化算法研究的主流方向。而考慮偏好關(guān)系對(duì)遺傳進(jìn)化的影響，大多是用模糊集方法進(jìn)行偏好信息的處理，而進(jìn)一步利用偏好對(duì)進(jìn)化進(jìn)行指導(dǎo)或通過(guò)進(jìn)化引導(dǎo)偏好的交互式多目標(biāo)進(jìn)化算法還僅僅處于概念研究階段，距算法實(shí)現(xiàn)尚有較大差距。多目標(biāo)遺傳算法的研究一直是這類算法研究的主流方向：盡管遺傳算法具有很好的全局搜索性能，但由于算法原理的限制，使它不可能具有其他進(jìn)化策略或啟發(fā)式局部搜索算法好的局部搜索性能，因此，以進(jìn)化算法為算法主體，結(jié)合遺傳算法全局搜索和一般啟發(fā)式進(jìn)化策略局部搜索的優(yōu)勢(shì)，獲得高性能的多目標(biāo)優(yōu)化算法，成為多目標(biāo)進(jìn)化算法研究的潛在發(fā)展方向。 多目標(biāo)進(jìn)化算法如果按決策方式劃分，則可以分為三類[11]：前決策（先驗(yàn)式）、后決策（后驗(yàn)式）和交互式?jīng)Q策，這是按照用戶的人工決策信息作用于算法的時(shí)間先后劃分的。其中，后決策是最常用的技術(shù)，即算法終止時(shí)提供給用戶一組最優(yōu)解。目前絕大多數(shù)多目標(biāo)進(jìn)化算法是排序選擇法和后決策技術(shù)類型的。SPEA/SPEA2 (Zitzler amp。 Thiele 2001)和NSGA/NSGAII (Srinivas amp。 Deb 2002)兩類算法目前的應(yīng)用更廣泛，也更具有代表性。由于本文需要對(duì)多目標(biāo)進(jìn)化算法的結(jié)構(gòu)進(jìn)行深入的分析，所以需要在此選擇一個(gè)代表性的算法，通過(guò)該算法的簡(jiǎn)介，來(lái)描述一下多目標(biāo)進(jìn)化算法的一些基本概念和工作原理。本文將以NSGAII算法和MOGLS（MultiObjective Genetic Lcal Search）算法為例，通過(guò)算例和指定的函數(shù)指標(biāo)來(lái)分析比較它們各自性能的優(yōu)缺點(diǎn)。NSGAII算法首先隨機(jī)產(chǎn)生一個(gè)初始種群，對(duì)種群通過(guò)采用輪盤(pán)賭的方式選擇、交叉和變異操作獲得新的種群，將種群中的個(gè)體構(gòu)造其Pareto 邊界集，并根據(jù)個(gè)體間的聚集距離，建立偏序關(guān)系，最終從偏序關(guān)系中選擇原始種群規(guī)模大小的個(gè)體，組成新的種群，完成了一次進(jìn)化操作。由此可見(jiàn)，對(duì)于多目標(biāo)進(jìn)化算法而言，構(gòu)造Pareto 邊界集和計(jì)算個(gè)體間的聚集距離是新的概念，也是絕大多數(shù)多目標(biāo)進(jìn)化算法共有的流程，這為之后提取算法公共流程方式的討論提供了基本的依據(jù)。MOGLS是Ishibuchi和Murata兩位學(xué)者提出的。最初的MOGLS是在遺傳進(jìn)化過(guò)程中，每代遺傳操作生成新個(gè)體后，對(duì)現(xiàn)有群體中的所有個(gè)體進(jìn)行局部搜索；后來(lái)Ishibuchi等人對(duì)局部搜索的步長(zhǎng)選取、鄰域搜索效率做了進(jìn)一步研究后，將局部搜索過(guò)程僅應(yīng)用于當(dāng)前群體中的優(yōu)秀，顯著提高了算法效率，改進(jìn)后的算法可獲得與SPEA、NSGAII相當(dāng)?shù)膬?yōu)化性能。MOGLS的優(yōu)點(diǎn)是通過(guò)隨機(jī)權(quán)將MOP轉(zhuǎn)化為SOP，算法容易實(shí)現(xiàn)，并且恰當(dāng)控制MOGLS中鄰域搜索個(gè)體的選取及步長(zhǎng)可以在減少計(jì)算復(fù)雜度的同時(shí)獲得良好的計(jì)算結(jié)果；算法的不足之處是，算法的構(gòu)造是基于MOP轉(zhuǎn)化為SOP的思想，因此在不明確多個(gè)目標(biāo)偏好情況下，采用隨機(jī)權(quán)的方法往往不能保證所得非劣解集分布的均勻性。第2章 多目標(biāo)進(jìn)化算法 多目標(biāo)優(yōu)化基本概念 多目標(biāo)問(wèn)題( MOP) 的一般描述為: 給定決策向量 , 它滿足下列約束: ( 21) ( 22)設(shè)有r 個(gè)優(yōu)化目標(biāo), 且這r 個(gè)優(yōu)化目標(biāo)是相互沖突的, 優(yōu)化目標(biāo)可表示為: 尋求, 使在滿足約束( 21) 和( 22) 的同時(shí)達(dá)到最小。對(duì)于多目標(biāo)優(yōu)化問(wèn)題, 由于其待優(yōu)化的各個(gè)子目標(biāo)一般是相互沖突的, 因此需要定義解個(gè)體間的優(yōu)劣關(guān)系, 以便對(duì)候選解進(jìn)行評(píng)價(jià)與取舍。本文采用廣泛使用的Pareto 最優(yōu)性[12]定義。定義1 ( 個(gè)體的Pareto 支配關(guān)系) 。設(shè)和是進(jìn)化群體中的任意兩個(gè)不同的個(gè)體,稱支配(dominate) ,則必須滿足下列二個(gè)條件:( 1) 對(duì)所有的子目標(biāo), 不比 差, 即 ( k=1, 2,?, r) 。 （2） 至少存在一個(gè)子目標(biāo),使比好。即, 使其中r 為子目標(biāo)的數(shù)量。此時(shí)稱 為非支配的( non dominated), 為被支配的( dominated) 。表示為, 其中“”是支配關(guān)系。定義2( Pareto 非支配集)。設(shè)有解集,若中的個(gè)體不被任何其它個(gè)體支配, 則是 中的非支配個(gè)體。 由 中的所有非支配個(gè)體構(gòu)成的子集稱為 的非支配集。即: 最優(yōu)性的含義為：是Pareto最優(yōu)解，表示在整個(gè)解空間中，不存在這樣的解：某一個(gè)目標(biāo)比小的同時(shí)，保持其余個(gè)目標(biāo)值不大于x的目標(biāo)值。因此，滿足這種最優(yōu)性的“最優(yōu)解”往往不是單個(gè)解，而是一組滿足上式最優(yōu)性條件的非劣解集合，包含非劣解的集合稱作非劣解集（Pareto Solutions Set）或非受控解集(nondominated solutions set)；非劣解對(duì)應(yīng)的目標(biāo)值在目標(biāo)空間中稱為非劣點(diǎn)；最優(yōu)解集在優(yōu)化目標(biāo)空間構(gòu)成的分布稱作非劣解前沿。在決策和優(yōu)化問(wèn)題中，最優(yōu)性取決于如何比較和排序候選解，及決策者的偏好結(jié)構(gòu)。從決策者的立場(chǎng)來(lái)看，一般認(rèn)為每對(duì)候選解具有以下比較關(guān)系：(1)一方明顯優(yōu)于另一方；(2)兩者相互非劣；(3)兩者不具有可比性。由此才可以對(duì)每對(duì)解之間的優(yōu)劣比較進(jìn)行細(xì)致的區(qū)分[13]。MOP問(wèn)題包含多個(gè)待優(yōu)化的子目標(biāo)，通常EAs用于多目標(biāo)優(yōu)化時(shí)必須考慮兩個(gè)關(guān)鍵問(wèn)題：(1)為了保證朝Pareto最優(yōu)集的方向搜索，如何實(shí)施適應(yīng)度賦值和選擇。(2)為了避免未成熟收斂和獲得均勻分布且范圍最廣的非劣解，如何保持群體的多樣性。在已有研究中，多目標(biāo)遺傳算法的適應(yīng)值設(shè)計(jì)(Fitness Assignment)主要有基于加權(quán)策略、基于目標(biāo)設(shè)計(jì)策略和基于非劣解等級(jí)優(yōu)先策略三種設(shè)計(jì)策略[14]：(1)基于加權(quán)策略的適應(yīng)值設(shè)計(jì)，即基于聚合策略的方法，是通過(guò)加權(quán)策略將多個(gè)目標(biāo)轉(zhuǎn)化為單個(gè)目標(biāo)后進(jìn)行優(yōu)化。這種適應(yīng)值設(shè)計(jì)的遺傳算法通常需要在算法進(jìn)化過(guò)程中系統(tǒng)地對(duì)函數(shù)中的參數(shù)的權(quán)重值進(jìn)行調(diào)整，以便得到一組非劣解集。在進(jìn)化的每一代中參數(shù)呈現(xiàn)有規(guī)律的變化，但在該代操作過(guò)程中保持不變，常見(jiàn)的進(jìn)化加權(quán)法，個(gè)體的評(píng)估使用確定的加權(quán)組合，所有個(gè)體都有一個(gè)適應(yīng)度值，保證了搜索方向朝最優(yōu)解邁進(jìn)。(2)基于目標(biāo)設(shè)計(jì)策略的算法，即基于準(zhǔn)則的策略，每當(dāng)個(gè)體選中后進(jìn)行復(fù)制時(shí)根據(jù)不同的目標(biāo)來(lái)決定是否被復(fù)制至配對(duì)池。此方法通過(guò)在不同進(jìn)化代之間更換優(yōu)化目標(biāo)每次優(yōu)化一個(gè)目標(biāo)，使算法群體每次運(yùn)行得到一個(gè)非劣解，從而通過(guò)多次運(yùn)行找到優(yōu)化問(wèn)題的非劣解集。目前，常用的方法是在選擇階段根據(jù)概率來(lái)確定各子目標(biāo)的排序，該概率值由用戶確定或隨機(jī)產(chǎn)生。這種策略存在的問(wèn)題是進(jìn)化結(jié)果容易偏向某些極端邊界解，并且對(duì)Pareto最優(yōu)前端的非凸部敏感。(3)基于非劣解等級(jí)優(yōu)先概念的適應(yīng)值分配策略由Goldberg最先提出，后人大多在此基礎(chǔ)上進(jìn)行改進(jìn)，如將群體劃分為幾個(gè)有序的子群體。這類算法的適應(yīng)值設(shè)計(jì)主要有等級(jí)優(yōu)先、深度優(yōu)先和基于優(yōu)先數(shù)三種：等級(jí)優(yōu)先策略算法在計(jì)算適應(yīng)值時(shí)主要考慮個(gè)體在群體中“優(yōu)于”其他個(gè)體的數(shù)目或考慮優(yōu)于該個(gè)體的其他個(gè)體數(shù)目之和，以此確定給個(gè)體的適應(yīng)度值；而深度優(yōu)先策略算法在分配個(gè)體適應(yīng)值時(shí)主要以個(gè)體所在的非劣解等級(jí)及等級(jí)內(nèi)的疏密程度有關(guān)；基于優(yōu)先數(shù)的適應(yīng)值分配算法在計(jì)算個(gè)體適應(yīng)值時(shí)，考慮了個(gè)體所優(yōu)先于或劣于群體中其他個(gè)體的數(shù)目。一般來(lái)說(shuō)直接統(tǒng)計(jì)優(yōu)勝個(gè)體數(shù)目的操作方式簡(jiǎn)單，在原理上一目了然。單目標(biāo)優(yōu)化中的目標(biāo)函數(shù)常與適應(yīng)度函數(shù)相同，但MOP問(wèn)題中的適應(yīng)度賦值和選擇必須考慮幾個(gè)子目標(biāo)，MOEAs必須根據(jù)個(gè)體間的Pareto優(yōu)勝關(guān)系和其他信息為個(gè)體確定適應(yīng)度值，這種適應(yīng)度值和每個(gè)目標(biāo)函數(shù)的具體大小沒(méi)有直接關(guān)系。另外，與單目標(biāo)優(yōu)化不同的是，在個(gè)體保持不變的條件下，同一個(gè)體在這一代和下一代的適應(yīng)值可能不相等。Pareto優(yōu)勝關(guān)系是決定個(gè)體適應(yīng)度函數(shù)值的重要依據(jù)，很多MOEAs根據(jù)個(gè)體間的這種關(guān)系，將個(gè)體的適應(yīng)度函數(shù)值分成兩個(gè)層次，即劣解和非劣解，后者的適應(yīng)度值總是優(yōu)于前者。當(dāng)個(gè)體間沒(méi)有Pareto優(yōu)勝關(guān)系時(shí)，其他形式的個(gè)體信息被用于確定適應(yīng)度函數(shù)值，其中個(gè)體密度值是利用最多的信息，并采用不同的方法估計(jì)個(gè)體密度值。基于Pareto優(yōu)勝關(guān)系的選擇方法已經(jīng)被廣大研究者采納，現(xiàn)已有多種基于Pareto的適應(yīng)度賦值方案，其中基于種群個(gè)體級(jí)別排序的適應(yīng)度賦值方法是較常見(jiàn)的一種方法。多目標(biāo)問(wèn)題與單目標(biāo)問(wèn)題不同，它的優(yōu)劣性與支配關(guān)系并非定義目標(biāo)向量之間的那種整體有序關(guān)系，只是給出部分有序關(guān)系，因而種群的級(jí)別排序不具有唯一性。假設(shè)第代種群中的個(gè)體，在第代種群個(gè)體排序中的位置為，基于個(gè)體排序的適應(yīng)度賦值步驟描述如下：(1)基于的數(shù)值將種群中所有個(gè)體進(jìn)行級(jí)別排序。(2)利用線性或非線性的插值方法在最低序號(hào)與最高序號(hào)之間進(jìn)行插值。(3)具有相同序號(hào)的個(gè)體進(jìn)行適應(yīng)度共享算子操作，即通過(guò)除以相同序號(hào)的個(gè)體數(shù)目得到新的適應(yīng)度值，另外，也可以給不同序號(hào)的個(gè)體分配固定不變的適應(yīng)度值。因?yàn)镋As是并行地處理一組解，通過(guò)雜交和變異來(lái)搜索空間以尋找可能的最優(yōu)區(qū)域，通過(guò)選擇來(lái)搜索具有較高適應(yīng)度的個(gè)體。傳統(tǒng)的進(jìn)化算法在Pareto最優(yōu)集上執(zhí)行多目標(biāo)搜尋，希望找出盡可能均勻分布的解集，因而個(gè)體的多樣性減少的很快，經(jīng)常收斂至單個(gè)解而丟失多個(gè)其他非劣解。在進(jìn)化過(guò)程中某些具有較高適應(yīng)度個(gè)體的大量復(fù)制造成高選擇壓力，使得個(gè)別具有更高適應(yīng)度的個(gè)體得不到遺傳的機(jī)會(huì)，甚至導(dǎo)致整個(gè)群體出現(xiàn)同解的現(xiàn)象[15]。如果單純從群體多樣性出發(fā)，群體規(guī)模應(yīng)該越大越好，但群體規(guī)模太大會(huì)帶來(lái)若干弊?。阂皇菑挠?jì)算效率來(lái)看，群體越大，導(dǎo)致其適應(yīng)度評(píng)估次數(shù)增加，引起計(jì)算量的增加，從而影響算法效能；二是群體中個(gè)體生存下來(lái)的選擇概率大多采用和適應(yīng)度成比例的方法，當(dāng)群體中個(gè)體非常多時(shí)，少量適應(yīng)度很高的個(gè)體會(huì)被選擇而生存下來(lái)，大多數(shù)個(gè)體被淘汰，嚴(yán)重影響交叉操作。因此群體規(guī)模只能維持在一定數(shù)量上，它并不能成為解決進(jìn)化算法多樣性的途徑。進(jìn)化算法由于其進(jìn)化算子固有的隨機(jī)誤差，因而基于有限群體實(shí)施進(jìn)化時(shí)會(huì)出現(xiàn)收斂至某一個(gè)解。因?yàn)槎嗄繕?biāo)優(yōu)化的目的是得到一組在整個(gè)Pareto曲面上盡可能均勻分布的一組解，因此必須在進(jìn)化過(guò)程中采取措施避免進(jìn)化結(jié)果收斂至單個(gè)解。為使算法優(yōu)化得到一組盡可能分布均勻的非劣解集而非此集合中的非劣解極值點(diǎn)，大多數(shù)MOEAs在當(dāng)代群體中維持多樣性是在選擇過(guò)程中結(jié)合了密度信息，即個(gè)體在其鄰域范圍內(nèi)所占的密度越高被選擇復(fù)制的機(jī)會(huì)越小?，F(xiàn)有多目標(biāo)遺傳算法可根據(jù)統(tǒng)計(jì)概率密度估計(jì)的方法加以分類為如下三種策略來(lái)維持群體多樣性：(1)基于核函數(shù)的評(píng)價(jià)策略：基于核函數(shù)的評(píng)價(jià)策略主要通過(guò)計(jì)算以個(gè)體為“核”、群體中其他個(gè)體距離“核”的核函數(shù)之和，通過(guò)優(yōu)先保留核函數(shù)值較大的個(gè)體即較稀疏的解個(gè)體達(dá)到維持群體多樣性的目的。具體應(yīng)用時(shí)首先根據(jù)內(nèi)核函數(shù)來(lái)定義一個(gè)點(diǎn)的鄰域范圍，內(nèi)核函數(shù)采用至另一點(diǎn)的距離作為參數(shù)。每一個(gè)個(gè)體計(jì)算至其他個(gè)體的距離，通過(guò)內(nèi)核函數(shù)的映射后求和計(jì)算出值，該累加值代表了個(gè)體的密度估計(jì)。(2)基于鄰域解數(shù)目的評(píng)價(jià)策略：基于鄰域解數(shù)目的評(píng)價(jià)策略是以評(píng)價(jià)解為核心、包含一定數(shù)量鄰域解的鄰域半徑為指標(biāo)，優(yōu)先保留鄰域半徑較大的個(gè)體即較稀疏的解個(gè)體。該策略主要考慮給定點(diǎn)至第個(gè)最近鄰居的距離，以便估計(jì)出其在鄰域內(nèi)的密度。(3)分區(qū)統(tǒng)計(jì)數(shù)目策略：分區(qū)統(tǒng)計(jì)數(shù)目策略是將目標(biāo)空間劃分成一定比例的區(qū)域，通過(guò)統(tǒng)計(jì)個(gè)體所在區(qū)域中鄰域解數(shù)目來(lái)確定個(gè)體被保留的概率鄰域解數(shù)目越大，被保留概率越小。該方法采用一個(gè)網(wǎng)格來(lái)定義空間上的鄰居關(guān)系，個(gè)體的密度只要通過(guò)簡(jiǎn)單地統(tǒng)計(jì)同一網(wǎng)格內(nèi)的個(gè)體數(shù)目即可，這種網(wǎng)絡(luò)可以是固定的，也可以根據(jù)當(dāng)前群體進(jìn)行自適應(yīng)調(diào)整。多目標(biāo)進(jìn)化算法與單目標(biāo)進(jìn)化算法類似，為了提高群體多樣性，在算法過(guò)程中盡量采用小生境（Niche）共享技術(shù)，使得在一個(gè)群體內(nèi)可以形成在多目標(biāo)問(wèn)題上分布均勻的非劣最優(yōu)解集。具有相同Pareto級(jí)別序號(hào)的解個(gè)體在實(shí)施共享適應(yīng)度值后，還必須按解的目標(biāo)向量之間的空間距離進(jìn)行小生境規(guī)模調(diào)整。當(dāng)兩個(gè)解的目標(biāo)向量之間的空間距離小于某一預(yù)定值時(shí)，相應(yīng)解的小生境規(guī)模就必須進(jìn)行調(diào)整。此外，還有同時(shí)基于決策向量空間與目標(biāo)向量空間的混合共享技術(shù)，共享問(wèn)題的關(guān)鍵是如何確定共享參數(shù)，的選擇將會(huì)影響算法的性能，而適應(yīng)度共享效果則共同取決于和種群大小[16]。遺傳算法是基于隨機(jī)進(jìn)化選擇的算法，因此，為改善遺傳算法的收斂性能，現(xiàn)有多目標(biāo)遺傳算法大都引入了精英保留策略。現(xiàn)有算法中精英策略的實(shí)現(xiàn)方式主要有兩種：其一是采用新舊群體合并，通過(guò)確定性的選擇方法在混合群體中選擇后代，而不是采用變化之后的配對(duì)池來(lái)替換舊群體，增大了精英個(gè)體在后代群體中出現(xiàn)的概率，以此改善算法收斂性。另一種實(shí)現(xiàn)方式是采用獨(dú)立于進(jìn)化群體的伴隨群體，即使用帶有所謂的檔案（Archive）的方式，保留與更新算法進(jìn)化過(guò)程中搜索到的非劣解集來(lái)維護(hù)當(dāng)代群體中的滿意群體，使其能夠復(fù)制到下一代，伴隨群體僅作為一個(gè)外部存儲(chǔ)集，獨(dú)立于進(jìn)化過(guò)程的優(yōu)化操作[17]。由于內(nèi)存資源的限制，以上兩種最優(yōu)個(gè)體保留