改進的人工蜂群算法在作業調度中的應用

邵金平，陳 亮，周 慶

(泰山職業技術學院，山東 泰安 271000)

1 引入

當今時代，人們更多的關注優化問題，并做了大量的工作，發明很多有效的算法，如遺傳算法、人工蜂群算法、神經網絡、魚群算法等等［1］。人工蜂群算法是較新的一個人工智能算法，由Dervis Karaboga在2005發明，人工蜂群算法比較容易實現和應用，只需要一些常用的參數，如群體規模、最大循環次數［4］。

在本文中，改進了經典的人工蜂群算法，在蜜蜂搜索食物源的過程中增加了變異操作和雜交操作，以提高食物源搜索的優化程度。實驗表明，改進人工蜂群算法在工作調度中的應用是有效的。

2 人工蜂群算法

在人工蜂群算法中，蜂群分為三蜜蜂:雇用蜂、跟隨蜂和偵查蜂，在沒有任何提示的情況下隨機搜索食物源的蜜蜂叫偵查蜂，在一定的前提下自行出去找食物的蜜蜂叫雇用蜂，等待目標食物源出現后才去食物源的蜜蜂叫跟隨蜂［1］。每個食物源只有一只雇用蜂，換句話說，雇用蜂的數量等于食物源的數量。當食物源被消耗完后(或食物源達不到最低要求)，雇用蜂(或跟隨蜂)升級為偵查蜂［5］。人工蜂群算法的主要步驟如下:

(1)初始化

(2)Repeat

(3)將雇用蜂放在一個食物源

(4)將跟隨蜂放在一個食物源

(5)將偵查蜂放在搜索區域搜索新的食物源

(6)Until(滿足預先設定的要求)

在人工蜂群算法中，每個循環分三步:發出雇用蜂到食物源并計算蜂蜜的數量;跟隨蜂分享雇用蜂的食物信息，并判斷蜂蜜數量是否達到要求;找不到達到最低要求的食物源時，發出偵查蜂，查找可能存在的食物源。在初始化階段，根據蜜蜂和食物源的蜂蜜數量決隨機選擇食物源，以位置的形式記錄下食物源，然后蜜蜂進入蜂巢與跟隨蜂共享食物源的蜂蜜數量的信息;在第二階段，每只雇用蜂進入食物源區域，根據上次循環的得到的食物源位置，在該位置的鄰域內搜索一個新的食物源;在第三階段，跟隨蜂根據雇用蜂的提供的食物源的蜂蜜數量的信息來到食物源，食物源的蜂蜜數量越大，這個食物源被跟隨蜂選中的概率也越大［2］。到達選中的食物源區域，在選中的食物源的鄰域內搜索一個新的食物源。當一個食物源被消耗盡，由偵查蜂隨機的選擇一個新的食物源，并代替消耗盡食物源。

在人工蜂群算法中，每個食物源的位置代表問題的一個候選解，每個解都有一個適合度，該適合度決定解的優劣，食物源的蜂蜜的數量即是候選解的適合度［6］。一般的雇用蜂或跟隨蜂的數量與解的數量相同。人工蜂群算法或隨機生成一個初始解或用蜜蜂的數量NF代替。每個解代表一個食物源的位置記為xij，i代表一個特解(i=1，2，…，NF)，每個解是一個 D-維向量，因此 j代表特解的“特維”(j=1，2，…，D)。初始化完成后，雇用蜂在前一個食物源的附近開始搜索新食物源，如果新食物源的蜂蜜數量(適應度)比前一個食物源大，則用新食物源代替前一個食物源。

當所有雇用蜂完成搜索過程，所有蜜蜂分享食物源的蜂蜜數量信息及跟隨蜂得到食物源的位置信息［3］。跟隨蜂選擇某個食物源與Pi有關，

其中，fi、fn是解i的適應度(或蜂蜜的數量)，NF是食物源的數量。雇用蜂訪問食物源后對其蜂蜜數量進行估算，從而確定了Pi的值，跟隨蜂根據Pi決定訪問的食物源。

可使用如下公式從前后選解生成新的后選解:

其中，j是列(或維)下標(j=1，2，…，D)，k 是某個特解的下標(k=1，2，…，NF)，i是某個特解的下標(i=1，2，…，NF)，i和 k 是不同的，k 是隨機生成的，而 i不是，Φij∈［-1，1］是一個隨機數，決定 xij鄰域的大小。xij和xkj的參數差別越小，兩者位置越近。因此，最優解的搜索的步長減小了。生成后選解νij后，計算相應的適應度并進行比較。

如果新后選解的適應度更高，則用新后選解代替原后選解，否則保留原后選解。如果經過一個循環后沒有找到更好的解，則設該食物源被消耗盡。然后放出偵查蜂，找新食物源來代替它。

3 帶變異和雜交操作的人工蜂群算法

首先，標準人工蜂群算法中添加了新動作——變異操作。變異操作是在雇用蜂之后插入的。人工蜂群算法分為四階段:初始化階段、雇用蜂階段、跟隨蜂和偵查蜂階段、變異和雜交階段。雇用蜂階段完成局部搜索，雇用蜂之后的變異用于突破搜索空間，并完成在新空間的搜索。因此變異改變了搜索空間，提供了改變局部最優的條件，防止陷于局部最優。在人工蜂群算法中，每次食物源搜索操作完成后，按一定的概率執行變異操作。按隨機方式從滿足一定條件食物源中選擇食物源，并執行變異操作。用新后代代替原后代。在本文中，當執行變異操作時，隨機選擇一個食物源xij，用一個隨機數替換它的某個列值。

下面是添加變異操作的人工蜂群算法。第一階段是初始化階段，完成單個食物源的搜索。

算法:添加變異操作的人工蜂群算法

(初始化階段)

步驟1:隨機產生NF個D-維向量，作為初始食物源位置xij，(i=1，…，NF，j=1，…，D)

步驟2:根據公式:

計算每個食物源的適應度，并選擇最好的作為初始解

(雇用蜂階段)

步驟3:根據公式(1)計算概率Pi，按公式(2)計算生成新的后選解

步驟4:按公式(3)計算每個新后選解的適應度fit(bi)，根據適應度判斷，如果新解優于原解，則用新解替換原解

步驟5:根據公式(1)重新每個食物源的概率Pi

(雜交階段)

步驟6:如果沒有產生新的解，并且原解不能達到最目標要求，則隨機選擇2個解，按公式(2)進行雜交，生成新解

步驟7:按公式(3)計算每個新后選解的適應度，用適應度最高的代替父解

(跟隨蜂階段)

步驟8:對每只跟隨蜂，根據Pi選擇新的食物源，生成食物源xij的新的后選解，并計算適應度，并選擇適應度最高的作為新的解

(變異階段)

步驟9:如果沒有產生新的解，并且原解不能達到最目標要求，則采用遺傳算法的變異公式對現存解進行變異，并計算變異后各解的適應度

(偵查蜂階段)

步驟10:如果根據適應度選出的新解達到最優或循環次數達到最大要求，則結束，

步驟11:如果食物源沒有消耗盡，則轉(步驟3)，否則，由偵查蜂隨機搜索一個新食物源，轉(步驟3)

4 實驗

實驗在某企業內的作業調度環境下進行的。實驗中涉及的參數有:最大循環次數為20000，最大食物源數為40，最大流程數為30，維數為30.變異概率值0.7。

實驗1:實驗設有5個工作點，17個任務，對比算法為遺傳算法，執行時間如下:

表1 實驗1執行時間對照表Table 1Experimental1execution time table

遺傳算法的產生序列:14，9，0，15，4，13，6，1，3，8，11，16，12，10，2，7，5.

基本人工蜂群算法產生序列:7，14，5，6，4，2，13，15，1，9，16，0，8，3，10，11，12

本文算法的產生序列:0，3，9，5，12，2，13，4，1，6，16，7，8，11，10，14，15.

實驗2:實驗設有10個工作點，27個任務，對比算法為遺傳算法，執行時間如下:

表2 實驗2執行時間對照表Table 2 experimental2execution time table

遺傳算法的產生序列:

24，9，7，2，26，1，8，13，3，18，10，0，23，5，17，14，4，15，12，6，16，20，11，22，25，19，21.

基本人工蜂群算法產生序列:

10，25，15，18，14，4，19，8，5，3，23，6，1，20，16，17，12，2，21，11，22，7，26，13，24，0，8

本文算法的產生序列:

0，5，1 5，9，23，4，19，8，7，3，26，6，1，14，16，2，12，11，21，17，22，25，18，13，24，10，20

實驗3:實驗設有12個工作點，30個任務，對比算法為遺傳算法，執行時間如下:

表3 實驗3執行時間對照表Table 3 experimental3execution time table

遺傳算法的產生序列:

28，24，20，25，10，7，17，4，9，22，6，11，14，18，0，29，15，13，26，12，1，19，21，5，3，27，2，29，16，8.

基本人工蜂群算法產生序列:

22，25，4，16，19，1，21，26，2，24，29，23，6，15，12，7，13，8，14，10，9，28，18，5，3，27，11，20，0，17

本文算法的產生序列:

0，5，1 9，16，24，1，21，9，2，4，29，3，6，15，17，7，13，8，23，10，26，28，18，14，25，27，11，20，12，22.

從表1、表2、表3很容易得出結論，本文改進的人工蜂群算法比遺傳算法執行時間較少，從后選解產生的序列易知，搜索到的解相同，只是順序不同。

5 結論

本文分析了人工蜂群算法的運行原理，在傳統的人工蜂群算法的雇用蜂階段后和跟隨蜂階段后插入了遺傳算法的變異和雜交操作。在滿足條件時，按一定的概率用變異操作選擇食物源。實驗在某企業的環境下以工作調度問題為目標進行的。在沒有設置特別的變異概率的情況下，得到了最佳工作調度序列。

［1］ 畢曉君，王艷嬌.加速收斂的人工蜂群算法［J］.計算機與數字工程.2011，33(12):76-79

［2］ 李小平，鄭世杰.基于遺傳算法和拓撲優化的結構多孔洞損傷識別［J］.振動與沖擊，2011，32(1):88-93

［3］ 龍 泓，向 勇.P2P工作流系統的調度框架設計和實現［J］.計算機工程與設計，2012，33(1):54-67

［4］ 高衛峰，劉三陽.混合人工蜂群算法［J］.系統工程與電子技術，2011，33(5):84-86

［5］ 陳 亮.基于混合蛙跳算法的背包問題求解算法［J］.河南城建學院學報，2011，20(3):41-44

［6］ Lei D.Simplified multi-objective genetic algorithms for stochastic job shop scheduling.Appl.Soft Comput.2011，doi:10.1016/j.asoc.2011.06.001.