楊志軍 趙一臨 鄭哲 李方娟

摘? 要：遺傳算法通過(guò)模擬自然進(jìn)化流程尋找最優(yōu)解，全局搜索力量較強(qiáng)。將其運(yùn)用于對(duì)藥品紙質(zhì)包裝盒的排樣環(huán)節(jié)，能夠取得非常好的效果。文章在多邊形掃描定位算法的基礎(chǔ)之上，采用遺傳算法進(jìn)一步優(yōu)化排樣，降低了計(jì)算復(fù)雜度，減少了算法運(yùn)行時(shí)間。實(shí)例分析表明，此算法在保證計(jì)算質(zhì)量的同時(shí)，計(jì)算復(fù)雜度明顯降低，適用于大規(guī)模藥品紙質(zhì)包裝盒的排樣。

關(guān)鍵詞：遺傳算法;掃描定位算法;紙盒;排樣;智能

中圖分類(lèi)號(hào)：TP301.6? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2096-4706（2021）22-0165-04

Abstract： Genetic algorithm seeks the optimal solution by simulating the natural evolution process， and has strong global search capabilities. It can achieve very good effect when it is applied to the layout of drug paper packaging boxes. Based on the polygon scanning and positioning algorithm， genetic algorithm is used to further optimize the layout， reduce the computational complexity and reduce the running time of the algorithm. The example analysis shows that this algorithm not only ensures the calculation quality， but also significantly reduces the calculation complexity. It is suitable for the layout of large-scale drug paper packaging boxes.

Keywords： genetic algorithm; scanning and positioning algorithm; paper packaging box; layout; intelligence

0? 引? 言

藥品紙質(zhì)包裝盒是藥品生產(chǎn)中一項(xiàng)重要的成本，需求量越來(lái)越大。近年來(lái)，中國(guó)現(xiàn)代包裝產(chǎn)業(yè)正逐步地向“綠色包裝”這一條節(jié)資環(huán)保的道路上前行，而增加紙板使用率也是現(xiàn)代包裝公司降低生產(chǎn)成本，增強(qiáng)產(chǎn)業(yè)競(jìng)爭(zhēng)力的主要手段。藥品紙質(zhì)包裝盒的平面展開(kāi)圖形都屬于不規(guī)則多邊形，紙盒的排樣問(wèn)題則屬于典型的NP問(wèn)題。隨著計(jì)算機(jī)科學(xué)技術(shù)的不斷發(fā)展，國(guó)內(nèi)外許多學(xué)者對(duì)紙質(zhì)包裝盒排樣問(wèn)題進(jìn)行了大量的研究。孫厚芳等人對(duì)各種型號(hào)沖裁件的預(yù)處理與智能排樣等過(guò)程展開(kāi)了深入研究，通過(guò)多邊形與頂點(diǎn)射線方法的運(yùn)用大大提高了加工材料的生產(chǎn)效率，同時(shí)也通過(guò)遺傳模擬與退火計(jì)算的融合解決了頂點(diǎn)算法計(jì)算量大、費(fèi)時(shí)多的問(wèn)題，為不規(guī)則零件的排樣優(yōu)化提出了可靠易行的方法。然而，由于紙盒平面展開(kāi)圖的幾何形狀十分復(fù)雜且數(shù)量很多，增加了計(jì)算的復(fù)雜性，造成算法收斂速度慢，排樣效率降低。如何改進(jìn)算法以降低計(jì)算復(fù)雜度，提高紙盒排樣效率（即提高材料利用率）是本文重點(diǎn)討論的問(wèn)題。

現(xiàn)代排樣算法在追求排樣最優(yōu)解的同時(shí)，往往忽略了時(shí)間因素。排樣計(jì)算過(guò)程中零件的判交和定位是比較耗時(shí)的工作，幾何圖形的復(fù)雜度是影響零件判交和定位的主要因素，本文在掃描定位算法的基礎(chǔ)上采用遺傳算法優(yōu)化計(jì)算，使得幾何復(fù)雜度并不會(huì)影響計(jì)算的繁簡(jiǎn)，從而簡(jiǎn)化運(yùn)算過(guò)程，提高紙盒排樣的效率。

1? 紙盒排樣數(shù)學(xué)模型建立

不規(guī)則多邊形的優(yōu)化排樣系指把多個(gè)不規(guī)則的平面幾何圖形[1，2，…，n]放置于一個(gè)固定的長(zhǎng)為a，寬為b的板材中（a≥b），通過(guò)尋找不同的擺放順序?qū)崿F(xiàn)板材利用率最大化，即通過(guò)尋找一個(gè)近似最優(yōu)的排樣順序，使排樣后的板料浪費(fèi)量最少，從而達(dá)到節(jié)省材料的目的。本文針對(duì)多個(gè)二維不規(guī)則待排樣件在同一樣板中的排樣建立數(shù)學(xué)模型。

約束條件為：

（1）e和f不能有重疊的部分，e∩f=?;

（2）e、f∈R;

（3）使用貪心旋轉(zhuǎn)算法在各個(gè)角度進(jìn)行試探性擺放，取最優(yōu)適應(yīng)角度后，在擺放過(guò)程中應(yīng)用BL思想。

e、f∈[1，n]為所有待排樣件中的某一個(gè)樣件;R為板材;條件（1）保證待排樣件兩兩之間不會(huì)重疊;條件（2）保證排樣完成后待排樣件位于板材內(nèi)。

板材的利用率可以用函數(shù)F（X）表示，每種排樣順序x，最高輪廓為f（x），如圖1所示。

f（x）下方面積表示排樣完成后所使用板材的面積，板材利用率可以表示為：

因此紙盒排樣問(wèn)題可以歸納為求minF（X）。函數(shù)F（X）的值越小，排列次序越優(yōu)，板材利用率越高。

2? 排樣問(wèn)題的求解

2.1? 多邊形掃描定位法

在紙盒排樣的計(jì)算中，零件的判交和定位是算法收斂速度的主要影響因素，而零件的判交和定位由于受幾何圖形不規(guī)則性的影響而增加了算法的復(fù)雜性。因此，有必要尋求一種簡(jiǎn)便的判交和定位方法來(lái)降低計(jì)算的復(fù)雜度。本文對(duì)文獻(xiàn)[2]中提出的多邊形掃描定位方法進(jìn)行改進(jìn)延伸，可有效地解決上述問(wèn)題。

2.1.1? 零件與樣板的幾何表示

對(duì)于零件H，將其旋轉(zhuǎn)α角度后，得到零件H（α），其在樣板平面坐標(biāo)系中橫縱坐標(biāo)的最大和最小值分別為Xmax、Xmin、Ymax、Ymin。系統(tǒng)使用0.5 mm的等間距水平直線掃描零件H（α）并計(jì)算掃描線與圖形的交點(diǎn)所得到的線段。對(duì)某一水平直線的計(jì)算步驟為：

Step1：計(jì)算水平直線與零件各邊的交點(diǎn);

Step2：對(duì)得到的交點(diǎn)進(jìn)行判斷，決定取舍，若與零件的交點(diǎn)為局部極值點(diǎn)，算作兩個(gè)交點(diǎn);其余算作一個(gè)交點(diǎn);

Step3：將得到的交點(diǎn)按遞增順序排序;

Step4：對(duì)于得到的交點(diǎn)，從第一個(gè)和第二個(gè)開(kāi)始兩兩進(jìn)行配對(duì)。

掃描最終圖形如圖2所示。

離散后得到的掃描線段實(shí)際上是由一對(duì)x坐標(biāo)（x1，x2）構(gòu)成的，只要判斷不同x值的大小，便可知是否重疊。

2.1.2? 算法過(guò)程

在零件的排樣次序和旋轉(zhuǎn)角度確定后，采用以下算法定位：

Step1：初始i=1，得到初始定位位置str（x，y）;

Step2：取H（α）上第i條掃描線，取樣板上第（y+i）條掃描線;

Step3：對(duì)于Step2中H（α）所得到的掃描區(qū)間[sx1，sx2]不斷更新，增加位移增量[sx1+x，sx2+x]。取Step2樣板掃描區(qū)間[px1，px2]，若其與[sx1+x，sx2+x]有重疊，則H（α）向右移動(dòng)△x=px2-（sx1+x）。將△x加入一個(gè)數(shù)組int[];

Step4：若P（α）在x方向上超過(guò)了矩形包圍盒范圍，則y=x+1，x=0，重新進(jìn)行Step1;

Step5：檢查int[]中元素的個(gè)數(shù)，若元素個(gè)數(shù)為0，則返回TRUE，表示H（α）可放在此區(qū)域，否則返回Step3中的最大值作為零件的offset值，同時(shí)返回FALSE，表示H（α）無(wú)法放到此區(qū)域，算法結(jié)束。

2.1.3? 多邊形掃描定位算法流程

在掃描算法開(kāi)始前，應(yīng)用貪心旋轉(zhuǎn)算法尋求最優(yōu)適應(yīng)角度，之后進(jìn)行零件的判交和定位，此算法設(shè)計(jì)流程圖如圖3所示。

此算法使用等距掃描線進(jìn)行排樣對(duì)象的表示，使其計(jì)算工作不受零件幾何復(fù)雜度的影響。同時(shí)基于BL思想，計(jì)算過(guò)程簡(jiǎn)潔，能有效利用樣板，獲得較高的排樣利用率。

2.2? 改進(jìn)的遺傳算法優(yōu)化排樣策略

遺傳算法優(yōu)化的排樣問(wèn)題也是一個(gè)多參數(shù)的優(yōu)化問(wèn)題。通過(guò)不斷變化的排列順序使排列計(jì)算實(shí)現(xiàn)近似最優(yōu)的估計(jì)求解，相較于其他計(jì)算，前者的全局搜索能力較強(qiáng)，從而減少陷入局部最優(yōu)估計(jì)求解的可能性。遺傳算法運(yùn)用達(dá)爾文的“優(yōu)勝劣汰，適者求生”原則，種群經(jīng)過(guò)交叉和變異之后，一部分個(gè)體被挑選出來(lái)繁衍下一代群體，此過(guò)程稱(chēng)為選擇過(guò)程。選擇過(guò)程是基于適應(yīng)度大小來(lái)完成優(yōu)勝劣汰的，適應(yīng)度高的個(gè)體更容易進(jìn)入下一代，適應(yīng)度低的個(gè)體則容易被淘汰，這樣更有利于優(yōu)良基因的擴(kuò)展。在排樣中通過(guò)人工方法對(duì)圖像進(jìn)行優(yōu)化排序，排列過(guò)程中需要關(guān)注以下三點(diǎn)：

（1）確定編碼方案。對(duì)于包含n個(gè)待排放零件的排樣問(wèn)題，可行解是由n個(gè)對(duì)象組成的序列，序列中的每個(gè)零件對(duì)象都包含排放順序和旋轉(zhuǎn)角度兩個(gè)變量。將待排放的n個(gè)零件按照排放順序編號(hào)，構(gòu)成一個(gè)整數(shù)序列{X1，X2，…，Xn}，Xi為第i個(gè)排入板材的多邊形零件編號(hào)，Oi為第i個(gè)零件排放時(shí)的旋轉(zhuǎn)角度，1≤Xi≤n。每個(gè)可行解序列可以表示為：{（X1，O1），（X2，O2），…，（Xn，On）}，其中（Xi，Oi）表示編號(hào)為Xi的零件旋轉(zhuǎn)Oi度后的排放。

（2）確定計(jì)算中的基本參數(shù)，如種群規(guī)模、計(jì)算執(zhí)行最大代數(shù)、交叉概率、變異概率、最優(yōu)秀個(gè)體的判定區(qū)間。

求解二維不規(guī)則排樣問(wèn)題時(shí)，所追求的目標(biāo)是實(shí)現(xiàn)原材料利用率的最大化。由（1）可知，函數(shù)F（x）值越小，板材利用率越高，為使計(jì)算更加簡(jiǎn)便，本文定義適應(yīng)度函數(shù)為：

故紙盒二維排樣問(wèn)題可歸納為求maxG（X），適應(yīng)度函數(shù)越大，排樣次序越優(yōu)。

通過(guò)初始父代種群的生成、選擇操作、交叉操作、變異操作、形成子代種群、演化迭代來(lái)尋求算法的最優(yōu)解。

（3）計(jì)算停止執(zhí)行的條件通常是，算法到達(dá)最大代數(shù)或者已經(jīng)取得所期望的最優(yōu)解。

本文應(yīng)用遺傳算法對(duì)多邊形掃描算法進(jìn)行優(yōu)化計(jì)算，使得算法計(jì)算的繁簡(jiǎn)與零件的幾何復(fù)雜度無(wú)關(guān)，從而縮短了判交和定位零件所消耗的時(shí)間，在一定程度上降低了計(jì)算復(fù)雜度。該算法流程如圖4所示。

3? 實(shí)例驗(yàn)證

對(duì)遺傳算法優(yōu)化的多邊形掃描定位算法使用Java語(yǔ)言進(jìn)行程序?qū)崿F(xiàn)。以30個(gè)不同類(lèi)型的藥品紙質(zhì)包裝盒的排樣為例進(jìn)行驗(yàn)證，排樣紙盒的數(shù)量和相應(yīng)尺寸如表1所示。

本文實(shí)例設(shè)置種群數(shù)量為30，最大迭代次數(shù)為50次，交叉概率Pc=0.95，變異概率Pm=0.45，采用市場(chǎng)上較為常見(jiàn)的三種藥品包裝盒——對(duì)插嵌套式、旋轉(zhuǎn)嵌套式、平鋪式——進(jìn)行排樣研究，排樣結(jié)果輸出圖如圖5所示。

第一代種群的最優(yōu)排樣利用率為54.93%，第一百代種群的最優(yōu)排樣利用率為80.71%，算法執(zhí)行時(shí)間為55 s。結(jié)果表明，本文算法與傳統(tǒng)遺傳算法相比，材料利用率提高了5%左右，算法執(zhí)行時(shí)間明顯降低，排樣達(dá)到了預(yù)期效果。

4? 結(jié)? 論

通過(guò)多邊形掃描定位算法與遺傳算法的結(jié)合來(lái)解決不規(guī)則零件的排樣問(wèn)題滿足了實(shí)際生產(chǎn)的需要，具有求解穩(wěn)定、排樣速度快、自動(dòng)化程度高等優(yōu)點(diǎn)。由于排樣問(wèn)題是復(fù)雜的組合優(yōu)化問(wèn)題，任何單一的算法都無(wú)法取得最優(yōu)解，而通過(guò)多邊形掃描定位算法與遺傳算法相結(jié)合進(jìn)行排樣，取得了更加顯著的排樣效果。實(shí)例驗(yàn)證結(jié)果表明，它不僅大大提高了材料利用率，而且縮短了運(yùn)算時(shí)間，將多邊形掃描定位法與遺傳算法相結(jié)合進(jìn)行排樣計(jì)算具有很好的應(yīng)用前景，是目前藥品中紙質(zhì)包裝盒排樣問(wèn)題研究的一個(gè)主要方向。

參考文獻(xiàn)：

[1] 雷賀功，孫厚芳，劉漢雄.遺傳模擬退火算法在沖裁件優(yōu)化排樣中的應(yīng)用 [J].現(xiàn)代制造工程，2004（6）：55-57.

[2] 李文學(xué).多約束二維排樣算法研究與應(yīng)用 [D].武漢：華中科技大學(xué)，2016.

[3] 宋亞男.鄧飛其，葉家瑋.基于改進(jìn)免疫遺傳算法的不規(guī)則圖形排樣 [J].計(jì)算機(jī)工程，2005（9）：170-172.

[4] 唐堅(jiān)剛，劉叢，張麗紅.基于改進(jìn)遺傳算法的不規(guī)則圖形排樣 [J].計(jì)算機(jī)工程，2010，36（21）：185-187.

[5] 王靜靜，瞿少成，李科林.一種基于并行交叉遺傳算法的二維不規(guī)則排樣問(wèn)題求解[J].計(jì)算機(jī)應(yīng)用與軟件，2020，37（7）：188-193.

[6] 張立馳，李健.優(yōu)化排樣問(wèn)題研究及其發(fā)展 [J].制造業(yè)自動(dòng)化，2010，32（5）：95-96+196.

作者簡(jiǎn)介：楊志軍（2000—），男，漢族，山西朔州人，本科在讀，研究方向：制藥工程與人工智能;鄭哲（2000—），男，漢族，浙江紹興人，本科在讀，研究方向：制藥工程與人工智能;趙一臨（2000—），女，滿族，云南紅河州人，本科在讀，研究方向：制藥工程與人工智能;通訊作者：李方娟（1978—），女，漢族，黑龍江綏化人，副教授，碩士，研究方向：制造技術(shù)與人工智能。