徐小斐，陳 婧，饒運(yùn)清，孟榮華,4+，袁 博，羅 強(qiáng)

(1.華中科技大學(xué) 機(jī)械科學(xué)與工程學(xué)院，湖北 武漢 430074；2.貴州交通職業(yè)技術(shù)學(xué)院 汽車工程系，貴州 貴陽 550008；3.武漢理工大學(xué) 機(jī)電工程學(xué)院，湖北 武漢 430074；4.三峽大學(xué) 機(jī)械與動力學(xué)院，湖北 宜昌 443002)

0 引言

矩形排樣是二維優(yōu)化下料問題的分支，指按照最優(yōu)方案在矩形板材上排放不同尺寸規(guī)格的矩形零件，同時(shí)實(shí)現(xiàn)板材利用率最大。矩形排樣廣泛存在于鋼板下料、玻璃切割、家具切割、皮革制造等行業(yè)中，可以幫助企業(yè)提高材料利用率，節(jié)約生產(chǎn)成本，也體現(xiàn)了“綠色制造”的理念，二維異形件也可以通過矩形包絡(luò)轉(zhuǎn)化成矩形排樣問題，因此該問題具有很高的研究與實(shí)用價(jià)值。矩形排樣是典型的NP-Hard問題，時(shí)間復(fù)雜度隨零件規(guī)模增加呈指數(shù)式“爆炸”增長。將經(jīng)典啟發(fā)式定位算法如最低水平線法[1]、BL(bottom-left)算法[2]、剩余矩形匹配算法[3]與啟發(fā)式智能搜索算法如遺傳算法[4](Genetic Algorithm, GA)、蟻群算法[5](Ant Colony Optimization, ACO)、粒子群算法[6]等結(jié)合解決矩形排樣問題已逐漸成為研究的熱點(diǎn)，但仍存在著求解時(shí)間過、利用率偏低的問題。

蟻群強(qiáng)化學(xué)習(xí)算法將蟻群算法與強(qiáng)化學(xué)習(xí)中的Q-learning算法相融合，該算法不僅繼承了蟻群算法強(qiáng)魯棒性、并行性和正反饋的優(yōu)點(diǎn)[7]，還兼并了強(qiáng)化學(xué)習(xí)中權(quán)衡探索(exploration)與利用(exploition)的特點(diǎn)[8]。文獻(xiàn)[9-10]在故障模型和網(wǎng)格資源分配問題中引入了強(qiáng)化學(xué)習(xí)和蟻群算法，文中首先使用Sarsa算法初始化各節(jié)點(diǎn)信息素資源分配，再借助蟻群算法進(jìn)一步尋優(yōu)。但兩篇文獻(xiàn)都是將強(qiáng)化學(xué)習(xí)作為信息初始化算法，沒有借助強(qiáng)化學(xué)習(xí)的優(yōu)勢提高單只螞蟻的尋優(yōu)能力，容易陷入局部最優(yōu)。文獻(xiàn)[11]使用蟻群算法協(xié)調(diào)多機(jī)器人運(yùn)行，同時(shí)用強(qiáng)化學(xué)習(xí)算法提高單機(jī)器人定位跟蹤能力。該算法提高了單只螞蟻的尋優(yōu)能力，但在求解任務(wù)時(shí)只關(guān)注任務(wù)本身，任務(wù)之間彼此孤立尋優(yōu)，求解優(yōu)化相似新任務(wù)時(shí)不能有效利用已有的經(jīng)驗(yàn)和知識，需重新開始搜索優(yōu)化，從而導(dǎo)致效率低下。

在實(shí)際生產(chǎn)中，由于同類產(chǎn)品采取批次輪番生產(chǎn)的方式且同系列內(nèi)的產(chǎn)品常采取變形設(shè)計(jì)，因此批量生產(chǎn)模式下前后排樣任務(wù)的待下料零件有一定的重復(fù)性。為提高排樣效率與優(yōu)化效果，新排樣任務(wù)在線尋優(yōu)時(shí)應(yīng)借助以前的排樣經(jīng)驗(yàn)和知識。機(jī)器學(xué)習(xí)中的知識遷移[12](Knowledge Transfer，KT)具有模擬人類思維的特點(diǎn)，旨在根據(jù)任務(wù)之間的相似性，利用已有知識和經(jīng)驗(yàn)，幫助新相似任務(wù)減少學(xué)習(xí)時(shí)間，提高尋優(yōu)性能。在實(shí)際工程問題中，文獻(xiàn)[13]通過貝葉斯理論計(jì)算源任務(wù)與目標(biāo)任務(wù)的相似度，從中篩選合適的樣本遷移，但當(dāng)任務(wù)規(guī)模增大時(shí)，需要耗費(fèi)大量的時(shí)間計(jì)算相似度與篩選合適遷移樣本；文獻(xiàn)[14-16]分別將知識遷移引入到電力系統(tǒng)的無功優(yōu)化、風(fēng)險(xiǎn)調(diào)度、多能源聯(lián)合優(yōu)化調(diào)度問題中，將Q-learning與群智能算法結(jié)合構(gòu)造試錯(cuò)學(xué)習(xí)模式，通過狀態(tài)—組合鏈實(shí)現(xiàn)大規(guī)模任務(wù)降維，并借助知識遷移技術(shù)實(shí)現(xiàn)智能群體的遷移學(xué)習(xí)。該算法適用于大規(guī)模電力系統(tǒng)問題快速求解，但目前尚未有將知識遷移應(yīng)用于矩形排樣方面的研究。

因此，本文將蟻群算法與強(qiáng)化學(xué)習(xí)中的Q-learning算法相結(jié)合，同時(shí)引入知識遷移技術(shù)，提出基于知識遷移的蟻群強(qiáng)化學(xué)習(xí)算法(Knowledge Transfer Ants Q-learning algorithm, KTAQ)，以解決矩形優(yōu)化排樣問題。為驗(yàn)證本文所提KTAQ算法的有效性，對不同規(guī)模的矩形排樣問題進(jìn)行了仿真驗(yàn)證，并與其他傳統(tǒng)智能算法對比，結(jié)果證明本文所提算法能夠有效求解大中規(guī)模矩形排樣問題。

1 矩形排樣數(shù)學(xué)模型

由于生產(chǎn)工藝的要求和加工條件的限制，不同領(lǐng)域的優(yōu)化下料問題對應(yīng)不同的數(shù)學(xué)模型[17-18]。本文所研究的矩形排樣問題為二維矩形件帶排樣問題(Two-dimensional Rectangular Strip Packing Problem, 2DRSP)。2DRSP可描述為：一組數(shù)量為n的待排矩形零件R1，R2，…，Rn，寬高一定，矩形之間有強(qiáng)互異性(strong heterogeneous)[19]。設(shè)第i個(gè)矩形的寬為wi，高為hi，則矩形Ri可表示為(wi，hi)(i=1,2,…,n)；設(shè)矩形板材的寬為W，高度不限。2DRSP的目標(biāo)是將n個(gè)小矩形排放到高度不限的矩形板材中，使板材利用率最大。2DRSP問題要滿足以下約束條件：①矩形零件不超出板材邊界；②任意矩形零件之間不相互重疊；③矩形零件允許90度旋轉(zhuǎn)；④矩形零件的邊需與板材邊界平行。如圖1所示為10個(gè)矩形排樣的實(shí)例，灰色部分表示不能利用的空洞。

Hmax表示矩形零件排放完成之后最高輪廓線所對應(yīng)的板材高度。2DRSP的目標(biāo)是使板材利用率最大化，即使板材高度Hmax最小，適應(yīng)度函數(shù)如式(1)所示：

(1)

且要滿足約束：

s.t.

?Ri:0≤xi≤W,0≤xi+yi≤W,yi>0

?Ri和Rj,且i≠j:xi≤xj≤xi+wi與

yi≤yj≤yi+hi不同時(shí)成立。

(2)

其中式(2)保證矩形零件排放后不超出板材邊界和零件之間互相不重疊。

本文采用十進(jìn)制編碼方式，將一個(gè)不重復(fù)的十進(jìn)制整數(shù)作為矩形零件的唯一標(biāo)識碼，一個(gè)完整的整數(shù)序列即對應(yīng)一個(gè)可行的排樣方案。求解矩形優(yōu)化排樣問題的關(guān)鍵在于零件的定序和定位算法。定序算法是搜索一組最優(yōu)的矩形排樣順序，目標(biāo)是調(diào)用定位算法解碼后的板材利用率最大；定位算法是對搜索到的序列進(jìn)行解碼，由算法中的定位規(guī)則確定零件在板材中的具體排放位置，由此生成排樣圖，并計(jì)算板材利用率即適應(yīng)度值。本文采用KTAQ算法搜索零件排入序列，用基于匹配度評價(jià)的最低水平線法進(jìn)行零件定位，將矩形零件排入板材最低輪廓線。

2 KTAQ算法原理

KTAQ算法主要分為預(yù)學(xué)習(xí)、知識遷移和遷移學(xué)習(xí)3個(gè)階段。預(yù)學(xué)習(xí)階段主要是學(xué)習(xí)源任務(wù)，以積累經(jīng)驗(yàn)知識；知識遷移階段是挖掘目標(biāo)任務(wù)與源任務(wù)的相似性，并從相似源任務(wù)中遷移合適的經(jīng)驗(yàn)策略；遷移學(xué)習(xí)階段將遷移知識作為初始動作策略，加速目標(biāo)任務(wù)在線學(xué)習(xí)尋優(yōu)過程。其中預(yù)學(xué)習(xí)和遷移學(xué)習(xí)雖知識初始化和具體參數(shù)設(shè)置不同，但都有相同的學(xué)習(xí)模式。下面具體闡述KTAQ算法學(xué)習(xí)模式和遷移模式。

2.1 KTAQ算法蟻群學(xué)習(xí)模式

2.1.1 知識獲取方式

傳統(tǒng)蟻群算法中螞蟻完全依賴概率對解空間進(jìn)行搜索，憑借蟻群的分布式搜索得到最優(yōu)解[20]。而強(qiáng)化學(xué)習(xí)中的智能體學(xué)習(xí)如何基于環(huán)境而行動，靠反復(fù)“試錯(cuò)”達(dá)到學(xué)習(xí)目的，學(xué)習(xí)的是當(dāng)前狀態(tài)下應(yīng)采取的動作策略[8]。因此，KTAQ算法中基于Q-learning的蟻群強(qiáng)化學(xué)習(xí)算法與傳統(tǒng)的蟻群搜索算法有較大的差異。

KTAQ算法中蟻群是有自學(xué)習(xí)能力的智能體，能不斷改善自身行為，其學(xué)習(xí)模式如圖2所示。螞蟻總是處于某種環(huán)境狀態(tài)中，蟻群根據(jù)狀態(tài)從知識空間獲取知識，并制定動作策略對環(huán)境進(jìn)行試錯(cuò)學(xué)習(xí)。一旦螞蟻?zhàn)隽四撤N動作選擇，狀態(tài)就隨之改變，在完整的動作序列執(zhí)行完畢后，反饋以獎勵(lì)形式給出，用以更新空間中原有知識。蟻群反復(fù)試錯(cuò)學(xué)習(xí)，直至獲得最大化長期總收益對應(yīng)的動作策略。在Q-learning中，知識空間內(nèi)的元素表示智能體在不同狀態(tài)下選擇不同動作的Q值，為智能體制定動作策略提供依據(jù)[21]。

2.1.2 知識空間分解降維

在Q-learning中，知識空間以lookup表形式呈現(xiàn)，設(shè)狀態(tài)集和動作集分別為S和A，則lookup表的大小為S×A={(s,a)|s∈S，a∈A}中元素的個(gè)數(shù)。當(dāng)任務(wù)規(guī)模增大時(shí)，表中元素個(gè)數(shù)呈指數(shù)式“爆炸”增長，發(fā)生高維空間常遇到的“維數(shù)災(zāi)難”，使計(jì)算時(shí)間大大增加。

本文將AQ空間定義為KTAQ算法的知識空間。空間元素AQ(s,a)值即為當(dāng)前狀態(tài)(s)與動作(a)下的經(jīng)驗(yàn)知識，簡稱為AQ值，其值越大，表示經(jīng)驗(yàn)中此狀態(tài)動作聯(lián)系越緊密，選擇該動作的評價(jià)也越高。在矩形排樣中，每個(gè)矩形既可以作為“當(dāng)前狀態(tài)”，也可以作為“待選動作”。針對大規(guī)模矩形排樣問題出現(xiàn)的“維數(shù)災(zāi)難”，受文獻(xiàn)[14]對高維動作狀態(tài)空間分解的啟發(fā)，本文提出一種基于知識延伸的高維空間合并方法，如圖3所示。假設(shè)任務(wù)有n個(gè)變量，每個(gè)變量的可選動作集為Ai(i=1,…,n)。將AQ空間劃分為n個(gè)二維小矩陣AQi(i=1,…,n)，相鄰變量間根據(jù)AQi中儲存的知識來聯(lián)系。變量i的動作即為變量i+1的狀態(tài)，由此形成基于知識的鏈?zhǔn)窖由?。對于矩形排樣等組合優(yōu)化問題，每個(gè)變量的“狀態(tài)”和“動作”都是從待排零件中選擇，因此每個(gè)小矩陣AQi的狀態(tài)集和動作集都相同。為避免矩陣過于稀疏，將所有小矩陣的知識都集中到一個(gè)二維矩陣AQT中，依靠該矩陣完成所有步驟中知識的更新與利用，該二維知識矩陣的橫縱坐標(biāo)分別為狀態(tài)集和動作集。

2.1.3 知識更新策略

KTAQ算法中所有螞蟻都根據(jù)初始矩陣對食物環(huán)境進(jìn)行試錯(cuò)學(xué)習(xí)，并將環(huán)境獎勵(lì)反饋給知識矩陣。單次迭代循環(huán)內(nèi)，當(dāng)螞蟻完成一條完整路徑的構(gòu)造(即產(chǎn)生一個(gè)可行的排樣序列)，為加深對優(yōu)秀解鄰域的探討，同時(shí)避免知識的學(xué)習(xí)進(jìn)入停滯階段，本文設(shè)計(jì)局部調(diào)整算子對已生成的排樣序列進(jìn)行調(diào)整，過程如下：設(shè)螞蟻數(shù)量為m，計(jì)算每只螞蟻對應(yīng)序列的適應(yīng)度并將其從高到低排列，取排名前m/2的序列進(jìn)行局部調(diào)整。設(shè)R={R1，R2，…，Rn}為矩形零件排入板材的一種順序，在序列中任意取兩個(gè)不重復(fù)矩形，按e(e∈(0,1))值決定是否交換。隨機(jī)生成(0,1)之間的數(shù)r，若r

(3)

式中：kiter為當(dāng)前迭代次數(shù)；kiter_max為最大迭代次數(shù)；μmin和μmax為經(jīng)驗(yàn)因子，大量實(shí)驗(yàn)表明，取0.5和0.9時(shí)可取得最佳仿真結(jié)果。每個(gè)序列重復(fù)上述交換操作s次，計(jì)算新序列的適應(yīng)度，若交換后新序列的適應(yīng)度高于原序列，則保留新序列，否則不改變。

與Q-learning中只有單智能體學(xué)習(xí)試錯(cuò)的模式不同，KTAQ算法中多智能體蟻群共同試錯(cuò)學(xué)習(xí)，全部螞蟻共有一個(gè)AQ知識矩陣，大大加快了學(xué)習(xí)尋優(yōu)的速度[22]。每次試錯(cuò)學(xué)習(xí)后，KTAQ算法會對本次迭代內(nèi)序列適應(yīng)度值最高的螞蟻進(jìn)行獎勵(lì)，并更新知識矩陣。其他序列對應(yīng)的知識只執(zhí)行揮發(fā)操作。矩陣元素更新操作如式(4)所示：

AQ(s,a)=AQ(s,a)+α[R+

(4)

式中；α為學(xué)習(xí)因子；γ為折扣因子；s′為狀態(tài)s下選擇動作a之后的狀態(tài)；z為s′狀態(tài)下可選的動作；R為選擇動作a后獲得的獎勵(lì)函數(shù)值，表示期待學(xué)習(xí)優(yōu)化的方向，但當(dāng)執(zhí)行揮發(fā)操作時(shí)，R值為0，表示不對該序列路徑進(jìn)行獎勵(lì)。本文為知識矩陣中每一個(gè)元素AQ(s,a)設(shè)置上下閾值，使值的大小控制在[AQmin，AQmax]范圍內(nèi)，避免學(xué)習(xí)陷入停滯。

2.1.4 動作選擇策略

蟻群在探索完整的序列時(shí)，每一步都面臨如何選擇下一步動作的問題，即要選擇路徑上的下一個(gè)矩形。與ACO算法完全依賴概率選擇路徑不同，KTAQ算法需要博弈“利用”和“探索”兩種動作選擇模式。側(cè)重知識利用時(shí)可以加快學(xué)習(xí)速度，但會造成知識的不準(zhǔn)確，極易陷入局部最優(yōu)；側(cè)重隨機(jī)探索時(shí)會加大全局搜索，有更高的概率收斂到最優(yōu)解，但對知識的利用程度較低且尋優(yōu)速度極慢。為權(quán)衡知識的利用和探索，本文選用知識經(jīng)驗(yàn)和隨機(jī)選擇結(jié)合的ε-greedy策略進(jìn)行動作選擇，如式(5)所示：

a=

(5)

式中：ε∈[0,1]，且為均勻分布的隨機(jī)數(shù)；ε0為按照知識經(jīng)驗(yàn)選擇動作的參數(shù)，ε0∈(0,1)；u表示狀態(tài)s下的可選動作集合A(s)中某一動作；δ和β分別表示經(jīng)驗(yàn)知識AQ值和啟發(fā)知識HE值對螞蟻下一步動作選擇的重要程度。

隨著矩形零件逐漸排入板材中，水平線被分割，會產(chǎn)生眾多零碎的水平線段，此時(shí)若沒有合適的矩形零件排入就會產(chǎn)生空隙，導(dǎo)致板材的浪費(fèi)。若將小零件靠后排放，就可以填補(bǔ)這些零碎的空隙。由于長寬比相差較大的矩形零件對空間的排放要求更高，因此也需優(yōu)先排放這些零件。受此啟發(fā)，基于板材利用率最大，啟發(fā)知識HE值設(shè)置要優(yōu)先考慮零件面積和長寬比，設(shè)lu和su表示零件u的長邊和短邊，啟發(fā)知識設(shè)置如式(6)所示：

(6)

式中Wa和Wr分別表示零件面積和長寬比在啟發(fā)信息中所占權(quán)重。

式(5)表明，當(dāng)隨機(jī)數(shù)ε≤ε0時(shí)，螞蟻受經(jīng)驗(yàn)知識和和啟發(fā)知識的指導(dǎo)來選擇下一個(gè)動作；否則，按照S式進(jìn)行隨機(jī)概率探索，如式(7)所示：

(7)

螞蟻每次動作選擇前都要進(jìn)行判斷，使智能體既可以利用知識矩陣中的先驗(yàn)知識，也可以進(jìn)行新的探索，這樣不僅加深了對優(yōu)秀解的探索能力，還能使算法有較強(qiáng)的全局搜索能力，避免陷入局部最優(yōu)。

2.2 KTAQ知識遷移方式

傳統(tǒng)強(qiáng)化學(xué)習(xí)所獲得的經(jīng)驗(yàn)知識與特定的任務(wù)相關(guān)，任務(wù)之間是孤立的。而遷移學(xué)習(xí)能將以往任務(wù)的經(jīng)驗(yàn)和知識遷移到相似任務(wù)中，以減少新任務(wù)學(xué)習(xí)時(shí)間，因此近年來在強(qiáng)化學(xué)習(xí)中有著廣泛地應(yīng)用[23]。如果新舊任務(wù)相似，則狀態(tài)集合和動作集合有很大的重疊和相似情況，可以將源任務(wù)學(xué)到的最優(yōu)知識矩陣通過一定的方式遷移給目標(biāo)任務(wù)作為其初始知識矩陣，通過這種方式實(shí)現(xiàn)知識的遷移和再利用。

在用遷移知識解決目標(biāo)任務(wù)之前，KTAQ算法需要對一系列源任務(wù)Si(i=1,…,p)進(jìn)行預(yù)學(xué)習(xí)以儲備知識，如圖4所示。將相似源任務(wù)Si的知識矩陣AQSi通過線性遷移策略遷移給目標(biāo)任務(wù)T，作為其初始知識矩陣AQT，以便目標(biāo)任務(wù)利用知識進(jìn)行快速高效的在線學(xué)習(xí)。

源任務(wù)與目標(biāo)任務(wù)存在一定的相似性，但遷移過程中不可避免地會產(chǎn)生負(fù)遷移(negative transfer)現(xiàn)象[24]。知識矩陣中存在著一些無價(jià)值、無關(guān)聯(lián)的知識，若不加以分辨并剔除則會使遷移后的尋優(yōu)性能變差。為此，要對新舊任務(wù)之間的相似性進(jìn)行深入挖掘，提取有效知識。后文將針對矩形優(yōu)化排樣問題展開相似性以及具體遷移策略的分析。

2.3 KTAQ算法流程

圖5對KTAQ算法的3個(gè)階段做了詳細(xì)描述。選定有代表性的任務(wù)為源任務(wù)，在預(yù)學(xué)習(xí)階段對其尋優(yōu)求解，積累學(xué)習(xí)經(jīng)驗(yàn)，并將其最優(yōu)知識矩陣存儲到知識庫；在線性知識遷移階段，根據(jù)目標(biāo)任務(wù)的特點(diǎn)選取相似源任務(wù)，對其最優(yōu)知識矩陣線性組合并遷移到目標(biāo)任務(wù)中；第3階段為遷移學(xué)習(xí)階段，將上階段整理得到的知識經(jīng)驗(yàn)作為目標(biāo)任務(wù)的初始化動作策略，以便加速目標(biāo)任務(wù)在線學(xué)習(xí)過程。算法結(jié)束的條件為迭代次數(shù)kiter>kiter_max或‖AQk-AQk-1‖<σ(σ∈R+且取較小值)，σ為AQ矩陣收斂判定系數(shù)。

3 矩形排樣求解

3.1 狀態(tài)動作與獎勵(lì)函數(shù)設(shè)計(jì)

用KTAQ算法求解矩形排樣時(shí)，選擇一個(gè)動作表示從剩余矩形零件中挑選一個(gè)矩形加入到排樣序列，當(dāng)前選擇的“動作矩形”即為下一步動作選擇時(shí)的“狀態(tài)矩形”。因此，本文知識空間中的狀態(tài)動作都由當(dāng)前任務(wù)的矩形零件構(gòu)成。每兩個(gè)不重復(fù)矩形Rs和Ra都對應(yīng)知識矩陣中的元素AQ(Rs,Ra)，其值表示經(jīng)驗(yàn)中當(dāng)前兩個(gè)矩形的密切程度，可作為矩形排樣序列構(gòu)建時(shí)動作選擇的知識依據(jù)。

式(1)給出的模型目標(biāo)函數(shù)是追求板材利用率最大，即最高輪廓線對應(yīng)的板材高度最小，而KTAQ算法式(4)的獎勵(lì)函數(shù)R表示期待優(yōu)化的方向，因此更小的板材高度代表著更優(yōu)的學(xué)習(xí)效果，設(shè)置環(huán)境獎勵(lì)函數(shù)如式(8)：

(8)

式中：ER為環(huán)境獎勵(lì)系數(shù)，hib表示當(dāng)前迭代最優(yōu)的螞蟻對應(yīng)的板材高度。若最優(yōu)螞蟻不經(jīng)過(Rs,Ra)，R值為0，表示不對此序列路徑進(jìn)行獎勵(lì)。

3.2 基于值評價(jià)的最低水平線法

KTAQ算法可學(xué)習(xí)得到一個(gè)完整的矩形排樣序列，代表零件依次排入板材的順序。本文提出基于匹配度評價(jià)的最低水平線法對序列進(jìn)行解碼，以確定零件在板材中的具體排放位置，生成排樣圖并計(jì)算板材利用率。零件排入板材過程中，出現(xiàn)的最低輪廓線為最低水平線Llow，若出現(xiàn)多段，則取最左一段。大部分文獻(xiàn)將矩形排入最低水平線時(shí)只考慮到矩形的寬度和水平線長度的匹配程度[25-26]，而較少有文獻(xiàn)考慮高度方向上的匹配度，致使板材利用率不高。

本文提出基于匹配度評價(jià)的最低水平線法，考慮矩形零件的寬高尺寸，依據(jù)評價(jià)值靈活的選擇排入最低水平線的矩形件，實(shí)現(xiàn)對板材空隙的充分利用。以矩形排入最低水平線后的對齊情況作為匹配度評價(jià)值，如表1所示。其中淺色部分表示已排入板材的零件，深色部分為待排入零件。

表1 匹配度規(guī)則評價(jià)表

具體排樣步驟如下：

步驟1初始化水平輪廓線集合為板材的底邊，同時(shí)也為最低水平線。

步驟2當(dāng)要排入零件Ri時(shí)，從當(dāng)前水平輪廓線集合中選取最低的一段作為最低水平線，在排樣序列中從矩形Ri向后搜索，對后續(xù)每個(gè)矩形及其旋轉(zhuǎn)后的情況按匹配度規(guī)則進(jìn)行評價(jià)，選取匹配度最高的矩形排入最低水平線，若有多個(gè)，則取最靠前的矩形；若所有待排矩形的匹配度值都為0，則提升最低水平線至與其相鄰且高度較低的一段平齊。更新輪廓線集合。

步驟3重復(fù)步驟2，直至所有矩形都排入板材中。

3.3 遷移設(shè)計(jì)

KTAQ算法遷移效果優(yōu)劣的關(guān)鍵在于是否將合適的知識遷移到目標(biāo)任務(wù)中。在矩形排樣中，相似任務(wù)的排樣結(jié)果往往有相同或相似的規(guī)律。排樣任務(wù)的相似程度主要取決于零件的組成情況，本文采用矩形重疊率作為衡量標(biāo)準(zhǔn)，它能夠反映源任務(wù)與目標(biāo)任務(wù)相似的程度，其值越大，相似程度越大，其計(jì)算如式(9)所示：

(9)

式中：nSi表示源任務(wù)Si與目標(biāo)任務(wù)T中矩形件重疊的數(shù)目，n為T中矩形零件的數(shù)目。目標(biāo)任務(wù)T進(jìn)行快速學(xué)習(xí)需要的是描述矩形與矩形間密切程度的知識，而與其矩形重疊率高的源任務(wù)正可以提供較多的知識供其學(xué)習(xí)。

為了充分利用源任務(wù)的知識，同時(shí)盡量避免負(fù)遷移現(xiàn)象的產(chǎn)生，遷移策略的設(shè)計(jì)本著相似度越高、遷移貢獻(xiàn)率越大的原則，從源任務(wù)中選擇相似度最大的兩個(gè)任務(wù)進(jìn)行知識遷移。由Ω1和Ω2歸一化處理得兩個(gè)源任務(wù)的遷移貢獻(xiàn)系數(shù)λ1和λ2，使λ1+λ2=1，則目標(biāo)任務(wù)T的知識矩陣元素值為式(10)所示：

(10)

綜上所述，具體的遷移過程如下：①選取若干典型源任務(wù)進(jìn)行學(xué)習(xí)，以獲得儲備知識；②選取與目標(biāo)任務(wù)T最為相似的兩個(gè)源任務(wù)，將其與T的矩形重疊率Ω1和Ω2歸一化處理，得到遷移貢獻(xiàn)系數(shù)λ1、λ2；③初始化目標(biāo)任務(wù)T中的知識矩陣，按上述遷移規(guī)則進(jìn)行知識遷移；④T利用知識矩陣策略進(jìn)行快速在線學(xué)習(xí)尋優(yōu)。

3.4 參數(shù)設(shè)置

在KTAQ算法中，對學(xué)習(xí)和尋優(yōu)效果影響較大的參數(shù)主要有蟻群規(guī)模m、學(xué)習(xí)因子α、折扣因子γ、知識經(jīng)驗(yàn)參數(shù)ε0、環(huán)境獎勵(lì)系數(shù)ER。經(jīng)過多次仿真實(shí)驗(yàn)，發(fā)現(xiàn)各參數(shù)對尋優(yōu)結(jié)果的影響如下：

(1)蟻群規(guī)模m參與學(xué)習(xí)的螞蟻智能體數(shù)量，m值越大，搜索到最優(yōu)解的可能性越大，但需要耗費(fèi)大量計(jì)算時(shí)間。經(jīng)多次試驗(yàn)仿真，將預(yù)學(xué)習(xí)階段和遷移學(xué)習(xí)階段的螞蟻數(shù)量分別設(shè)置為150和50。

(2)學(xué)習(xí)因子α蟻群從食物環(huán)境中學(xué)習(xí)的速度，α∈(0,1)，α值越大表示學(xué)習(xí)越快，但極易陷入局部最優(yōu)。本文預(yù)學(xué)習(xí)和遷移學(xué)習(xí)階段分別設(shè)置為0.5和0.3。

(3)折扣因子γ對歷史獎勵(lì)值的折扣程度，γ值越大，表示對當(dāng)前獎勵(lì)越重視，本文兩個(gè)階段都取值0.9。

(4)知識經(jīng)驗(yàn)參數(shù)ε0表示蟻群利用經(jīng)驗(yàn)知識和隨機(jī)探索之間的權(quán)衡。當(dāng)目標(biāo)任務(wù)已獲得初始的經(jīng)驗(yàn)策略時(shí)，可適當(dāng)增大ε0，以提高尋優(yōu)的速度。因此預(yù)學(xué)習(xí)和遷移學(xué)習(xí)階段分別取值0.75和0.9。

(5)環(huán)境獎勵(lì)系數(shù)ER代表環(huán)境對最優(yōu)解的獎勵(lì)。本文統(tǒng)一設(shè)置ER為500。

4 仿真實(shí)驗(yàn)

從目前已發(fā)表文獻(xiàn)來看，國內(nèi)外缺乏將知識遷移應(yīng)用于矩形排樣領(lǐng)域中的研究，因此并沒有標(biāo)準(zhǔn)算例來對本文提出的算法進(jìn)行效果對比。為驗(yàn)證本文所提算法的有效性，對現(xiàn)今國際通用的矩形排樣標(biāo)準(zhǔn)算例加以修改，進(jìn)而保證源任務(wù)和目標(biāo)任務(wù)的相似性，用改進(jìn)的幾組算例來對本文算法進(jìn)行測試，使之能適應(yīng)遷移策略的展開。仿真算例均在CPU為Intel(R) Core(TM) i3-2100、主頻率為3.10 GHz、內(nèi)存為8 GB的計(jì)算機(jī)上運(yùn)行，算法基于Windows平臺并采用C++語言編程實(shí)現(xiàn)。為消除隨機(jī)因素的影響，結(jié)果均10次獨(dú)立運(yùn)算后取平均值。

4.1 實(shí)驗(yàn)1

本實(shí)驗(yàn)采用NICE測試集中的nice5問題進(jìn)行矩形優(yōu)化排樣問題研究。為保證任務(wù)之間的相似性，便于遷移動作的展開，本文中的源任務(wù)和目標(biāo)任務(wù)均從nice5中的500個(gè)矩形零件中隨機(jī)選取375個(gè)零件進(jìn)行優(yōu)化排樣?，F(xiàn)由系統(tǒng)隨機(jī)生成3個(gè)源任務(wù)S1、S2、S3和目標(biāo)任務(wù)T，S1、S2、S3與T的矩形重疊率分別為80%、73%、67%。

首先，為證明矩形重疊率越高，知識被利用的程度越高，從而遷移效果越好，進(jìn)行單源遷移實(shí)驗(yàn)。單源遷移即為從單個(gè)源任務(wù)中獲取知識，并將其遷移到目標(biāo)任務(wù)中。如圖6所示為從各源任務(wù)遷移的KTSk算法和無遷移的標(biāo)準(zhǔn)蟻群ACO算法的排樣高度收斂情況。

由圖6可以發(fā)現(xiàn)，ACO在初期搜尋和后期收斂階段的尋優(yōu)性能均劣于其他3種算法，并且陷入了局部最優(yōu)。這是由于目標(biāo)任務(wù)缺乏經(jīng)驗(yàn)知識，只得在與環(huán)境不斷交互中為自己積累經(jīng)驗(yàn)，因此排樣尋優(yōu)效果較差。同時(shí)可以看出，源任務(wù)與目標(biāo)任務(wù)的矩形重疊率越高，算法的求解效果越好，重疊率為80%的源任務(wù)S1的遷移性能最優(yōu)。這是由于任務(wù)越相似，可提供給目標(biāo)任務(wù)借鑒的經(jīng)驗(yàn)越多，遷移知識被利用的程度越高，因而減少了目標(biāo)任務(wù)在線尋優(yōu)的盲目性。因此，為提高遷移性能，應(yīng)盡可能選擇重疊率高的源任務(wù)進(jìn)行知識遷移。

二維矩形件帶排樣問題的特點(diǎn)是板材寬度確定、高度不限，本文選定板材寬度作為板材型號劃分依據(jù)。上述單源遷移實(shí)驗(yàn)中，源任務(wù)與目標(biāo)任務(wù)所使用板材型號相同。但在實(shí)際生產(chǎn)中，板材型號不止一種，前后排樣任務(wù)可能存在零件相似、板材型號不同的情況，遷移效果可能有所差異。為驗(yàn)證板材相似度對遷移效果的影響，以上述單源遷移實(shí)驗(yàn)中板材寬度為1 000的S1為源任務(wù)，對不同板材寬度的目標(biāo)任務(wù)T的遷移效果做對比分析。由于板材寬度不同，無法直接從排樣高度或利用率的角度來衡量不同型號板材的遷移效果，為更準(zhǔn)確地描述遷移結(jié)果的優(yōu)劣，現(xiàn)對遷移性能TQi作定量描述[13]，如式(11)所示：

(11)

式中：ANT表示無遷移的ACO算法的排樣高度收斂曲線與x軸所圍成的面積，Ai表示各板材型號的排樣高度收斂曲線與x軸所圍成的面積，A0為其他智能算法所求得的最優(yōu)排樣高度y=h0與x軸所圍成的面積，可得各型號板材的遷移效果如表2所示。

表2 不同型號板材遷移效果對比 %

由表2可以看出，同種型號遷移后的板材利用率明顯優(yōu)于遷移之前，從而表明了知識遷移的有效性。同時(shí)可以看出，寬度為1 000的目標(biāo)任務(wù)板材利用率最高，遷移性能也最好，這是由于源任務(wù)S1的板材型號也為1 000，源任務(wù)的經(jīng)驗(yàn)可以較多地被目標(biāo)任務(wù)所借鑒，幫助其提高在線尋優(yōu)能力。比較其他型號的遷移效果，發(fā)現(xiàn)目標(biāo)任務(wù)與源任務(wù)的板材寬度差異越大，遷移效果越不明顯，板材利用率也會有所下降，但仍高于無遷移的板材利用率，這是由于板材寬度差異較大，目標(biāo)任務(wù)只能從源任務(wù)中借鑒少部分的經(jīng)驗(yàn)知識。因此，目標(biāo)任務(wù)在套料時(shí)，要盡可能選擇與源任務(wù)相同或?qū)挾炔町愝^小的板材，以更有效地利用遷移知識。但在實(shí)際生產(chǎn)中，二維矩形件帶排樣問題多用于卷材下料問題，卷材的寬度型號有限，前后相似任務(wù)大都會使用同種型號的板材下料，因此為更有效地驗(yàn)證知識遷移效果，使其在生產(chǎn)中得以應(yīng)用，下述雙源遷移等實(shí)驗(yàn)中，源任務(wù)與目標(biāo)任務(wù)板材型號仍相同。

4.2 實(shí)驗(yàn)2

為驗(yàn)證本文所提雙源遷移設(shè)計(jì)的有效性，現(xiàn)進(jìn)行雙源遷移實(shí)驗(yàn)。單源遷移實(shí)驗(yàn)已證明遷移效果與矩形重疊率有關(guān)，只需比較重疊率最高和最低的源任務(wù)組合即可?，F(xiàn)選取重疊率較高的S1、S2形成遷移算法KTS12，取重疊率較低的S3和S2形成遷移算法KTS23，并將遷移結(jié)果與無遷移的ACO算法以及單源遷移最優(yōu)算法KTS1進(jìn)行比較，如圖7所示。

為更準(zhǔn)確地描述遷移結(jié)果的優(yōu)劣，現(xiàn)對遷移性能TQi作定量描述，借助式(11)求解遷移性能。其中，Ai表示圖7各遷移算法的收斂曲線與x軸所圍成的面積，其余字母含義不變。求得遷移性能如表3所示。

表3 遷移性能對比

由圖7可以看出，無論是單源還是雙源遷移，其收斂速度與結(jié)果明顯優(yōu)于ACO算法，證明了知識遷移的有效性。雖然在迭代初期，單源遷移KTS1的收斂速度快于雙源遷移KTS23，但在收斂階段，KTS23結(jié)果優(yōu)于KTS1。結(jié)合表3可看出，雙源遷移的性能都達(dá)到90%以上，明顯高于單源最優(yōu)遷移結(jié)果的性能80.15%。多源遷移為目標(biāo)任務(wù)的在線學(xué)習(xí)提供了更全面有效的知識，但為了減少無用知識的干擾，降低遷移難度，無需進(jìn)行三源等多源遷移實(shí)驗(yàn)，兩源知識足以為目標(biāo)任務(wù)的優(yōu)化提供充足的經(jīng)驗(yàn)。觀察圖表可以看出，兩個(gè)源任務(wù)與目標(biāo)任務(wù)的矩形重疊率越高，遷移性能越好，KTS12的遷移性能達(dá)到了99.34%。因此，在選擇遷移的知識時(shí)，要選擇更有遷移價(jià)值的兩個(gè)源任務(wù)，以便獲得較優(yōu)的遷移結(jié)果。知識遷移前后效果如圖8所示，深色部分表示板材中沒有被利用的空洞?？梢钥闯鲋R遷移后，空洞部分明顯減少，板材使用高度由776降低到765，提高了板材利用率，也證明了本文提出的KTAQ算法的有效性。

4.3 實(shí)驗(yàn)3

為驗(yàn)證本文算法的有效性，現(xiàn)采用不同規(guī)模的算例對雙源知識遷移算法進(jìn)行測試。與實(shí)驗(yàn)1相同，測試中源任務(wù)和目標(biāo)任務(wù)均從相應(yīng)算例中隨機(jī)選取總零件數(shù)量的3/4，以保證任務(wù)之間的相似性。設(shè)置兩個(gè)源任務(wù)與目標(biāo)任務(wù)的相似度分別為70%和80%。測試算例均從標(biāo)準(zhǔn)算例C21、CX、NICE、N13測試集中選取，經(jīng)過整理得到相應(yīng)的源任務(wù)和目標(biāo)任務(wù)。

遺傳算法和狼群算法作為經(jīng)典和新興智能算法的代表，在求解組合優(yōu)化問題上獲得了廣泛的應(yīng)用，同時(shí)在矩形優(yōu)化排樣問題上也展現(xiàn)出優(yōu)異的性能。為驗(yàn)證KTAQ算法的有效性，現(xiàn)將基于復(fù)合因子評價(jià)的遺傳算法[27]、十進(jìn)制狼群算法[28](Wolf Pack Algorithm，WPA)和ACO算法求解目標(biāo)任務(wù)的結(jié)果與本文KTAQ相比較。各算法優(yōu)化結(jié)果如表4所示，表中h表示排樣高度、t表示計(jì)算時(shí)間(單位：s)加粗字體表示每個(gè)算例的最優(yōu)計(jì)算結(jié)果，所有結(jié)果均取整。

表4 算例優(yōu)化結(jié)果對比

從表4可以看出，對于小規(guī)模算例C61和Nice3，KTAQ算法結(jié)果稍劣于其他3種算法，分析認(rèn)為，源任務(wù)不可能為目標(biāo)任務(wù)提供其所需要的全部知識，目標(biāo)任務(wù)仍需要根據(jù)任務(wù)特點(diǎn)學(xué)習(xí)新知識，并不斷做出權(quán)衡，將遷移知識和新知識融合，這個(gè)過程反而阻礙了小規(guī)模問題快速收斂，使遷移優(yōu)勢不明顯。與ACO算法相比，從第3個(gè)算例起，隨著零件數(shù)目的增加，計(jì)算時(shí)間急劇增長，KTAQ算法的遷移優(yōu)勢便逐漸突顯出來。除了N11算例求得的排樣高度相等以外，KTAQ算法求得的排樣高度均明顯優(yōu)于ACO算法，求解速度基本是ACO的2～6倍，呈現(xiàn)出良好的優(yōu)化性能。這是由于ACO缺乏遷移知識，只能與環(huán)境在線交互積累經(jīng)驗(yàn)，而KTAQ算法在尋優(yōu)過程中得到了相似任務(wù)經(jīng)驗(yàn)知識的指導(dǎo)，因此尋優(yōu)性能大大提高。與智能算法GA、WPA相比，當(dāng)排樣任務(wù)為大中規(guī)模時(shí)(零件數(shù)量達(dá)到100以上)，除算例1 000外，KTAQ算法求解到的排樣高度整體上優(yōu)于前兩個(gè)算法。在算例1 000中，KTAQ算法也有尋得GA算法中最優(yōu)解的能力，但其平均排樣高度稍遜于GA算法，因此算法的尋優(yōu)穩(wěn)定性還有改進(jìn)的空間。從求解速度上來看，KTAQ算法的速度基本上能達(dá)到GA、WPA算法的2～6倍，能滿足大中規(guī)模零件快速尋優(yōu)的要求。

上述算例中KTAQ算法板材的利用率都能達(dá)到96%以上，具有較好的實(shí)用性。整體來說，KTAQ算法在保證較高質(zhì)量解的同時(shí)，尋優(yōu)時(shí)間大幅縮減，證明了本文提出的基于知識遷移的蟻群強(qiáng)化學(xué)習(xí)算法的有效性。

5 結(jié)束語

本文將知識遷移引入到基于強(qiáng)化學(xué)習(xí)的蟻群算法中，提出了KTAQ算法，并將其應(yīng)用到矩形優(yōu)化排樣中。在大中規(guī)模矩形優(yōu)化排樣問題上，該算法能在獲得高質(zhì)量解的基礎(chǔ)上，求解速度達(dá)到普通智能算法的2～6倍，可以有效降低求解時(shí)間，提高尋優(yōu)性能。本文的創(chuàng)新點(diǎn)可歸納如下：

(1)借鑒Q-learning的試錯(cuò)學(xué)習(xí)模式構(gòu)造具有自學(xué)習(xí)能力的螞蟻群體，并建立基于局部調(diào)整算子的知識更新策略和知識利用探索權(quán)衡的動作選擇策略，加速蟻群知識空間的形成，并在此基礎(chǔ)上實(shí)現(xiàn)知識的學(xué)習(xí)、遷移和再利用。

(2)針對矩形排樣問題知識空間出現(xiàn)的“維數(shù)爆炸”情況，提出基于知識延伸的高維空間合并方法，極大地降低了計(jì)算難度，使之更適應(yīng)大規(guī)模矩形排樣問題求解。

(3)提出基于匹配度評價(jià)的最低水平線法，結(jié)合動作選擇策略中的優(yōu)先考慮排入零件面積及長寬比較大的矩形，使矩形排入板材時(shí)充分利用了板材空隙，提高了板材利用率。

(4)提出雙源線性遷移策略，對最相似的兩個(gè)源任務(wù)用線性組合的方式遷移知識，仿真實(shí)驗(yàn)也對提出的雙源線性遷移策略的有效性進(jìn)行了驗(yàn)證。

此外，在遷移尋優(yōu)過程中，求解的穩(wěn)定性還可以進(jìn)一步提高；仍需要對遷移算法進(jìn)行改進(jìn)，使之適宜求解有復(fù)雜約束的矩形排樣問題。同時(shí)，將知識遷移、強(qiáng)化學(xué)習(xí)與智能算法相結(jié)合，用于求解旅行商、車間調(diào)度等其他組合優(yōu)化問題，也是筆者下一步研究的重點(diǎn)。