邱　傲，項鐵銘

(杭州電子科技大學天線與微波技術研究所，浙江 杭州 310018)

?

基于佳點集原理的多維競爭文化入侵雜草算法

邱傲，項鐵銘

(杭州電子科技大學天線與微波技術研究所，浙江 杭州 310018)

摘要：針對入侵雜草算法收斂速度較慢，解決復雜高維問題時仍難跳出局部最優(yōu)的不足，提出了基于佳點集原理的多維競爭文化入侵雜草算法.首先，采用佳點集原理均勻的初始化種群，從而提高初始解的質量；其次，采用多維競爭的機制，使算法更容易跳出局部最優(yōu)；最后，將改進的入侵雜草算法嵌入到文化框架中，通過不斷更新信念空間知識對種群進行全局指導，提高算法的收斂速度.通過5個經典測試函數(shù)的測試表明，算法不僅收斂速度快，而且跳出局部最優(yōu)的能力也得到很大的提升.

關鍵詞：佳點集；多維競爭；入侵雜草算法；文化框架

0引言

入侵雜草算法(Invasive Weed Optimization，IWO)由于其多樣性豐富、魯棒性好、代碼易于實現(xiàn)，受到廣泛關注和應用.目前，入侵雜草算法已應用到很多復雜問題中，如陣列天線方向圖綜合[1]、圖像聚類、DNA序列設計[2]等.然而，該算法還有很多不足，如收斂速度慢、求解精度低等.為此，前人做出了很多的改進工作，總結起來有3種策略.一是跟其它智能算法混合，例如文獻[3]采用文化框架，利用信仰空間群體指導種群空間進行進化，提高了算法的收斂速度；文獻[4]將IWO和PSO混合，利用雜草算法的廣度和PSO算法的深度，在子代擴散中以PSO算法中的位置、速度公式代替了雜草算法中的正態(tài)分布擴散，算法收斂速度和全局搜索能力有所提高.二是分群策略[5].三是改進IWO內在進化機制，例如文獻[6]提出了離散二進制入侵雜草算法，并將改進的IWO用于解決離散問題.本文提出了基于佳點集構造的多維競爭文化入侵雜草算法(CMAIWO算法)，采用佳點集原理構造初始種群，使種群均勻分布在可行解空間，并且針對IWO淘汰機制過于僵化的嚴重缺陷，采用多維淘汰機制，使得種群競爭更為合理.通過大量實驗證明，這種改進機制可行有效的.

1標準入侵雜草算法

入侵雜草算法是受雜草啟發(fā)而提出的，它是模擬雜草入侵過程的算法.算法主要有種群初始化、繁衍后代、子代分布、競爭淘汰4個階段，具體階段如下：

1)種群空間初始化.采用隨機的形式，若干的雜草種子擴散在D維的種群空間中.如果解決的問題維度比較大，一般選擇的種群數(shù)目會多一點，要視具體情況而定，選擇合適的種群數(shù)目.

3)子代分布.個體產生子代后，此時采用正態(tài)分布的形式，子代以父代為中心在D維空間中向周圍擴散.在標準入侵雜草算法中，每一代擴散的標準差有其自己的規(guī)律，公式為

4)競爭淘汰.生存空間是有限制的，在繁殖一定的代數(shù)后，為了種群的可持續(xù)性，必須淘汰一些適應力較差的個體.通過設定種群最大存活數(shù)目Nmax來控制整個種群的數(shù)目，保證算法持續(xù)往下運行.算法的每一次迭代后，都會按照個體及其產生的子代的所有適應度值降序排列，然后將適應度值較大的前Nmax個個體選出來進行下一次迭代，剩下的個體則被環(huán)境淘汰.

以上就是標準入侵雜草算法的4個基本過程，環(huán)境決定了部分個體的淘汰，這樣就導致了算法多樣性相對較低，容易陷入局部最優(yōu).

2算法改進策略

2.1佳點集原理構造初始種群

為驗證佳點集構造的優(yōu)越性，本文選取隨機抽樣，拉丁超立方抽樣與佳點集的構造進行比較.取種群個數(shù)為100，范圍是[0，1]，圖1中的(a)，(b)，(c)分別為不同初始條件下粒子在二維空間的分布圖.

圖1　不同抽樣方法的粒子分布圖

2.2多維競爭機制

標準入侵雜草算法在競爭淘汰階段只是根據(jù)函數(shù)值大小選擇最優(yōu)個體來作為下一輪迭代的父代個體.這會造成多樣性的降低，這顯然是個嚴重的缺陷.本文針對這一缺陷提出新的改進方案，從每一代產生的子代中按照種群最大存活個數(shù)以一定的比例(本文選取10%)選出具有潛力的部分個體.設每一代具有潛力的個體數(shù)為Nalive，剩余存活的個體為Ns，種群最大存活個數(shù)為Nmax.本文的淘汰規(guī)則如下：

1)設每一父代產生的子代的潛力系數(shù)為Pi，表示為第i個父代個體所產生子代的適應度值與每個父代個體的適應度值之比，即Pi=fson/Fi，fson為保存第i個個體產生所有子代適應度值的矩陣，F(xiàn)i為第i個個體的適應度值.由于本文算法是最小優(yōu)化，Pi保存了每個子代的潛力系數(shù)，值越小說明該個體潛力越大；

2)潛力個體與剩余存活個體必須保證沒有相同的個體，且滿足Nalive+Ns=Nmax，然后潛力個體與剩余存活個體一起進入下一次迭代；

3)為保證每一代具有潛力的個體具有更大的活躍性，約定潛力個體并不受文化框架的指導，并且下一代的迭代中比其他個體多產生兩個子代.

2.3嵌入文化框架

圖2　文化算法框架

為提高算法的收斂速度，本文引入文化框架這個概念，將改進后的入侵雜草算法嵌入到文化框架.文化框架是模擬人類社會，將以往的經驗知識世代傳遞作為歷史經驗以各種介質保存下來，然后人類從歷史經驗獲取知識提高生產效率，避免危險等.往往人類進化的關鍵之源是以往經驗積淀而形成的文化，也就是文化傳承著歷史信息.人們是通過學習文化來提高自己的知識儲備，再運用學習到的知識從事社會活動；并且通過實踐獲取沒有學習到的歷史知識，形成新的文化，人類社會在獲取知識和形成知識中不斷進步和完善.假如不進行文化的傳承，人類只會通過自身的實踐來獲取知識，往往浪費大量的時間、精力.這樣就產生了一種新的框架，即文化算法[8]，用來模擬人類社會的歷史經驗積累傳承.文化框架如圖2所示，REYNOLDS將文化框架分為種群空間和信念空間，信念空間在宏觀上表征種群進化過程中不斷產生的文化知識，種群空間在微觀上表征不斷進化種群，并向信念空間獲取知識指導種群進化.

2.4本文算法流程

以上給出了本文的對標準入侵雜草算法的改進策略，其算法流程如圖3所示.圖3中，T為當前迭代次數(shù)，AcceptStep本文取5，“T%AcceptStep”如果為0，將種群空間當前全局最好個體替換信仰空間中最差個體，否則繼續(xù)進行種群空間的演化.信念空間和種群空間通過接受函數(shù)和影響函數(shù)這種通信協(xié)議來更新知識以及影響種群空間進化，多維競爭機制持續(xù)為進化選擇更有質量的種子，佳點集的構造在源頭控制種子的初始質量.通過實驗分析，本文算法的時間復雜度不足以達到標準入侵雜草算法的數(shù)量級.

圖3　本文算法流程

3算法分析與對比

3.1測試函數(shù)

本文采用5個有代表性的測試函數(shù)，分別從收斂速度、收斂精度等性能指標來驗證本文算法的有效性.Sphere函數(shù)(f1)為單峰函數(shù)，一般用于測試算法的尋優(yōu)精度；Griewwank函數(shù)(f2)有許多對稱分布的全局最優(yōu)；Rosenbrock函數(shù)(f3)函數(shù)為典型的病態(tài)非凸單模函數(shù)，極難找到全局最小值.Ackley函數(shù)(f4)有一個很小全局最優(yōu)和周圍許多較小的局部最優(yōu)；Rastrigin函數(shù)(f5)為復雜多模函數(shù)，在搜索區(qū)域內有大量局部極小點(約有10 個全局極小值).所選5個測試函數(shù)的理論值均為0.

3.2實驗結果分析

本文算法參數(shù)設置：初始化種群數(shù)取10，最大種群規(guī)模取30，初始化標準差取300，最終標準差取0.05，非線性因子取3；經過多次實驗，結果顯示最大種子個數(shù)和最小種子個數(shù)分別取15和0效果比較好.在相同參數(shù)設置的情況下，本文提出的CMAIWO算法分別與標準IWO和文獻[9]的CMIWO算法進行對比.為減少隨機性的影響，對每個測試函數(shù)獨立運行50次，測試結果如表1所示.

表1　3種算法的收斂精度測試結果

表1的結果顯示CMAIWO在解決高維復雜問題時有著明顯的優(yōu)勢，對于函數(shù)f2，f3，f4，f5，CMAIWO在最優(yōu)值和平均值方面，比CMIWO有1～4個數(shù)量級的提高，并且在標準差方面也有相當明顯的優(yōu)勢.這是由于本文引入多維競爭機制，部分有潛力的個體被留下，這些個體一般會指向最優(yōu)值的方向，往往能幫助種群跳出局部最優(yōu).

3種算法在迭代200次的情況下，各個測試函數(shù)的收斂軌跡如圖4所示.各個測試函數(shù)的收斂軌跡表明，CMAIWO在很少的迭代次數(shù)內就可以達到很好的值.這是因為CMAIWO采用佳點集原理構造初始解，種群在空間內更容易找到最優(yōu)解，并且采用文化框架，大大加快了收斂速度.經過多次的實驗測試表明，每一代具有潛力個體個數(shù)的選取對算法的性能有很明顯的影響，一般取種群個數(shù)的10%比較好.

圖4　各個函數(shù)的收斂軌跡

4結束語

本文提出的基于佳點集構造的多維競爭文化入侵雜草算法從種群初始解優(yōu)化，競爭機制優(yōu)化，以及框架優(yōu)化上做出了改進，對于解決高維復雜問題能力有了很大的提升，但沒能從理論上做進一步分析，這是下一步要研究的方向.另外，在應用方面，以后本文算法的研究方向將轉向解決多目標問題的研究.

參考文獻

[1]劉燕,焦永昌,張亞明,等.基于分解的多目標入侵雜草算法用于陣列天線方向圖綜合[J].西北工業(yè)大學學報,2014,32(6):981-986.

[2]蘇守寶,方杰,汪繼文，等.基于入侵性雜草克隆的圖像聚類方法[J].華南理工大學學報(自然科學版),2008,36(5):95-100.

[3]ZHANG X, XU J, CUI G, et al.Research on Invasive Weed Optimization Based on the Cultural Framework[J].Journal of Computational and Theoretical Nanoscience,2010,7(5)：820-825.

[4]HAJIMIRSADEHGI H, LUCAS C. A hybrid IWO/PSO algorithm for fast and global optimization[C]//EUROCON 2009, EUROCON'09. IEEE, 2009: 1964-1971.

[5]宋玉堅,葉春明,黃佐钘.多智能體入侵雜草算法[J].計算機應用研究, 2014, 31(10):2957-2961.

[6]張帥,王營冠,夏凌楠.離散二進制入侵雜草算法[J].華中科技大學學報, 2011, 39(10):55-60.

[7]陳義雄，梁昔明，黃亞飛. 基于佳點集構造的改進量子粒子群優(yōu)化算法[J].中南大學學報(自然科學版), 2013, 44(4):1409-1414.

[8]LIU S, YOU X, WU Z. A Cultural Immune Quantum Evolutionary Algorithm and Its Application[J]. Journal of Computers, 2013, 8(1): 163-169.

[9]陳歡, 周永權,趙光偉.基于混沌序列的多種群入侵雜草算法[J].計算機應用, 2012, 32(7):1958-1961.

DOI：10.13954/j.cnki.hdu.2016.03.018

收稿日期：2015-09-15

作者簡介：邱傲(1990-)，男，湖北仙桃人，碩士研究生，智能優(yōu)化算法及其應用.通信作者：項鐵銘副教授，E-mail:tmxiang@126.com.

中圖分類號：TP301.6

文獻標識碼：A

文章編號：1001-9146(2016)03-0089-05

Multi-dimensional Competitive Culture Invasive Weed Optimization Algorithm Based on Good-point Set

QIU Ao, XIANG Tieming

(InstituteofAntennaandMicrowaveTechnology,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

Abstract：In the paper, the algorithm of multi-dimensional competitive based on the good-point set is proposed to solve the problem that the convergence rate of the invasive weed algorithm is slow and it is still difficult to solve the problem of local optimization. First, the algorithm uses the principle of the best point set, and then improves the initialization of the population to improve the quality of the initial solution; Second, for the invasion of weed algorithm is only based on the size of the fitness value of the problem, this paper uses the multi-dimensional competitive mechanism, making the algorithm more easy to jump out of local optimum; Third, the improved invasive weed algorithm is embedded into the cultural framework, and the global guidance of the population is improved by the continuous updating of the belief space knowledge. Through the test of the 5 test functions, the results show that the algorithm not only has a fast convergence speed, but also has a great improvement in the ability to jump out of the local optimum.

Key words：good-point set; multi-dimensional competition; invasive weed algorithm; cultural framework