改進的果蠅優(yōu)化算法在多目標搜索中的應用

張斌艷，羅萬成，楊志剛

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

0 引言

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

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

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

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

Xi=X_axis+randomvalue

Yi=Y_axis+randomvalue

(1)

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

(2)

si=1/disti

(3)

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

smelli=function(si)

(4)

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

semllbest=bestsmell

(5)

X_axis=X(bestindex)

(6)

Y_axis=Y(bestindex)

(7)

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

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

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

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

(8)

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

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

(9)

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

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

多目標的最優(yōu)化問題實際上是數學當中的優(yōu)化問題，一般通過數學定義的方式完成公式化的表達，如公式(10)所示．

minf(x)

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

(10)

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

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

3.1 混合步長嗅覺MFOA參數

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

3.2 MFOA編碼

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

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

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

3.4 混合步長嗅覺的應用

由于本文所針對的車間優(yōu)化問題空間較大，因此離散問題也較多，為了能夠準確地實現果蠅優(yōu)化算法的最優(yōu)解多目標優(yōu)化，應當采用混合步長進行搜索，盡可能避免單一步長的領域搜索．具體來說，在算法完成第一次迭代之后，需要依照離散問題的生成而展開多種步長的鄰域搜索，并將嗅覺搜索作為基礎的操作原理，同時將基本操作標記為mutation operation．在算法當中，基本操作mutation operation是基于工序所完成的變異操作，同時在變異操作的基礎之上通過設備布局完成操作．

3.5 全局協(xié)作

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

4 結語

在目前的科學技術領域和工程設計領域中，果蠅優(yōu)化算法有著豐富的應用前景．而在多目標搜索的離散環(huán)境當中，由于所選目標數量較多，單一的果蠅優(yōu)化算法無法完成計算，因此需要通過改進的MFOA算法來完成目標優(yōu)化．