基于獎懲機制的協(xié)同多目標優(yōu)化算法

伍大清，邵 明，李 悛，李 康

（1.南華大學計算機科學與技術學院，湖南 衡陽421001；2.東華大學旭日工商管理學院，上海200051；3.教育部計算智能與信號處理重點實驗室，合肥 230039；4.上海工程技術大學管理學院，上海 200051）

基于獎懲機制的協(xié)同多目標優(yōu)化算法

伍大清1，2，3，邵 明4，李 悛1，李 康2

（1.南華大學計算機科學與技術學院，湖南 衡陽421001；2.東華大學旭日工商管理學院，上海200051；3.教育部計算智能與信號處理重點實驗室，合肥 230039；4.上海工程技術大學管理學院，上海 200051）

為提高已有多目標優(yōu)化算法在求解高維復雜多目標優(yōu)化問題上的解集分布性和收斂性，提出一種新的多目標微粒群優(yōu)化算法。該算法基于多目標協(xié)同框架，將多種群獎懲機制進化算法用于求解分解后的若干單目標優(yōu)化子問題，采用動態(tài)環(huán)形的拓撲結構，設計一種新型精英學習策略，獲得逼近Pareto前沿的最優(yōu)解集。通過典型的多目標優(yōu)化函數(shù)進行測試驗證，結果表明，與現(xiàn)有多目標優(yōu)化算法相比，該算法不僅具有較好的收斂性能，而且解集分布性更均勻、覆蓋范圍更廣。

多目標優(yōu)化算法；協(xié)同；精英學習策略；拓撲結構；獎懲機制

DO I：10.3969/j.issn.1000-3428.2015.10.035

1 概述

在科學研究和工程設計中許多優(yōu)化問題涉及多個目標同時優(yōu)化，而且這些目標之間彼此沖突、相互制約，通常把這類型問題稱為多目標優(yōu)化問題（Multiobjective Optimization Problem，MOP），多目標優(yōu)化問題一般情況下幾乎找不到使得多個目標同時達到最優(yōu)的解，通常采用帕累托最優(yōu)解集平衡多個相互沖突

的目標。近年來，進化多目標優(yōu)化前沿領域涌現(xiàn)出了不少新的求解思路和算法框架，如粒子群優(yōu)化、人工免疫系統(tǒng)、分布估計算法、協(xié)同進化算法、基于偏好的算法、文化進化算法和基于分解的算法等，越來越多地被引入到進化多目標優(yōu)化領域［1］，目的在于在多目標空間前端上找到一組分布具有盡可能好的逼近性、寬廣性和均勻性帕累托解集。

目前，求解多目標優(yōu)化問題的方法很多［2］。文獻［3］提出的基于最小生成樹的多目標進化算法；Eber-hart引入擴展內(nèi)存存儲Pareto最優(yōu)解［4］，并將其作為群體的領導粒子，通過個體經(jīng)驗和群體經(jīng)驗單向共享信息引導粒子向最優(yōu)值進化；文獻［5］為了保持Pareto解集的分布性，采用了基于支配關系及適應度共享的策略；許多多目標進化算法都是把多目標優(yōu)化問題當作一個整體來對待，而文獻［6］構造了基于分解的多目標進化算法（MOEA/D）框架，在多目標進化算法中引入數(shù)學規(guī)劃中較為成熟的分解策略［2］，算法將逼近整個帕累托前沿面的問題分解為一定數(shù)量的單目標優(yōu)化問題，然后利用進化算法同時求解這些問題。文獻［7］提出基于分解的均勻設計的多目標差分算法，文獻［8］提出進化多目標優(yōu)化的混合框架等，結果表明，基于分解的多目標進化算法是一種有效方法［9］，為求解進化多目標優(yōu)化問題提供了一種新思路［2］。

本文基于合作協(xié)同的多目標進化算法框架，將基于獎懲機制以及精英學習策略的進化算法用于求解分解后的若干單目標優(yōu)化子問題，提出一種基于獎懲機制的協(xié)同微粒群多目標優(yōu)化算法（CCMPSO）。在該算法中，種群被劃分成多個子種群分別優(yōu)化不同的子問題，每個子種群采用環(huán)形的拓撲結構，每隔一定周期內(nèi)動態(tài)地重組，以提高種群多樣性。同時提出基于獎懲機制的微粒群優(yōu)化算法速度更新方式，并設計了一種新型精英學習策略，以避免外部存檔集陷入局部最優(yōu)。

2 協(xié)同多目標優(yōu)化算法

2.1 基本原理

基本單目標PSO算法中［10］的粒子僅通過跟蹤個體最優(yōu)和群體最優(yōu)進行學習，顯然，這是一個理想社會條件，而且在搜索的過程中很難平衡勘測與開發(fā)這對矛盾。而實際上除了個體最優(yōu)與群體最優(yōu)，粒子在運行過程中所處的鄰域環(huán)境對它的影響非常大，如果對自身起推動（pull）作用的環(huán)境粒子進行獎勵，對自身起阻礙（push）作用的環(huán)境粒子進行懲罰，將有助于粒子在多目標空間前端上快速找到一組分布具有盡可能好的逼近性、寬廣性和均勻性帕累托解集。

因此，CCMPSO算法中引進局部鄰居粒子N max，在每個小種群中，所有粒子的個體最優(yōu)粒子所對應的適應度值排序，最大的適應度粒子將被選作N max，N max（t）=argmax｛f（Pbest1），f（Pbest2），…，f（Pbestn）｝。引入獎懲因子r2，判斷每一代生成的新個體是否對Pareto解集做貢獻，如果產(chǎn)生的新個體能支配外部存檔集中的非支配解，則產(chǎn)生r2＞0的獎勵因子，加快粒子的飛行速度，提高粒子勘測區(qū)域深度的能力；如果產(chǎn)生的新個體未能支配外部存檔集中的非支配解，則產(chǎn)生r2＜0懲罰因子，將減緩粒子的飛行速度，提高粒子開發(fā)區(qū)域廣度的能力，如圖1所示。

圖1 CCMPSO粒子運行過程自適應獎/懲學習過程

2.2 拓撲結構

CCMPSO中的子種群采用環(huán)形拓撲結構，為了粒子向周圍環(huán)境中的不同的粒子學習，充分保持種群的多樣性，每隔一定周期，子種群的結構進行重組，每個粒子所在的鄰域粒子發(fā)生改變。CCMPSO動態(tài)種群結構如圖2所示，具體過程在文獻［11］中有詳細的介紹。

圖2 CCMPSO動態(tài)種群結構

2.3 粒子更新

粒子通過在搜索空間中以一定的速度飛行，粒子的飛行速度基于個體的飛行經(jīng)驗和群體的飛行經(jīng)驗以及環(huán)境的飛行經(jīng)驗動態(tài)調(diào)整，在D維的搜索空間，n個粒子通過競爭與協(xié)作來尋找問題的最優(yōu)解。優(yōu)化問題的過程可看做粒子不斷更新的過程，粒子的速度和位移更新模型如下：

其中：i=1，2，…，n；d=1，2，…，D；r1，r2以及r3是學習因子，是服從U（0，1）分布的隨機數(shù)，r1+r2+r3= 1；w是慣性系數(shù)；t表示迭代次數(shù)，χi（t）是第 t次迭代第i個粒子對應的位置向量；νi（t）是第t次迭代第i個粒子對應的速度向量；Pbesti是粒子個體最優(yōu)；Achiνe是外部共享Pareto解集合，以及Nmax對鄰域環(huán)境影響的獎懲粒子。參照文獻［10］對粒子位置和速度越界進行處理。

顯然，粒子速度位移更新模型受到4個部分之間的相互平衡和制約：（1）代表粒子有保持本身原來速度的趨勢；（2）代表粒子有向本身歷史最佳位置逼近的趨勢；（3）反映了粒子受到周圍環(huán)境鄰域粒子的影響；（4）代表粒子間協(xié)同合作與知識共享的群體歷史經(jīng)驗，有向群體歷史最佳位置逼近的趨勢。

2.4 精英學習策略

為了防止外部存檔庫中的粒子陷入局部最優(yōu)，CCMPSO在外部存檔中增加了一個精英學習策略，以增強算法跳出局部最優(yōu)的能力，該策略通過外部擾動機制來改善搜索未知區(qū)域的能力，通過內(nèi)部擾動機制來增強已知搜索區(qū)域的搜索深度，引入該策略，減緩了粒子收斂速度，能夠為外部存檔庫中粒子提供有效信息找到更多的非劣解，獲得種群多樣性，如式（3）、式（4）所示：

其中，X1，X2為已知搜索區(qū)域外部存儲庫中的自由向量；未知搜索區(qū)域的Y1，Y22個新的搜索向量可由公式獲得；c1，c2是0～1之間的隨機數(shù)。外部存檔集所有種群共享一個外部存檔集，用來存儲每次迭代產(chǎn)生的非劣解。如果檔案集合中的非劣解數(shù)目超過其最大容量時，則需要在檔案中篩選具有代表性的個體保留下來，將利用擁擠距離算法［12］來保持解群分布的均勻性，對產(chǎn)生新的非支配解進行擇優(yōu)處理。

2.5 共享外部存檔集更新

CCMPSO中所有子種群共享一個外部存檔集Achiνe，用來存儲每次迭代產(chǎn)生的非劣解。在每次迭代之后進行更新，每個粒子全局最優(yōu)位置視為非劣解的候選方案被存儲在外部存檔中，在不同的前沿面保存最終的解群即是算法求解的結果。通常外部存檔集一般與種群的規(guī)模一致，如果數(shù)目超過設定的閾值時，則需要利用文獻［13］中的擁擠距離算子將具有代表性的個體保留下來，從而保持解群分布的均勻性，偽代碼如下所示：

2.6 算法描述

CCMPSO基于多目標技術，根據(jù)多目標優(yōu)化問題個數(shù)將種群劃分成多個子種群，利用基于獎懲機制的微粒群優(yōu)化算法分別對各個子問題進行尋優(yōu)處理，使用新型精英學習策略對外部存檔進行更新，每個子種群在一定的學習周期內(nèi)重組種群結構，通過共享的外部存檔，相互協(xié)同合作尋找到分布盡可能好的逼近性、寬廣性和均勻性Pareto最優(yōu)解集合。CCMPSO算法流程如下：

Step1 初始化種群。隨機初始化粒子數(shù)為N的群體以及對應的適應度，針對多目標問題的目標個

數(shù)N，將種群劃分成N個子種群，各個粒子所對應的速度，算法終止條件為最大迭代次數(shù)T，初始化粒子的個體最優(yōu)位置Pbest，外部存檔集Achiνe以及局部鄰居粒子N max，外部存檔集初始化空集。

Step2 對種群中所有的粒子采用式（1）、式（2）更新粒子的速度和位置；并對粒子越界速度、位移進行處理。

Step3 計算新粒子的各個目標適應度值，判斷是否能支配外部存檔中的非支配解，若是則產(chǎn)生獎勵因子；否則產(chǎn)生懲罰因子。分別更新 Pbest以及N max。

Step4 執(zhí)行精英學習策略。

Step5 利用2.5節(jié)更新外部存檔集，判斷外部存檔大小是否超過種群規(guī)模，若是，則使用擁擠距離更新外部存檔。

Step6 迭代計數(shù)器累增1，是否能整除拓撲結構重組周期 G，如果是，則執(zhí)行 Step7；否則執(zhí)行Step8。

Step7 對所有粒子的拓撲結構進行重組，轉Step2。

Step8 迭代次數(shù)累增1，判斷是否滿足算法終止條件。若滿足，則執(zhí)行Step6；否則轉Step2。

Step9 輸出Pareto最優(yōu)前沿面，算法結束。

1 本刊辟有論著、專科護理、護理管理、護理教育、基礎護理、心理衛(wèi)生、個案護理、藥物與護理、健康教育、社區(qū)護理、調(diào)查分析、經(jīng)驗交流、海外之窗、護士筆談等欄目，歡迎廣大護理人員踴躍投稿。

3 仿真實驗結果與分析

3.1 測試函數(shù)

本文的實驗部分通過5個不同類型的經(jīng)典測試問題［14］來驗證CCMPSO算法的有效性，表1列出了測試函數(shù)的表達式。實驗結果與 CMPSO［15］，MOCLPSO［16］進行了比較。所有算法在每個測試函數(shù)上的初始種群大小NP均設置為100，算法終止條件均為迭代次數(shù)T=1 000，CCMPSO中慣性系數(shù)ω=0.729，拓撲結構重組周期G=8，其他算法中的控制參數(shù)設置同相應原文獻。

表1 測試函數(shù)

在實驗中，算法性能對比采用通用的2個性能評價標準：

（1）收斂性γ。γ測量算法最終獲得的非支配解集Q與理論Pareto最優(yōu)解的近似解集P*的逼近程度：

其中，di為目標空間中Q的個體i與其相鄰個體間

其中，di為Q中的個體i與P*中距離最近個體在目標空間中的歐氏距離；γ的值越小說明算法獲得的非支配解Q越接近真實的Pareto前沿，算法收斂性越好［17］。

3.2 參數(shù)敏感性分析

參數(shù)敏感性分析過程如下：

（1）獎懲機制特性分析

為了檢驗獎懲機制對粒子尋優(yōu)的作用，以ZDT3函數(shù)為例，分別對粒子速度更新公式中是否包含

第3項環(huán)境影響部分進行了測試。

圖3為1 000次迭代過程中1個粒子有無受到獎懲粒子影響的進化情況，圖3（b）展示了CCMPSO算法中的粒子在進化過程中有明顯被初始化的痕跡，是因為算法的多樣性保持機制在一定情況下被激活所造成。從粒子進化圖看，CCMPSO算法包含獎懲機制的速度更新模型，粒子更具有多樣性，不易陷入局部極值。

圖3 1 000次迭代過程中1個粒子進化的情況

（2）子種群拓撲結構重組周期G

CCMPSO所涉及的參數(shù)子種群拓撲結構重組周期G，以FON、ZDT3為例，結果如表2所示，間隔周期過小，會對粒子飛行造成擾動，所得到的支配解收斂性不足；間隔周期過大，種群多樣性缺失容易陷入局部最優(yōu)解；因此G取值為8。表3給出3種算法獨立運行30次，每次迭代1 000次，在不同測試函數(shù)上的收斂性、多樣性度量平均值和方差，實驗數(shù)據(jù)表明，CCMPSO具有較強的魯棒性。圖4中給出在3個測試函數(shù)上的Pareto前沿面，仿真結果表明，結合精英學習策略以及動態(tài)拓撲結構重組策略，基于獎懲機制協(xié)同框架下的微粒群多目標優(yōu)化算法CCMPSO，在解群分布的均勻性和寬廣性方面明顯優(yōu)于其他算法。

表2 不同重組周期下FON、ZDT3函數(shù)多樣性、收斂性度量結果

表3 3種算法分別求得5個測試函數(shù)評價指標比較

圖4 測試函數(shù)SCH，ZDT3，ZDT6最優(yōu)Pareto前沿面

4 結束語

針對現(xiàn)有多目標進化算法在求解高維復雜多目標優(yōu)化問題時求解精度較差、解集分布不均勻等問題，本文提出一種基于合作協(xié)同的多目標進化算法CCMPSO。該算法引進獎懲機制對微粒群多目標進化算法進行綜合改進，采用動態(tài)環(huán)形的拓撲結構以及精英學習策略，有效提升了CCMPSO的收斂性和解集分布性。通過對5個標準測試函數(shù)進行實驗，結果表明，該算法與現(xiàn)有多種多目標算法相比，不僅具有較好的收斂性能，而且解集分布性也更均勻，覆蓋范圍更廣。

［1］ 沈佳杰，江 紅.基于多變異個體的多目標差分進化改進算法［J］.計算機工程，2014，40（5）：203-208，215.

［2］ 侯 薇，董紅斌，印桂生.一種改進的基于分解的多目標進化算法［J］.計算機科學，2014，41（2）：114-118.

［3］ 李密青，鄭金華.一種多目標進化算法解集分布廣度評價方法［J］.計算機學報，2011，34（4）：647-664.

［4］ Coello C，Pulido G T.Handling Multiple Objectives with Particle Swarm Optimization［J］.IEEE Transactions on Evolutionary Computation，2004，8（3）：256-279.

［5］ Salazar-Lechuga M.Particle Swarm Optimization and Fitness Sharing to Solve Multi-objective Optimization Problem s［C］//Proceedings of IEEE CEC’05. Washington D.C.，USA：IEEE Press，2005：1204-1211.

［6］ Zhang Q.MOEA/D：A Multi-objective Evolutio-nary Algorithm Based on Decomposition［J］.IEEE Transactions on Evolutionary Computation，2007，11（6）：712-731.

［7］ Tan Y，Jiao Y，Li H，et al.MOEA/D Uniform Design：A New Version of MOEA/D for Optimization Problem s with M any Objectives［J］.Com puters&Operations Research，2013，40（6）：1648-1660.

［8］ Sindhya K.A Hybrid Framework for Evolutionary Multiobjective Optimization［J］.IEEE Transactions on Evolutionary Computation，2013，17（4）：495-511.

［9］ 薛 羽，莊 毅，顧晶晶，等.自適應離散差分進化算法策略的選擇［J］.軟件學報，2014，25（5）：984-996.

［10］ 伍大清.基于混合策略自適應學習的并行微粒群優(yōu)化算法研究［J］.控制與決策，2013，28（7）：1086-1094.

［11］ Wu Daqing.A Dynamic Multistage Hybrid Swarm Intelligence Optimization Algorithm for Function Optimization［J］. Discrete Dynamics in Nature and Society，2012，（2012）.［12］ Said M，Ahamed A.Hybrid Periodic Boundary Condition for Particle Swarm Optimization［J］.IEEE Transations on Antennas and Propagation，2007，55（11）：3251-3256.

［13］ Pratap D K.A Fast and Elitist Multi-objective Genetic Algorithm：NSGA-II［J］.IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.

［14］ Coello C A，Cortes N C.Solving Multi-objective Optimization Problems Using an Artificial Immune System［J］.Genetic Programming and Evolvable Machines，2005，（6）：163-190.

［15］ Zhan Z H.Multiple Opulations for Multiple Objectives： A Co-evolutionary Technique for Solving Multiobjective Optimization Problem s［J］.IEEE Transactions on Cybernetics，2013，43（2）：445-463.

［16］ Huang V L，Suganthan P N，Liang J J.Comprehensive Learning Particle Swarm Optimizer for Solving Multiobjective Optimization Problem s［J］.International Journal of Intelligent System s，2006，21（2）：209-226.

［17］ 畢曉君.基于自適應差分進化的多目標進化算法［J］.計算機集成制造系統(tǒng)，2012，17（12）：2660-2665.

編輯 索書志

Cooperative Multi-objective Optimization Algorithm Based on Reward and Punishment Mechanism

WU Daqing1，2，3，SHAO Ming4，LI Quan1，LI Kang2
（1.School of Computer Science and Technology，University of South China，Hengyang 421001，China；2.Glorious Sun School of Business and Management，Donghua University，Shanghai200051，China；3.Key Laboratory of Intelligent Computing&Signal Processing，Ministry of Education，Hefei230039，China；4.School of Management，Shanghai University of Engineering Science，Shanghai200051，China）

To improve the convergence and distribution of Multi-objective Evolutionary Algorithm（MOEA）in dealing with large-dimensional Multi-objective Optimization Problem（MOP），a multi-objective particle swarm optimization algorithm based on human disciplinary behavior is proposed.The strategies such as promoting/punishment factor，the elite learning strategy as well as restructuring topology structure strategy with dynamic population in period are introduced in proposed algorithm，to make the algorithm have strong global search ability and good robust performance.Some typical multi-objective optimization functions are tested to verify the algorithm，and simulation results show that，compared with recent other algorithms，the algorithm can ensure good convergence while having uniform distribution and wild coverage area.

multi-objective optimization algorithm；cooperative；elite learning strategy；topology structure；reward and punishment mechanism

伍大清，邵 明，李 悛，等.基于獎懲機制的協(xié)同多目標優(yōu)化算法［J］.計算機工程，2015，41（10）：186-191，198.

英文引用格式：Wu Daqing，Shao Ming，Li Quan，et al.Cooperative Multi-objective Optimization Algorithm Based on Reward and Punishment Mechanism［J］.Computer Engineering，2015，41（10）：186-191，198.

1000-3428（2015）10-0186-06

A

TP301

湖南省教育廳基金資助項目“基于協(xié)同演化計算的不確定信息車輛路徑問題研究”（13C818）；湖南省衡陽市科技局科技計劃基金資助項目“自學習演化計算在智能交通控制中的應用研究”（2013KG63）；教育部人工智能重點實驗室基金資助項目“基于冷鏈云配送模式的車輛路徑優(yōu)化模型及協(xié)同控制研究”。

伍大清（1982-），女，講師、博士，主研方向：多目標智能決策，智能計算；邵 明，副教授、博士；李 悛、李 康，講師、博士。

2014-08-11

2014-11-26E-mail：dqw-1982@126.com