姜新波,李 珂,楊春梅
(東北林業(yè)大學 林業(yè)機械與木工工程技術中心,黑龍江 哈爾濱 150040)
木材作為四大原材料中唯一綠色可再生的資源而被廣泛應用,隨著我國造紙、人造板、實木地板和家具等行業(yè)的蓬勃發(fā)展,木材作為生產(chǎn)原材料其消耗量逐年遞增,然而我國林木資源相對匱乏,因此每年需進口大量原木和鋸材[1]。木材資源巨大的供需矛盾給我國木材加工企業(yè)帶來了挑戰(zhàn),推動木材加工向著自動化與智能化發(fā)展[2]。
伴隨著人工智能技術的不斷發(fā)展,為高效利用木材資源,各國學者逐漸將智能算法及理論融入到木材加工中:Urbonas等[3]將基于區(qū)域的快速卷積神經(jīng)網(wǎng)絡應用于鋸材表面缺陷識別,采用機器視覺代替人工目視檢測,快速準確地識別木材表面的節(jié)子、孔洞等缺陷。李海蕓等[4]為提高毛邊鋸材清邊效率,設計了基于視覺檢測的鋸材加工系統(tǒng),可實現(xiàn)毛邊鋸材的智能化清邊。張國梁等[5]采用分組降維的方法將大規(guī)模人造板鋸切問題轉(zhuǎn)化為每組不超過3種板材的組間排序問題,并采用懲罰函數(shù)與遺傳算法求解,減少了計算時間并提高了木材出材率;劉誠等[6]采用局部枚舉與貪心算法,通過改變局部枚舉規(guī)模并采用貪心策略,在較小空間內(nèi)得到高質(zhì)量人造板鋸切方案,降低了鋸切原料成本;Ying等[7]提出一種啟發(fā)式算法確定含單個缺陷木材鋸切方案,提高了木材加工效率;孫理越[8]對最低水平線算法進行改進,對含2個缺陷的矩形木材進行鋸切方案求解,算例測試表明出材率有8%以上提升。
從上述研究可以看出,將智能算法與木材加工相融合可更合理地使用木材。但以往研究對木材鋸切方案的求解主要針對人造板與含少量缺陷的木材,對含缺陷較多的毛邊鋸材鋸切方案求解研究較少。雖然國外先進木材加工企業(yè)如威力木工、豪邁等已研制出鋸材智能鋸切系統(tǒng),但大多已形成技術壟斷,國內(nèi)大型木工企業(yè)主要通過進口國外先進技術進行鋸材加工[9]。就目前而言,適合我國中小企業(yè)的鋸材智能鋸切系統(tǒng)相對較少,中小企業(yè)進行鋸材加工主要采用“人海戰(zhàn)術”,鋸材加工全部依賴工人主觀進行,無法針對缺陷眾多的鋸材快速準確地計算合理加工方案,造成木材原料大量浪費[10]。為解決此問題,對鋸材自動化鋸切進行研究和優(yōu)化以提高鋸材出材率是十分必要的。因此本研究通過分析毛邊鋸材下鋸方式構建了優(yōu)化下鋸模型,采用非支配排序與遺傳算法實現(xiàn)模型求解,最后通過算法仿真鋸切測試,驗證了本算法的可行性,為我國毛邊鋸材智能化鋸切提供一種新的解決方案。
由于鋸材中含有節(jié)子、腐朽和孔洞等缺陷,需去除后制成木制品坯料使用。加工鋸材時,通常根據(jù)鋸材的種類和尺寸選擇鋸切方法,對于毛邊鋸材,常用的有先截斷后縱解、先縱解后截斷2種加工方式[11],如圖1a—b所示。
圖1 毛邊鋸材下鋸方式Fig.1 The cutting methods of burr sawn timber
當采用先截斷后縱解的方式加工時,首先根據(jù)缺陷位置將鋸材橫向截斷,再通過多鋸片縱解圓鋸機將產(chǎn)生的短板縱解。此方法由于將長鋸材截斷成短板,便于車間運輸加工且能夠利用部分鋸材彎曲部分,但在橫向去除缺陷時會造成較多優(yōu)質(zhì)木材浪費。
當采用先縱解后截斷方式加工時,初步將鋸材按坯料寬度縱向鋸解,然后根據(jù)坯料長度將鋸材橫向截斷,同時去除缺陷部分。與先截斷后縱解加工相比,此方法去除缺陷時切除的優(yōu)質(zhì)木材較少且能獲得較長的坯料,但會因鋸材邊緣的縱向彎曲而降低出材率。
通過上述分析可知,以上2種加工方式在進行鋸材加工時均存在部分木材浪費。為更充分利用木材,本研究在以上2種加工方式的基礎上提出一種新的加工方法,即先截斷后縱解再截斷的加工方式,如圖1c所示。首先根據(jù)橫向截斷長度將鋸材鋸切成2~3段,再根據(jù)坯料寬度縱解鋸材,最后橫向去除缺陷。此方法與單一的先縱解后截斷加工方式相比,鋸材沿邊緣縱向彎曲的影響將減小,可充分利用木材,并且最終坯料長度也大于采用先截斷后縱解的加工方式。
本研究擬采用先截斷后縱解再截斷的加工方式,因其具有木材利用率高、便于車間運輸加工等優(yōu)點。但由于傳統(tǒng)鋸材加工在進行縱向鋸解時會采用固定寬度等寬鋸切,并由工人自主確定下鋸位置,鋸切過程中存在木材浪費、智能化加工能力不足和短坯料數(shù)量過多等問題,無法實現(xiàn)鋸材最大化利用,導致鋸材出材率降低。針對此問題,本研究提出一種優(yōu)化鋸切模式,縱向鋸解時采用不等寬鋸切,將出材率作為優(yōu)化目標,根據(jù)坯料寬度與鋸材缺陷調(diào)整鋸路位置,最大程度避開鋸材缺陷鋸切,提高出材率的同時合理考慮經(jīng)濟因素,具體如下:
對于被橫向截斷后產(chǎn)生的多段含缺陷短毛邊鋸材,首先將其視作無缺陷鋸材進行下鋸方案求解。在確定每段無缺陷鋸材下鋸方案時,同時考慮出材率與經(jīng)濟價值2個目標。對于出材率目標,視作在一塊去除毛邊后可用寬度為W的待縱向鋸切的整邊鋸材中,使用寬度為W1,W2,…,Wn的坯料進行寬度組合,坯料合計寬度Z1越高,則出材率越大,但寬度總和不可超出可用寬度。對于經(jīng)濟價值目標,則通過寬度組合中對應坯料價值與數(shù)量計算,坯料合計價值S越高,則整體經(jīng)濟價值越好。對以上2個目標和約束進行整合即:
求解目標:
約束條件:
式中:Wk表示第k種方案的坯料合計寬度,mm;Sk表示第k種方案的坯料合計價值;Sk表示第k種坯料對應價值;Qnk表示第k種方案的第n種坯料對應數(shù)量。
圖2 無缺陷鋸材下鋸方案的確定Fig.2 The sawing plan for clear sawn timber
圖3 確定最終下鋸方案Fig.3 The final sawing plan
通過求解上述雙目標問題,可得到多組優(yōu)秀下鋸方案(Q1,Q2,…,Qn),取出所有下鋸方案對原含缺陷鋸材模擬鋸切以獲取對應出材率(f1,f2,…,fn),選取其中最大出材率方案作為最終下鋸方案,即可得到高出材率與經(jīng)濟價值較優(yōu)的鋸切方案。
最終求解目標:
支配等級排序和擁擠距離排序是求解多目標問題的有效方法,通過對種群內(nèi)個體的支配關系和相應擁擠距離對種群內(nèi)個體逐級、逐個進行區(qū)分,確定每個解集的優(yōu)劣,并以此為基礎通過后續(xù)策略實現(xiàn)種群尋優(yōu)[12]。
2.1.1 編碼與初始種群生成
編碼方式采用基于坯料寬度的實數(shù)編碼,采用隨機長度的二維數(shù)組表示基因個體,基因上序號與對應的坯料寬度相映射,每一基因個體代表一種下鋸方案(圖4)。下鋸時,根據(jù)基因上坯料寬度從左到右依次鋸切。
圖4 基因編碼示意Fig.4 The schematic diagram of encoding
采用隨機生成的方式產(chǎn)生初始種群。每次在坯料寬度W1,W2,…,Wn中隨機選取一個放入,并統(tǒng)計總寬度,以此往復,直至總寬度將要大于鋸材可用寬度W即生成一組基因個體。重復上述過程,直至產(chǎn)生個體數(shù)量達到設置種群規(guī)模即生成初始種群。解碼時,通過統(tǒng)計寬度相同的基因序號個數(shù)即可求得對應坯料數(shù)量。
2.1.2 種群支配等級排序與個體擁擠距離排序
多目標問題中由于每個個體具有多種屬性,比較個體之間解的優(yōu)劣不采用簡單的大小關系而采用支配關系進行比較。支配關系按如下方式定義,設a、b是種群中的任意不同個體,若同時滿足:
1)對任意求解目標,有Zk(a)≥Zk(b)(k=1,2, ......,r)。
2)至少存在一個求解目標, ?m∈(1 ,2,......,r) ,使Zm(a)>Zm(b)。
那么則稱個體b被個體a支配,若a不被種群其余任何個體支配,則稱a為非支配個體,式中:r為求解目標數(shù)量。
種群的支配等級排序是一個循環(huán)分級的過程,本研究采用變量NP表示種群支配等級為P的個體集合,SP表示個體的支配個體集合,F(xiàn)P表示個體的被支配計數(shù)。首先找出整個種群中所有FP=0的個體,將其支配等級P設置為1,計入N1并統(tǒng)計每個個體對應的SP。然后遍歷每個支配個體集合SP,找出其中FP的個體,將其支配等級P設置為2,計入N2同時統(tǒng)計SP。循環(huán)往復,直至完成對整個種群的支配等級排序。
完成種群支配等級排序后,由于同支配等級中可能含有多個個體,此時需對處于同一支配等級的個體再次進行排序。采用傳統(tǒng)擁擠距離排序方法,個體間按照擁擠距離從大到小進行排序。該方法無須重新定義參數(shù)即可使整個解集在目標空間內(nèi)均勻分布,可有效維持種群的多樣性[13-14]。計算公式如下:
式中:di為第i個體擁擠距離;Zk(i+1)與Zk(i-1)分別表示了第i+1與i-1個體的第k目標函數(shù)值;Zkmax與Zkmin則代表種群中所有個體在第k目標函數(shù)上的最值。
2.1.3 多種群尋優(yōu)策略
初始種群產(chǎn)生后,需進行迭代搜索優(yōu)秀下鋸方案,本研究提出一種多種群尋優(yōu)策略(圖5)。初始時產(chǎn)生多個種群a1,a2,…,an,隨機選擇其中一個作為父代種群A1,對其余初始種群進行支配等級排序并取出其中精英解集N1放入子代種群B1直至填滿。將A1與B2并入中間種群C1,對C1進行支配等級排序和個體擁擠度排序,按支配等級和擁擠度距離區(qū)分C1以構造新父代種群A2。子代種群B2則同樣通過隨機產(chǎn)生初始種群選取其中的精英序列構造,同樣通過合并A2與B2產(chǎn)生C2,對C2排序即可產(chǎn)生A3,重復上述步驟直至產(chǎn)生最終種群An。迭代過程中,子代種群的產(chǎn)生均由相應種群的優(yōu)質(zhì)個體組成,可保證每代種群Ak中均為優(yōu)秀下鋸方案。
圖5 多種群尋優(yōu)Fig.5 Screening the excellent solution sets through multiple populations
在多種群尋優(yōu)過程中會不可避免地產(chǎn)生重復解集,而重復解集在進行支配等級排序時會被賦予同樣的支配等級,在迭代過程中可能被重復選入新種群,影響后續(xù)鋸切方案求解。因此,本研究在每次合并產(chǎn)生新種群時會對中間種群C進行一次重復檢測,統(tǒng)計C中完全重復的多個解集,對于每個重復解集只選取其中第一個重復個體進入父代種群,有效消除重復個體,保證后續(xù)求解質(zhì)量。
通過多種群尋優(yōu)策略,最終可得到多組下鋸方案,此時需在原含缺陷鋸材中進行模擬鋸切以選出最終下鋸方案。但與無缺陷鋸材鋸切不同,鋸切含缺陷鋸材時,由于缺陷存在,下鋸順序會對出材率產(chǎn)生影響,因此,需對每一下鋸方案尋找最佳下鋸順序。
遺傳算法起源于進化算法,是一種模仿生物進化機制的全局搜索算法,常被用于求解排序、旅行商等問題,該算法通過對問題可能的解編碼產(chǎn)生個體,每個個體即對應一種問題解決方案,采用選擇、交叉、變異等遺傳操作進行種群迭代,并采用適應度函數(shù)對種群進行評估以淘汰劣質(zhì)解,使得種群不斷進化,最終收斂至最優(yōu)解[15]。因此,本研究選擇遺傳算法進行每一下鋸方案的最優(yōu)下鋸順序搜索,以最終種群An中第k種下鋸方案Qk為例進行說明,假設。
2.2.1 初始種群生成與適應度計算
延續(xù)2.1.1小節(jié)中的編碼方法,對Qk進行隨機調(diào)序一次即生成一種新的下鋸方案,重復n次即生成初始種群R1。采用毛邊鋸材出材率作為適應度函數(shù),計算方法如下:
首先建立坐標系,以右下角為原點,為方便不同寬度毛邊鋸材計算,以距離鋸材中心線下方250 mm處向左為X軸正方向,沿鋸材最底端向上為Y軸正方向,通過四元數(shù)組(xn,yn,bn,hn)表示缺陷位置。對于種群中任意一個個體Pk,按以下步驟計算適應度(在整個計算過程中不計鋸路損耗)。
圖6 適應度計算Fig.6 The calculation of fitness
步驟1:首先去除鋸材毛邊,同時記錄鋸路初始縱坐標yl1,并依據(jù)Pk中寬度產(chǎn)生下一鋸路縱坐標yl2=yl1+W1;
步驟2:依次讀取缺陷,根據(jù)以下公式判斷是否有缺陷位于yl1與yl2之間。
步驟3:若無缺陷位于兩鋸路之間,則產(chǎn)生完整坯料,記錄坯料寬度與體積并通過Pk中下一個寬度更新鋸路縱坐標,轉(zhuǎn)回步驟2。若鋸路之間存在缺陷,則進行步驟4,直至所有寬度讀取完畢結(jié)束。
步驟4:統(tǒng)計位于鋸路之間缺陷個數(shù)與位置,從左至右依次鋸切,統(tǒng)計所產(chǎn)生短坯料寬度、體積和個數(shù)(小于150 mm的短坯料不記錄),更新鋸路縱坐標,轉(zhuǎn)回步驟2。
步驟5:通過完整坯料總體積與短坯料總體積計算適應度。
式中:Vjk為采用第k種鋸切方案鋸切后完整坯料總體積;Vdk為采用第k種鋸切方案切除缺陷后短坯料總體積;V為毛邊鋸材總體積。
2.2.2 遺傳操作
1)選擇操作:初始種群產(chǎn)生后,通過適應度對整個種群進行優(yōu)劣區(qū)分,此時需選擇優(yōu)秀個體進行后續(xù)遺傳操作。由于無精英策略的遺傳算法不收斂[16],因此每次選擇前首先保存最大適應度個體,防止后續(xù)遺傳操作對其進行破壞。對其余個體采用錦標賽選擇,每次進行選擇操作時隨機選取2個種群個體,取適應度大者進入后續(xù)交叉、變異操作。
2)交叉操作:交叉是遺傳算法核心操作,通過對選擇操作產(chǎn)生優(yōu)質(zhì)個體進行基因互換,使整個種群不斷進化。本研究采用片段匹配交叉,對于需交叉的2個父代,隨機產(chǎn)生2個實數(shù)m、n,將父代中各自位于m和n之間的基因片段交換產(chǎn)生新子代個體。
圖7 片段匹配交叉Fig.7 Partial-mapped crossover
圖8 矛盾檢測Fig.8 Conflict detection
與其他智能算法相同,遺傳算法在求解過程中可能會陷入局部優(yōu)解,其原因在于通過大量交叉后種群內(nèi)部個體趨于相似,此時再進行交叉操作難以獲得新解。為加強算法搜索新解的能力,本算法采用自適應交叉概率,在算法迭代前中期設置較大交叉概率,使得種群內(nèi)部快速、大量交叉,加快算法尋優(yōu)速度。隨著迭代進行,種群內(nèi)部相似度開始增大,則將交叉概率不斷減小,主要通過后續(xù)變異操作搜索新優(yōu)質(zhì)解。交叉概率計算公式如下:
式中:k1為設置初始交叉概率;m為當前迭代次數(shù);n為算法總迭代次數(shù)。
3)變異操作:采用基本位變異方式,變異時,隨機選取基因上2個位置交換序列,若選取序列對應寬度相同,則重新選取,直至選取非重復寬度。同樣設置自適應變異概率,隨著迭代進行,變異概率逐漸增大,增強算法后期搜索新解能力。
式中:k2為設置初始變異概率。
算法求解總流程圖如圖9所示。
圖9 算法總流程Fig.9 The overall flowchart of algorithm
采用C++編程實現(xiàn)算法功能,并通過OpenCV C++編程顯示仿真結(jié)果,編譯器采用Visual Studio 2019,在CORE i7 2.00 GHz CPU,8 GB 內(nèi)存的PC機上進行下文仿真測試,算法相關參數(shù)設置為:無缺陷情形下種群規(guī)模為150,迭代次數(shù)為100;含缺陷情形下種群規(guī)模為20,迭代次數(shù)為100,初始交叉概率為0.9,初始變異概率設置為0.2。橫向截斷長度設置3種,分別為1、2、3 m;坯料寬度為自輸入,本研究設置了11種寬度,坯料價值系數(shù)由相應寬度計算得出,坯料越寬其價值越大。為保證求解質(zhì)量,每次計算算法運行10次,取最優(yōu)結(jié)果。
式中:Sn為寬度為Wn的坯料價值系數(shù)。
為驗證算法的有效性,從遼寧某木材加工企業(yè)實測毛邊鋸材數(shù)據(jù),使用不同橫向截斷長度、不同輸入坯料寬度與不同毛邊鋸材進行算法仿真測試。
首先采用鋸材a進行仿真測試,鋸材實測模型如圖10所示。其中鋸材長度為6 050 mm,寬度從鋸材底端(圖中右端)至鋸材頂端(圖中左端)每隔1 m分別為350、340、340、330、320、330、330 mm,含14個缺陷。
圖10 鋸材a實測模型圖Fig.10 Measured model diagram of sawn timber a
輸入坯料寬度設置為50~150 mm(每10 mm一種寬度),采用不同的橫向截斷長度(1、2、3 m),分別使用傳統(tǒng)等寬鋸切方法(60、80 mm)與本算法對鋸材a進行仿真鋸切,數(shù)據(jù)統(tǒng)計結(jié)果見表1。圖11中為不同橫向截斷長度下傳統(tǒng)等寬鋸切方法(80 mm)與本算法的仿真鋸切結(jié)果。
圖11 仿真鋸切結(jié)果對比圖Fig.11 The comparison diagram of simulation sawing results
由表1可知,與傳統(tǒng)等寬鋸切方法相比:橫向截斷長度設置為1 m時,本算法仿真鋸切結(jié)果中完整坯料出材率平均提升了24.30%,總出材率平均提升了8.59%;橫向截斷長度設置為2 m時,本算法仿真鋸切結(jié)果中完整坯料出材率平均提升了24.80%,總出材率平均提升了7.06%;橫向截斷長度設置為3 m時,本算法仿真鋸切結(jié)果中完整坯料出材率平均提升了11.91%,總出材率平均提升了6.42%;說明在不同橫向截斷長度下,與傳統(tǒng)等寬鋸切方法相比,本算法均能夠根據(jù)所輸入坯料寬度,依據(jù)鋸材缺陷位置提供合理下鋸方案,高效使用鋸材。
表1 3類橫向截斷長度下仿真鋸切結(jié)果對比表Table 1 The comparison table of simulation sawing results in 3 types of transverse truncation lengths
更換鋸材,采用鋸材b進行仿真測試,鋸材b實測模型圖如圖12所示。其中鋸材長度為6 100 mm,寬度從鋸材底端至鋸材頂端每間隔1 m分別為360、360、360、350、340、340、350 mm,含11個缺陷。
圖12 鋸材b實測模型Fig.12 Measured model diagram of sawn timber b
采用2 m的橫向截斷長度,輸入坯料寬度分別設置為50~100 mm(每5 mm一種寬度)、50~150 mm(每10 mm一種寬度)、50~200 mm(每15 mm一種寬度),使用傳統(tǒng)等寬鋸切方法與本算法對鋸材b進行模擬鋸切,數(shù)據(jù)統(tǒng)計結(jié)果見表2。圖13中舉例說明了輸入坯料寬度設置為50~100 mm時,采用傳統(tǒng)等寬鋸切方法(85 mm)與本算法的模擬鋸切結(jié)果。
圖13 仿真鋸切結(jié)果對比Fig.13 The comparison diagram of simulation sawing results
表2 3類輸入坯料寬度下仿真鋸切結(jié)果對比表Table 2 The comparison table of simulation sawing results in three types of input widths
由表2可以看出,與傳統(tǒng)等寬鋸切方法相比,輸入坯料寬度設置為50~100 mm時,本算法仿真鋸切結(jié)果中完整坯料出材率平均提升了34.36%,總出材率平均提升了6.72%;輸入坯料寬度設置為50~150 mm時,本算法仿真鋸切結(jié)果中完整坯料出材率平均提升了36.45%,總出材率平均提升了12.73%;輸入坯料寬度設置為50~200 mm時,本算法仿真鋸切結(jié)果中完整坯料出材率平均提升了33.89%,總出材率平均提升了15.57%;說明在不同輸入坯料寬度下,本算法同樣能夠提供合理的下鋸方案。
為進一步驗證本算法的有效性,隨機選取實測鋸材中5塊不同的毛邊鋸材,選用2 m的橫向截斷長度,輸入坯料寬度設置為50~150 mm(每10 mm一種寬度),分別使用傳統(tǒng)等寬鋸切方法與本算法對鋸材進行仿真鋸切,數(shù)據(jù)統(tǒng)計結(jié)果見表3。
由表3可知,本算法的仿真鋸切結(jié)果均優(yōu)于傳統(tǒng)等寬鋸切方法,完整坯料出材率和總出材率明顯提升,其中完整坯料出材率平均提升了12.62%、23.58%、21.01%、25.93%和24.25%,總出材率平均提升了5.16%、7.97%、6.62%、9.20%和4.88%,說明本算法能夠針對不同鋸材合理計算下鋸方案。
表3 不同鋸材的仿真鋸切結(jié)果對比Table 3 Comparison of simulation sawing results in different sawn timbers
為解決我國木材加工企業(yè)智能化加工能力不足和出材率低的問題,本研究提出了基于非支配排序與遺傳算法的毛邊鋸材優(yōu)化下鋸算法,主要結(jié)論如下:
1)通過分析毛邊鋸材下鋸方法,確定了先截斷后縱解再截斷的加工方法,并以此為依據(jù)將鋸材出材率作為優(yōu)化目標同時合理考慮坯料價值完成了優(yōu)化下鋸模型的構建。
2)求解無缺陷鋸材下鋸方案時,通過非支配排序與擁擠度排序確定個體之間的優(yōu)劣,并提出了一種多種群尋優(yōu)策略,快速尋找優(yōu)秀下鋸方案。使用遺傳算法搜尋每一方案的最佳下鋸順序時,采用片段匹配完成基因交叉,并通過對照關系去除了基因矛盾,同時設置了自適應交叉變異概率來加強算法的搜索新解能力。
3)算法仿真測試結(jié)果表明,本研究提出的算法能夠針對不同橫向截斷長度、不同輸入坯料寬度與不同毛邊鋸材分別確定合理的下鋸方案,為我國毛邊鋸材智能化鋸切提供一種新的解決方案。
本研究還存在一些不足之處:
1)由于確定最終下鋸方案時是以鋸材出材率作為求解目標,若毛邊鋸材上缺陷過多,那么通過無缺陷鋸材下鋸方案求解得到的部分高價值下鋸方案因為坯料較寬,在出材率計算時將處于劣勢,在后續(xù)的研究中,應當尋找出材率與坯料價值之間的平衡方法。
2)本研究中輸入坯料寬度設置為11種,最終求解得到的下鋸方案僅為給定輸入寬度下的合理方案。在未來的研究中,應該擴大可輸入坯料寬度種類,并合理調(diào)整無缺陷情形下種群大小,針對每一塊毛邊鋸材求解更優(yōu)秀的下鋸方案。