基于遺傳算法的多頭組合秤稱重優化

丁威濤，蘇宇鋒

（鄭州大學機械與動力工程學院，河南 鄭州 450001）

1 引言

近年來，食品工業對中小定量包裝的需求越來越大。傳統的單頭包裝秤存在稱重精度不高、包裝速度慢、抗干擾能力差等弊病，特別是在稱量形狀不規則、單體重量不平均的物料如速凍水餃、湯圓時，稱量的誤差較大，導致產品不合格率升高。多頭組合秤非常適用于稱量各種不規則形狀和單體重量不平均又需定量稱重的物品，具有精確度高、可靠性強、抗干擾能力強等優勢［1］。多頭組合秤的應用不但降低企業人力成本，還明顯提高產品生產效率，增加了企業的經濟效益。

目前，用于多頭組合秤的算法有窮舉法和動態規劃法。窮舉法是列舉出所有組合的可能性，從所有列舉出的組合中選取最優解的方法。當組合秤有n個稱重斗時，一共就有2n種組合的方式。窮舉法要求把所有的組合方式都列舉和存儲起來，雖然這種方法的準確性很高，但每一次都要列舉和存儲所有的組合結果，這勢必會造成內存資源的浪費，因此這種算法只適合小規模組合。

動態規劃算法依據最優子結構和狀態轉移方程能很好的實現組合問題，但動態規劃算法的輸入只能是整數［2］，這與實際稱重傳感器的精度相差很大，降低了組合的精度。傳統算法雖然算法原理簡潔、求解方法簡單，但只適合于小規模組合問題，對于復雜問題會花費大量的時間，特別在處理多目標函數問題時，往往都得不到滿意的結果。

2 多頭組合秤稱重原理分析

多頭組合秤主要包括儲料槽、線振盤、進料斗、稱重斗，稱重傳感器和集料槽等［3］，有的高檔組合秤還有記憶斗，如圖1所示。

圖1 多頭組合秤結構圖Fig.1 Structure Diagram of Multi-Head Combination Weigher

儲料槽中的物料在線振盤的振動作用下均勻的散落到各個進料斗中，進料斗每隔固定的時間把一定量的物料輸送到稱重斗中，稱重斗中的稱重傳感器對物料進行稱量，得到的物料重量經由電腦組合配重選擇出最接近目標重量的稱重斗組合，被選中的稱重斗將物料送到集料槽中，進料斗再為空缺的稱重斗補料，依次循環組合。擁有記憶斗的組合秤，稱重斗會把稱量好的物料先送到記憶斗中，在電腦組合配重時是記憶斗和組合斗一起參與組合，因此擁有記憶斗的組合秤里稱重斗一般設置兩個出口，一個出個用于為記憶斗供料，另一個出口為集料槽供料，這里不考慮帶有記憶斗的組合秤。

3 多頭組合秤數學模型

多頭組合秤的配重問題是一個典型的組合優化問題。該問題可以簡單的描述為：一個由n個稱重斗組成的多頭組合秤，每一個稱重斗i（i=1，2，3，…，n）中都有獨立的重量ωi（i=1，2，3，…，n），選中其中的m（m≤n）個稱重斗式（4），組合出來的重量最接近給定的目標重量T的問題。該問題也是典型的0-1規劃問題：xi表示稱重斗被選中的狀態：xi=0表示第i個稱重斗沒有被選中；xi=1表示第i個稱重斗被選中，并且同一時間同一稱重斗只能滿足以上一種狀態。

食品行業的企業為了贏得消費者的青睞，往往在包裝食品的實際重量不會少于包裝袋上標注的重量，與此同時企業為了獲得最大的利潤也不希望實際重量超出標注重量太多，因此組合秤配重問題的第一個目標函數是要求配重在大于目標重量T的前提下最小式（1）、式（3）。這里研究的包裝物料是速凍水餃、速凍湯圓等不易長時間保存的食物，為了保障此類食物在配重時不會因為時間過長融化影響食物的品質，就要求物料在稱重斗中的時間不能過長，也就是稱重斗不能長時間不被選中，這里針對此問題引進優先級θi=A-λi+ 1（i=1，2，3，…，n）的概念，A表示總的組合次數，λi表示第i個稱重斗被選中時的組合次數，優先級θi越大表示第i個稱重斗未被選中的時間越長，這里要求每個稱重斗的優先級都不能太大，優先級越大的稱重斗越容易被選中，因此組合秤配重問題的第二個目標函數是要求選中的稱重斗的優先級之和最大式（2）［4-6］。數學模型入歸納下：

式中：xi—稱重斗被選中的狀態；ωi—稱重斗中的重量；θi—稱重斗的優先級；T—目標重量；m—被選中稱重斗的個數。

4 遺傳算法

就傳統算法所存在的問題，提出了基于遺傳算法的多頭組合秤程序設計，并針對種群在進化過程中出現的違反約束的個體提出了基于“重量優先”的修復方法。遺傳算法是一種抽象于生物進化過程的基于自然選擇和生物遺傳機制的優化技術，是一種高度并行、隨機性強和適應全局優化搜索的優化算法，其具有簡單通用、魯棒性強、易于并行處理以及高效、實用等顯著特點［7］。基于遺傳算法求解的步驟如下。

4.1 編碼

遺傳算法首先要對求解種群中個體進行編碼處理，常用的編碼方式有：二進制編碼，格雷碼編碼，浮點數編碼等。這里采用二進制編碼，個體編碼的長度為稱重斗的數量。設種群中有t個個體，種群編碼為X=｛X1，X2，X3，…，Xt｝，個體編碼Xa=｛x1，x2，x3，…，xn｝（1 ≤a≤t），xi（1 ≤i≤n）表示種群中第a個個體的第i個稱重斗選中狀態，xi=1表示第i個稱重斗被選中，xi=0表示第i個稱重斗未被選中。例如種群編碼Xa=｛1，0，0，1，0，0，0，1，1，0｝，表示組合秤有10個稱重斗，種群中第a個個體的第1、4、8和9個稱重斗被選中，其余的稱重斗未被選中［8］。

4.2 選擇操作

選擇操作是種群根據適應度函數值進化的過程，在進化的過程中生命力強（適應度值高）的個體被選擇到下一代的概率高，生命力弱（適應度值低）的個體被選擇到下一代的概率低。選擇操作是種群中個體進行優勝劣汰的過程，也是目標函數不斷接近最優解的過程。常用的選擇操作有：輪盤賭、隨機競爭、最佳保留等［9］。這里采用輪盤賭選擇操作，輪盤賭選擇操作是一種放回式隨機采樣方法，這種方式下的個體進入下一代的概率就等于它的適應度值與整個種群中個體適應度值之和的比例，比例越高，被選中的可能性就越大，進入下一代的概率就越大。這里把要求解的目標函數設置為種群的適應度函數。對于有兩個及兩個以上目標函數的問題稱為多目標函數問題。對于多目標函數的求解常用權重系數變換法、并列選擇法、排列選擇法等。這里采用并列選擇的方式求解多目標函數，首先將完整的種群平均分為兩個子種群，每個子種群隨機分配一個目標函數作為該種群的適應度函數，兩個子種群獨立的根據適應度函數值進行選擇操作，產生的新的子種群再合并為這一代的完整新種群，再將新種群進行交叉和變異操作，進而生成下一代完整的種群，如此的不斷“分割—并列選擇—合并”操作，最終可求出多目標化問題的Pareto最優解。

4.3 交叉和變異操作

交叉和變異操作是在遺傳算法中產生新的個體的主要方式，新個體增加了種群的多樣性，使算法有很好的全局搜索能力［9］。交叉操作也是遺傳算法區別其他算法的重要特征。這里的交叉和變異操作方法都是隨機生成法：交叉操作中要交叉個體和交叉位置都是隨機確定，隨機選出的兩個交叉個體在交叉位置被截斷，再分別和對應的個體進行交換；變異個體和變異位置也是隨機確定，隨機選出的變異個體的變異位置原來是0則變異為1，原來是1則變異為0。完全隨機的方式可以最大化的提高遺傳算法的全局搜索能力，保證遺傳算法能收斂于全局最優解。

4.4 修復操作

遺傳算法每次迭代的過程中，交叉操作和變異操作都會產生新的個體，這雖然增強了種群的多樣性，提高了算法的全局搜索能力，但也會產生違背原問題約束條件的個體，稱為不可行解［10］。對于不可行解的處理一般會采用罰函數法，通過罰函數把約束條件添加到目標函數當中，從而把有約束問題轉化為無約束問題求解。罰函數直接決定了目標函數的精確程度，但是罰函數的確定比較困難，這里提出了基于“重量優先”的修復策略來處理不可行解。所謂的“重量優先”是把不可行解中選中的稱重斗按重量大小遞增排序，未選中的稱重斗按重量大小遞減排序，進行修復操作時把兩個序列按序號交換直到滿足約束條件。被選中稱重斗的最小重量和未被選中稱重斗的最大重量進行交換使不可行解能最快滿足約束條件，減少運算時間。

4.5 遺傳算法的具體流程

遺傳算法的流程，如圖2所示。其中gen表示遺傳算法的迭代次數，MAXGEN表示遺傳算法的最大迭代次數。

圖2 遺傳算法流程圖Fig.2 Flow Chart of Genetic Algorithm

5 仿真

由文獻［11-12］研究可知，多頭組合秤下料的重量滿足正態分布的規律，其中多頭組合秤稱重斗總數越大，每個稱重斗中重量分布的標準差越小，組合合格的概率越大［12］。這里仿真選取10頭的組合秤，選取其中4 個稱重斗組合目標重量。這里研究的對象為速凍餃子、速凍湯圓，這些物料都由機器進行制作，每一個的重量差別不會特別大，一般每個重量在25g左右，考慮到包裝袋上的重量是整數，稱重傳感器的測量精確到小數點后一位即可，這里仿真物料的重量由滿足N～（25，2）的正態分布精度為小數點后一位的隨機數替代，目標重量設置為100g，遺傳算法中最大迭代次數MAXGEN=100，交叉操作的概率Ps=0.7，變異操作的概率Pm=0.2，每一代種群中個體數量設置為100個。考慮到產生隨機數的隨機性和不均勻性，本仿真的組合重量誤差小于1g就算合格。

仿真中遺傳算法組合一次的收斂情況，如圖3 所示。橫坐標表示種群的迭代次數，縱坐標是組合的最終組合得重量，圖中：實線—種群最小值的變化；虛線—種群平均值的變化。

圖3 遺傳算法收斂情況圖Fig.3 Convergence Graph of Genetic Algorithm

本仿真共設置4組，分別為組合100、500、1000和5000次，分別記錄下每組實驗的合格數、不合格數、最大優先級和總計算時間。根據合格數和不合格數可以得到組合成功率；根據最大優先級和總計算時間可以得出每組合所需時間和物料在稱重斗中存放的最長時間，具體組合結果，如表1所示。

表1 組合結果Tab.1 Result of Combination

6 結論

根據仿真數據可以知道，基于遺傳算法的多頭組合秤稱重算法收斂迅速平穩，組合合格概率大于98%，平均完成一次組合分析的時間小于0.15s，稱重斗的最大優先級控制在20以內，保證了物料在稱重斗中的時間不會高于10s。仿真數據表明，基于遺傳算法的多頭組合秤既能確保組合合格率也能保證物料的新鮮度，能很好的滿足組合要求。