改進(jìn)的果蠅優(yōu)化算法在多目標(biāo)搜索中的應(yīng)用

張斌艷，羅萬(wàn)成，楊志剛

(重慶文理學(xué)院，重慶402160)

0 引言

果蠅優(yōu)化算法是一種十分先進(jìn)的仿生學(xué)算法，于2011年被首次提出．研究者通過(guò)觀察果蠅生物的覓食方法，推導(dǎo)得出全局優(yōu)化技術(shù)，從而完成局部搜索的任務(wù)需求，在科學(xué)以及工程領(lǐng)域都有著較為廣泛的應(yīng)用．但是，由于算法理論的誕生較晚，一些理論尚未完全成熟，因此更多表現(xiàn)為局部最優(yōu)解和早熟收斂等弊端．為了能夠在多目標(biāo)搜索中發(fā)揮作用，需要對(duì)其進(jìn)行優(yōu)化．在當(dāng)前的研究當(dāng)中，果蠅優(yōu)化算法主要集中在單一目標(biāo)的優(yōu)化之上，而對(duì)離散環(huán)境多目標(biāo)的優(yōu)化存在一定不足，筆者為了能夠準(zhǔn)確地實(shí)現(xiàn)多目標(biāo)檢索，需要進(jìn)行算法的改進(jìn)．

1 果蠅優(yōu)化算法的改進(jìn)方法

1.1果蠅優(yōu)化算法的使用

果蠅優(yōu)化算法最早于2011年被首次提出，研究人員觀察了果蠅等生物的覓食以及生活習(xí)慣后發(fā)現(xiàn)，果蠅在空中飛翔的過(guò)程中，能夠通過(guò)嗅覺(jué)以及視覺(jué)來(lái)判斷空氣當(dāng)中存有的氣味，并根據(jù)氣味的大小和散播規(guī)律來(lái)判斷食物源的具體方向，從而完成食物位置或同伴位置的確定，形成覓食流程的最優(yōu)化．研究人員通過(guò)對(duì)這一現(xiàn)象進(jìn)行分析總結(jié)，構(gòu)成FOA算法．算法當(dāng)中，step1代表果蠅群的位置，作為整個(gè)算法當(dāng)中的初始算法參數(shù)，需要通過(guò)sisepop來(lái)表示果蠅的群體規(guī)模，而用maxgen表示算法的最大迭代次數(shù)，因此在坐標(biāo)當(dāng)中可以通過(guò)x、y來(lái)表示具體的初始化位置，如x(axis)和y(axis)[1]．step2則表示果蠅群體在覓食過(guò)程中的方向以及位置的選擇，研究人員通過(guò)搜索距離的取值方法確定randomvalue的范圍，如公式(1)所示：

Xi=X_axis+randomvalue

Yi=Y_axis+randomvalue

(1)

通過(guò)公式(1)，研究人員可以獲得進(jìn)行覓食的果蠅群體的位置范圍區(qū)間．而step3則表示果蠅在判斷空氣氣息濃度時(shí)的判斷值si，并用disti表示判斷值si的距離．如公式(2)和公式(3)所示．

(2)

si=1/disti

(3)

在判斷的過(guò)程中，果蠅會(huì)根據(jù)濃度的判斷值進(jìn)行精確的位置判斷，而在運(yùn)用算法時(shí)則需要利用fitnessfunction適應(yīng)度函數(shù)進(jìn)行判定值的代入計(jì)算，從而獲得濃度個(gè)體的判定值smelli，如公式(4)所示．

smelli=function(si)

(4)

而為了能夠準(zhǔn)確模擬濃度判斷最佳的果蠅，要利用最佳的個(gè)體位置通過(guò)視覺(jué)引導(dǎo)群體向個(gè)體不斷靠攏，最終完成群體最優(yōu)濃度的更新，此時(shí)需要算法完成對(duì)公式(5)、公式(6)以及公式(7)的聯(lián)立，從而實(shí)現(xiàn)最優(yōu)解．

semllbest=bestsmell

(5)

X_axis=X(bestindex)

(6)

Y_axis=Y(bestindex)

(7)

在完成上述步驟之后，需要進(jìn)行迭代，尋找最優(yōu)解．通過(guò)不斷重復(fù)執(zhí)行的方式達(dá)到迭代的次數(shù)要求，以提高精度和準(zhǔn)確度．

1.2 果蠅優(yōu)化算法改進(jìn)

傳統(tǒng)的果蠅優(yōu)化算法，雖然能夠在一定程度上模擬果蠅覓食對(duì)空氣氣息濃度的最優(yōu)判斷，但是在實(shí)際的迭代過(guò)程中，由于最優(yōu)個(gè)體學(xué)習(xí)策略的不斷深化會(huì)加快收斂速度，導(dǎo)致種族多樣性分析的丟失，最終造成局部最優(yōu)，無(wú)法體現(xiàn)出最優(yōu)解的要求．因此對(duì)于傳統(tǒng)的果蠅優(yōu)化算法來(lái)說(shuō)，其所具有的單目標(biāo)問(wèn)題解決的特征使其無(wú)法直接應(yīng)用在多目標(biāo)的環(huán)境當(dāng)中．在進(jìn)行多目標(biāo)搜索優(yōu)化研究時(shí)，研究人員如果盲目地通過(guò)果蠅優(yōu)化算法進(jìn)行多目標(biāo)的離散環(huán)境判斷，很可能造成最劣解的隨機(jī)選擇，因此在進(jìn)行改進(jìn)時(shí)，需要進(jìn)一步控制環(huán)境的連續(xù)性，通過(guò)個(gè)體的產(chǎn)生和變化來(lái)進(jìn)行位置維度變化的記錄，從而在前期迭代當(dāng)中尋求多數(shù)解，最終通過(guò)半徑計(jì)算的方法進(jìn)行區(qū)域內(nèi)部的密集檢索，如公式(8)所示：

radius(搜索半徑)=radiusmax·elg(rediusmin/radiusmax)·(g/maxgen)

(8)

在公式(8)當(dāng)中，radius代表搜索半徑，可通過(guò)極值max和min分別表示最大搜索半徑和最小搜索半徑，而字母g則表示在算法當(dāng)中的實(shí)時(shí)迭代次數(shù)．maxgen表示迭代的極值，即最大迭代次數(shù)．在函數(shù)分析中，radius(1,10)表示radiusmax不會(huì)超過(guò)10，不會(huì)小于1，因此搜索半徑的曲線變化呈單調(diào)遞減的趨勢(shì)，且隨著迭代次數(shù)的不斷增加，搜索半徑會(huì)快速減少．而為了能夠準(zhǔn)確解決多目標(biāo)離散環(huán)境中對(duì)問(wèn)題最優(yōu)的要求，需要根據(jù)迭代和搜索半徑的變化規(guī)律進(jìn)行優(yōu)化算法改進(jìn)．筆者在進(jìn)行優(yōu)化時(shí)采用新個(gè)體產(chǎn)生的方法，使其在種群位置當(dāng)中表現(xiàn)為局部?jī)?yōu)化外的最優(yōu)解計(jì)算方式，如公式(9)所示.

IND(i)=mod(X+radius·randval，upper)+1

(9)

在公式(9)當(dāng)中，radius表示動(dòng)態(tài)搜索半徑，在具體計(jì)算時(shí)可由公式(8)進(jìn)行計(jì)算和推導(dǎo)，而X表示果蠅種群的具體位置，可由公式(1)進(jìn)行推導(dǎo)計(jì)算，upper表示算法的上界，randval表示隨機(jī)范圍的取值，在本文算法當(dāng)中，表示{-1,0,1}．

2 多目標(biāo)優(yōu)化的算法要求

多目標(biāo)的最優(yōu)化問(wèn)題實(shí)際上是數(shù)學(xué)當(dāng)中的優(yōu)化問(wèn)題，一般通過(guò)數(shù)學(xué)定義的方式完成公式化的表達(dá)，如公式(10)所示．

minf(x)

St.gi(x)≤a1，i=1,2，…，m

(10)

公式(10)當(dāng)中，x作為向量，表示最優(yōu)化函數(shù)當(dāng)中所擁有的自變量，而函數(shù)f(x)則作為Rii→R當(dāng)中的目標(biāo)求解，因此用來(lái)表示R變化的函數(shù)gi實(shí)際上應(yīng)當(dāng)屬于一個(gè)約束不等式，從而為常數(shù)a提供約束條件和臨界值，進(jìn)而使x可以作為問(wèn)題的最優(yōu)解．在數(shù)學(xué)模型當(dāng)中，當(dāng)向量x的目標(biāo)函數(shù)值為最小值時(shí)，表示任何滿足gi函數(shù)且小于等于常數(shù)a的向量都應(yīng)當(dāng)具備f(x)≤f(s)，因此在求得最大值時(shí)，就可以通過(guò)相反數(shù)的方式將f(x)表示為-f(x)，進(jìn)而根據(jù)目標(biāo)函數(shù)和約束條件方程獲得極值的優(yōu)化[2]．

3 多目標(biāo)搜索中果蠅優(yōu)化算法的應(yīng)用

3.1 混合步長(zhǎng)嗅覺(jué)MFOA參數(shù)

在車間的設(shè)計(jì)當(dāng)中，主要問(wèn)題集中在車間設(shè)備所具有的功率、效率以及搬運(yùn)量、搬運(yùn)距離等因素，因此為了能夠更好地完成車間設(shè)備的布置，降低調(diào)度成本，需要設(shè)定多因素的NP-hard問(wèn)題，并基于果蠅優(yōu)化算法形成多目標(biāo)果蠅優(yōu)化算法MFOA．

3.2 MFOA編碼

在實(shí)例當(dāng)中，車間的調(diào)度和設(shè)備布置問(wèn)題實(shí)際上是多目標(biāo)的離散優(yōu)化問(wèn)題，因此為了滿足調(diào)度最優(yōu)，在進(jìn)行車間設(shè)備的布局以及加工順序的設(shè)定時(shí)，需要在工序和設(shè)備的配置方面通過(guò)編碼的方式對(duì)所需要進(jìn)行選用的設(shè)備進(jìn)行標(biāo)簽化處理，不同的設(shè)備擁有不同的編號(hào)，從而使其能夠更好地表現(xiàn)在算法當(dāng)中．

3.3 果蠅優(yōu)化算法種群初始化

在完成針對(duì)車間內(nèi)部的設(shè)備排序編碼后，需要依照果蠅優(yōu)化算法MFOA進(jìn)行種群的初始化．通過(guò)初始化完成population個(gè)體的設(shè)置和產(chǎn)生．在設(shè)置中，算法需要兼顧population所擁有的質(zhì)量以及多樣性，因此在population當(dāng)中40%的個(gè)體需要通過(guò)貪心算法產(chǎn)生，而剩下的部分則主要依靠隨機(jī)方式生成．一般來(lái)說(shuō)，如果運(yùn)用貪心算法產(chǎn)生個(gè)體，則需要采用兩種貪心策略：一種是通過(guò)選擇加工時(shí)間短的機(jī)床，優(yōu)先完成最早的工件加工，從而避免與另一個(gè)零件沖突：另一種則是優(yōu)先對(duì)碳排放較低的工件進(jìn)行加工，從而控制加工成本，實(shí)現(xiàn)調(diào)度優(yōu)化．

3.4 混合步長(zhǎng)嗅覺(jué)的應(yīng)用

由于本文所針對(duì)的車間優(yōu)化問(wèn)題空間較大，因此離散問(wèn)題也較多，為了能夠準(zhǔn)確地實(shí)現(xiàn)果蠅優(yōu)化算法的最優(yōu)解多目標(biāo)優(yōu)化，應(yīng)當(dāng)采用混合步長(zhǎng)進(jìn)行搜索，盡可能避免單一步長(zhǎng)的領(lǐng)域搜索．具體來(lái)說(shuō)，在算法完成第一次迭代之后，需要依照離散問(wèn)題的生成而展開(kāi)多種步長(zhǎng)的鄰域搜索，并將嗅覺(jué)搜索作為基礎(chǔ)的操作原理，同時(shí)將基本操作標(biāo)記為mutation operation．在算法當(dāng)中，基本操作mutation operation是基于工序所完成的變異操作，同時(shí)在變異操作的基礎(chǔ)之上通過(guò)設(shè)備布局完成操作．

3.5 全局協(xié)作

果蠅在進(jìn)行覓食和空氣氣息濃度分析時(shí)，會(huì)采用種群間的學(xué)習(xí)方法獲取信息，并不斷進(jìn)行自我位置的更新，而在算法當(dāng)中設(shè)備編碼由于受到工序的約束[3]，因此與果蠅在獲取信息的過(guò)程所表現(xiàn)的特征相同，一般需要通過(guò)F1和F2不同個(gè)體的基因隨機(jī)選擇來(lái)確定位置信息，在完成信息步驟后，通過(guò)差分信息的方式，將信息依照大小完成排列，最終得到變化位置調(diào)整后的Fr編碼信息，完成優(yōu)化．

4 結(jié)語(yǔ)

在目前的科學(xué)技術(shù)領(lǐng)域和工程設(shè)計(jì)領(lǐng)域中，果蠅優(yōu)化算法有著豐富的應(yīng)用前景．而在多目標(biāo)搜索的離散環(huán)境當(dāng)中，由于所選目標(biāo)數(shù)量較多，單一的果蠅優(yōu)化算法無(wú)法完成計(jì)算，因此需要通過(guò)改進(jìn)的MFOA算法來(lái)完成目標(biāo)優(yōu)化．