丁威濤，蘇宇鋒

（鄭州大學(xué)機(jī)械與動(dòng)力工程學(xué)院，河南 鄭州 450001）

1 引言

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

目前，用于多頭組合秤的算法有窮舉法和動(dòng)態(tài)規(guī)劃法。窮舉法是列舉出所有組合的可能性，從所有列舉出的組合中選取最優(yōu)解的方法。當(dāng)組合秤有n個(gè)稱重斗時(shí)，一共就有2n種組合的方式。窮舉法要求把所有的組合方式都列舉和存儲(chǔ)起來，雖然這種方法的準(zhǔn)確性很高，但每一次都要列舉和存儲(chǔ)所有的組合結(jié)果，這勢(shì)必會(huì)造成內(nèi)存資源的浪費(fèi)，因此這種算法只適合小規(guī)模組合。

動(dòng)態(tài)規(guī)劃算法依據(jù)最優(yōu)子結(jié)構(gòu)和狀態(tài)轉(zhuǎn)移方程能很好的實(shí)現(xiàn)組合問題，但動(dòng)態(tài)規(guī)劃算法的輸入只能是整數(shù)［2］，這與實(shí)際稱重傳感器的精度相差很大，降低了組合的精度。傳統(tǒng)算法雖然算法原理簡(jiǎn)潔、求解方法簡(jiǎn)單，但只適合于小規(guī)模組合問題，對(duì)于復(fù)雜問題會(huì)花費(fèi)大量的時(shí)間，特別在處理多目標(biāo)函數(shù)問題時(shí)，往往都得不到滿意的結(jié)果。

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

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

圖1 多頭組合秤結(jié)構(gòu)圖Fig.1 Structure Diagram of Multi-Head Combination Weigher

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

3 多頭組合秤數(shù)學(xué)模型

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

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

式中：xi—稱重斗被選中的狀態(tài)；ωi—稱重斗中的重量；θi—稱重斗的優(yōu)先級(jí)；T—目標(biāo)重量；m—被選中稱重斗的個(gè)數(shù)。

4 遺傳算法

就傳統(tǒng)算法所存在的問題，提出了基于遺傳算法的多頭組合秤程序設(shè)計(jì)，并針對(duì)種群在進(jìn)化過程中出現(xiàn)的違反約束的個(gè)體提出了基于“重量?jī)?yōu)先”的修復(fù)方法。遺傳算法是一種抽象于生物進(jìn)化過程的基于自然選擇和生物遺傳機(jī)制的優(yōu)化技術(shù)，是一種高度并行、隨機(jī)性強(qiáng)和適應(yīng)全局優(yōu)化搜索的優(yōu)化算法，其具有簡(jiǎn)單通用、魯棒性強(qiáng)、易于并行處理以及高效、實(shí)用等顯著特點(diǎn)［7］?；谶z傳算法求解的步驟如下。

4.1 編碼

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

4.2 選擇操作

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

4.3 交叉和變異操作

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

4.4 修復(fù)操作

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

4.5 遺傳算法的具體流程

遺傳算法的流程，如圖2所示。其中g(shù)en表示遺傳算法的迭代次數(shù)，MAXGEN表示遺傳算法的最大迭代次數(shù)。

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

5 仿真

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

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

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

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

表1 組合結(jié)果Tab.1 Result of Combination

6 結(jié)論

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