基于種群分類的動態約束多目標進化算法

許 峰，季洪霄

（安徽理工大學理學院，安徽 淮南232001）

動態優化問題（Dynamic Optimization Problem，DOP）的特點是目標函數會隨著時間（環境）動態變化。盡管動態進化算法的研究最早可追溯到1966年［1］，但直到20世紀80年代中期，動態進化算法的研究才逐漸形成熱點［2-3］。

相比單目標動態優化問題，動態多目標優化問題（Dynamic Multiobjective Optimization Problem，DMOP）的早期研究并不多。2000年后，DMOP日益受到眾多學者的重視，取得了一系列成果。Marco等［4］提出了一種鄰域搜索算法；Deb等［5］在 NSGAII基礎上提出了動態多目標進化算法DNSGAII；Iason等［6］提出了一種基于向前預測的動態多目標進化算法；Zhang等［7］提出了動態免疫多目標進化算法；Amato等［8］提出了基于人工生命的動態多目標進化算法；Bingul等［9］提出了自適應動態多目標進化算法。另外，動態多目標進化算法測試函數的研究成果也相繼出現［10-11］。

動態約束多目標優化問題（Dynamic Constrained Multiobjective Optimization Problem，DCMOP）的研究難度較大，相關成果并不多［12-13］。本文將聚類分析引入動態約束多目標進化算法，用以處理約束條件，并對算法進行了性能測試。

1 多目標動態優化問題的相關概念

1．1 多目標動態優化問題及其最優解

記V0，VF和W 分別為n0維，nF維和mW維向量空間，則動態多目標優化問題可表述為

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

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

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

相比多目標靜態優化問題而言，多目標動態優化問題的Pareto最優解和最優前沿不是固定的，而是可能隨時間動態變化的。

1．2 最優解集的評價標準

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

其中，n為最優前沿PFknown包含的向量個數，di為PFknown中的向量到最優前沿PFtrue的最短距離。

GD指標反映了計算最優前沿對理論最優前沿的近似程度，即算法的收斂性。

（2）錯誤率（Error Ration，ER）

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

ER描述了PFknown對PFtrue的覆蓋程度，即最優解集的分布性。

（3）分散性（Spaing，SP）

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

顯然，分散性就是di的標準差，它反映了Pareto解集的均勻性。

2 群體劃分動態約束多目標進化算法

2．1 劃分群體

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

由于在進化初期可行解的數量較少，此時進行Pareto運算意義不大，還會導致算法效率的降低。因此，在劃分群體時，首先要將其劃分為可行群體和非可行群體，提高Pareto運算的效率。

2．1．2 按Pareto性能劃分

將群體劃分為可行和不可行2個群體后，再對可行群體中的個體進行Pareto運算，找出所有的Pareto最優解。這樣，就將可行群體劃分為可行非Pareto群體與可行Pareto群體。

2．1．3 對可行Pareto群體進行聚類

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

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

2．2 群體的R適應度

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

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

除前幾代外，選擇操作均根據R適應度進行。

2．3 算法步驟

（1）對時間區間進行等距分割，記不同環境為t1，…，ts，令t＝t1；

（2）在環境ti（i＝1，2，…，s），隨機產生初始種群，令k＝0；

（7）對群體進行基本遺傳操作（比例選擇、單點交叉、均勻變異）運算；

（8）若滿足停止條件，輸出優化結果，算法終止；否則轉（3）。

3 算法性能測試

下面分別用種群分類動態多目標進化算法（IDMEA）、常規動態多目標進化算法（DMEA）動態NSGAII算法對2個動態約束多目標測試函數DMOP1和DMOP2進行數值優化計算，并利用2個性能度量指標函數C-measure和U-measure對算法進行定量評價。

（1）DMOP1測試函數

該函數的Pareto最優解集不隨時間變化，但Pareto最優前端隨時間變化。

（2）DMOP2測試函數

（2）DMOP2測試函數該函數的Pareto最優前端隨時間變化。

數值實驗參數為：群體規模為100，進化代數為50，交叉概率為0．9，變異概率為0．1。

圖1～圖4分別給出了由IDMEA和DMEA計算出的DMOP1和DMOP2當t＝0．25和0．5時的Perato最優前端。

為了消除算法的隨機性，下面再根據算法的性能統計指標對IDMEA進行測評［14］。

圖1 t＝0．25時DMOP 1的Perato最優前端

圖2 t＝0．50時DMOP 1的Perato最優前端

圖3 t＝0．25時DMOP 2的Perato最優前端

可以利用性能度量指標函數C-measure來進行解的收斂性評測，利用性能度量指標函數U-measure來進行解的分布性和均勻性評測。

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

圖4 t＝0．50時DMOP 2的Perato最優前端

圖5 3種算法對DMOP1和DMOP2在t＝0．25，0．50時C-measure值的統計盒圖

圖6 3種算法對DMOP1和DMOP2在t＝0．25，0．50時U-measure值的統計盒圖

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

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

從圖5中可以看出，C（3，i）＞C（i，3）（i＝1，2），這意味著IDMEA在不同環境下對不同測試函數求得的Perato最優解的收斂性比其它2種算法所得的結果更好。

從圖6中可以看出，IDMEA在不同環境下對不同測試函數求得的Perato最優解的U-measure值小于其它2種算法所得的結果，即算法IDMEA在不同環境下對不同測試函數求得的Perato最優解在Perato最優前端上的分布更廣泛、均勻。

4 結語

本文將聚類分析引入動態約束多目標進化算法，改進了約束條件的處理機制，數值實驗結果和統計指標表明：與常規動態約束多目標進化算法相比，改進后算法具有較好的分布性。

需要指出的是，動態多目標進化算法與粒子群算法、蟻群算法、人工免疫系統、分布估計算法等均為近年來出現的新型進化范例，理論體系尚不完善，分布性和收斂性等關鍵理論問題有待進一步研究。本文對2個典型測試函數，基于對比實驗研究了新算法的性能。由于如何衡量多次優化結果的一致性和穩定性等問題目前尚未解決，所以世代距離、錯誤率和分散性3個量化評價指標并不能完全反映多目標優化算法的性能，這在一定程度上影響了本文研究結論的普遍性。

［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，Faro，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，Farina 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］劉淳安．動態多目標優化進化算法及其應用［M］．北京：科學出版社，2011．

［14］楊亞強，劉淳安．一類帶約束動態多目標優化問題的進化算法［J］．計算機工程與應用，2012，48（21）：45-48．