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

來源：互聯(lián)網(wǎng)   發(fā)布日期：2011-10-17 12:54:05   瀏覽：7957次  

    摘要制造業(yè)必須以運營效率和快速的反應(yīng)適應(yīng)產(chǎn)品的復雜化和需求。探討了對生產(chǎn)部門間制造設(shè)施的布置和重組，以使物料搬運和重組成本最小化，進而提出動態(tài)設(shè)施布置問題及資源的有效組合和配置，確保設(shè)施間的物流通暢和提高企業(yè)生產(chǎn)效率。
    關(guān)鍵詞模擬退火啟發(fā)式動態(tài)設(shè)施布置
    靜態(tài)設(shè)施布置問題被認為是解決設(shè)施布置的有效方法。資源的有效組合和配置，可以確保設(shè)施間的物流通暢和提高企業(yè)生產(chǎn)效率。
    當設(shè)施間的物流量在布置范圍內(nèi)變化時，SFLP就成了動態(tài)。這就是由Rosenblatt首次提出的聞名的動態(tài)設(shè)施布置問題。
    啟發(fā)式算法成功發(fā)展之前，曾經(jīng)用禁忌搜索技術(shù)、遺傳算法等工具來求解大型組合優(yōu)化問題。換言之，就是利用最速下降成對交換啟發(fā)式從初始解開始產(chǎn)生鄰域解。通常這類啟發(fā)式的時間效率不高，并且只收斂于局部最優(yōu)。為了克服這些缺陷，本文提出用模擬退火啟發(fā)式解決DFLP最優(yōu)問題，用固體退火的思想來接受鄰域解，以免陷入局部最優(yōu)。
1DFLP的基本思想
    企業(yè)隨著市場的變化而調(diào)整其設(shè)施布置，本文稱其為柔性布置。DFLP就是以將來的可猜測變化為基礎(chǔ)的。預期的未來可以劃分為很多區(qū)段，這些區(qū)段可以定義為周、月甚至是年。研究動態(tài)設(shè)施布置問題時，設(shè)每一區(qū)段的流量數(shù)據(jù)是可猜測和連續(xù)的，則設(shè)施布置問題中的每個區(qū)段，可以用SFLP進行解決。
    DFLP的布置規(guī)劃是以可猜測未來為基礎(chǔ)的一系列布置，每個布置規(guī)劃跟每個區(qū)段有關(guān)。在布置過程中，在原有基礎(chǔ)上對設(shè)施的移動而產(chǎn)生的成本稱為再布置成本，設(shè)施的再布置可能導致產(chǎn)品的損失，還可能需要專業(yè)人員和專門的設(shè)備。因此，再布置成本由勞動力成本、設(shè)備成本和產(chǎn)品損耗成本組成；另外，對制造設(shè)施來說，在設(shè)施間還要對物料進行搬運以滿足設(shè)施加工的需要，搬運物料所投入的成本，稱為物料搬運成本。成本的大小由設(shè)施間物料的流量以及設(shè)施間的距離決定，它是決定布置是否合理的最重要的衡量標準，一般占總運作成本的20%～50%，占產(chǎn)品制造成本的15%～70%，這成為設(shè)施布置中需要考慮的重要指標。因此，布置規(guī)劃的總成本由所有區(qū)段的物料搬運成本和與再布置成本之和組成。
    布置規(guī)劃的目的是使搬運成本與再布置成本之和達到最小。在這過程中，須重復交換部門間的位置以滿足上述要求，當物料搬運成本大于再布置成本時，可以把DFLP看作一系列的SFLPs來求解。
    附圖所示是具有6個設(shè)施在3個區(qū)段的DFLP事例。在第一區(qū)段，設(shè)施1、2、3、4、5和6分別被安置在位置3、4、1、5、2和6，由于設(shè)施3和5在第2區(qū)段被分配到不同的位置，則其再布置成本就是把設(shè)施3移動到位置2所產(chǎn)生的成本與把設(shè)施5移動到位置1所產(chǎn)生的成本之和。另外，在布置中，由于在階段2和在階段3的布置是一樣的，故在階段3中沒有再布置成本。
    為了操作方便，可以對DFLP進行如下的假設(shè)：設(shè)施間的流量是動態(tài)而確定的，設(shè)施的面積和位置的大小一致，布置類型為已知的；部門之間的距離確定為一個單位。關(guān)于DFLP問題的求解，本文在Urban提出的最速下降成對交換啟發(fā)式解法之上，提出用一種通用的模擬退火算法和最速下降成對交換相結(jié)合的啟發(fā)式算法來求解DFLP的最優(yōu)化問題。
2模擬退火算法
    模擬退火算法的思想最早是由N.Metropolis等人在1953年借鑒統(tǒng)計力學中物質(zhì)退火方法而提出的。其思想觀念來自固體的退火過程，加熱固體至最高溫使之溶化，冷卻時，液體中原子的熱運動漸漸減弱，隨著溫度的漸漸降低，原子運動漸趨有序，達到固體的最低能量狀態(tài)或者基態(tài)。根據(jù)Metropolis準則，粒子在溫度T時趨于平衡的概率為e，其中E為溫度T時的內(nèi)能，ΔE為其改變量，k為Boltzmann常數(shù)。
    1982年，Kinkpatrick等人首次用模擬退火算法解決組合優(yōu)化問題，將內(nèi)能E模擬為目標函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法。由初始解i和控制參數(shù)初值t開始，對當前解重復“產(chǎn)生新解-計算目標函數(shù)差-判定是否接受-接受或舍棄”的迭代，并逐步衰減t值，算法終止時的當前解即為所得近似最優(yōu)解。
下面給出模擬退火算法的基本步驟：
    給定模型每一個參數(shù)變化范圍，在這個范圍內(nèi)隨機選擇一個初始模型m0，并計算相應(yīng)的目標函數(shù)值E。
    對當前模型進行擾動產(chǎn)生一個新模型m，計算相應(yīng)的目標函數(shù)值E，得到△E=E-E。
    若ΔE0，則新模型m被接受；若ΔE0，則新模型按概率P=exp進行接受，T為溫度。當模型被接受時，置m0=m，E=E。
   在溫度T下，重復一定次數(shù)的擾動和接受過程，即重復步驟、。
    緩慢降低溫度T。
   重復步驟、，直至收斂條件滿足為止。
3DFLP中的模擬退火啟發(fā)式解法
3.1參數(shù)設(shè)置
    接受新布置的概率確定。用模擬退火算法來解決DFLP的最優(yōu)化問題，首先要確定的是接受新布置的概率。接受概率如下：
P=exp
Tc=T0αr-1r=1，2，…，R
其中：Tc表示當前溫度，△Tc表示總成本的改變量，T0是初始溫度，α為降溫率，通常為0.9，r-1為溫度降低的數(shù)量。設(shè)x是0～1之間的隨機數(shù)，且x初始溫度的確定。SA啟發(fā)式需要設(shè)置參數(shù)，用來降低當前溫度以進行尋優(yōu)。在程序執(zhí)行的初期，接受鄰域解的概率較高，這是初始溫度的高低造成的。初始溫度選得太高，則算法的計算量增加許多；反之，初始溫度選得太低，則一旦算法落入局部最優(yōu)解的陷阱中就無法再跳出來，從而無法求得全局近似最優(yōu)解。本文采用如下公式確定初始溫度：
T0=-△Tc/1n）=-0.01f/1n
其中：T0表示初始溫度，f表示初始解的成本。
3.2DFLP中的算法描述
模擬退火算法是一種隨機算法，在降溫的過程中，須執(zhí)行一系列的成對交換，確保系統(tǒng)處于穩(wěn)定狀態(tài)。把SA啟發(fā)式算法直接應(yīng)用于DFLP的思想，叫做SAI，其步驟如下：
步驟0：把每階段的流量矩陣、長度矩陣和再布置成本作為輸入數(shù)據(jù)，確定SA參數(shù)：設(shè)T0為初始溫度，α為降溫率，A為每次溫度變化時產(chǎn)生的變化數(shù)量，Tmin為最低溫度。
步驟1：假定存在溫度變化產(chǎn)生器r，置r=1。
步驟2：①產(chǎn)生初始解y0，并將其賦予當前解；②產(chǎn)生當前解的成本f；③設(shè)置下列參數(shù)：best__sol=y；best__cost=f。
步驟3：給每個溫度改變次數(shù)賦予初值：i=0，根據(jù)退火調(diào)度設(shè)置當前溫度，Tc=T0αr-1，假如Tc步驟4：①隨機選取區(qū)段t，然后隨機選取其中的兩個設(shè)施u和v，相互交換其位置，得到的解設(shè)為y′，置i=i+1；②計算總成本的改變量：△Tc=f-f。
步驟5：iforf，thenbest__cost=fandbestsol=y。
步驟6：ifi=A，thenupdater=r+1返回步驟3，否則返回步驟4。
以上的啟發(fā)式參數(shù)最初的α、A和Tmin由試驗得出，Tmin的值取0.01。由于p=exp以及Tc=T0，r=1。
在步驟2中，初始解或布置規(guī)劃y的值y0=，初始解中的n元矢量αx0代表了t階段的初始布置規(guī)劃，其中t=1，2，…，T。另外αx0=，其中的元素x0是矢量，代表部門i的位置，i=1，2，…，N。例如，有6個部門的初始布置中，第一階段：αx0=，假如這個任務(wù)還用于階段2和階段3，αx0=αx0=αx0，則沒有再布置成本。簡言之，在階段1、2、3，設(shè)施1、2、3、4、5和6被布置在1、2、3、4、5、和6幾個位置。步驟2和3中，啟發(fā)式參數(shù)和數(shù)值被初始化，假如達到終止條件f）且x3.3改進的模擬退火算法在DFLP中的應(yīng)用
從上面的步驟中得知，把模擬退火的思想直接應(yīng)用于DFLP中求最優(yōu)解的方法，比較復雜，計算機執(zhí)行的效率也比較低，本文把這種思想稱為SAⅠ。針對SAⅠ復雜和執(zhí)行效率的缺點，在SAⅠ基礎(chǔ)上添加了正反饋技術(shù)的算法用于求解DFLP最優(yōu)化問題，把這種思想稱為SAⅡ。
SAⅡ執(zhí)行SAⅠ的1-6步驟，區(qū)別是在步驟5包含了正反饋技術(shù)，在步驟4重復執(zhí)行完隨機成對交換以后，獲取鄰域解y′。同時，獲取總成本改變量ΔTc。
由于SAⅡ和SAⅠ的唯一不同點在于步驟5，雖然SAⅡ啟發(fā)式執(zhí)行更多的步驟，但SAⅡ因需要較少的重復次數(shù)獲取高質(zhì)量的解，從而在計算上更有效率。
4結(jié)語
模擬退火算法作為一種有效的全局優(yōu)化算法，正以其思路清楚、原理簡單、使用靈活得到廣泛應(yīng)用。隨著全局優(yōu)化技術(shù)不斷發(fā)展，新的優(yōu)化機制、技術(shù)和方法不斷涌現(xiàn)，作為基礎(chǔ)算法的模擬退火算法亦可充分發(fā)揮其串行優(yōu)勢，自身不斷改進的同時不斷與新的優(yōu)秀算法結(jié)合，得出更合理、有效的混合優(yōu)化算法。由于在中文文獻中，暫時很少有人用模擬退火算法解決DFLP問題，本文提出用模擬退火算法求解DFLP最優(yōu)解的思想，以供參考。
參考文獻
1AlanR，McKendallJretc.Simulatedannealingheuristicsforthedynamicfacilitylayoutproblem.ComputersOperationsResearch，2005來源：論文網(wǎng)
2吳斐，侯云章.基于啟發(fā)式結(jié)果的模擬退火算法在布局問題中的應(yīng)用.物流技術(shù)，2005
3王金敏．布局問題的模擬退火算法.計算機輔助設(shè)計與圖形學學，1998
4謝云.模擬退火算法綜述.微計算機信息，1998

贊助本站