基于改進(jìn)遺傳算法的浮法玻璃優(yōu)化切割

王聰聰，楊明順，原 欣，高新勤

WANG Congcong,YANG Mingshun,YUAN Xin,GAO Xinqin

西安理工大學(xué) 機(jī)械與精密儀器工程學(xué)院，西安 710048

School of Mechanical and Precision Instrument Engineering,Xi’an University of Technology,Xi’an 710048,China

1 引言

浮法玻璃是平板玻璃的一種，具有表面平整光滑、透視性佳、厚度均勻等優(yōu)點(diǎn)，廣泛應(yīng)用于制鏡玻璃、汽車(chē)擋風(fēng)玻璃、建筑門(mén)窗等多個(gè)方面[1]。和普通平板玻璃不同，浮法玻璃生產(chǎn)過(guò)程中的許多因素都會(huì)導(dǎo)致玻璃表面產(chǎn)生各種缺陷，而以目前的生產(chǎn)水平，浮法玻璃廠家很難杜絕缺陷的出現(xiàn)[2]，這些缺陷的種類(lèi)、數(shù)量和大小會(huì)不同程度地影響玻璃質(zhì)量，進(jìn)而影響玻璃價(jià)格。因此，在浮法玻璃切割過(guò)程中，僅關(guān)注提高玻璃原板利用率的傳統(tǒng)切割方法對(duì)浮法玻璃不再適用，必須根據(jù)浮法玻璃的生產(chǎn)特性，提出新的優(yōu)化切割方案。

玻璃切割問(wèn)題是一個(gè)典型的組合優(yōu)化問(wèn)題，類(lèi)似的問(wèn)題還有二維下料問(wèn)題、矩形件排樣問(wèn)題、二維裝箱問(wèn)題等。近年來(lái)，學(xué)者們對(duì)該類(lèi)問(wèn)題進(jìn)行了大量研究。文獻(xiàn)[3]針對(duì)玻璃優(yōu)化切割問(wèn)題，以玻璃原板利用率最大為優(yōu)化目標(biāo)，提出了一種啟發(fā)式優(yōu)化排樣算法，并通過(guò)實(shí)例對(duì)該算法進(jìn)行了驗(yàn)證；文獻(xiàn)[4]通過(guò)對(duì)玻璃切割問(wèn)題的研究，以玻璃原板利用率最大為優(yōu)化目標(biāo)，提出了一種融合量子粒子群優(yōu)化和蟻群優(yōu)化的混合算法，并通過(guò)實(shí)驗(yàn)對(duì)該算法進(jìn)行了驗(yàn)證；文獻(xiàn)[5]針對(duì)有約束的兩階段二維切割問(wèn)題，以板材利用率最大為優(yōu)化目標(biāo)，提出了一種并行算法，并以實(shí)例對(duì)該算法進(jìn)行了驗(yàn)證；文獻(xiàn)[6]針對(duì)矩形件二維下料問(wèn)題，以板材利用率最大為優(yōu)化目標(biāo)，提出了一種單毛坯條帶四塊排樣方法，并通過(guò)實(shí)驗(yàn)對(duì)該方法進(jìn)行了驗(yàn)證；文獻(xiàn)[7]針對(duì)多規(guī)格的兩階段二維一刀切下料問(wèn)題，以板材利用率最大為優(yōu)化目標(biāo)，提出了一種列生成啟發(fā)式算法，并以實(shí)例對(duì)該算法進(jìn)行了驗(yàn)證；文獻(xiàn)[8]針對(duì)一刀切矩形件排樣問(wèn)題，以板材利用率最大為優(yōu)化目標(biāo)，提出了一種將啟發(fā)式遞歸與免疫克隆算法相結(jié)合的混合優(yōu)化算法，并以兩個(gè)實(shí)例對(duì)該算法進(jìn)行了驗(yàn)證；文獻(xiàn)[9]針對(duì)二維矩形件優(yōu)化排樣問(wèn)題，以板材利用率最大為優(yōu)化目標(biāo)，提出了一種確定性啟發(fā)式最佳匹配算法，并以兩個(gè)實(shí)例對(duì)該算法進(jìn)行了驗(yàn)證；文獻(xiàn)[10]針對(duì)二維裝箱問(wèn)題，以填充率最大為優(yōu)化目標(biāo)，提出了一種混合進(jìn)化算法，并通過(guò)實(shí)例對(duì)該算法進(jìn)行了驗(yàn)證；文獻(xiàn)[11]針對(duì)離線定向和不定向二維裝箱問(wèn)題，以填充率最大為優(yōu)化目標(biāo)，提出了一種超啟發(fā)式算法，并通過(guò)實(shí)驗(yàn)對(duì)該算法進(jìn)行了驗(yàn)證。

圖1 浮法玻璃優(yōu)化切割過(guò)程圖示

上述算法都不同程度達(dá)到了減少材料浪費(fèi)，提高原板利用率（填充率）的目的，但僅考慮提高玻璃原板利用率，并不能完全滿足浮法玻璃優(yōu)化切割的基本要求。浮法玻璃的價(jià)格是由切割獲得的玻璃成品的面積和玻璃質(zhì)量共同決定的，因此，即使玻璃原板利用率最大，也并不能保證玻璃成品總價(jià)格最高。

迄今為止，僅有少數(shù)學(xué)者在解決以上組合優(yōu)化問(wèn)題時(shí)，將缺陷對(duì)成品質(zhì)量的影響考慮在內(nèi)。文獻(xiàn)[12]針對(duì)考慮質(zhì)量要求的一維下料問(wèn)題，提出了一種二階段序列啟發(fā)式算法，并以實(shí)例對(duì)該算法進(jìn)行了驗(yàn)證；文獻(xiàn)[13]針對(duì)考慮缺陷的二維切割問(wèn)題，以切割獲得的矩形塊的價(jià)值最大為優(yōu)化目標(biāo)，提出了一種基于動(dòng)態(tài)規(guī)劃的啟發(fā)式算法，并通過(guò)實(shí)例驗(yàn)證了算法的有效性；文獻(xiàn)[14]針對(duì)紡織工業(yè)中考慮缺陷的布料切割問(wèn)題，以總利潤(rùn)最大為優(yōu)化目標(biāo)提出了一種改進(jìn)模擬退火算法，并通過(guò)實(shí)例證明了算法的有效性；文獻(xiàn)[15]針對(duì)考慮缺陷的玻璃優(yōu)化切割問(wèn)題，以最小化切割獲得的廢品數(shù)量為優(yōu)化目標(biāo)，提出了一種基于動(dòng)態(tài)規(guī)劃的算法，并通過(guò)實(shí)例證明了算法的有效性。

本文在上述研究的基礎(chǔ)上，結(jié)合浮法玻璃的生產(chǎn)實(shí)際，考慮相應(yīng)的缺陷分級(jí)和玻璃分級(jí)標(biāo)準(zhǔn)，同時(shí)考慮提高玻璃成品質(zhì)量和玻璃原板利用率，以玻璃成品總價(jià)格最大為優(yōu)化目標(biāo)建立數(shù)學(xué)模型，提出了一種符合浮法玻璃切割問(wèn)題特性的遺傳算法。

2 浮法玻璃優(yōu)化切割問(wèn)題簡(jiǎn)介

浮法玻璃的切割過(guò)程主要包括：缺陷檢測(cè)、生成切割方案、縱向切割和橫向切割4個(gè)步驟，如圖1所示。在實(shí)際生產(chǎn)過(guò)程中，玻璃帶被輸送輥道緩慢勻速向前輸送，在玻璃帶運(yùn)行過(guò)程中，首先，通過(guò)缺陷檢測(cè)裝置，獲得玻璃帶上各缺陷的位置、種類(lèi)和大小等信息；其次，在已知玻璃缺陷信息的基礎(chǔ)上，根據(jù)切割訂單要求，在某一固定長(zhǎng)度的玻璃帶上生成有效的切割方案；最后，按照確定的切割方案實(shí)施縱向切割和橫向切割，獲得玻璃成品。

與普通平板玻璃切割相比，浮法玻璃優(yōu)化切割的特性主要體現(xiàn)在以下三方面：

（1）浮法玻璃的切割工藝要求。縱切必須切整個(gè)板寬，中間不能抬刀，橫切可以改變玻璃規(guī)格。據(jù)此可知，在規(guī)劃切割方案時(shí)，只有長(zhǎng)度相等的玻璃原片才能排放在玻璃原板的同一列。以表1中的切割訂單為例：訂單編號(hào)為1的玻璃原片可以和自身或編號(hào)為2的玻璃原片規(guī)劃在同一列。

表1 切割訂單

（2）浮法玻璃原片質(zhì)量等級(jí)的判定。按照浮法玻璃國(guó)家標(biāo)準(zhǔn)或企業(yè)自行制定的標(biāo)準(zhǔn)，可將切割獲得的玻璃成品劃分為若干個(gè)質(zhì)量等級(jí)，不同等級(jí)的玻璃允許含有的缺陷種類(lèi)、數(shù)量和等級(jí)不同，玻璃質(zhì)量等級(jí)越高，其每平方米價(jià)格越高，因此應(yīng)盡可能切出質(zhì)量等級(jí)較高的玻璃成品。

（3）玻璃原片的質(zhì)量等級(jí)與其排放位置息息相關(guān)。如圖2所示，假設(shè)排放在第1列第1個(gè)位置和第2個(gè)位置的訂單編號(hào)分別為i和j(i≠j)，若交換這兩塊玻璃的排放位置，并不會(huì)改變玻璃原板的利用率，但由于玻璃原片的位置變動(dòng)，其上包含的缺陷信息也隨之改變。因此，當(dāng)某塊玻璃原片的位置發(fā)生變動(dòng)，其質(zhì)量等級(jí)需要根據(jù)新的缺陷信息進(jìn)行重新判定。

圖2 排放位置對(duì)玻璃原片質(zhì)量的影響

3 數(shù)學(xué)模型

浮法玻璃優(yōu)化切割問(wèn)題是指：在一塊已知長(zhǎng)度、寬度以及缺陷信息的浮法玻璃板面上，根據(jù)訂單要求切割一定規(guī)格的玻璃原片時(shí)，應(yīng)優(yōu)先規(guī)劃質(zhì)量較好的玻璃原片，并保證玻璃原板的利用率較大，以使得切割所得玻璃成品的銷(xiāo)售總價(jià)最高。

該問(wèn)題中各變量及其符號(hào)表示如下：

Length為玻璃原板的長(zhǎng)度；Width為玻璃原板的寬度；n為玻璃原板上的缺陷點(diǎn)總數(shù)；D為缺陷集，其中即每個(gè)缺陷點(diǎn)均含有3個(gè)基本屬性：缺陷位置pi，缺陷種類(lèi)ti，缺陷大小si，其中pi=(xi,yi)，xi、yi分別為缺陷點(diǎn)中心到切割原點(diǎn)的橫向和縱向距離，ti∈{氣泡，夾雜，光畸變，錫灰，玻筋，線道，其他}。

m為切割訂單包含的訂單規(guī)格總數(shù)；CO表示切割訂單，其中Oj=(lj,wj)，lj和wj分別表示切割訂單中各訂單規(guī)格對(duì)應(yīng)的長(zhǎng)度和寬度，l和w分別表示切割訂單中所有訂單規(guī)格對(duì)應(yīng)的長(zhǎng)度和寬度的集合，

DC為缺陷分級(jí)參數(shù)，用于判定缺陷的等級(jí)，DC=根據(jù)缺陷分級(jí)參數(shù)可將缺陷劃分為H+1個(gè)等級(jí)，等級(jí)為H+1的缺陷也稱(chēng)為“不允許缺陷”。

QC為玻璃分級(jí)參數(shù)，用于判定玻璃原片的質(zhì)量等級(jí)，其中O≤M1≤M2≤…≤MT，且矩陣Mt互不相等（“≤”表示前一個(gè)矩陣的所有元素均不超過(guò)后一個(gè)矩陣對(duì)應(yīng)位置的元素）。Mt表示一個(gè)N×(H+1)的矩陣，O表示一個(gè)和矩陣Mt同型的零矩陣，N為玻璃原板上包含的缺陷種類(lèi)數(shù)，矩陣Mt中第i行第j列的元素Mt(i,j)表示等級(jí)為t的玻璃每平方米允許含有種類(lèi)為i等級(jí)為j的缺陷的數(shù)量，根據(jù)玻璃分級(jí)參數(shù)可將玻璃劃分為T(mén)+1個(gè)質(zhì)量等級(jí)，等級(jí)為T(mén)+1的玻璃也稱(chēng)為“廢品級(jí)玻璃”。

SP為玻璃單位面積價(jià)格的集合，SP={St|t=1,其中St表示等級(jí)為t的玻璃每平方米價(jià)格為St。

xc,r為決策變量，其值等于排放在玻璃原板第c列的第r塊玻璃原片的訂單規(guī)格編號(hào)；colMax為玻璃原板上排放玻璃原片的最大列數(shù)；glaNumMax為每列最多可以排放的玻璃原片塊數(shù)；colReal為玻璃原板上實(shí)際排放的玻璃原片的列數(shù)；glaNum(c)為第c列實(shí)際排放的玻璃原片的塊數(shù)；集合cset為列數(shù)集合cset={1,2,…,colMax}；rset為塊數(shù)集合，rset={1,2,…,glaNum(c)}；lrnd等于集合l中的任意一個(gè)值，即glassArr表示一個(gè)可行的切割方案；g(c,r)表示該切割方案中排放在玻璃原板第c列的第r塊玻璃原片的信息集：

其中，xst(xc,r)和yst(xc,r)分別為該玻璃原片左下角距離切割原點(diǎn)的橫向和縱向距離；lr(xc,r)和wr(xc,r)分別表示該玻璃原片的長(zhǎng)度和寬度；Dr(xc,r)為該玻璃原片上包含的缺陷集，Dr(xc,r)∈D,nr為該玻璃原片上的缺陷總數(shù)，dpk、dtk、dsk分別表示該玻璃原片上各缺陷的位置、種類(lèi)和大小，為該玻璃原片對(duì)應(yīng)的缺陷計(jì)數(shù)矩陣，用來(lái)存儲(chǔ)該玻璃原片實(shí)際每平方米包含的不同種類(lèi)、不同等級(jí)缺陷的數(shù)量；glag(xc,r)為該玻璃原片的質(zhì)量等級(jí)；pr(xc,r)為該塊玻璃原片每平方米的價(jià)格。圖3為一個(gè)可行切割方案示例。

該問(wèn)題的目標(biāo)函數(shù)及約束條件如下：

圖3 可行切割方案示例

式（1）為目標(biāo)函數(shù)的計(jì)算公式，其值為玻璃成品的總價(jià)格；式（2）、（3）為玻璃原板最多可以排放玻璃原片的列數(shù)colMax，及每列最多可以排放的玻璃原片的塊數(shù)glaNumMax的計(jì)算公式；式（4）、（5）表示玻璃原板實(shí)際排放的玻璃原片的列數(shù)不超過(guò)colMax，每列實(shí)際排放的玻璃原片的塊數(shù)不超過(guò)glaNumMax；式（6）、（7）分別為玻璃原板的長(zhǎng)度約束和寬度約束，表示排放的所有玻璃原片均不能超過(guò)玻璃原板的邊界；式（8）為排放在同一列的玻璃原片的等長(zhǎng)約束，即排放在玻璃原板同一列的玻璃原片的長(zhǎng)必須相等；式（9）為決策變量的取值范圍，表示排放的玻璃原片的規(guī)格必須來(lái)自切割訂單；式（10）、（11）為該玻璃原片上缺陷的位置約束，表示同時(shí)滿足式（10）、（11）約束的缺陷點(diǎn)在該玻璃原片上；式（12）為缺陷等級(jí)的判定公式；式（13）為玻璃質(zhì)量等級(jí)的判定公式，其含義為已知某塊玻璃的缺陷計(jì)數(shù)矩陣CM，玻璃分級(jí)參數(shù)QC，首先判斷CM≤M1是否成立（CM的所有元素均不超過(guò)玻璃分級(jí)參數(shù)矩陣M1對(duì)應(yīng)位置的元素），若成立，則該玻璃等級(jí)為1，否則降級(jí)，繼續(xù)判斷CM≤M2是否成立，若成立，則該玻璃的等級(jí)為2，否則降級(jí)，繼續(xù)判斷，以此類(lèi)推，若直至CM≤MT仍不成立，則該玻璃等級(jí)為T(mén)+1（即廢品級(jí)）；式（14）為玻璃原片單位面積價(jià)格的判定公式，用于根據(jù)玻璃原片的質(zhì)量等級(jí)進(jìn)一步判定其每平方米的價(jià)格。

4 算法設(shè)計(jì)

浮法玻璃優(yōu)化切割屬于NP難類(lèi)組合優(yōu)化問(wèn)題，隨著訂單規(guī)格的增加及缺陷信息的多樣化，尋優(yōu)過(guò)程將變得十分復(fù)雜，此時(shí)很難在有限時(shí)間內(nèi)遍歷所有解空間，從中找出最優(yōu)解，因此精確求解算法不再適用。遺傳算法是基于進(jìn)化理論原理發(fā)展起來(lái)的一種高效的隨機(jī)搜索算法，在解決組合優(yōu)化問(wèn)題時(shí)具有較好的性能。本文根據(jù)浮法玻璃優(yōu)化切割問(wèn)題的特點(diǎn)，提出了一種基于玻璃原片排放位置編碼的遺傳算法。以下對(duì)該算法的基本步驟進(jìn)行說(shuō)明。

4.1 編碼

根據(jù)浮法玻璃切割“縱切必須切整個(gè)板寬”的要求（即排在同一列的訂單規(guī)格的長(zhǎng)度必須相等），以及玻璃原片排放位置對(duì)其質(zhì)量等級(jí)的影響，提出了一種基于玻璃原片排放位置的序列編碼方式。每條染色體含有g(shù)n=colMax×glaNumMax個(gè)基因，每個(gè)基因gi的取值為切割訂單中某一個(gè)訂單規(guī)格的編號(hào)，即區(qū)間 [glaNumMax×(k-1)+1,k×glaNumMax]上的基因值對(duì)應(yīng)的玻璃規(guī)格的長(zhǎng)度相等，

以表1中的訂單規(guī)格為例，假設(shè)玻璃原板的長(zhǎng)Length為12200，寬Width為4000，根據(jù)式（2）、（3）可知該玻璃原板最多可以排放6列，每列最多可以排放2塊玻璃原片，染色體基因數(shù)gn=6×2=12。經(jīng)過(guò)編碼得到一個(gè)可能的染色體如圖4所示，該染色體表示玻璃原板上每個(gè)位置擬排放的訂單規(guī)格。如：第一個(gè)基因位上的元素7表示排放在玻璃原板第一列的第一塊玻璃原片的訂單規(guī)格編號(hào)為7；而編號(hào)為7和編號(hào)為6的訂單規(guī)格的長(zhǎng)度相等，可以排在同一列。

圖4 染色體編碼示例

4.2 解碼

為得到具體規(guī)劃方案，需要對(duì)染色體進(jìn)行解碼。根據(jù)玻璃原板的寬度約束和長(zhǎng)度約束從左向右對(duì)染色體依次進(jìn)行解碼，獲得每列實(shí)際允許排放的玻璃規(guī)格。圖4所示染色體的解碼結(jié)果為glassArr={(7,6),(5),(1,2),(4,3),(2,1)}，其含義為：玻璃原板第一列實(shí)際排放的訂單規(guī)格編號(hào)依次為7和6，第二列排放的訂單規(guī)格編號(hào)為5，以此類(lèi)推。

4.3 種群初始化

為保證初始種群的多樣性，采用一種啟發(fā)式搜索算法獲得符合浮法玻璃切割要求的初始種群。一個(gè)可行初始解的生成過(guò)程如下：

步驟1輸入玻璃原板上可排放玻璃原片的最大列數(shù)colMax，每列可排放的玻璃原片的最大塊數(shù)glaNumMax。

步驟2令c=1,r=2。

步驟3從切割訂單中隨機(jī)選擇一個(gè)訂單規(guī)格編號(hào)firstp，排放在第c列的第1個(gè)位置，即染色體的第glaNumMax×(c-1)+1個(gè)位置。

步驟4在切割訂單中尋找和firstp等長(zhǎng)的所有玻璃規(guī)格的編號(hào)，存放在集合eql中。

步驟5在等長(zhǎng)訂單規(guī)格集合eql中隨機(jī)選擇一個(gè)訂單規(guī)格編號(hào)，排放在第c列第r個(gè)位置，即染色體的第glaNumMax×(c-1)+r個(gè)位置。

步驟6判斷r=glaNumMax是否成立，若成立，繼續(xù)進(jìn)行步驟7，否則令r=r+1，轉(zhuǎn)步驟5。

步驟7判斷c=colMax是否成立，若成立，結(jié)束程序，否則，令r=2,c=c+1，轉(zhuǎn)步驟3。

將以上過(guò)程循環(huán)N(p)次，即可獲得該問(wèn)題的初始種群。

4.4 計(jì)算適應(yīng)度函數(shù)值

采用該問(wèn)題的目標(biāo)函數(shù)值作為該算法的適應(yīng)度函數(shù)值，第i個(gè)染色體的適應(yīng)度函數(shù)值的計(jì)算公式為：

某塊玻璃原片的價(jià)格是由其面積lr×wr及其單位面積的價(jià)格pr共同決定的，當(dāng)訂單規(guī)格已知時(shí)，該玻璃原片的面積是確定的，但該玻璃原片單位面積的價(jià)格需要由其包含的缺陷信息判定。

以下給出根據(jù)某塊玻璃原片上包含的缺陷信息，判定其質(zhì)量等級(jí)，進(jìn)而判定其單位面積價(jià)格的步驟：

步驟1輸入缺陷分級(jí)參數(shù)DC,玻璃分級(jí)參數(shù)QC,玻璃單位面積價(jià)格的集合SP,玻璃原片上包含的缺陷集合Dr。

步驟2根據(jù)缺陷分級(jí)參數(shù)DC判定該玻璃原片上各缺陷的等級(jí)，見(jiàn)式（12），整理缺陷的種類(lèi)和等級(jí)信息，獲得該玻璃原片的缺陷計(jì)數(shù)矩陣CM。

步驟3根據(jù)缺陷計(jì)數(shù)矩陣CM判定該玻璃原片等級(jí)，見(jiàn)式（13）。

步驟4根據(jù)玻璃原片等級(jí)判定其每平方米價(jià)格，見(jiàn)式（14）。

根據(jù)以上過(guò)程，依次判斷glassArr中每塊玻璃原片的單位面積價(jià)格，再根據(jù)式（15）計(jì)算該染色體對(duì)應(yīng)的適應(yīng)度函數(shù)值。

4.5 選擇算子

采用隨機(jī)按比例的方式選擇個(gè)體進(jìn)入交配庫(kù)，使得適應(yīng)度函數(shù)值較大的個(gè)體被選擇概率較大。

步驟1將所有個(gè)體的適應(yīng)度函數(shù)值按照升序排列，得到集合Fsort。

步驟3將步驟2循環(huán)N(p)次，直至選滿N(p)個(gè)個(gè)體為止。

4.6 交叉算子

為保證交叉后染色體的可行性，本文針對(duì)浮法玻璃切割問(wèn)題的特點(diǎn)，提出了一種兩點(diǎn)交叉法。

步驟1從選擇操作產(chǎn)生的交配庫(kù)中隨機(jī)選取兩個(gè)染色體F1、F2，作為交叉操作的父代。

步驟2隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)P1、P2，為保證兩個(gè)父代經(jīng)過(guò)交叉后不破壞染色體的可行性，P1,P2∈{k×glaNumMax}，其中k=1,2,…,colMax-1，且P1≠P2。

步驟3將父代染色體F1中第[1,P1]、[P2+1,gn]之間的基因復(fù)制到子代染色體O1的對(duì)應(yīng)位置，其中g(shù)n為染色體包含的基因總數(shù)。

步驟4將父代染色體F2中第[P1+1,P2]之間的基因復(fù)制到染色體O1的對(duì)應(yīng)位置，獲得子代染色體O1。

步驟5將F1和F2的位置交換，同理，可以得到后代O2。

如圖5所示，對(duì)父代F1、F2執(zhí)行交叉操作，選擇交叉點(diǎn)P1=4,P2=8，按照以上方式執(zhí)行交叉操作，得到子代O1、O2。

圖5 染色體交叉示例

4.7 變異算子

為避免搜索過(guò)程過(guò)早地陷入局部最優(yōu)，變異算子隨機(jī)選擇部分染色體的部分基因進(jìn)行變異，具體步驟如下：

步驟1依據(jù)變異概率Pm和變異臨時(shí)隨機(jī)數(shù)Pmt的大小關(guān)系判斷是否對(duì)該個(gè)體進(jìn)行變異，若Pmt≤Pm(Pmt,Pm∈[0,1])成立，則對(duì)該個(gè)體進(jìn)行變異操作，否則，不進(jìn)行變異操作。

步驟2隨機(jī)選擇排放在玻璃原板的第k(k=1,2,…,colMax)列的所有玻璃原片進(jìn)行變異，即選擇染色體在區(qū)間[glaNumMax×(k-1)+1,k×glaNumMax]之間的基因進(jìn)行變異。

步驟3隨機(jī)生成一組可行的列訂單組合替換排放在第k列的訂單規(guī)格，得到變異后的染色體。一個(gè)可行列訂單組合的生成步驟為：從切割訂單中隨機(jī)選擇一個(gè)玻璃規(guī)格編號(hào)firstp，排放在第1個(gè)位置；在切割訂單中尋找和firstp等長(zhǎng)的所有玻璃規(guī)格的編號(hào)，存放在集合eql中；在等長(zhǎng)訂單規(guī)格集合eql中隨機(jī)選擇訂單規(guī)格編號(hào)，排放在第[2,glaNumMax]個(gè)位置。

為避免種群收縮于局部最優(yōu)解，又使種群進(jìn)化保持一定的連續(xù)性，在進(jìn)化過(guò)程中采用動(dòng)態(tài)變異率。在進(jìn)化的初級(jí)階段，采用較高的變異率，使種群具有足夠的突變性，避免收斂到局部最優(yōu)解，而隨著進(jìn)化代數(shù)的提高，降低種群的變異率，避免種群無(wú)序化，使其在較優(yōu)情況下向著最優(yōu)解靠攏。取第t代個(gè)體的變異率Pm,t=N/(N+t)×Pm，其中Pm為最初設(shè)定的變異率，N為開(kāi)始階段設(shè)定的最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)。

4.8 精英保留策略

為加快算法的收斂速度，防止進(jìn)化結(jié)果停滯不前或發(fā)生隨機(jī)漫游現(xiàn)象，采用最優(yōu)保留策略，即從本代染色體中選擇適應(yīng)度值最高的染色體中的一個(gè)，來(lái)取代子代染色體中適應(yīng)度值最低的染色體中的一個(gè)。

4.9 算法整體流程

設(shè)P(t)為第t代種群，算法整體流程如下：

步驟1輸入相關(guān)參數(shù)。輸入浮法玻璃切割相關(guān)參數(shù)，即種群規(guī)模N(p)，交叉概率Pc，變異概率Pm，最大迭代次數(shù)N。

步驟2初始化種群。令t=0，產(chǎn)生個(gè)體數(shù)為N(p)的初始種群P(0)。

步驟3計(jì)算適應(yīng)度函數(shù)值。根據(jù)缺陷分級(jí)參數(shù)、玻璃分級(jí)參數(shù)判定每塊玻璃原片的質(zhì)量等級(jí)，判定其單位面積的價(jià)格，進(jìn)而計(jì)算第t代種群P(t)中每個(gè)個(gè)體的適應(yīng)度函數(shù)值。

步驟4選擇操作。采用隨機(jī)按比例的方式，從P(t)中選擇N(p)個(gè)個(gè)體復(fù)制到P(t+1)中。

步驟5交叉操作。依據(jù)交叉臨時(shí)隨機(jī)數(shù)Pct和交叉概率Pc的大小關(guān)系，Pct、Pc∈[0,1]，從選擇操作所得種群中隨機(jī)選擇一對(duì)臨時(shí)父代進(jìn)行交叉，共進(jìn)行N(p)/2次，產(chǎn)生N(p)個(gè)后代形成的臨時(shí)種群。

步驟6變異操作。對(duì)于交叉操作產(chǎn)生的臨時(shí)種群，依據(jù)變異臨時(shí)隨機(jī)數(shù)Pmt和當(dāng)代變異概率Pm,t的大小關(guān)系，對(duì)個(gè)體進(jìn)行變異操作，產(chǎn)生N(p)個(gè)后代形成新的后代種群。

步驟7最優(yōu)保留策略。用P(t)中適應(yīng)度函數(shù)值最大的一個(gè)個(gè)體取代P(t+1)中適應(yīng)度函數(shù)值最小的一個(gè)個(gè)體。

步驟8令t=t+1，判斷是否達(dá)到最大迭代次數(shù)，即若t=N，輸出計(jì)算結(jié)果，結(jié)束程序；否則，轉(zhuǎn)步驟3。

5 實(shí)例分析

5.1 實(shí)例說(shuō)明

現(xiàn)有一塊長(zhǎng)12200 mm、寬4000 mm的浮法玻璃原板，經(jīng)檢測(cè)，該玻璃板面上共含有40個(gè)缺陷點(diǎn)，表2為各缺陷點(diǎn)的詳細(xì)信息。已知缺陷等級(jí)參數(shù)DC={0.5,1.0,1.5,3,5}，玻璃分級(jí)參數(shù)QC={M1,M2,M3}，各等級(jí)玻璃單位面積的價(jià)格依次為11.2 元/m2，10.5 元/m2，9.6 元/m2，0元/m2，在該玻璃原板上切割表1所示訂單規(guī)格，要求盡可能使獲得的玻璃成品總價(jià)格最高。

表2 缺陷信息

表3 實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)

玻璃分級(jí)參數(shù)QC中M1、M2、M3的取值如下：

5.2 求解結(jié)果與分析

采用本文提出的改進(jìn)遺傳算法解決上述算例。令種群規(guī)模N(p)=10，迭代次數(shù)N=50，染色體交叉概率Pc=0.8，變異概率Pm=0.2。對(duì)遺傳算法而言，其優(yōu)化結(jié)果并不是唯一、確定的，因此針對(duì)以上浮法玻璃切割問(wèn)題，將該遺傳算法運(yùn)行10次，計(jì)算結(jié)果見(jiàn)表3。

根據(jù)表3所示實(shí)驗(yàn)結(jié)果，可得出以下結(jié)論：

（1）對(duì)浮法玻璃優(yōu)化切割問(wèn)題而言，切割獲得的玻璃成品塊數(shù)越多，玻璃成品總價(jià)不一定最大。如：第1次和第2次實(shí)驗(yàn)均獲得12塊玻璃成品，但其玻璃成品的總價(jià)格均不是最大。

（2）切割獲得的玻璃成品總面積最大，玻璃成品總價(jià)不一定最大。如：第6次實(shí)驗(yàn)獲得的玻璃成品總面積最大，但其玻璃成品總價(jià)并不是最大。

（3）玻璃成品的總價(jià)是由玻璃成品面積和玻璃質(zhì)量等級(jí)共同決定的。如：第7次實(shí)驗(yàn)獲得10塊玻璃成品，玻璃成品總面積為39.7788 m2，但其所得玻璃成品總價(jià)最大，是上述實(shí)驗(yàn)中的最佳方案。

以上10次實(shí)驗(yàn)中，第7次實(shí)驗(yàn)獲得的玻璃成品總價(jià)最大，將該次實(shí)驗(yàn)對(duì)應(yīng)的切割方案作為上述實(shí)例的最終切割方案，圖6為最終切割方案的示意圖。

圖6 玻璃原板缺陷信息及切割方案圖示

5.3 算法性能比較

針對(duì)浮法玻璃優(yōu)化切割問(wèn)題，以玻璃成品總價(jià)格最大為優(yōu)化目標(biāo)，本文還提出了一種基于局部遍歷的啟發(fā)式搜索算法，該算法在保證排放在每個(gè)位置上的玻璃原片的質(zhì)量等級(jí)最高的基礎(chǔ)上，使其面積盡可能大，以保證排放每個(gè)位置的玻璃原片的價(jià)格最大。針對(duì)表4中6組不同的切割訂單，將其優(yōu)化結(jié)果與改進(jìn)遺傳算法進(jìn)行比較。

由表5可知，和隨機(jī)啟發(fā)式算法相比，本文提出的改進(jìn)遺傳算法具有更好的性能，且針對(duì)一個(gè)確定切割訂單和玻璃原板，隨機(jī)啟發(fā)式算法只能找到一組解決方案，而遺傳算法每次運(yùn)算可以獲得最優(yōu)解對(duì)應(yīng)的多個(gè)解決方案，可以為規(guī)劃人員提供多種選擇。

表4 切割訂單

表5 算法優(yōu)化性能對(duì)比

6 結(jié)束語(yǔ)

本文針對(duì)浮法玻璃切割問(wèn)題，根據(jù)缺陷分級(jí)參數(shù)和玻璃分級(jí)參數(shù)對(duì)玻璃原片的質(zhì)量等級(jí)進(jìn)行判定，進(jìn)而獲得玻璃原片的價(jià)格，以玻璃成品總價(jià)最大為優(yōu)化目標(biāo)，建立該問(wèn)題的數(shù)學(xué)模型，提出了一種基于玻璃原片排放位置編碼的遺傳算法。對(duì)算法的各個(gè)模塊進(jìn)行了設(shè)計(jì)，并以實(shí)例驗(yàn)證了所建模型的正確性及算法的有效性。實(shí)驗(yàn)結(jié)果表明：浮法玻璃的成品總價(jià)格是由玻璃成品面積和玻璃質(zhì)量等級(jí)共同決定的，僅追求玻璃利用率最高或玻璃質(zhì)量等級(jí)最高，均不能滿足生產(chǎn)利益最大化的要求。本文提出的遺傳算法，在一定程度上能夠提高玻璃成品的銷(xiāo)售價(jià)格，具有較好的性能。