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

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

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

0 引 言

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

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

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

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

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

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

圖1 野草適應值與種子數(shù)的線性關系

(1)

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

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

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

(2)

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

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

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

2.1 基于免疫進化的野草標準差優(yōu)化策略

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

采用免疫進化算法對野草繁殖的當前標準差進行控制，即：

(3)

其中，A表示標準差的動態(tài)調整系數(shù)。

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

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

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

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

步驟三：根據(jù)式(3)計算當前野草標準差ρiter。

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

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

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

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

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

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

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

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

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

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

如圖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ù)設置情況下，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)曲線

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

4 結束語

針對野草優(yōu)化隨機搜索算法在局部搜索能力上的缺陷，提出了一種基于免疫進化的野草優(yōu)化隨機搜索算法。該算法通過對野草群體最優(yōu)個體進行迭代進化計算，增加了解空間搜索密度，提高了群體多樣性，且有效避免了算法的不成熟收斂，能以更高的精度逼近全局最優(yōu)解。通過對4個典型測試函數(shù)進行數(shù)值尋優(yōu)實驗，結果表明，在相同條件下，該算法具有較好的優(yōu)化效果、穩(wěn)定性和收斂效率，且適用于多種不同類型的復雜多模態(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)化算法的從線畫圖精確重構三維物體[J].計算機輔助設計與圖形學學報,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] 紀 震,周家銳,廖惠連,等.智能單粒子優(yōu)化算法[J].計算機學報,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] 蘇守寶,汪繼文,張 鈴,等.一種約束工程設計問題的入侵性雜草優(yōu)化算法[J].中國科學技術大學學報,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計算模型的研究及應用[D].武漢:華中科技大學,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] 張 氫,陳丹丹,秦仙蓉,等.雜草算法收斂性分析及其在工程中的應用[J].同濟大學學報:自然科學版,2010,38(11):1689-1693.

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

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