多目標(biāo)演化算法研究綜述

多目標(biāo)演化算法研究綜述

1多目標(biāo)優(yōu)化方法人類對自然的改造和設(shè)計過程中通常反映了最大效率和最小成本的基本優(yōu)化原則。最大化效益、最小化成本實質(zhì)上是一個多目標(biāo)的優(yōu)化問題(MOP)。效益可能包括多種效益,如經(jīng)濟(jì)效益、政治效益與社會效益等;成本或損失也可能包括生產(chǎn)成本與非生產(chǎn)成本,或與此相關(guān)聯(lián)的其他目標(biāo)如環(huán)境污染等方面損失。航天器總體設(shè)計中的有效載荷、射程、推力等指標(biāo)參數(shù)的綜合是一個典型的多目標(biāo)的優(yōu)化問題?？刂乒こ讨锌刂葡到y(tǒng)的穩(wěn)、準(zhǔn)、快等時域指標(biāo)與穩(wěn)定域度、系統(tǒng)帶寬等頻域特性的綜合問題也是一個多目標(biāo)工程優(yōu)化設(shè)計問題。此外還有社會發(fā)展與國民經(jīng)濟(jì)的中長遠(yuǎn)發(fā)展計劃的優(yōu)化與決策問題等。一般說來,科學(xué)與工程實踐中的許多優(yōu)化問題大都是多目標(biāo)的優(yōu)化與決策問題。傳統(tǒng)的多目標(biāo)優(yōu)化方法往往將其轉(zhuǎn)化為各目標(biāo)之加權(quán)和,然后采用單目標(biāo)的優(yōu)化技術(shù)。但是,這樣做存在幾大缺點:a.不同性質(zhì)的目標(biāo)之間單位不一致,不易作比較;b.各目標(biāo)加權(quán)值的分配帶有較大的主觀性;c.優(yōu)化目標(biāo)僅為各目標(biāo)的加權(quán)和,優(yōu)化過程中各目標(biāo)的優(yōu)度進(jìn)展不可操作;d.各目標(biāo)之間通過決策變量相互制約,往往存在相互矛盾的目標(biāo),致使加權(quán)目標(biāo)函數(shù)的拓?fù)浣Y(jié)構(gòu)十分復(fù)雜?；趥鹘y(tǒng)數(shù)學(xué)規(guī)劃原理的多目標(biāo)優(yōu)化方法在實際工程優(yōu)化問題中往往表現(xiàn)出一定的脆弱性,因此,有必要研究高效實用的多目標(biāo)優(yōu)化與決策的算法及理論。多目標(biāo)優(yōu)化/決策問題不存在唯一的全局最優(yōu)解,而是存在多個最優(yōu)解的集合。多目標(biāo)問題最優(yōu)解集中的元素就全體目標(biāo)而言是不可比較的,一般稱為Pareto最優(yōu)解集。所謂Pareto最優(yōu)解集,是對于一些解不可能進(jìn)一步優(yōu)化某一個或幾個目標(biāo)而其他目標(biāo)不至于劣化,因此也稱為非劣最優(yōu)解集。Pareto最優(yōu)概念是建立在集合論基礎(chǔ)上對多目標(biāo)解的一種向量評估方式。而傳統(tǒng)的數(shù)學(xué)規(guī)劃法與模擬退火算法是以單點搜索為特征的串行算法,不可能利用Pareto最優(yōu)概念對解進(jìn)行評估。因此,Pareto最優(yōu)概念雖然提出來已百年有余,但卻仍無傳統(tǒng)算法意義上的相關(guān)算法?；诜N群操作的演化算法可以隱并行地搜索解空間的多個解,并能利用不同解之間的相似性來提高其并發(fā)求解問題效率,如果與Pareto最優(yōu)概念相結(jié)合,有可能產(chǎn)生真正基于Pareto最優(yōu)概念的多目標(biāo)優(yōu)化的演化算法,實現(xiàn)對非劣最優(yōu)解集的搜索。雖然Rosenberg曾提到可用基于遺傳的搜索算法來求解多目標(biāo)的優(yōu)化問題,但直到1985年才出現(xiàn)基于向量評估的遺傳算法(VEGA),這是第一個多目標(biāo)演化算法(MOEA),但仍然不是基于Pareto最優(yōu)概念的演化算法。1990年后,相繼提出了不同的多目標(biāo)演化算法。1993年和1994年,多目標(biāo)遺傳算法(MOGA)、非劣性分層遺傳算法(NSGA)、小組決勝遺傳算法(NPGA)已成為基于Pareto最優(yōu)概念的多目標(biāo)演化算法研究工作的奠基石。此外,還存在一些不基于Pareto最優(yōu)概念的多目標(biāo)演化算法,如多性別遺傳算法、目標(biāo)向量方法以及最大最小方法等。多目標(biāo)演化算法已用于燃?xì)鉁u輪泵控制器設(shè)計、航空器結(jié)構(gòu)設(shè)計以及汽車發(fā)動機(jī)優(yōu)化設(shè)計等等,因此,多目標(biāo)演化算法研究直接受到實際工程問題的推動。盡管如此,多目標(biāo)優(yōu)化與決策問題的演化計算技術(shù)中待研究的問題還很多,如適應(yīng)值賦值方法、選種配對機(jī)制、多目標(biāo)演化種群動力學(xué)行為及其穩(wěn)定性分析、非劣最優(yōu)解域收斂性分析、種群更新終止條件以及實際多目標(biāo)優(yōu)化問題的演化求解等,都是目前的研究熱點。實際的多目標(biāo)問題不僅是一個優(yōu)化問題,而且最后往往歸結(jié)為一個決策問題。運(yùn)籌學(xué)研究領(lǐng)域曾采用數(shù)學(xué)規(guī)劃的多目標(biāo)優(yōu)化技術(shù)對與設(shè)計領(lǐng)域緊密相關(guān)的多目標(biāo)決策問題(MODM)作過一些研究,這些設(shè)計問題的共同特征由三方面組成:一組定量的目標(biāo)函數(shù),一組完整定義的設(shè)計約束,以及一個可在諸目標(biāo)之間作權(quán)衡的操作過程。2最優(yōu)解的性質(zhì)最小化與最大化問題可以相互轉(zhuǎn)化,因此,僅以無約束最小化多目標(biāo)問題為研究對象。一個多目標(biāo)問題可以表示如下,其中決策向量x∈Rm,目標(biāo)向量y∈Rn:miny=f(x)=(f1(x),f2(x),?,fn(x))。定義1優(yōu)劣性(dominance/inferiority)如果目標(biāo)向量解u=(u1,u2,…,un)部分小于目標(biāo)向量解v=(v1,v2,…,vn),也就是?i∈{1,2,…,n},ui≤vi∧?j∈{1,2,…,n},uj<vj,則稱u優(yōu)于v,記為up<v。反之,如果目標(biāo)向量解u=(u1,u2,…,un)部分大于目標(biāo)向量解v=(v1,v2,…,vn),也就是?i∈{1,2,…,n},ui≥vj∧?j∈{1,2,…,n},uj>vj,則稱u劣于v,記為up>v。定義2非劣最優(yōu)解(Paretooptimal)只有不存在決策變量xv∈Rn,使得相應(yīng)的目標(biāo)向量解v=f(xv∈Rn)=(v1,v2,…,vn)優(yōu)于目標(biāo)向量解u=f(xu∈Rn)=(u1,u2,…,un),即vp<u,則稱決策變量xu∈Rn為多目標(biāo)問題的非劣最優(yōu)解。由所有非劣最優(yōu)解組成的集合稱為多目標(biāo)優(yōu)化問題的最優(yōu)解集,也稱為可接受解集或有效解集,記為Ptrue;相應(yīng)非劣最優(yōu)解的目標(biāo)向量稱為非支配的目標(biāo)向量(non-dominated),由所有非支配的目標(biāo)向量構(gòu)成多目標(biāo)問題的非劣最優(yōu)目標(biāo)域(Paretofront),記為PFtrue。Ptrue與PFtrue由具體的多目標(biāo)優(yōu)化問題中各目標(biāo)函數(shù)所決定,是一個確定的不變集合。由優(yōu)化算法所發(fā)現(xiàn)的非劣最優(yōu)解組成的集合記為Pknown與PFknown,使用演化算法求解多目標(biāo)優(yōu)化問題時,隱含下列假設(shè)之一在某些賦范空間(如歐氏空間,RMS賦范空間等)中成立:Pknown=Ptrue,Pknown?Ptrue或PFknown∈[PFtrue,PFtrue+ε]。3多目標(biāo)優(yōu)化和決策問題的解決方案的分類3.1優(yōu)化演化過程的主要任務(wù)組成多目標(biāo)演化算法的任務(wù)分解如圖1所示,由以下功能任務(wù)單元組成:1為種群初始化過程;2為適應(yīng)值評估過程;2a為向量目標(biāo)→標(biāo)量適應(yīng)值轉(zhuǎn)換過程;3為雜交操作;4為變異操作;5為選擇過程。可見其主要任務(wù)組成與單目標(biāo)優(yōu)化演化算法相同,其中2a部分是單目標(biāo)演化算法所沒有的。2a任務(wù)是把多目標(biāo)問題解的向量表示轉(zhuǎn)化為標(biāo)量化的適應(yīng)值,決策者對各目標(biāo)的偏重程度、權(quán)衡優(yōu)先次序與對各目標(biāo)的期望值,通過2a部分轉(zhuǎn)化為決策過程中的效用值,對多目標(biāo)演化算法的研究主要集中在2a部分,不同的轉(zhuǎn)換機(jī)制決定了不同的多目標(biāo)演化算法。3.2多目標(biāo)優(yōu)化系統(tǒng)整體架構(gòu)與單目標(biāo)優(yōu)化問題的本質(zhì)區(qū)別在于多目標(biāo)問題的解是一個非劣最優(yōu)解的集合,實際的多目標(biāo)問題往往希望按某些可以定量或定性的領(lǐng)域約束、目標(biāo)偏好或難以表述的專家經(jīng)驗,從這一非劣最優(yōu)解集中選擇唯一現(xiàn)實可行的最優(yōu)方案。圖2表示多目標(biāo)優(yōu)化與決策系統(tǒng)的基本構(gòu)成方式,非劣最優(yōu)解的搜索過程由優(yōu)化器實現(xiàn),解的選擇過程由決策器完成。優(yōu)化器可由演化算法等多目標(biāo)優(yōu)化算法實現(xiàn),而決策器則由決策專家或具有領(lǐng)域決策知識的專家系統(tǒng)承擔(dān)。決策器可以從優(yōu)化器對非劣最優(yōu)域的搜索過程中不斷獲得與精煉決策信息,而不斷變化與豐富的決策信息可以逐步引導(dǎo)優(yōu)化器搜索最感興趣的非劣最優(yōu)域。決策信息決定了非劣最優(yōu)域的性質(zhì)以及對最終解的選擇結(jié)果,一般以決策者對目標(biāo)的偏好關(guān)系與程度、目標(biāo)期望值、權(quán)衡優(yōu)先次序、效用函數(shù)、模糊邏輯等表示,因此,多目標(biāo)優(yōu)化問題最終表現(xiàn)為一個與問題相關(guān)的本質(zhì)主觀的決策過程。有關(guān)偏好信息處理參見文獻(xiàn)。3.3基于多目標(biāo)優(yōu)化的決策技術(shù)多目標(biāo)演化算法是在多目標(biāo)數(shù)學(xué)規(guī)劃技術(shù)的基礎(chǔ)上發(fā)展起來的。根據(jù)決策者對各目標(biāo)主觀偏重程度與非劣最優(yōu)解搜索過程之間的相互影響關(guān)系,多目標(biāo)優(yōu)化技術(shù)可分為三大類:先驗優(yōu)先權(quán)技術(shù),優(yōu)先權(quán)演化技術(shù)與后驗優(yōu)先權(quán)技術(shù)。3.3.1產(chǎn)單目標(biāo)優(yōu)化問題的框架過程,其重點在于標(biāo)量化的總效用函數(shù)決策器事先(主觀)設(shè)置各目標(biāo)的優(yōu)先權(quán)值,將全體目標(biāo)按權(quán)值合成一個標(biāo)量效用函數(shù),把多目標(biāo)優(yōu)化問題轉(zhuǎn)化成單目標(biāo)優(yōu)化問題。優(yōu)點是多目標(biāo)問題的決策過程隱含在標(biāo)量化的總效用函數(shù)中,對總效用函數(shù)的優(yōu)化過程也是相應(yīng)多目標(biāo)問題的決策過程;缺點是很難獲得各目標(biāo)精確的先驗優(yōu)先權(quán)值,而且相應(yīng)多目標(biāo)問題的Pareto最優(yōu)解搜索空間受到限制。先驗優(yōu)先權(quán)技術(shù)可分為排序聚合方法與標(biāo)量化聚合方法兩類。1開始下一多級目標(biāo)按目標(biāo)的先驗優(yōu)先順序,解的優(yōu)劣比較從最高優(yōu)先級的目標(biāo)開始,如上一級目標(biāo)出現(xiàn)平局,則開始下一優(yōu)先級目標(biāo)的比較直至平局結(jié)束;算法采用排序選擇法。特點是簡單易執(zhí)行,所得多目標(biāo)問題的解皆為Pareto最優(yōu)解,但當(dāng)目標(biāo)數(shù)過多時,因?qū)δ繕?biāo)空間搜索的不平衡特性,算法易收斂于非劣最優(yōu)域的局部區(qū)域。2非線性聚合方法將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題的方法,可分為線性聚合方法與非線性聚合方法。非線性聚合方法又可分為乘性聚合方法、目標(biāo)向量方法與最大最小方法。線性聚合方法即常規(guī)的加權(quán)法,根據(jù)各目標(biāo)的重要性賦以相應(yīng)權(quán)值,采用標(biāo)準(zhǔn)化的權(quán)向量對各目標(biāo)進(jìn)行線性加權(quán),原多目標(biāo)問題化為單目標(biāo)優(yōu)化問題。Fonseca與Fleming指出,由任何正的加權(quán)向量形成的加權(quán)目標(biāo)函數(shù)的全局最優(yōu)解一定是非劣最優(yōu)解。線性聚合方法的特點是簡單易執(zhí)行,但在非凸搜索空間中找不到適當(dāng)?shù)腜areto最優(yōu)解。非線性聚合方法將多目標(biāo)以非線性形式轉(zhuǎn)化為單目標(biāo),如乘性聚合方法以各目標(biāo)之乘積形式轉(zhuǎn)化為單目標(biāo)優(yōu)化問題。目標(biāo)向量方法則將多目標(biāo)轉(zhuǎn)化為某種范式下距預(yù)定目標(biāo)向量之間的距離優(yōu)化問題。最大最小方法則將多目標(biāo)問題轉(zhuǎn)化為最小化距預(yù)定目標(biāo)值中之最大者。3.3.2非劣最優(yōu)解集的生成優(yōu)先權(quán)決策(決策器)與非劣最優(yōu)解的搜索過程(優(yōu)化器)交替進(jìn)行(參見圖2),變化的優(yōu)先權(quán)可產(chǎn)生變化的非劣最優(yōu)解集,決策器從優(yōu)化器的搜索過程中提取有利于精煉優(yōu)先權(quán)設(shè)置的信息,而優(yōu)先權(quán)的設(shè)置則有利于優(yōu)化器搜索到更感興趣的非劣最優(yōu)域。優(yōu)先權(quán)演化技術(shù)中一般可采用后驗優(yōu)先權(quán)技術(shù)中的多目標(biāo)演化算法?？梢哉J(rèn)為優(yōu)先權(quán)演化技術(shù)是先驗優(yōu)先權(quán)技術(shù)與后驗優(yōu)先權(quán)技術(shù)的一種有機(jī)結(jié)合。3.3.3共混合式多目標(biāo)優(yōu)化方法框架優(yōu)化器進(jìn)行非劣最優(yōu)解的搜索,決策器從搜索到的非劣最優(yōu)解集中進(jìn)行選擇,選擇過程就是一個優(yōu)先權(quán)的決策過程。包括獨立采樣法與合作搜索法,而合作搜索法又分為目標(biāo)選擇法、聚合選擇法與Pareto選擇法,其中Pareto選擇法又可分為Pareto排序法、Pareto排序與小生境法、同類群法及Pareto最優(yōu)保持法。獨立采樣法以各目標(biāo)的多種聚合形式對解空間進(jìn)行獨立搜索,算法每次運(yùn)行即是以不同加權(quán)向量形成聚合目標(biāo)函數(shù)獨立采樣問題的非劣最優(yōu)域。在合作搜索法中,各目標(biāo)相互合作,協(xié)同參與對非劣最優(yōu)解域的搜索,其中目標(biāo)選擇法中各目標(biāo)輪流參與下代種群個體的選擇,如Shaffer的VEGA算法;聚合選擇法則用各目標(biāo)的線性或非線性聚合值來選擇下代種群。Pareto選擇法采用Pareto最優(yōu)概念對解進(jìn)行選擇,如Pareto排序法基于Pareto最優(yōu)概念對解進(jìn)行優(yōu)劣比較與排序;排序與小生境法則以Pareto最優(yōu)概念對解進(jìn)行排序并賦適應(yīng)值,然后通過共享函數(shù)將Pareto最優(yōu)解均勻分布于非劣最優(yōu)域,如MOGA算法、NSGA算法與NPGA算法等;同類群法在島嶼模型中基于解的Pareto排序及在種群中的幾何位置對解進(jìn)行選擇;最優(yōu)保持法則以解的精華狀態(tài)作為選擇準(zhǔn)則,將Pareto排序居先的最優(yōu)解直接保留至下代種群,剩余部分則以另外方式產(chǎn)生。此外,如果按適應(yīng)值賦值方法分類,多目標(biāo)優(yōu)化技術(shù)可分為基于Pareto最優(yōu)概念與不基于Pareto最優(yōu)概念的兩大類技術(shù)。基于Pareto概念的優(yōu)化技術(shù)采用Pareto最優(yōu)概念對多目標(biāo)解進(jìn)行比較與排序,并基于Pareto排序進(jìn)行適應(yīng)值賦值,如MOGA算法、NSGA算法以及NPGA算法。不基于Pareto最優(yōu)概念的多目標(biāo)優(yōu)化技術(shù)包括直接與間接的目標(biāo)加權(quán)和方法。間接的目標(biāo)加權(quán)和方法如VEGA方法、BenTal的有序比較法與隨機(jī)比較法、概率向量選擇法以及加權(quán)向量與目標(biāo)解向量混合編碼方法等,雖然能提高種群的多樣度,但本質(zhì)上都與傳統(tǒng)直接加權(quán)法一樣。如果按種群更新選擇方案,間接加權(quán)和方法又可分為按目標(biāo)適應(yīng)值的比例選擇方法(Shaffer,Hajela&Lin)、錦標(biāo)賽選擇法(BenTal,Kursawe)與排序選擇法(Goldberg)等。錦標(biāo)賽法與排序法克服了目標(biāo)值尺度(量綱)的影響,但與各目標(biāo)的優(yōu)先順序有關(guān)。4近似解的解的計算多目標(biāo)與單目標(biāo)優(yōu)化問題的本質(zhì)區(qū)別是,前者一般是一組或多組連續(xù)解的集合,而后者只是單個解或一組不連續(xù)的解。得到一個解集合的近似解集比得到單個解的近似解難得多。本節(jié)代表性地介紹文獻(xiàn)中五種比較常見的多目標(biāo)演化算法:多性別遺傳算法,VEGA算法,MOGA算法,NSGA算法,以及NPGA算法,其中前2種是不基于Pareto最優(yōu)概念的間接加權(quán)算法,后3種則是基于Pareto最優(yōu)概念的多目標(biāo)演化算法。4.1性別吸引機(jī)制Allenson在做直線管道路徑規(guī)劃時提出了一種有性別的二目標(biāo)優(yōu)化演化算法。兩目標(biāo)分別定義為雄性和雌性。個體產(chǎn)生時性別隨機(jī)決定,只允許異性個體之間雜交。個體適應(yīng)值由其相應(yīng)性別的目標(biāo)函數(shù)值決定。初始種群中雌雄個體數(shù)相等,但隨著種群的更迭,種群個體性別可能失衡,每代中的最差個體由隨機(jī)選取同性別的個體取代。Allenson還采用演化策略來實現(xiàn)生物個體之間的性別吸引機(jī)制,以減少雜交算子的隨機(jī)性。Lis與Eiben把Allenson的方法擴(kuò)展至三個以上的多目標(biāo)優(yōu)化問題,并稱為多性別遺傳算法,其中每一個目標(biāo)都有相應(yīng)的性別。多性別遺傳算法的雜交算子有別于傳統(tǒng)演化算法中的兩兩雜交算子,允許多個不同性別個體之間隨機(jī)交配,由參與雜交的不同性別個體各取相應(yīng)性別的部分基因生成雜交后代。雜交后代的性別由貢獻(xiàn)基因數(shù)最多的親本個體的性別決定,當(dāng)有兩個以上個體貢獻(xiàn)最大基因數(shù)量相同時,后代個體性別在這些親本性別中采用抽簽法決定。變異算子不允許改變個體的性別。個體適應(yīng)值由相應(yīng)性別所標(biāo)示的目標(biāo)函數(shù)值決定。非劣最優(yōu)解隨種群更迭過程逐步更新,即去掉過時的非劣解,加進(jìn)新的非劣解,直至找到多目標(biāo)問題的Pareto最優(yōu)解。多性別遺傳算法對不同的目標(biāo)定義了相應(yīng)的子種群,但這種子種群定義不同于VEGA算法。多性別遺傳算法中的雜交算子只允許受限的隨機(jī)雜交,只有性別不同的個體之間才能雜交。因為生成一個雜交后代個體需要所有不同性別的個體參與雜交,因此,隨著目標(biāo)個數(shù)的增加,在計算代價上這種受限隨機(jī)雜交算子的效率將降低。4.2與vega算法的比較Shaffer與Grefenstette利用演化算法對不同尺度的多目標(biāo)優(yōu)化問題分別處理,可在一次演化計算過程中并發(fā)地搜索多個非劣最優(yōu)解。VEGA算法的基本思想是:分別利用每一目標(biāo)從種群中選擇部分個體,組成相應(yīng)的下代子種群,然后混合各子種群,從中均勻隨機(jī)地選擇配對個體進(jìn)行雜交與變異,生成新一代種群,如此往復(fù)進(jìn)行。子種群的歸并混合是一個對各目標(biāo)的相應(yīng)標(biāo)準(zhǔn)化適應(yīng)值實行平均的過程,每一親本所生子代個體的期望數(shù)是該親本根據(jù)各目標(biāo)所生子代個體期望數(shù)之和。因為VEGA算法采用適應(yīng)值比例分配方案,因此,向量解個體的總體適應(yīng)值相當(dāng)于各目標(biāo)的加權(quán)和,只是加權(quán)指數(shù)隨每代種群的分布而變化。這一結(jié)論已被Richardson等提出并得到了Shaffer本人的證實。與非劣最優(yōu)解定義不相稱的是不同的非劣最優(yōu)解在VEGA算法中將賦以不同的適應(yīng)值。VEGA算法易于在種群中形成相對于各目標(biāo)的子種群,Shaffer稱為物種形成。雖然VEGA本質(zhì)上如同傳統(tǒng)加權(quán)法一樣不適合求解折中目標(biāo)具有凹面的多目標(biāo)問題,但VEGA算法中隱含的加權(quán)方案有待進(jìn)一步研究。VEGA算法中對每一目標(biāo)的加權(quán)值與該目標(biāo)的子種群大小成正比,而與種群中該目標(biāo)的平均適應(yīng)值成反比。假定各目標(biāo)子種群大小固定,VEGA算法的子種群選擇方案將對各目標(biāo)的優(yōu)化進(jìn)展進(jìn)行自適應(yīng)權(quán)衡,即如果某一目標(biāo)優(yōu)化的進(jìn)展較快,該目標(biāo)的平均適應(yīng)值增大,相應(yīng)地該目標(biāo)的加權(quán)值減小。VEGA算法對各目標(biāo)的自動平衡原理與平衡多解問題中所用的共享函數(shù)法有類似之處。與普通固定加權(quán)和算法相比,VEGA算法對不同物種能夠維持比較多的種群代數(shù),因而提高了種群的多樣度。Fourman提出了與VEGA類似的算法。Fourman算法中物種的選擇采用錦標(biāo)賽方案,即基于某一固定或隨機(jī)選擇的目標(biāo)來比較一對向量解之間的優(yōu)劣,如果前一次比較產(chǎn)生平局,則按預(yù)定目標(biāo)優(yōu)先順序或隨機(jī)地選擇下一個目標(biāo)作為比較基準(zhǔn)。這種基于錦標(biāo)賽的選擇方案本質(zhì)上也是一種加權(quán)和方法,各目標(biāo)的權(quán)重與該目標(biāo)被選為錦標(biāo)賽準(zhǔn)則的概率成比例。Fourman算法中采用逐對比較法對向量解進(jìn)行排序,錦標(biāo)賽個體排序是對整個種群全排序的一種隨機(jī)逼近,克服了VEGA算法對目標(biāo)尺度的依賴性。Kursawe提出一種基于預(yù)定目標(biāo)選擇概率向量的多目標(biāo)演化策略,選種過程包括k步(k為目標(biāo)個數(shù)),每一步根據(jù)預(yù)定目標(biāo)選擇概率隨機(jī)選擇一個目標(biāo),以此目標(biāo)從當(dāng)前種群中選出一部分予以刪除,經(jīng)過k步有選擇的刪除以后,當(dāng)前種群中剩下的個體即為下一代親本。雖然Kursawe方法與VEGA算法和Fourman方法(隨機(jī)目標(biāo)選擇)有許多相似之處,但由于目標(biāo)選擇的隨機(jī)性,每代中不同的目標(biāo)選擇方案會產(chǎn)生不同的適應(yīng)值圖景,因此Kursawe方法會產(chǎn)生不穩(wěn)定的動態(tài)演化環(huán)境,降低了算法的收斂性。最后,Hajela與Lin提出了加權(quán)指數(shù)與向量解混合編碼的改進(jìn)型加權(quán)和方法,并采用共享函數(shù)提高種群多樣度,使得具有不同加權(quán)指數(shù)的向量解可以在一個種群中并發(fā)地得到優(yōu)化。4.3限制條件與適應(yīng)值賦值Fonseca與Fleming提出的多目標(biāo)遺傳算法(MOGA)是基于Pareto最優(yōu)概念的演化算法,包括:按目標(biāo)的優(yōu)先順序與期望目標(biāo)值進(jìn)行向量解的優(yōu)劣比較,基于排序的適應(yīng)值賦值策略,共享函數(shù)與小生境技術(shù),雜交約束技術(shù)。MOGA算法中先給出了基于期望目標(biāo)值及其優(yōu)先順序的優(yōu)先性定義,向量目標(biāo)等價性定義以及優(yōu)先性與優(yōu)劣性之間關(guān)系。如果完全缺乏各目標(biāo)之間的優(yōu)先關(guān)系信息,算法將不可能在各目標(biāo)之間做折中處理。通過以期望目標(biāo)向量形式給出目標(biāo)之間部分優(yōu)先關(guān)系信息,MOGA算法基于Pareto最優(yōu)概念對給定折中區(qū)域進(jìn)行搜索。假定各目標(biāo)的優(yōu)先順序與期望目標(biāo)值已給定,兩目標(biāo)向量的優(yōu)劣性比較從優(yōu)先級最高的子目標(biāo)向量開始,每一級子目標(biāo)向量的優(yōu)劣性比較是從目標(biāo)未滿足的子目標(biāo)元素部分開始。除最后一級子目標(biāo)向量中的各目標(biāo)分量要全部參與比較外,其余子目標(biāo)向量僅須對目標(biāo)未滿足的子目標(biāo)元素進(jìn)行比較,而期望目標(biāo)已滿足的目標(biāo)則不影響向量之間的優(yōu)劣性。如果給定一個不可實現(xiàn)的期望目標(biāo)向量,則所有目標(biāo)元素都必須參與比較,此時,向量比較退化至原始的Pareto排序。算法運(yùn)行過程中不斷改變期望目標(biāo)值可相應(yīng)改變適應(yīng)值圖景,決策者即可將種群引導(dǎo)并集中至某一特定折中區(qū)域。種群中每一個向量解的排序是由當(dāng)前種群中(基于Pareto最優(yōu)概念)優(yōu)于該解的其他解的個數(shù)來決定,因此,種群個體排序是不連續(xù)的,而當(dāng)前種群中所有非劣最優(yōu)解都置為同一排序1(或0)。向量解的排序除以種群規(guī)模得到該向量的標(biāo)準(zhǔn)化序數(shù),如果種群規(guī)模足夠大,該標(biāo)準(zhǔn)化序數(shù)反映了解空間中優(yōu)于相應(yīng)向量解的空間比例。適應(yīng)值賦值策略是根據(jù)排序先后按線性或非線性插值方法給不同的排序個體賦以不同的適應(yīng)值,具有同一排序號的向量解共享適應(yīng)值。為了實現(xiàn)種群個體對多目標(biāo)問題非劣最優(yōu)域的均勻采樣,算法采用共享函數(shù)與小生境技術(shù)來提高種群多樣度。通過非劣最優(yōu)域PFtrue的大小與種群規(guī)模來確定共享半徑或小生境的大小σshare,目標(biāo)向量之間距離小于σshare的解向量集合(即小生境)將共享適應(yīng)值。此外,由于多目標(biāo)問題非劣最優(yōu)域的復(fù)雜性,距離較遠(yuǎn)的向量解之間的雜交后代,其適應(yīng)值往往低于親本。而且,隨機(jī)雜交過程一般導(dǎo)致種群多樣度降低。因此,算法采用雜交約束方式,即只有目標(biāo)空間距離小于雜交半徑σmate的親本才允許雜交。如果在雜交半徑內(nèi)找不到雜交對象,則隨機(jī)任取種群中其他親本進(jìn)行雜交。σmate的確定方法如同σshare。MOGA算法的選擇過程借用Baker的隨機(jī)均勻采樣算法(SUS)。MOGA算法的主要優(yōu)點是算法的執(zhí)行相對容易且效率高,缺點是算法易受小生境大小的影響,但Fonseca與Fleming已經(jīng)從理論上解決了小生境大小σshare的計算問題。4.4nsga算法非劣性分層遺傳算法(NSGA),基于非劣最優(yōu)性定義對多目標(biāo)解種群進(jìn)行逐層分類,每代選種配對之前先按個體的非劣性進(jìn)行排序。首先,找出當(dāng)代種群中的非劣最優(yōu)解并分配最高序號(如零級),賦給該層非劣最優(yōu)解集與當(dāng)前種群規(guī)模成比例的總體適應(yīng)值。為了保持解的多樣性,所有該層非劣最優(yōu)解基于決策向量空間距離共享此總體適應(yīng)值。此后,該層非劣最優(yōu)解集將不予考慮。然后,開始下一層非劣最優(yōu)解集搜索,在該層得到的非劣最優(yōu)解集稱為第二層,分配排列序號(如一級),并賦給與該層種群規(guī)模(除去以上各層被分解出來的非劣最優(yōu)解)成比例的總體適應(yīng)值,同樣,必須在各層非劣最優(yōu)解集中實行適應(yīng)值共享。如此重復(fù)直到當(dāng)前種群中最后一個被分解完。雜交配對個體采用適應(yīng)值比例選擇。因為最高層非劣最優(yōu)解集具有最大的總體適應(yīng)值,因此,該算法易于使整個種群收斂并均勻分布到多目標(biāo)問題的非劣最優(yōu)域。算法性能取決于如何利用非劣最優(yōu)性定義進(jìn)行逐層排序,并把多目標(biāo)問題轉(zhuǎn)化為各層總體適應(yīng)值的函數(shù)賦值方式。NSGA算法的種群排序不同于MOGA算法,前者排序序號是連續(xù)的,后者可以是斷續(xù)的;NSGA算法的適應(yīng)值賦值方式不同于MOGA算法,前者與非劣最優(yōu)解的比較范圍有關(guān),后者僅與序號有關(guān);NSGA算法的適應(yīng)值共享方式也不同于MOGA算法,前者是基于決策向量空間距離共享適應(yīng)值,后者是基于目標(biāo)向量空間距離共享適應(yīng)值。NSGA算法的優(yōu)點是優(yōu)化目標(biāo)個數(shù)任選,非劣最優(yōu)解分布均勻,允許存在多個不同的等價解;缺點是算法效率(包括計算復(fù)雜度與最終解Pknown的優(yōu)度)較低,且對共享參數(shù)σshare的依賴性較大。4.5多目標(biāo)演化小組決勝遺傳算法(NPGA)采用基于非劣最優(yōu)性定義的錦標(biāo)賽選擇機(jī)制。與直接比較兩個個體不同的是,算法還從種群中隨機(jī)選取一定數(shù)量(一般為10個)的其他個體組成參賽組tdom,參與非劣最優(yōu)解的競選。如果參與競賽的兩個個體中的一個劣于參賽組tdom中的所有個體,而另一個體至少優(yōu)于參賽組tdom中的一個個體,則后一個體在競賽中得勝。如果兩個竟賽的個體都優(yōu)于或劣于參賽組tdom中的所有個體,即認(rèn)為此次競賽成為平局,而其輸贏由彼此的共享值來決定。在每一個體的目標(biāo)空間鄰域σshare內(nèi),共享個體數(shù)較少的競賽個體取勝,即獲得繁殖后代的機(jī)會。因為該算法的非劣最優(yōu)解選擇是基于種群的部分而非全體,因此其優(yōu)點是能很快找到一些好的非劣最優(yōu)解域,并能維持一個較長的種群更新期,缺點是除了設(shè)置共享參數(shù)外還需要選擇一個適當(dāng)?shù)腻\標(biāo)賽規(guī)模,限制了該算法的實際應(yīng)用效果。對多目標(biāo)演化算法的系統(tǒng)比較研究還不足以說明上述算法的優(yōu)劣。Zitzler與Thiele等對上述三種算法(NSGA,NPGA,VEGA)與Hajela和Lin的加權(quán)向量算法以及純隨機(jī)搜索算法,作了系統(tǒng)的定量實驗比較,采用多背包問題擴(kuò)展形式的九種不同規(guī)模設(shè)置作為數(shù)值型多目標(biāo)測試問題,通過全面的比較分析,NSGA算法的性能最優(yōu),其次是VEGA算法。但NPGA算法與Hajela和Lin的加權(quán)向量算法的全部實驗結(jié)果仍不分上下。由于測試問題的單一性,這種比較結(jié)果不能無限制地外推。NFL理論認(rèn)為,不可能存在一種對所有問題的求解效率都高于其他算法的超級算法,因此,任何算法的優(yōu)點總是針對特有的問題。在多目標(biāo)問題求解的三大類技術(shù)中,先驗優(yōu)先權(quán)技術(shù)雖然最簡單,但先驗優(yōu)先權(quán)知識很難獲取,而缺乏優(yōu)先權(quán)知識的多目標(biāo)搜索無異于瞎子摸象,其求解能力最弱;即使各目標(biāo)的優(yōu)先權(quán)值能精確定義,此類算法也具有其固有的弱點,即其非劣最優(yōu)解搜索空間受限。然而,先驗優(yōu)先權(quán)技術(shù)所表現(xiàn)出來的明顯弱點并不意味著優(yōu)先權(quán)演化技術(shù)與后驗優(yōu)先權(quán)技術(shù)就是我們的最佳選擇。從已發(fā)表的相關(guān)文獻(xiàn)而言,以算法理論的完備性作為選擇多目標(biāo)演化算法的基本準(zhǔn)則是明智的。因此,本節(jié)3種基于Pareto最優(yōu)概念的演化算法是值得推廣的。5多目標(biāo)發(fā)展算法的研究5.1pftrae、pftrae的調(diào)值無論問題規(guī)模(維數(shù))的大小,任何非劣最優(yōu)解域PFtrue都應(yīng)有理論上的極限。例如,PFtrue一定是單調(diào)的,并且PFtrue應(yīng)該具有漸近邊界。最近,David與Gary證明了以下定理:具有二個目標(biāo)的多目標(biāo)優(yōu)化/決策問題(k=2)的非劣最優(yōu)解域PFtrue至多只是一根曲線,而具有三個目標(biāo)以上的多目標(biāo)優(yōu)化問題(k≥3)的非劣最優(yōu)解域PFtrue至多只是一個曲面,而不是如Horn所說的一定是一個(k-1)維曲面。5.2測試問題的描述為了提高算法研究與比較的效率,必須設(shè)計一些能反映實際多目標(biāo)優(yōu)化問題基本特征的標(biāo)準(zhǔn)測試函數(shù)集,它包含多目標(biāo)問題領(lǐng)域的基本知識。Whitley等曾提出多目標(biāo)優(yōu)化/決策問題的測試函數(shù)設(shè)計準(zhǔn)則:a.測試問題必須是簡單搜索策略所不易解決的;b.測試函數(shù)中應(yīng)包括非線性耦合以及非對稱問題;c.測試問題中應(yīng)包括問題規(guī)?？缮炜s的問題;d.一些測試問題的評估代價應(yīng)具有可伸縮性;e.測試問題應(yīng)有規(guī)范的表達(dá)形式。演化計算曾經(jīng)使用過不同的測試函數(shù),如五個單目標(biāo)優(yōu)化函數(shù)(F1～F5),五個單目標(biāo)約束優(yōu)化測試函數(shù)(G1～G5),Whitley與Goldberg也設(shè)計了一些有關(guān)的測試函數(shù)以及GA欺騙問題。此外,組合優(yōu)化中的測試問題有旅行商(TSP)問題與背包(Knapsack)問題等。這些函數(shù)為研究演化計算提供了有應(yīng)用背景價值且問題規(guī)?？缮炜s的基準(zhǔn)測試問題。文獻(xiàn)列出了比較詳盡的多目標(biāo)優(yōu)化問題測試函數(shù)表,并最終歸納成三類數(shù)值測試問題,即MOP1,MOP2,MOP3。Rudolph給出了MOP1非劣最優(yōu)解集的完整表示。MOP2多目標(biāo)數(shù)值優(yōu)化問題不會因增加決策變量的個數(shù)而改變其PFtrue結(jié)構(gòu),而且其非劣最優(yōu)解集Ptrue具有完整的表示形式。MOP3是三目標(biāo)數(shù)值優(yōu)化問題,其PFtrue是目標(biāo)空間中相當(dāng)復(fù)雜的三維曲線。此測試問題具有非線性與不對稱特性,可用來測試多目標(biāo)優(yōu)化算法發(fā)現(xiàn)并保持整個PFtrue的能力。此外,多目標(biāo)演化算法的測試函數(shù)集中還必須包括等式或/和不等式的約束條件。5.3moea的絕對評估方法對各種多目標(biāo)演化算法的性能比較研究必須建立在某種度量標(biāo)準(zhǔn)上。已有的性能比較方法有絕對評估方法、統(tǒng)計分布方法與非劣最優(yōu)區(qū)域占有率方法等。對于任何一個多目標(biāo)優(yōu)化問題,都不易得到類似MOP1完整的非劣最優(yōu)解的集合表達(dá)形式,因此,很難對MOEA的有效性作絕對評估。對于比較簡單的多目標(biāo)數(shù)值優(yōu)化問題,可以在一定精度內(nèi)對決策變量進(jìn)行離散化處理,轉(zhuǎn)化為一個有窮離散空間的多目標(biāo)優(yōu)化問題,通過窮盡枚舉法計算所有可能的決策變量組合,得到問題的近似Ptrue和PFtrue,作為對MOEA進(jìn)行絕對評估的依據(jù)。統(tǒng)計分布方法以已知的PFknown在PFtrue中統(tǒng)計分布的均勻性來評估算法對Pareto最優(yōu)解的搜索能力,區(qū)域占有率方法采用PFknown在PFtrue中所占的區(qū)域比例來反映算法的搜索廣度,或以一種算法與另一種算法所得到的PFknown之間的交集來反映其相對性能。5.4+1-ea的演化策略對一般多目標(biāo)優(yōu)化問題收斂行為的理論分析有助于改進(jìn)現(xiàn)有算法的收斂性。Rudolph對由兩個目標(biāo)組成的簡單多目標(biāo)優(yōu)化問題的演化算法的收斂行為進(jìn)行了分析,以集合之間的距離定義解的收斂性,說明具有比例步長均勻變異算子的(1+1)-EA(演化策略)能以概率1收斂到問題的非劣最優(yōu)域。但是,Rudolph的分析過程比較復(fù)雜,而且中間過程不太清晰,似有疑問,且這種收斂性向一般多目標(biāo)問題的推廣上具有局限性。理論上,多目標(biāo)優(yōu)化問題的演化算法缺乏與單目標(biāo)優(yōu)化問題演化算法相類似的收斂性理論,因此,目前還未出現(xiàn)描述多目標(biāo)問題演化算法中代與代之間的動態(tài)行為的理論分析結(jié)果。5.5多目標(biāo)并行效率多目標(biāo)優(yōu)化演化算法中的并行實現(xiàn)方式也是值得研究的問題。向量目標(biāo)評估與相應(yīng)解的適應(yīng)值賦值是算法并行性開發(fā)中可以首先考慮的兩個任務(wù)。因為各目標(biāo)函數(shù)可以彼此獨立地并行計算,因此,開發(fā)各目標(biāo)計算的