張世龍，趙罘，薛美榮，李娜

（北京工商大學(xué)材料與機(jī)械工程學(xué)院，北京　100048）

基于遺傳算法的煙草輸送機(jī)振槽排樣優(yōu)化算法

張世龍，趙罘，薛美榮，李娜

（北京工商大學(xué)材料與機(jī)械工程學(xué)院，北京100048）

針對(duì)煙草輸送機(jī)振槽加工材料浪費(fèi)率高的問(wèn)題，提出了遺傳算法對(duì)其進(jìn)行優(yōu)化排樣。確定了適用于排樣優(yōu)化的編碼方式，編寫了選擇算子，交叉算子及變異算子，在Matlab上編寫程序并得到實(shí)現(xiàn)。實(shí)例測(cè)試結(jié)果表明通過(guò)遺傳算法對(duì)其進(jìn)行優(yōu)化排樣可有效提升材料利用率。

振槽；遺傳算法；排樣優(yōu)化

0　引言

在煙草生產(chǎn)過(guò)程中，煙草輸送一般都是通過(guò)輸送機(jī)帶動(dòng)振槽進(jìn)行往復(fù)振動(dòng)，從而使得煙草在振槽中進(jìn)行前進(jìn)運(yùn)動(dòng)。由于需要長(zhǎng)期進(jìn)行往復(fù)振動(dòng)，所以振槽比較容易損壞。為了保證穩(wěn)定生產(chǎn)，需要定期更換振槽。由于煙草輸送線比較長(zhǎng)，所以振槽也相應(yīng)比較長(zhǎng)，在生產(chǎn)振槽過(guò)程中，往往是用多條小矩形母材加以焊接拼接而成。

然而目前多數(shù)企業(yè)在實(shí)際生產(chǎn)中仍是根據(jù)目測(cè)和經(jīng)驗(yàn)，采用手工進(jìn)行排樣。排樣工人預(yù)先用一些材料做出零件模型，當(dāng)需要在板料上加工某些零件時(shí)，把這些零件的模型盡可能緊密地放在板料上，沿模型的輪廓把形狀畫出來(lái)，然后再進(jìn)行切割。排樣工人通過(guò)反復(fù)排放、比較來(lái)尋求較好的排放方案，勞動(dòng)強(qiáng)度高、工作量大且效率和材料利用率都較低。故本文旨在基于遺傳算法提出一個(gè)有效的求解輸送機(jī)振槽排樣問(wèn)題的方法，以期提高材料的利用率。

1　遺傳算法

1975年，J.H.Holland教授受生物學(xué)中“生物進(jìn)化”和“自然選擇”學(xué)說(shuō)的啟發(fā)，提出了著名的遺傳算法。遺傳算法可看成一種全局?jǐn)?shù)值優(yōu)化，它模擬基因重組與進(jìn)化的自然過(guò)程，把待解問(wèn)題的參數(shù)編成二進(jìn)制碼，稱為“基因”，若干基因組成一個(gè)“染色體”。許多染色體進(jìn)行類似于自然選擇、雜交和變異的運(yùn)算，經(jīng)過(guò)多次重復(fù)運(yùn)算（即世代遺傳），直至得到最后的優(yōu)化結(jié)果［1］。圖1是遺傳算法的基本流程圖。

1.1數(shù)學(xué)模型

設(shè)振槽展開后矩形的長(zhǎng)為L(zhǎng)，寬為W。有K種矩形母材，其中長(zhǎng)、寬分別為li、wi，即可橫放也可豎放，如圖2所示。

圖1　遺傳算法的基本流程圖Fig.1 Basic flow figure of genetic algorithm

圖2　數(shù)學(xué)模型圖Fig.2 Figure of mathematical model

為了使得只在一個(gè)方向上有焊縫，需要所使用母材在寬度方向比目標(biāo)振槽寬度寬，然后一條一條通過(guò)焊接得到最終振槽矩形。因此在縱向方向只能排放一行母材，一行上的母材只能被橫放或豎放，假設(shè)板材的數(shù)量總是足夠的。我們用yi表示橫放時(shí)的零件個(gè)數(shù)，xi表示豎放時(shí)的零件個(gè)數(shù)。目標(biāo)函數(shù)：

這是一個(gè)多維有約束離散優(yōu)化問(wèn)題。其已知參數(shù)為W、L、wi、li，未知參數(shù)為xi、yi。用傳統(tǒng)優(yōu)化方法很難找到有效的算法對(duì)其求解。根據(jù)遺傳算法的特點(diǎn)，我們對(duì)這一問(wèn)題考慮了遺傳算法的可行性。為了使問(wèn)題簡(jiǎn)單化，將一個(gè)矩形件（li，wi）看成（li，wi）和（wi，li）兩種不同的矩形件考慮。這樣，上面的數(shù)學(xué)模型變?yōu)橐韵滦问?。目?biāo)函數(shù)：

1.2遺傳算法模型

（1）編碼。染色體編碼是指將矩形件排樣問(wèn)題的可行解從其解空間轉(zhuǎn)換到遺傳算法能夠處理的搜索空間的解。在遺傳算法中，用染色體表示問(wèn)題的一個(gè)可能解，其編碼方式通常有二進(jìn)制編碼、實(shí)數(shù)編碼和符號(hào)編碼等［2］?；趩?wèn)題特點(diǎn)，此處采用十進(jìn)制編碼方式：每個(gè)矩形件的編號(hào)作為染色體（問(wèn)題解）的一個(gè)基因，所有矩形件編號(hào)所構(gòu)成的序列代表各矩形件的排樣順序，這樣的一個(gè)序列就是一個(gè)染色體。

（2）選擇算子。選擇算子是為了避免有效基因的損失，使高性能的個(gè)體得以更大的概率生存，從而提高全局收斂性和計(jì)算效率。選擇算子采用輪盤賭選擇法［3］，具體過(guò)程為：①對(duì)種群中每個(gè)個(gè)體預(yù)排樣，求出每個(gè)個(gè)體的適應(yīng)度值，再求出所有個(gè)體的適應(yīng)度值總和；②求出每個(gè)個(gè)體的相對(duì)適應(yīng)度，也就是被選中概率，pi=Fi/Fsum。其中pi表示第i個(gè)個(gè)體被選中概率；Fi表示第i個(gè)個(gè)體的適應(yīng)度值；Fsum表示所有個(gè)體的適應(yīng)度值之和；③求出每個(gè)個(gè)體的的累積選擇概率；④產(chǎn)生一個(gè)隨機(jī)數(shù)rand=［0，1］。若rand＜qi，第一個(gè)個(gè)體被選中，否則第i個(gè)個(gè)體被選中，使qi-1＜rand＜qi成立。重復(fù)該操作，直到選擇的個(gè)體數(shù)等于初始種群的個(gè)體總數(shù)。

（3）交叉算子。交叉算子在遺傳算法中起著關(guān)鍵的作用，通過(guò)交叉可產(chǎn)生新的個(gè)體。常用的交叉算子有單點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉等［4］。

設(shè)定交叉操作算子的方法如下：在染色體上選擇一個(gè)位置作為交叉位置，交叉位置之前的基因片段不交叉，交叉位置之后的片段交叉。比較兩個(gè)參與交叉的染色體，將交叉位置之前的相同基因去除，將交叉位置之前的剩余基因順序不變的存入數(shù)組p［］和q［］中。然后對(duì)染色體的交叉部分進(jìn)行交叉，若交叉部分的基因不等于這兩個(gè)數(shù)組中基因，則直接交換；若與數(shù)組中的基因相同，則先把相同基因換成數(shù)組p［］或q［］中對(duì)應(yīng)基因之后再交換。

（4）變異算子。變異算子是將染色體中的某些基因位上的基因值加以改變，從而產(chǎn)生一個(gè)新的個(gè)體。變異算子一方面可以使遺傳算法具有局部的隨機(jī)搜索能力，另一方面有助于遺傳算法維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象［5］。

（5）停止準(zhǔn)則。遺傳算法收斂判斷準(zhǔn)則較多，比較常見的是根據(jù)迭代次數(shù)以及解的質(zhì)量來(lái)判斷。迭代次數(shù)是表示遺傳算法運(yùn)行終止條件的一個(gè)主要參數(shù)，它表示遺傳算法運(yùn)行到規(guī)定的進(jìn)化代數(shù)之后就停止運(yùn)行，并將當(dāng)前群體中的最佳個(gè)體作為所求問(wèn)題的最優(yōu)解輸出。

2　振槽排樣優(yōu)化實(shí)例及分析

本文通過(guò)上述的遺傳算法編制了計(jì)算程序，并在Matlab上進(jìn)行了實(shí)現(xiàn)。在實(shí)驗(yàn)中取群體規(guī)模N=40，交叉概率Pr=0.7，變異概率Pm=0.05或0.15。企業(yè)現(xiàn)用的母材數(shù)據(jù)如表1所示。

表1　矩形件信息Tab.1 Rectangular parts information

共有4種母材，每種母材的數(shù)量都是一定的，現(xiàn)在要加工一個(gè)輸送機(jī)振槽，振槽展開后矩形的長(zhǎng)為16000mm，寬為1200mm。為了得到這個(gè)振槽，在Matlab上通過(guò)500代的迭代計(jì)算，當(dāng)變異概率為0.05時(shí)，得到排樣的材料利用率為96.69%，當(dāng)變異概率為0.15時(shí)，得到排樣的材料利用率為97.65%。

可見本文提出的排樣算法在提高板材利用率方面有一定的優(yōu)越性。

3　結(jié)論

本文用遺傳算法來(lái)求解煙草輸送機(jī)振槽的排樣問(wèn)題，可有效解決振槽在加工生產(chǎn)中浪費(fèi)材料和費(fèi)時(shí)、費(fèi)工的問(wèn)題。

到目前為止，對(duì)優(yōu)化排樣問(wèn)題的研究，無(wú)論是一維、二維還是三維，帶約束或不帶約束，都沒(méi)有出現(xiàn)針對(duì)這一問(wèn)題的系統(tǒng)化解決方案。由于問(wèn)題的多樣性，大多數(shù)研究都只是停留在對(duì)某些算法的部分改進(jìn)，以適應(yīng)各自的問(wèn)題，假如能夠建立一套完整的排樣理論體系，必將大大推進(jìn)排樣問(wèn)題的研究，減少重復(fù)性工作。

［1］曹炬，周濟(jì).矩形件排樣優(yōu)化的一種近似算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2009，3.

［2］劉德全，滕弘飛.矩形件排樣問(wèn)題的遺傳算法求解［J］.小型微型計(jì)算機(jī)系統(tǒng)，1998，12.

［3］趙新芳，崔耀東，徐瑩.矩形件帶排樣的一種遺傳算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2008，4.

［4］減輝.遺傳算法及其應(yīng)用［J］.武漢科技學(xué)院學(xué)報(bào)，2005，4.

［5］葉軍君，殷國(guó)富.板材下料優(yōu)化排樣CAD系統(tǒng)的研究［J］.現(xiàn)代制造工程，2004，10.

Optimization Algorithm for Vibration Slot of Tobacco Vibrating Conveyor Based on Genetic Algorithm

ZHANG Shi-Long，ZHAO Fu，XUE Mei-Rong，LI Na
（School of Materias and Mechanical Engineering，Beijing Technology and Business University，Beijing 100048，China）

Aiming at the problem of high wastage rate of vibration slot processing material in tobacco conveyer，the genetic algorithm was proposed to optimize the layout.Encoder mode of layout optimization was determined.The selection operator，crossover operator and mutation operator were designed，and the program was written in Matlab.The test results of the examples show that the method can effectively improve the utilization of materials by the genetic algorithm.

vibration slot；genetic algorithm；layout optimization

TH122

A

10.3969/j.issn.1002-6673.2015.06.014

1002-6673（2015）06-040-03

2015-09-10

項(xiàng)目來(lái)源：北京工商大學(xué)研究生科研能力提升計(jì)劃項(xiàng)目資助（2015）

張世龍（1991-），男，河南信陽(yáng)人，研究生。主要研究方向：機(jī)械設(shè)計(jì)及理論；通訊作者：趙罘（1972-），男，吉林長(zhǎng)春人，副教授。