藥品紙質包裝盒智能排樣算法研究

楊志軍 趙一臨 鄭哲 李方娟

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

關鍵詞：遺傳算法;掃描定位算法;紙盒;排樣;智能

中圖分類號：TP301.6? ? ? ?文獻標識碼：A文章編號：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? 引? 言

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

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

1? 紙盒排樣數學模型建立

不規則多邊形的優化排樣系指把多個不規則的平面幾何圖形[1，2，…，n]放置于一個固定的長為a，寬為b的板材中（a≥b），通過尋找不同的擺放順序實現板材利用率最大化，即通過尋找一個近似最優的排樣順序，使排樣后的板料浪費量最少，從而達到節省材料的目的。本文針對多個二維不規則待排樣件在同一樣板中的排樣建立數學模型。

約束條件為：

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

（2）e、f∈R;

（3）使用貪心旋轉算法在各個角度進行試探性擺放，取最優適應角度后，在擺放過程中應用BL思想。

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

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

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

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

2? 排樣問題的求解

2.1? 多邊形掃描定位法

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

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

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

Step1：計算水平直線與零件各邊的交點;

Step2：對得到的交點進行判斷，決定取舍，若與零件的交點為局部極值點，算作兩個交點;其余算作一個交點;

Step3：將得到的交點按遞增順序排序;

Step4：對于得到的交點，從第一個和第二個開始兩兩進行配對。

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

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

2.1.2? 算法過程

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

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

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

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

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

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

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

在掃描算法開始前，應用貪心旋轉算法尋求最優適應角度，之后進行零件的判交和定位，此算法設計流程圖如圖3所示。

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

2.2? 改進的遺傳算法優化排樣策略

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

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

（2）確定計算中的基本參數，如種群規模、計算執行最大代數、交叉概率、變異概率、最優秀個體的判定區間。

求解二維不規則排樣問題時，所追求的目標是實現原材料利用率的最大化。由（1）可知，函數F（x）值越小，板材利用率越高，為使計算更加簡便，本文定義適應度函數為：

故紙盒二維排樣問題可歸納為求maxG（X），適應度函數越大，排樣次序越優。

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

（3）計算停止執行的條件通常是，算法到達最大代數或者已經取得所期望的最優解。

本文應用遺傳算法對多邊形掃描算法進行優化計算，使得算法計算的繁簡與零件的幾何復雜度無關，從而縮短了判交和定位零件所消耗的時間，在一定程度上降低了計算復雜度。該算法流程如圖4所示。

3? 實例驗證

對遺傳算法優化的多邊形掃描定位算法使用Java語言進行程序實現。以30個不同類型的藥品紙質包裝盒的排樣為例進行驗證，排樣紙盒的數量和相應尺寸如表1所示。

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

第一代種群的最優排樣利用率為54.93%，第一百代種群的最優排樣利用率為80.71%，算法執行時間為55 s。結果表明，本文算法與傳統遺傳算法相比，材料利用率提高了5%左右，算法執行時間明顯降低，排樣達到了預期效果。

4? 結? 論

通過多邊形掃描定位算法與遺傳算法的結合來解決不規則零件的排樣問題滿足了實際生產的需要，具有求解穩定、排樣速度快、自動化程度高等優點。由于排樣問題是復雜的組合優化問題，任何單一的算法都無法取得最優解，而通過多邊形掃描定位算法與遺傳算法相結合進行排樣，取得了更加顯著的排樣效果。實例驗證結果表明，它不僅大大提高了材料利用率，而且縮短了運算時間，將多邊形掃描定位法與遺傳算法相結合進行排樣計算具有很好的應用前景，是目前藥品中紙質包裝盒排樣問題研究的一個主要方向。

參考文獻：

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

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

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

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

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

[6] 張立馳，李健.優化排樣問題研究及其發展 [J].制造業自動化，2010，32（5）：95-96+196.

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