改進的人工蜂群算法在作業(yè)調(diào)度中的應(yīng)用

邵金平，陳 亮，周 慶

(泰山職業(yè)技術(shù)學(xué)院，山東 泰安 271000)

1 引入

當(dāng)今時代，人們更多的關(guān)注優(yōu)化問題，并做了大量的工作，發(fā)明很多有效的算法，如遺傳算法、人工蜂群算法、神經(jīng)網(wǎng)絡(luò)、魚群算法等等［1］。人工蜂群算法是較新的一個人工智能算法，由Dervis Karaboga在2005發(fā)明，人工蜂群算法比較容易實現(xiàn)和應(yīng)用，只需要一些常用的參數(shù)，如群體規(guī)模、最大循環(huán)次數(shù)［4］。

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

2 人工蜂群算法

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

(1)初始化

(2)Repeat

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

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

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

(6)Until(滿足預(yù)先設(shè)定的要求)

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

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

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

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

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

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

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

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

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

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

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

(初始化階段)

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

步驟2:根據(jù)公式:

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

(雇用蜂階段)

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

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

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

(雜交階段)

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

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

(跟隨蜂階段)

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

(變異階段)

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

(偵查蜂階段)

步驟10:如果根據(jù)適應(yīng)度選出的新解達到最優(yōu)或循環(huán)次數(shù)達到最大要求，則結(jié)束，

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

4 實驗

實驗在某企業(yè)內(nèi)的作業(yè)調(diào)度環(huán)境下進行的。實驗中涉及的參數(shù)有:最大循環(huán)次數(shù)為20000，最大食物源數(shù)為40，最大流程數(shù)為30，維數(shù)為30.變異概率值0.7。

實驗1:實驗設(shè)有5個工作點，17個任務(wù)，對比算法為遺傳算法，執(zhí)行時間如下:

表1 實驗1執(zhí)行時間對照表Table 1Experimental1execution time table

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

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

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

實驗2:實驗設(shè)有10個工作點，27個任務(wù)，對比算法為遺傳算法，執(zhí)行時間如下:

表2 實驗2執(zhí)行時間對照表Table 2 experimental2execution time table

遺傳算法的產(chǎn)生序列:

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.

基本人工蜂群算法產(chǎn)生序列:

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

本文算法的產(chǎn)生序列:

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:實驗設(shè)有12個工作點，30個任務(wù)，對比算法為遺傳算法，執(zhí)行時間如下:

表3 實驗3執(zhí)行時間對照表Table 3 experimental3execution time table

遺傳算法的產(chǎn)生序列:

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.

基本人工蜂群算法產(chǎn)生序列:

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

本文算法的產(chǎn)生序列:

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很容易得出結(jié)論，本文改進的人工蜂群算法比遺傳算法執(zhí)行時間較少，從后選解產(chǎn)生的序列易知，搜索到的解相同，只是順序不同。

5 結(jié)論

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

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

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

［3］ 龍 泓，向 勇.P2P工作流系統(tǒng)的調(diào)度框架設(shè)計和實現(xiàn)［J］.計算機工程與設(shè)計，2012，33(1):54-67

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

［5］ 陳 亮.基于混合蛙跳算法的背包問題求解算法［J］.河南城建學(xué)院學(xué)報，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.