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

于淼淼 史磊 周嬉嬉 王蕊

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

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

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

1 人工蜂群算法概述

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

1.1算法原理

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

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

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

1.2算法特點

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

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

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

2.1算法改進

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

2.2算法應(yīng)用

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

在上表中，J表示工件，M表示機器，JO表示工序步驟，后續(xù)的數(shù)字表示某臺機器加工某個工件工序所需的時間，0表示機器無法對該工件的該工序進行加工。

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

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

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

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

3 結(jié)語

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

參考文獻：

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

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

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

作者簡介：

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

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