【正文】 m = MaxGens = 1000 PopSize = 100Pc = 。 Pm = MaxGens = 1000 PopSize = 100Pc = 。采用這兩種算法對典型的多目標(biāo)函數(shù)優(yōu)化KUR算例進(jìn)行了優(yōu)化求解，將兩種算法的所得結(jié)果進(jìn)行比較分析，研究結(jié)果表明，NSGAII有比 MOGLS更優(yōu)的非劣解等級及非劣解集分布，因此驗(yàn)證了這兩種算法對多目標(biāo)函數(shù)優(yōu)化問題的求解性能的強(qiáng)弱關(guān)系。而以現(xiàn)有的條件來看，這是很難辦到的，研究人員只能在給定初始參數(shù)后，運(yùn)行算法，等待結(jié)果的輸出，而中間的執(zhí)行過程透明，也不可控，這使得通過測試來進(jìn)行算法改進(jìn)的效率較為低下。另外，對于結(jié)果的比較，也應(yīng)該有統(tǒng)一的、通用的優(yōu)劣標(biāo)準(zhǔn)或指標(biāo)體系。因此，本文在比較函數(shù)優(yōu)化算例結(jié)果時(shí)，首先對兩種種算法優(yōu)化和所得的結(jié)果進(jìn)行比較，進(jìn)而初步確定這兩種算法對于少變量復(fù)雜空間優(yōu)化問題的求解性能，然后參照兩種種算法求解ZDT4算例所得的非劣解集(見附錄B)，通過類似方法評價(jià)出算法對多變量函數(shù)優(yōu)化問題的求解能力。經(jīng)實(shí)驗(yàn)確定，三種算法優(yōu)化測試函數(shù)的進(jìn)化參數(shù)設(shè)定為：群體規(guī)模：100/200進(jìn)化代數(shù)：500/1000交叉概率：變異概率：MOGLS每代個(gè)體的非劣解局部搜索步長：5所以本實(shí)驗(yàn)要獲得8組解。尤其是Zitzler、Deb、Thiele提出的系列測試函數(shù)，是目前為止評價(jià)新的多目標(biāo)優(yōu)化算法性能時(shí)采用最廣泛的測試函數(shù)族[27]，因此，對新算法的評價(jià)及其改進(jìn)具有重要的指導(dǎo)意義。但MOGLS能處理帶有凹的Praeto前端的多目標(biāo)進(jìn)化問題。（3）選擇：重復(fù)以下過程去選擇父代解的： 通過(27) 在適應(yīng)度函數(shù)(*1)中計(jì)算隨機(jī)的權(quán)值，、。從用于通過交叉操作的后代群體的當(dāng)前群體中選擇一組父代解，、已經(jīng)通過上面的式子確定，在當(dāng)前種群中每個(gè)解的適應(yīng)度已經(jīng)作為個(gè)目標(biāo)權(quán)值之和而得到。這個(gè)權(quán)值被定義為 (27) 其中，是隨機(jī)值。每個(gè)解通過不同的權(quán)值矢量執(zhí)行。使個(gè)體數(shù)量達(dá)到。(3)引入精英策略，擴(kuò)大采樣空間。由原來的降到，其中，為目標(biāo)函數(shù)個(gè)數(shù)，為種群大小。其中, ( 24) 表示個(gè)體i 的小生境數(shù)。然后著重介紹了多目標(biāo)進(jìn)化算法的關(guān)鍵技術(shù)，現(xiàn)代多目標(biāo)進(jìn)化算法正是在這些方面存在差異，也是判斷算法之間性能優(yōu)劣的出發(fā)點(diǎn)?，F(xiàn)有的性能評價(jià)體系可以分為兩種形式[22]：1. 理論證明理論證明即是對算法的復(fù)雜度、收斂性等進(jìn)行求解和比較，即通過理論的分析得出正確的結(jié)論。以解集間覆蓋率為例，該覆蓋率又稱為S指標(biāo)(Zitzler, 2000) [21]，用來計(jì)算一個(gè)解集中被另一個(gè)解集中的個(gè)體支配的個(gè)體所占的比率。然而在對多目標(biāo)進(jìn)化算法的性能進(jìn)行評價(jià)時(shí)，一般需要考慮到三個(gè)較為重要的因素[19]：算法的效率、算法的效果，以及算法的魯棒性。對于選中的個(gè)體，隨機(jī)選擇某一位進(jìn)行取反操作。 (4) 優(yōu)化準(zhǔn)則：也可稱作終止條件，是用來判斷算法是否可以終止的標(biāo)準(zhǔn)。這些信息包括密度信息，個(gè)體進(jìn)入伴隨群體所需時(shí)間。此外，還有同時(shí)基于決策向量空間與目標(biāo)向量空間的混合共享技術(shù)，共享問題的關(guān)鍵是如何確定共享參數(shù)，的選擇將會影響算法的性能，而適應(yīng)度共享效果則共同取決于和種群大小[16]。每一個(gè)個(gè)體計(jì)算至其他個(gè)體的距離，通過內(nèi)核函數(shù)的映射后求和計(jì)算出值，該累加值代表了個(gè)體的密度估計(jì)。在進(jìn)化過程中某些具有較高適應(yīng)度個(gè)體的大量復(fù)制造成高選擇壓力，使得個(gè)別具有更高適應(yīng)度的個(gè)體得不到遺傳的機(jī)會，甚至導(dǎo)致整個(gè)群體出現(xiàn)同解的現(xiàn)象[15]。當(dāng)個(gè)體間沒有Pareto優(yōu)勝關(guān)系時(shí)，其他形式的個(gè)體信息被用于確定適應(yīng)度函數(shù)值，其中個(gè)體密度值是利用最多的信息，并采用不同的方法估計(jì)個(gè)體密度值。目前，常用的方法是在選擇階段根據(jù)概率來確定各子目標(biāo)的排序，該概率值由用戶確定或隨機(jī)產(chǎn)生。由此才可以對每對解之間的優(yōu)劣比較進(jìn)行細(xì)致的區(qū)分[13]。表示為, 其中“”是支配關(guān)系。第2章 多目標(biāo)進(jìn)化算法 多目標(biāo)優(yōu)化基本概念 多目標(biāo)問題( MOP) 的一般描述為: 給定決策向量 , 它滿足下列約束: ( 21) ( 22)設(shè)有r 個(gè)優(yōu)化目標(biāo), 且這r 個(gè)優(yōu)化目標(biāo)是相互沖突的, 優(yōu)化目標(biāo)可表示為: 尋求, 使在滿足約束( 21) 和( 22) 的同時(shí)達(dá)到最小。 Deb 2002)兩類算法目前的應(yīng)用更廣泛，也更具有代表性。但由于這些方法不能通過幾次運(yùn)行獲得穩(wěn)定的非劣解集，且算法復(fù)雜性較高，因此這類研究不是多目標(biāo)進(jìn)化算法研究的主流方向。這類算法的不足之處是，算法進(jìn)化模式單一、局部搜索性能欠佳，之所以存在這些不足，主要是因?yàn)檫@類算法大多由第二類算法改進(jìn)得到，因此進(jìn)化模式不可能完全擺脫先前的算法框架，并且遺傳算法的進(jìn)化原理決定了它不可能具有性能較高的局部搜索能力。代表算法有VEGA、WBGA、DM等。這是因?yàn)閭鹘y(tǒng)數(shù)學(xué)規(guī)劃方法存在一些缺陷,例如有些方法對Pareto 前沿比較敏感,當(dāng)Pareto 前沿是凹的或者不連續(xù)時(shí),這些方法失效。多目標(biāo)進(jìn)化算法是一門新興的學(xué)科，理論與算法并不完善，尚處于發(fā)展階段。多目標(biāo)優(yōu)化問題的各目標(biāo)之間通過決策變量相互制約,對其中一個(gè)目標(biāo)優(yōu)化必須以其它目標(biāo)作為代價(jià),而且各目標(biāo)的單位又往往不一致,因此很難客觀地評價(jià)多目標(biāo)問題解的優(yōu)劣性。多目標(biāo)進(jìn)化算法的應(yīng)用應(yīng)該在未來不斷地延續(xù)，MOEA的理論分析比它本身更復(fù)雜而且應(yīng)該通過主要從事計(jì)算機(jī)和數(shù)學(xué)研究人員的努力工作來解決。許多MOEA的方面被廣泛地調(diào)研，然而一些問題仍然沒有被很好地受到關(guān)注。3. 分別利用NSGAII算法和MOGLS算法對算例進(jìn)行求解，并用C指標(biāo)對兩種算法的結(jié)果進(jìn)行評價(jià)，得出它們各自的優(yōu)缺點(diǎn)。進(jìn)化算法(Evolutionary Algorithm, EA)是一種通過模擬生物進(jìn)化規(guī)律來進(jìn)行選擇與變化的隨機(jī)搜索算法，起源于20 世紀(jì)50 年代末，現(xiàn)有的代表性進(jìn)化方法有遺傳算法(Genetic Algorithm, GA)、進(jìn)化規(guī)劃(Evolutionary Programming, EP)和進(jìn)化策略(EvolutionStrategy, ES)等幾種方法[2]。多目標(biāo)進(jìn)化算法(MultiObjective Evolutionary Algorithm, MOEA)就是一類可以有效解決這種問題的優(yōu)化技術(shù)[3]。遺傳算法自出現(xiàn)以來在許多領(lǐng)域得到了廣泛的應(yīng)用，在解決簡單的單目標(biāo)優(yōu)化問題方面取得了很好的成果，但面對復(fù)雜的多目標(biāo)優(yōu)化問題，傳統(tǒng)的遺傳算法就顯得力不從心。按照算法原理與進(jìn)化模式劃分，現(xiàn)有多目標(biāo)進(jìn)化算法可分如下四大類：第一類算法是早期基于單目標(biāo)群體優(yōu)化的MOGA。代表算法有MOGA、NSGA和NPGA等。其不足是，由于算法的全局搜索性能不象遺傳算法那樣既能保證全局尋優(yōu)、又能維持群體多樣性，因此，在算法設(shè)計(jì)時(shí)往往設(shè)置了許多控制參數(shù)對算法性能進(jìn)行調(diào)整，這又導(dǎo)致在求解問題時(shí)常常需要借助大量試驗(yàn)計(jì)算分析確定進(jìn)化參數(shù)，因此算法性能不夠穩(wěn)健。目前絕大多數(shù)多目標(biāo)進(jìn)化算法是排序選擇法和后決策技術(shù)類型的。MOGLS是Ishibuchi和Murata兩位學(xué)者提出的。 （2） 至少存在一個(gè)子目標(biāo),使比好。因此，滿足這種最優(yōu)性的“最優(yōu)解”往往不是單個(gè)解，而是一組滿足上式最優(yōu)性條件的非劣解集合，包含非劣解的集合稱作非劣解集（Pareto Solutions Set）或非受控解集(nondominated solutions set)；非劣解對應(yīng)的目標(biāo)值在目標(biāo)空間中稱為非劣點(diǎn)；最優(yōu)解集在優(yōu)化目標(biāo)空間構(gòu)成的分布稱作非劣解前沿。在進(jìn)化的每一代中參數(shù)呈現(xiàn)有規(guī)律的變化，但在該代操作過程中保持不變，常見的進(jìn)化加權(quán)法，個(gè)體的評估使用確定的加權(quán)組合，所有個(gè)體都有一個(gè)適應(yīng)度值，保證了搜索方向朝最優(yōu)解邁進(jìn)。單目標(biāo)優(yōu)化中的目標(biāo)函數(shù)常與適應(yīng)度函數(shù)相同，但MOP問題中的適應(yīng)度賦值和選擇必須考慮幾個(gè)子目標(biāo)，MOEAs必須根據(jù)個(gè)體間的Pareto優(yōu)勝關(guān)系和其他信息為個(gè)體確定適應(yīng)度值，這種適應(yīng)度值和每個(gè)目標(biāo)函數(shù)的具體大小沒有直接關(guān)系。(3)具有相同序號的個(gè)體進(jìn)行適應(yīng)度共享算子操作，即通過除以相同序號的個(gè)體數(shù)目得到新的適應(yīng)度值，另外，也可以給不同序號的個(gè)體分配固定不變的適應(yīng)度值。為使算法優(yōu)化得到一組盡可能分布均勻的非劣解集而非此集合中的非劣解極值點(diǎn)，大多數(shù)MOEAs在當(dāng)代群體中維持多樣性是在選擇過程中結(jié)合了密度信息，即個(gè)體在其鄰域范圍內(nèi)所占的密度越高被選擇復(fù)制的機(jī)會越小。多目標(biāo)進(jìn)化算法與單目標(biāo)進(jìn)化算法類似，為了提高群體多樣性，在算法過程中盡量采用小生境（Niche）共享技術(shù)，使得在一個(gè)群體內(nèi)可以形成在多目標(biāo)問題上分布均勻的非劣最優(yōu)解集。通常采用優(yōu)勝準(zhǔn)則來確定最優(yōu)個(gè)體。 (2) 產(chǎn)生初始種群：隨機(jī)地產(chǎn)生一個(gè)由個(gè)個(gè)體組成的種群，該種群代表一些可能解的集合。在此操作中，適應(yīng)于生存環(huán)境的優(yōu)良個(gè)體將有更多的機(jī)會繁殖后代，這使得優(yōu)良特性能夠遺傳到下一代。對一個(gè)需要進(jìn)行優(yōu)化計(jì)算的實(shí)際應(yīng)用問題，一般可以按照上述步驟來構(gòu)造求解該問題的遺傳算法。下面分別對二者加以介紹。以空間評價(jià)方法為例，該方法又被稱為Delta指標(biāo)(Schott, 1995) [22]，用來計(jì)算解的分布信息的，如式(32)所示。但是，由于這種方法可以簡單直觀的反映出算法的一些特性，所以在分析算法性能領(lǐng)域的應(yīng)用十分廣泛。 其次, 根據(jù)Goldberg和Deb等[23]提出的共享方法, 按式(23) 和式( 24) 計(jì)算出每一個(gè)Pareto 最優(yōu)解的小生境數(shù), 將該個(gè)體原適應(yīng)度除以小生境數(shù),就得到它的共享適應(yīng)度。首先，找到種群中所有的個(gè)體，將它們存入當(dāng)前集合，然后對于當(dāng)前集合的每個(gè)個(gè)體，考察它所支配的個(gè)體集,將集合中的每個(gè)個(gè)體的減去1，即支配個(gè)體的解個(gè)體數(shù)減1，如果則將個(gè)體存入另一個(gè)集。擁擠度比較算子：為了維持種群的多樣性，需要一個(gè)比較擁擠度的算子以確保算法能夠收斂到一個(gè)均勻分布的Pareto面上。然后進(jìn)行非支配排序，產(chǎn)生一系列非支配集并計(jì)算擁擠度，通常選擇前個(gè)個(gè)體組成，滿足且。這種算法應(yīng)用在適應(yīng)度評價(jià)功能上應(yīng)用一種計(jì)算權(quán)值和的方式，即當(dāng)一對父代種群被選擇通過交叉變異去獲得新解時(shí)使用這個(gè)功能。 （2） (26)如果我們使用連續(xù)的權(quán)值，通過GA局部搜索的方向是已經(jīng)固定的。按照慣例的局部搜索，只有等在檢驗(yàn)所有相鄰解后沒找到比當(dāng)前解更好的解時(shí)，搜索才結(jié)束。在試驗(yàn)集合中，一小部分解被任意地選擇作為局部搜索的最初解，這是因?yàn)槿绻粋€(gè)非劣解沒有父代解，隨機(jī)權(quán)值分配給那個(gè)非劣解去執(zhí)行局部搜索，隨機(jī)選擇的非劣解可能被認(rèn)為是精英解，因?yàn)樗鼈儽惶砣霙]有進(jìn)過遺傳操作的當(dāng)前種群。當(dāng)前種群被局部搜索改進(jìn)的解置換。為了對新提出的多目標(biāo)進(jìn)化算法性能進(jìn)行評價(jià)，或?qū)Χ喾N不同的多目標(biāo)進(jìn)化算法進(jìn)行性能比較，研究者們常常需要借助不同性狀的標(biāo)準(zhǔn)測試函數(shù)對算法性能進(jìn)行考察。設(shè)隨機(jī)選中進(jìn)行變異的個(gè)體為，則非均勻變異算子采用如下公式生成新個(gè)體：其中、分別為變量的下界和上界，可由下式計(jì)算得出：其中、為之間均勻分布的隨機(jī)數(shù)，為當(dāng)前遞進(jìn)層的進(jìn)化代數(shù)，為每層遞進(jìn)設(shè)定的最大進(jìn)化代數(shù)，為一形式參數(shù)，此處取2。采用MOGLS和NSGAⅡ算法和優(yōu)化函數(shù)測試算例KUR時(shí)，為保證算法結(jié)果比較的公正性，將兩種算法的進(jìn)化參數(shù)設(shè)置為相同的進(jìn)化條件（進(jìn)化群體規(guī)模、進(jìn)化代數(shù)以及交叉和變異概率，等）。采用這兩種算法對典型的多目標(biāo)函數(shù)優(yōu)化KUR算例進(jìn)行了優(yōu)化求解，將兩種算法的所得結(jié)果進(jìn)行比較分析，研究結(jié)果表明，NSGAII有比 MOGLS更優(yōu)的非劣解等級及非劣解集分布，因此驗(yàn)證了這兩種算法對多目標(biāo)函數(shù)優(yōu)化問題的求解性能的強(qiáng)弱關(guān)系。所以基于以上兩個(gè)原因，人工方式就顯得效率極其低下，不能使研究人員專注于算法自身的改進(jìn)上。最后簡單介紹了算法的性能評價(jià)體系，為幾種算法比較的方案提供依據(jù)，得出基于實(shí)驗(yàn)的方法是科學(xué)可行的。Sons,1988.[27]Zitzler E..Evolutionary Algorithms for Multiobjective Optimization:Methods and Applications[D].PhD Thesis,Switzerland:Swiss Federal Institute of Technology,2001.[28] Zitzler E. Multiobjective Evolutionary Algorithms:A Comparative Case Study and the Strength Pareto Approach.[J][29] 程鵬. 多目標(biāo)進(jìn)化算法測試問題的設(shè)計(jì)[J]. 清華大學(xué)學(xué)報(bào)（自然科學(xué)版）, 2008, 48(S2): 17561761.[30][D]. 北京: 北京航空航天大學(xué), 2005.附錄采用NSGAII和MOGLS優(yōu)化KUR結(jié)果MaxGens = 500 PopSize = 100Pc = 。 Pm = C(N,M)C(M,N)C(N,M)C(M,N)C(N,M)C(M,N)C(N,M)C(M,N)123456789101112131415161718192021222324