第14章布局設(shè)計的現(xiàn)代算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、并乘上從至表中相應(yīng)的數(shù)據(jù)。例如部門A和B距心間直角距離為6格，CRAFT就以6乘以45，并將結(jié)果加到目標(biāo)函數(shù)值中。對所有非零流的部門單位對，重復(fù)上述過程，得到初始布置的成本為2974單位（這里CRAFT按方格數(shù)來計算，如果按英尺計算，實際布置成本為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的位置后的結(jié)果如圖14-10所示。該布置成本為2833.50單位，實際降低119.50單位。這清楚地說明估算的誤差在每一個方向都有。 圖14-10交換B、C位置所得布置圖14-11修改打磨后所得的布置4. 布置的修改 在打磨布置時，分析人員一般不采用網(wǎng)格，而采用連續(xù)式表現(xiàn)方式，這樣就可以平滑部門邊界并在必要時稍微修改部門的面積和取向。對圖14.10所示的布置打磨后，所得的布置如圖14.11所示。 5相鄰不是交換的充分條件 前面的短評中提到對兩個面積不等的部門，相鄰是不影響其他部門進行位置交換的必要而非充分

17、條件。顯然，相鄰是必要的，否則就不可能這樣交換，但相鄰并不是充分條件，可以由下例說明。 圖14-12部門2和4不能交換 6三相交換 三相交換所需的條件比較復(fù)雜。假設(shè)部門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可以不管兩個部門是否相鄰就進行換位）。 考慮