国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

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

2018-03-05 02:36:58穆柯楠武曉潔
計算機技術(shù)與發(fā)展 2018年2期
關(guān)鍵詞:測試函數(shù)搜索算法野草

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

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

0 引 言

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

在該算法的迭代計算過程中,最差個體空間位置在更新前后發(fā)生較大變化。這種更新策略雖擴大了解空間搜索范圍,卻易于跳過全局最優(yōu)解,導(dǎo)致陷入局部最優(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)化隨機搜索算法將待求解問題轉(zhuǎn)化為目標函數(shù)優(yōu)化問題[19]。該算法中,“種群”代表所有野草的集合,“野草”代表隨機產(chǎn)生的可行解,“適應(yīng)值”代表個體的目標函數(shù),“種子”代表野草繁殖產(chǎn)生的后代。在進化過程中,野草通過不斷繁殖產(chǎn)生后代種子,種子通過空間擴散分布在搜索空間中,種子繼續(xù)生長成為野草。該過程一直迭代反復(fù),當野草數(shù)量超過環(huán)境資源的承受能力時,通過優(yōu)勝劣汰將適應(yīng)度較好的野草留下,而適應(yīng)度較差的野草被環(huán)境淘汰[20]。一般地,IWO算法包括以下4個步驟。

步驟一:在D維搜索空間中隨機產(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為當前野草的適應(yīng)值;Fmax和Fmin分別表示當前種群中野草的最大適應(yīng)值和最小適應(yīng)值;Nmax和Nmin分別為單個野草產(chǎn)生的種子數(shù)的最大值和最小值。

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

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

(2)

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

步驟四:經(jīng)過itermax次生長繁殖產(chǎn)生的野草后代數(shù)量將超過環(huán)境資源的承受力,需要通過最大種群數(shù)目Pmax控制種群數(shù)量。即將種群中所有野草按適應(yīng)值以降序排列,適應(yīng)值最好的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)解空間距離較小的個體有較高的適應(yīng)值。

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

(3)

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

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

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

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

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

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

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

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

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

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)典的復(fù)雜優(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算法初始信息設(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種隨機搜索算法對4種測試函數(shù)的適應(yīng)值隨總進化代數(shù)iter變化的進化曲線。對每種測試函數(shù)均獨立運行100次,并計算其平均最優(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種算法具有較好的全局搜索能力,快速的收斂速度以及較高的計算精度。

4 結(jié)束語

針對野草優(yōu)化隨機搜索算法在局部搜索能力上的缺陷,提出了一種基于免疫進化的野草優(yōu)化隨機搜索算法。該算法通過對野草群體最優(yōu)個體進行迭代進化計算,增加了解空間搜索密度,提高了群體多樣性,且有效避免了算法的不成熟收斂,能以更高的精度逼近全局最優(yōu)解。通過對4個典型測試函數(shù)進行數(shù)值尋優(yōu)實驗,結(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].計算機輔助設(shè)計與圖形學(xué)學(xué)報,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].計算機學(xué)報,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è)計問題的入侵性雜草優(yōu)化算法[J].中國科學(xué)技術(shù)大學(xué)學(xué)報,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計算模型的研究及應(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].同濟大學(xué)學(xué)報:自然科學(xué)版,2010,38(11):1689-1693.

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

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

猜你喜歡
測試函數(shù)搜索算法野草
小心野草
大灰狼畫報(2022年5期)2022-08-06 07:42:16
改進的和聲搜索算法求解凸二次規(guī)劃及線性規(guī)劃
李建國:誓把“野草”變身致富草
我種了一棵野草
一束野草
具有收縮因子的自適應(yīng)鴿群算法用于函數(shù)優(yōu)化問題
帶勢函數(shù)的雙調(diào)和不等式組的整體解的不存在性
約束二進制二次規(guī)劃測試函數(shù)的一個構(gòu)造方法
基于汽車接力的潮流轉(zhuǎn)移快速搜索算法
基于逐維改進的自適應(yīng)步長布谷鳥搜索算法
汉沽区| 江津市| 喜德县| 大新县| 桑植县| 宁德市| 沿河| 商水县| 北票市| 郁南县| 台南县| 南通市| 曲松县| 北京市| 永康市| 泽州县| 高邮市| 姜堰市| 寻乌县| 灌云县| 板桥市| 北辰区| 彭山县| 潢川县| 高雄市| 龙门县| 康平县| 岚皋县| 开化县| 酉阳| 儋州市| 吉隆县| 松江区| 潮安县| 鹿泉市| 乐清市| 张家界市| 蓝田县| 南澳县| 博白县| 龙岩市|