基于文化算法的改進(jìn)遺傳人工魚(yú)群優(yōu)化算法

劉全明,賀劍強(qiáng),張虎

(山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院,山西 太原 030006)

0 引言

函數(shù)優(yōu)化問(wèn)題作為一種常見(jiàn)的目標(biāo)優(yōu)化求解問(wèn)題,廣泛應(yīng)用于各領(lǐng)域,工程、控制、決策等領(lǐng)域的大多數(shù)問(wèn)題都能通過(guò)分析與抽象轉(zhuǎn)換成函數(shù)優(yōu)化問(wèn)題[1]。傳統(tǒng)的函數(shù)求解方法要求目標(biāo)函數(shù)具備一系列苛刻的條件,這導(dǎo)致部分不具備相關(guān)性質(zhì)的函數(shù)求解困難,不易求得全局最優(yōu)解。20世紀(jì)中后期以來(lái),一部分學(xué)者從仿生學(xué)的運(yùn)行機(jī)制中得到啟式,提出了一系列基于種群優(yōu)化的計(jì)算方法,如遺傳算法，人工免疫算法，粒子群算法，模擬退火算法，人工魚(yú)群算法等,將這些基于種群優(yōu)化的智能算法運(yùn)用到函數(shù)求解后取得較好的結(jié)果。但是由于被優(yōu)化函數(shù)的多樣性和復(fù)雜性,在實(shí)際使用中所有算法都或多或少地表現(xiàn)出了優(yōu)勢(shì)與不足。

人工魚(yú)群算法[2](artificial fish swarm algorithm,AFSA)是我國(guó)學(xué)者李曉磊等人于2002年提出的一種基于魚(yú)群自主尋優(yōu)的群體優(yōu)化算法,被廣泛應(yīng)用于多個(gè)優(yōu)化計(jì)算領(lǐng)域,該算法實(shí)現(xiàn)簡(jiǎn)單,魯棒性強(qiáng),對(duì)初值、參數(shù)不敏感。但是研究發(fā)現(xiàn)人工魚(yú)群存在兩個(gè)明顯缺點(diǎn):(1)當(dāng)函數(shù)最優(yōu)解所在范圍較大或相對(duì)平穩(wěn)時(shí),算法收斂緩慢,搜索結(jié)果精度不高;(2)算法在運(yùn)行初期收斂速度較快,能快速收斂到最優(yōu)解周?chē)?但是后期收斂緩慢還可能出現(xiàn)不收斂現(xiàn)象。目前,已有部分學(xué)者提出一些改進(jìn)算法,來(lái)克服基本魚(yú)群算法的缺點(diǎn)。文獻(xiàn)[3]中將粒子群算法中粒子的尋優(yōu)方式引入,改進(jìn)人工魚(yú)個(gè)體的覓食、聚群、追尾等行為,使得改進(jìn)后的人工魚(yú)個(gè)體,只需依據(jù)自身視野進(jìn)行位置更新,避免了固定步長(zhǎng)給算法性能帶來(lái)的影響。文獻(xiàn)[4-5]通過(guò)對(duì)人工魚(yú)自身聚群、追尾、覓食行為的改進(jìn)來(lái)達(dá)到更好的效果。文獻(xiàn)[6-8]引入遺傳算法的交叉、變異算子,當(dāng)人工魚(yú)最優(yōu)個(gè)體在連續(xù)多次迭代中改變程度低于預(yù)期或者保持不變時(shí),則停止算法迭代,并保留最優(yōu)個(gè)體狀態(tài),將剩余個(gè)體中的一部分按一定概率進(jìn)行交叉、變異操作。此方法通過(guò)引入遺傳算法中的交叉、變異算子,讓人工魚(yú)個(gè)體實(shí)現(xiàn)了突變,從而使得算法后期個(gè)體改變較慢的問(wèn)題得到解決,人工魚(yú)收斂速度加快的同時(shí)算法收斂精度也得以提高。文獻(xiàn)[9-10]通過(guò)引入粒子群算法,將初始種群隨機(jī)分成兩個(gè)不同的子種群,分別利用粒子群算法和人工魚(yú)群算法進(jìn)行優(yōu)化。計(jì)算結(jié)束后,比較兩個(gè)算法得到的最優(yōu)值,將其中的較優(yōu)值代替公告板中當(dāng)前最優(yōu)值,用作下一次比較使用。其變異算子是將兩組種群中最差的5個(gè)個(gè)體按照一定的概率進(jìn)行變異,變異結(jié)束后加入各自種群。此算法雖然對(duì)兩個(gè)算法的缺點(diǎn)起到一定的改進(jìn)作用,但是也會(huì)使得局部最優(yōu)解形成聚集效應(yīng),導(dǎo)致算法失去應(yīng)有的作用,并且兩個(gè)算法各自單獨(dú)進(jìn)化,沒(méi)有對(duì)算法缺點(diǎn)有根本性的改變。

遺傳算法(genetic algorithm,GA)是由Holland教授模擬自然界中物種的選擇進(jìn)化和基因傳播提出的一種仿生智能優(yōu)化算法,通過(guò)模擬物競(jìng)天擇的自然選擇法則來(lái)搜索最優(yōu)解[11]。遺傳算法的優(yōu)點(diǎn)是具有較強(qiáng)的全局收斂能力,對(duì)問(wèn)題領(lǐng)域不敏感,魯棒性強(qiáng);搜索過(guò)程從解的串集出發(fā),不是從單個(gè)解個(gè)體出發(fā),同時(shí)處理種群中的多個(gè)個(gè)體有助于找到全局最優(yōu)解,同時(shí)使得算法易于并行化;對(duì)最優(yōu)個(gè)體的評(píng)價(jià)采用適應(yīng)度函數(shù),不受其他無(wú)關(guān)信息影響,使得遺傳算法適用性大大增加。但是由于遺傳算法采用遺傳機(jī)理進(jìn)行計(jì)算,編碼和解碼會(huì)增大算法的復(fù)雜度影響效率,同時(shí)遺傳算法對(duì)進(jìn)化過(guò)程中系統(tǒng)的反饋信息未能加以利用。

綜合分析人工魚(yú)群算法和遺傳算法的優(yōu)缺點(diǎn),本文將引入文化算法作為基本框架,利用文化算法的雙層進(jìn)化機(jī)制,建立遺傳算法演化的信仰空間和人工魚(yú)群算法演化的種群空間,種群空間通過(guò)接受函數(shù)不斷向信仰空間貢獻(xiàn)精英個(gè)體,信仰空間通過(guò)自身演化并利用影響函數(shù)來(lái)指導(dǎo)種群空間,最終形成雙演化雙促進(jìn)的雙層進(jìn)化機(jī)制。改進(jìn)算法充分利用了遺傳算法全局搜索能力強(qiáng),搜索精度高和人工魚(yú)群算法初期收斂速度快的優(yōu)點(diǎn),使得改進(jìn)后的算法比原算法搜索速度更快,精度更高。

1 算法基本原理

1.1 人工魚(yú)群算法

人工魚(yú)群算法把實(shí)際待優(yōu)化問(wèn)題中的解抽象成一條人工魚(yú),每條人工魚(yú)的位置狀態(tài)可以用向量X=(x1,x2,…,xn)來(lái)表示,其中xi(i=1,…,n)表示待尋優(yōu)的變量,人工魚(yú)當(dāng)前所在位置的食物濃度Y=f(X)其中Y為目標(biāo)函數(shù)值;di,j=‖Xi-Xj‖表示兩條人工魚(yú)之間的距離;V表示人工魚(yú)的感知視野;S表示人工魚(yú)的移動(dòng)步長(zhǎng);δ表示食物周?chē)膿頂D度因子。每條人工魚(yú)通過(guò)模擬魚(yú)的覓食、聚群、追尾和隨機(jī)移動(dòng)行為來(lái)尋找最優(yōu)適應(yīng)度從而達(dá)到搜素優(yōu)化的目的。

覓食行為:設(shè)當(dāng)前人工魚(yú)所在位置為Xi,在視野范圍內(nèi)隨機(jī)尋找位置Xj,在求極大值尋優(yōu)問(wèn)題中,如果Yj>Yi,按公式(1)更新人工魚(yú)所在位置;反之,則在視野范圍內(nèi)重新嘗試尋找位置Xj,判斷新的Xj是否滿足更新條件,設(shè)最大嘗試次數(shù)為T(mén)r，當(dāng)進(jìn)行Tr次嘗試后依然無(wú)法找到滿足條件的Xj,即Yj

(1)

聚群行為:設(shè)當(dāng)前人工魚(yú)所在位置為Xi,nf和Xc分別表示視野范圍內(nèi)(即di,jδYi,則按公式(2)更新人工魚(yú)所在位置,否則執(zhí)行覓食行為。

(2)

追尾行為:設(shè)當(dāng)前人工魚(yú)所在位置為Xi,搜尋自身視野范圍內(nèi)食物濃度值Ym最大的人工魚(yú)Xm,并以Xm為中心搜尋其視野范圍內(nèi)的人工魚(yú)數(shù)目nf,如果Ym/nf>δYi則表明Xm處食物濃度較大且不擁擠,按公式(3)向Xj的方向移動(dòng)一步,否則執(zhí)行覓食行為。

(3)

隨機(jī)行為:在當(dāng)前人工魚(yú)視野內(nèi)隨機(jī)選擇一條人工魚(yú),并以所選人工魚(yú)為目標(biāo)移動(dòng)一步,是覓食行為的默認(rèn)行為。

更新公告板:每次迭代結(jié)束后,比較當(dāng)前最優(yōu)解和公告板,若當(dāng)前最優(yōu)解優(yōu)于公告板則將公告板用當(dāng)前最優(yōu)解替換。

1.2 遺傳算法

遺傳算法基本流程為:

(1)個(gè)體編碼。種群中的每一個(gè)個(gè)體代表解集中的一個(gè)解,在遺傳算法運(yùn)行時(shí)需要將個(gè)體編碼為二進(jìn)制的染色體,利用編碼好的二進(jìn)制串進(jìn)行運(yùn)算。

(2)初始化種群。根據(jù)實(shí)際問(wèn)題的規(guī)模,設(shè)定種群的大小,并初始化種群個(gè)體。

(3)適應(yīng)度計(jì)算。每次迭代過(guò)程中,利用適應(yīng)度函數(shù)計(jì)算每個(gè)個(gè)體的適應(yīng)度。

(4)遺傳算子(選擇、交叉、變異)

a)選擇:選擇算子從舊種群中按一定概率選擇優(yōu)秀個(gè)體組成新的種群進(jìn)行繁殖產(chǎn)生新一代種群。選擇過(guò)程中個(gè)體被選中的概率與適應(yīng)度值成正比。

b)交叉:交叉算子從種群中隨機(jī)選擇兩個(gè)個(gè)體,選擇交叉點(diǎn),并將交叉點(diǎn)處染色體互換,產(chǎn)生新個(gè)體。

c)變異:變異算子隨機(jī)從種群中選擇一個(gè)個(gè)體,將個(gè)體的部分染色體進(jìn)行變異,通過(guò)變異操作產(chǎn)生新的優(yōu)秀個(gè)體,同時(shí)保持種群多樣性。

2 基于文化算法框架的遺傳魚(yú)群算法

2.1 文化算法

自然界給人類(lèi)提供了許多仿生智能計(jì)算的靈感,關(guān)于這方面的研究大多數(shù)集中在種群的自然選擇層面上。隨著時(shí)間的推移,人類(lèi)在自身發(fā)展過(guò)程中通過(guò)對(duì)信息知識(shí)的采集、提取、編碼和傳播,逐漸形成了共同的知識(shí)結(jié)晶,這種超越種群層面的知識(shí)積累與傳播是自然界其他生物所不具備的。正是這種能力使得人類(lèi)社會(huì)高速發(fā)展,形成了現(xiàn)如今高度發(fā)達(dá)的文明。

文化算法模擬人類(lèi)文明的發(fā)展,在傳統(tǒng)的種群空間之上引入可以進(jìn)行知識(shí)積累、進(jìn)化和傳播的信仰空間,形成雙層進(jìn)化機(jī)制。信仰空間通過(guò)接受函數(shù)獲得種群空間進(jìn)化過(guò)程中積累的知識(shí),把這些知識(shí)保存并加以演化,最終用于影響和指導(dǎo)種群空間進(jìn)化[11]。

文化算法總體包括三部分:種群空間、信仰空間和溝通渠道,其中溝通渠道又包括影響函數(shù)和接受函數(shù)兩部分。種群空間和信仰空間分別從微觀和宏觀兩個(gè)層面模擬人類(lèi)社會(huì)的發(fā)展進(jìn)化,在進(jìn)化過(guò)程中保持相對(duì)獨(dú)立,通過(guò)溝通渠道進(jìn)行相互作用。

2.2 文化算法框架下的改進(jìn)遺傳人工魚(yú)群算法(CA_GAFSA)

文化算法的雙層進(jìn)化機(jī)制給基于種群的進(jìn)化算法提供改進(jìn)的靈感和條件。通過(guò)分析發(fā)現(xiàn)蟻群算法、粒子群算法、人工蜂群算法等都是通過(guò)模仿特定生物群體中個(gè)體的行為來(lái)優(yōu)化待求解問(wèn)題,這樣使得最優(yōu)解容易集中到局部最優(yōu)解附近陷入局部收斂;而遺傳算法通過(guò)選擇、交叉、變異操作,在給種群加入新的優(yōu)秀個(gè)體時(shí)具有一定的隨機(jī)性,有利于跳出局部最優(yōu)值,從而達(dá)到全局收斂。因此本文提出的改進(jìn)算法模型主要是基于文化算法的框架結(jié)構(gòu),建立以遺傳算法優(yōu)化的信仰空間和以人工魚(yú)群算法優(yōu)化的種群空間。經(jīng)遺傳算法初始化信仰空間、人工魚(yú)群算法優(yōu)化種群空間后,通過(guò)適應(yīng)度函數(shù)評(píng)價(jià)種群空間中的個(gè)體適應(yīng)度,每次迭代過(guò)程中將種群空間中的最優(yōu)個(gè)體通過(guò)接受函數(shù)傳遞給信仰空間,信仰空間通過(guò)遺傳算法演化后每隔一定時(shí)間將積累的優(yōu)秀個(gè)體通過(guò)影響函數(shù)反饋給種群空間,種群空間利用更新后的新種群繼續(xù)演化,并不斷向信仰空間傳遞最優(yōu)個(gè)體,整個(gè)過(guò)程不斷重復(fù),直到滿足結(jié)束條件,算法終止。

改進(jìn)后的算法流程描述如下:

(1)種群空間初始化:種群空間采用人工魚(yú)群算法演化,編碼方式采用十進(jìn)制方式。在求解問(wèn)題變量空間域內(nèi)隨機(jī)初始化N個(gè)人工魚(yú)個(gè)體(問(wèn)題的N個(gè)初始解),并計(jì)算適應(yīng)度值。設(shè)定人工魚(yú)最大視野V,移動(dòng)步長(zhǎng)S,最大嘗試次數(shù)Tr,擁擠度因子δ。

(2)信仰空間初始化:信仰空間采用遺傳算法演化,編碼方式采用二進(jìn)制方式。在求解問(wèn)題變量空間域內(nèi)隨機(jī)初始化一定數(shù)量的個(gè)體(問(wèn)題的解),數(shù)量規(guī)模取種群空間個(gè)體數(shù)量的20%到30%。

(3)定義接受函數(shù)。每次種群空間和信仰空間更新結(jié)束后,信仰空間接受種群空間中的當(dāng)前最優(yōu)解,替換自身當(dāng)前最劣解。

(4) 定義影響函數(shù)。每迭代5次,用信仰空間中適應(yīng)度排名前T個(gè)(本文取T=5)個(gè)體(問(wèn)題的解)將種群空間中等量的適應(yīng)度較差的個(gè)體(問(wèn)題的解)進(jìn)行替換。

(5)迭代求解:

a)種群空間更新。當(dāng)滿足條件時(shí),運(yùn)行影響函數(shù)。然后利用人工魚(yú)群算法對(duì)種群空間進(jìn)行演化(新的一次求解過(guò)程)。

b)信仰空間更新。運(yùn)行接受函數(shù),然后利用遺傳算法對(duì)信仰空間進(jìn)行演化(新的一次求解過(guò)程)。

(6)更新公告板。每次迭代完成后比較當(dāng)前公告板的值和種群空間中的最優(yōu)值,并將兩者中的較優(yōu)值賦給公告板。

(7)判斷終止條件。比較終止條件和公告板上的值,如果滿足終止要求,算法終止;否則重復(fù)步驟(5)-(7),直到滿足終止條件。

(8)算法終止,將最優(yōu)值和其對(duì)應(yīng)的狀態(tài)值輸出。

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證本文算法的有效性,本實(shí)驗(yàn)采用的實(shí)驗(yàn)平臺(tái)處理器為AMD處理器,主頻2.35 GHz,內(nèi)存大小4 GB,操作系統(tǒng)為Windows10家庭中文版,程序運(yùn)行環(huán)境為Matlab R2014a。

同時(shí)選取了4個(gè)具有代表性的基準(zhǔn)測(cè)試函數(shù),通過(guò)兩種不同的測(cè)試方法來(lái)評(píng)價(jià)改進(jìn)算法和其他算法對(duì)測(cè)試函數(shù)的優(yōu)化性能[13]:(1)在固定迭代次數(shù)下,比較優(yōu)化函數(shù)的最優(yōu)值、平均值和最差值,通過(guò)比較可以從一定程度上反映出優(yōu)化算法的搜索精度和速度;(2)成功率和迭代次數(shù),成功率指在指定的求解精度以及最大迭代次數(shù)下,算法優(yōu)化結(jié)果達(dá)到預(yù)定精度的次數(shù)和總的測(cè)試次數(shù)的比值,此項(xiàng)指標(biāo)可在一定程度上反映出算法的可靠性,達(dá)到指定精度的下的平均迭代次數(shù)可反映出算法的進(jìn)化速度。本文選取的四個(gè)基準(zhǔn)測(cè)試函數(shù)如表1所示:

表1 基準(zhǔn)測(cè)試函數(shù)Table 1 Benchmark function

3.2 結(jié)果分析

本文對(duì)四個(gè)基準(zhǔn)函數(shù)進(jìn)行測(cè)試過(guò)程中遺傳算法采用謝菲爾德遺傳算法工具箱,其中參數(shù)設(shè)置均為:變量的二進(jìn)制編碼位數(shù)PRECI=20,選擇算子代溝GGAP=0.95,交叉概率px=0.7,變異概率pm=0.1。分別對(duì)兩個(gè)二維函數(shù)和兩個(gè)多維函數(shù)進(jìn)行測(cè)試,驗(yàn)證本文算法對(duì)不同變量維度函數(shù)的優(yōu)化性能,并將文獻(xiàn)[4]和[15]中的兩種改進(jìn)算法與基本魚(yú)群算法加入對(duì)比,以驗(yàn)證本文算法相對(duì)于其他改進(jìn)算法的性能優(yōu)勢(shì)。

3.2.1 二維函數(shù)優(yōu)化分析

函數(shù)f1為多模態(tài)函數(shù),存在多個(gè)極小值點(diǎn),但是最小值只有一個(gè)。因其最小值周?chē)幸粋€(gè)環(huán)形的波谷,在函數(shù)求解中很容易陷入局部極小值[18],因此該函數(shù)常被當(dāng)作基準(zhǔn)函數(shù)檢驗(yàn)算法的性能。在測(cè)試過(guò)程中,遺傳算法參數(shù)設(shè)置如前所述,人工魚(yú)群算法參數(shù)均設(shè)置為:人工魚(yú)個(gè)數(shù)N=100,最大嘗試次數(shù)Tr=100,視野V=1,步長(zhǎng)S=0.3,擁擠度因子δ=0.618,實(shí)驗(yàn)獨(dú)立進(jìn)行30次。迭代次數(shù)取50次和100次的結(jié)果如表2所示。尋優(yōu)精度分別為0.000 1和0.000 01時(shí)結(jié)果比較如表3所示。迭代次數(shù)取50次和100次時(shí)算法的平均最優(yōu)值隨迭代次數(shù)的變化曲線分別如圖1和圖2所示。

表2 固定迭代次數(shù)下四種算法比較Table 2 Comparison of four algorithms under fixed iteration times

表3 固定精度下四種算法比較Table 3 Comparison of four algorithms under fixed precision

Fig.1 Change curve of average optimal solution圖1 平均最優(yōu)解變化曲線

Fig.2 Change curve of average optimal solution圖2 平均最優(yōu)解變化曲線

函數(shù)f2在測(cè)試過(guò)程中,遺傳算法參數(shù)設(shè)置如前所述,人工魚(yú)群算法參數(shù)均設(shè)置為:人工魚(yú)個(gè)數(shù)N=100,最大嘗試次數(shù)Tr=100,視野V=2.97,步長(zhǎng)S=1.31,擁擠度因子δ=0.618,實(shí)驗(yàn)獨(dú)立進(jìn)行30次。迭代次數(shù)取50次和100次的結(jié)果如表4所示。尋優(yōu)精度分別為199.999和199.999 9時(shí)的結(jié)果比較如表5所示。迭代次數(shù)取50次和100次時(shí)的平均最優(yōu)值隨迭代次數(shù)的變化曲線分別如圖3和圖4所示。

表4 固定迭代次數(shù)下四種算法比較Table 4 Comparison of four algorithms under fixed iteration times

表5 固定精度下四種算法比較Table 5 Comparison of four algorithms under fixed precision

Fig.3 Change curve of average optimal solution圖3 平均最優(yōu)解變化曲線

Fig.4 Change curve of average optimal solution圖4 平均最優(yōu)解變化曲線

從表2和表3可以看出,對(duì)于函數(shù)f1本文提出的算法結(jié)果在最優(yōu)值、平均值、最差值上均優(yōu)于文中的對(duì)比算法,在尋優(yōu)精度方面同樣高于對(duì)比算法。從表4、表5可以看出,對(duì)于函數(shù)f2雖然三種對(duì)比算法也取得較好的優(yōu)化結(jié)果,但是在各對(duì)比項(xiàng)中本文算法還是全面優(yōu)于其他三種對(duì)比算法,表現(xiàn)出很好的優(yōu)化能力。從圖1-4可以看出在相同迭代次數(shù)下本文算法的迭代速度更快,更加接近最優(yōu)解。表明本文算法具有更高的精度、更快的搜索速度和更好的可靠性。

3.2.2 多維函數(shù)優(yōu)化分析

函數(shù)f3在測(cè)試過(guò)程中,遺傳算法參數(shù)設(shè)置如前所述,人工魚(yú)群算法參數(shù)均設(shè)置為:人工魚(yú)個(gè)數(shù)N=100,最大嘗試次數(shù)Tr=50,視野V=1.5,步長(zhǎng)S=1,擁擠度因子δ=0.618,實(shí)驗(yàn)獨(dú)立進(jìn)行30次。當(dāng)變量維數(shù)分別取10和20時(shí),迭代次數(shù)分別取1 000次和1 500次的結(jié)果如表6所示。圖5中按從左到右、從上到下的順序四幅圖分別表示變量維數(shù)取10維迭代次數(shù)取1 000次、變量維數(shù)取10維迭代次數(shù)取1 500次、變量維數(shù)取2維迭代次數(shù)取1 000次、變量維數(shù)取2維迭代次數(shù)取1 500次時(shí)四種算法的平均最優(yōu)值隨迭代次數(shù)的變化曲線。

函數(shù)f4在測(cè)試過(guò)程中,遺傳算法參數(shù)設(shè)置如前所述,人工魚(yú)群算法參數(shù)均設(shè)置為:人工魚(yú)個(gè)數(shù)N=100,最大嘗試次數(shù)Tr=100,視野V=20,步長(zhǎng)S=2,擁擠度因子δ=0.618,實(shí)驗(yàn)獨(dú)立進(jìn)行30次。當(dāng)變量維數(shù)取10和20時(shí),基本魚(yú)群算法和本文算法迭代1 000次和1 500次的結(jié)果如表7所示。圖6中按從左到右、從上到下的順序四幅圖分別表示變量維數(shù)取10維迭代次數(shù)取1 000次、變量維數(shù)取10維迭代次數(shù)取1 500次、變量維數(shù)取2維迭代次數(shù)取1 000次、變量維數(shù)取2維迭代次數(shù)取1 500次時(shí)四種算法的平均最優(yōu)值隨迭代次數(shù)的變化曲線。

表6 四種算法比較Table 6 Comparison of four algorithms

Fig.5 Change curve of average optimal solution圖5 平均最優(yōu)解變化曲線

由表6可以看出對(duì)函數(shù)f3來(lái)說(shuō),在變量維數(shù)增加到10維和20維時(shí),本文算法優(yōu)化結(jié)果優(yōu)于其他三種對(duì)比算法,且隨著迭代次數(shù)的增加本文算法的結(jié)果依然不斷向最優(yōu)值收斂,展現(xiàn)了本文算法在迭代后期良好的收斂性;而其他三種算法在增加迭代次數(shù)的同時(shí),優(yōu)化結(jié)果并沒(méi)有太大的改變,其中文獻(xiàn)[4]中算法出現(xiàn)一定的退化,表明算法后期收斂能力的弱化,甚至不再繼續(xù)收斂。圖6展現(xiàn)了在相同迭代次數(shù)下,本文算法收斂精度明顯好于其他對(duì)比算法,表明本文算法收斂速度更快。由表7可以看出對(duì)于函數(shù)f4來(lái)說(shuō),在變量維數(shù)取到10 時(shí)四種算法均取得很好的優(yōu)化結(jié)果,文獻(xiàn)[4]中算法的最優(yōu)值比本文算法結(jié)果還要好,但是其平均值和最差值卻劣于本文算法結(jié)果,甚至出現(xiàn)最差值完全不收斂的情況。在函數(shù)f4變量維數(shù)取到20維時(shí),本文算法結(jié)果依然在接受范圍內(nèi),而其他三種對(duì)比算法的求解結(jié)果卻距離最優(yōu)值相差甚遠(yuǎn),完全沒(méi)有起到優(yōu)化求解的效果。

表7 四種算法比較Table 7 Comparison of four algorithms

Fig.6 Change curve of average optimal solution圖6 平均最優(yōu)解變化曲線

綜上分析,本文算法對(duì)比其他三種算法在對(duì)文中四個(gè)基準(zhǔn)測(cè)試函數(shù)優(yōu)化過(guò)程中,雖然極個(gè)別結(jié)果稍微劣于對(duì)比算法,但總體上本文算法對(duì)于四個(gè)測(cè)試函數(shù)都能起到很好的優(yōu)化求解結(jié)果,針對(duì)不同情況都能表現(xiàn)出較為均衡的優(yōu)化能力,魯棒性更強(qiáng)。對(duì)于算法的收斂速度,由于人工魚(yú)群算法作為仿生學(xué)算法的一種,其算法行為都是模仿自然界中動(dòng)物的生活習(xí)性來(lái)設(shè)計(jì)提出,理論性較弱,但是可以從圖1-6中函數(shù)最優(yōu)值隨迭代次數(shù)的變化曲線上直觀看出,本文算法相對(duì)其他三種對(duì)比算法在相同迭代次數(shù)下迭代結(jié)果更優(yōu),同時(shí)在取得相同的迭代精度時(shí)需要更少的迭代次數(shù),表明本文算法具有更快的迭代速度。

4 結(jié)論

利用文化算法模型的雙層進(jìn)化機(jī)制,提出了一種基于文化算法框架的改進(jìn)人工魚(yú)群算法,旨在解決基本人工魚(yú)群算法存在的缺點(diǎn)。通過(guò)4個(gè)基準(zhǔn)測(cè)試函數(shù)的優(yōu)化實(shí)驗(yàn)表明:本文算法相比三種對(duì)比算法來(lái)說(shuō)優(yōu)化結(jié)果精度更高,算法收斂速度更快,魯棒性更強(qiáng);尤其是對(duì)于高維函數(shù),其他三種算法優(yōu)化結(jié)果較差甚至無(wú)法優(yōu)化,本文算法優(yōu)化結(jié)果精度較高且收斂速度較快。

參考文獻(xiàn)：

[1] 劉白,周永權(quán).基于遺傳算法的人工魚(yú)群優(yōu)化算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,29(2):5827-5829. DOI:10.16208/j.issn1000-7024.2008.22.077.

[2] 李曉磊,邵之江,錢(qián)積新.一種基于動(dòng)物自治體的尋優(yōu)模式:魚(yú)群算法[J].系統(tǒng)工程理論與實(shí)踐,2002,22(11):32-38.DOI:10.3321/j.issn:1000-6788.2002.11.007.

[3] 姚衛(wèi)紅,方仁孝,張旭東.基于混合人工魚(yú)群優(yōu)化SVR的交通流量預(yù)測(cè)[J].大連理工大學(xué)學(xué)報(bào),2015,55(6):632-637.DOI:10.7511/dllgxb201506011.

[4] 黃美華,溫潔娥,何勇.求解多目標(biāo)背包問(wèn)題的改進(jìn)人工魚(yú)群算法[J]廣東工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,33(5):44-48.DOI:10.3969/j.issn.1007-7162.2016.05.008.

[5] 劉東林,李樂(lè)樂(lè).一種新穎的改進(jìn)人工魚(yú)群算法[J].計(jì)算機(jī)科學(xué),2017,44(4):281-287. DOI:10.11896/j.issn.1002-137X.2017.04.058.

[6] 吳旭,洪聯(lián)系,魏德志,等.改進(jìn)的人工魚(yú)群混合算法在智能組卷中的應(yīng)用[J]集美大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,17(5):394-400.DOI:10.3969/j.issn.1007-7405.2012.05.013.

[7] 姚麗莎,王占鳳,程家興.基于人工魚(yú)群遺傳算法的異構(gòu)多核系統(tǒng)任務(wù)調(diào)度研究[J].計(jì)算機(jī)工程與科學(xué),2014,36(10):1866-1871.DOI:10.3969/j.issn.1007-130X.2014.10.005.

[8] 姜山,季業(yè)飛.改進(jìn)的人工魚(yú)群混合算法在交通分配中的應(yīng)用[J].計(jì)算機(jī)仿真,2011,28(6):326-329. DOI:10.3969/j.issn.1006-9348.2011.06.080.

[9] 羅德相,周永權(quán),黃華娟.粒子群和人工魚(yú)群混合優(yōu)化算法[J].計(jì)算機(jī)與應(yīng)用化學(xué),2009,26(10):1257-1261. DOI:10.3969/j.issn.1001-4160.2009.10.011.

[10] 洪蕾粒.子群及人工魚(yú)群算法優(yōu)化研究[J].軟件,2014,35(8):83-86.DOI:10.3969/j.issn.1003-6970.2014.08.019.

[11] Holland J.Genetic Algorithms,Gomputer Programs that Evolve in Ways that Even Their Greators do Not Fully Understand[J].ScientificAmerican,1975(267):66-72.

[12] Reynolds R G.An Introduction to Cultural Algorithms[C]∥Proceedings of the Third Annual Conferenceon Evolutionary Programming,World Scientific.River Edge,New Jersey:[s.n.],1994:131-139.DOI:10.1136/ewjm.172.5.335.

[13] 陳雷.基于群智能優(yōu)化方法的盲信號(hào)分離算法研究[D].天津：天津大學(xué)，2011.

[14] 費(fèi)騰,張立毅,白煜,等.基于DNA的改進(jìn)人工魚(yú)群算法[J].天津大學(xué)學(xué)報(bào)(自然科學(xué)與工程技術(shù)版),2016,49(6):581-588.DOI:10.11784/tdxbz201501007.

[15] 鄧濤,姚宏,杜軍.多峰函數(shù)優(yōu)化的改進(jìn)人工魚(yú)群混合算法[J].計(jì)算機(jī)應(yīng)用,2012,32(10):2904-2906,2910.DOI:10.3724/SP.J.1087.2012.02904.

[16] Mao M,Duan Q,Yang Z,etal.Modeling and Global MPPT for PV System under Partial Shading Conditions using Modified Artificial Fish Swarm Algorithm[C]∥IEEE International Symposium on Systems Engineering.IEEE,2016:1-7.

[17] Azizi R.Empirical Study of Artificial Fish Swarm Algorithm[J].ComputerScience,2014,17(6):626-641.

[18] 張嚴(yán),楚曉麗.一種改進(jìn)的人工魚(yú)群算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2011,20(5):199-201. DOI:10.3969/j.issn.1003-3254.2011.05.046.