基于免疫進化的野草優化隨機搜索算法

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

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

0 引 言

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

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

1 野草優化隨機搜索算法

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

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

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

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

(1)

其中，Fiter為當前野草的適應值；Fmax和Fmin分別表示當前種群中野草的最大適應值和最小適應值；Nmax和Nmin分別為單個野草產生的種子數的最大值和最小值。

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

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

(2)

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

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

2 基于免疫進化的野草優化隨機搜索算法

2.1 基于免疫進化的野草標準差優化策略

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

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

(3)

其中，A表示標準差的動態調整系數。

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

2.2 基于免疫進化的野草優化隨機搜索算法的實現步驟

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

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

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

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

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

步驟六：當迭代次數滿足iter=itermax時，算法停止，輸出最優解；否則轉入步驟三。

3 算法的數值尋優實驗

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

表1 4種測試函數

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

IWO算法和MIWO算法初始信息設置為：最大種群50，最大迭代次數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種測試函數的適應值隨總進化代數iter變化的進化曲線。對每種測試函數均獨立運行100次，并計算其平均最優值及平均迭代次數，對比結果如表2所示。

表2 平均最優解對比結果

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

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

圖2 不同算法對4種測試函數的數值尋優曲線

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

4 結束語

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

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

[2] 鄒常青,劉健莊.基于優化算法的從線畫圖精確重構三維物體[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] 紀 震,周家銳,廖惠連,等.智能單粒子優化算法[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.基于人工免疫算法的推測多線程線程劃分參數的優化(英文)[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] 蘇守寶,汪繼文,張 鈴,等.一種約束工程設計問題的入侵性雜草優化算法[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] 黃 霞,葉春明,曹 磊.一種混沌變異的入侵雜草優化算法及性能仿真[J].系統仿真學報,2016,28(8):1732-1739.