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

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

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

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

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

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

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

2 浮法玻璃優(yōu)化切割問題簡介

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

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

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

表1 切割訂單

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

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

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

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

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

該問題中各變量及其符號表示如下：

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

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

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

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

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

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

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

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

圖3 可行切割方案示例

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

4 算法設(shè)計

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

4.1 編碼

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

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

圖4 染色體編碼示例

4.2 解碼

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

4.3 種群初始化

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

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

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

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

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

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

步驟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。

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

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

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

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

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

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

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

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

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

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

4.5 選擇算子

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

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

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

4.6 交叉算子

為保證交叉后染色體的可行性，本文針對浮法玻璃切割問題的特點，提出了一種兩點交叉法。

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

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

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

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

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

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

圖5 染色體交叉示例

4.7 變異算子

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

步驟1依據(jù)變異概率Pm和變異臨時隨機(jī)數(shù)Pmt的大小關(guān)系判斷是否對該個體進(jìn)行變異，若Pmt≤Pm(Pmt,Pm∈[0,1])成立，則對該個體進(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ī)格，得到變異后的染色體。一個可行列訂單組合的生成步驟為：從切割訂單中隨機(jī)選擇一個玻璃規(guī)格編號firstp，排放在第1個位置；在切割訂單中尋找和firstp等長的所有玻璃規(guī)格的編號，存放在集合eql中；在等長訂單規(guī)格集合eql中隨機(jī)選擇訂單規(guī)格編號，排放在第[2,glaNumMax]個位置。

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

4.8 精英保留策略

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

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)生個體數(shù)為N(p)的初始種群P(0)。

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

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

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

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

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

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

5 實例分析

5.1 實例說明

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

表2 缺陷信息

表3 實驗結(jié)果統(tǒng)計

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

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

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

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

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

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

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

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

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

5.3 算法性能比較

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

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

表4 切割訂單

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

6 結(jié)束語

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