一種新型的果蠅優(yōu)化算法

張曉茹，張著洪

(1.貴州大學(xué) 理學(xué)院，貴州 貴陽 550025；2.貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽 550025)

?

一種新型的果蠅優(yōu)化算法

張曉茹1，張著洪2*

(1.貴州大學(xué) 理學(xué)院，貴州 貴陽 550025；2.貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽 550025)

針對(duì)維數(shù)較高的單目標(biāo)非約束函數(shù)優(yōu)化問題, 探討一種易于應(yīng)用的新型果蠅優(yōu)化算法。算法設(shè)計(jì)中，優(yōu)質(zhì)種群經(jīng)由局部變異增強(qiáng)探測(cè)能力；中等種群經(jīng)由優(yōu)質(zhì)種群有引導(dǎo)性地實(shí)現(xiàn)個(gè)體轉(zhuǎn)移；劣質(zhì)種群經(jīng)由均勻變異展開多方位搜尋多樣個(gè)體。比較性的數(shù)值實(shí)驗(yàn)顯示, 該算法求解偏高維函數(shù)優(yōu)化問題具有一定的優(yōu)勢(shì)。

果蠅優(yōu)化; 函數(shù)優(yōu)化; 多模態(tài)

基本果蠅優(yōu)化算法(Basic Fly Optimization Algorithm, BFOA)[1]因其結(jié)構(gòu)簡(jiǎn)單、可操作性強(qiáng)等優(yōu)點(diǎn)，已受到智能優(yōu)化學(xué)者的足夠重視。該算法主要涉及果蠅嗅覺感知食物遠(yuǎn)近和視覺感知食物所在方位等生物機(jī)理，被用于解決決策區(qū)域?yàn)閷?duì)稱區(qū)域的連續(xù)函數(shù)優(yōu)化問題[2]。但此算法極大依賴于果蠅與食物源之間的距離且算法中個(gè)體間信息交互能力弱等，使得其易于陷入局部搜索。如何通過個(gè)體多樣化的更新策略，增強(qiáng)算法跳出局部搜索的能力，以及深入研究算法的理論基礎(chǔ)、群體多樣性、算法應(yīng)用，均有待開展。

本文借鑒果蠅嗅覺對(duì)事物的感知行為和視覺的方向選擇特征，以小種群為進(jìn)化載體，依據(jù)果蠅協(xié)同覓食的生物特征設(shè)計(jì)進(jìn)化框架，力求提出新型果蠅優(yōu)化算法 (Fly Optimization Algorithm, FOA)，解決維數(shù)偏高的函數(shù)優(yōu)化問題。比較性的數(shù)值實(shí)驗(yàn)結(jié)果顯示，該算法獲得的解質(zhì)量具有明顯優(yōu)勢(shì)，對(duì)偏高維函數(shù)優(yōu)化有一定的應(yīng)用潛力。

1　問題描述與果蠅基本理論

考慮如下靜態(tài)優(yōu)化問題(P)

其中，D是Rp中有界閉區(qū)域，x∈D為候選解，x=(x1,x2,…,xp)，f(x)為D上有界、非線性連續(xù)函數(shù)。由于D為有界閉區(qū)域，所以問題(P)必存在最優(yōu)解。

果蠅是一種微小的生物體，能通過嗅覺和味覺感知附近食物源的大體方位和遠(yuǎn)近，通過復(fù)眼捕捉周圍環(huán)境信息。就果蠅的嗅覺而言，嗅覺器官依據(jù)食物源的遠(yuǎn)近，能嗅到40 km以外的食物源[3]；另一方面，果蠅的復(fù)眼是一種極為重要的光感受器，其兩只復(fù)眼是由數(shù)千只小眼組成的兩個(gè)半球，對(duì)稱地分布在頭部的兩側(cè)，每只復(fù)眼都像一個(gè)探測(cè)器，可探測(cè)視角區(qū)內(nèi)的目標(biāo)。

2　算法原理與算法設(shè)計(jì)

FOA由群體分割和種群進(jìn)化兩個(gè)模塊構(gòu)成。群體分割依據(jù)個(gè)體適應(yīng)度將進(jìn)化群體劃分為優(yōu)質(zhì)、中等、劣質(zhì)子群；各子群依據(jù)特定變異方式和歷史信息更新自身位置，并產(chǎn)生新群體。在此，將果蠅視為個(gè)體，并與以上問題(P)的候選解對(duì)應(yīng)，食物源被視為該問題本身。FOA的描述與設(shè)計(jì)如下：

步1輸入?yún)?shù)：群體規(guī)模N, 迭代數(shù)Gmax，選擇率α、β、pm；

步2置n←1,隨機(jī)產(chǎn)生N個(gè)個(gè)體構(gòu)成初始群體An，依據(jù)個(gè)體適應(yīng)度，將An中最好個(gè)體作為當(dāng)前最好個(gè)體xbest；

步3An中α%個(gè)較好個(gè)體構(gòu)成優(yōu)質(zhì)子群A、β%個(gè)較差個(gè)體構(gòu)成劣質(zhì)子群C，其余個(gè)體構(gòu)成中等子群B；

步4優(yōu)質(zhì)子群A更新：對(duì)于A中每一個(gè)體x，對(duì)xbest進(jìn)行單點(diǎn)隨機(jī)變異，例如對(duì)第j個(gè)基因變異：

(1)

步5中等子群B更新：對(duì)于B中每個(gè)個(gè)體x，隨機(jī)抽取A中一個(gè)個(gè)體y，并與xbest一起對(duì)x實(shí)施更新：

x′←y+λ(xbest-x)

(2)

獲群體B*，在此λ是0～1之間的隨機(jī)數(shù)；

步6 種群C中個(gè)體依據(jù)概率pm執(zhí)行如下變異：

x′←(1-Δ)ηx+Δη(b-a)

(3)

步7利用A*∪ B*∪ C*中最好個(gè)體更新xbest；

步8An+1←A*∪B*∪ C*; 若n

該算法借助果蠅嗅覺特征，將當(dāng)前最好個(gè)體視為可能的食物源，群體進(jìn)化中的個(gè)體在此個(gè)體位置和方向的引導(dǎo)下，逐漸向食物源所在方向轉(zhuǎn)移。優(yōu)質(zhì)子群A中的個(gè)體被認(rèn)為距離食物源較近，僅作局部變異；中等子群B在A中個(gè)體的引導(dǎo)下，逐漸向該子群轉(zhuǎn)移；然而，劣質(zhì)子群C則通過均勻變異增加發(fā)現(xiàn)食物源的機(jī)會(huì)和增強(qiáng)群體多樣性的能力，防止算法陷入局部搜索。

3　數(shù)值實(shí)驗(yàn)

在Window XP/CPU 2.50GHz /RAM 3.0GB /VC++環(huán)境下展開數(shù)值實(shí)驗(yàn)。選擇3種近年被報(bào)道的新果蠅優(yōu)化算法FFO[1,3]、IFFO[2]和MFOA[4]參與FOA的比較分析。各算法求解以下各測(cè)試問題的種群規(guī)模均為10，最大迭代數(shù)為300，且均獨(dú)立求解每種測(cè)試問題100次。參與比較的算法的參數(shù)設(shè)置與相應(yīng)文獻(xiàn)的相同；FOA中三個(gè)可調(diào)參數(shù)設(shè)置為α=0.2,β=0.2,pm=0.4。

文獻(xiàn)[2]中的測(cè)試問題F1至F4被用于檢測(cè)以上4種算法的性能：

函數(shù)F1

最優(yōu)解x*=(-2,…,-2), 最小值2(n+2)(n-1)。

函數(shù)F2

最優(yōu)解x*=0, 最小值-1。

函數(shù)F3

-600≤xi≤600,

最優(yōu)解x*=0, 最小值0。

函數(shù)F4

最優(yōu)解x*=0, 最小值1-n。

F1和F2是單模態(tài)函數(shù)優(yōu)化問題；雖然均各自僅有1個(gè)最優(yōu)解，但在維數(shù)較大的情形下，目標(biāo)函數(shù)在決策區(qū)域的大部分區(qū)域上的函數(shù)值較大，算法收斂速度受到極大影響；F3和F4是極為困難的多峰值函數(shù)優(yōu)化問題，其決策變量的耦合性強(qiáng)，多個(gè)局部最優(yōu)解嚴(yán)重干擾算法的全局搜索，加之，當(dāng)維數(shù)較高時(shí)，目標(biāo)函數(shù)在多個(gè)子決策區(qū)域的函數(shù)值較大，特別是F3的決策區(qū)域較大，使得算法求解變得極為困難。

3.130維測(cè)試問題的實(shí)驗(yàn)結(jié)果分析

在F1至F4的維數(shù)均為30下，以上4種算法分別獨(dú)立求解每個(gè)測(cè)試問題100次后，統(tǒng)計(jì)結(jié)果如表1所示；以F1、F4為例，各算法求解每個(gè)測(cè)試問題獲得的100個(gè)目標(biāo)值形成的箱線圖如圖1所示，圖中AE表示各算法獲得的目標(biāo)值與理論最小值的絕對(duì)誤差。

表1　30維測(cè)試問題的統(tǒng)計(jì)結(jié)果比較

注：μ為獨(dú)立運(yùn)行100次后獲得的100個(gè)目標(biāo)值的均值，σ為獨(dú)立運(yùn)行100次后獲得的100個(gè)目標(biāo)值的均方值

圖1　求解30維測(cè)試問題獲得的箱線圖比較

由表1的均值可知，從獲得的解質(zhì)量看，F(xiàn)OA優(yōu)于其它算法；MFOA求解F1-F3 獲得的解質(zhì)量?jī)?yōu)于FFO和IFFO獲得的解質(zhì)量；FFO最差。從搜索效果的穩(wěn)定性看，基于表中的均方差，F(xiàn)OA的搜索效果最穩(wěn)定，MFOA次之，IFFO卻表現(xiàn)出極不穩(wěn)定的搜索行為。另一方面，經(jīng)由圖1獲知，求解F1、F4的最小值時(shí)，F(xiàn)OA獲得的中位線均較其它算法獲得的中位線低，也即所獲得的目標(biāo)值距離理論最優(yōu)值較近，搜索效果最好；再?gòu)南渚€圖的中位線距離下四分位線的遠(yuǎn)近得知，F(xiàn)OA的搜索效果較穩(wěn)定，F(xiàn)FO次之。

3.2100維測(cè)試問題的實(shí)驗(yàn)結(jié)果分析

類似于以上實(shí)驗(yàn)，4種算法的統(tǒng)計(jì)結(jié)果如表2所示，獲得的箱線圖如圖2所示。

表2　100維測(cè)試問題的統(tǒng)計(jì)結(jié)果比較

圖2　求解100維測(cè)試問題獲得的箱線圖比較

與表1中的結(jié)果相比，表2表明，隨著維數(shù)的增加，各算法的搜索效果均有不同程度的退化(除FOA求解函數(shù)F1之外)，尤其是求解F2、F3，參與比較的算法的退化現(xiàn)象較為嚴(yán)重，但FOA整體效果較為穩(wěn)定，受維數(shù)增加的影響較??；從獲得的均方值看，各算法的穩(wěn)定性也有所下降，尤其體現(xiàn)在F1和F3上。FOA除F4外，獲得其它函數(shù)的均方值均較小，尤其求解F1獲得的均方值與其它算法獲得的均方值有較為明顯的差異；經(jīng)由圖2不難發(fā)現(xiàn)，由于FFO、IFFO及MFOA的個(gè)體更新方式單一、群體中個(gè)體整體向當(dāng)前最優(yōu)個(gè)體靠近，致使最終獲得的目標(biāo)值與理論極值的偏差較大(如F1)。

綜上，從以上4種算法對(duì)以上4個(gè)問題在不同維數(shù)下進(jìn)行求解獲得的結(jié)果可以看出，F(xiàn)OA的尋優(yōu)效果和算法穩(wěn)定性均有一定的優(yōu)勢(shì)，但算法的進(jìn)化能力有待進(jìn)一步增強(qiáng)。

4　結(jié)論

基于果蠅嗅覺和視覺覓食的行為特征，獲得可調(diào)參數(shù)少且具有協(xié)同進(jìn)化特點(diǎn)的新型果蠅優(yōu)化算法。該算法利用優(yōu)質(zhì)子群進(jìn)行局部搜索，增強(qiáng)局部搜索能力；利用當(dāng)前最好個(gè)體和優(yōu)質(zhì)子群引導(dǎo)中等子群向最優(yōu)解所在區(qū)域轉(zhuǎn)移；劣質(zhì)子群通過特定的變異方式，增強(qiáng)群體多樣性和提供發(fā)現(xiàn)最優(yōu)解的機(jī)會(huì)。比較性的數(shù)值實(shí)驗(yàn)表明，此算法是一種具有競(jìng)爭(zhēng)力的果蠅優(yōu)化算法。雖然該算法結(jié)構(gòu)簡(jiǎn)單，處理偏高維優(yōu)化問題已呈現(xiàn)了一定的優(yōu)勢(shì)，但算法中個(gè)體自身進(jìn)化的歷史信息未被利用，個(gè)體間的競(jìng)爭(zhēng)、合作協(xié)同進(jìn)化尚未充分體現(xiàn)，有待進(jìn)一步改進(jìn)該算法的進(jìn)化能力。

[1] W T Pan. A new fruit fly optimization algorithm: Taking the financial distress model as an example [J]. Knowledge-Based Systems, 2012, 26: 69-74.

[2] Q K Pan, H Y Sang, J H Duan, et al. An improved fruit fly optimization algorithm for continuous function optimization problems [J]. Knowledge-Based Systems, 2014, 62: 69-83.

[3] 潘文超. 果蠅最佳化演算法—最新演化式計(jì)算技術(shù) [M]. 臺(tái)北: 滄海書局, 2011: 1-12.

[4] X Yuan, X Dai, J Zhao, et al. On a novel multi-swarm fruit fly optimization algorithm and its application [J]. Applied Mathematics & Computation, 2014, 233(3): 260-271.

(責(zé)任編輯：曾晶)

A New Fly Optimization Algorithm

ZHANG Xiaoru1, ZHANG Zhuhong2*

(1.College of Science, Guizhou University, Guiyang 550025, China; 2.College of Big Data & Information Engineering, Guizhou University, Guiyang 550025, China)

For the problem of single-objective non-constrained higher-dimensional function optimization, this work investigates a new applicable fly optimization algorithm. In the design of algorithm, a local mutation strategy ensures the elitist sub-population to achieve strong exploitation; the medium sub-population transforms its individuals towards specific directions upon such elitist sub-population; the inferior sub-population creates diverse individuals along multiple directions. Comparatively numerical results have showed that the proposed algorithm is of potential for higher-dimensional function optimization problems.

fly optimization; function optimization; multi-modality

1000-5269(2016)02-0093-04

10.15958/j.cnki.gdxbzrb.2016.02.21

2015-10-08

國(guó)家自然科學(xué)基金(61563009)；教育部博士點(diǎn)基金 (20125201110003); 貴州大學(xué)研究生創(chuàng)新基金 (研理工2015057)

張曉茹(1987-), 女, 在讀碩士, 研究方向: 智能優(yōu)化算法，Email: xiaoruzh@163. com.

張著洪，Email：sci. zhzhang@gzu. edu. cn.

TP301.6

A