基于多變異個體的多目標差分進化改進算法

沈佳杰，江 紅，王 肅

(華東師范大學信息科學技術學院，上海 20024 1)

基于多變異個體的多目標差分進化改進算法

沈佳杰，江 紅，王 肅

(華東師范大學信息科學技術學院，上海 20024 1)

針對多目標差分進化算法在高維函數下收斂速度慢和易早熟的問題，提出一種基于多變異個體的多目標差分進化改進算法。通過在多目標差分進化算法的個體變異及交叉操作中，引入多個變異個體，使得在高維多目標函數情況下，多目標差分進化算法種群可以更好地保持多樣性，減少種群陷入局部最優(yōu)解的可能性，從而提高該算法在高維多目標優(yōu)化問題環(huán)境下，最優(yōu)值解的搜索速度及全局最優(yōu)值解的查找能力。實驗結果表明，在高維多目標環(huán)境下，與標準多目標差分進化算法相比，該算法可以更快速地找到多個目標函數組的非劣最優(yōu)值解集。

多目標優(yōu)化問題；差分進化算法；多變異個體；計算智能；最優(yōu)值搜索；迭代速度

1 概述

差分進化[1](Differential Evolution, DE)算法作為一個具有良好性能的優(yōu)化算法[2]，在優(yōu)化領域得到廣泛的應用，具有出色的性能表現，所以已有許多學者對其進行了研究，如使用領域內的信息進行算子的改進[3]、在差分進化算法中使用采樣排序[4]、加入自適應概念[5]以及引入極大熵的概念[6]。差分進化算法的綜述還可以參考文獻[7-8]。在多目標環(huán)境下，如何提高其算法性能成為一個研究的熱點，也有不少研究者對此問題提出了改進方案，如在多目標算法中加入混沌理論對多目標差分進化算法進行分階段二次變異改進[9]、直接將混沌理論與差分進化算法結合[10]、在多目標差分進化算法中引入雙群體[11]、基于Pareto解的性質改進差分進化算法[12]及直接將差分進化算法應用于多目標問題等；利用非劣最優(yōu)值的性質對差分進化算法進行改進，從而使其能夠對于多目標問題求解[13]及使用基于非劣最優(yōu)值競爭、排序的方法改進差分進化算法，將差分進化算法應用于多目標問題[14]。對于多目標問題本身也有很多不同的探討，如文獻[15]對主要的多目標算法進行綜述和總結，文獻[16]對于多目標算法的概念、理論以及應用場景進行了綜述，文獻[17]對于多目標算法的收斂性進行了研究。

本文提出一種基于多變異個體的多目標差分進化改進算法，引入多個變異個體，在交叉操作生成實驗個體的過程中，對不同的個體引入不同交叉概率，通過多個變異個體交叉生成實驗個體。

2 標準DE、多目標問題描述及標準多目標DE

2.1 標準差分進化算法

差分進化算法是基于群體智能的進化算法，其主要的操作有變異操作、交叉操作和選擇操作，通過這3種不同操作，標準的差分進化算法[1-2]可以高效地找出函數的最優(yōu)值，其主要定義如下：

個體種群由N個獨立的個體組成，記為：

其中，N為種群數。每一個個體是一個D維向量，記為：

其中，D為問題維數。

類似于遺傳算法，需要通過差分進化算法中的變異、交叉和選擇操作對種群進行變換，從而找出最優(yōu)值點。

2.1.1 變異操作

變異操作的主要作用是對不同個體進行差分變換，從而產生新的變異個體。變異公式為：

i通過式(3)計算而得。

2.1.2 交叉操作

交叉操作的主要作用是生成的實驗個體與原個體進行交叉操作，從而生成新的變異個體。交叉操作為：

其中，rand(0,1)為(0,1)之間隨機數；CR為交叉概率，其取值在[0,1]之間；rnbr( i)是指第i個個體的向量標號。

如式(4)所示，交叉操作的本質是將變異個體與原個體在各個維度向量上以一定概率進行交叉，生成新的實驗個體ui。

2.1.3 選擇操作

選擇操作的主要作用是在個體進入下一步迭代時，在現在個體和實驗個體中選擇一個適應度較高的個體生成下一代的種群。選擇操作為：

如式(5)所示，當改進實驗個體的適應度大于原來個體適應度值，則采用改進后的實驗個體，其他情況下采用原來個體。

2.1.4 標準差分算法

標準的差分進化算法步驟如下：

步驟1初始化種群X0進入差分進化算法，確定CR，將迭代步數t設為1，同時設定最大迭代步數tmax。

步驟3調用交叉操作。通過式(4)，生成所有個體的實驗個體uit+1。

步驟4調用選擇操作。通過式(5)，判斷生成的實驗個體是否比現存?zhèn)€體的適應度高，如果適應度高于現存?zhèn)€體，則讓實驗個體uit+1代替當前個體xit；否則保留xit，進而生成下一代個體xit+1。

步驟5判斷是否達到最優(yōu)值或迭代步驟數超過最大迭代步驟數，如果是，轉向步驟6；否則轉向步驟2。

步驟6輸出最優(yōu)值點。

對于傳統(tǒng)的差分進化算法，不同學者提出了各自的改進方案，如文獻[4]通過對差分進化算法中引入粒子群算法的相關概念，從而提高算法的效率。

2.2 多目標問題描述

通常多目標問題描述如下[1]：

其中，決策向量x∈Rm；目標向量y∈Rn；fi( x)為目標函數；gi( x)為約束條件。

由式(6)可知，只有在有限條件下，才可使所有的目標函數達到最優(yōu)值，但是存在這樣的解：對于一個或多個目標函數不可能再進一步優(yōu)化，而對于其他函數不可能再劣化，這樣的解叫做非劣最優(yōu)解。非劣最優(yōu)解的定義如下[1]：

定義1若存在一個x*，使得不存在i，使得fi(x)＜fi( x*)，則稱x*是非劣最優(yōu)解。

定義2 由所有的非劣最優(yōu)解組成的集合叫做多目標非劣最優(yōu)解集。

2.3 多目標標準差分進化算法

由于標準差分進化算法只能針對于單目標問題，因此不同的研究學者對標準差分進化算法在多目標情況下進行了改進，如文獻[13]提出Pareto差分進化方法(PDEA)，可以很好地維護種群的多樣性，但是收斂速度較慢；文獻[14]提出了多目標差分進化方法(DEMO)，雖然提高了收斂速度，但是損失了種群的多樣性易陷入早熟。

本文介紹文獻[10]中多目標差分進化方法(DEMO)主要步驟，相對于標準差分進化算法，文獻[10]最大的改進在于重新定義每一個粒子的適應度函數和引入混沌理論。本文提到的標準差分進化算法中每個個體的適應度函數采用文獻[10]種群個體的排序方法，根據個體的優(yōu)劣水平和擁擠距離2個指標實現。首先找出種群中的所有非劣最優(yōu)解，其優(yōu)劣等級都取1，然后找出剩余個體中的所有非劣最優(yōu)解，其等級都取2重復進行，直到種群所有個體都具有相應的優(yōu)劣等級為止。

3 本文改進的差分進化算法

3.1 本文算法的假設及定義

本文算法的假設及定義如下：

假設1當前的最優(yōu)值點有一定的概率是全局的最優(yōu)值點，且非劣最優(yōu)解集一般在最優(yōu)值周圍可以找到。

假設2個體的每一維對于每一個目標函數值的影響相對獨立的。

假設3個體對于每一個目標函數值對于非劣最優(yōu)值的適應度值(即個體的適應度值)的影響相對獨立。

定義3當前所有的個體中對于目標函數i的最大值稱為對于目標函數i的全局最優(yōu)值，記為：

對于第j號個體，在第i個目標函數下的歷史最優(yōu)值所在的位置參數，稱為第j號個體在第i個目標函數下的歷史最優(yōu)值位置，記為：

定義4第j個個體對于第i個函數存在一個變異個體，這個變異個體由下式計算而得[4]：

其中，當前狀態(tài)下xr1，xr2，xr3是3個不同個體；F1，F2是2個縮放比例因子；pik為第k步時第i個目標函數的全局最優(yōu)值；pikj為第k步時第i個目標函數第j個粒子的局部最優(yōu)值。

定義5 對于每一個變異個體和原來的個體分配一個交叉概率，變異個體中每一維選中加入實驗個體的概率等于其交叉概率，由多個變異個體和原個體通過交叉概率，生成實驗個體，稱為多變異實驗體，記為：

其中，rd=rand(0,1)代表(0,1)之間的隨機數；cri代表交叉概率對于每一個變異個體和原個體被選擇的累計概率。對于比較重要的目標函數(即優(yōu)先度較高的目標函數)，通常需要分配更高的交叉概率值。

定義6算法迭代終止時，所有目標函數當前的平均最優(yōu)值減去所有目標函數的理論最優(yōu)值的乘積，稱為平均最優(yōu)值乘積，記為：

其中，fitk(j)為j號粒子在第k函數條件下的適應度；n為粒子群中粒子的個數；fmin是所有函數的最小值；m為獨立實驗的次數；p為目標函數的個數。

這個定義主要是為了客觀評價一個多目標算法的優(yōu)劣提供一個客觀的標準，由以上的定義可知在對于求最小值問題，如果多目標粒子群算法的乘積平均最優(yōu)值越小，則說明這個算法可以更快找到更好的優(yōu)化解。

3.2 本文算法

本文算法的迭代步驟如下：

步驟1初始化多目標差分進化算法個體，對于每一個目標函數設置一個交叉概率。

步驟2根據所有個體的狀態(tài)，按照式(7)、式(8)計算目標函數i下所有個體全局最優(yōu)值和歷史最優(yōu)值位置

步驟6判斷當前個體群是否滿足多目標條件或超過最大迭代步驟數，如果是則進入步驟7，否則進入步驟2。

步驟7輸出當前最優(yōu)點。

3.3 本文算法性質及定理證明

本文算法的性質以及定理證明如下：

定理在有足夠個體數量和迭代步驟數的條件下，變異個體找到每一個目標函數的最優(yōu)值。

證明：由于個體不同的維度對于目標函數值的影響相對獨立，因此如果當前個體進化為最優(yōu)值，其適應度函數也會相應增加，因為每一維的變異個體有一定的概率進入實驗個體，而每一個實驗個體又有一定的概率變成下一代的個體且必然優(yōu)于原先個體，第k+n步的生成個體i的第d維對于函數j的函數最優(yōu)值的影響必然優(yōu)于第k步的被選入實驗個體i的第d維對于函數j的影響，即：

本文改進的多目標差分進化算法在有足夠粒子數量和迭代步驟數的條件下，每一維對于目標函數最優(yōu)值的影響將會單調上升，又因為每一維的目標函數值單調上升，同時每一維對于目標函數值的影響相對獨立，所以本文改進的差分進化算法可以找到每一個目標函數的最優(yōu)值。

推論 在有足夠個體數量和迭代步驟數的條件下，本文的多目標差分進化算法可以有效地找到函數的非劣最優(yōu)解集。

證明：由定理可知，本文改進的多目標差分進化算法可以找到各個目標函數的全局最優(yōu)值，又因為每一個目標函數值相對獨立地影響非劣最優(yōu)值的適應度值，所以在有足夠個體數量和迭代步驟數的條件下，個體的非劣最優(yōu)值的適應度值會足夠好，從而找到全局的非劣最優(yōu)值。

由定理和推論可知，本文改進的多目標差分進化算法主要通過保證每一個目標函數的每一維的最優(yōu)值的取得進而保證單個目標函數的最優(yōu)值的取得，從而實現取得全局的多目標問題的非劣最優(yōu)值。

4 實驗結果與分析

實驗中使用5個測試函數，如表1所示，對于這5個測試函數進行兩兩組合形成10個不同的測試情況。在低維(2,2,2,2,2)和高維(2,10,5,5,10)條件下，當2個函數的維數不一致時以維數小的函數維數為準，分別對4種不同的交叉概率CR(0.1, 0.2, 0.3, 0.4)，進行10次獨立的實驗，統(tǒng)計其最小迭代步驟數、最多迭代步驟數和平均迭代步驟數。對于目標值的設定，如種群同時滿足2個測試函數達標值時，則認為這個測試函數已經找到函數的最優(yōu)解，算法結束。

在多變異個體的情況下每一個函數的交叉概率是指每一個個體的交叉概率，在標準差分進化算法的條件下，變異個體的交叉概率等于標注交叉概率的2倍。

表1展示了5個測試函數的各項參數設定，表2展示了在低維條件下本文改進粒子群算法和文獻[1]中粒子群算法迭代步驟數的比較，表3展示了在高維條件下本文改進粒子群算法和文獻[1]中粒子群算法迭代步驟數的比較。其中，SDE代表標準的多目標差分進化算法，IDE代表本文改進的多目標粒子算法。

表1 實驗測試函數

表2 低維條件下(2,2,2,2,2)5個基本函數組合改進前后的迭代步驟數比較

表3 高維條件下(2,10,5,10,5)5個基本函數組合改進前后的迭代步驟數比較

如表2所示，在低維條件下，本文改進的多目標差分進化算法和標準多目標差分進化算法都可以在較短的迭代步驟數中達到多目標問題的達標值。如表3所示，在高維條件下，標準多目標差分進化算法在部分情況下(如函數3、函數5)，在1 000步內已經很難達到達標值時，本文的差分進化算法依然可以在1 0 00步的迭代步驟數中使種群滿足達標的最優(yōu)值。

圖1、圖2展示了標準多目標差分進化算法和本文差分進化算法在不同的函數組合條件下迭代結束時，標準的多目標差分進化算法與本文中改進的多目標差分進化算法的平均最優(yōu)值乘積的比較。

圖1 低維條件下不同目標函數組合與函數平均乘積最優(yōu)值關系

圖2 高維條件下不同目標函數組合與函數平均乘積最優(yōu)值關系

圖1展示了在低維環(huán)境下，改進的多目標差分進化算法的平均最優(yōu)值乘積優(yōu)于標準多目標差分進化算法。圖2展示了在高維環(huán)境下，改進的多目標差分進化算法的平均最優(yōu)值乘積也優(yōu)于標準多目標差分進化算法，2種多目標差分進化算法之間差值變大，且標準多目標差分進化算法不能找到最優(yōu)值的目標函數組也變多。

圖3、圖4分別展示了標準多目標差分進化算法和本文差分進化算法，在不同的函數組合條件下迭代結束時，在不同交叉概率的情況下，標準多目標差分進化算法與本文改進的多目標差分進化算法的函數平均最優(yōu)值乘積的比較。

圖3 低維環(huán)境下不同交叉概率與函數平均乘積最優(yōu)值的關系

圖4 高維環(huán)境下不同交叉概率與函數平均乘積最優(yōu)值的關系

圖3展示了在低維條件下，不同交叉概率下改進的多目標差分進化算法相較于標準差分進化算法可以找到更優(yōu)的函數平均最優(yōu)值乘積。圖4展示了在高維條件下，改進的多目標差分進化算法依然可以找到比標準多目標差分進化算法更優(yōu)的函數平均最優(yōu)值乘積，且2種多目標差分進化算法之間的差值變大，在部分情況下，如交叉概率為0.3時，2種多目標差分進化算法之間的差值甚至達到1倍左右。

圖5、圖6展示了在低、高維條件下平均最優(yōu)值乘積與迭代步驟數之間的關系。其中，在圖中展示的迭代步驟數為100步。在如圖5所示的低維條件下，2個函數都可以在較短的迭代步驟數 內找到平均最優(yōu)值乘積，且在相同迭代步驟數下，改進的多目標差分進化算法可以找到更好的平均最優(yōu)值乘積。在如圖6所示的高維條件下，改進的多目標差分進化算法依然可以在相同迭代步驟數下，找到更好的函數平均最優(yōu)值乘積，并且2種多目標差分進化算法之間的差值變大。

圖5 低維環(huán)境下迭代步驟數與平均乘積最優(yōu)值之間的關系

圖6 高維環(huán)境下迭代步驟數與平均乘積最優(yōu)值之間的關系

5 結束語

本文通過引入多個不同變異個體和在交叉操作中引入多個交叉概率，提出基于多個變異個體的改進的多目標差分進化算法。通過理論推導及實驗，證明改進的多目標差分進化算法較標準多目標差分進化算法在相同迭代步驟下，可以找到更好的最優(yōu)值解。由于本文中的實驗有限，僅測試了2個目標函數組的情況，對于本文中改進的多目標差分進化算法是否可以在多個目標函數的情況下，依然保持其良好的性能，以及本文中改進的基于多變異個體的多目標差分進化算法與其他的多目標優(yōu)化算法的優(yōu)缺點的比較，則需要進一步理論論證以及實驗證明。

[1] S torn R, Price K. Differential Evolution——A S imple and Efficient He uristic f or Gl obal Optimization o ver Continuous Spaces[J]. Journal of Global Optimization, 1997, 11(1): 341-359.

[2] S torn R, Price K. Minimizing the Real Functions of the ICEC’96 Contest by Differential Evolution[C]//Proceedings of IEEE Conference on Evolutionary Computation. [S. 1.]: IEEE Press, 1996: 231-236.

[3] Chakraborty U K, Das S, Ko nar A. Dif ferential Evolution with Local Ne ighborhood[C]//Proceedings of IEEE Con ference on Evolutionary Co mputation. [S. 1.]: IEEE P ress, 2 006: 20 42-2049.

[4] 邵 梁. 基于排序采樣策略的差分演化算法[J]. 計算機工程與應用, 2012, 48(1): 49-52.

[5] 鄧澤喜, 曹敦虔, 劉曉冀, 等. 一種新的差分進化算法[J].計算機工程與應用, 2008, 44(24): 40-42.

[6] 雍龍泉, 陳 濤, 張建科. 求解互補問題的極大熵差分進化算法[J]. 計算機應用研究, 2010, 27(4): 1308-1310.

[7] 楊啟文, 蔡 亮, 薛云燦. 差分進化算法綜述[J]. 模式識別與人工智能, 2008, 21(4): 506-513.

[8] 劉 波, 王 凌, 金以慧. 差分進化算法的研究進展[J].控制與決策, 2007, 22(7): 721-729.

[9] 王筱珍, 李 鵬, 俞國燕. 分階段二次變異的多目標混沌差分進化算法[J]. 控制與決策, 2011, 26(3): 457-163.

[10] 牛大鵬, 王福利, 何大闊. 多目標混沌差分進化算法[J].控制與決策, 2009, 24(3): 261-264.

[11] 孟紅云, 張小華, 劉三陽. 用于約束多目標優(yōu)化問題的雙群體差分進化算法[J]. 計算機學報, 2008, 31(2): 228-235.

[12] Zitzler E, Thiele L. Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach[J]. IEEE Transactions on E volutionary Computation, 1999, 3(4): 257-271.

[13] Madavan N K. Multiobj ective Optimization U sing a Pareto Differential Evolution Approach[C]//Proceedings of IEEE Conference on E volutionary Computation. Piscataway, USA: IEEE Press, 2002: 1145-1150.

[14] R obic T, Filipic B. DEMO: D ifferential Evolution for Multi-objective Optimization[C]//Proceedings of EM O’05. Berlin, Germany: Springer, 2005: 520-533.

[15] 公茂果, 焦李成, 楊咚咚, 等. 進化多目標優(yōu)化算法研究[J].軟件學報, 2009, 20(2): 272-289.

[16] 謝 濤, 陳火旺, 康立山. 多目標優(yōu)化的演化算法[J]. 計算機學報, 2003, 26(8): 997-1003.

[17] 周育人, 閔華清, 許孝元, 等. 多目標演化算法的收斂性研究[J]. 計算機學報, 2004, 27(10): 1415-1421.

編輯 索書志

Improved Multi-objective Differential Evolution Algorithm Based on Multi-mutation Individuals

SHEN Jia-jie, JIANG Hong, WANG Su

(School of Information Science Technology, East China Normal University, Shanghai 200241, China)

Aiming to the problem of multi-objective Differential Evolution(DE) algorithms which have the characteristics of prematurity and slow convergence speed under high-dimensional situation, this paper prop oses an improved mul ti-objective DE algorithms based on multi-mutation samples. Through using method of introducing multi-mutation individuals into the mutation operator and crossover operator of multi-objective DE algorithm, multi-objective DE algorithm popu lations can keep diversity, reduce the possibility of falling into local optimal solution, it has guick speed for optimal solution, and the improves the ab ility finding optimal solution using shorter iteration steps than standard multi-objective differential evolution algorithm. Experimental results show that compared with standarded multi-objective DE algorithms, the improved algorithm can find optimal value effectively in high-dimensional multi-objective environment.

multi-objective optimizat ion problem; D ifferential Evolution(DE) algorithm; multi-mutation individuals; computational intelligence; optimal value searching; iteration speed

10.3969/j.issn.1000-3428.2014.05.042

國家“863”計劃基金資助項目(2013AA01A211)。

沈佳杰(1989－)，男，碩士研究生，主研方向：多目標優(yōu)化；江 紅，副教授；王 肅，講師。

2013-05-07

2013-06-03E-mail：51111211010@ecnu.cn

1000-3428(2014)05-0203-06

A

TP18