【正文】 用MOGLS和NSGAⅡ算法和優(yōu)化函數(shù)測(cè)試算例KUR時(shí)，為保證算法結(jié)果比較的公正性，將兩種算法的進(jìn)化參數(shù)設(shè)置為相同的進(jìn)化條件（進(jìn)化群體規(guī)模、進(jìn)化代數(shù)以及交叉和變異概率，等）。符號(hào)集約定為：設(shè)有種算法（本文有兩種）參與性能評(píng)價(jià)，對(duì)于某個(gè)優(yōu)化算例，采用每種算法獨(dú)立運(yùn)行次（本文為30次），每次獨(dú)立運(yùn)行后，獲得非劣解集， ，合并各算法獨(dú)立運(yùn)行所得的非劣解集，剔除其中劣解后得到算法優(yōu)化的最終非劣解集，則Zitzler評(píng)價(jià)方法的實(shí)現(xiàn)過(guò)程可描述為：(1)令， ；。 首先，計(jì)算兩種算法優(yōu)化算例得到的C指標(biāo)（見(jiàn)附錄A），從附錄A中可以反映出，C（NSGAII,MOGLS）接近于1，C（MOGLS ，NSGAII）接近于零，即NSGAII算法優(yōu)于MOGLS算法。因?yàn)楝F(xiàn)代啟發(fā)式算法存在不確定性，因此在每組參數(shù)組合下計(jì)算30次做統(tǒng)計(jì)分析。設(shè)隨機(jī)選中進(jìn)行變異的個(gè)體為，則非均勻變異算子采用如下公式生成新個(gè)體：其中、分別為變量的下界和上界，可由下式計(jì)算得出：其中、為之間均勻分布的隨機(jī)數(shù)，為當(dāng)前遞進(jìn)層的進(jìn)化代數(shù)，為每層遞進(jìn)設(shè)定的最大進(jìn)化代數(shù)，為一形式參數(shù)，此處取2。分別選用線性交叉和非均勻變異方式生成新個(gè)體。本文性能測(cè)試函數(shù)使用KUR和ZDT4來(lái)分別測(cè)試MOGLS和NSGAⅡ。針對(duì)這些測(cè)試原則中的一種或幾種原則的組合，借鑒單目標(biāo)遺傳算法測(cè)試函數(shù)的設(shè)計(jì)方法，Deb、Fonseca、Fleming、Veldhuizen和Zitzler等人通過(guò)長(zhǎng)期研究，分別提出了多個(gè)具有不同優(yōu)化性狀的測(cè)試函數(shù)。為了對(duì)新提出的多目標(biāo)進(jìn)化算法性能進(jìn)行評(píng)價(jià)，或?qū)Χ喾N不同的多目標(biāo)進(jìn)化算法進(jìn)行性能比較，研究者們常常需要借助不同性狀的標(biāo)準(zhǔn)測(cè)試函數(shù)對(duì)算法性能進(jìn)行考察。指標(biāo)由Zitzler提出，其定義為：設(shè)是兩種算法優(yōu)化所得的非劣解集，指標(biāo)是一種值域定義在上、用來(lái)刻畫之間偏序能性的指標(biāo)：。具體流程見(jiàn)下圖：現(xiàn)有研究中，對(duì)新的多目標(biāo)遺傳算法進(jìn)行性能評(píng)價(jià)時(shí)，普遍采用兩種方法：一種是構(gòu)造一系列可以獨(dú)立評(píng)價(jià)算法性能的指標(biāo)用于考察算法搜索到的非劣解集的優(yōu)劣；另一種是選取一種迄今為止性能優(yōu)越的驗(yàn)證算法與新算法在相同進(jìn)化條件下對(duì)測(cè)試算例進(jìn)行優(yōu)化，比較搜索到的非劣解集。如果多目標(biāo)優(yōu)化問(wèn)題有凹的Praeto前端，使用帶有連續(xù)權(quán)值的計(jì)算權(quán)值之和的方法將不能得到整個(gè)Praeto前端。當(dāng)前種群被局部搜索改進(jìn)的解置換。（5）精英保留策略：從試驗(yàn)非劣解集中隨機(jī)選擇解，接著將這個(gè)選中的解加入到在(4)中解中，它的功能是為了創(chuàng)建解的一個(gè)種群。通過(guò)（28）確定的選擇概率，從當(dāng)前種群中選擇一組父代解。（2）評(píng)價(jià)適應(yīng)值：對(duì)當(dāng)前種群中每個(gè)解在個(gè)目標(biāo)方向計(jì)算適應(yīng)度值，更新臨時(shí)非劣解集。在試驗(yàn)集合中，一小部分解被任意地選擇作為局部搜索的最初解，這是因?yàn)槿绻粋€(gè)非劣解沒(méi)有父代解，隨機(jī)權(quán)值分配給那個(gè)非劣解去執(zhí)行局部搜索，隨機(jī)選擇的非劣解可能被認(rèn)為是精英解，因?yàn)樗鼈儽惶砣霙](méi)有進(jìn)過(guò)遺傳操作的當(dāng)前種群。精英保留策略：本算法保留了兩組解：當(dāng)前解和試驗(yàn)的非劣解。解選擇概率已經(jīng)通過(guò)使用線性縮放的輪盤賭方法得到： (28) 是當(dāng)前群體最壞解的適應(yīng)度?？傊覀兡芡ㄟ^(guò)局部搜索調(diào)整計(jì)算時(shí)間。按照慣例的局部搜索，只有等在檢驗(yàn)所有相鄰解后沒(méi)找到比當(dāng)前解更好的解時(shí)，搜索才結(jié)束。這種方法下，每個(gè)解都有自己的搜索方向。無(wú)論何時(shí)選擇一組父代種群我們都這樣定義權(quán)值。為了實(shí)現(xiàn)各個(gè)方向搜索，而提出這種算法。 （2） (26)如果我們使用連續(xù)的權(quán)值，通過(guò)GA局部搜索的方向是已經(jīng)固定的。雜交算法的目的不是確定一個(gè)單一的最終解，而是試圖尋找這個(gè)多目標(biāo)問(wèn)題所有符合約束條件的最優(yōu)解。另一個(gè)特點(diǎn)是在局部搜索的過(guò)程中不需要計(jì)算當(dāng)前種群的所有鄰域解，只有少部分鄰域解被檢驗(yàn)避免在這個(gè)算法中消耗過(guò)多的所有可行解的計(jì)算時(shí)間。這個(gè)算法的一大典型特性是無(wú)論何時(shí)選擇一組父代種群都要指定權(quán)值效率。這種算法應(yīng)用在適應(yīng)度評(píng)價(jià)功能上應(yīng)用一種計(jì)算權(quán)值和的方式，即當(dāng)一對(duì)父代種群被選擇通過(guò)交叉變異去獲得新解時(shí)使用這個(gè)功能。非支配解的多樣性由擁擠度比較算子保證，不需要額外的共享參數(shù)。然后通過(guò)遺傳算子產(chǎn)生新的子代種群。如果的大小小于，則繼續(xù)向中填充，直到添加到時(shí)種群大小超出，對(duì)中的個(gè)體進(jìn)行擁擠度排序，取前個(gè)個(gè)體。然后進(jìn)行非支配排序，產(chǎn)生一系列非支配集并計(jì)算擁擠度，通常選擇前個(gè)個(gè)體組成，滿足且。然后采用選擇、交叉、變異算子產(chǎn)生下一代種群，大小也為，完成第一代進(jìn)化。將父代種群與其產(chǎn)生的子代種群組合，共同競(jìng)爭(zhēng)產(chǎn)生下一代種群，有利于保持父代中的優(yōu)良個(gè)體進(jìn)入下一代，并通過(guò)對(duì)種群中所有個(gè)體的分層存放，使得最佳個(gè)體不會(huì)丟失，迅速提高種群水平。即如果兩個(gè)個(gè)體的非支配排序不同，取排序號(hào)較小的個(gè)體；如果兩個(gè)個(gè)體在同一級(jí)，取周圍較不擁擠的個(gè)體。擁擠度比較算子：為了維持種群的多樣性，需要一個(gè)比較擁擠度的算子以確保算法能夠收斂到一個(gè)均勻分布的Pareto面上。為了計(jì)算每個(gè)個(gè)體的聚集距離，需要對(duì)群體按每個(gè)子目標(biāo)函數(shù)值進(jìn)行排序，在本算法中，若群體規(guī)模為，最極端情況下，對(duì)個(gè)子目標(biāo)分別進(jìn)行排序的時(shí)間復(fù)雜度為。(2)提出了擁擠度和擁擠度比較算子，代替了需要指定共享半徑的適應(yīng)度共享策略，并在快速排序后的同級(jí)比較中作為勝出標(biāo)準(zhǔn)，使準(zhǔn)Pareto域中的個(gè)體能擴(kuò)展到整個(gè)域，并均勻分布，保持了種群的多樣性。如此操作降低了算法的計(jì)算復(fù)雜度。首先，找到種群中所有的個(gè)體，將它們存入當(dāng)前集合，然后對(duì)于當(dāng)前集合的每個(gè)個(gè)體，考察它所支配的個(gè)體集,將集合中的每個(gè)個(gè)體的減去1，即支配個(gè)體的解個(gè)體數(shù)減1，如果則將個(gè)體存入另一個(gè)集。首先將當(dāng)前的所有的非劣解個(gè)體劃為同一等級(jí)，令其等級(jí)為；然后將這些個(gè)體從種群中移出，在剩余個(gè)體中尋找出新的非劣解，再令其等級(jí)為；重復(fù)上述過(guò)程，直至種群中所有個(gè)體都被設(shè)定相應(yīng)的等級(jí)。雖然非支配排序遺傳算法（NSGA）在許多問(wèn)題上得到了應(yīng)用，但仍存在一些問(wèn)題，如計(jì)算復(fù)雜度較高，需要指定共享半徑，易丟失已經(jīng)得到的滿意解。 (23)其中, 表示個(gè)體 與個(gè)體 的距離, 是同一小生境中個(gè)體間的最大允許距離, 表示距離為時(shí)的共享函數(shù)值。 其次, 根據(jù)Goldberg和Deb等[23]提出的共享方法, 按式(23) 和式( 24) 計(jì)算出每一個(gè)Pareto 最優(yōu)解的小生境數(shù), 將該個(gè)體原適應(yīng)度除以小生境數(shù),就得到它的共享適應(yīng)度。第三章 優(yōu)化算例及分析 NSGAⅡ和MOGLS算法（NSGAⅡ）在NSGA 中, 同一個(gè)小生境內(nèi)的個(gè)體適應(yīng)度共享, 從而降低該小生境內(nèi)個(gè)體的競(jìng)爭(zhēng)力, 防止種群在收斂過(guò)程中陷入局部最優(yōu), 實(shí)現(xiàn)種群多樣性。第三部分給出了多目標(biāo)進(jìn)化算法的一般流程，這是所有算法的原型，不同算法都是在此基礎(chǔ)上做出改動(dòng)，了解此框架是學(xué)習(xí)其他算法的基礎(chǔ)。 本章首先介紹了多目標(biāo)進(jìn)化算法的基本概念和原理。但是，由于這種方法可以簡(jiǎn)單直觀的反映出算法的一些特性，所以在分析算法性能領(lǐng)域的應(yīng)用十分廣泛。2. 實(shí)驗(yàn)比較分析實(shí)驗(yàn)比較分析是指通過(guò)對(duì)優(yōu)化算例的結(jié)果和結(jié)果的各種指標(biāo)進(jìn)行比較，驗(yàn)證新算法與已存在的算法之間的性能差別。但是由于多目標(biāo)進(jìn)化算法是一門新興的學(xué)科，多目標(biāo)進(jìn)化計(jì)算的理論基礎(chǔ)尚未成熟，算法收斂性的理論證明對(duì)有限時(shí)間內(nèi)的收斂性分析較少，而時(shí)間無(wú)窮大的收斂性并沒(méi)有工程實(shí)際的應(yīng)用價(jià)值。由于收斂性評(píng)價(jià)與分布性評(píng)價(jià)的應(yīng)用方向不同，因而在比較算法的時(shí)候，多會(huì)綜合兩種評(píng)價(jià)后，對(duì)算法的性能得出適當(dāng)?shù)慕Y(jié)論。以空間評(píng)價(jià)方法為例，該方法又被稱為Delta指標(biāo)(Schott, 1995) [22]，用來(lái)計(jì)算解的分布信息的，如式(32)所示。2. 解集分布性評(píng)價(jià)在更多的算法應(yīng)用領(lǐng)域中，解集的空間分布特性是十分重要的，決策一般希望能夠在目標(biāo)空間中找到一組均勻的解集，以便做出不同的決策，如果解過(guò)于集中，則周圍的很多解事實(shí)上并沒(méi)有太大的意義，也不利于產(chǎn)生新個(gè)體，從而影響了種群的進(jìn)化效果。如式(31)所示。收斂性的評(píng)價(jià)方法有很多種，如錯(cuò)誤率、解集間覆蓋率、世代距離、最大出錯(cuò)率等等。下面分別對(duì)二者加以介紹。所以現(xiàn)階段的性能評(píng)價(jià)方法主要集中于對(duì)算法的效果的衡量。算法的效率是指算法自身的時(shí)間復(fù)雜度和空間復(fù)雜度，也即算法運(yùn)算時(shí)間的長(zhǎng)短和資源消耗的多少；算法的效果是指算法求得的解集的質(zhì)量，也即算法的收斂效果和解集的分布性效果；算法的魯棒性是指算法的應(yīng)用范圍和穩(wěn)定性，也即是否對(duì)多種問(wèn)題都有很好的求解能力、是否求解問(wèn)題時(shí)總是相對(duì)穩(wěn)定的。多目標(biāo)遺傳算法的性能評(píng)價(jià)與傳統(tǒng)優(yōu)化算法及單目標(biāo)遺傳算法的性能評(píng)價(jià)有所不同，傳統(tǒng)算法的優(yōu)化性能可以通過(guò)梯度下降速度進(jìn)行評(píng)價(jià)，并且可以通過(guò)嚴(yán)格的數(shù)學(xué)證明分析其收斂性能；單目標(biāo)遺傳算法可以采用基于模式定理或基于馬爾可夫隨機(jī)過(guò)程理論的證明分析其收斂性，盡管這類證明研究還很初步。對(duì)一個(gè)需要進(jìn)行優(yōu)化計(jì)算的實(shí)際應(yīng)用問(wèn)題，一般可以按照上述步驟來(lái)構(gòu)造求解該問(wèn)題的遺傳算法。遺傳算法的選擇和交叉算子賦予了它強(qiáng)有力的搜索能力，變異算子則使算法能搜索到問(wèn)題解空間的每一個(gè)點(diǎn)，以確保算法能達(dá)到全局最優(yōu)。對(duì)產(chǎn)生的新一代群體重新進(jìn)行評(píng)價(jià)、選擇、雜交和變異。(7) 變異操作:以一定的概率從群體中選擇若干個(gè)個(gè)體。在此操作中，適應(yīng)于生存環(huán)境的優(yōu)良個(gè)體將有更多的機(jī)會(huì)繁殖后代，這使得優(yōu)良特性能夠遺傳到下一代。通常情況下，這兩種方法同時(shí)作為優(yōu)化準(zhǔn)則使用?？梢栽O(shè)定進(jìn)化的最大代數(shù)，當(dāng)進(jìn)化到最大代數(shù)時(shí)，算法終止運(yùn)行。 (3) 設(shè)計(jì)適應(yīng)度函數(shù)：把問(wèn)題的目標(biāo)函數(shù)轉(zhuǎn)換成合適的適應(yīng)度函數(shù)，并根據(jù)適應(yīng)度函數(shù)計(jì)算種群中的每個(gè)個(gè)體的適應(yīng)度，為種群進(jìn)化的選擇提供依據(jù)。 (2) 產(chǎn)生初始種群：隨機(jī)地產(chǎn)生一個(gè)由個(gè)個(gè)體組成的種群，該種群代表一些可能解的集合。Holland教授提出的遺傳算法，現(xiàn)在一般稱為簡(jiǎn)單遺傳算法或基本遺傳算法[18]，其基本流程如下圖：圖21遺傳算法基本流程 (1)參數(shù)編碼：遺傳算法一般不直接處理問(wèn)題空間的參數(shù)，因此在算法開(kāi)始進(jìn)行之前，首先要選擇合適的編碼方式對(duì)待優(yōu)化的參數(shù)進(jìn)行編碼。MOEAs的最優(yōu)個(gè)體大多利用優(yōu)勝關(guān)系和密度兩者的組合來(lái)進(jìn)行挑選，最優(yōu)個(gè)體保存在每代的伴隨群體中。但是使用優(yōu)勝關(guān)系比較的方法有時(shí)也存在問(wèn)題，如對(duì)某些連續(xù)型問(wèn)題所對(duì)應(yīng)的Pareto集可能包含無(wú)窮多個(gè)解，因此需要補(bǔ)充其他的信息知識(shí)來(lái)減小所存儲(chǔ)的個(gè)體數(shù)目。通常采用優(yōu)勝準(zhǔn)則來(lái)確定最優(yōu)個(gè)體。另一種實(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]。遺傳算法是基于隨機(jī)進(jìn)化選擇的算法，因此，為改善遺傳算法的收斂性能，現(xiàn)有多目標(biāo)遺傳算法大都引入了精英保留策略。當(dāng)兩個(gè)解的目標(biāo)向量之間的空間距離小于某一預(yù)定值時(shí)，相應(yīng)解的小生境規(guī)模就必須進(jìn)行調(diào)整。多目標(biāo)進(jìn)化算法與單目標(biāo)進(jìn)化算法類似，為了提高群體多樣性，在算法過(guò)程中盡量采用小生境（Niche）共享技術(shù)，使得在一個(gè)群體內(nèi)可以形成在多目標(biāo)問(wèn)題上分布均勻的非劣最優(yōu)解集。(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ù)目越大，被保留概率越小。(2)基于鄰域解數(shù)目的評(píng)價(jià)策略：基于鄰域解數(shù)目的評(píng)價(jià)策略是以評(píng)價(jià)解為核心、包含一定數(shù)量鄰域解的鄰域半徑為指標(biāo)，優(yōu)先保留鄰域半徑較大的個(gè)體即較稀疏的解個(gè)體。具體應(yīng)用時(shí)首先根據(jù)內(nèi)核函數(shù)來(lái)定義一個(gè)點(diǎn)的鄰域范圍，內(nèi)核函數(shù)采用至另一點(diǎn)的距離作為參數(shù)。為使算法優(yōu)化得到一組盡可能分布均勻的非劣解集而非此集合中的非劣解極值點(diǎn)，大多數(shù)MOEAs在當(dāng)代群體中維持多樣性是在選擇過(guò)程中結(jié)合了密度信息，即個(gè)體在其鄰域范圍內(nèi)所占的密度越高被選擇復(fù)制的機(jī)會(huì)越小。進(jìn)化算法由于其進(jìn)化算子固有的隨機(jī)誤差，因而基于有限群體實(shí)施進(jìn)化時(shí)會(huì)出現(xiàn)收斂至某一個(gè)解。如果單純從群體多樣性出發(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)重影響交叉操作。傳統(tǒng)的進(jìn)化算法在Pareto最優(yōu)集上執(zhí)行多目標(biāo)搜尋，希望找出盡可能均勻分布的解集，因而個(gè)體的多樣性減少的很快，經(jīng)常收斂至單個(gè)解而丟失多個(gè)其他非劣解。(3)具有相同序號(hào)的個(gè)體進(jìn)行適應(yīng)度共享算子操作，即通過(guò)除以相同序號(hào)的個(gè)體數(shù)目得到新的適應(yīng)度值，另外，也可以給不同序號(hào)的個(gè)體分配固定不變的適應(yīng)度值。假設(shè)第代種群中的個(gè)體，在第代種群個(gè)體排序中的位置為，基于個(gè)體排序的適應(yīng)度賦值步驟描述如下：(1)基于的數(shù)值將種群中所有個(gè)體進(jìn)行級(jí)別排序?；赑areto優(yōu)勝關(guān)系的選擇方法已經(jīng)被廣大研究者采納，現(xiàn)已有多種基于Pareto的適應(yīng)度賦值方案，其中基于種群個(gè)體級(jí)別排序的適應(yīng)度賦值方法是較常見(jiàn)的一種方法。Pareto優(yōu)勝關(guān)系是決定個(gè)體適應(yīng)度函數(shù)值的重要依據(jù)，很多MOEAs根據(jù)個(gè)體間的這種關(guān)系，將個(gè)體的適應(yīng)度函數(shù)值分成兩個(gè)層次，即劣解和非劣解，后者的適應(yīng)度值總是優(yōu)于前者。單目標(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)系。這類算法的適應(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ù)目。這種策略存在的問(wèn)題是進(jìn)化結(jié)果容易偏向某些極端邊界解，并且對(duì)Pareto最優(yōu)前