47基于遺傳算法對W公司最終布局優(yōu)化與評價(jià)案例綜述1基于遺傳算法的車間布局優(yōu)化模型構(gòu)建模型的基本要求和思想模型的基本要求數(shù)學(xué)模型是將實(shí)際問題與數(shù)學(xué)理論相結(jié)合的一門學(xué)科，主要就是用定性或者定量的方法通過字母、數(shù)字或者其他符號等建立數(shù)學(xué)表達(dá)式使抽象的問題具體化，在近年來發(fā)展迅速并得到廣泛應(yīng)用。在建立數(shù)學(xué)模型的過程中，為了方便后續(xù)模型求解以及增強(qiáng)模型的實(shí)用性常常需要對復(fù)雜的現(xiàn)實(shí)問題做一些簡化和假設(shè)，通常需要滿足以下幾點(diǎn)要求：真實(shí)完整。實(shí)際問題的完整性以及數(shù)據(jù)的真實(shí)性是保證建立合理有效數(shù)學(xué)模型的前提，以便更好的體現(xiàn)模型的應(yīng)用價(jià)值。條件充分。在建立模型時(shí)，要根據(jù)實(shí)際問題所需選取恰當(dāng)?shù)臎Q策變量來描述問題的特征，要明確實(shí)際問題所需的約束條件，以便更好的建立模型。適應(yīng)變化。隨著人們對理論知識的深入研究以及實(shí)際問題情況的相關(guān)條件的變化，可以對模型中相關(guān)變量以約束做出調(diào)整，以便更好的解決實(shí)際問題。車間布局優(yōu)化模型的思想車間作為制造型企業(yè)生產(chǎn)的基礎(chǔ)，車間布局是否合理直接影響企業(yè)產(chǎn)品生產(chǎn)周期以及生產(chǎn)成本，因此成為跨學(xué)科的研究課題以及規(guī)劃設(shè)計(jì)專員一直在探索研究以尋求更好的解決方案的問題。在本文中主要對W公司物流關(guān)系和非物流關(guān)系進(jìn)行分析，建立雙目標(biāo)目標(biāo)函數(shù)并根據(jù)企業(yè)實(shí)際情況設(shè)定約束條件，以得到車間布局最優(yōu)得方案。車間布局和常見得幾何形體布局不同，幾何形體布局一般各個(gè)幾何形體之間不存在相關(guān)性，是獨(dú)立的個(gè)體，并且要求根據(jù)其約束條件以實(shí)現(xiàn)最小化體積或者面積。相較于幾何形體布局，車間布局各個(gè)作業(yè)單元之間存在物流關(guān)系甚至存在非物流關(guān)系。因此建立車間布局優(yōu)化模型時(shí)，要根據(jù)車間的生產(chǎn)區(qū)域面積以及各個(gè)作業(yè)單元所需面積情況，建立最大化物流關(guān)系目標(biāo)函數(shù)，此外還需要考慮現(xiàn)實(shí)約束條件，如各個(gè)作業(yè)單元在車間只能出現(xiàn)一次、相鄰作業(yè)單元之間不可以出現(xiàn)重疊等等，只有這樣求解出的布局方案才能符合實(shí)際情況且具有一定的應(yīng)用價(jià)值。模型的假設(shè)由于W公司實(shí)際的生產(chǎn)車間布局較復(fù)雜，而數(shù)學(xué)模型是對實(shí)際問題的簡化描述。因此，為了更好的構(gòu)建適合車間布局的模型，增強(qiáng)模型的可靠性與實(shí)用性，本文對其所設(shè)及到的相關(guān)數(shù)據(jù)和條件列出下列假設(shè)：（1）假設(shè)W公司生產(chǎn)車間以及車間各個(gè)工作單元的形狀都為矩形，車間邊長已知，忽略它們的具體形狀細(xì)節(jié)；（2）假設(shè)W公司生產(chǎn)車間各個(gè)工作單元間物料的搬運(yùn)方向與車間的長度和寬度平行，都采用直線行駛的方式；（3）假設(shè)W公司生產(chǎn)車間各個(gè)工作單元隨機(jī)排列，且與車間的墻壁四周平行；綜合上述假設(shè)，W公司的車間布局優(yōu)化問題的數(shù)學(xué)問題可以描述為：在工作單元數(shù)目、搬運(yùn)距離、物流量已知的情況下，求解最小化物流量距積和最大化非物流關(guān)系的雙目標(biāo)函數(shù)，即根據(jù)車間現(xiàn)狀所得出得最優(yōu)布局方案。具體生產(chǎn)車間布局坐標(biāo)示意圖見圖5-1。圖5-1生產(chǎn)車間布局坐標(biāo)示意圖Figure5-1Layoutcoordinatediagramofproductionworkshop模型的目標(biāo)函數(shù)在對W公司車間布局進(jìn)行優(yōu)化研究的過程中不僅對其物料搬運(yùn)強(qiáng)度進(jìn)行減少，而且對其有相關(guān)關(guān)系作業(yè)單元之間的緊密程度進(jìn)行加強(qiáng)。因此，構(gòu)建出以最小化物流量距積和最大化非物流相關(guān)單元的雙目標(biāo)函數(shù)。首先確定物流量距積的目標(biāo)函數(shù)。假設(shè)W公司車間布局有一個(gè)布局規(guī)劃方案，和是其中的作業(yè)單元，則用表示作業(yè)單元和作業(yè)單元之間的距離，表示作業(yè)單元和作業(yè)單元之間的物料搬運(yùn)量，其中。故作業(yè)單元間的距離矩陣和物料搬運(yùn)量矩陣為：（5-1）（5-2）由距離矩陣和物料搬運(yùn)量得到最小化物料搬運(yùn)強(qiáng)度的目標(biāo)函數(shù)：（5-3）在公式5-3中，表示物流量量距積。然后確定非物流關(guān)系的目標(biāo)函數(shù)，通過各個(gè)作業(yè)單元之間的密切關(guān)系等級來表示其遠(yuǎn)近程度。故得到最大化非物流相關(guān)作業(yè)單元之間關(guān)系的目標(biāo)函數(shù)：（5-4）在公式5-4中，表示非物流相關(guān)作業(yè)單元關(guān)系的總和，表示作業(yè)單元和作業(yè)單元之間的密切程度與距離產(chǎn)生的關(guān)聯(lián)因子，表示作業(yè)單位在非物流關(guān)系影響下的相互之間的密切等級。和的取值分別見表5-1和表5-2[41]，其中的取值由作業(yè)單元和作業(yè)單元之間的距離所決定的，其界定值采用的定義，分成六個(gè)子區(qū)域，根據(jù)所處的子區(qū)間判斷各相關(guān)作業(yè)單元間的鄰接度[42]。表5-1非物流強(qiáng)度等級量化表Table5-1Quantitativetableofnon-logisticsintensitylevel密切關(guān)系等級意義A絕對重要4E非常重要3I重要2O一般1U不重要0X需要遠(yuǎn)離-1表5-2關(guān)聯(lián)因子量化值表Table5-2Quantitativevaluesofcorrelationfactors作業(yè)單元距離關(guān)聯(lián)度取值10.80.60.40.20其中，為W公司生產(chǎn)車間規(guī)劃區(qū)域的長度和寬度的總和[41]。綜上以上對物流關(guān)系和非物流關(guān)系的分析，構(gòu)建出以最小化物流量距積和最大化非物流相關(guān)單元的雙目標(biāo)函數(shù)，且物料搬運(yùn)距離的計(jì)算公式為物料在工作單元中心點(diǎn)的起始位置坐標(biāo)與終止位置坐標(biāo)的差值，即：（5-5）在公式5-5中，是物料搬運(yùn)的距離，`是工作單元中心點(diǎn)的起始位置坐標(biāo)，是工作單元中心點(diǎn)的終止位置坐標(biāo)。各個(gè)表達(dá)式符合和具體代表的含義見表5-3。表5-3各公式符號及其含義Table5-3Formulasymbolsandtheirmeanings符號含義作業(yè)單元序號總物料搬運(yùn)強(qiáng)度非物流相關(guān)作業(yè)單元之間關(guān)系之和作業(yè)單元和作業(yè)單元之間的物料搬運(yùn)距離工作單元中心點(diǎn)的起始位置坐標(biāo)工作單元中心點(diǎn)的終止位置坐標(biāo)作業(yè)單元和作業(yè)單元之間的物料搬運(yùn)量作業(yè)單元和作業(yè)單元之間的密切程度與距離產(chǎn)生的關(guān)聯(lián)因子作業(yè)單位在非物流關(guān)系影響下的相互之間的密切等級為了求解方便，將雙目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù)后得到下面目標(biāo)函數(shù)表達(dá)式：（5-6）（5-7）（5-8）（5-9）通過查閱相關(guān)資料數(shù)據(jù)以及企業(yè)自身生產(chǎn)規(guī)模狀況，決定將物流量距積和非物流相關(guān)強(qiáng)度的權(quán)重設(shè)定為1：1，即。此外，考慮到和之間存在量綱的差異，因此對二者進(jìn)行標(biāo)準(zhǔn)化處理：（5-10）（5-11）故最終目標(biāo)函數(shù)表達(dá)式為：（5-12）結(jié)合W公司實(shí)際情況后為了實(shí)現(xiàn)目標(biāo)函數(shù)表達(dá)式（5-12），目標(biāo)函數(shù)需滿足以下約束條件：（1）每一個(gè)作業(yè)單位在車間布局中只能出現(xiàn)一次，而且只能布置在某一行中，即（5-13）每一個(gè)作業(yè)單元之間留有一定的間隙，確保相鄰作業(yè)單元不會出現(xiàn)重疊的情況，即：（5-14）（5-15）每一行或者列上的作業(yè)單元在X軸或者Y軸方向上的長度或者寬度總和必須小于生產(chǎn)車間的總長度或總寬度，即：（5-16）（5-17）在上述約束條件中，和分別表示W(wǎng)公司車間的長度和寬度，和分別表示作業(yè)單元和的長度，同樣和分別表示作業(yè)單元和的寬度，和分別表示作業(yè)單元和在X軸的距離和Y軸的距離。2基于遺傳算法的模型求解過程2.1編碼機(jī)制對于車間布局問題主要是確定各個(gè)作業(yè)單元的相對位置進(jìn)而得到布局規(guī)劃方案，因此在選擇算法編碼機(jī)制時(shí)只需要選擇表示相對位置的符號即可，無需涉及到數(shù)值運(yùn)算。針對車間布局問題的這一特征，本模型采用符號編碼機(jī)制，即選用自然數(shù)來表示各個(gè)作業(yè)單元及其相對位置關(guān)系。2.2初始種群在使用遺傳算法對研究對象進(jìn)行求解時(shí)，為了在優(yōu)化過程中較快找到最優(yōu)解，還需要產(chǎn)生一組個(gè)體組成初始種群來做為遺傳算法的初始解。傳統(tǒng)遺傳算法大都采用隨機(jī)方式來產(chǎn)生初始化種群，雖然該方式簡單易操作，但對于算法后續(xù)的運(yùn)行速率以及種群選取的合理性進(jìn)行保證。為了增強(qiáng)遺傳算法的運(yùn)行速率和準(zhǔn)確性，專家學(xué)者在后續(xù)的研究中提出可以根據(jù)研究對象的實(shí)際情況構(gòu)造或者從其他算法中選取較優(yōu)的染色體作為初始種群。因此，本模型采用SLP方法初始布局方案和隨機(jī)方案相結(jié)合作為初始種群。2.3適應(yīng)度函數(shù)遺傳算法在求解過程中根據(jù)適者生存原則選擇下一代的個(gè)體，對外部信息的依賴度不高，主要通過對目標(biāo)函數(shù)進(jìn)行變形后得到適應(yīng)度函數(shù)，進(jìn)而對初始化種群中的個(gè)體好壞程度進(jìn)行評判，選擇出適應(yīng)度較高的個(gè)體使其更多的繁殖下一代，依次循環(huán)，最終留下最好的個(gè)體。大多數(shù)情況下采用表示目標(biāo)函數(shù)，表示適應(yīng)度函數(shù)的表達(dá)方式，根據(jù)對適應(yīng)度函數(shù)的分析以及本模型所研究的是物流量距積最小的目標(biāo)函數(shù)，采用取倒數(shù)法來確定適應(yīng)度函數(shù)，即：（5-18）其中，2.4遺傳算子遺傳算子在操作過程中，主要涉及到選擇、交叉、變異和終止四個(gè)步驟。選擇在運(yùn)用遺傳算法進(jìn)行求解的過程中所涉及到的選擇操作，最常用的是輪盤賭方法。本次遺傳算法運(yùn)用輪盤賭的方法對初始種群個(gè)體進(jìn)行選擇操作，首先對每一個(gè)個(gè)體的適應(yīng)性值進(jìn)行計(jì)算并全部進(jìn)行求和，然后計(jì)算出每一個(gè)個(gè)體適應(yīng)性值在總體適應(yīng)性值中的所占的比例大小，最后運(yùn)用輪盤賭方法對種群中的個(gè)體進(jìn)行選擇，個(gè)體被保留遺傳給后代的概率為：（5-19）其中，為種群規(guī)模，為個(gè)體所計(jì)算出的適應(yīng)性值。（2）交叉交叉操作是增加樣本種群中個(gè)體數(shù)量的主要方法。遺傳算法中的交叉是指按照一定的規(guī)則，對種群中的兩個(gè)相互配對的個(gè)體中的單個(gè)基因、多個(gè)基因或者部分基因進(jìn)行交叉運(yùn)算，進(jìn)而產(chǎn)生兩個(gè)新的種群個(gè)體。在進(jìn)行交叉操作之前，首先需要采用隨機(jī)配對法對初始種群中的所有個(gè)體進(jìn)行兩兩配對，然后根據(jù)研究對象的實(shí)際情況進(jìn)行分析，在保證不對個(gè)體的良好基因進(jìn)行過多破壞的同時(shí)有較多的個(gè)體產(chǎn)生。根據(jù)本次研究對象的情況的交叉操作運(yùn)用部分匹配交叉的方法。（3）變異變異操作是增加樣本種群中個(gè)體數(shù)量的輔助方法。遺傳算法中的變異是指種群中的個(gè)體在遺傳運(yùn)算的過程中，通過對單條染色體基因的改變進(jìn)而產(chǎn)生新得種群個(gè)體，其對遺傳算法的局部搜索能力有較大影響。通過交叉和變異操作的結(jié)合，增強(qiáng)了遺傳算法的搜索能力，可以使得尋找最優(yōu)解的過程變得高效。常見的變異算子設(shè)計(jì)方法有基本位變異、逆轉(zhuǎn)變異和交換變異三種。（4）終止遺傳算法通過對種群規(guī)模最大迭代次數(shù)進(jìn)行限定來終止算法的運(yùn)行，并根據(jù)實(shí)際所需將編碼進(jìn)行解碼得到最終結(jié)果。為了防止算法過早終止而得不到最優(yōu)解，本次將遺傳算法迭代次數(shù)設(shè)置為1500次。綜合上述分析，遺傳算法的整個(gè)運(yùn)算求解過程見圖5-2。圖5-2遺傳算法求解步驟Figure5-2Geneticalgorithmsolvingstep3模型應(yīng)用與結(jié)果評價(jià)3.1模型應(yīng)用W公司整個(gè)生產(chǎn)車間長為60米，寬約45米，占地面積約2700平方米，是單層生產(chǎn)結(jié)構(gòu)，可分為18個(gè)作業(yè)單元，各個(gè)作業(yè)單元所需面積及長寬參數(shù)見表5-4。表5-4車間作業(yè)單元面積及長寬參數(shù)Table5-4Workshopareaandlengthandwidthparameters作業(yè)單元序號作業(yè)單元名稱需求面積/平方米長/米寬/米1原料庫1261872研發(fā)室24643來料待檢區(qū)24644投料區(qū)32485燒錄區(qū)136946燒錄區(qū)236947組裝區(qū)40858入庫待檢區(qū)40859測試區(qū)328410老化區(qū)7212611包裝區(qū)16416412包裝區(qū)2549613入庫暫存區(qū)4041014半成品庫143131115成品庫200102016維修區(qū)12030417辦公室17.553.518消防重點(diǎn)區(qū)45153各個(gè)作業(yè)單元之間的物流量矩陣和作業(yè)單位在非物流關(guān)系影響下相互之間的密切等級關(guān)系矩陣分別見（5-20）和（5-21)：(5-20)（5-21）作業(yè)單元和作業(yè)單元之間的密切程度與距離產(chǎn)生的關(guān)聯(lián)因子采用Lee的定義[42]，由作業(yè)單位之間的距離與生產(chǎn)車間規(guī)劃區(qū)域的長寬之和的比值劃分為六個(gè)子區(qū)域，每一個(gè)區(qū)域有一個(gè)對應(yīng)的關(guān)聯(lián)因子，根據(jù)W公司實(shí)際情況可得，具體關(guān)聯(lián)因子量化表見表5-5。表5-5關(guān)聯(lián)因子量化表Table5-5Correlationfactorquantizationtable作業(yè)單元間距離10.80.60.40.20為了防止遺傳算法在求解過程中過早收斂的情況發(fā)生，相關(guān)參數(shù)設(shè)定如下：初始種群大小,最大迭代次數(shù)，交叉概率，變異概率。運(yùn)用MATLAB編寫遺傳算法程序，相關(guān)參數(shù)均按照上述數(shù)據(jù)設(shè)定后對模型進(jìn)行求解，運(yùn)算過程見圖5-3。圖5-3遺傳算法迭代曲線Figure5-3Geneticalgorithmiterationcurve從圖5-3可以看出，遺傳算法迭代運(yùn)行次數(shù)到1300次左右時(shí)接近收斂，可以認(rèn)為此時(shí)求解出的布局方案為最優(yōu)解，作業(yè)單元之間的相對位置即車間最優(yōu)規(guī)劃布局見圖5-4。圖5-4最終車間布局規(guī)劃圖Figure5-4Finalworkshoplayoutplan3.2結(jié)果評價(jià)為了驗(yàn)證最終車間布局規(guī)劃方案的有效性，采用定量與定性相結(jié)合的方法進(jìn)行分析評價(jià)。首先是定量分析，根據(jù)W公司實(shí)際情況車間布局現(xiàn)狀、SLP方法初始布局方案以及遺傳算法最終車間布局的相關(guān)作業(yè)單元的物料搬運(yùn)距離見表5-6。表5-6優(yōu)化前后車間布局物流量距積Table5-6Logisticsvolumeproductofworkshoplayoutbeforeandafteroptimization序號相關(guān)作業(yè)單元現(xiàn)有車間布局物流量距積（Kg·m）SLP方法車間布局物流量距積（Kg·m）遺傳算法車間布局物流量距積（Kg·m）11-2749.291249.351402.8121-3504.871094.63183.3331-42057.193882.493577.9342-51015.002092.94591.5352-8600.96500.06335.7962-1697.64267.31368.5172-1739.8795.62136.1483-51961.703996.20761.9793-147135.545541.156248.39103-18384.24423.03115.23114-52156.491724.351011.47124-71918.721920.561312.75135-61094.801164.721369.13145-71097.822552.851703.89156-72223.262886.013541.08166-141042.371069.981442.79177-88638.757755.75296.82187-143003.003119.582430.34198-98030.308104.352196.28208-10439.43128.915497.93219-113411.803760.95226.87229-14657.941068.281445.04239-16160.69139.85745.902410-11284.32222.9163.252510-161625.481081.651476.732611-1