基于種群分類的動(dòng)態(tài)約束多目標(biāo)進(jìn)化算法

許 峰，季洪霄

（安徽理工大學(xué)理學(xué)院，安徽 淮南232001）

動(dòng)態(tài)優(yōu)化問題（Dynamic Optimization Problem，DOP）的特點(diǎn)是目標(biāo)函數(shù)會(huì)隨著時(shí)間（環(huán)境）動(dòng)態(tài)變化。盡管動(dòng)態(tài)進(jìn)化算法的研究最早可追溯到1966年［1］，但直到20世紀(jì)80年代中期，動(dòng)態(tài)進(jìn)化算法的研究才逐漸形成熱點(diǎn)［2-3］。

相比單目標(biāo)動(dòng)態(tài)優(yōu)化問題，動(dòng)態(tài)多目標(biāo)優(yōu)化問題（Dynamic Multiobjective Optimization Problem，DMOP）的早期研究并不多。2000年后，DMOP日益受到眾多學(xué)者的重視，取得了一系列成果。Marco等［4］提出了一種鄰域搜索算法；Deb等［5］在 NSGAII基礎(chǔ)上提出了動(dòng)態(tài)多目標(biāo)進(jìn)化算法DNSGAII；Iason等［6］提出了一種基于向前預(yù)測(cè)的動(dòng)態(tài)多目標(biāo)進(jìn)化算法；Zhang等［7］提出了動(dòng)態(tài)免疫多目標(biāo)進(jìn)化算法；Amato等［8］提出了基于人工生命的動(dòng)態(tài)多目標(biāo)進(jìn)化算法；Bingul等［9］提出了自適應(yīng)動(dòng)態(tài)多目標(biāo)進(jìn)化算法。另外，動(dòng)態(tài)多目標(biāo)進(jìn)化算法測(cè)試函數(shù)的研究成果也相繼出現(xiàn)［10-11］。

動(dòng)態(tài)約束多目標(biāo)優(yōu)化問題（Dynamic Constrained Multiobjective Optimization Problem，DCMOP）的研究難度較大，相關(guān)成果并不多［12-13］。本文將聚類分析引入動(dòng)態(tài)約束多目標(biāo)進(jìn)化算法，用以處理約束條件，并對(duì)算法進(jìn)行了性能測(cè)試。

1 多目標(biāo)動(dòng)態(tài)優(yōu)化問題的相關(guān)概念

1．1 多目標(biāo)動(dòng)態(tài)優(yōu)化問題及其最優(yōu)解

記V0，VF和W 分別為n0維，nF維和mW維向量空間，則動(dòng)態(tài)多目標(biāo)優(yōu)化問題可表述為

其中，g（v0，vF）≤0，h（v0，vF）＝0分別為不等式和等式約束，f：V0×VF→W 是目標(biāo)向量函數(shù)，fi（v0，vF）為第i個(gè)子目標(biāo)函數(shù)。

若令V是n維決策變量空間，W 是m維目標(biāo)向量空間，參數(shù)VF是取值于實(shí)值空間T的參數(shù)，則（1）可描述為

其中，g（v，t）≤0，h（v，t）＝0分別為不等式和等式約束，f：V×T→W 是目標(biāo)向量函數(shù)。

相比多目標(biāo)靜態(tài)優(yōu)化問題而言，多目標(biāo)動(dòng)態(tài)優(yōu)化問題的Pareto最優(yōu)解和最優(yōu)前沿不是固定的，而是可能隨時(shí)間動(dòng)態(tài)變化的。

1．2 最優(yōu)解集的評(píng)價(jià)標(biāo)準(zhǔn)

（1）代間距離（Generation Distance，GD）

其中，n為最優(yōu)前沿PFknown包含的向量個(gè)數(shù)，di為PFknown中的向量到最優(yōu)前沿PFtrue的最短距離。

GD指標(biāo)反映了計(jì)算最優(yōu)前沿對(duì)理論最優(yōu)前沿的近似程度，即算法的收斂性。

（2）錯(cuò)誤率（Error Ration，ER）

其中，n為PFknown中的向量個(gè)數(shù)，且PFknown＝｛X1，X2，…，Xn｝，ei定義如下：

ER描述了PFknown對(duì)PFtrue的覆蓋程度，即最優(yōu)解集的分布性。

（3）分散性（Spaing，SP）

其中，n和di與代間距離中的定義相同。

顯然，分散性就是di的標(biāo)準(zhǔn)差，它反映了Pareto解集的均勻性。

2 群體劃分動(dòng)態(tài)約束多目標(biāo)進(jìn)化算法

2．1 劃分群體

2．1．1 按群體的可行性劃分

由于在進(jìn)化初期可行解的數(shù)量較少，此時(shí)進(jìn)行Pareto運(yùn)算意義不大，還會(huì)導(dǎo)致算法效率的降低。因此，在劃分群體時(shí)，首先要將其劃分為可行群體和非可行群體，提高Pareto運(yùn)算的效率。

2．1．2 按Pareto性能劃分

將群體劃分為可行和不可行2個(gè)群體后，再對(duì)可行群體中的個(gè)體進(jìn)行Pareto運(yùn)算，找出所有的Pareto最優(yōu)解。這樣，就將可行群體劃分為可行非Pareto群體與可行Pareto群體。

2．1．3 對(duì)可行Pareto群體進(jìn)行聚類

由于進(jìn)化算法并不限制相同或相似個(gè)體的數(shù)量，因此在算法的后期，可行Pareto群體中有可能會(huì)出現(xiàn)大量相同或類似的個(gè)體，從而影響解的分布性和均勻性。為了解決此問題，可以對(duì)可行Pareto群體進(jìn)行聚類，即在每個(gè)聚類群體中隨機(jī)挑選一個(gè)個(gè)體，將它們合并為一個(gè)群體。

通過(guò)上述4步劃分，種群最終被劃分為4個(gè)子種群：不可行子種群、非Pareto子種群、非聚類Pareto子種群和聚類Pareto子種群。

2．2 群體的R適應(yīng)度

顯然，在上述4類子種群中，不可行子種群的適應(yīng)能力最差，依次遞增，所以可以根據(jù)下列大小關(guān)系給上述4類子種群賦以R適應(yīng)度：

R（不可行子種群）?R（可行非Pareto子種群）≤R（非聚類Pareto子種群）?R（聚類Pareto子種群）

除前幾代外，選擇操作均根據(jù)R適應(yīng)度進(jìn)行。

2．3 算法步驟

（1）對(duì)時(shí)間區(qū)間進(jìn)行等距分割，記不同環(huán)境為t1，…，ts，令t＝t1；

（2）在環(huán)境ti（i＝1，2，…，s），隨機(jī)產(chǎn)生初始種群，令k＝0；

（7）對(duì)群體進(jìn)行基本遺傳操作（比例選擇、單點(diǎn)交叉、均勻變異）運(yùn)算；

（8）若滿足停止條件，輸出優(yōu)化結(jié)果，算法終止；否則轉(zhuǎn)（3）。

3 算法性能測(cè)試

下面分別用種群分類動(dòng)態(tài)多目標(biāo)進(jìn)化算法（IDMEA）、常規(guī)動(dòng)態(tài)多目標(biāo)進(jìn)化算法（DMEA）動(dòng)態(tài)NSGAII算法對(duì)2個(gè)動(dòng)態(tài)約束多目標(biāo)測(cè)試函數(shù)DMOP1和DMOP2進(jìn)行數(shù)值優(yōu)化計(jì)算，并利用2個(gè)性能度量指標(biāo)函數(shù)C-measure和U-measure對(duì)算法進(jìn)行定量評(píng)價(jià)。

（1）DMOP1測(cè)試函數(shù)

該函數(shù)的Pareto最優(yōu)解集不隨時(shí)間變化，但Pareto最優(yōu)前端隨時(shí)間變化。

（2）DMOP2測(cè)試函數(shù)

（2）DMOP2測(cè)試函數(shù)該函數(shù)的Pareto最優(yōu)前端隨時(shí)間變化。

數(shù)值實(shí)驗(yàn)參數(shù)為：群體規(guī)模為100，進(jìn)化代數(shù)為50，交叉概率為0．9，變異概率為0．1。

圖1～圖4分別給出了由IDMEA和DMEA計(jì)算出的DMOP1和DMOP2當(dāng)t＝0．25和0．5時(shí)的Perato最優(yōu)前端。

為了消除算法的隨機(jī)性，下面再根據(jù)算法的性能統(tǒng)計(jì)指標(biāo)對(duì)IDMEA進(jìn)行測(cè)評(píng)［14］。

圖1 t＝0．25時(shí)DMOP 1的Perato最優(yōu)前端

圖2 t＝0．50時(shí)DMOP 1的Perato最優(yōu)前端

圖3 t＝0．25時(shí)DMOP 2的Perato最優(yōu)前端

可以利用性能度量指標(biāo)函數(shù)C-measure來(lái)進(jìn)行解的收斂性評(píng)測(cè)，利用性能度量指標(biāo)函數(shù)U-measure來(lái)進(jìn)行解的分布性和均勻性評(píng)測(cè)。

圖5中給出了DNSGAII、DMEA和IDMEA（分別記為1，2，3）3種算法對(duì)DMOP1和DMOP2在不同環(huán)境下C-measure值的統(tǒng)計(jì)盒圖。其中，第1行前2個(gè)圖為DMOP1在t＝0．25時(shí)的C-measure值盒圖，后2個(gè)圖為DMOP1在t＝0．50時(shí)的C-measure值盒圖；第2行前2個(gè)圖為DMOP2在t＝0．25時(shí)的C-measure值盒圖，后2個(gè)圖為DMOP2在t＝0．50時(shí)的C-measure值盒圖。圖中的C（i，j）表示第i種算法和第j種算法對(duì)同一問題分別求得的Pareto最優(yōu)解集Ai和Bj的C-measure值。

圖4 t＝0．50時(shí)DMOP 2的Perato最優(yōu)前端

圖5 3種算法對(duì)DMOP1和DMOP2在t＝0．25，0．50時(shí)C-measure值的統(tǒng)計(jì)盒圖

圖6 3種算法對(duì)DMOP1和DMOP2在t＝0．25，0．50時(shí)U-measure值的統(tǒng)計(jì)盒圖

圖6中給出了DNSGAII、DMEA和IDMEA這3種算法對(duì)DMOP1和DMOP2在不同環(huán)境下U-measure值的統(tǒng)計(jì)盒圖。其中，第1行分別為DMOP1在t＝0．25和t＝0．50時(shí)的U-measure值盒圖；第2行分別為DMOP2在t＝0．25和t＝0．50時(shí)的U-measure值盒圖。

從圖1～圖4中可以很清楚地看出，IDMEA方法得到的Perato最優(yōu)解不僅數(shù)量比較多，而且分布較為均勻。

從圖5中可以看出，C（3，i）＞C（i，3）（i＝1，2），這意味著IDMEA在不同環(huán)境下對(duì)不同測(cè)試函數(shù)求得的Perato最優(yōu)解的收斂性比其它2種算法所得的結(jié)果更好。

從圖6中可以看出，IDMEA在不同環(huán)境下對(duì)不同測(cè)試函數(shù)求得的Perato最優(yōu)解的U-measure值小于其它2種算法所得的結(jié)果，即算法IDMEA在不同環(huán)境下對(duì)不同測(cè)試函數(shù)求得的Perato最優(yōu)解在Perato最優(yōu)前端上的分布更廣泛、均勻。

4 結(jié)語(yǔ)

本文將聚類分析引入動(dòng)態(tài)約束多目標(biāo)進(jìn)化算法，改進(jìn)了約束條件的處理機(jī)制，數(shù)值實(shí)驗(yàn)結(jié)果和統(tǒng)計(jì)指標(biāo)表明：與常規(guī)動(dòng)態(tài)約束多目標(biāo)進(jìn)化算法相比，改進(jìn)后算法具有較好的分布性。

需要指出的是，動(dòng)態(tài)多目標(biāo)進(jìn)化算法與粒子群算法、蟻群算法、人工免疫系統(tǒng)、分布估計(jì)算法等均為近年來(lái)出現(xiàn)的新型進(jìn)化范例，理論體系尚不完善，分布性和收斂性等關(guān)鍵理論問題有待進(jìn)一步研究。本文對(duì)2個(gè)典型測(cè)試函數(shù)，基于對(duì)比實(shí)驗(yàn)研究了新算法的性能。由于如何衡量多次優(yōu)化結(jié)果的一致性和穩(wěn)定性等問題目前尚未解決，所以世代距離、錯(cuò)誤率和分散性3個(gè)量化評(píng)價(jià)指標(biāo)并不能完全反映多目標(biāo)優(yōu)化算法的性能，這在一定程度上影響了本文研究結(jié)論的普遍性。

［1］Fogel L J，Owens A J，Walsh M J．ArtificialIntelligence through Simulation Evolution［M］．New York：John Wiley，1966．

［2］Goldberg D E，Smith R E．Non-stationaryFunction Optimization Using Genetic Algorithms with Dominance and Diploids［C］．Proc．of the 2nd Int Conf．on Genetic Algorithms，Grefenstette J J（Eds．），1987：59-68．

［3］Krishnakumar K．Micro-geneticAlgorithms for Stationary and Non-stationary Function Optimization［J］．SPIE，Intelligent Control and Adaptive Systems，1989，289-296．

［4］Marco F，Deb K，Amato P．Dynamic Multiobjective Optimization Problems：Test Cases，Approximation，and Applications［C］．Proc．of the Evolutionary Multiobjective Optimization International Conference，F(xiàn)aro，Portugal，2003：311-326．

［5］Deb K，Bhadkara U R N，Karthik S．Dynamic Nultiobjective Optimization and Decision-making Using Modified NSGA-II：A Case on Hydro-thermal Power Scheduling［C］．Proc．of the 4th International Conference on Evolutionary Multi-Criterion Optimization，INCS 4403，Springer-Verlag，Matsushima，Japan，2007：803-817．

［6］Iason H，David W．Dynamic Multiobjective Optimization with Evolutionary Algorithms：A Forward-looking Approach［C］．Proc．of the GECCO'06，Washington USA，2006：1201-1208．

［7］Zhang Z H．MultiobjectiveOptimization Immune Algorithm in Dynamic Environment and Its Application to Greenhouse Control［J］．Applied Soft Computing，2008：959-971．

［8］Amato P，F(xiàn)arina M．An Life-Inspired Evolutionary Algorithm for Dynamic Multiobjective Optimization Problems［J］．Advances in Soft Computing，2005：113-125．

［9］Bingul Z，Sekmen A，Zein-Sabatto S．Adaptive Genetic Algorithms Applied to Dynamic Multi-objective Problems［C］．Proceedings of the Artificial Neural Networks in Engineering Conference（ANNIE'2000），Cihan H D，Anna L B，Joydeep G（EDs．）New York，ASME Press，2000：273-278．

［10］Jin Y C，Sendhoff B．Constructing Dynamic Optimization Test Problems Using the Multiobjective Optimization Concept．Proc．of the Evolutionary Workshops 2004，LNCS 3005，Springer-Verlag，Heidelberg，Germany，2004：525-536．

［11］Farina M，Deb K，Amato P．Dynamic Multi-objective Optimization Problems：Test Cases，Approximation，and Applications［J］．IEEE Transactions on Evolutionary Computation，2004，8（5）：311-326．

［12］Mei Y，Tang K，Yao X．Capacitated Arc Routing Problem in Uncertain Environments［C］．Proc．of the 2010 IEEE Congress on Evolutionary Computation（CEC2010），Barcelona，Spain，2010，18-23．

［13］劉淳安．動(dòng)態(tài)多目標(biāo)優(yōu)化進(jìn)化算法及其應(yīng)用［M］．北京：科學(xué)出版社，2011．

［14］楊亞強(qiáng)，劉淳安．一類帶約束動(dòng)態(tài)多目標(biāo)優(yōu)化問題的進(jìn)化算法［J］．計(jì)算機(jī)工程與應(yīng)用，2012，48（21）：45-48．