基于免疫進(jìn)化的野草優(yōu)化隨機(jī)搜索算法

楊 瀾，惠 飛，侯 俊，穆柯楠，武曉潔

(1.長安大學(xué) 信息工程學(xué)院，陜西 西安 710064; 2.長安大學(xué) 電子與控制工程學(xué)院，陜西 西安 710064)

0 引 言

在計(jì)算機(jī)科學(xué)、電子工程、生物學(xué)以及管理科學(xué)等領(lǐng)域存在的行商問題、圖著色問題、設(shè)備布局問題等大規(guī)模組合優(yōu)化問題，無法通過現(xiàn)有近似算法求解高質(zhì)量近似解[1-2]。傳統(tǒng)的隨機(jī)搜索算法，如最小二乘法、線性規(guī)劃法、最速下降法以及單純形法等主要適用于求解較為簡單的問題。對于具有多約束非線性多極值的復(fù)雜問題，這些方法的求解過程比較復(fù)雜、收斂速度慢，且很難求得全局最優(yōu)解。近年來，研究人員通過模擬自然現(xiàn)象、過程以及生物特性，提出了用于解決復(fù)雜問題的隨機(jī)搜索算法，如演化算法(evolutionary algorithms,EAs)、人工免疫系統(tǒng)(artificial immune system,AIS)、模擬退火算法(simulated annealing,SA)、粒子群算法(particle swarm optimization,PSO)、蟻群算法(ant colony optimization,ACO)、煙花算法(fireworks algorithm，F(xiàn)WA)以及其他混合策略、新型改進(jìn)算法等[3-10]。由Mehrabian和Lucas提出的野草優(yōu)化隨機(jī)搜索算法(invasive weed optimization,IWO)是一種基于群體智能的全局協(xié)同后啟發(fā)式計(jì)算技術(shù)，具有較強(qiáng)的隨機(jī)性、魯棒性和自適應(yīng)性，可以求解離散、連續(xù)變量、非線性等復(fù)雜優(yōu)化問題，目前已應(yīng)用于動態(tài)控制系統(tǒng)柔性結(jié)構(gòu)的控制參數(shù)調(diào)整、飛機(jī)智能機(jī)翼壓電式控制器的最優(yōu)定位、DNA編碼順序設(shè)計(jì)優(yōu)化和天線設(shè)計(jì)配置優(yōu)化等問題中[11-18]。

在該算法的迭代計(jì)算過程中，最差個體空間位置在更新前后發(fā)生較大變化。這種更新策略雖擴(kuò)大了解空間搜索范圍，卻易于跳過全局最優(yōu)解，導(dǎo)致陷入局部最優(yōu)，不利于在可行域內(nèi)有效搜索。為了提高野草優(yōu)化隨機(jī)搜索算法的求解精度，文中引入免疫進(jìn)化(immune evolutionary algorithm，IEA)思想，提出了基于免疫進(jìn)化改進(jìn)的野草優(yōu)化隨機(jī)搜索算法(modified invasive weed optimization,MIWO)。該算法運(yùn)用免疫進(jìn)化理論促使其不斷持續(xù)進(jìn)化，不僅可以避免不成熟收斂，以更高的精度逼近全局最優(yōu)解，且可以提高算法的收斂速度。

1 野草優(yōu)化隨機(jī)搜索算法

野草優(yōu)化隨機(jī)搜索算法將待求解問題轉(zhuǎn)化為目標(biāo)函數(shù)優(yōu)化問題[19]。該算法中，“種群”代表所有野草的集合，“野草”代表隨機(jī)產(chǎn)生的可行解，“適應(yīng)值”代表個體的目標(biāo)函數(shù)，“種子”代表野草繁殖產(chǎn)生的后代。在進(jìn)化過程中，野草通過不斷繁殖產(chǎn)生后代種子，種子通過空間擴(kuò)散分布在搜索空間中，種子繼續(xù)生長成為野草。該過程一直迭代反復(fù)，當(dāng)野草數(shù)量超過環(huán)境資源的承受能力時(shí)，通過優(yōu)勝劣汰將適應(yīng)度較好的野草留下，而適應(yīng)度較差的野草被環(huán)境淘汰[20]。一般地，IWO算法包括以下4個步驟。

步驟一：在D維搜索空間中隨機(jī)產(chǎn)生一組初始種群；

步驟二：每個野草種子生長至開花，根據(jù)式(1)，由野草適應(yīng)值、種群中野草的最大適應(yīng)值和最小適應(yīng)值繁殖產(chǎn)生后代種子(線性關(guān)系見圖1)。

圖1 野草適應(yīng)值與種子數(shù)的線性關(guān)系

(1)

其中，F(xiàn)iter為當(dāng)前野草的適應(yīng)值；Fmax和Fmin分別表示當(dāng)前種群中野草的最大適應(yīng)值和最小適應(yīng)值；Nmax和Nmin分別為單個野草產(chǎn)生的種子數(shù)的最大值和最小值。

從式(1)可以看出，適應(yīng)能力較強(qiáng)的個體子代數(shù)目較多，適應(yīng)能力較弱的個體也有生存繁殖機(jī)會。

步驟三：野草種子在其父代附近以正態(tài)分布N(0,ρ2)方式隨機(jī)擴(kuò)散。在每一代進(jìn)化中，目標(biāo)函數(shù)標(biāo)準(zhǔn)差ρ從初始值ρ0到最終值ρf動態(tài)調(diào)整，當(dāng)前代的標(biāo)準(zhǔn)差為：

(2)

其中，itermax和iter分別為最大迭代次數(shù)與當(dāng)前迭代數(shù)；n為非線性調(diào)節(jié)因子，指生物群體動力學(xué)的選擇勢力。式(2)確保在距離較遠(yuǎn)區(qū)域產(chǎn)生種子的可能性隨迭代次數(shù)而非線性增加。

步驟四：經(jīng)過itermax次生長繁殖產(chǎn)生的野草后代數(shù)量將超過環(huán)境資源的承受力，需要通過最大種群數(shù)目Pmax控制種群數(shù)量。即將種群中所有野草按適應(yīng)值以降序排列，適應(yīng)值最好的Pmax個野草個體保留，其余被淘汰。

2 基于免疫進(jìn)化的野草優(yōu)化隨機(jī)搜索算法

2.1 基于免疫進(jìn)化的野草標(biāo)準(zhǔn)差優(yōu)化策略

在實(shí)際工程函數(shù)優(yōu)化問題中，理想優(yōu)化算法能利用少量資源求解出最優(yōu)解。而在野草繁殖過程中，目標(biāo)函數(shù)標(biāo)準(zhǔn)差ρ會隨著迭代次數(shù)的增加而緩慢遞減，陷入局部最優(yōu)解。因此為了充分利用群體中最優(yōu)個體信息進(jìn)行最優(yōu)解搜索，提出將免疫進(jìn)化算法融入到野草標(biāo)準(zhǔn)差更新過程中，從而群體中優(yōu)秀個體與全局最優(yōu)解之間的空間距離小于群體中其他個體與全局最優(yōu)解之間的空間距離，并且與全局最優(yōu)解空間距離較小的個體有較高的適應(yīng)值。

采用免疫進(jìn)化算法對野草繁殖的當(dāng)前標(biāo)準(zhǔn)差進(jìn)行控制，即：

(3)

其中，A表示標(biāo)準(zhǔn)差的動態(tài)調(diào)整系數(shù)。

在標(biāo)準(zhǔn)差計(jì)算過程中，增加隨迭代次數(shù)iter衰減的指數(shù)因子，確保野草種子在較遠(yuǎn)區(qū)域的傳播概率以非線性方式逐漸降低，使適應(yīng)值較好的個體快速聚合并保留，而適應(yīng)能力差的個體被清除。因此，在野草繁殖過程中，對每個解迭代的標(biāo)準(zhǔn)差用免疫進(jìn)化算法進(jìn)行優(yōu)化迭代計(jì)算，再在生成的解中選擇適應(yīng)值較好的Pmax個解進(jìn)化替代群體進(jìn)化。這樣改進(jìn)的目的在于：在算法迭代進(jìn)化前期，能圍繞最優(yōu)解進(jìn)行搜索，既增加解空間的搜索密度，保持較好的群體多樣性，有效避免算法不成熟收斂，又加快了算法收斂速度；在算法進(jìn)化后期，局部搜索能力進(jìn)一步加強(qiáng)，算法能夠逼近全局最優(yōu)解，從而提高求解精度。

2.2 基于免疫進(jìn)化的野草優(yōu)化隨機(jī)搜索算法的實(shí)現(xiàn)步驟

步驟一：初始化。設(shè)置問題維數(shù)D，野草初始種群規(guī)模Pmax，最大和最小生成種子數(shù)Nmax和Nmin，最大迭代次數(shù)itermax，目標(biāo)函數(shù)的標(biāo)準(zhǔn)差初始值ρ0和最終值ρf，非線性調(diào)節(jié)因子n，標(biāo)準(zhǔn)差動態(tài)調(diào)整系數(shù)A及初始搜索空間X等參數(shù)。

步驟二：根據(jù)初始化參數(shù)隨機(jī)生成Pmax個野草，并根據(jù)其適應(yīng)值大小降序排列。

步驟三：根據(jù)式(3)計(jì)算當(dāng)前野草標(biāo)準(zhǔn)差ρiter。

步驟四：根據(jù)式(1)計(jì)算每個野草繁殖種子的個數(shù)。每個野草繁殖種子的總數(shù)是在保留上一代解的基礎(chǔ)上，以當(dāng)前解為期望值、ρ2為標(biāo)準(zhǔn)差的正態(tài)分布方式，不斷產(chǎn)生新解并更新。

步驟五：按照野草適應(yīng)值的大小降序排列，選取適應(yīng)值較好的Pmax個野草。

步驟六：當(dāng)?shù)螖?shù)滿足iter=itermax時(shí)，算法停止，輸出最優(yōu)解；否則轉(zhuǎn)入步驟三。

3 算法的數(shù)值尋優(yōu)實(shí)驗(yàn)

實(shí)驗(yàn)通過不同的測試函數(shù)來分析各種優(yōu)化算法的搜索性能差異。如表1所示，采用4個典型的30維標(biāo)準(zhǔn)測試函數(shù)驗(yàn)證文中算法的數(shù)值尋優(yōu)特性，并且和遺傳算法(GA)、粒子群優(yōu)化算法(PSO)以及傳統(tǒng)IWO算法進(jìn)行性能對比。

表1 4種測試函數(shù)

如表1所示，在上述4種測試函數(shù)中，f1和f4都是單峰函數(shù)；f2是經(jīng)典的復(fù)雜優(yōu)化問題，一般用于驗(yàn)證隨機(jī)搜索算法執(zhí)行效率。它的全局最優(yōu)值坐落于一個平滑且狹長的拋物線形峽谷中，因?yàn)楹瘮?shù)僅為優(yōu)化算法提供少量信息，使算法較難辨別搜索方向，因此找到全局最優(yōu)點(diǎn)的幾率微乎其微。f4是非凸病態(tài)函數(shù)，一般用于測試算法的求解精度和執(zhí)行能力。f2和f3是多峰函數(shù)，具有較多最小值點(diǎn)，因此較難找出全局最優(yōu)解。這4種測試函數(shù)通常用來測試隨機(jī)搜索算法跳出局部最優(yōu)解的能力。

IWO算法和MIWO算法初始信息設(shè)置為：最大種群50，最大迭代次數(shù)100，n為3，[Smax，Smin]=[5，3]，[ρinitial,ρfinal]=[10,0.001]，A=5；遺傳算法中的交叉概率pc=0.75，變異概率pm=0.5；粒子群算法中的學(xué)習(xí)因子c1=1.473 9，c2=1.473 9，權(quán)值w=0.801。

圖2為4種隨機(jī)搜索算法對4種測試函數(shù)的適應(yīng)值隨總進(jìn)化代數(shù)iter變化的進(jìn)化曲線。對每種測試函數(shù)均獨(dú)立運(yùn)行100次，并計(jì)算其平均最優(yōu)值及平均迭代次數(shù)，對比結(jié)果如表2所示。

表2 平均最優(yōu)解對比結(jié)果

如圖2所示，MIWO算法在收斂精度和收斂效率上均優(yōu)于其他3種尋優(yōu)算法。特別地，MIWO算法的收斂速度優(yōu)于IWO算法，且MIWO算法能夠保持較好的收斂效果。遺傳算法的收斂速度比粒子群算法慢，更甚于傳統(tǒng)IWO算法。MIWO算法以其較快的收斂速度收斂于全局最優(yōu)解。傳統(tǒng)IWO算法和MIWO算法均未陷入局部最優(yōu)值。相比之下，遺傳算法收斂速度較慢，并且同粒子群優(yōu)化算法一樣陷入了全局最優(yōu)解。

如表2所示，在相同初始參數(shù)設(shè)置情況下，MIWO算法的平均最優(yōu)解與平均迭代次數(shù)均優(yōu)于GA算法、PSO算法和傳統(tǒng)IWO算法。特別地，在測試函數(shù)f1和f2中，MIWO算法的最優(yōu)值高于GA算法和PSO算法兩個量級；在測試函數(shù)f2中，MIWO算法的最優(yōu)值高于GA算法和PSO算法兩個量級；在測試函數(shù)f3中，MIWO的最優(yōu)值高于GA和PSO分別一個量級和兩個量級；在測試函數(shù)f4中，MIWO的最優(yōu)值高于GA和PSO兩個量級，它的收斂次數(shù)也優(yōu)于其他3種算法。

圖2 不同算法對4種測試函數(shù)的數(shù)值尋優(yōu)曲線

結(jié)合可以看出，MIWO算法是解決單峰和多峰優(yōu)化問題最行之有效的優(yōu)化算法，相比于其他3種算法具有較好的全局搜索能力，快速的收斂速度以及較高的計(jì)算精度。

4 結(jié)束語

針對野草優(yōu)化隨機(jī)搜索算法在局部搜索能力上的缺陷，提出了一種基于免疫進(jìn)化的野草優(yōu)化隨機(jī)搜索算法。該算法通過對野草群體最優(yōu)個體進(jìn)行迭代進(jìn)化計(jì)算，增加了解空間搜索密度，提高了群體多樣性，且有效避免了算法的不成熟收斂，能以更高的精度逼近全局最優(yōu)解。通過對4個典型測試函數(shù)進(jìn)行數(shù)值尋優(yōu)實(shí)驗(yàn)，結(jié)果表明，在相同條件下，該算法具有較好的優(yōu)化效果、穩(wěn)定性和收斂效率，且適用于多種不同類型的復(fù)雜多模態(tài)函數(shù)優(yōu)化問題。

[1] 張艷梅,姜淑娟,陳若玉,等.基于粒子群優(yōu)化算法的類集成測試序列確定方法[D/OL].2016-03-23.http://www.cnki.net/kcms/detail/11.1826.tp.20160323.0000.002.html.

[2] 鄒常青,劉健莊.基于優(yōu)化算法的從線畫圖精確重構(gòu)三維物體[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2012,24(12):1585-1591.

[3] LEE Z J,LEE C Y.A hybrid search algorithm with heuristics for resource allocation problem[J].Information Sciences,2005,173(1-3):155-167.

[4] 紀(jì) 震,周家銳,廖惠連,等.智能單粒子優(yōu)化算法[J].計(jì)算機(jī)學(xué)報(bào),2010,33(3):556-561.

[5] ALAM S, DOBBIE G, YUN S K,et al.Research on particle swarm optimization based clustering:a systematic review of literature and techniques[J].Swarm & Evolutionary Computation,2014,17:1-13.

[6] 謝曉鋒,張文俊,楊之廉.微粒群算法綜述[J].控制與決策,2003,18(2):129-134.

[7] NESHAT M,SEPIDNAM G,SARGOLZAEI M,et al.Artificial fish swarm algorithm:a survey of the state-of-the-art,hybridization,combinatorial and indicative applications[J].Artificial Intelligence Review,2014,42(4):965-997.

[8] LI Yuxiang,ZHAO Yinliang,LIU Bin,et al.基于人工免疫算法的推測多線程線程劃分參數(shù)的優(yōu)化(英文)[J].Journal of Zhejiang University-Science C:Computers & Electronics,2015,16(3):205-217.

[9] KARABOGA D，BASTURK B．A powerful and efficient algorithm for numerical function optimization:artificial bee colony

(ABC) algorithm[J]．Journal of Global Optimization，2007，39(3):459-471．

[10] CHETTY S,ADEWUMI A O.Comparison study of swarm intelligence techniques for the annual crop planning problem[J].IEEE Transactions on Evolutionary Computation,2014,18(2):258-268.

[11] MEHRABIAN A R,LUCAS C.A novel numerical optimization algorithm inspired from weed colonization[J].Ecological Informatics,2006,1(4):355-366.

[12] 蘇守寶,汪繼文,張 鈴,等.一種約束工程設(shè)計(jì)問題的入侵性雜草優(yōu)化算法[J].中國科學(xué)技術(shù)大學(xué)學(xué)報(bào),2009,39(8):885-893.

[13] KARIMKASHI S，KISHK A A.Invasive weed optimization and its features in electromagnetic[J].IEEE Transactions on Antennas and Propagation,2010,58(4):1269-1278.

[14] 張勛才.自組裝DNA計(jì)算模型的研究及應(yīng)用[D].武漢:華中科技大學(xué),2009.

[15] SEDIGHY S H,MALLAHZADEH A R,SOLEIMANI M,et al.Optimization of printed Yagi antenna using invasive weed optimization (IWO)[J].IEEE Antennas and Wireless Propagation Letters,2010,9(1):1275-1278.

[16] ZHANG X,WANG Y,CUI G,et al.Application of a novel IWO to the design of encoding sequences for DNA computing[J].Computers and Mathematics with Applications,2009,57(11-12):2001-2008.

[17] MARYAM Q,MAHDI S.Solving quadratic assignment problem (QAP) using invasive weed optimization algorithm[J].Journal of Industrial Engineering,2011,45:113-125.

[18] 張 氫,陳丹丹,秦仙蓉,等.雜草算法收斂性分析及其在工程中的應(yīng)用[J].同濟(jì)大學(xué)學(xué)報(bào):自然科學(xué)版,2010,38(11):1689-1693.

[19] 劉 燕,焦永昌,張亞明,等.混合入侵雜草算法用于陣列天線波束賦形[J].西安電子科技大學(xué)學(xué)報(bào),2014,41(4):94-99.

[20] 黃 霞,葉春明,曹 磊.一種混沌變異的入侵雜草優(yōu)化算法及性能仿真[J].系統(tǒng)仿真學(xué)報(bào),2016,28(8):1732-1739.