求解約束優(yōu)化問(wèn)題的偏好多目標(biāo)進(jìn)化算法

董 寧,王宇平

(1.西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,陜西西安 710071; 2.西安電子科技大學(xué)計(jì)算機(jī)學(xué)院,陜西西安 710071)

求解約束優(yōu)化問(wèn)題的偏好多目標(biāo)進(jìn)化算法

董 寧1,王宇平2

(1.西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,陜西西安 710071; 2.西安電子科技大學(xué)計(jì)算機(jī)學(xué)院,陜西西安 710071)

將約束優(yōu)化問(wèn)題轉(zhuǎn)化為雙目標(biāo)優(yōu)化問(wèn)題,用進(jìn)化算法求解轉(zhuǎn)化的雙目標(biāo)問(wèn)題.設(shè)計(jì)了新的混合交叉算子以提高算法在進(jìn)化過(guò)程中的搜索能力,加快算法收斂;借鑒多目標(biāo)優(yōu)化加權(quán)度量法中成績(jī)標(biāo)量函數(shù)的特點(diǎn),提出新的偏好適應(yīng)度函數(shù),進(jìn)行個(gè)體比較和選擇.新適應(yīng)度以個(gè)體到參考點(diǎn)的加權(quán)距離衡量個(gè)體優(yōu)劣,參考點(diǎn)和權(quán)向量體現(xiàn)選擇的偏好.在進(jìn)化過(guò)程中,自適應(yīng)地選擇參考點(diǎn)和權(quán)向量平衡進(jìn)化的不同階段對(duì)各個(gè)目標(biāo)的偏好程度,增加種群多樣性,避免算法早熟收斂.

約束優(yōu)化;多目標(biāo)優(yōu)化;進(jìn)化算法;偏好;成績(jī)標(biāo)量函數(shù)

約束優(yōu)化問(wèn)題是科學(xué)和工程應(yīng)用領(lǐng)域經(jīng)常出現(xiàn)的一類數(shù)學(xué)規(guī)劃問(wèn)題,也是優(yōu)化領(lǐng)域一類很難處理的問(wèn)題.進(jìn)化算法是一種基于群體的搜索方法,它能有效地解決復(fù)雜問(wèn)題,因此適合于求解約束優(yōu)化問(wèn)題,近年來(lái)引起許多學(xué)者的關(guān)注,并涌現(xiàn)出大量的約束優(yōu)化進(jìn)化算法[1-6].用進(jìn)化算法求解約束優(yōu)化問(wèn)題,其性能好壞取決于兩個(gè)因素:一是進(jìn)化算法的搜索機(jī)制,二是約束處理技術(shù)[6].由于約束優(yōu)化問(wèn)題是要找到滿足約束條件的最好解,約束滿足是首要問(wèn)題.如何用約束條件和目標(biāo)函數(shù)定義適應(yīng)度函數(shù)是至關(guān)重要的,也是非常困難的,因?yàn)榇藭r(shí)適應(yīng)度函數(shù)不僅要評(píng)價(jià)解的好壞,還要反映解與可行域的距離.約束優(yōu)化進(jìn)化算法發(fā)展初期,一些算法認(rèn)為可行解總是優(yōu)于不可行解[2,7],進(jìn)化搜索過(guò)程中過(guò)分強(qiáng)調(diào)可行解的作用,忽略甚至拋棄不可行解攜帶的有用信息,而對(duì)于最優(yōu)解位于可行域邊界的優(yōu)化問(wèn)題,從約束違反小的不可行解出發(fā)比從遠(yuǎn)離邊界的可行解出發(fā)更容易找到全局最優(yōu)解.忽略或者拋棄這些不可行解,算法性能將大受影響.利用罰函數(shù)思想,將約束優(yōu)化問(wèn)題轉(zhuǎn)換為多目標(biāo)優(yōu)化問(wèn)題是近年來(lái)處理約束的一種有效方法[8-9].在求解轉(zhuǎn)化的多目標(biāo)問(wèn)題時(shí),如果用Pareto支配關(guān)系比較個(gè)體,即認(rèn)為目標(biāo)函數(shù)和約束滿足同等重要,一些遠(yuǎn)離可行域但目標(biāo)函數(shù)值較小的不可行解首先被保留下來(lái),而實(shí)際上,這些解對(duì)某些問(wèn)題(如最優(yōu)解在可行域內(nèi)部)的尋優(yōu)沒(méi)有幫助.因此在進(jìn)化搜索過(guò)程中,個(gè)體的比較和選擇是影響算法效率的重要因素,應(yīng)設(shè)計(jì)恰當(dāng)?shù)倪m應(yīng)度函數(shù)以平衡進(jìn)化過(guò)程對(duì)約束滿足和目標(biāo)函數(shù)最優(yōu)的偏好.

筆者將約束優(yōu)化問(wèn)題轉(zhuǎn)化為雙目標(biāo)優(yōu)化問(wèn)題[8-9],設(shè)計(jì)了新的進(jìn)化算法求解這個(gè)有偏好的雙目標(biāo)優(yōu)化問(wèn)題.在進(jìn)化算法搜索時(shí),設(shè)計(jì)了新的混合交叉算子,保證在進(jìn)化初期群體快速向可行域靠近,在進(jìn)化后期快速收斂到全局最優(yōu)解.在約束處理技術(shù)上,將原問(wèn)題轉(zhuǎn)化為雙目標(biāo)問(wèn)題,借鑒多目標(biāo)優(yōu)化中的加權(quán)度量函數(shù)——成績(jī)標(biāo)量函數(shù)(ASF)的特點(diǎn),將原問(wèn)題的目標(biāo)函數(shù)和約束違反函數(shù)標(biāo)量化為適應(yīng)度函數(shù),該函數(shù)使用參考點(diǎn)和加權(quán)向量平衡進(jìn)化過(guò)程對(duì)不同目標(biāo)的偏好程度.在進(jìn)化過(guò)程中,根據(jù)群體特征,自適應(yīng)地確定參考點(diǎn)和加權(quán)向量,使算法在進(jìn)化初期偏好約束滿足,在進(jìn)化后期偏好原問(wèn)題的目標(biāo)函數(shù),保證進(jìn)化過(guò)程中群體的多樣性和個(gè)體的最優(yōu)性,使算法快速找到全局最優(yōu)解.

1 約束優(yōu)化問(wèn)題及相關(guān)概念

1.1 約束優(yōu)化問(wèn)題

不失一般性,考慮如下的約束優(yōu)化問(wèn)題:

其中,x=(x1,x2,…,xn)∈S?Rn,是決策向量.一般地,搜索空間S={x∈Rn|li≤xi≤ui,i=1,2,…,n},其中,ui∈R,li∈R,分別表示xi的上下界;f(x)是目標(biāo)函數(shù);gi(x)≤0,是不等式約束;hj(x)=0,是等式約束;Ω={x|x∈S,gi(x)≤0,hj(x)=0,i=1,…,q,j=q+1,…,m},稱為問(wèn)題(1)的可行域,可行域中的點(diǎn)稱為可行解.

1.2 問(wèn)題的轉(zhuǎn)化及相關(guān)概念

傳統(tǒng)的罰函數(shù)法是求解約束優(yōu)化問(wèn)題時(shí)常用的約束處理方法,但罰參數(shù)的選取比較困難,且罰參數(shù)的取值直接影響算法的性能.此外,在基于罰函數(shù)的處理方法[7]中,當(dāng)進(jìn)行個(gè)體比較時(shí),可行解總是優(yōu)于不可行解;對(duì)全局最優(yōu)解位于可行域邊界附近的優(yōu)化問(wèn)題,從位于最優(yōu)解附近的不可行解出發(fā)比從遠(yuǎn)離最優(yōu)解的可行解出發(fā)更容易找到最優(yōu)解.如果忽略這些不可行解,算法的效率將受到影響.利用罰函數(shù)思想將約束優(yōu)化問(wèn)題轉(zhuǎn)化為有兩個(gè)目標(biāo)的多目標(biāo)優(yōu)化問(wèn)題是近年來(lái)處理約束的有效方法[8-9],具體轉(zhuǎn)化方法為:

其中,δ為等式約束條件的容忍值,一般取較小的正數(shù).顯然,Gi(x)≥0.若Gi(x)=0,則x滿足第i個(gè)約束條件;若Gi(x)＞0,則Gi(x)表示x違反第i個(gè)約束條件的程度.定義約束違反函數(shù),它表示個(gè)體x違反所有約束條件的程度,同時(shí)也反映了個(gè)體x離可行域的距離.

將問(wèn)題(1)的目標(biāo)函數(shù)f(x)作為一個(gè)目標(biāo),將約束違反函數(shù)G(x)作為另一個(gè)目標(biāo),則問(wèn)題(1)可轉(zhuǎn)化為有兩個(gè)目標(biāo)的多目標(biāo)優(yōu)化問(wèn)題:

其中,x∈S?Rn,是決策向量;S稱為決策空間,x∈S的像空間稱為目標(biāo)空間.為簡(jiǎn)單起見,將問(wèn)題(3)的兩個(gè)目標(biāo)記為f1(x)=f(x),f2(x)=G(x).下面給出雙目標(biāo)優(yōu)化問(wèn)題的基本概念.

定義1(Pareto支配) 設(shè)向量u=(u1,u2),u Pareto支配(Pareto非劣于)向量v,v=(v1,v2),記為u?v,當(dāng)且僅當(dāng)u1≤v1且u2＜v2,或u1＜v1且u2≤v2.

定義2(Pareto最優(yōu)解) 向量xu∈S,稱為雙目標(biāo)問(wèn)題(3)的Pareto最優(yōu)解(Pareto非劣解),當(dāng)且僅當(dāng)xv∈S,使得v?u,其中,u=(f1(xu),f2(xu)),v=(f1(xv),f2(xv)).

定義3(Pareto最優(yōu)解集) 對(duì)雙目標(biāo)優(yōu)化問(wèn)題(3),Pareto最優(yōu)解集合記為PS,則

定義4(Pareto前沿) 對(duì)雙目標(biāo)優(yōu)化問(wèn)題(3),Pareto最優(yōu)解集合PS在目標(biāo)空間中的像稱為Pareto前沿,記為PF,則

雖然將約束優(yōu)化問(wèn)題(1)轉(zhuǎn)化成雙目標(biāo)優(yōu)化問(wèn)題(3),但是它們的解有著本質(zhì)區(qū)別,如圖1所示.問(wèn)題(3)致力于找到位于Pareto前沿上均勻分布的代表解集,而問(wèn)題(1)是要找到滿足約束條件(即G(x)=0)且f(x)達(dá)到最小值的解,即Pareto前沿和可行域的交點(diǎn)f(x*).

圖1 雙目標(biāo)優(yōu)化問(wèn)題及約束優(yōu)化問(wèn)題最優(yōu)解的關(guān)系

2 雙目標(biāo)進(jìn)化算法

2.1 基于偏好的新適應(yīng)度函數(shù)

在多目標(biāo)進(jìn)化算法中,個(gè)體間的比較是偏序關(guān)系,即當(dāng)兩個(gè)個(gè)體互相非支配時(shí)不能比較其優(yōu)劣.利用雙目標(biāo)求解約束優(yōu)化問(wèn)題時(shí),目的是找到滿足約束(G(x)=0)且使目標(biāo)函數(shù)f(x)達(dá)到最小的解,約束滿足是首要問(wèn)題,因此問(wèn)題(3)實(shí)際上是有偏好的雙目標(biāo)問(wèn)題.基于這一特點(diǎn),借助多目標(biāo)優(yōu)化技術(shù)的加權(quán)度量法,將兩個(gè)目標(biāo)通過(guò)加權(quán)度量化為一個(gè)標(biāo)量函數(shù)——成績(jī)標(biāo)量函數(shù)(Achievement Scalarizing Function,ASF),該函數(shù)通過(guò)加權(quán)向量和參考點(diǎn)體現(xiàn)對(duì)兩個(gè)目標(biāo)的不同偏好.對(duì)一般的雙目標(biāo)問(wèn)題(極小化問(wèn)題),成績(jī)標(biāo)量函數(shù)為

圖2 多目標(biāo)加權(quán)度量函數(shù)與成績(jī)標(biāo)量函數(shù)示意圖

基于上述成績(jī)標(biāo)量函數(shù)的特點(diǎn),結(jié)合約束優(yōu)化問(wèn)題最優(yōu)解和多目標(biāo)Pareto最優(yōu)解的關(guān)系,將種群進(jìn)化分為3個(gè)階段.在每一階段自適應(yīng)選擇參考點(diǎn)和權(quán)向量ω,以F(x)為適應(yīng)度函數(shù)進(jìn)行個(gè)體的比較和選擇,實(shí)現(xiàn)在不同進(jìn)化階段偏好不同的目標(biāo).

第1階段:群體中只有不可行解,即ρ=0(其中ρ表示群體中可行解的比例).此時(shí)個(gè)體的比較要偏好于約束滿足,即約束違反小的個(gè)體.但是,如果只考慮約束,一些約束違反較小但目標(biāo)函數(shù)值較大的個(gè)體會(huì)優(yōu)先進(jìn)入下一代,這些解對(duì)種群進(jìn)化作用較小,而這種選擇策略會(huì)忽略那些約束違反稍大,但目標(biāo)函數(shù)較小的個(gè)體(即群體中一部分Pareto最優(yōu)解).另外,還有一些算法采用多目標(biāo)的Pareto排序法[11],這種方法認(rèn)為所有目標(biāo)同等重要,種群中所有Pareto最優(yōu)解被賦予小的適應(yīng)值,優(yōu)先進(jìn)入下一代.實(shí)際上,對(duì)于某些問(wèn)題(如最優(yōu)解在可行域內(nèi)部),那些遠(yuǎn)離可行域且目標(biāo)函數(shù)值較小的不可行Pareto解對(duì)尋優(yōu)沒(méi)有幫助.基于上述考慮,在這一階段,在保證約束違反小的同時(shí)也要求目標(biāo)函數(shù)值不太大.此外,由于群體中沒(méi)有可行解,約束違反最小的非支配不可行解(稱其為最好不可行解)是目前種群中的最好解,因此選擇它作為參考點(diǎn).由于此時(shí)群體進(jìn)化方向偏好于約束滿足,故取ω=(0.1,0.9),即離最好不可行解的ω加權(quán)距離式(4)越小,個(gè)體越好;反之越差.如圖3(a)所示.

圖3 進(jìn)化不同階段適應(yīng)度函數(shù)的等高線及個(gè)體選擇情況

第2階段:群體中既有可行解也有不可行解,即0＜ρ＜1.若ρ較小,即可行解較少,要么進(jìn)化處于初期階段,要么可行域較小,找到可行解的難度較大,此時(shí)應(yīng)偏好于可行解;若ρ較大,即可行解較多,則約束違反小的非支配不可行解比一些目標(biāo)函數(shù)值較大的可行解更重要,特別是對(duì)最優(yōu)解處于可行域邊界或其附近的優(yōu)化問(wèn)題.在這一階段,選擇最好的可行解作為參考點(diǎn).當(dāng)ρ較小時(shí),偏好于可行解(G(x)=0)及約束違反G(x)小的解;當(dāng)ρ較大時(shí),偏好于目標(biāo)函數(shù)值f(x)小的個(gè)體.由于要求的是滿足約束條件的最優(yōu)解,約束滿足是首要的,對(duì)目標(biāo)函數(shù)的偏好不能太大,因此對(duì)目標(biāo)函數(shù)的偏好權(quán)值設(shè)定上限為0.5,即,故如圖3(b)和圖3(c)所示.

第3階段:群體中只有可行解,即ρ=1.由于只有可行解,因此按照目標(biāo)函數(shù)值的大小比較優(yōu)劣,即在式(4)中,最好的可行解作為參考點(diǎn),權(quán)向量ω=(ρ,1-ρ)=(1,0).

以F(x)作為個(gè)體的適應(yīng)度,適應(yīng)度越小,個(gè)體越好.由于采用加權(quán)距離式(4)進(jìn)行個(gè)體比較,為了避免目標(biāo)函數(shù)f(x)與約束違反程度G(x)數(shù)量級(jí)不同對(duì)目標(biāo)偏好的影響,先對(duì)目標(biāo)函數(shù)f(x)和約束違反程度G(x)進(jìn)行如下正規(guī)化:

其中,fmax和fmin、Gmax和Gmin分別表示f(x)、G(x)的最大值和最小值.由于已知Gmin=0,其他未知,因此用當(dāng)前群體中f(x)的最大值和最小值、G(x)的最大值分別表示fmax,fmin和Gmax.此處不用當(dāng)前群體中G(x)的最小值作為Gmin,是因?yàn)橛迷撝嫡?guī)化函數(shù)后,約束違反最小的不可行解將變成可行解.

2.2 混合交叉算子

用進(jìn)化算法求解雙目標(biāo)優(yōu)化問(wèn)題式(3)時(shí),進(jìn)化初期群體中只有不可行解,而且這些不可行解的目標(biāo)函數(shù)值通常較大.在這一階段,需要設(shè)計(jì)有效的交叉算子使群體快速向可行域靠近,同時(shí)個(gè)體的目標(biāo)函數(shù)值也得到改善,針對(duì)這一特點(diǎn)提出了非支配聚類交叉算子.隨著種群進(jìn)化,一些個(gè)體進(jìn)入可行域,此時(shí)群體中既有可行解又有不可行解.針對(duì)很多約束優(yōu)化問(wèn)題的最優(yōu)解位于可行域邊界上或邊界附近的特點(diǎn),設(shè)計(jì)了可行解和不可行解之間的二分交叉算子,使群體向可行域邊界聚集,加快收斂速度.

2.2.1 非支配聚類交叉算子

非支配聚類交叉算子用于不可行群體(即種群中只含有不可行個(gè)體).由于種群中只有不可行解,首先找到種群的所有非支配個(gè)體,每個(gè)非支配個(gè)體主導(dǎo)一個(gè)聚類.種群中的其他個(gè)體至少被一個(gè)非支配個(gè)體支配.根據(jù)支配關(guān)系將被支配個(gè)體聚入支配它的非支配個(gè)體主導(dǎo)的聚類,在每一個(gè)聚類內(nèi),讓被支配個(gè)體向非支配個(gè)體靠近,從而使被支配個(gè)體沿不同方向向約束違反函數(shù)減小最快的方向移動(dòng),從而快速找到可行解.設(shè)第k代群體P(k)={x1,x2,…,xN},且G(xi)＞0(i=1,2,…,N).具體算法如下.

算法1 非支配聚類交叉.

(1)Pareto非支配解:找到P(k)的非支配個(gè)體.不妨設(shè)P(k)的前k個(gè)為非支配解,且其約束違反由小到大排列,記非支配解集合(k)={x1,x2,…,xk},令P(k)=P(k)(k),并將其元素表示為P(k)={y1,y2,…,yN-k}.

(3)交叉:每個(gè)聚類內(nèi)只有一個(gè)非支配個(gè)體xi,其他個(gè)體yj都被xi支配,因此交叉分兩種情形.

①對(duì)聚類內(nèi)的支配個(gè)體yj,讓yj沿著方向dj=xi-yj進(jìn)行一維搜索,希望產(chǎn)生比xi和yj都好的后代yj+1=yj+αdj,其中,α＞0,為步長(zhǎng).因?yàn)閤i?yj,沿方向dj,個(gè)體yj的目標(biāo)函數(shù)值f和約束違反函數(shù)G都可能下降.

②對(duì)聚類的主導(dǎo)個(gè)體xi,找約束違反比它小的主導(dǎo)個(gè)體進(jìn)行線性交叉.

該交叉算子保證所有被支配解都向支配它且約束違反最小的非支配解靠近,既能保證約束違反減小,又使目標(biāo)函數(shù)值得到改善,而且聚類方法保證在多個(gè)下降方向中,選擇讓約束違反函數(shù)減小最快的方向,使群體沿不同方向快速向可行域靠近,加快算法的收斂.

2.2.2 二分交叉算子

二分交叉算子用于既有可行解,又有不可行解的種群進(jìn)化.設(shè)種群中要進(jìn)行交叉的個(gè)體為xi.若xi是可行個(gè)體,則在種群中找到和它非支配的不可行個(gè)體xj進(jìn)行配對(duì),此時(shí)f(xj)＜f(xi).若xi為不可行個(gè)體,可分為如下兩種情況:(1)若存在支配xi的可行個(gè)體xj,則將xj與xi配對(duì),此時(shí)f(xj)＜f(xi)且G(xj)＜G(xi);(2)若不存在支配xi的可行個(gè)體,則任意找一個(gè)可行個(gè)體xj與xi配對(duì),此時(shí)G(xj)＜G(xi),將配對(duì)的個(gè)體進(jìn)行二分交叉生成后代xi+1=(xi+xj)/2,即取xi和xj連線的中點(diǎn)作為xi的后代,xi+1可看成將個(gè)體xi沿著由xi指向xj的方向向xj靠近.由于xj至少在一個(gè)目標(biāo)上比xi好,從而上述配對(duì)進(jìn)行二分交叉的方法使后代個(gè)體的目標(biāo)函數(shù)值或者約束違反程度減小.此外,生成的個(gè)體可能是可行解,也可能是不可行解,維持了種群的多樣性.

混合交叉算子對(duì)搜索空間進(jìn)行線性搜索,加快了算法的收斂速度.為了避免算法早熟收斂,提高算法的搜索能力,在進(jìn)化過(guò)程中引入單形交叉算子.

2.2.3 單形交叉算子

單形交叉算子[12]是進(jìn)化算法中常用的交叉算子,它基于均勻分布產(chǎn)生后代個(gè)體,并且交叉過(guò)程不需要父代個(gè)體的適應(yīng)值信息.單形交叉算子的搜索區(qū)域隨著進(jìn)化過(guò)程自適應(yīng)地調(diào)整,保證了算子在進(jìn)化初期具有較強(qiáng)的全局搜索能力,后期具有較強(qiáng)的局部搜索能力.具體步驟如下:

在Rn中,n+1個(gè)獨(dú)立的父代個(gè)體xi(i=1,2,…,n+1)形成一個(gè)單形,首先以一定比例ε將單形沿各個(gè)方向xi-o(i=1,2,…,n+1)擴(kuò)張形成一個(gè)新的單形,其中o是n+1個(gè)父代的中心,即,新單形的頂點(diǎn)yi=(1+ε)(xi-o),i=1,2,…,n+1.然后在新單形中任取一點(diǎn)作為后代個(gè)體z,即z=k1y1+ k2y2+…+kn+1yn+1+o,其中ki(i=1,2,…,n+1)是[0,1]上均勻分布的隨機(jī)數(shù),且k1+k2+…+kn+1=1.

2.3 雙目標(biāo)偏好約束優(yōu)化進(jìn)化算法

對(duì)轉(zhuǎn)化的雙目標(biāo)優(yōu)化問(wèn)題(3),筆者提出的偏好進(jìn)化算法步驟如下.

(1)初始化群體:隨機(jī)產(chǎn)生規(guī)模為N的初始種群P(0)={x1,x2,…,xN},其中xi∈S(i=1,2,…,N),令k=0.

(2)交叉操作:計(jì)算種群中可行解的比例ρ.當(dāng)0≤ρ＜1時(shí),先對(duì)種群進(jìn)行混合交叉,并采用穩(wěn)態(tài)策略更新種群,對(duì)更新后的種群再進(jìn)行單形交叉;當(dāng)ρ=1時(shí),對(duì)種群只進(jìn)行單形交叉.將進(jìn)行交叉的個(gè)體稱為目標(biāo)個(gè)體.

①混合交叉:以概率pc1選擇交叉的個(gè)體.若ρ=0,對(duì)P(k)中個(gè)體進(jìn)行2.2.1節(jié)的非支配聚類交叉.若目標(biāo)個(gè)體是被支配個(gè)體,則后代個(gè)體直接代替目標(biāo)個(gè)體;若目標(biāo)個(gè)體是主導(dǎo)個(gè)體,且后代個(gè)體支配目標(biāo)個(gè)體,或與目標(biāo)個(gè)體互相非支配且后代個(gè)體的約束違反小,則后代個(gè)體代替目標(biāo)個(gè)體,否則拋棄后代個(gè)體.若0＜ρ＜1,進(jìn)行2.2.2節(jié)的二分交叉.若后代可行,則后代和可行父代中目標(biāo)函數(shù)值小的代替可行父代;若后代不可行,則后代和不可行父代中約束違反值小的代替不可行父代.

(3)變異操作:設(shè)xi=(xi1,xi2,…,xin),是以概率pm從O1中選出進(jìn)行變異的個(gè)體,對(duì)xi進(jìn)行如下變異.(a)隨機(jī)從xi=(xi1,xi2,…,xin)中選擇一個(gè)基因位xik(k=1,2,…,n);(b)從[lk,uk]隨機(jī)產(chǎn)生實(shí)數(shù)x′ik代替xik,得到變異后代x′i=(x′i1,x′i2,…,x′in),即

其中,r是[0,1]的隨機(jī)數(shù),變異后代集合記為O2.

(4)選擇操作:在P(k)∪O1∪O2中,用2.1節(jié)的適應(yīng)度函數(shù)選擇適應(yīng)值小的前N個(gè)個(gè)體作為下一代種群P(k+1).

(5)判斷停止準(zhǔn)則:若滿足停止條件(通常采用目標(biāo)函數(shù)值評(píng)估次數(shù)),則輸出最優(yōu)解;否則,令k=k+1,轉(zhuǎn)步驟(2).

3 數(shù)值實(shí)驗(yàn)

3.1 測(cè)試函數(shù)及參數(shù)設(shè)置

為了測(cè)試筆者提出算法的有效性,采用文獻(xiàn)[1]中6個(gè)常用的標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行試驗(yàn).實(shí)驗(yàn)中,參數(shù)取值如下:種群規(guī)模N=250,混合交叉概率pc1=0.5,單形交叉概率pc2=0.8,變異概率pm=0.1,單形交叉擴(kuò)張比例ε=6,產(chǎn)生后代個(gè)數(shù)λ=5,適應(yīng)度函數(shù)評(píng)價(jià)次數(shù)(FES)是240 000,等式約束違反的容忍值δ=0.000 1.對(duì)所有測(cè)試函數(shù),獨(dú)立運(yùn)行30次,記錄結(jié)果的最好值、平均值、最差值以及標(biāo)準(zhǔn)差.

表1 筆者提出的算法(PMO)與經(jīng)典算法SR,SMES和SAFF的實(shí)驗(yàn)結(jié)果比較

3.2 結(jié)果及分析

將筆者提出的算法(PMO)與另外3個(gè)經(jīng)典高效的進(jìn)化算法SR[1],SMES[13]和SAFF[14]進(jìn)行比較.表1給出了各方法的最好值、平均值、最差值及標(biāo)準(zhǔn)差(3種經(jīng)典算法的結(jié)果來(lái)自相關(guān)文獻(xiàn)).從表1可看出,除g03外,筆者提出的算法在30次運(yùn)行中都找到了全局最優(yōu)解,且所得到解的最好值、平均值、最差值以及方差都比另外3種算法好,說(shuō)明筆者提出的算法具有良好的穩(wěn)定性.

此外,從函數(shù)評(píng)估次數(shù)來(lái)看,PMO為240 000次,與SMES算法相同,比SR算法的350 000次及SAFF算法1 400 000次都少.對(duì)于g03,筆者提出的算法找到了最優(yōu)值,雖然在平均值、最差值上稍劣于其他方法,但是從30次運(yùn)行的統(tǒng)計(jì)結(jié)果看,有18次得到的結(jié)果優(yōu)于-1.000.如果將函數(shù)評(píng)估次數(shù)增加到350 000,進(jìn)一步實(shí)驗(yàn)表明,30次獨(dú)立運(yùn)行結(jié)果中有15次找到全局最優(yōu)解-1.000 5,此外還有12次的結(jié)果優(yōu)于-1.000,只有3次的結(jié)果稍劣于-1.000.

以上結(jié)果表明,PMO算法用較少的計(jì)算次數(shù)得到的結(jié)果類似或優(yōu)于另外3種算法,得到結(jié)果的方差更小,因此PMO算法具有較強(qiáng)的尋優(yōu)能力和良好的穩(wěn)定性.

4 總 結(jié)

筆者將約束優(yōu)化問(wèn)題轉(zhuǎn)化為雙目標(biāo)優(yōu)化問(wèn)題,用進(jìn)化算法求解轉(zhuǎn)化后的問(wèn)題.根據(jù)群體特征設(shè)計(jì)了混合交叉算子,保證群體在進(jìn)化初期沿著不同方向快速向可行域靠近,加快了算法收斂.提出了新的帶偏好適應(yīng)度函數(shù)進(jìn)行個(gè)體比較和選擇,新適應(yīng)度函數(shù)以個(gè)體到參考點(diǎn)的加權(quán)距離衡量個(gè)體優(yōu)劣,參考點(diǎn)和加權(quán)向量體現(xiàn)了進(jìn)化過(guò)程中選擇的偏好.筆者將算法的進(jìn)化過(guò)程分為3個(gè)階段,在每個(gè)階段,自適應(yīng)地選擇參考點(diǎn)和加權(quán)向量,實(shí)現(xiàn)進(jìn)化過(guò)程對(duì)不同目標(biāo)的偏好,使算法快速找到全局最優(yōu)解.數(shù)值實(shí)驗(yàn)結(jié)果表明,筆者提出的算法對(duì)具有不同特點(diǎn)的測(cè)試問(wèn)題是有效的,與3種經(jīng)典算法[1,13-14]的結(jié)果對(duì)比,說(shuō)明筆者提出的算法效率更高.

[1]Runarsson T P,Yao X.Stochastic Ranking for Constrained Evolutionary Optimization[J].IEEE Transactions on Evolutionary Computation,2000,4(3):284-294.

[2]Deb K.An Efficient Constraint Handling Method for Genetic Algorithms[J].Computer Methods in Applied Mechanics and Engineering,2000,186(2):311-338.

[3] 劉若辰,焦李成,雷七峰,等.一種新的差分進(jìn)化約束優(yōu)化算法[J].西安電子科技大學(xué)學(xué)報(bào),2011,38(1):47-53. Liu Ruochen,Jiao Licheng,Lei Qifeng,et al.New Differential Evolution Constrained Optimization Algorithm[J]. Journal of Xidian University,2011,38(1):47-53.

[4]鄭建國(guó),王翔,劉榮輝.求解約束優(yōu)化問(wèn)題的ε-DE算法[J].軟件學(xué)報(bào),2012,23(9):2374-2387. Zheng Jianguo,Wang Xiang,Liu Ronghui.ε-Differential Evolution Algorithm for Constrained Optimization Problems [J].Journal of Software,2012,23(9):2374-2387.

[5] 劉大蓮,徐尚文.求解約束優(yōu)化問(wèn)題的內(nèi)外交叉遺傳算法[J].系統(tǒng)工程理論與實(shí)踐,2012,32(1):189-195. Liu Dalian,Xu Shangwen.Inward-outward Crossover Based Genetic Algorithm for Constrained Optimization Problem [J].System Engineering-Theory and Practice,2012,32(1):189-195.

[6] 龍文,梁昔明,徐松金,等.聚類佳點(diǎn)集交叉的約束優(yōu)化混合進(jìn)化算法[J].計(jì)算機(jī)研究與發(fā)展,2012,49(8):1753-1761. Long Wen,Liang Ximing,Xu Songjin,et al.A Hybrid Evolutionary Algorithm Based on Clustering good-point Set Crossover for Constrained Optimization[J].Journal of Computer Research and Development,2012,49(8):1753-1761.

[7]Homaifar A,Qi C X,Lai S H.Constrained Optimization Via Genetic Algorithms[J].Simulation,1994,62(4):242-254.

[8]周育人,李元香,王勇,等.Pareto強(qiáng)度值演化算法求解約束優(yōu)化問(wèn)題[J].軟件學(xué)報(bào),2003,14(7):1243-1249. Zhou Yuren,Li Yuanxiang,Wang Yong,et al.A Pareto Strength Evolutionary Algorithm for Constrained Optimization [J].Journal of Software,2003,14(7):1243-1249.

[9]Wang Y,Cai Z X.Combining Multiobjective Optimization with Differential Evolution to Solve Constrained Optimization Problems[J].IEEE Transactions on Evolutionary Computation,2012,16(1):117-134.

[10]Miettinen K.Nonlinear Multiobjective Optimization[M].Boston:Kluwer Academic Publishers,1999.

[11]Aguirre A H,Rionda S B,Coello C C A,et al.Handling Constraints Using Multiobjective Optimization Concepts[J]. International Journal for Numerical Methods in Engineering,2004,59(15):1989-2017.

[12]Tsutsui S,Yamamura M,Higuchi T.Multi-parent Recombination with Simplex Crossover in Real-coded Genetic Algorithms[C]//Proceedings of the Genetic and Evolutionary Computing Conference.San Francisco:Morgan Kaufmann Publishers,1999:657-664.

[13]Mezura-Montes E,Coello C C A.A Simple Multimembered Evolution Strategy to Solve Constrained Optimization Problems[J].IEEE Transactions on Evolutionary Computation,2005,9(1):1-17.

[14]Farmani R,Wright J A.Self-adaptive Fitness Formulation for Constrained Optimization[J].IEEE Transactions on Evolutionary Computation,2003,7(5):445-455.

(編輯:郭 華)

Multi-objective evolutionary algorithm based on preference for constrained optimization problems

DONG Ning1,WANG Yuping2

(1.School of Mathematics and Statistics,Xidian Univ.,Xi’an 710071,China; 2.School of Computer Science and Technology,Xidian Univ.,Xi’an 710071,China)

Constrained optimization problems(COPs)are converted into the bi-objective optimization problem and solved with a new preference based multi-objective evolutionary algorithm.A new hybrid crossover operator is proposed to improve the search ability in the evolutionary process,and also a novel fitness function with preference based on the achievement scalarizing function(ASF)which is used in the method of weighted metrics in multi-objective optimization is presented.The new fitness measures the merits of individuals by the weighting distance from individuals to the reference point,where the reference point and the weighting vector afford the preference for selection.In different evolutionary stages,the reference point and weighting vector are chosen adaptively according to the individuals in population to make a tradeoff between the preferences to the two objectives.Numerical experiments for several standard test functions with different characteristics illustrate that the new proposed algorithm is effective and efficient.

constrained optimization;multi-objective optimization;evolutionary algorithm;preference; achievement scalarizing function

TP301.6

A

1001-2400(2014)01-0098-07

10.3969/j.issn.1001-2400.2014.01.018

2012-10-16 < class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2013-09-16

國(guó)家自然科學(xué)基金資助項(xiàng)目(61272119)

董 寧(1980-),女,西安電子科技大學(xué)博士研究生,E-mail:dongning@snnu.edu.cn.

http://www.cnki.net/kcms/detail/61.1076.TN.20130916.0926.201401.121_014.html