欒方軍 王 帥 崔洪斌

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

0 引 言

近年來我國建筑業(yè)持續(xù)快速發(fā)展，隨著建筑規(guī)模的不斷擴(kuò)大，傳統(tǒng)的建筑方式出現(xiàn)了勞動(dòng)力缺乏、成本變高、資源緊缺等問題。為了應(yīng)對(duì)上述問題和亟待加快建筑工業(yè)化[1]的進(jìn)程，裝配式建筑[2-3]方式得到了迅猛發(fā)展。這種建筑方式需要用到大量的預(yù)制混凝土構(gòu)件，即PC構(gòu)件(Prefabricated Concrete Component)，因此現(xiàn)階段對(duì)于裝配式建筑生產(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)件上線時(shí)，通過選擇不同的構(gòu)件組合分配到模臺(tái)上進(jìn)行加工，而每個(gè)預(yù)制構(gòu)件通過固定在模臺(tái)上的模具進(jìn)行生產(chǎn)，模臺(tái)作為轉(zhuǎn)運(yùn)工具承載著模具完成預(yù)制構(gòu)件生產(chǎn)的全過程。每個(gè)模臺(tái)尺寸完全相同，而模具尺寸有差異，為更充分地利用模臺(tái)的臺(tái)面空間，需要盡可能多地?cái)[放模具。如果不能合理地依據(jù)模具尺寸將模具分配到模臺(tái)上，會(huì)導(dǎo)致模臺(tái)的臺(tái)面得不到充分利用，完成生產(chǎn)同樣數(shù)量的預(yù)制構(gòu)件需要使用更多的模臺(tái)，導(dǎo)致模臺(tái)的利用率低，這嚴(yán)重地制約了企業(yè)產(chǎn)能的發(fā)揮。因此，研究建筑預(yù)制構(gòu)件生產(chǎn)線上模具在模臺(tái)上的組合分配問題，探索提高模臺(tái)利用率的方法，對(duì)企業(yè)發(fā)揮現(xiàn)有產(chǎn)能和降低生產(chǎn)成本具有重要的意義。

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

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

采用改進(jìn)的BL定位算法后，給定構(gòu)件的模具擺放在模臺(tái)上的位置即被唯一確定，即模具在模臺(tái)上的組合分配問題就可以轉(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ā)式算法，模擬了帶電粒子在電磁場(chǎng)中的吸引或排斥原理，通過該原理使得粒子朝著最優(yōu)粒子移動(dòng)，其獨(dú)特的優(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é)合的方法，來解決模具分配到模臺(tái)上的組合分配問題，從而獲取能夠更有效利用模臺(tái)面積的模具組合分配結(jié)果，實(shí)現(xiàn)提高模臺(tái)利用率，減少模臺(tái)使用數(shù)量的目標(biāo)。

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

1.1 模型參數(shù)

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

1.2 模具在模臺(tái)上的組合分配問題描述

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

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

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

圖2 模具在模臺(tái)上的組合方式

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

圖3 模具在模臺(tái)上的擺放模型圖

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

(1)

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

1.3 模具在模臺(tái)臺(tái)面上組合分配的約束條件

模具在模臺(tái)上組合分配問題需要滿足以下四個(gè)約束條件：

① 放置在同一模臺(tái)上的兩個(gè)模具之間互不重疊。

(2)

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

(3)

③ 在同一模臺(tái)上布置的所有模具面積總和小于單個(gè)模臺(tái)的面積。

(4)

④ 使用的模臺(tái)面積總和大于等于所有擺放模具的面積總和。

(5)

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

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

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

(6)

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

2 模具在模臺(tái)上的擺放方法

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

2.1 BL定位算法

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

圖4 BL定位算法原理圖

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

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

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

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

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

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

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

如果第一個(gè)模具縱向擺放：

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

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

圖5 模具在模臺(tái)上的擺放方向和順序

2.2.2算法步驟

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

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

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

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

3.2 EM算法步驟

EM算法劃分為四個(gè)步驟，分別為初始種群的建立、局部搜索、合力計(jì)算和粒子移動(dòng)。

3.2.1初始種群的建立

3.2.2局部搜索

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

3.2.3計(jì)算合力

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

(7)

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

(8)

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

3.2.4粒子移動(dòng)

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

(9)

且有：

(10)

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

綜上所述，算法的結(jié)束準(zhǔn)則有兩個(gè)條件：(1) 使用最優(yōu)粒子在一定的迭代次數(shù)內(nèi)不發(fā)生變化作為結(jié)束準(zhǔn)則；(2) 將最大迭代次數(shù)設(shè)定為一個(gè)固定值作為算法的結(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)速率快等特點(diǎn)。該算法與其他算法相比，通過采用Metropolis接受機(jī)制這種獨(dú)特的方式接受優(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算法易陷入局部極值而無法跳出的問題，提高了整個(gè)算法的尋優(yōu)精度。

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

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

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

(11)

(12)

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

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

3.3.2SAEM算法步驟

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

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

Step3所有粒子在可行域中依據(jù)最大移動(dòng)步長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或者搜索到一個(gè)新的粒子來代替原粒子時(shí)停止局部搜索過程。

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

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

4 實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

續(xù)表1

4.2 設(shè)計(jì)仿真方案及構(gòu)建評(píng)價(jià)指標(biāo)

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

4.2.1設(shè)計(jì)仿真方案

針對(duì)模具在模臺(tái)上的組合分配問題，本文提出了基于模擬退火的類電磁算法與改進(jìn)的BL定位算法相結(jié)合的方法求解該問題，分別設(shè)置了4組對(duì)比方法。在控制模具在模臺(tái)上的擺放位置和方向問題上，方法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)件的上線順序。對(duì)這4組方法的仿真結(jié)果進(jìn)行對(duì)比，分析各個(gè)方法求解模具在模臺(tái)上組合分配問題的優(yōu)化效果，構(gòu)建組合分配方法的信息如表2所示。

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

4.2.2構(gòu)建評(píng)價(jià)指標(biāo)

① 平均模臺(tái)利用率：

(13)

② 最低模臺(tái)利用率：

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

(14)

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

③ 最高模臺(tái)利用率：

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

(15)

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

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

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

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

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

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

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

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

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