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

第十四章布局設計的現(xiàn)代算法14.1布局設計的數(shù)學建模求解算法目前計算機布置算法可分為兩類。一類是對布局設計問題簡化并建立數(shù)學模型，再采用計算機現(xiàn)代算法求解的方法，稱為數(shù)學建模求解算法。這類方法不能得出布局設計圖，需要設計人員根據(jù)算出的數(shù)據(jù)，構(gòu)思布局設計，然后再在圖形繪制工具中繪制布局圖。另一類是用計算機算法直接對布局圖進行優(yōu)化求解，最后得出優(yōu)化的布局設計圖，

14.1.1設施布局問題數(shù)學模型1．單行布置的模型首先要做如下假設，假設機器的形狀是方形，機器排成一列，機器的方位是預先確定的。如圖14-1所示。設有n臺機器排成一列，要確定各機器的位置坐標，使機器間運送物料的成本最低。圖14-1單行布置示意圖2．多行布置的模型圖14-2多行布置示意圖3．二次分派問題模型給定n個地點，現(xiàn)要把n個設施分配到這n個地點，這實際上是組合問題，共有n！種方案，在這n！種方案里找最佳方案使總的物料搬運費用最短。如果n等于4，則共有24種方案，顯然可以用窮舉發(fā)來求最優(yōu)方案，如果n等于10，則有3628800種方案，如果n大于10，方案會更多，顯然沒有辦法窮舉，往往通過一些啟發(fā)式算法尋找次優(yōu)方案。

14.1.2遺傳算法在布局設計中的應用1．遺傳算法的結(jié)構(gòu)遺傳算法開始時先隨機地產(chǎn)生一些染色體（欲求解問題的侯選解），計算其適應度，根據(jù)適應度對諸染色體進行選擇、交換、變異等遺傳操作，剔除適應度低的染色體，從而得到新的群體。由于新群體的成員是上一代群體的優(yōu)秀者，繼承了上一代的優(yōu)良性態(tài)，因而在總體上優(yōu)于上一代。就這樣反復迭代，向著更優(yōu)解的方向進化，直至滿足某種預定的優(yōu)化指標。(1)編碼與譯碼許多應用問題結(jié)構(gòu)很復雜，但可以化為簡單的位串形式編碼表示，我們將問題結(jié)構(gòu)變換為位串形式編碼表示的過程叫編碼；而相反將位串形式編碼表示變換為原問題結(jié)構(gòu)的過程叫譯碼。我們把位串形式編碼表示叫染色體，有時也叫個體。(2)適應度函數(shù)為了體現(xiàn)染色體的適應能力，引入了對問題中的每一個染色體都能進行度量的函數(shù)，叫適應度函數(shù)。通過適應度函數(shù)來決定染色體的優(yōu)、劣程度，它體現(xiàn)了自然進化中的優(yōu)利劣汰原則。對優(yōu)化問題，適應度函數(shù)就是目標函數(shù)。(3)遺傳操作簡單遺傳算法的遺傳操作主要有三種:選擇(selection)、交叉(crossover)、變異(mutation)。改進的遺傳算法大量擴充了遺傳操作，以達到更高的效率。選擇操作也叫復制操作，根據(jù)個體的適應度函數(shù)值所度量的優(yōu)、劣程度決定它在下一代是被淘汰還是被遺傳。一般地說，選擇將使適應度較大(優(yōu)良)個體有較大的存在機會，而適應度較小（低劣）的個體繼續(xù)存在的機會也較小。交叉操作的簡單方式是將被選擇出的兩個個體P1和P2作為父母個體，將兩者的部分碼值進行交換。圖14-3交叉前示意圖圖14-4交叉后示意圖變異操作的簡單方式是改變數(shù)碼串的某個位置上的數(shù)碼。我們先以最簡單的二進制編碼表示方式來說明.圖14-5變異示意圖(4)控制參數(shù)

并不是所有被選擇了的染色體都要進行交叉操作和變異操作，而是以一定的概率進行，交叉概率種群的染色體總數(shù)叫種群規(guī)模，另一個控制參數(shù)是個體的長度2.遺傳算法應用舉例問題的描述假設有九臺設備M1～M9，在某個生產(chǎn)階段設備之間的物流矩陣(實際上就是從至表)如圖所示?，F(xiàn)需要將這九臺進行布置，使其運輸工具的總行程最小。假設由于場地的限制，設備需要分成三行來排列，且各生產(chǎn)設備之間距離相等為單位1圖14-6設備之間的物流矩陣(2)遺傳算法的設計編碼方法：這里使用浮點數(shù)編碼方法，用設備的位置向量表示染色體適應度函數(shù)：

初始群體的產(chǎn)生：以隨機的方式將這九臺設備進行排列，共得到M種設備布局形式。選擇算子：這里使用比例選擇算子，即個體被選中并遺傳到下一代群體中的概率與該個體的適應度大小成正比。交叉算子：將群體中M個個體以隨機的方式兩兩配對，組成M/2對配對個體組。每對配對個體組隨機選擇其中之一為Parent1，則另外一個個體為Parent2。

變異算子：隨機地選取個體中兩個基因座，交換它們的基因，產(chǎn)生新個體。圖14-7交叉算子示意圖(3)運算結(jié)果在該算法中，采用保留最佳個體策略，加快了收斂速度，并且取得較優(yōu)的解。計算出最優(yōu)布局為(2，4，1，6，3，5，8，7，9)。在此布局下，目標函數(shù)值為2530，而最劣布局的目標函數(shù)值為3653。14.1.3模擬退火算法在布局設計中的應用

1．模擬退火算法流程隨機產(chǎn)生一個初始解，計算目標函數(shù)值;(2)設置初始溫度(3)當時，對應某個具體的溫度T，重復執(zhí)行步驟（4）K次。

(4)對當前最優(yōu)解按照某一鄰域函數(shù)，產(chǎn)生一新的解。計算新的目標函數(shù)值，并計算目標函數(shù)值的增量，根據(jù)增量的正負，確定最優(yōu)解。(5)步驟（4）完成k次重復后，令，若執(zhí)行步驟（6），若，回到步驟3。(6)輸出當前最優(yōu)解，計算結(jié)束。2．模擬退火算法的簡單應用考慮遺傳算法部分的例題，用模擬退火算法求解，要點如下：解空間S是所有布局方案的集合，S中的成員記為：，其中為第k臺機器所在的地點。初始解可選為(1，……，n)。此時的目標函數(shù)即為運輸工具的總行程

若k<m，則將變?yōu)椋喝绻莐>m，則將

變?yōu)椋?．模擬退火算法的參數(shù)控制問題(1)溫度T的初始值設置問題。溫度T的初始值設置是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優(yōu)解的可能性大，但因此要花費大量的計算時間；反之，則可節(jié)約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據(jù)實驗結(jié)果進行若干次調(diào)整。(2)退火速度問題。模擬退火算法的全局搜索性能也與退火速度密切相關。一般來說，同一溫度下的“充分”搜索(退火)是相當必要的，但這需要計算時間。實際應用中，要針對具體問題的性質(zhì)和特征設置合理的退火平衡條件。(3)冷卻進度表T(t)。冷卻進度表是指從某一高溫狀態(tài)To向低溫狀態(tài)冷卻時的降溫管理表。假設時刻t的溫度用T(t)來表示，則經(jīng)典模擬退火算法的降溫方式為：而快速模擬退火算法的降溫方式為：

14.2布置圖的設計算法14.2.1布置圖設計算法的分類與原理1．算法的輸人數(shù)據(jù)類型布置算法可以按照它們所需的輸人數(shù)據(jù)類型分類。有些算法只接受像相關圖之類定性的“物流”數(shù)據(jù)，而有些接受由從至表表示的定量物流數(shù)據(jù)；還有一些算法同時接受相關圖和從至表兩種數(shù)據(jù)（如BLOCPLAN），但是在評價布置方案時只能選擇這兩種數(shù)據(jù)中的一種?，F(xiàn)在的算法更趨向于采用從至表數(shù)據(jù)，2．基于“量距積的和最小”為目標的算法首先考慮基于距離的目標，設m為部門數(shù)，為從部門i到部門j的物流量；為將一個單元的物料從部門i移動到部門j單位距離的成本。于是目標函數(shù)是要使單位時間內(nèi)部門間物料的移動總成本最小化3．基于相近程度目標函數(shù)的算法考慮基于相近程度的目標函數(shù)，其中相近程度的分值是按布置中所有相鄰兩個部門物流量值的總和來計算的。如果部門i和j相鄰就令＝1，否則；＝0，目標是求相鄰值最大

但如果要評價一個特定布置在某個上下邊界的相對效率（相對優(yōu)劣）時，設施規(guī)劃人員可采用以下“歸一化”的相鄰值。如果采用“負流量”值。歸一化的相鄰值計算公式修改如下14.2.2CRAFT算法1.CRAFT算法的初始條件CRAFT是一種改進型布置算法，所以先要給它一定的基礎，如從一個已有設施的實際布置或由另一種算法給出的初始布置開始，先確定初始布置中各部門的矩心，然后計算兩兩部門距心之間直角距離，并存儲在距離矩陣之中。2.CRAFT算法的迭代過程在程序考慮部門i和j的位置交換時，不是實際交換它們的位置再來計算新的矩心和布置成本，而是臨時互換當前布置中部門i和部門j的矩心數(shù)據(jù)來估算布置成本。在按估算的布置成本找到最佳交換后，CRAFT程序再交換兩者的位置并計算它們新的矩心后才開始下一步迭代。3.迭代結(jié)果依賴于路徑在搜索更好結(jié)果時，CRAFT只是從每次迭代中選擇最好的交換方式，這是一種最速下降法。在上述的搜索過程中，它既不瞻前也不顧后。因此，CRAFT搜索時會在第一次碰到二相或三相最佳方案時就予以終結(jié)，這樣的結(jié)果很可能只是局部最優(yōu)解。4.CRAFT用于非矩形廠房的策略CRAFT一般僅限用于矩形廠房，但通過引人“虛”部門它也可以用于非矩形廠房。虛部門與其他部門沒有任何物流或相互作用，但要由布置規(guī)劃人員指定它的面積。一般來說，虛部門主要用于：①填補建筑物的不規(guī)則之處；②代表一設施內(nèi)的障礙或不能用的區(qū)域（如樓梯、電梯、廠房維護區(qū)等）；③代表廠房的額外空間；④在最終布置中用于幫助通道位置的確定。5.CRAFT布置的修改CRAFT的優(yōu)點之一是能以合理的精確度找到初始布置。這主要是因為CRAFT能在非矩形建筑物內(nèi)的任何地方容納矩形的部門或障礙。但是除了高度依賴路徑外，CRAFT的缺點是產(chǎn)生的最終布置很少有部門形狀是規(guī)則的，也少有直線形的且不中斷的通道。14.2.3CRAFT算法案