沈佳杰，江 紅，王 肅

（華東師范大學信息科學技術學院，上海200241）

0 引 言

差分進化算法（differential evolution，DE）是由D.Storn和K.Price在1995年共同提出的一個在連續(xù)空間內(nèi)啟發(fā)式搜索的隨機算法［1，2］。由于其優(yōu)良的可擴展性和對于不同的優(yōu)化問題的通用性，已經(jīng)廣泛應用到各個領域。

本文中通過引入速度概率和自適應速度值，提出了一種改進的二進制離散差分進化算法，通過理論推導改進的離散二進制差分進化算法較傳統(tǒng)的離散差分進化算法在復雜的問題環(huán)境下，可以找到更好的問題最優(yōu)解。通過對于經(jīng)典的0－1背包問題的測試，改進的離散二進制差分進化算法較標準的離散差分進化算法較明顯的改進，從而驗證了本文中提出的速度概率和自適應速度值的差分進化算法的可行性。

1 標準差分進化算法與離散差分進化算法

1.1 標準差分進化算法

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

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

其中N為種群數(shù)。

每一個個體i是一個D維向量，記為

其中D為問題維數(shù)。

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

1.1.1 變異操作

變異操作的主要作用是對于不同個體進行差分變換，從而產(chǎn)生新的變異個體。變異公式如下所示

新的變異個體Vi由3個不同的個體通過式（3）計算而得。

1.1.2 交叉操作

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

其中rand（0，1）為［0，1］之間隨機數(shù)，CR為交叉概率其取值在［0，1］之間，rnbr（i）是指第i個個體的向量標號。

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

1.1.3 選擇操作

選擇操作的主要作用是在個體進入下一步迭代時，在現(xiàn)在個體和實驗個體中選擇一個適應度較高的個體生成下一代的種群。選擇操作如下所示

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

1.2 標準差分算法步驟

標準差分算法步驟如下:

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

步驟2 調用變異操作。通過式（3），計算所有個體的變異個體

步驟3 調用交叉操作。通過式（4），生成所有個體的實驗個體

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

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

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

由于標準的差分進化算法主要是處理連續(xù)優(yōu)化問題，不同的學者對標準的差分進化算法進行了改進以適應離散的優(yōu)化問題的環(huán)境，如文獻［3］通加入了貪心機制、文獻［4］通過改進編碼方式將差分進化算法應用到離散問題中，而對于進化算法本身的改進，如在差分進化算法中加入不同的機制［5，6］以及改進差分進化算法的算子［7，8］。于此同時，也有不少的文獻也對于差分進化算法的研究現(xiàn)狀進行了總結［9，10］，同時對于進化算法對于多目標問題的適用性也有許多文獻進行了討論，如文獻［11］主要對于多目標收斂性進行了討論，文獻［12，13］主要對于主要對于多目標問題的描述和主要的進化解決算法進行了描述。下面我們主要介紹一種離散二進制的差分進化算法。

1.3 標準的離散二進制差分進化算法介紹

由于標準的差分進化算法，對于連續(xù)問題進行求解，所以已經(jīng)有了許多的文獻對于如何將差分進化算法應用離散問題進行討論［3，4］。

這里我們主要介紹文獻［3］中的離散差分進化算法。其與標準的差分進化算法的主要差別是將變異算子改進成如下公式

文獻［3］中的二進制差分進化算法步驟數(shù)如下:

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

步驟6 判斷是否已經(jīng)達到最優(yōu)值或迭代步驟數(shù)是已經(jīng)超過最大迭代步驟數(shù)，如果是，轉向步驟7；否則轉向步驟2。

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

2 改進差分進化算法定義、步驟和性質

2.1 改進差分進化算法假設以及定義

本文中的算法的假設以及定義如下:

假設1:局部最優(yōu)值的鄰域內(nèi)出現(xiàn)全局最優(yōu)值的概率大于不是局部最優(yōu)值點出現(xiàn)全局最優(yōu)值的概率。

假設2:算法找到全局的最優(yōu)值點可能需要不止一步迭代步驟。

假設3:在迭代步驟的過程中個體的適應度可能下降，且隨著離散問題的擴大離散問題的局部最優(yōu)解會增多。

定義1 對于每一個粒子點軌跡最優(yōu)值點存在一個最優(yōu)值向量，記為

定義2 對于每一個粒子的每一維為存在一個速度值，這個速度值與迭代的步驟數(shù)成正比，稱為自適應速度值，記為

由以上的定義可知，如果當?shù)趇粒子的第k維為0時，以上函數(shù)為正，而當?shù)趇粒子的第k維為1時，以上函數(shù)為負，所以式（8）可以變形為

本文中的改進的變異算子是由定義1和定義2疊加組成，其變異個體的生成公式如下所示

其中ki為縮放比例因子，為第t步時第r1個個體的位置、為第t步時第r2個個體的個體、為當前粒子的位置、為xid的取反、rd為一個［0，1］之間的隨機數(shù)。

定義3 當實驗個體優(yōu)于原個體時，有一定的較小的概率選擇原個體，而較大的概率選擇實驗個體，而當原個體優(yōu)于實驗個體時，有一定的較小的概率選擇實驗個體，而較大的概率選擇原個體的選擇算子，稱為概率選擇算子，記為

其中rd為一個（0，1）之間的隨機數(shù)，thmax為［0，1］之間的一個數(shù)，thmin為［0，1］之間的一個數(shù)，thmax＋thmin＝1，thmax＞＞thmin。

2.2 改進差分進化算法步驟

本文中算法步驟如下:

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

步驟3 根據(jù)式（10）以及式（11），調用變異算子，計算速度概率以及變異個體。

步驟5 根據(jù)式（12），調用概率選擇操作，比較生成的實驗個體與原來個體，選擇較優(yōu)者生成下一代的個體。

步驟6 判斷是否已經(jīng)達到最優(yōu)值或迭代步驟數(shù)是已經(jīng)超過最大迭代步驟數(shù)，如果是，轉向步驟7；否則轉向步驟2。

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

2.3 改進差分進化算法的性質以及定理證明

本文中算法的性質以及定理證明:

定理1 如果所有的都在一步之內(nèi)實驗個體都不優(yōu)于原個體的情況下，標準的離散差分進化算法將很難找到最優(yōu)值點。

證明:

由于在標準的離散差分進化算法中，最后的選擇算子，會比較實驗個體與原個體并選擇適應度較高的個體，如果所有的實驗個體的適應值都小于原來的，則用于進化的實驗個體將不會替換原來的個體，即陷入局部最優(yōu)值，所以標準的離散差分進化算法將很難找到最優(yōu)值點。

定理1說明標準的離散差分進化算法，如果個體種群生成的實驗個體如果都小于，則算法會陷入局部最優(yōu)解，這在一定的程度限制了標準的離散差分進化算法在高維環(huán)境下，找到全局最優(yōu)解的能力。

推論1:如果問題規(guī)模過大的情況下，標準的離散差分進化算法已陷入早熟將很難找到全局最優(yōu)值。

證明:

因為隨著問題規(guī)模的變大，離散問題的局部解將增多，所以當所有的個體都陷入局部最優(yōu)解的情況下，生成實驗個體極可能小于原個體，而在這種情況下，算法將維持原始個體，即沒有個體更新，因此標準的離散差分進化算法已陷入早熟將很難找到全局最優(yōu)值。

定理2 本文改進的離散二進制差分進化算法，在所有的實驗個體都不優(yōu)于原個體的情況下，依然可以繼續(xù)搜索全局最優(yōu)值。

證明:

由于改進的離散二進制差分進化算法中的概率選擇算子，有一定的概率選擇適應度較差的個體，所以即使實驗個體的適應度小于原個體的適應度，本文改進的概率選擇算子依然又會有一定的概率選擇適應度較差的實驗個體以保證算法對于最優(yōu)值搜索的進行。

由定理2可知，即使是在實驗個體都不優(yōu)于原先個體的情況下，依然可以繼續(xù)進行全局最優(yōu)值搜索，所以本文中離散二進制差分進化算法可以持續(xù)的進行最優(yōu)值搜索。

推論2:改進的離散二進制差分進化算法，當個體數(shù)量和迭代步驟數(shù)足夠的情況下，改進的離散二進制差分進化算法可以找到較好的全局最優(yōu)值。

證明:

由于本文中的的離散二進制差分進化算法由于引入了概率選擇算子，所以在個體陷入局部最優(yōu)值的情況下，依然可以在一定的概率下，選擇適應度較差的實驗個體，所以算法容易跳出局部最優(yōu)值，因此本文中的改進的離散二進制差分進化算法，當個體數(shù)量和迭代步驟數(shù)足夠的情況下，可以找到較好的全局最優(yōu)值。

3 實 驗

本文中使用經(jīng)典的0－1背包問題進行測試［5］，本文對于物品數(shù)為10、20、50、60、100、500、1000八種不同的測試問題，在交叉概率為0.9、0.8、0.7、0.6這4種不同的條件下，分別進行10次獨立的實驗，表1中展示了本文中的4個測試用例，其中5－8問題用例中的數(shù)據(jù)隨機生成。表2中主要展示了在不同問題用例下，標準的離散二進制優(yōu)化算法和本文中改進的離散二進制算法的10次算法迭代中的所找到最優(yōu)解，平均解和最差解以及各個不同的最優(yōu)解之間的方差以及找到最優(yōu)解時，二進制離散差分算法經(jīng)過的最小、最大和平均的迭代步驟數(shù)。

其中SDE表示標準的離散粒子群算法，IDE表示本文中改進的離散二進制粒子群算法。

由表2可知，改進的離散二進制差分進化算法較標準的離散差分進化算法，在問題規(guī)模比較小的情況下（如問題實例1），標準的離散差分進化算法和本文中離散二進制差分進化算法都可以找到較好的最優(yōu)值，而當問題規(guī)模較大時（如問題實例5－8），改進的離散二進制差分進化算法較標準的離散差分進化算法在最優(yōu)值和標準方差穩(wěn)定性方面具有一定的優(yōu)勢，在部分問題實例中（如問題5）最優(yōu)值的差距接近于一倍。

圖1（a）主要展示了在算法迭代終止時，不同的問題規(guī)模與算法找到的平均最優(yōu)值之間的關系，圖1（b）中主要展示了在算法迭代終止時，不同的交叉概率的條件下，不同的交叉概率與算法找到的平均最優(yōu)值之間的關系。

表1 本文中實驗中測試用例

表2 標準的離散二進制差分進化算法和本文中改進的離散二進制差分進化算法性能對比

SDE 2 20 0.9 1016 855 957.8 5 723 153.2 57.71539 0.8 1024 915 972.6 3 620 132.4 40.73819 0.7 1018 910 971.6 4 362 105.5 29.38329 0.6 1024 940 1000 14 678 229 28.61623 IDE 0.9 1024 1024 1024 14 33 25.4 0 0.8 1024 1024 1024 11 42 24.5 0 0.7 1024 1024 1024 10 51 22.6 0 0.6 1024 1024 1024 11 50 20.7 0 SDE 3 50 0.9 3006 2855 2936.7 49 779 430.5 43.10465 0.8 3004 2885 2934.6 142 956 575.6 32.73191 0.7 3015 2911 2963.7 84 943 580.2 32.28364 0.6 2987 2917 2952.3 107 955 407.1 20.14972 IDE 0.9 3098 3071 3087.7 93 897 354.1 7.04036 0.8 3103 3084 3093 153 620 281.5 5.291503 0.7 3096 3070 3086.3 158 970 398.1 8.340663 0.6 3097 3076 3089.6 215 624 319.5 6.221825 SDE 4 60 0.9 7914 6400 7149.4 3 490 145 608.2869 0.8 7916 7012 7447.5 3 343 89.6 287.5804 0.7 7959 6890 7396.7 2 220 40.7 362.5502 0.6 7839 7173 7545.2 5 712 159 254.933 IDE 0.9 8362 8354 8359.8 97 452 153.8 3.583915 0.8 8362 8344 8356.6 114 174 148.7 5.738757 0.7 8362 8354 8360 98 228 165.3 3.265986 0.6 8362 8354 8358 142 225 169.7 3.527668 SDE 5 100 0.9 5394 713 3369.5 7 26 14.5 1454.455 0.8 5654 2068 4373.5 2 34 16.8 1273.546 0.7 6855 3691 5041.5 8 50 25.4 1028.763 0.6 6598 3326 4926.4 3 70 29.8 1103.259 IDE 0.9 10502 10091 10256.4 185 374 255.9 127.1807 0.8 10490 9792 10071 208 548 346.3 226.2511 0.7 10129 8840 9728.8 144 343 232.9 362.696 0.6 9974 8999 9441.9 178 387 277.7 300.0305 SDE 6 200 0.9 24076 20968 22480.8 123 993 569.2 770.8438 0.8 23826 22123 22969.8 29 982 420.4 519.5534 0.7 23596 22770 23114.9 400 994 720.5 302.0873 0.6 24796 22736 23567.3 124 980 539.1 569.758 IDE 0.9 30488 29837 30157.4 410 994 715.2 195.8294 0.8 30420 30117 30227.1 535 992 778 90.94253 0.7 30132 29624 30027.4 648 987 809.8 151.4891 0.6 30419 29244 29891.7 504 931 713.9 339.7175 SDE 7 500 0.9 33750 28506 31500.9 1 138 42.4 1723.221 0.8 33194 29644 31457.2 1 105 20.3 1088.771 0.7 33798 28428 31362.5 1 134 30.7 1640.353 0.6 36657 28726 32200.3 1 178 40.8 2509.981 IDE 0.9 53152 49793 51774.5 417 940 619.9 1043.984 0.8 50265 48049 49018.1 309 506 397.2 868.6936 0.7 48489 41765 45598.5 171 443 318.3 2205.574 0.6 45096 40719 42920.5 108 464 256.3 1440.184 SDE 8 1000 0.9 35564 6079 28177.4 3 28 11.3 9625.978 0.8 40030 30536 35194.8 4 149 40.3 2747.1 0.7 42518 27695 35712.8 10 247 74.8 3816.219 0.6 41995 24885 35128.9 8 268 58.6 4260.846 IDE 0.9 59411 44256 53365.8 133 504 360.4 4130.141 0.8 52247 43864 47340.1 148 425 247.5 3432.584 0.7 45719 38008 41860 23 335 152.4 2724.898 0.6 41011 36177 38429.3 10 92 33.6 1552.747

圖1 迭代終止時，差分進化算法平均最優(yōu)值的對比

如圖1（a）可知，在問題規(guī)模較小時，標準的離散差分進化算法和改進的離散二進制差分進化算法都可以在算法迭代終止時找到比較好的最優(yōu)值，而當問題規(guī)模比較大的情況下（問題實例5－8），改進的差分進化算法較標準的差分進化算法有較大的優(yōu)勢，在問題實例7、8中本文中的差分進化算法找到的最優(yōu)值與標準的差分進化算法的最優(yōu)值差距達到了近一倍。如圖1（b）所示在不同交叉概率的條件下，改進的離散二進制差分進化算法比標準的離散差分進化算法更好的平均最優(yōu)值。

圖2主要展示了在部分問題實例中，標準的離散二進制差分進化算法和改進離散二進制差分進化算法迭代步驟數(shù)與算法所能找到平均最優(yōu)值之間的關系:

如圖2所示，在問題規(guī)模較小的情況下，改進的離散二進制差分進化算法與標準的離散差分進化算法都可以找到幾乎相同的平均最優(yōu)值，如圖2（a）中標準的離散差分進化算法和本改進的離散二進制差分進化算法都可以在算法迭代的過程中找到較好的平均最優(yōu)值，隨著問題規(guī)模的擴大（如圖2（b）－（d）），改進的離散二進制差分進化算法和標準的離散差分進化算法相同的迭代步驟數(shù)中，可以找到更好的最優(yōu)值而平均最優(yōu)值之間的差距逐步擴大，如圖2（c）（d）中，當本文中的改進的離散二進制差分進化算法與標準的離散差分進化算法算法收斂時，兩者之間的差距達到了將近一倍。

圖2 算法迭代步驟數(shù)與平均最優(yōu)值之間的關系

4 結束語

本文中通過速度概率和自適應速度值，提出了一個改進的差分進化算法，通過理論推導和實驗證明改進的離散二進制差分進化算法較傳統(tǒng)離散差分進化算法在問題規(guī)模較大時，可以在相同的優(yōu)化條件下取得更好的最優(yōu)化結果。

本文中雖然提出了一個改進的離散二進制差分進化算法并進行了理論證明以及實驗驗證，但是由于實驗有限是否可以找到一種不同的實驗問題條件下，通用的離散二進制差分進化算法，依然是一個值得研究的問題。

［1］Storn R，PRICE K.Differential evolution－a simple and efficient heuristic for global optimization over continuous spaces［J］.Journal of Global Optimization，1997（11）:341－359.

［2］Storn R，Price K.Minimizing the real functions of the ICEC＇96 contest by differential evolution［C］//Evolutionary Computation，1996.

［3］MIAO Shiqing，GAO Yuelin.Discrete differential evolution algorithm for solving 0/1 knapsack problem［J］.Journal of Chinese Computer Systems，2009，30（9）:1828－1830（in Chinese）.［苗世清，高岳林.求解0/1背包問題的離散差分進化算法［J］.小型微型計算機系統(tǒng)，2009，30（9）:1828－1830.］

［4］HE Yichao，WANG Xizhao，KOU Yingzhan.A binary differential evolution algorithm with hybrid encoding［J］.Journal of Computer Research and Development，2007，44（9）:1476－1484（in Chinese）.［賀毅朝，王熙照，寇應展.一種具有混合編碼的二進制差分演化算法［J］.計算機研究與發(fā)展，2007，44（9）:1476－1484.］

［5］WU Lianghong，WANG Yaonan，YUAN Xiaofang，et al.Differential evolution algorithm with adaptive second mutation［J］.Control and Decision，2006，21（8）:898－902（in Chinese）.［吳亮紅，王耀南，袁小芳，等.自適應二次變異差分進化算法［J］.控制與決策，2006，21（8）:898－902.］

［6］SHAO Liang.Differential evolution algorithm based on indivi－dual ordering and sampling［J］.Computer Engineering and Application，2012，48（1）:49－52（in Chinese）.［邵梁.基于排序采樣策略的差分演化算法［J］.計算機工程與應用，2012，48（1）:49－52.］

［7］Epitropakis M G，Pavlidis N G，Plagianakos V P，et al.Enhancing differential evolution utilizing proximity－based mutation operators［J］.Evolutionary Computation，2011，15（1）:99－119.

［8］Zaharie D.Influence of crossover on the behavior of differential evolution algorithms［J］.Applied Soft Computing，2009，9（3）:1126－1138.

［9］YANG Qiwen，CAI Liang，XUE Yuncan.A survey of differential evolution algorithms［J］.Pattern Recognition and Artificial Intelligence，2008，21（4）:506－513（in Chinese）.［楊啟文，蔡亮，薛云燦.差分進化算法綜述［J］.模式識別與人工智能，2008，21（4）:506－513.］

［10］LIU Bo，WANG Ling，JIN Yihui.Advances in differential evolution［J］.Control and Decision，2007，22（7）:721－729（in Chinese）.［劉波，王凌，金以慧.差分進化算法研究進展［J］.控制與決策，2007，22（7）:721－729.］

［11］ZHOU Yuren，MIN Huaqin，XU Xiaoyuan，et al.A multi－objective evolutionary algorithm and its convergence［J］.Chinese Journal of Computer，2004，27（10）:1415－1421（in Chinese）.［周育人，閔華清，許孝元，等.多目標演化算法的收斂性研究［J］.計算機學報，2004，27（10）:1415－1421.］［12］XIE Tao，CHEN Huowang，KANG Lishan.Evolutionary algorithms of multi－objective optimization problems［J］.Chinese Journal of Computer，2003，26（8）:997－100（in Chinese）.［謝濤，陳火旺，康立山.多目標優(yōu)化的演化算法［J］.計算機學報，2003，26（8）:997－100.］

［13］GONG Maoguo，JIAO Licheng，YANG Dongdong，et al.Research on evolutionary multi－objective optimization algorithms［J］.Journal of Software，2009，20（2）:271－289（in Chinese）.［公茂果，焦李成，楊咚咚，等.進化多目標優(yōu)化算法研究［J］.軟件學報，2009，20（2）:272－289.］