雙種群分子動理論優(yōu)化算法*

范朝冬,任 柯,易靈芝,肖樂意，朱彪明,李 杰

(1.湘潭大學信息工程學院,湖南 湘潭 411105; 2.湖南大學電氣與信息工程學院,湖南 長沙 410082)

1 引言

在目前的全局優(yōu)化算法中，啟發(fā)式算法因實現(xiàn)簡單且效率高而逐漸成為國內外學者研究的熱點。當前主流的啟發(fā)式算法主要可分為三大類：(1)模擬自然進化規(guī)律的優(yōu)化算法，如遺傳算法GA(Genetic Algorithm)[1]、進化策略ES(Evolutionary Strategy)[2]等；(2)模擬生物群體的生活習性與活動規(guī)律的優(yōu)化算法，如微粒群優(yōu)化PSO(Particle Swarm Optimization)算法[3]、人工蜂群ABC(Artificial Bee Colony)算法[4]、螢火蟲GSO(Glowworm Swarm Optimization)算法[5]等；(3)模擬物理現(xiàn)象或物理規(guī)律的優(yōu)化算法，如中心引力CFO(Central Force Optimization)算法[6]、萬有引力算法GSA(Gravitational Search Algorithm)[7]、人工物理優(yōu)化APO(Artificial Physics Optimization)算法[8]等。其中,基于物理規(guī)律的優(yōu)化算法因模型規(guī)范且尋優(yōu)效果好，已逐漸成為智能優(yōu)化領域的研究熱點[9]。

2013年，筆者通過模擬分子運動機制提出了分子動理論優(yōu)化算法MKTOA(Molecular Kinetic Theory Optimization Algorithm)[10]，因該算法同時考慮了個體間的吸引和排斥作用，所以取得了較好的優(yōu)化效果；2014年，筆者進一步將其應用于圖像閾值分割問題，通過搜索最優(yōu)閾值取得了理想的分割效果[11,12]；2015年，為避免MKTOA發(fā)生錯誤引導而影響算法效率，筆者提出了M精英協(xié)同進化分子動理論優(yōu)化算法MECMKTOA(M-Elite Coevolutionary MKTOA)[9]。雖然當前對MKTOA的研究已取得一定進展，但因其研究才剛剛起步，各方面還不夠完善，局部極值和收斂精度等問題仍有待解決。

針對MKTOA的上述問題，本文提出了一種雙種群分子動理論優(yōu)化算法DP-MKTOA(Dual Population of Molecular Kinetic Theory Optimization Algorithm)。該算法將種群分為精英和普通兩個子群，普通子群執(zhí)行MKTOA的搜索過程進行大范圍搜索，而精英子群則通過協(xié)同學習而實現(xiàn)局部搜索；在迭代過程中，分別采用模擬退火個體更新策略和多樣性監(jiān)測波動算子，以免個體移動隨機性過大并增強算法全局搜索能力，函數(shù)實驗測試驗證了DP-MKTOA的有效性。

2 傳統(tǒng)分子動理論優(yōu)化算法

在MKTOA中，每個分子在不同的位置上得到不同目標函數(shù)值，表示為個體的適應度值。分子運動的規(guī)律就是種群的搜索策略。分子間存在的相互作用力有引力、斥力以及不受力的情況。通過這種相互作用力所建立的搜索策略來搜索目標函數(shù)的最優(yōu)解。

吸引算子計算公式為:

ifrand

(1)

ai=Fi/Mi=GMBest(XBest-Xi)

(2)

排斥算子計算公式為:

ifPAttraction

Fi=-GMiMBest(XBest-Xi)

(3)

ai=Fi/Mi=-GMBest(XBest-Xi)

(4)

熱運動算子計算公式為:

if 1-PFluctuation

(5)

其中,rand為0～1的隨機數(shù)，PAttraction表示分子所受合力為引力的概率，PElimination為分子所受合力為斥力的概率，PFluctuation代表分子不受力的概率(PAttraction+PElimination+PFluctuation=1)，Mi、MBest分別為分子Xi和最優(yōu)個體XBest的質量，Xi表示第i個分子的位置。根據(jù)牛頓第二定理，Xi的加速度計算公式分別如式(2)、式(4)、式(5)所示，其中aij為個體i的j維加速度，pc∈[0,1]為變異率，本文取pc=0.05。Xmaxj、Xminj分別為解空間的第j維的上、下界，A為振動幅度，N(0,1)為服從正態(tài)分布的隨機數(shù),Prand為0～1的隨機數(shù)。

3 雙種群分子動理論優(yōu)化算法

由于MKTOA中個體只受到當前最優(yōu)個體引導，故算法易陷入局部極值。對此，本文引入雙種群思想，首先按適應度順序將群體分為精英和普通兩個子種群；然后兩子群分別按不同的搜索策略進行搜索，并通過信息交流共同完成尋優(yōu)過程。

3.1 普通種群搜索過程

對于普通種群，執(zhí)行MKTOA搜索行為而進行隨機化搜索，其具體過程如前所述。因MKTOA易陷入局部極值，而種群多樣性的保持有助于增強算法全局搜索能力。對此，為實現(xiàn)大范圍搜索，本文通過監(jiān)測種群多樣性，充分利用多樣性信息調節(jié)變異率，設計了一種基于種群多樣性監(jiān)測的波動算子:

if 1-PFluctuation

(6)

3.2 精英種群搜索過程

因為精英都是優(yōu)良的候選解，在大范圍移動中容易破壞候選解。對此，本文設計如下的精英學習算子，以便精英間協(xié)同學習而實現(xiàn)精細化搜索，其定義如式(7)所示：

ui,k=Xi,k+(Xj,k-Xi,k)N(0,1),k=1,2,…,D

(7)

其中：Xi,k(不為最優(yōu)個體)、Xj,k分別表示精英i、j的第k維分量，D為解向量的維數(shù)，ui,k為協(xié)同操作完成后所得子代個體的第k維分量，D維分量的集合構成個體μi,N(0,1)為服從標準正態(tài)分布的隨機變量，因標準正態(tài)分布在原點附近的概率較大，而遠離原點的概率較?。患?Xj,k-Xi,k)N(0,1)以較大的概率取得較小值，因而有利于精英在其附近進行精細化搜索，以提高收斂精度。

由于算法的隨機性，按式(7)得到的子代個體ui往往比原精英Xi差，很可能引起精英大規(guī)模退化，而影響尋優(yōu)效果。模擬退火算法SA(Simulated Annealing)中的Metropolis接受準則僅以小概率接受退化個體，從而使算法在兼顧全局搜索能力的情況下能盡可能地避免個體退化[13]。對此，本文基于Metropolis接受準則，設計了一種基于模擬退火的個體更新策略。

(8)

其中,Xi(t)表示第t代時的精英個體i，PSA是基于模擬退火原理設計的新個體接受率，T為退火溫度參數(shù)。由式(8)可知：當新個體優(yōu)于原個體時，則接受新個體；否則，以小概率接受比原個體更差的新個體，以保持算法跳出局部“陷阱”的能力。

3.3 遷移交流過程

普通種群在迭代過程中，將不斷產生優(yōu)良個體，這些優(yōu)良個體有時甚至比精英種群中的精英還優(yōu)秀，此時為維持精英種群和普通種群的界限，采用遷移算子將優(yōu)良個體從普通種群遷入精英種群，同時將精英種群中的不良個體從精英種群遷入普通種群。分別記POPCommon、POPElite為普通種群和精英種群，XExcellent、YPoor為普通種群中的最優(yōu)個體和精英種群中的最差個體，則遷入、遷出過程如圖1所示。

Figure 1 Migration process between the subgroups圖1 子群間遷移過程

3.4 DP-MKTOA算法流程

雙種群分子動理論優(yōu)化算法的算法流程如圖2所示。

Figure 2 Algorithm process of the DP-MKTOA圖2 DP-MKTOA算法流程

3.5 算法收斂性分析

在理論上對算法的收斂性進行分析，是算法有效性的重要依據(jù)，對算法改進具有指導作用。對此，本文對DP-MKTOA 的收斂性進行了初步分析，具體過程如下：

定義1給定的目標函數(shù)f，其解空間的范圍為RN，其中N表示維度(N=0,1,2,3,…,n)，則集合:

Ω={Xi|?Xj∈RN,f(Xi)≤f(Xj)}

(9)

稱為函數(shù)f的最優(yōu)解集合。

定義2對于一個隨機數(shù)列δ={Y(t),t=1,2,…,T}，如滿足:

(δ∩Ω≠?)=1

(10)

則稱隨機數(shù)列δ是概率弱收斂于函數(shù)f的最優(yōu)解。

要證明DP-MKTOA的收斂性，即證以下假設成立。

假設:對于任意的初始種群的給定，DP-MKTOA是概率弱收斂的。

證明Y(t)表示算法第t次迭代時的種群，記:

χt=P(Y(t+1)∩Ω=?|Y(t)∩Ω≠?)

(11)

λt=P(Y(t+1)∩Ω≠?|Y(t)∩Ω=?)

(12)

由DP-MKTOA的算法過程可知，種群產生的最優(yōu)個體不會發(fā)生退化，故χt=0；又由分子熱運動的擾動加速度可知，受力為零的個體具有從空間一點移動到空間任意一點的能力，基于模擬退火機制可知，個體還具有跳出局部極值的能力，故λt>0。

由全概率公式可知:

(13)

其中，λmin=min(λi),i=1,2,…,t。

由對任意t，有λt>0，所以0<1-λmin<1。

(14)

所以:

?)=

(15)

故DP-MKTOA以概率1收斂到最優(yōu)解。

□

4 算法性能測試

4.1 基準測試函數(shù)

為了驗證DP-MKTOA的有效性，選用文獻[9]中的15個經典函數(shù)作為基準測試函數(shù)，這些函數(shù)形態(tài)復雜，能對算法的性能進行全面測試，且這些函數(shù)已被廣泛應用于算法性能測試。表1中，f1～f8為單模函數(shù)，f9～f15為多模函數(shù)，f5為噪聲函數(shù)。f8、f15是2維函數(shù)，其它函數(shù)為30維函數(shù)。f1～f15的具體定義如表1所示。

Table 1 Benchmark test functions表1 基準測試函數(shù)

4.2 算法改進有效性驗證

為測試DP-MKTOA的性能，選取慣性權重微粒群算法IWPSO(Inertia Weight Particle Swarm Optimization)、帶隨機位置的微粒群算法RPPSO(Particle Swarm Optimization with Random Position)、進化策略(DE)和分子動理論優(yōu)化算法(MKTOA)作為比較對象，各算法參數(shù)設置與參考文獻[14,15]一致，如表2所示，種群規(guī)模和最大迭代次數(shù)分別為50和2 000。

由表3可知，與IWPSO、RPPSO和DE相比，MKTOA及其改進算法DP-MKTOA在收斂精度和算法穩(wěn)定性方面都具有明顯優(yōu)勢。對于函數(shù)f6和f9，傳統(tǒng)MKTOA距離問題的最優(yōu)解較遠，這是因為該算法僅依靠最優(yōu)個體引導尋優(yōu)過程，易陷于局部極值；而DP-MKTOA因采用雙子群，依靠整個精英子群對普通子群進行引導，并采用多樣性檢測的波動算子，能盡量避免陷于局部極值，因而尋優(yōu)結果更接近于理論最優(yōu)值。對于函數(shù)f5和f14，MKTOA和DP-MKTOA的結果都接近于理論最優(yōu)值，但因DP-MKTOA對精英個體采用相互

Table 2 Algorithm parameter Settings表2 算法參數(shù)設置

Table 3 Benchmark test function experiment表3 基準測試函數(shù)實驗

學習的協(xié)作算子，能在精英附近進行精細化搜索，因而取得了更高的收斂精度。對比實驗驗證了改進措施的有效性。

4.3 高維及超高維函數(shù)測試

為測試DP-MKTOA求解復雜問題的能力并分析問題復雜度的增加對算法性能的影響，用DP-MKTOA分別求解高維和超高維(1 000維及以上)條件下的f10和f13，并將其所求結果與文獻[16]中的免疫記憶克隆規(guī)劃算法IMCPA(Immune Memory Clonal Programming Algorithm)及無記憶功能的免疫記憶克隆規(guī)劃算法(nIMCPA)進行比較。算法終止條件為gbestF<ε，gbestF為算法當前的最優(yōu)值，ε為算法的收斂精度，比較結果如表4所示，其中“#”表示參考文獻中沒有該實驗數(shù)據(jù)。

由表4可知：與IMCPA和nIMCPA相比，在同一收斂精度條件下，DP-MKTOA 所需的函數(shù)評價次數(shù)相對較少；隨著維數(shù)的增加，DP-MKTOA的函數(shù)評價次數(shù)增長得相對緩慢。比較結果表明：DP-MKTOA即使在超高維條件下仍能表現(xiàn)出良好的性能，且其性能不隨問題維數(shù)的增加而迅速下降，表現(xiàn)出良好的魯棒性。

4.4 動態(tài)函數(shù)測試

為了檢測算法的動態(tài)變化跟蹤能力，選用Shift動態(tài)函數(shù)來測試算法的動態(tài)優(yōu)化性能[17]。選用如表5所示的典型動態(tài)函數(shù)進行實驗。

從表6實驗結果可以看出，在典型的Shift動態(tài)函數(shù)問題求解上，DP-MKTOA算法在全局最優(yōu)值(Mean)、標準方差(Std.Dev)及其收斂速度方面都表現(xiàn)良好，表明DP-MKTOA具有較好的動態(tài)自適應尋優(yōu)能力與抗干擾能力。

4.5 算法多樣性分析

由于本文篇幅有限，僅選取f5、f8、f12、f15四個具有代表性的函數(shù)進行分析，其中f5為30維的噪聲函數(shù)，f12為30維的多模函數(shù)，f8、f15是2維函數(shù)。由圖3～圖6的比較結果可得出以下結論：各算法的種群多樣性順序為DP-MKTOA>MKTOA>RPPSO>IWPSO>DE，其中IWPSO、DE的多樣性迅速下降并趨近于零，這無益于個體進化；RPPSO多樣性下降的速率比較慢，要好于IWPSO、DE，但最終還是在迭代的中后期趨近于零；DP-MKTOA和MKTOA的多樣性較好，能在2 000次的迭代過程中始終保持一定的多樣性，而DP-MKTOA仍優(yōu)于MKTOA。綜上可知，基于種群多樣性監(jiān)測的波動算子因能實時監(jiān)測種群多樣性，并據(jù)此調節(jié)波動率，對維持種群多樣性(即保持算法全局搜索能力)具有重要意義。

Table 4 Test of high-dimensional functions表4 高維函數(shù)性能測試

Table 5 Dynamic functions表5 動態(tài)函數(shù)

Table 6 Dynamic function experiment contrast表6 動態(tài)函數(shù)實驗對比

Figure 3 Diversity comparison of f5圖3 對f5求解的多樣性比較

Figure 5 Diversity comparison of f12圖5 對f12求解的多樣性比較

Figure 4 Diversity comparison of f8圖4 對f8求解的多樣性比較

Figure 6 Diversity comparison of f15圖6 對f15求解的多樣性比較

5 結束語

本文針對傳統(tǒng)分子動理論優(yōu)化算法存在尋優(yōu)精度差、易陷入局部極值等不足，提出了以下改進措施：(1)采用雙種群思想，每個子群按不同的策略進行搜索，通過分工合作而共同實現(xiàn)尋優(yōu)過程；(2)為使普通種群在大范圍內進行搜索，提出了多樣性波動算子，基于反饋的種群多樣性信息調節(jié)變異率，以增強算法的全局搜索能力；(3)為使精英種群實現(xiàn)精細化搜索，設計了協(xié)同學習算子，并采用模擬退火個體更新策略，盡量避免移動隨機性過大問題，從對比實驗可驗證算法改進的有效性。為進一步測試算法性能，分別以高維函數(shù)和動態(tài)函數(shù)作為測試對象，結果表明DP-MKTOA的性能不隨維數(shù)的增加而迅速下降，且對動態(tài)函數(shù)表現(xiàn)出良好的動態(tài)尋優(yōu)能力。雖然DP-MKTOA具備較好的綜合尋優(yōu)能力，但測試實驗表明，其性能仍有改善空間，且該算法僅適于求解單目標問題，不能直接求解多目標問題。因此，逐步對其改進和完善，進一步提高其尋優(yōu)性能和應用范圍，在后續(xù)工作中具有重要意義。

參考文獻:

[1] An Li-ping,Liu Sen.Two-phase genetic algorithm for attributes reduction [J].Systems Engineering-Theory & Practice,2014,34(11):2892-2899.(in Chinese)

[2] Wang Xiao-yuan, Gao Peng.Optimal design of permanent magnets of in-wheel motor based on evolution strategy [J].Proceedings of the CSEE,2015,35(4):979-984.(in Chinese)

[3] Panda S,Mohanty B,Hota P K.Hybrid BFOA—PSO algorithm for automatic generation control of linear and nonlinear interconnected power systems [J].Applied Soft Computing Journal,2013,13(12):4718-4730.

[4] Zhang Dong-li. Improved artificial bee colony algorithm and its applications [D].Qinhuangdao:Yanshan University,2014:15-22.(in Chinese)

[5] Wu B,Cun H Q,Wei H N,et al.The improvement of glowworm swarm optimization for continuous optimization problems [J].Expert Systems with Applications,2012,39(7):6335-6342.

[6] Meng Chao,Sun Zhi-xin.Research on central force optimization algorithm[J].Acta Electronica Sinica,2013,41(4):698-703.(in Chinese)

[7] Bi Xiao-jun, Diao Peng-fei,Wang Yan-jiao,et al.Improved multi-population gravitational search algorithm for dynamic optimization problems [J].Journal of Central South University,2015,46(9):3325-3331.(in Chinese)

[8] Sun Bao,Sun Da-gang,Li Zhan-long.Aritificial physics multi-objective algorithm based on sequence value and crowding degree [J].Systems Engineering and Electronics,2014,36(12):2442-2448.(in Chinese)

[9] Fan Chao-dong,Zhang Jing,Yi Ling-zhi.M-elite coevolutionary kinetic-molecular theory optimization algorithm [J].Journal on Communications,2015,36(7):144-152.(in Chinese)

[10] Fan Chao-dong, Ou Yang Hong-lin,Zhang Ying-jie,et al.Optimization algorithm based on kinetic-molecular theory [J].Journal of Central South University,2013,20(12):3504-3512.

[11] Fan Chao-dong, Zhang Ying-jie,Ou Yang Hong-lin,et al.Improved otsu method based on histogram oblique segmentation for segmentation of rotary kiln flame image[J].Acta Automatica Sinica,2014,40(11):2480-2489.(in Chinese)

[12] Fan Chao-dong, Ou Yang Hong-lin,Zhang Ying-jie,et al.Optimal multilevel thresholding using molecular kinetic theory optimization algorithm [J].Applied Mathematics and Computation,2014,239(15):391-408.

[13] Lu Jian-zhong, Cheng Hao.Short-term traffic flow forecast based on modified GA optimized BP neural network [J].Journal of Hefei University of Technology,2015,38(1):127-131.(in Chinese)

[14] Voglis C, Parsopoulos K E,Papageorgiou D G,et al.MEMPSODE:A global optimization software based on hybridization of population-based algorithms and local searches [J].Computer Physics Communications,2012,183(5):1139-1154.

[15] Zhou D W,Gao X,Liu G H,et al.Randomization in particle swarm optimization for global search ability [J].Expert Systems with Applications,2011,38(12):15356-15364.

[16] Liu Xing-bao,Cai Zi-xing, Wang Yong, et al. Novel immune evolutionary for global optimization [J].Control and Decision,2011,26(1):59-65.(in Chinese)

[17] Liang J J,Suganthan P N,Deb K.Novel composition test functions for numerical global optimization [J].IEEE Swarm Intelligence Symposium,2005,75(2):68-75.

[18] Nickabadi A,Ebadzadeh M M,Safabakhsh R.A novel particle swarm optimization algorithm with adaptive inertia weight [J].Applied Soft Computing,2011,11(4):3658-3670.

附中文參考文獻：

[1] 安利平,劉森.屬性約簡的兩階段遺傳算法[J].系統(tǒng)工程理論與實踐,2014,34(11):2892-2899.

[2] 王曉遠,高鵬.基于進化策略的輪轂電機永磁體結構優(yōu)化設計[J].中國電機工程學報,2015,35(4):979-984.

[4] 張冬麗,人工蜂群算法的改進及相關應用研究[D].秦皇島:燕山大學,2014:15-22.

[6] 孟超,孫知信.中心引力優(yōu)化CFO算法研究[J].電子學報,2013,41(4):698-703.

[7] 畢曉君,刁鵬飛,王艷嬌.求解動態(tài)優(yōu)化問題的改進多種群引力搜索算法[J].中南大學學報,2015,46(9):3325-3331.

[8] 孫寶,孫大剛,李占龍.基于序值與擁擠度的擬態(tài)物理學多目標算法[J].系統(tǒng)工程與電子技術,2014,36(12):2442-2448.

[9] 范朝冬,章兢,易靈芝.M-精英協(xié)同進化分子動理論優(yōu)化算法[J].通信學報,2015,36(7):144-152.

[11] 范朝冬,張英杰,歐陽紅林,等.基于改進斜分Otsu法的回轉窯火焰圖像分割[J].自動化學報,2014,40(11):2480-2489.

[13] 盧建中,程浩.改進GA優(yōu)化BP神經網絡的短時交通流預測[J].合肥工業(yè)大學學報,2015,38(1):127-131.

[16] 劉星寶,蔡自興,王勇,等.應用于高維優(yōu)化問題的免疫進化算法[J].控制與決策,2011,26(1):59-65.