張曉茹，張著洪

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

?

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

張曉茹1，張著洪2*

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

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

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

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

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

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

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

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

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

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

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

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

(1)

步5中等子群B更新：對于B中每個個體x，隨機抽取A中一個個體y，并與xbest一起對x實施更新：

x′←y+λ(xbest-x)

(2)

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

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

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

(3)

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

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

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

3　數(shù)值實驗

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

文獻[2]中的測試問題F1至F4被用于檢測以上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個最優(yōu)解，但在維數(shù)較大的情形下，目標(biāo)函數(shù)在決策區(qū)域的大部分區(qū)域上的函數(shù)值較大，算法收斂速度受到極大影響；F3和F4是極為困難的多峰值函數(shù)優(yōu)化問題，其決策變量的耦合性強，多個局部最優(yōu)解嚴(yán)重干擾算法的全局搜索，加之，當(dāng)維數(shù)較高時，目標(biāo)函數(shù)在多個子決策區(qū)域的函數(shù)值較大，特別是F3的決策區(qū)域較大，使得算法求解變得極為困難。

3.130維測試問題的實驗結(jié)果分析

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

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

注：μ為獨立運行100次后獲得的100個目標(biāo)值的均值，σ為獨立運行100次后獲得的100個目標(biāo)值的均方值

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

由表1的均值可知，從獲得的解質(zhì)量看，F(xiàn)OA優(yōu)于其它算法；MFOA求解F1-F3 獲得的解質(zhì)量優(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的最小值時，F(xiàn)OA獲得的中位線均較其它算法獲得的中位線低，也即所獲得的目標(biāo)值距離理論最優(yōu)值較近，搜索效果最好；再從箱線圖的中位線距離下四分位線的遠近得知，F(xiàn)OA的搜索效果較穩(wěn)定，F(xiàn)FO次之。

3.2100維測試問題的實驗結(jié)果分析

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

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

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

與表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的個體更新方式單一、群體中個體整體向當(dāng)前最優(yōu)個體靠近，致使最終獲得的目標(biāo)值與理論極值的偏差較大(如F1)。

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

4　結(jié)論

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

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

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

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

TP301.6

A