人工蜂群算法及其在調(diào)度問題中的應(yīng)用探討

于淼淼 史磊 周嬉嬉 王蕊

摘 要：人工蜂群算法是一種群體性智能性算法，在解決復(fù)雜優(yōu)化問題的過程中，有著非常顯著的效果，而且算法本身的設(shè)置參數(shù)較少，魯棒性較強(qiáng)，將其應(yīng)用到調(diào)度問題中，能夠?qū)崿F(xiàn)資源的優(yōu)化配置，促進(jìn)生產(chǎn)效率和生產(chǎn)水平的提高。本文對(duì)人工蜂群算法的原理、特點(diǎn)進(jìn)行了分析，并就其在調(diào)度問題中的應(yīng)用進(jìn)行了探討。

關(guān)鍵詞：人工蜂群算法;調(diào)度問題;應(yīng)用

前言：在生產(chǎn)及管理領(lǐng)域，調(diào)度問題呈現(xiàn)出復(fù)雜性和實(shí)時(shí)性特征，傳統(tǒng)的調(diào)度算法無法很好的滿足現(xiàn)實(shí)需求，難以取得令人滿意的結(jié)果。基于此，越來越多的研究人員開始將目光放在群體智能算法的研究方面，人工蜂群算法就是其中一種，其能夠有效的應(yīng)對(duì)復(fù)雜的生產(chǎn)調(diào)度問題，相比傳統(tǒng)算法有著更好的尋優(yōu)搜索能力，可以很好的尋找到全局最優(yōu)目標(biāo)。

1 人工蜂群算法概述

人工蜂群算法是一種基于蜂群采蜜過程的群體智能算法，主要是模仿蜜蜂群采蜜時(shí)對(duì)于蜜源的偵查、跟隨采蜜、蜜源選擇以及跳舞傳遞信息等行為，能夠?qū)崿F(xiàn)對(duì)于目標(biāo)的有效搜索。人工蜂群算法的模型簡(jiǎn)單，無論是控制還是實(shí)現(xiàn)都十分方便，也因此受到了研究人員的關(guān)注。

1.1算法原理

在人工蜂群算法中，食物源的位置代表了等待優(yōu)化問題的一個(gè)可行解，對(duì)于最優(yōu)解的求解過程，體現(xiàn)在算法中，就是尋找較高收益度食物源的過程。初始化階段，隨機(jī)生成的食物源表明存在和食物源數(shù)量一致的隨機(jī)可行解，可以將其表現(xiàn)為

其中，xi表示D維向量，代表了某個(gè)食物源的位置，F(xiàn)（xi）則表示每一個(gè)xi所對(duì)應(yīng)的目標(biāo)函數(shù)，能夠決定xi的好壞，SN表示食物源的數(shù)量。

在完成初始化之后，為了能夠最優(yōu)食物源，蜂群會(huì)重復(fù)三個(gè)階段的動(dòng)作，第一是雇傭蜂階段，主要是通過運(yùn)算的方式，獲得相應(yīng)的鄰域內(nèi)蜜源，將自身處處蜜源與該蜜源的適應(yīng)度數(shù)值進(jìn)行對(duì)比，選擇其中的可行解，并且對(duì)適應(yīng)度值進(jìn)行記憶;二是跟隨蜂階段，其能夠通過相應(yīng)的搖擺舞實(shí)現(xiàn)與雇傭蜂之間的信息傳遞，在接收到相應(yīng)的信息后，可以依照食物源本身的富足程度，對(duì)蜜源進(jìn)行選擇;三是偵查蜂階段，若雇傭蜂提供的蜜源信息良好，跟隨蜂會(huì)募集更加大量的雇傭蜂來參與蜜源采集，反之，則該蜜源會(huì)被放棄，雇傭蜂也會(huì)轉(zhuǎn)變?yōu)閭刹榉洌⑶抑匦码S機(jī)選擇新的食物源進(jìn)行偵查。

1.2算法特點(diǎn)

人工蜂群算法的特點(diǎn)體現(xiàn)在幾個(gè)方面：一是正負(fù)反饋機(jī)制。不同階段，正負(fù)反饋機(jī)制有著不同的作用，例如，雇傭蜂階段，正反饋機(jī)制可以對(duì)系統(tǒng)的進(jìn)化方向進(jìn)行引導(dǎo)，使得其能夠逐步得到最優(yōu)解，有助于獲得較快的算法收斂速度;偵查蜂階段，負(fù)反饋機(jī)制的存在，使得群體能夠保持良好的創(chuàng)新能力，允許存在一定的退化誤差，這樣能夠規(guī)避早熟收斂的問題;二是分布式計(jì)算。在人工蜂群算法中，所有蜜蜂的對(duì)于食物源的搜索行動(dòng)都是獨(dú)立進(jìn)行的，可以借助相應(yīng)的信息交流與傳遞，實(shí)現(xiàn)彼此協(xié)作，獲取最佳的解決方案;三是良好的魯棒性。對(duì)比傳統(tǒng)算法，人工蜂群算法對(duì)初始路線并沒有很高的要求，也不需要對(duì)相應(yīng)的先驗(yàn)信息進(jìn)行明確，換言之，就是算法得到的求解結(jié)果與初始路線并沒有直接關(guān)聯(lián)，在進(jìn)行搜索的過程中，也不需要進(jìn)行干預(yù)和調(diào)整。當(dāng)然，人工蜂群算法同樣也存在一定的缺陷，即偵查蜂在對(duì)新的路徑進(jìn)行探索的過程中，做出的選擇具有很強(qiáng)的隨機(jī)性，會(huì)導(dǎo)致算法出現(xiàn)過慢收斂，可能出現(xiàn)局部最優(yōu)的情況。

2 人工蜂群算法在調(diào)度問題中的應(yīng)用

在傳統(tǒng)的調(diào)度問題處理中，采用的一般都是啟發(fā)式算法，而新時(shí)期，伴隨著群智能算法的興起，更多的研究人員開始試圖利用群智能算法來對(duì)調(diào)度問題進(jìn)行解決，比較常見的算法除了人工蜂群算法，還有蟻群算法、粒子群算法以及遺傳算法等，而對(duì)比其他三種算法，人工蜂群算法在對(duì)連續(xù)空間數(shù)值優(yōu)化問題進(jìn)行解決時(shí)，有著更加明顯的優(yōu)勢(shì)，不過常規(guī)意義上的人工蜂群算法在面對(duì)排列組合優(yōu)化問題時(shí)，表現(xiàn)出了一定的不足，需要對(duì)其進(jìn)行適當(dāng)優(yōu)化。

2.1算法改進(jìn)

一是對(duì)初始化進(jìn)程的改進(jìn)，以作業(yè)車間調(diào)度為例，對(duì)算法進(jìn)行初始化，將與雇傭蜂數(shù)量相同的調(diào)度方案作為初始蜜源;二是搜尋方法的改進(jìn)，通過對(duì)某個(gè)工件中其中一道加工工序加工設(shè)備的改進(jìn)組合來形成鄰域，考慮到加工順序的約束，需要在加工順序改變后，對(duì)新解的可行性做出判斷;三是適應(yīng)度計(jì)算的改進(jìn)，通過對(duì)調(diào)度過程的解析，計(jì)算出能夠?qū)φ{(diào)度方案優(yōu)劣進(jìn)行評(píng)估的數(shù)值，依照具體調(diào)度目標(biāo)選擇相應(yīng)的數(shù)據(jù)信息，對(duì)適應(yīng)度進(jìn)行計(jì)算。

2.2算法應(yīng)用

以3×4的作業(yè)車間調(diào)度問題為例，具體描述如表1所示。

在上表中，J表示工件，M表示機(jī)器，JO表示工序步驟，后續(xù)的數(shù)字表示某臺(tái)機(jī)器加工某個(gè)工件工序所需的時(shí)間，0表示機(jī)器無法對(duì)該工件的該工序進(jìn)行加工。

這里將尋優(yōu)目標(biāo)設(shè)定為工件平均加工時(shí)間最小，則在對(duì)改進(jìn)后的人工蜂群算法的相關(guān)參數(shù)進(jìn)行設(shè)置時(shí)，將蜜蜂種群的數(shù)量設(shè)置為20，最大迭代次數(shù)100，經(jīng)過相應(yīng)的分析計(jì)算，得到的最佳調(diào)度方案為

{（2，1，3），（3，1，2），（2，2，1），（3，2，4），（2，3，4），（1，1，3），（1，2，2）}

最小的平均加工時(shí)間為4，算法計(jì)算用時(shí)約為0.5352秒，依照算法得出的調(diào)度方案，繪制相應(yīng)的甘特圖，如圖1所示。

對(duì)照上圖分析，工件1、工件2和工件3的加工時(shí)間依次為4，6，2，對(duì)比傳統(tǒng)調(diào)度方案，結(jié)果如表2所示。可以看出，在經(jīng)過相應(yīng)的優(yōu)化改進(jìn)后，人工蜂群算法得到的調(diào)度方案較之前的方案有了很大提升。

3 結(jié)語

總而言之，作為一種比較新穎的群體智能優(yōu)化算法，人工蜂群算法的計(jì)算簡(jiǎn)單，控制參數(shù)較少，而且魯棒性強(qiáng)，在實(shí)踐中容易實(shí)現(xiàn)，能夠?qū)σ恍?fù)雜的問題進(jìn)行優(yōu)化。將人工蜂群算法應(yīng)用到調(diào)度問題的解決中，能夠獲得最佳的調(diào)度方案，提升調(diào)度的有效性。不過也需要認(rèn)識(shí)到，人工蜂群算法在實(shí)際應(yīng)用中也容易陷入局部最優(yōu)的狀況，需要有關(guān)人員做好理論研究工作，提升算法的適用性，在降低算法復(fù)雜度的同時(shí)，保障算法的收斂效果，對(duì)其應(yīng)用領(lǐng)域進(jìn)行拓展，得到更加符合實(shí)際應(yīng)用需求的人工蜂群改進(jìn)算法，將人工蜂群算法的應(yīng)用價(jià)值切實(shí)發(fā)揮出來。

參考文獻(xiàn)：

[1]鄭友蓮，雷德明，鄭巧仙.求解高維多目標(biāo)調(diào)度的新型人工蜂群算法[J].計(jì)算機(jī)科學(xué)，2020，47（07）：186-191.

[2]鄭小操，龔文引.改進(jìn)人工蜂群算法求解模糊柔性作業(yè)車間調(diào)度問題[J].控制理論與應(yīng)用，2020，37（06）：1284-1292.

[3]張松.人工蜂群算法研究及其應(yīng)用[D].西安電子科技大學(xué)，2019.

作者簡(jiǎn)介：

于淼淼 （1986-）女，遼寧大連人，碩士學(xué)歷，助理工程師，從事通信、大數(shù)據(jù)相關(guān)方面研究

（中國人民解放軍31436部隊(duì) ?遼寧 ?沈陽 ?110000）