藥品紙質(zhì)包裝盒智能排樣算法研究

楊志軍 趙一臨 鄭哲 李方娟

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

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

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

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

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

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

約束條件為：

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

（2）e、f∈R;

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

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

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

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

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

2? 排樣問題的求解

2.1? 多邊形掃描定位法

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

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

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

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

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

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

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

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

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

2.1.2? 算法過程

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

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

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

Step3：對于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方向上超過了矩形包圍盒范圍，則y=x+1，x=0，重新進(jìn)行Step1;

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

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

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

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

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

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

（1）確定編碼方案。對于包含n個(gè)待排放零件的排樣問題，可行解是由n個(gè)對象組成的序列，序列中的每個(gè)零件對象都包含排放順序和旋轉(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ī)則排樣問題時(shí)，所追求的目標(biāo)是實(shí)現(xiàn)原材料利用率的最大化。由（1）可知，函數(shù)F（x）值越小，板材利用率越高，為使計(jì)算更加簡便，本文定義適應(yīng)度函數(shù)為：

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

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

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

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

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

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

本文實(shí)例設(shè)置種群數(shù)量為30，最大迭代次數(shù)為50次，交叉概率Pc=0.95，變異概率Pm=0.45，采用市場上較為常見的三種藥品包裝盒——對插嵌套式、旋轉(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é)? 論

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

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

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