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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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