欒方軍 王 帥 崔洪斌

(沈陽建筑大學(xué)信息與控制工程學(xué)院 遼寧 沈陽 110168)

0 引 言

近年來我國建筑業(yè)持續(xù)快速發(fā)展，隨著建筑規(guī)模的不斷擴(kuò)大，傳統(tǒng)的建筑方式出現(xiàn)了勞動力缺乏、成本變高、資源緊缺等問題。為了應(yīng)對上述問題和亟待加快建筑工業(yè)化[1]的進(jìn)程，裝配式建筑[2-3]方式得到了迅猛發(fā)展。這種建筑方式需要用到大量的預(yù)制混凝土構(gòu)件，即PC構(gòu)件(Prefabricated Concrete Component)，因此現(xiàn)階段對于裝配式建筑生產(chǎn)企業(yè)，如何高標(biāo)準(zhǔn)、高效率和高質(zhì)量地生產(chǎn)出PC構(gòu)件成為預(yù)制構(gòu)件生產(chǎn)企業(yè)研究的重要問題。

在預(yù)制構(gòu)件的生產(chǎn)過程中，當(dāng)投產(chǎn)預(yù)制構(gòu)件上線時，通過選擇不同的構(gòu)件組合分配到模臺上進(jìn)行加工，而每個預(yù)制構(gòu)件通過固定在模臺上的模具進(jìn)行生產(chǎn)，模臺作為轉(zhuǎn)運工具承載著模具完成預(yù)制構(gòu)件生產(chǎn)的全過程。每個模臺尺寸完全相同，而模具尺寸有差異，為更充分地利用模臺的臺面空間，需要盡可能多地擺放模具。如果不能合理地依據(jù)模具尺寸將模具分配到模臺上，會導(dǎo)致模臺的臺面得不到充分利用，完成生產(chǎn)同樣數(shù)量的預(yù)制構(gòu)件需要使用更多的模臺，導(dǎo)致模臺的利用率低，這嚴(yán)重地制約了企業(yè)產(chǎn)能的發(fā)揮。因此，研究建筑預(yù)制構(gòu)件生產(chǎn)線上模具在模臺上的組合分配問題，探索提高模臺利用率的方法，對企業(yè)發(fā)揮現(xiàn)有產(chǎn)能和降低生產(chǎn)成本具有重要的意義。

近年來，由于預(yù)制構(gòu)件生產(chǎn)線與傳統(tǒng)制造企業(yè)生產(chǎn)線相比有著獨特的工藝要求和生產(chǎn)運作規(guī)律，因此越來越多的學(xué)者開始重視對預(yù)制構(gòu)件生產(chǎn)相關(guān)問題的研究。王中原等[4]對混凝土預(yù)制構(gòu)件生產(chǎn)過程中模具的排布問題進(jìn)行了研究，采用遺傳算法對預(yù)制構(gòu)件生產(chǎn)中模具在模臺上的排布方案進(jìn)行優(yōu)化。張立新[5]對小型預(yù)制構(gòu)件的施工工藝、方法，以及質(zhì)量保證措施進(jìn)行了研究探討，闡述了其存在的問題及應(yīng)采取的解決措施。劉猛等[6]為了縮短構(gòu)件在生產(chǎn)線上的機(jī)器空閑時間和等待時間，運用混合整數(shù)線性規(guī)劃算法，建立了預(yù)制混凝土構(gòu)件生產(chǎn)調(diào)度優(yōu)化模型，以此來提高預(yù)制構(gòu)件生產(chǎn)車間的生產(chǎn)效率。謝思聰?shù)萚7]提出了一種基于多層編碼的遺傳算法對兩階段裝配式建筑預(yù)制構(gòu)件生產(chǎn)調(diào)度進(jìn)行優(yōu)化，在分析預(yù)制構(gòu)件生產(chǎn)工藝的基礎(chǔ)上提出預(yù)制構(gòu)件廠生產(chǎn)參數(shù)的量化途徑，提高預(yù)制構(gòu)件生產(chǎn)效率。Zhai等[8]提出了基于仿真和遺傳算法的PC生產(chǎn)規(guī)劃模型，并通過3種仿真測試方法驗證了其有效性。通過對近年來相關(guān)研究文獻(xiàn)的分析表明，當(dāng)前學(xué)者們主要側(cè)重對預(yù)制構(gòu)件生產(chǎn)管控和工藝流程的角度進(jìn)行研究，對建筑預(yù)制構(gòu)件生產(chǎn)線支模工序段中模具在模臺上的組合分配問題研究較少。

模臺作為轉(zhuǎn)運工具承載著模具完成預(yù)制構(gòu)件生產(chǎn)的全過程，模具依據(jù)預(yù)制構(gòu)件的上線順序依次被擺放到模臺上，與此同時，模具的擺放過程還受到其尺寸、擺放位置和擺放方向的影響，采取不同的模具在模臺上擺放的方法也會對擺放結(jié)果產(chǎn)生影響，因此，會產(chǎn)生多種模具在模臺上組合分配的結(jié)果。模具在模臺上的擺放規(guī)則采用改進(jìn)的BL定位算法。根據(jù)某預(yù)制構(gòu)件生產(chǎn)企業(yè)實際生產(chǎn)過程可知，對于預(yù)制構(gòu)件這類大體積和大質(zhì)量的在制品，標(biāo)準(zhǔn)模臺上最多只能放下3個模具。將模臺表面看作一個二維平面，改進(jìn)的BL定位算法為首先通過被擺放在模臺上的第一個模具的擺放方向來依次確定該模臺上后續(xù)分配模具的擺放情況；然后按上線順序分配到模臺上的模具與模臺上已擺放的模具不發(fā)生重疊交叉的條件下，將模具在模臺表面盡可能地往下往左移動擺放，直到受到其他模具或者模臺邊界的阻礙不能再移動為止。

采用改進(jìn)的BL定位算法后，給定構(gòu)件的模具擺放在模臺上的位置即被唯一確定，即模具在模臺上的組合分配問題就可以轉(zhuǎn)換為確定加工預(yù)制構(gòu)件的順序，不同的預(yù)制構(gòu)件上線順序可以產(chǎn)生不同的組合分配結(jié)果。由于預(yù)制構(gòu)件生產(chǎn)企業(yè)日投產(chǎn)上線的預(yù)制構(gòu)件數(shù)量較大，故產(chǎn)生的排列組合結(jié)果非常復(fù)雜，因此需要采用啟發(fā)式算法或智能優(yōu)化算法[9]來進(jìn)行求解。類電磁機(jī)制算法[10-12](Electromagnetism-like Mechanism, EM)作為一種較新的元啟發(fā)式算法，模擬了帶電粒子在電磁場中的吸引或排斥原理，通過該原理使得粒子朝著最優(yōu)粒子移動，其獨特的優(yōu)化機(jī)制與其他群體智能算法相比，具有處理復(fù)雜問題的能力和更強(qiáng)大的搜索能力，因此該算法更適用于作為全局優(yōu)化算法優(yōu)化數(shù)量龐大的預(yù)制構(gòu)件的上線順序。但由于標(biāo)準(zhǔn)EM算法的局部搜索采用隨機(jī)線性搜索的方式，易陷入局部極值，故本文為了避免算法在迭代過程中陷入局部極值，在標(biāo)準(zhǔn)EM算法中加入了模擬退火算法[13-14]思想，以一定的概率接受目標(biāo)適應(yīng)度更差的解，進(jìn)而擴(kuò)大算法的搜索范圍。通過改進(jìn)的類電磁算法與改進(jìn)的BL定位算法相結(jié)合的方法，來解決模具分配到模臺上的組合分配問題，從而獲取能夠更有效利用模臺面積的模具組合分配結(jié)果，實現(xiàn)提高模臺利用率，減少模臺使用數(shù)量的目標(biāo)。

1 模具在模臺上的組合分配數(shù)學(xué)規(guī)劃模型

1.1 模型參數(shù)

m表示模臺使用個數(shù)；W表示模臺的長度；H表示模臺的寬度；n為待生產(chǎn)加工的預(yù)制構(gòu)件數(shù)量；Mi表示第i個模具，i∈{1,2,…,n}；Z表示n個構(gòu)件實際需要放的模臺數(shù)量；Bj表示第j個模臺，j∈{1,2,…,m}；wi表示第i個模具的長度，i∈{1,2,…,n}；hi表示第i個模具的寬度，i∈{1,2,…,n}；f表示模臺的利用率；C表示模臺邊緣和模具、模具和模具之間的工藝間距,依據(jù)某預(yù)制構(gòu)件生產(chǎn)企業(yè)的生產(chǎn)工藝規(guī)范的要求，模具和模臺邊緣、模具之間的間距是一致的；ri為模具擺放方向，i∈{0,1}，ri=0，表示橫向擺放，ri=1，表示縱向擺放；Si表示第i個模具M(jìn)i的面積，i∈{1,2,…,n}；xi1,i2表示模具M(jìn)i擺放在模臺Bj上時定位點pi1,i2的橫坐標(biāo)；yi1,i2表示模具M(jìn)i擺放在模臺Bj上時定位點pi1,i2的縱坐標(biāo)。

1.2 模具在模臺上的組合分配問題描述

預(yù)制構(gòu)件的生產(chǎn)車間是半自動化流水車間，主要生產(chǎn)的預(yù)制構(gòu)件類型為疊合板，其工藝流程[15]主要包括清理作業(yè)、噴油作業(yè)、邊模安裝、鋼筋安裝、預(yù)埋件安裝、澆筑振搗、靜停、拉毛作業(yè)、碼垛作業(yè)、蒸養(yǎng)作業(yè)、拆模、吊裝和成品，其中清理作業(yè)、噴油作業(yè)和邊模安裝三個工序在支模工序段執(zhí)行。預(yù)制構(gòu)件需要通過一個固定尺寸的模臺來承載對應(yīng)的模具以完成全部工序，該模臺在流水線上順序移動，如圖1所示。

圖1 板類預(yù)制構(gòu)件生產(chǎn)工藝圖

經(jīng)過分析得出模具在模臺上的組合分配問題可以看作是一類典型矩形排樣問題，是指在給定的矩形模臺上擺放生產(chǎn)所需的模具，即將n個待生產(chǎn)加工的預(yù)制構(gòu)件對應(yīng)的模具{M1,M2,…,Mn}擺放在模臺{B1,B2,…,Bm}上，使得所使用的總模臺個數(shù)最少，模臺利用率最高。該問題可描述為設(shè)有m個規(guī)格尺寸完全相同的模臺，模臺的長為W，寬為H，一次投產(chǎn)任務(wù)要求生產(chǎn)n個不同尺寸的預(yù)制構(gòu)件，每個預(yù)制構(gòu)件有相對應(yīng)的模具，通過調(diào)整模具對應(yīng)預(yù)制構(gòu)件的上線順序，并且依據(jù)一定的方式來控制模具在模臺上的擺放位置和方向，從而得出一組模具在模臺上的最優(yōu)排列擺放組合，提高模臺的利用率。例如，模具在模臺上的擺放位置和方向如圖2所示。

圖2 模具在模臺上的組合方式

將實際模臺平面模擬為二維坐標(biāo)的矩形平面，將x軸的一段距離設(shè)定為固定長度W,表示模臺的長度，y軸的一段距離設(shè)定為固定的長度H,表示模臺的寬度，設(shè)二維坐標(biāo)圖像的左下角坐標(biāo)為原點(0,0)，則圖像的左上角坐標(biāo)為(0，H)，右下角坐標(biāo)為(W,0)，右上角坐標(biāo)為(W,H)。待擺放的矩形模具M(jìn)i的尺寸參數(shù)已知，為滿足生產(chǎn)工藝要求，即保證模具和模具、模具和模臺之間至少保留一定的工藝間隔C，模具在模臺上固定所需預(yù)留的固定螺栓空洞尺寸忽略不計，模具在模臺上的擺放以模具的左上角為定位點。模具pi在模臺上的左上角坐標(biāo)為(xi1,yi1)，左下角坐標(biāo)為(xi1,yi1-hi)，右下角坐標(biāo)為(xi1+wi,yi1-hi)，若模具需要旋轉(zhuǎn)90°擺放，則在計算矩形模具頂點時的長度和寬度互換，即模具左上角的坐標(biāo)為(xi1,yi1+wi)，則其右下角的坐標(biāo)(xi2,yi2)=(xi1+hi,yi1-wi)。如圖3所示。

圖3 模具在模臺上的擺放模型圖

用變量ri表示模具的擺放方向，則按式(1)計算右下角的坐標(biāo)。

(1)

因此，利用所排模具左上角坐標(biāo)(xi1,yi1)、右下角坐標(biāo)(xi2,yi2)、長度wi、寬度hi，以及是否旋轉(zhuǎn)變量ri，即可確定模具M(jìn)i在模臺Bj的擺放位置和方向。

1.3 模具在模臺臺面上組合分配的約束條件

模具在模臺上組合分配問題需要滿足以下四個約束條件：

① 放置在同一模臺上的兩個模具之間互不重疊。

(2)

② 預(yù)制構(gòu)件的模具全部位于模臺的內(nèi)部。

(3)

③ 在同一模臺上布置的所有模具面積總和小于單個模臺的面積。

(4)

④ 使用的模臺面積總和大于等于所有擺放模具的面積總和。

(5)

除了上述的約束條件，還需要滿足模具在模臺上正交擺放、不可出現(xiàn)傾斜擺放等。

1.4 模具在模臺上擺放的優(yōu)化目標(biāo)

在模具模臺組合分配的過程中，優(yōu)化目標(biāo)為模臺的利用率，即指所有排列的模具面積之和與已使用的模臺面積之和的比值(用f表示)：

(6)

從優(yōu)化目標(biāo)顯示，生產(chǎn)構(gòu)件數(shù)量n確定，則所需模具的總面積也確定，由于模臺的尺寸大小是固定的，則求解模臺利用率問題轉(zhuǎn)換為求解所用模臺數(shù)量問題，當(dāng)使用模臺數(shù)量m最小時可以使模臺利用率f最大。

2 模具在模臺上的擺放方法

模具在模臺上的擺放過程中，預(yù)制構(gòu)件對應(yīng)的模具被分配到模臺上，模具在模臺上的擺放方式有多種，不同的擺放方式對于模臺利用率都有著不同的影響。模具在模臺上的這種擺放方式可以看作是一類矩形排樣問題(Nesting Problems)[16-17]，排樣問題又被稱為下料問題，其目標(biāo)是在材料切割過程中尋求一個較高的材料利用率。目前解決此問題的方法主要有BL定位算法、低水平線法[18]和分層排布法等。綜合考慮所研究問題的特殊性，即預(yù)制構(gòu)件具有立數(shù)大、面積大等特點，低水平線法和分層排布法等不符合預(yù)制構(gòu)件的生產(chǎn)加工特點。BL定位算法在處理大型預(yù)制構(gòu)件方面具有更大的優(yōu)勢，故本文采用了BL定位算法。

2.1 BL定位算法

BL定位算法[19-20]的基本原理是在板材內(nèi)部與其他已排樣零件不發(fā)生干涉的情況下，將零件盡可能地往下往左移動，直到受到其他零件或板材邊界的阻礙不能再移動為止，如圖4所示。

圖4 BL定位算法原理圖

2.2 基于改進(jìn)BL定位算法的模具在模臺上的擺放方法

由于預(yù)制構(gòu)件屬于大體積在制品，根據(jù)工藝要求，應(yīng)充分發(fā)揮模臺利用率，在實際的生產(chǎn)企業(yè)中，預(yù)制構(gòu)件生產(chǎn)企業(yè)模臺上一般最多放3個模具。經(jīng)典的BL定位算法在實行的過程中，不滿足實際的生產(chǎn)要求，如圖4(c)所示，按BL定位算法不能再擺放模具，但是在模具的上方還有機(jī)會擺放適合尺寸的模具，因此需要對BL定位算法進(jìn)行改進(jìn)。

2.2.1改進(jìn)BL定位算法

改進(jìn)的規(guī)則是根據(jù)模臺上擺放的第一個模具的擺放方向來判斷后續(xù)模具的擺放順序和位置。具體的擺放方法如下。

首先判斷擺放在模臺上第一個模具的擺放方向，其不同的擺放結(jié)果決定之后模具的擺放順序和位置。如果第一個模具橫向擺放：

(1) 第二個待擺放模具選擇放置的位置首先是第一個擺放模具的右側(cè)，若右側(cè)區(qū)域不滿足擺放條件，則選擇第一個模具的上側(cè)進(jìn)行擺放，如果上側(cè)區(qū)域不滿足擺放條件，則選擇下一個模臺進(jìn)行擺放。

(2) 若第二個模具滿足擺放在第一個模具的右側(cè)的條件，則第三個模具選擇放置的位置是第一個模具的上側(cè)，如果上側(cè)區(qū)域不滿足擺放條件，則選擇下一個模臺進(jìn)行擺放，如圖5(a)所示。

如果第一個模具縱向擺放：

(1) 第二個待擺放模具選擇擺放的位置首先是第一個擺放模具的右側(cè)，如果右側(cè)區(qū)域不滿足擺放條件，則選擇下一個模臺進(jìn)行擺放。

(2) 如果第二個模具滿足擺放在第一個模具的右側(cè)的條件，第三個模具選擇放置的位置是第二個擺放模具的上側(cè)，如果不滿足擺放條件，則選擇下一個模臺進(jìn)行擺放，如圖5(b)所示。

圖5 模具在模臺上的擺放方向和順序

2.2.2算法步驟

Step1判斷模具M(jìn)i(i=1,2,…,n)在模臺Bj(j=1,2,…,m)上的擺放角度(ri=0 表示模具橫向擺放；ri=1表示模具縱向擺放)。ri=0,計算x0=xi1+wi,y0=yi1,i=i+1,跳轉(zhuǎn)Step2；ri=1，將wi和hi值進(jìn)行交換，計算x0=xi1+hi,y0=yi1-wi,i=i+1,跳轉(zhuǎn)Step4。

Step2將模具M(jìn)i(i=2,3,…,n)擺放在所在模臺上模具的右側(cè)位置。如果滿足wi≤W-w0和hi≤H，更新x0、y0，i=i+1，則跳轉(zhuǎn)Step6；如果不滿足wi≤W-w0和hi≤H，則跳轉(zhuǎn)Step3。

Step3將Mi(i=2,3,…,n)擺放在所在模臺上第一個擺放模具的上側(cè)位置。如果滿足wi≤W和hi≤H-y0，i=i+1,j=j+1，則跳轉(zhuǎn)Step1；如果不滿足wi≤W和hi≤H-y0，j=j+1，如果j=Z，則結(jié)束循環(huán)，否則跳轉(zhuǎn)Step1。

Step4將模具M(jìn)i(i=2,3,…,n)擺放在所在模臺上第一個擺放模具的右側(cè)位置。如果模具滿足wi≤W-w0和hi≤H，更新x0，y0，i=i+1，則跳轉(zhuǎn)Step5；如果不滿足wi≤W-w0和hi≤H，j=j+1，如果j=Z，則結(jié)束循環(huán)，否則跳轉(zhuǎn)Step1。

Step5將模具M(jìn)i(i=2,3,…,n)擺放在所在模臺上第一個擺放模具的右上側(cè)位置。如果滿足wi≤W-w0和hi≤H-y0，i=i+1,j=j+1，則跳轉(zhuǎn)Step1；如果模具不滿足wi≤W-w0和hi≤H-y0，j=j+1，如果j=Z，則結(jié)束循環(huán)，否則跳轉(zhuǎn)Step1。

Step6將模具M(jìn)i(i=2,3,…,n)擺放在所在模臺上第一個擺放模具的上側(cè)位置。如果滿足wi≤W和hi≤H-y0，i=i+1,j=j+1，則跳轉(zhuǎn)Step1；如果不滿足wi≤W和hi≤H-y0，j=j+1，如果j=Z，則結(jié)束循環(huán)，否則跳轉(zhuǎn)Step1。

3 全局優(yōu)化算法

投產(chǎn)預(yù)制構(gòu)件對應(yīng)使用的模具在模臺上組合分配的過程中，對于一個確定的預(yù)制構(gòu)件上線順序，依次將預(yù)制構(gòu)件對應(yīng)的模具分配到模臺上時，受到模具尺寸、模具擺放的位置和方向的影響，會產(chǎn)生多組分配結(jié)果。當(dāng)預(yù)制構(gòu)件的上線順序改變時，依次選取的預(yù)制構(gòu)件所對應(yīng)使用的模具進(jìn)行分配又會產(chǎn)生更多組合分配結(jié)果。因此，多個模具在多個模臺上進(jìn)行組合分配會出現(xiàn)“組合爆炸”[21]的情況。為能夠高效地求解這類具有高復(fù)雜性的問題，在確定模臺擺放方法后，需要一種能夠快速尋優(yōu)的算法對預(yù)制構(gòu)件的上線順序進(jìn)行優(yōu)化。相比其他的優(yōu)化算法，類電磁機(jī)制算法是一種智能優(yōu)化算法，具有強(qiáng)大的搜索能力和魯棒性等優(yōu)點，因此選用類電磁機(jī)制算法來優(yōu)化預(yù)制構(gòu)件的上線順序。

3.1 類電磁機(jī)制算法

EM算法作為一種全局優(yōu)化算法，是一種基于種群的隨機(jī)的啟發(fā)式算法。這種算法的原理雖然與真正的電磁場有所區(qū)別，但卻是模擬電磁場中帶電粒子之間的吸引與排斥機(jī)制，故稱這種優(yōu)化機(jī)制為類電磁機(jī)制。EM算法的基本思想是將可行域中的所有解看作多個帶電粒子，而所有解的目標(biāo)函數(shù)值是由每個帶電粒子的電荷量所決定的。同時電荷量的大小決定著每個帶電粒子對群體中的其他帶電粒子吸引或排斥作用的強(qiáng)弱，電荷量越大，目標(biāo)函數(shù)值越優(yōu)，其吸引或排斥力也就越大。其后粒子之間的吸引力或排斥力決定著每個帶電粒子下一步的移動方向，結(jié)果導(dǎo)致種群中每個粒子都向著最優(yōu)解粒子所在的區(qū)域移動，最終得到全局優(yōu)化的最優(yōu)解。

3.2 EM算法步驟

EM算法劃分為四個步驟，分別為初始種群的建立、局部搜索、合力計算和粒子移動。

3.2.1初始種群的建立

3.2.2局部搜索

EM算法根據(jù)局部搜索因子δ和局部搜索迭代最大次數(shù)L，計算可行域中所有粒子在每一維移動的最大步長同時進(jìn)行局部搜索，其搜索結(jié)束條件為局部搜索迭代次數(shù)等于L或找到一個目標(biāo)函數(shù)值更優(yōu)的點。每個粒子在其所在的可行域中完成局部搜索后會產(chǎn)生一些新的粒子，新生成的粒子會重新組成一個較優(yōu)的種群，計算這個新種群每一個粒子的目標(biāo)函數(shù)值，經(jīng)過多重比較，最優(yōu)目標(biāo)函數(shù)值的粒子仍記為xbest。

3.2.3計算合力

粒子之間受力的疊加原理為粒子與粒子之間所受電磁力的大小與粒子之間距離的平方成反比，與粒子所攜帶的電荷量成正比。通過上述的疊加原理，可以計算所有粒子自身的電荷量與粒子之間所受到的合力。粒子xi在電場中所帶電荷量qi的大小決定著吸引力或排斥力的大小和目標(biāo)函數(shù)值的大小，qi計算如下:

(7)

由式(7)可知，EM算法中攜帶電荷量較大(目標(biāo)函數(shù)值較優(yōu))的粒子相對于電荷量較小(目標(biāo)函數(shù)值較差)的粒子具有更強(qiáng)的吸引力，所以合力的方向是通過比較粒子與粒子之間目標(biāo)函數(shù)值的大小來確定的。在電磁場中，通過模擬粒子與粒子之間的受力計算方式，得出所有粒子所受到的作用力，然后通過電磁場疊加原理，得到粒子xi(i=1,2,…,s) 的合力Fi:

(8)

可以看出，目標(biāo)函數(shù)值較優(yōu)的粒子總是決定著粒子與粒子之間的合力Fi的方向，目標(biāo)函數(shù)值越優(yōu)的個體，其吸引其他粒子的能力越強(qiáng)，即種群內(nèi)具有最優(yōu)目標(biāo)函數(shù)值的粒子xbest的吸引力最大，種群內(nèi)的其他粒子均會被其所吸引。種群中除目標(biāo)函數(shù)值最優(yōu)的粒子xbest以外的所有粒子所受到的合力方向的向量和，將一直朝向目標(biāo)函數(shù)值最優(yōu)粒子所在的區(qū)域。

3.2.4粒子移動

在計算粒子的合力后，下一步將對除最優(yōu)粒子xbest以外的其他粒子進(jìn)行移動，種群中每個粒子受到合力的方向即為該粒子的移動方向。粒子在移動過程中需要選取移動步長，移動步長取得適當(dāng)與否將直接影響算法的收斂速度，本文移動步長λ的選取采用均勻分布的隨機(jī)數(shù)，即λ∈[0,1]。同時，控制向量RNG=(v1,v2,…,vn)控制粒子的可行移動范圍，粒子對應(yīng)的向上和向下邊界移動的可行步長是由控制向量的分量表示。粒子移動計算式為：

(9)

且有：

(10)

3.2.5結(jié)束準(zhǔn)則

綜上所述，算法的結(jié)束準(zhǔn)則有兩個條件：(1) 使用最優(yōu)粒子在一定的迭代次數(shù)內(nèi)不發(fā)生變化作為結(jié)束準(zhǔn)則；(2) 將最大迭代次數(shù)設(shè)定為一個固定值作為算法的結(jié)束準(zhǔn)則，但即便如此，EM算法易陷入局部極值的缺陷還是無法避免，影響算法的搜索范圍和尋優(yōu)精度。

3.3 改進(jìn)類電磁算法

標(biāo)準(zhǔn)EM算法采用隨機(jī)線性搜索作為局部搜索過程的方式，該方式搜索方向固定，進(jìn)而使得標(biāo)準(zhǔn)EM算法的搜索范圍小，易陷入局部極值且無法跳出，最終導(dǎo)致算法無法找到全局最優(yōu)解。模擬退火算法是一種已在許多復(fù)雜的組合優(yōu)化問題中得到廣泛應(yīng)用的算法，其具有受控條件少、全局優(yōu)化性能較高、尋優(yōu)速率快等特點。該算法與其他算法相比，通過采用Metropolis接受機(jī)制這種獨特的方式接受優(yōu)化過程中的非優(yōu)解，具有極好的躍出局部極值的能力。

本文引入模擬退火的思想，用以解決標(biāo)準(zhǔn)EM算法搜索范圍小、易陷入局部極值且無法跳出的問題。為避免標(biāo)準(zhǔn)EM算法在局部搜索過程中陷入局部極值的問題，本文加入了模擬退火算法，通過Metropolis接受機(jī)制以一定概率接受目標(biāo)適應(yīng)度更差的解，增加粒子的多樣性，擴(kuò)大局部搜索范圍，使得算法在隨機(jī)搜索過程中可以改變搜索方向，進(jìn)而改善標(biāo)準(zhǔn)EM算法局部搜索過程中陷入極值的問題，最終達(dá)到搜尋全局最優(yōu)解能力和增加算法精度的目的。綜上所述，將模擬退火算法與標(biāo)準(zhǔn)EM算法結(jié)合所得出的基于模擬退火的類電磁算法(Electromagnetism-like Mechanism algorithm based on simulated annealing algorithm, SAEM)，可有效地解決標(biāo)準(zhǔn)EM算法易陷入局部極值而無法跳出的問題，提高了整個算法的尋優(yōu)精度。

3.3.1模擬退火算法的Metropolis接受機(jī)制[22]

模具在模臺上的組合分配問題可描述為一個組合優(yōu)化問題：優(yōu)化函數(shù)為f:x→R+，其中x∈S，它表示優(yōu)化問題的一個可行解，R+={y|y∈R,y>0}，S表示函數(shù)的定義域。N(x)?S表示x的一個鄰域集合。

接受機(jī)制需要設(shè)定一個初始溫度T0和待解決優(yōu)化問題的一個初始解x(0)，并且x(0)下一個新解x′∈N(x(0))，一個新解x(1)是否接受x′取決于如下概率：

(11)

(12)

在溫度Ti下，經(jīng)過多次的變換和轉(zhuǎn)移之后，不斷降低溫度Ti以此得到Ti+1

模具在模臺上排列組合的過程中，通過優(yōu)化預(yù)制構(gòu)件的上線順序進(jìn)行排列組合，當(dāng)EM算法陷入局部極值時，加入的模擬退火的Metropolis機(jī)制就會以一定的概率吸收更差的值進(jìn)來，擴(kuò)大種群的多樣性，從而有助于跳出局部極值，找到最優(yōu)解。

3.3.2SAEM算法步驟

Step1設(shè)置初始化算法參數(shù)α，初始的退火溫度記為T0。

Step2依據(jù)參數(shù)α，對于每一個粒子的各維坐標(biāo)分別計算，各維坐標(biāo)計算所得的進(jìn)行移動的最大步長記為v。

Step3所有粒子在可行域中依據(jù)最大移動步長v進(jìn)行局部搜索過程。

Step4在局部搜索的過程中，將新生成粒子的適應(yīng)度值與原粒子的適應(yīng)度值進(jìn)行比較，若前者較大，則轉(zhuǎn)到Step5，否則轉(zhuǎn)到Step7。

Step5將新生成粒子的適應(yīng)度值f(x′)減去之前可行解中的適應(yīng)度值f(x)，通過概率公式P=exp(-(f(x′)-f(x))/T0)>rand[0,1]判斷接受新可行解是否滿足條件，其中rand[0,1]是[0,1]之間的隨機(jī)數(shù)。

Step6在算法進(jìn)化的過程中，一旦溫度T0達(dá)到平衡狀態(tài)，退火機(jī)制開始按照溫度更新函數(shù)Tk+1=WTk降低溫度，其中W∈[0,1]。

Step7直到局部搜索的次數(shù)等于設(shè)置的最大值L或者搜索到一個新的粒子來代替原粒子時停止局部搜索過程。

Step8重新計算新種群中所有粒子的適應(yīng)度值并進(jìn)行比較更新直到找到最優(yōu)粒子，記為xbest。

Step9判斷SAEM算法是否滿足設(shè)置的結(jié)束準(zhǔn)則，若滿足結(jié)束準(zhǔn)則則終止算法進(jìn)程，否則轉(zhuǎn)到Step3。

4 實驗與結(jié)果分析

為進(jìn)一步研究本文方法，即改進(jìn)的類電磁算法優(yōu)化投產(chǎn)預(yù)制構(gòu)件的上線順序與改進(jìn)的BL定位算法控制模具在模臺上的擺放位置和方向相結(jié)合的方法，通過使用某混凝土預(yù)制構(gòu)件生產(chǎn)企業(yè)的生產(chǎn)實例對該方法進(jìn)行仿真實驗，分別從優(yōu)化效果、多種優(yōu)化算法組合結(jié)果和全局算法優(yōu)化效果，多角度分析評估該方法，來驗證該方法的有效性。

4.1 構(gòu)造仿真數(shù)據(jù)

某建筑預(yù)制構(gòu)件生產(chǎn)企業(yè)的生產(chǎn)線中，模臺的尺寸為6 000(mm)×4 000(mm)，需要生產(chǎn)一批不同尺寸的板類預(yù)制構(gòu)件，共有37種類型，共計生產(chǎn)130個預(yù)制構(gòu)件，其尺寸及數(shù)量如表1所示。

表1 預(yù)制構(gòu)件生產(chǎn)清單

續(xù)表1

4.2 設(shè)計仿真方案及構(gòu)建評價指標(biāo)

為驗證本文方法的有效性和實驗結(jié)果的合理性，針對上述仿真數(shù)據(jù)，需要提出多種方法對不同的評價指標(biāo)進(jìn)行對比實驗。

4.2.1設(shè)計仿真方案

針對模具在模臺上的組合分配問題，本文提出了基于模擬退火的類電磁算法與改進(jìn)的BL定位算法相結(jié)合的方法求解該問題，分別設(shè)置了4組對比方法。在控制模具在模臺上的擺放位置和方向問題上，方法1和方法2均使用了標(biāo)準(zhǔn)的BL定位算法，方法3和方法4均使用了改進(jìn)的BL定位算法；在優(yōu)化投產(chǎn)的預(yù)制構(gòu)件上線順序問題上，方法2和方法3均使用了標(biāo)準(zhǔn)的EM算法作為全局優(yōu)化算法來優(yōu)化預(yù)制構(gòu)件的上線順序，方法4使用了SAEM算法作為全局優(yōu)化算法來優(yōu)化預(yù)制構(gòu)件的上線順序。對這4組方法的仿真結(jié)果進(jìn)行對比，分析各個方法求解模具在模臺上組合分配問題的優(yōu)化效果，構(gòu)建組合分配方法的信息如表2所示。

表2 4組組合分配方法信息

4.2.2構(gòu)建評價指標(biāo)

① 平均模臺利用率：

(13)

② 最低模臺利用率：

fmin=min{f1,f2,…,fe}

(14)

式中:fmin表示進(jìn)行E次仿真實驗過程中模臺利用率的最小值。

③ 最高模臺利用率：

fmax=max{f1,f2,…,fe}

(15)

式中：fmax表示進(jìn)行E次仿真實驗過程中模臺利用率的最大值。

4.3 優(yōu)化仿真結(jié)果分析

由于預(yù)制構(gòu)件屬于大型的在制品，立數(shù)大、面積大，板類的預(yù)制構(gòu)件又都是矩形形狀，同時各個模具和模臺邊緣要有一定的工藝間隔，本文設(shè)計的工藝間隔C=10 cm，所以模臺的利用率無法達(dá)到100%。為分析全局優(yōu)化算法和改進(jìn)的BL定位算法在求解模具在模臺上的組合分配問題中的應(yīng)用效果，選取仿真數(shù)據(jù)中類型編號1-50的矩形預(yù)制構(gòu)件，分別采用方法1和方法4的優(yōu)化算法對這50個預(yù)制構(gòu)件進(jìn)行10次仿真實驗，采用方法1所得到的10次仿真結(jié)果如表3所示，10次仿真結(jié)果中最優(yōu)結(jié)果模臺利用率f為60.0%。從兩個方法中分別選出模具在模臺上的組合分配最好的結(jié)果可視化如圖6和圖7所示。從圖6可以看出，由于采用隨機(jī)方式生成構(gòu)件的上線順序，會出現(xiàn)多個模臺上只擺放2個模具的情況，模臺沒有被充分利用，共需使用22個模臺來承載模具完成50個預(yù)制構(gòu)件的加工任務(wù)。從圖7可以看出，通過采用改進(jìn)的BL定位算法優(yōu)化模具在模臺上的擺放位置和方向與SAEM算法優(yōu)化預(yù)制構(gòu)件上線順序，有多個模臺承載3個模具的情況，模臺臺面空間得到了更充分的利用，承載50個模具所使用模臺的數(shù)量降低到17個，為優(yōu)化的最大限度，減少了模臺的使用數(shù)量，提高了模臺的利用率。因此，本文方法對于提高模臺利用率和減少模臺使用數(shù)量是有明顯效果的。

表3 1-50號的預(yù)制構(gòu)件10次隨機(jī)生成的上線順序結(jié)果

圖6 隨機(jī)生成上線順序和BL定位算法結(jié)合生成的模具模臺簡圖

圖7 采用SAEM算法和改進(jìn)BL定位算法結(jié)合生成的模具模臺簡圖

表4 3種方法在不同的數(shù)據(jù)規(guī)模下就優(yōu)化目標(biāo)產(chǎn)生的3組對應(yīng)方案

圖8 模臺利用率在不同數(shù)據(jù)規(guī)模下的變化曲線

方案3和方案4中分別使用EM算法和SAEM算法作為全局優(yōu)化算法優(yōu)化預(yù)制構(gòu)件的上線順序。數(shù)據(jù)規(guī)模為130時，選取模臺利用率f作為優(yōu)化目標(biāo)，繪制的優(yōu)化過程曲線如圖9所示?？梢钥闯觯惴ㄔ谶M(jìn)化初始階段收斂迅速，表現(xiàn)出較強(qiáng)的搜索能力，但隨著進(jìn)化代數(shù)的增加，EM算法陷入了局部極值，在第70代左右停止進(jìn)化。而SAEM算法在第90代左右陷入了極值，但在210代左右跳出了局部極值并最終進(jìn)化得到了最優(yōu)值，這表明了基于模擬退火的電磁算法在優(yōu)化上線順序的過程中較標(biāo)準(zhǔn)的電磁算法具有更優(yōu)的效果。

圖9 EM算法和SAEM進(jìn)化曲線

5 結(jié) 語

本文以建筑預(yù)制構(gòu)件生產(chǎn)線中模具在模臺上的組合分配問題為研究對象，結(jié)合建筑預(yù)制構(gòu)件本身排布的特點建立數(shù)學(xué)模型，針對模具在模臺上的擺放問題，將經(jīng)典的BL定位算法進(jìn)行改進(jìn)以適合預(yù)制構(gòu)件的加工特點。同時將基于模擬退火的類電磁算法作為全局優(yōu)化算法來優(yōu)化預(yù)制構(gòu)件的上線順序，擴(kuò)大標(biāo)準(zhǔn)EM算法的局部搜索范圍，增加粒子的多樣性，提高算法的靈活度。建立了四組實驗優(yōu)化方法進(jìn)行對比分析，并分別測試方法在不同數(shù)據(jù)規(guī)模下的求解效果。測試結(jié)果表明，SAEM算法優(yōu)化投產(chǎn)預(yù)制構(gòu)件上線順序與改進(jìn)的BL定位算法控制模具在模臺上擺放位置和方向相結(jié)合的方法，能夠有效地解決預(yù)制構(gòu)件生產(chǎn)過程中模具在模臺上組合分配問題。接下來會訓(xùn)練多種不同尺寸的數(shù)據(jù)來提高本文方法的穩(wěn)定性和魯棒性，希望能在預(yù)制構(gòu)件生產(chǎn)企業(yè)發(fā)揮巨大的作用，提高企業(yè)的生產(chǎn)效率。