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

邱　傲，項(xiàng)鐵銘

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

?

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

邱傲，項(xiàng)鐵銘

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

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

關(guān)鍵詞：佳點(diǎn)集；多維競爭；入侵雜草算法；文化框架

0引言

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

1標(biāo)準(zhǔn)入侵雜草算法

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

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

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

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

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

2算法改進(jìn)策略

2.1佳點(diǎn)集原理構(gòu)造初始種群

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

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

2.2多維競爭機(jī)制

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

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

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

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

2.3嵌入文化框架

圖2　文化算法框架

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

2.4本文算法流程

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

圖3　本文算法流程

3算法分析與對(duì)比

3.1測(cè)試函數(shù)

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

3.2實(shí)驗(yàn)結(jié)果分析

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

表1　3種算法的收斂精度測(cè)試結(jié)果

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

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

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

4結(jié)束語

本文提出的基于佳點(diǎn)集構(gòu)造的多維競爭文化入侵雜草算法從種群初始解優(yōu)化，競爭機(jī)制優(yōu)化，以及框架優(yōu)化上做出了改進(jìn)，對(duì)于解決高維復(fù)雜問題能力有了很大的提升，但沒能從理論上做進(jìn)一步分析，這是下一步要研究的方向.另外，在應(yīng)用方面，以后本文算法的研究方向?qū)⑥D(zhuǎn)向解決多目標(biāo)問題的研究.

參考文獻(xiàn)

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

[2]蘇守寶,方杰,汪繼文，等.基于入侵性雜草克隆的圖像聚類方法[J].華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版),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]宋玉堅(jiān),葉春明,黃佐钘.多智能體入侵雜草算法[J].計(jì)算機(jī)應(yīng)用研究, 2014, 31(10):2957-2961.

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

[7]陳義雄，梁昔明，黃亞飛. 基于佳點(diǎn)集構(gòu)造的改進(jìn)量子粒子群優(yōu)化算法[J].中南大學(xué)學(xué)報(bào)(自然科學(xué)版), 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]陳歡, 周永權(quán),趙光偉.基于混沌序列的多種群入侵雜草算法[J].計(jì)算機(jī)應(yīng)用, 2012, 32(7):1958-1961.

DOI：10.13954/j.cnki.hdu.2016.03.018

收稿日期：2015-09-15

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

中圖分類號(hào)：TP301.6

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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