ＶＢ環(huán)境下的模擬退火算法求指派問題

摘要：模擬退火算法是一種隨機(jī)搜索算法，可應(yīng)用于許多前提信息很少的問題，能漸進(jìn)地收斂于全局最優(yōu)解。指派問題是組合優(yōu)化問題中的一種，可用模擬退火算法來解此問題。模擬退火算法解決指派問題時(shí)，需要考慮實(shí)現(xiàn)此算法的技術(shù)問題，例如解的形式，初始溫度的計(jì)算，鄰域的生成方式，解的接受和舍棄，內(nèi)外循環(huán)的中止條件等。在VB編程環(huán)境下，實(shí)現(xiàn)了該算法的求解過程。實(shí)例仿真表明了該方法能夠以一定的概率跳出局部最優(yōu)而實(shí)現(xiàn)全局尋優(yōu)。

關(guān)鍵詞：VB；模擬退火算法；指派問題；仿真

中圖分類號(hào)：TP18文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)35-2153-03

Simulated Annealing Algorithm to Solve Assignment Problem under VB

DUAN Cha-li，CHEN Bo

(Lanzhou Jiaotong University，Lanzhou 730070，China)

Abstract: Simulated annealing algorithm is a random search algorithm， and it can be applied to many problems with little premise information， gradual convergence in the global optimal solution. The assignment problem is one of combinatorial optimization problems. Simulated annealing algorithm can be used to solve assignment problem. When using the algorithm， various technical issues of the algorithm must be considered， such as the form of solution， the initial temperature account， the formation of neighborhood， accepting and giving up the solution， suspension conditions of both inside and outside cycles etc. Under VB programming environment， the author carries out the solution process of the algorithm. Examples simulation shows that the method can jump out of local optimum solution with a certain probability to achieve global optimization.

Key words: VB;simulated annealing algorithm;assignment problem;simulation

1 引言

在企業(yè)、公司的運(yùn)營與管理中，管理者總是希望把人員最佳分派以發(fā)揮其優(yōu)勢(shì)，從而降低成本、提高效益。例如某公司需完成 m項(xiàng)任務(wù)，恰好有n名員工可承擔(dān)這些任務(wù)（n≥m）；每項(xiàng)任務(wù)只能由一名員工來做，每名員工也只能做一項(xiàng)任務(wù)；不同的員工完成各項(xiàng)任務(wù)的成本不同。問怎樣分配任務(wù)公司的花費(fèi)最小[1] ?這類問題被稱為標(biāo)準(zhǔn)的指派問題 (assignment problem)。模擬退火算法(Simulated Annealing，簡(jiǎn)稱SA)的思想最早是由Metropolis等(1953年)提出的，1983年Kirkpatrick等成功的將其用于組合優(yōu)化問題中。模擬退火算法在某初溫下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部?jī)?yōu)解能概率性地跳出并最終趨于全局最優(yōu)[2]。本文在VB編程環(huán)境完成模擬退火算法求解指派問題。

2 指派問題模型

有n個(gè)人，m項(xiàng)任務(wù)（n≥m），一個(gè)人最多可以干一項(xiàng)任務(wù)，而一項(xiàng)任務(wù)只能由一個(gè)人做。cij表示第i個(gè)人做第j項(xiàng)任務(wù)的費(fèi)用，找出任務(wù)分配方案，使得總費(fèi)用最小。首先引入一個(gè)0-1變量xij：

(1)

模型為：

3 模擬退火算法（SA算法）

模擬退火算法的基本思想是將組合優(yōu)化問題比做成一個(gè)熱力學(xué)系統(tǒng)，將優(yōu)化問題的費(fèi)用函數(shù)f(s)比擬成系統(tǒng)的能量E(i)，組合優(yōu)化問題的解s就比擬成退火過程中能量的狀態(tài)i。把優(yōu)化求解過程比擬成系統(tǒng)逐步降溫( 迭代搜索) 達(dá)到最低能量狀態(tài)的退火過程。通過模擬退火過程獲得優(yōu)化問題的全局最優(yōu)解，其算法先確定一個(gè)能量函數(shù)即目標(biāo)函數(shù)，求解最優(yōu)化問題一般通過Metropolis抽樣和退火兩個(gè)過程實(shí)現(xiàn)。該算法在接受較優(yōu)解的同時(shí)，還在一定范圍內(nèi)接受差解，從而使模擬退火算法能跳出局部最優(yōu)解而獲得最優(yōu)解[3]。

模擬退火算法步驟[4]：

STEP 1:任選—個(gè)初始解s0；s:=s0；k:=0；t0:=tmax(初始溫度)；

STEP 2:若在該溫度達(dá)到內(nèi)循環(huán)停止條件，則到STEP3；否則，從鄰域N(s)中隨機(jī)選一個(gè)（新解）q，計(jì)算Δfsq=f(s)-f(q);若Δfsq≤0，則s:=q;否則若時(shí)，則s:=q；重復(fù)STEP 2。

STEP 3：tk+1=d(tk)；k:=k+1；若滿足停止條件，終止計(jì)算；否則，回到STEP 2。

3.1 指派問題解s的形式

n表示員工數(shù)目，m表示任務(wù)數(shù)。在輸出結(jié)果時(shí)，用一個(gè)2×m的二維數(shù)組來表示解，即第一行表示各項(xiàng)工作，由1到m；第二行表示任務(wù)分配 ，即從n個(gè)人中選擇m個(gè)做各項(xiàng)工作。

顯然該解滿足模型中的約束條件 (3) 、(4) ，如果此解還滿足條件(1) 、(2)，則為可行解，否則為不可行解。

3.2 鄰域的生成

模擬退火算法中，解的搜索過程是在一個(gè)能量狀態(tài)點(diǎn)附近搜索另外一個(gè)能量狀態(tài)點(diǎn)。在溫度tk時(shí)刻，指定一個(gè)可行解s，然后任意交換兩個(gè)人的工作，生成一個(gè)新的解q，如果滿足模型的約束條件(1)和(2) ，則q就是s鄰域中的一個(gè)可行解。解s的鄰域就是由以上方法生成的可行解。

3.3 新解的接受與淘汰

在當(dāng)前解的鄰域中搜索到一個(gè)新解，是否接受，要看新解的目標(biāo)函數(shù)值（費(fèi)用）和當(dāng)前最優(yōu)解的目標(biāo)函數(shù)值（費(fèi)用）的差Δfsq，如果Δfsq≤0，則說明新解的目標(biāo)函數(shù)值較小，當(dāng)前解被新解代替；否則Δfsq>0，看新解的接受概率是否大于一個(gè)在0到1之間的隨機(jī)數(shù)ε，若大于，則接收新解為當(dāng)前最優(yōu)解，否則舍棄該解。

3.4 初始溫度以及退溫函數(shù)

初始溫度t0=Kδ，K是充分大的數(shù)，其中δ=max{f(s)∣s∈D}-min{f(s)∣s∈D}[4]，在實(shí)際計(jì)算中，可以選取K=10，20，100…等試驗(yàn)值， max{f(s)∣s∈D}和min{f(s)∣s∈D}是解空間隨機(jī)取的兩個(gè)解的目標(biāo)函數(shù)值。退溫函數(shù)采用tk+1=αtk，其中0<α<1，α越接近1，溫度下降越慢，溫度以相同的比率下降。

3.5 內(nèi)外循環(huán)中止條件

內(nèi)循環(huán)是在溫度tk時(shí)，采用固定長(zhǎng)度法結(jié)束內(nèi)循環(huán)。因?yàn)橹概蓡栴}的鄰域是兩個(gè)人的任務(wù)交換生產(chǎn)新的解，故它的大小是n(n-1)/2，我們可以選取迭代步數(shù)為n(n-1)/2。外循環(huán)采用零度法，模擬退火的最終溫度為零，因此可以給定一個(gè)比較小的正數(shù)ε，當(dāng)溫度tk≤ε時(shí)，外循環(huán)停止。

4 SA算法解指派問題的VB的實(shí)現(xiàn)

4.1 算法中所需的主要變量的定義

包括最優(yōu)解數(shù)組Mn(Pn，Tn)，最優(yōu)解的解碼數(shù)組Nn(2，Tn)；搜索鄰域中的隨機(jī)解Ch(Pn，Tn)，該隨機(jī)解的接受概率變量Pc，C(Pn，Tn)工作價(jià)值矩陣。

4.2 算法中所有功能函數(shù)的實(shí)現(xiàn)

模擬退火算法的初始化，此過程是用commond控件的click事件的來完成的，初始化包括：工作數(shù)、員工數(shù)、初始溫度比率和溫度下降率的輸入，價(jià)值矩陣的生成，計(jì)算初始退火溫度，給出一個(gè)可行的初始解；執(zhí)行模擬退火算法的外循環(huán)，此過程在主函數(shù)中使用do…while語句來控制。在外循環(huán)中調(diào)用鄰域搜索函數(shù)LinYu(x()， y()， z())，退火溫度是通過tk+1=αtk方式下降。鄰域搜索函數(shù)LinYu(x()， y()， z())是整個(gè)算法的核心函數(shù)，它實(shí)現(xiàn)的是在tk溫度下搜索可行解，并且判斷是否接受此解即實(shí)現(xiàn)的是算法的內(nèi)循環(huán)。此外還有幾個(gè)輔助函數(shù)：求解目標(biāo)值函數(shù)f1(x()， y)，拷貝函數(shù)copyArray x()， y()，解碼函數(shù)f3(x()， y())用于輸出最優(yōu)解等。

4.3鄰域搜索子函數(shù)LinYu Mn()， a()， Ch()的主要代碼

Fori = 1 To Pn - 1 '形成搜索鄰域

For d = i + 1 To Pn

b1 = 0

For j = 1 To Tn

b1 = b1 + z(i， j) + z(d， j)

Next j

Ifb1 >= 1 Then '如果兩個(gè)人中至少有一個(gè)人有工作，就可以交換兩j = 1個(gè)人的工作，否則不交換

For To Tn'滿足交換條件實(shí)行交換

h = z(i， j)

z(i， j) = z(d， j)

z(d， j) = h

Next j

f1 z()， m '計(jì)算交換之后所得新解的目標(biāo)函數(shù)值m

f1 x()， min'計(jì)算當(dāng)前最優(yōu)解的目標(biāo)函數(shù)值min

r = m - min'計(jì)算新解的目標(biāo)值和最優(yōu)解的函數(shù)值之間的差r

Ifr <= 0 Then'若新解的函數(shù)值小于最優(yōu)解的函數(shù)值，用當(dāng)前新解替換最優(yōu)解

copyArray z()， x()

Else'否則，判斷接收概率Pc是否大于(0，1)之間的一個(gè)隨機(jī)數(shù)

sjs = Rnd'sjs是一個(gè)隨機(jī)數(shù)

Pc = Exp(-r / T)

IfPc > sjsThen copyArray z()， x()'以概率Pc接受此新解為最優(yōu)解

End If

End If

End If

copyArrayy()， z() '重新給交換矩陣賦值

Next d'進(jìn)行下一個(gè)鄰域中可行解是搜索

Next i

5 仿真數(shù)據(jù)以及運(yùn)行結(jié)果分析

假設(shè)人數(shù)Pn=6，工作Tn=4，價(jià)值矩陣C（6，4）為：

＜E:\\2008學(xué)術(shù)交流\\200學(xué)術(shù)交流第四卷第八期(2008總第35期)\\第1次96篇\\1.3軟件設(shè)計(jì)開發(fā)\\dcl05.tif＞

當(dāng)rate=10，K=0.6時(shí)，算法仿真圖及所得最優(yōu)分配方案見圖1：

＜E:\\2008學(xué)術(shù)交流\\200學(xué)術(shù)交流第四卷第八期(2008總第35期)\\第1次96篇\\1.3軟件設(shè)計(jì)開發(fā)\\dcl06.tif＞

由圖1可見，該算法可以實(shí)現(xiàn)全局尋優(yōu)。曲線隨著迭代次數(shù)的增加一直在波動(dòng)，體現(xiàn)了該算法尋優(yōu)過程中以一定的概率接受較優(yōu)解，跳出局部最優(yōu)，實(shí)現(xiàn)全局尋優(yōu)。

表1是該算法不同的初始溫度比率rate及不同的溫度下降率K下，執(zhí)行模擬退火算法時(shí)的迭代步數(shù)、所用時(shí)間，以及得到的最優(yōu)解目標(biāo)函數(shù)值情況。可以看出，改變初始溫度比率rate和溫度下降率K，雖然都可以得到最優(yōu)解，但是隨著rate和K的增大，迭代次數(shù)也在增加，效率在降低，所以要確定rate和K合理數(shù)值是提高該算法運(yùn)行是的效率方法之一。

表1 不同rate和K下的模擬退火算法比較

＜E:\\2008學(xué)術(shù)交流\\200學(xué)術(shù)交流第四卷第八期(2008總第35期)\\第1次96篇\\1.3軟件設(shè)計(jì)開發(fā)\\dcl07.tif＞

6 結(jié)束語

在VB編程語言環(huán)境下實(shí)現(xiàn)模擬退火算法，能夠找到指派問題最優(yōu)解分配方案。仿真結(jié)果表明了該算法的有效性。同時(shí)從仿真結(jié)果可以看出，初始溫度比率rate和溫度下降率K對(duì)找到最優(yōu)解的效率及迭代次數(shù)有影響。從最優(yōu)解目標(biāo)函數(shù)值的仿真曲線上可以看到，模擬退火算法的迭代過程體現(xiàn)了集中和擴(kuò)散兩個(gè)策略的平衡，該算法可以跳出局部最優(yōu)，而實(shí)現(xiàn)全局最優(yōu)。

參考文獻(xiàn)：

[1] 李秦渝，代存杰.禁忌搜索算法解指派問題[J].甘肅科技，2007，23(10):24-26.

[2] 王凌.智能優(yōu)化算法及其應(yīng)用[M].北京:清華大學(xué)出版社，2001.

[3] 駱文輝，劉少偉，周建美，等.目標(biāo)分配問題的模擬退火算法[J].上海航天，2008(1):61-64.

[4] 邢文訓(xùn)，謝金星.智能優(yōu)化算法及其應(yīng)用[M].北京:清華大學(xué)出版社，1999:94-126.