1、第十四章第十四章 布局設計的現代算法布局設計的現代算法14.1布局設計的數學建模求解算法 目前計算機布置算法可分為兩類。一類是對布局設計問題簡化并建立數學模型，再采用計算機現代算法求解的方法，稱為數學建模求解算法。這類方法不能得出布局設計圖，需要設計人員根據算出的數據，構思布局設計，然后再在圖形繪制工具中繪制布局圖。另一類是用計算機算法直接對布局圖進行優化求解，最后得出優化的布局設計圖， 14.1.1設施布局問題數學模型設施布局問題數學模型1單行布置的模型 首先要做如下假設，假設機器的形狀是方形，機器排成一列，機器的方位是預先確定的。如圖14-1所示。設有n臺機器排成一列，要確定各機器的位置坐

2、標，使機器間運送物料的成本最低。 圖14-1 單行布置示意圖2多行布置的模型圖14-2 多行布置示意圖3二次分派問題模型 給定n個地點，現要把n個設施分配到這n個地點，這實際上是組合問題，共有n！種方案，在這n！種方案里找最佳方案使總的物料搬運費用最短。如果n等于4，則共有24種方案，顯然可以用窮舉發來求最優方案，如果n等于10，則有3628800種方案，如果n大于10，方案會更多，顯然沒有辦法窮舉，往往通過一些啟發式算法尋找次優方案。 11niikx11nkikx11njjhx11nhjhxjhikninknjnhkhxxdxf1111ijijfc21)(min14.1.2遺傳算法在布局設計

3、中的應用遺傳算法在布局設計中的應用1遺傳算法的結構遺傳算法的結構 遺傳算法開始時先隨機地產生一些染色體（欲求解問題的侯選解），計算其適應度，根據適應度對諸染色體進行選擇、交換、變異等遺傳操作，剔除適應度低的染色體，從而得到新的群體。由于新群體的成員是上一代群體的優秀者，繼承了上一代的優良性態，因而在總體上優于上一代。就這樣反復迭代，向著更優解的方向進化，直至滿足某種預定的優化指標。(1)編碼與譯碼 許多應用問題結構很復雜，但可以化為簡單的位串形式編碼表示，我們將問題結構變換為位串形式編碼表示的過程叫編碼；而相反將位串形式編碼表示變換為原問題結構的過程叫譯碼。我們把位串形式編碼表示叫染色體，有時

4、也叫個體。 (2)適應度函數 為了體現染色體的適應能力，引入了對問題中的每一個染色體都能進行度量的函數，叫適應度函數。通過適應度函數來決定染色體的優、劣程度，它體現了自然進化中的優利劣汰原則。對優化問題，適應度函數就是目標函數。(3)遺傳操作 簡單遺傳算法的遺傳操作主要有三種:選擇(selection)、交叉(crossover)、變異(mutation)。改進的遺傳算法大量擴充了遺傳操作，以達到更高的效率。 選擇操作也叫復制操作，根據個體的適應度函數值所度量的優、劣程度決定它在下一代是被淘汰還是被遺傳。一般地說，選擇將使適應度較大(優良)個體有較大的存在機會，而適應度較小（低劣）的個體繼續存

5、在的機會也較小。 交叉操作的簡單方式是將被選擇出的兩個個體P1和P2作為父母個體，將兩者的部分碼值進行交換。圖 14-3 交叉前示意圖 圖 14-4 交叉后示意圖 變異操作的簡單方式是改變數碼串的某個位置上的數碼。我們先以最簡單的二進制編碼表示方式來說明. 圖14-5 變異示意圖(4)控制參數 并不是所有被選擇了的染色體都要進行交叉操作和變異操作，而是以一定的概率進行，交叉概率 種群的染色體總數叫種群規模， 另一個控制參數是個體的長度2. 遺傳算法應用舉例問題的描述 假設有九臺設備M1M9，在某個生產階段設備之間的物流矩陣(實際上就是從至表)如圖所示。現需要將這九臺進行布置，使其運輸工具的總行

6、程最小。假設由于場地的限制，設備需要分成三行來排列，且各生產設備之間距離相等為單位1 圖14-6 設備之間的物流矩陣(2)遺傳算法的設計 編碼方法：這里使用浮點數編碼方法，用設備的位置向量表示染色體 適應度函數： maxmaxmax)(0)()()(CxfCxfxfCxF 初始群體的產生：以隨機的方式將這九臺設備進行排列，共得到M種設備布局形式。 選擇算子：這里使用比例選擇算子，即個體被選中并遺傳到下一代群體中的概率與該個體的適應度大小成正比。 交叉算子：將群體中M個個體以隨機的方式兩兩配對，組成M/2對配對個體組。每對配對個體組隨機選擇其中之一為Parent1，則另外一個個體為Parent2

7、。 變異算子：隨機地選取個體中兩個基因座，交換它們的基因，產生新個體。圖14-7 交叉算子示意圖(3)運算結果 在該算法中，采用保留最佳個體策略，加快了收斂速度，并且取得較優的解。計算出最優布局為(2，4，1，6，3，5，8，7，9)。在此布局下，目標函數值為2530，而最劣布局的目標函數值為3653。14.1.3 模擬退火算法在布局設計中的應用模擬退火算法在布局設計中的應用 1模擬退火算法流程隨機產生一個初始解，計算目標函數值;(2) 設置初始溫度 (1) (3) 當 時，對應某個具體的溫度T，重復執行步驟（4）K次。 minTT (4) 對當前最優解按照某一鄰域函數，產生一新的解。計算 新

8、的目標函數值，并計算目標函數值的增量，根據增量的正負，確定最優解。(5) 步驟（4）完成k次重復后，令 ，若 執行步驟（6），若 ，回到步驟3。(6) 輸出當前最優解，計算結束。newTT minTT minTT 2模擬退火算法的簡單應用 考慮遺傳算法部分的例題，用模擬退火算法求解，要點如下： 解空間S是所有布局方案的集合，S中的成員記為： ，其中為第k臺機器所在的地點。初始解可選為(1，n)。 此時的目標函數即為運輸工具的總行程 ),(21nkwwwwninjjiijdqwf11)(若km，則將 變為：),(121nmkkwwwwww),(1121nkkmmwwwwwww),(1121nkk

9、mmwwwwwww),(11111knnkmmmwwwwwwww3模擬退火算法的參數控制問題 (1) 溫度T的初始值設置問題。 溫度T的初始值設置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優解的可能性大，但因此要花費大量的計算時間；反之，則可節約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據實驗結果進行若干次調整。 (2) 退火速度問題。 模擬退火算法的全局搜索性能也與退火速度密切相關。一般來說，同一溫度下的“充分”搜索(退火)是相當必要的，但這需要計算時間。實際應用中，要針對具體問題的性質和特征設置合理的退火平衡條件。 (3) 冷卻進

10、度表T(t)。 冷卻進度表是指從某一高溫狀態To向低溫狀態冷卻時的降溫管理表。假設時刻t的溫度用T(t)來表示，則經典模擬退火算法的降溫方式為： 而快速模擬退火算法的降溫方式為： )1lg()(0tTtTtTtT1)(014.2 布置圖的設計算法14.2.1 布置圖設計算法的分類與原理布置圖設計算法的分類與原理1算法的輸人數據類型 布置算法可以按照它們所需的輸人數據類型分類。有些算法只接受像相關圖之類定性的“物流”數據，而有些接受由從至表表示的定量物流數據；還有一些算法同時接受相關圖和從至表兩種數據（如BLOCPLAN），但是在評價布置方案時只能選擇這兩種數據中的一種。現在的算法更趨向于采用從

11、至表數據， 2基于“量距積的和最小”為目標的算法 首先考慮基于距離的目標，設m為部門數， 為從部門i到部門j的物流量； 為將一個單元的物料從部門i移動到部門j單位距離的成本。于是目標函數是要使單位時間內部門間物料的移動總成本最小化 ijfijcijijmimjijdcfZ11min3基于相近程度目標函數的算法 考慮基于相近程度的目標函數，其中相近程度的分值是按布置中所有相鄰兩個部門物流量值的總和來計算的。如果部門i和j相鄰就令 1，否則； 0，目標是求相鄰值最大 ijxijxijmimjijxfZ11max 但如果要評價一個特定布置在某個上下邊界的相對效率（相對優劣）時，設施規劃人員可采用以下

12、“歸一化”的相鄰值。mimjijmimjijijfxfZ1111 如果采用 “負流量”值。歸一化的相鄰值計算公式修改如下FjiFjiijijFjiFjiijijijijffxfxfZ),(),(),(),()1 (14.2.2 CRAFT算法算法1.CRAFT算法的初始條件 CRAFT 是一種改進型布置算法，所以先要給它一定的基礎，如從一個已有設施的實際布置或由另一種算法給出的初始布置開始，先確定初始布置中各部門的矩心，然后計算兩兩部門距心之間直角距離，并存儲在距離矩陣之中。 2.CRAFT算法的迭代過程 在程序考慮部門i和j的位置交換時，不是實際交換它們的位置再來計算新的矩心和布置成本，而是

13、臨時互換當前布置中部門i和部門j的矩心數據來估算布置成本。在按估算的布置成本找到最佳交換后，CRAFT程序再交換兩者的位置并計算它們新的矩心后才開始下一步迭代。3.迭代結果依賴于路徑 在搜索更好結果時，CRAFT只是從每次迭代中選擇最好的交換方式，這是一種最速下降法。在上述的搜索過程中，它既不瞻前也不顧后。因此，CRAFT搜索時會在第一次碰到二相或三相最佳方案時就予以終結，這樣的結果很可能只是局部最優解。 4.CRAFT用于非矩形廠房的策略 CRAFT一般僅限用于矩形廠房，但通過引人“虛”部門它也可以用于非矩形廠房。虛部門與其他部門沒有任何物流或相互作用，但要由布置規劃人員指定它的面積。 一般

14、來說，虛部門主要用于：填補建筑物的不規則之處；代表一設施內的障礙或不能用的區域（如樓梯、電梯、廠房維護區等）；代表廠房的額外空間；在最終布置中用于幫助通道位置的確定。5.CRAFT布置的修改 CRAFT的優點之一是能以合理的精確度找到初始布置。 這主要是因為CRAFT能在非矩形建筑物內的任何地方容納矩形的部門或障礙。但是除了高度依賴路徑外，CRAFT的缺點是產生的最終布置很少有部門形狀是規則的，也少有直線形的且不中斷的通道。 14.2.3 CRAFT算法案例算法案例1從至表2計算它們矩心間的直角距離 CRAFT首先計算圖14-8所示各部門的矩心。然后對每一個部門單位對計算它們矩心間的直角距離，

15、并乘上從至表中相應的數據。例如部門A和B距心間直角距離為6格，CRAFT就以6乘以45，并將結果加到目標函數值中。對所有非零流的部門單位對，重復上述過程，得到初始布置的成本為2974單位（這里CRAFT按方格數來計算，如果按英尺計算，實際布置成本為29742059480單位）。圖14-8初始CRAFT布置及各部門的矩心3迭代與交換 隨后，CRAFT進行第一次迭代，交換部門E和F的位置所得布置如圖14-9所示。部門E和F面積并不相等，但位置相鄰，因此想像用一個框架將E和F框起來，不包括其他部門（如果E和F不相鄰就找不到這樣的框子）。CRAFT就在這個框架里交換E和F的位置。 圖14-9交換部門E

16、和F的位置所得布置 下一次迭代時，估算的布置成本降低值是95單位，CRAET交換部門B和C的位置后的結果如圖14-10所示。該布置成本為2833.50單位，實際降低119.50單位。這清楚地說明估算的誤差在每一個方向都有。 圖14-10交換B、C位置所得布置圖14-11修改打磨后所得的布置4. 布置的修改 在打磨布置時，分析人員一般不采用網格，而采用連續式表現方式，這樣就可以平滑部門邊界并在必要時稍微修改部門的面積和取向。對圖14.10所示的布置打磨后，所得的布置如圖14.11所示。 5相鄰不是交換的充分條件 前面的短評中提到對兩個面積不等的部門，相鄰是不影響其他部門進行位置交換的必要而非充分

17、條件。顯然，相鄰是必要的，否則就不可能這樣交換，但相鄰并不是充分條件，可以由下例說明。 圖14-12部門2和4不能交換 6三相交換 三相交換所需的條件比較復雜。假設部門i，j和k要進行三相交換，如部門i換j，部門j換k，部門k換i。如果能用一個框架將部門i，j和k框起來，而不含其他部門，那么（除了上述部門2和4的情況），可以進行三相交換而不影響其他部門。注意要找到這樣的框架，三個部門中的每個部門井不一定都要和其他兩個共邊。例如部門i和j相鄰（但不與k相鄰），或者部門k與j相鄰（但不與i相鄰）時都可以找到這樣的框架。14.2.4 MCRAFT算法案例算法案例 MICRO-CRAFT（或簡稱MCRAFT ）類似于CRAFT，只是上述約束放松了（即MCRAFT可以不管兩個部門是否相鄰就進行換位）。 考慮