模擬退火算法在動態(tài)設施布置中的應用研究

1、模擬退火算法在動態(tài)設施布置中的應用研究    畢業(yè)論文    摘要制造業(yè)必須以運營效率和快速的反應適應產(chǎn)品的復雜化和需求。探討了對生產(chǎn)部門間制造設施的布置和重組，職稱論文發(fā)表以使物料搬運和重組成本最小化，進而提出動態(tài)設施布置問題及資源的有效組合和配置，確保設施間的物流通暢和提高企業(yè)生產(chǎn)效率。 關鍵詞模擬退火啟發(fā)式動態(tài)設施布置 靜態(tài)設施布置問題（staticfacilitylayoutproblem，SFLP）被認為是解決設施布置的有效方法。資源（如機器、部門或者勞動力）的有效組合和配置，可以確保設施間的物流通暢和提

2、高企業(yè)生產(chǎn)效率。 當設施間的物流量在布置范圍內(nèi)變化時，SFLP就成了動態(tài)。這就是由Rosenblatt首次提出的著名的動態(tài)設施布置問題（dynamicfacilitylayoutproblem，DFLP）。 啟發(fā)式算法成功發(fā)展之前，曾經(jīng)用禁忌搜索技術、遺傳算法等工具來求解大型組合優(yōu)化問題。換言之，就是利用最速下降成對交換啟發(fā)式（steepest-descentpairwiseexchangeheuristic）從初始解開始產(chǎn)生鄰域解。通常這類啟發(fā)式的時間效率不高，并且只收斂于局部最優(yōu)。為了克服這些缺陷，本文提出用模擬退火啟發(fā)式解決DFLP最優(yōu)問題，用固體退火的思想來接受鄰域解，以免陷入局部最優(yōu)

3、。 1DFLP的基本思想 企業(yè)隨著市場的變化而調(diào)整其設施布置，本文稱其為柔性布置。DFLP就是以將來的可預測變化為基礎的。預期的未來可以劃分為很多區(qū)段，這些區(qū)段可以定義為周、月甚至是年。研究動態(tài)設施布置問題時，設每1區(qū)段的流量數(shù)據(jù)是可預測和連續(xù)的，則設施布置問題中的每個區(qū)段，可以用SFLP（QAP）進行解決。 DFLP的布置規(guī)劃是以可預測未來為基礎的1系列布置，每個布置規(guī)劃跟每個區(qū)段有關。在布置過程中，在原有基礎上對設施的移動而產(chǎn)生的成本稱為再布置成本，設施的再布置可能導致產(chǎn)品的損失，還可能需要專業(yè)人員和專門的設備。因此，再布置成本由勞動力成本、設備成本和產(chǎn)品損耗成本組成；另外，對制造設施來說

4、，在設施間還要對物料進行搬運以滿足設施加工的需要，搬運物料所投入的成本，稱為物料搬運成本。成本的大小由設施間物料的流量以及設施間的距離決定，它是決定布置是否合理的最重要的衡量標準，1般占總運作成本的20%50%，占產(chǎn)品制造成本的15%70%，這成為設施布置中需要考慮的重要指標。因此，布置規(guī)劃的總成本由所有區(qū)段的物料搬運成本和與再布置成本之和組成。 布置規(guī)劃的目的是使搬運成本與再布置成本之和達到最小。在這過程中，須重復交換部門間的位置以滿足上述要求，當物料搬運成本大于再布置成本時，可以把DFLP看作1系列的SFLPs（QAPs）來求解。 附圖所示是具有6個設施在3個區(qū)段的DFLP事例。在第1區(qū)段

5、，設施1、2、3、4、5和6分別被安置在位置3、4、1、5、2和6，由于設施3和5在第2區(qū)段被分配到不同的位置（即分別在位置2和1），則其再布置成本就是把設施3移動到位置2所產(chǎn)生的成本與把設施5移動到位置1所產(chǎn)生的成本之和。另外，在布置中，由于在階段2和在階段3的布置是1樣的，故在階段3中沒有再布置成本。 為了操作方便，可以對DFLP進行如下的假設：設施間的流量是動態(tài)而確定的（deterministic），設施的面積和位置的大小1致，布置類型為已知的（即如附圖為2×3的布置）；部門之間的距離確定為1個單位。 關于DFLP問題的求解，本文在Urban提出的最速下降成對交換啟發(fā)式解法之上

6、，提出用1種通用的模擬退火算法和最速下降成對交換相結合的啟發(fā)式算法來求解DFLP的最優(yōu)化問題。 2模擬退火算法 模擬退火（SimulatedAnnealing，SA）算法的思想最早是由N.Metropolis等人在1953年借鑒統(tǒng)計力學中物質退火方法而提出的。其思想觀念來自固體的退火過程，加熱固體至最高溫使之溶化，冷卻時，液體中原子的熱運動漸漸減弱，隨著溫度的徐徐降低，原子運動漸趨有序，達到固體的最低能量狀態(tài)或者基態(tài)。根據(jù)Metropolis準則，粒子在溫度T時趨于平衡的概率為e，其中E為溫度T時的內(nèi)能，E為其改變量，k為Boltzmann常數(shù)。    

7、1982年，Kinkpatrick等人首次用模擬退火算法解決組合優(yōu)化問題，將內(nèi)能E模擬為目標函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法。由初始解i和控制參數(shù)初值t開始，對當前解重復“產(chǎn)生新解-計算目標函數(shù)差-判斷是否接受-接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優(yōu)解。 下面給出模擬退火算法的基本步驟： （1）給定模型每1個參數(shù)變化范圍，在這個范圍內(nèi)隨機選擇1個初始模型m0，并計算相應的目標函數(shù)值E(m0)。 （2）對當前模型進行擾動產(chǎn)生1個新模型m，計算相應的目標函數(shù)值E(m)，得到E=E（m）-E（m0）。 （3）若E<0，則新模型

8、m被接受；若E>0，則新模型按概率P=exp（-E/T）進行接受，T為溫度。當模型被接受時，置m0=m，E（m0）=E（m）。 （4）在溫度T下，重復1定次數(shù)的擾動和接受過程，即重復步驟（2）、（3）。 （5）緩慢降低溫度T。 （6）重復步驟（2）、（5），直至收斂條件滿足為止。 3DFLP中的模擬退火啟發(fā)式解法 3.1參數(shù)設置 （1）接受新布置的概率確定。用模擬退火算法來解決DFLP的最優(yōu)化問題，首先要確定的是接受新布置的概率。接受概率如下： P（Tc）=exp（Tc/Tc） Tc=T0r-1r=1，2，R 其中：Tc表示當前溫度，Tc表示總成本的改變量(如果鄰域解的成本比當前解的成本

9、低，則Tc=f（y）-f（y）)，T0是初始溫度，為降溫率，通常為0.9，r-1為溫度降低的數(shù)量。設x是01之間的隨機數(shù)，且x（2）初始溫度的確定。SA啟發(fā)式需要設置參數(shù)，用來降低當前溫度以進行尋優(yōu)。在程序執(zhí)行的初期，接受鄰域解的概率較高，這是初始溫度的高低造成的。初始溫度選得太高，則算法的計算量增加許多；反之，初始溫度選得太低，則1旦算法落入局部最優(yōu)解的陷阱中就無法再跳出來，從而無法求得全局近似最優(yōu)解。本文采用如下公式確定初始溫度： T0=-Tc/1n（p（Tc）=-0.01f（y0）/1n（0.25） 其中：T0表示初始溫度，f(y0)表示初始解的成本。 3.2DFLP中的算法描述 模擬退

10、火算法是1種隨機算法，在降溫的過程中，須執(zhí)行1系列的成對交換，確保系統(tǒng)處于穩(wěn)定狀態(tài)。把SA啟發(fā)式算法直接應用于DFLP的思想，叫做SAI，其步驟如下： 步驟0：把每階段的流量矩陣、長度矩陣和再布置成本作為輸入數(shù)據(jù)，確定SA參數(shù)：設T0為初始溫度，為降溫率，A為每次溫度變化時產(chǎn)生的變化數(shù)量，Tmin為最低溫度。 步驟1：假定存在溫度變化產(chǎn)生器r，置r=1。 步驟2：產(chǎn)生初始解y0，并將其賦予當前解（即置y=y0）；產(chǎn)生當前解的成本f（y）；設置下列參數(shù)：best_sol=y；best_cost=f（y）。 步驟3：給每個溫度改變次數(shù)賦予初值：i=0，根據(jù)退火調(diào)度設置當前溫度，Tc=T0r-1，如

11、果Tc步驟4：隨機選取區(qū)段t，然后隨機選取其中的兩個設施u和v，相互交換其位置，得到的解設為y，置i=i+1；計算總成本的改變量：Tc=f（y）-f（y）。 步驟5：if（Tc<0）or（Tc>0andx=random（0，1）f（y），thenbest_cost=f（y）andbestsol=y。 步驟6：ifi=A，thenupdater=r+1返回步驟3，否則返回步驟4。 以上的啟發(fā)式參數(shù)最初的、A和Tmin由試驗得出，Tmin的值取0.01（Tmin=0.01）。由于p（Tc）=exp（-VTc/Tc）以及Tc=T0，r=1。 在步驟2中，初始解或布置規(guī)劃y的值y0=x0（1），x0（2），x0（f），初始解中的n元矢量x0（f）代表了t階段的初始布置規(guī)劃，其中t=1，2，T。另外x0（f）=x0（1），x0（2），x0（N），其中的元素x0（i）是矢量，代表部門i的位置，i=1，2，N。例如，有6個部門的初始布置中，第1階段