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

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

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

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

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

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

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

多目標(biāo)優(yōu)化算法；協(xié)同；精英學(xué)習(xí)策略；拓?fù)浣Y(jié)構(gòu)；獎懲機(jī)制

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

1 概述

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

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

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

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

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

2.1 基本原理

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

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

圖1 CCMPSO粒子運(yùn)行過程自適應(yīng)獎/懲學(xué)習(xí)過程

2.2 拓?fù)浣Y(jié)構(gòu)

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

圖2 CCMPSO動態(tài)種群結(jié)構(gòu)

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是學(xué)習(xí)因子，是服從U（0，1）分布的隨機(jī)數(shù)，r1+r2+r3= 1；w是慣性系數(shù)；t表示迭代次數(shù)，χi（t）是第 t次迭代第i個粒子對應(yīng)的位置向量；νi（t）是第t次迭代第i個粒子對應(yīng)的速度向量；Pbesti是粒子個體最優(yōu)；Achiνe是外部共享Pareto解集合，以及Nmax對鄰域環(huán)境影響的獎懲粒子。參照文獻(xiàn)［10］對粒子位置和速度越界進(jìn)行處理。

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

2.4 精英學(xué)習(xí)策略

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

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

2.5 共享外部存檔集更新

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

2.6 算法描述

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

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

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

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

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

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

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

Step6 迭代計數(shù)器累增1，是否能整除拓?fù)浣Y(jié)構(gòu)重組周期 G，如果是，則執(zhí)行 Step7；否則執(zhí)行Step8。

Step7 對所有粒子的拓?fù)浣Y(jié)構(gòu)進(jìn)行重組，轉(zhuǎn)Step2。

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

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

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

3 仿真實(shí)驗結(jié)果與分析

3.1 測試函數(shù)

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

表1 測試函數(shù)

在實(shí)驗中，算法性能對比采用通用的2個性能評價標(biāo)準(zhǔn)：

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

其中，di為目標(biāo)空間中Q的個體i與其相鄰個體間

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

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

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

（1）獎懲機(jī)制特性分析

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

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

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

圖3 1 000次迭代過程中1個粒子進(jìn)化的情況

（2）子種群拓?fù)浣Y(jié)構(gòu)重組周期G

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

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

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

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

4 結(jié)束語

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

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

［2］ 侯 薇，董紅斌，印桂生.一種改進(jìn)的基于分解的多目標(biāo)進(jìn)化算法［J］.計算機(jī)科學(xué)，2014，41（2）：114-118.

［3］ 李密青，鄭金華.一種多目標(biāo)進(jìn)化算法解集分布廣度評價方法［J］.計算機(jī)學(xué)報，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］ 薛 羽，莊 毅，顧晶晶，等.自適應(yīng)離散差分進(jìn)化算法策略的選擇［J］.軟件學(xué)報，2014，25（5）：984-996.

［10］ 伍大清.基于混合策略自適應(yīng)學(xué)習(xí)的并行微粒群優(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］ 畢曉君.基于自適應(yīng)差分進(jìn)化的多目標(biāo)進(jìn)化算法［J］.計算機(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

伍大清，邵 明，李 悛，等.基于獎懲機(jī)制的協(xié)同多目標(biāo)優(yōu)化算法［J］.計算機(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）；湖南省衡陽市科技局科技計劃基金資助項目“自學(xué)習(xí)演化計算在智能交通控制中的應(yīng)用研究”（2013KG63）；教育部人工智能重點(diǎn)實(shí)驗室基金資助項目“基于冷鏈云配送模式的車輛路徑優(yōu)化模型及協(xié)同控制研究”。

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

2014-08-11

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