付玉珍，周潔文，邵龍秋，張 慧

(1.茂名職業(yè)技術學院計算機工程系，廣東 茂名 525000;2.廣東省石化裝備故障診斷重點實驗室，廣東 茂名 525000)

1 約束優(yōu)化問題數(shù)學描述

不失一般性，以最小化問題為例，約束優(yōu)化問題可描述為:

其中:x=(x1，x2，…，xn)是一個n 維向量，f(x)為目標函數(shù)，gi(x)≤0 和hi(x)=0 分別為q 個不等式約束和m-q 個等式約束，函數(shù)f(x)、gi(x)和hi(x)可以是線性和非線性實值函數(shù)，li和ui分別是決策變量xi取值的下界和上界。若搜索空間記作S，滿足所有約束條件的可行解空間為F=，則有F?S。若x 滿足所有的約束，則稱其為一個可行解;若x 至少違反了一個約束，則稱其為不可行解。約束優(yōu)化問題就是在F 空間內搜尋使目標函數(shù)達到最小值的解。

2 傳統(tǒng)差分算法及其相關的改進算法

差分算法由Storn 和Price［1］于1995 年提出，它通過群體內個體間的合作與競爭產(chǎn)生群體智能指導優(yōu)化搜索，具有記憶個體最優(yōu)解和種群內信息共享的特點，采用實數(shù)編碼?；诓罘值暮唵巫儺惒僮骱鸵粚σ坏母偁幧娌呗?，使得算法遺傳操作簡單且具有較強的全局收斂能力和魯棒性。由于差分算法這種簡單高效的特性，差分算法已成功應用到眾多領域，其中將差分算法用于求解約束優(yōu)化問題的研究主要集中在算法搜索能力的提高與約束處理技術的使用。近十幾年以來很多改進的差分算法相繼被提出用于改進算法的搜索性能，如文獻［2］采用父代個體產(chǎn)生多個子代個體，從多個子代個體當中選擇一個最優(yōu)個體進入下一代來提高算法的搜索性能，但所有父代個體產(chǎn)生相同多的子代個體，并未考慮個體之間的優(yōu)劣。文獻［3］提出一種自適應差分算法，引入一種衰老機制，當算法陷入局部最優(yōu)的時候重新生成個體替換衰老的個體。文獻［4-5］提出基于ε 水平比較的差分算法，該方法在可行域比較小的情況下可以顯著減少評估次數(shù)，但其收斂精度和魯棒性還需進一步提高。文獻［6］指出有效的變異策略和合適的參數(shù)設置可以顯著提高差分算法的性能，但如何選擇變異策略和合適的參數(shù)需要進一步研究。文獻［7］通過自適應調節(jié)縮放因子和交叉率來搜索最優(yōu)解。進化算法求解約束優(yōu)化問題能力除了與進化算法自身有關外，還與所采用的約束處理技術密切相關，文獻［8］采用改進算法的同時，構造了一種個體比較準則，引導搜索過程更好地向最優(yōu)解靠近。可以看出如何提高算法的搜索性引起了廣泛研究，本文在文獻［9］所提COMDE 算法的基礎上加入擇優(yōu)策略和克隆策略，使其快速定位到最優(yōu)解區(qū)域的同時提高求解精度，提高原算法的搜索性能。

3 本文提出的算法

通過分析，算法首先要搜索到可行域，然后在可行域中找到最優(yōu)解，本文算法(PLMIDE)通過擇優(yōu)學習策略在搜索空間內快速找到可行域，通過克隆策略在可行域的最優(yōu)解區(qū)域展開更詳盡的搜索，最終找到最優(yōu)解。

3.1 約束處理機制及比較規(guī)則

差分算法是一種無約束的搜索技術，用于求解約束問題需結合某種約束處理機制，常用的約束處理技術有:懲罰函數(shù)法［10］、Deb 準則［11］、隨機排序法［12］、多目標法［13］和ε 約束［14］等。本文算法采用的約束處理方法為區(qū)分可行解和不可行解的多目標法，首先將等式約束條件轉換為不等式約束條件|hk(xi)| -ε＜0，等式約束條件的容忍因子ε 是一個非常小的大于0 的實數(shù)，cv(xi)為個體i 的違約函數(shù)值，其反映了個體xi的不可行性。

采用Deb 的比較準則:1)可行解總是優(yōu)于不可行解;2)若2 個解均可行，則目標函數(shù)值小的解為優(yōu)(以求最小值為例);3)若2 個解均不可行，則約束違反程度小的解為優(yōu);如式(7)所示，其中f 為目標函數(shù)值。

通過以上比較準則可以對群體做一個排序。

3.2 擇優(yōu)學習策略［15］

根據(jù)比較準則排好序的群體中，排在個體i 前面的個體都是比其優(yōu)秀的個體，這些優(yōu)秀個體可以指導個體i 的學習，則第i 個個體有i -1 個個體可以用來選擇參與進個體i 的變異。擇優(yōu)學習策略如圖1 所示。

圖1 擇優(yōu)學習策略

r1、r2、r3、r4的取值為:

其中:i 表示第i 個個體，j 表示第i 個個體的第j 維分量，G 表示個體進化到第G 代，r1、r2、r3、r4標識群體中的不同個體，F(xiàn)0、F1、F2是縮放因子。i ＞4 是為了保證DE 有足夠多個體用于個體i 的變異操作，jrand∈［1，d］，其中d 為個體的維數(shù)，用于保證個體每次至少有一位變異。

在眾多的變異算子中，DE/best/1/bin 和DE/rand-to-best/1/bin 被證明效果優(yōu)于其他變異算子［16］，將擇優(yōu)學習策略應用到這2 種變異算子中，在進化初期側重變異算子2，隨著進化過程選擇使用變異算子1 的概率增加，進化后期2 種變異算子趨于平衡，這種擇優(yōu)學習的混合變異算子可以提高變異的有效性，加快個體向最優(yōu)解靠近，最終提高算法的收斂速度。

3.3 克隆策略

為了增加群體的多樣性，如文獻［2］所述，父代個體不再是產(chǎn)生一個子代個體，每個父代個體產(chǎn)生nc 個子代個體，從nc 個子代個體中選擇最優(yōu)個體進入下一代，克隆操作有效地擴展了搜索空間，但是文獻［2］中nc 選擇某固定值，本文根據(jù)父代個體在群體中的排名，動態(tài)生成nc 個子代個體，ncβ·」，β 為克隆倍數(shù)，本文取值為1，r 為個體在群體中的排名，NP 為群體數(shù)目，該策略可以保持群體多樣性的同時加大對優(yōu)秀個體所在區(qū)域的搜索。

3.4 算法相關參數(shù)設置

算法中涉及的參數(shù)采用自適應方式產(chǎn)生，算法中相關參數(shù)有容忍因子ε，縮放參數(shù)F0、F1、F2，變異選擇概率Pf，種群個數(shù)NP。

1)等式約束條件的容忍因子ε，通常ε 取值為0.000 1，本文隨迭代次數(shù)自適應地調整，根據(jù)文獻［4］，修改為ε=0.0001·，0 ＜G ＜Gmax。

2)因使用了混合變異策略，變異選擇概率Pf隨迭代次數(shù)變化，主要用于權衡群體的全局搜索和局部搜索，開始側重變異策略2，隨著迭代次數(shù)的增加，Pf的值越來越大，算法側重混合策略的變異，防止群體陷入局部最優(yōu)。Pf=0.5-Math.pow(1 -G/Gmax，4)。

3)縮放因子F0、F1、F2決定了差分向量的縮放比例，本文參數(shù)取值見表1，為了增大最優(yōu)解的導向作用，取F1＞F2。

表1 縮放因子取值

3.5 算法偽代碼

4 對比實驗及結果分析

4.1 比較測試實驗

CEC2006 中有24 個測試函數(shù)，函數(shù)g20 沒有可行解，函數(shù)g22 很難找到可行解［9］，故本文算法重點對其余22 個測試函數(shù)進行測試，算法評估次數(shù)為5×104次，每個函數(shù)獨立運行25 次，實驗結果見表2，表2 中的性能指標包括最好結果、中間結果、平均結果、最差結果和解的標準方差，分別與COMDE 算法［9］作對比。1 表示本文算法(PLMIDE)，2 表示COMDE 算法。表2 中黑體為最優(yōu)解。

表2 PLMIDE 算法(1)與COMDE 算法(2)實驗結果對比

4.2 實驗結果分析

實驗數(shù)據(jù)驗證了本文算法除了約束性很強的2個函數(shù)g20 和g22 以外，都成功地找到了最優(yōu)解，對大部分函數(shù)效果非常好，求解精度也很高，特別是函數(shù)g3、g5、g7、g8、g10、g14、g15、g16、g18、g21、g23、g24取得了比筆者所了解到的最優(yōu)解更優(yōu)解，函數(shù)g2 因其目標函數(shù)維數(shù)較高且拓撲結構非常復雜可以用來考察進化算法的搜索能力［17］，從數(shù)據(jù)對比可以看出，本文算法確實比COMDE 算法有更好的搜索能力。從算法標準差對比中，本文算法普遍小于COMDE 算法，說明收斂精度更高，魯棒性也更好。

5 結束語

本文提出了一種新的結合擇優(yōu)學習的混合變異策略和克隆策略的多個體差分算法，利用擇優(yōu)學習來實現(xiàn)對解空間的快速搜索，這種擇優(yōu)學習策略，具有快速找到可行解區(qū)域，且能夠加快算法的收斂速度的能力。而使用克隆策略擴展搜索空間，可以使群體在最優(yōu)解區(qū)域更加詳盡地搜索，向最優(yōu)解逼近，提高了算法的求解精度，通過實驗驗證，結果表明，本文算法在進化初期就能夠快速定位到可行域中的最優(yōu)解區(qū)域，后期通過克隆策略提高了求解精度，最終使得算法在求解效率和求解精度上都有較好表現(xiàn)，筆者下一步工作主要是研究其他搜索算法和約束處理技術用來提高本文算法的性能，以及嘗試將本文算法擴展到求解多目標約束優(yōu)化問題中。

［1］Storn R，Price K.Differential Evolution:A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces［R］.TR-95-012，Berkeley:University of California，1995.

［2］Mezura-Montes E，Velázquez-Reyes J，Coello Coello C A.Modified differential evolution for constrained optimization［C］// Proceedings of the 2006 IEEE Congress on Evolutionary Computation.2006:25-32.

［3］Brest J，Bo?kovi B，Zumer V.An improved self-adaptive differential evolution algorithm in single objective constrained real-parameter optimization［C］// Proceedings of the 2010 IEEE Congress on Evolutionary Computation.2010:1073-1080.

［4］Takahama T，Sakai S.Constrained optimization by the ε constrained differential evolution with an archive and gradient-based mutation［C］// Proceedings of the 2010 IEEE Congress on Evolutionary Computation.2010:1680-1688.

［5］Takahama T，Sakai S.Efficient constrained optimization by the ε constrained differential evolution with rough approximation using kernel regression［C］// Proceedings of the 2013 IEEE Congress on Evolutionary Computation.2013:1334-1341.

［6］Wang Yong，Cai Zixing，Zhang Qingfu.Differential evolution with composite trial vector generation strategies and control parameters［J］.IEEE Transactions on Evolutionary Computation，2011，15(1):55-66.

［7］Zou Dexuan，Liu Haikuan，Gao Liqun，et al.A novel modified differential evolution algorithm for constrained optimization problems［J］.Computers ＆ Mathematics with Applications，2011，61(6):1608-1623.

［8］鄭建國，王翔，劉榮輝.求解約束優(yōu)化問題εDE 算法［J］.軟件學報，2012，23(9):2374-2387.

［9］Mohamed A W，Sabry H Z.Constrained optimization based on modified differential evolution algorithm［J］.Information Sciences，2012，194:171-208.

［10］Datta R，Deb K.Individual penalty based constraint handling using a hybrid bi-objective and penalty function approach［C］// Proceedings of the 2013 IEEE Congress on Evolutionary Computation.2013:2720-2727.

［11］Mezura-Montes E，Coello Coello C A.Constraint-handling in nature-inspired numerical optimization:Past，present and future［J］.Swarm and Evolutionary Computation，2011，1(4):173-194.

［12］Runarsson T P，Yao Xin.Search biases in constrained evolutionary optimization［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part C:Applications and Reviews，2005，35(2):233-243.

［13］Long Qiang.A constraint handling technique for constrained multi-objective genetic algorithm［J］.Swarm and Evolutionary Computation，2014，15:66-79.

［14］Takahama T，Sakai S.Constrained optimization by the ε constrained differential evolution with gradient-based mutation and feasible elites［C］// Proceedings of the 2006 IEEE Congress on Evolutionary Computation.2006:308-315.

［15］Cheng Ran，Jin Yaochu.A social learning particle swarm optimization algorithm for scalable optimization［J］.Information Sciences，2015，291:43-60.

［16］Mezura-Montes E，Velázquez-Reyes J，Coello Coello C A.A comparative study of differential evolution variants for global optimization［C］// Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation.2006:485-492.

［17］王勇，蔡自興，周育人，等.約束優(yōu)化進化算法［J］.軟件學報，2009，20(1):11-29.