遷移蟻群強(qiáng)化學(xué)習(xí)算法及其在矩形排樣中的應(yīng)用

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

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

0 引言

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

蟻群強(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)格資源分配問(wèn)題中引入了強(qiáng)化學(xué)習(xí)和蟻群算法，文中首先使用Sarsa算法初始化各節(jié)點(diǎn)信息素資源分配，再借助蟻群算法進(jìn)一步尋優(yōu)。但兩篇文獻(xiàn)都是將強(qiáng)化學(xué)習(xí)作為信息初始化算法，沒(méi)有借助強(qiáng)化學(xué)習(xí)的優(yōu)勢(shì)提高單只螞蟻的尋優(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)和知識(shí)，需重新開始搜索優(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)和知識(shí)。機(jī)器學(xué)習(xí)中的知識(shí)遷移[12](Knowledge Transfer，KT)具有模擬人類思維的特點(diǎn)，旨在根據(jù)任務(wù)之間的相似性，利用已有知識(shí)和經(jīng)驗(yàn)，幫助新相似任務(wù)減少學(xué)習(xí)時(shí)間，提高尋優(yōu)性能。在實(shí)際工程問(wèn)題中，文獻(xiàn)[13]通過(guò)貝葉斯理論計(jì)算源任務(wù)與目標(biāo)任務(wù)的相似度，從中篩選合適的樣本遷移，但當(dāng)任務(wù)規(guī)模增大時(shí)，需要耗費(fèi)大量的時(shí)間計(jì)算相似度與篩選合適遷移樣本；文獻(xiàn)[14-16]分別將知識(shí)遷移引入到電力系統(tǒng)的無(wú)功優(yōu)化、風(fēng)險(xiǎn)調(diào)度、多能源聯(lián)合優(yōu)化調(diào)度問(wèn)題中，將Q-learning與群智能算法結(jié)合構(gòu)造試錯(cuò)學(xué)習(xí)模式，通過(guò)狀態(tài)—組合鏈實(shí)現(xiàn)大規(guī)模任務(wù)降維，并借助知識(shí)遷移技術(shù)實(shí)現(xiàn)智能群體的遷移學(xué)習(xí)。該算法適用于大規(guī)模電力系統(tǒng)問(wèn)題快速求解，但目前尚未有將知識(shí)遷移應(yīng)用于矩形排樣方面的研究。

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

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

由于生產(chǎn)工藝的要求和加工條件的限制，不同領(lǐng)域的優(yōu)化下料問(wèn)題對(duì)應(yīng)不同的數(shù)學(xué)模型[17-18]。本文所研究的矩形排樣問(wèn)題為二維矩形件帶排樣問(wèn)題(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問(wèn)題要滿足以下約束條件：①矩形零件不超出板材邊界；②任意矩形零件之間不相互重疊；③矩形零件允許90度旋轉(zhuǎn)；④矩形零件的邊需與板材邊界平行。如圖1所示為10個(gè)矩形排樣的實(shí)例，灰色部分表示不能利用的空洞。

Hmax表示矩形零件排放完成之后最高輪廓線所對(duì)應(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)識(shí)碼，一個(gè)完整的整數(shù)序列即對(duì)應(yīng)一個(gè)可行的排樣方案。求解矩形優(yōu)化排樣問(wèn)題的關(guān)鍵在于零件的定序和定位算法。定序算法是搜索一組最優(yōu)的矩形排樣順序，目標(biāo)是調(diào)用定位算法解碼后的板材利用率最大；定位算法是對(duì)搜索到的序列進(jìn)行解碼，由算法中的定位規(guī)則確定零件在板材中的具體排放位置，由此生成排樣圖，并計(jì)算板材利用率即適應(yīng)度值。本文采用KTAQ算法搜索零件排入序列，用基于匹配度評(píng)價(jià)的最低水平線法進(jìn)行零件定位，將矩形零件排入板材最低輪廓線。

2 KTAQ算法原理

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

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

2.1.1 知識(shí)獲取方式

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

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

2.1.2 知識(shí)空間分解降維

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

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

2.1.3 知識(shí)更新策略

KTAQ算法中所有螞蟻都根據(jù)初始矩陣對(duì)食物環(huán)境進(jìn)行試錯(cuò)學(xué)習(xí)，并將環(huán)境獎(jiǎng)勵(lì)反饋給知識(shí)矩陣。單次迭代循環(huán)內(nèi)，當(dāng)螞蟻完成一條完整路徑的構(gòu)造(即產(chǎn)生一個(gè)可行的排樣序列)，為加深對(duì)優(yōu)秀解鄰域的探討，同時(shí)避免知識(shí)的學(xué)習(xí)進(jìn)入停滯階段，本文設(shè)計(jì)局部調(diào)整算子對(duì)已生成的排樣序列進(jìn)行調(diào)整，過(guò)程如下：設(shè)螞蟻數(shù)量為m，計(jì)算每只螞蟻對(duì)應(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知識(shí)矩陣，大大加快了學(xué)習(xí)尋優(yōu)的速度[22]。每次試錯(cuò)學(xué)習(xí)后，KTAQ算法會(huì)對(duì)本次迭代內(nèi)序列適應(yīng)度值最高的螞蟻進(jìn)行獎(jiǎng)勵(lì)，并更新知識(shí)矩陣。其他序列對(duì)應(yīng)的知識(shí)只執(zhí)行揮發(fā)操作。矩陣元素更新操作如式(4)所示：

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

(4)

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

2.1.4 動(dòng)作選擇策略

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

a=

(5)

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

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

(6)

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

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

(7)

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

2.2 KTAQ知識(shí)遷移方式

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

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

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

2.3 KTAQ算法流程

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

3 矩形排樣求解

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

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

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

(8)

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

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

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

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

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

具體排樣步驟如下：

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

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

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

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

KTAQ算法遷移效果優(yōu)劣的關(guān)鍵在于是否將合適的知識(shí)遷移到目標(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í)需要的是描述矩形與矩形間密切程度的知識(shí)，而與其矩形重疊率高的源任務(wù)正可以提供較多的知識(shí)供其學(xué)習(xí)。

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

(10)

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

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

在KTAQ算法中，對(duì)學(xué)習(xí)和尋優(yōu)效果影響較大的參數(shù)主要有蟻群規(guī)模m、學(xué)習(xí)因子α、折扣因子γ、知識(shí)經(jīng)驗(yàn)參數(shù)ε0、環(huán)境獎(jiǎng)勵(lì)系數(shù)ER。經(jīng)過(guò)多次仿真實(shí)驗(yàn)，發(fā)現(xiàn)各參數(shù)對(duì)尋優(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)折扣因子γ對(duì)歷史獎(jiǎng)勵(lì)值的折扣程度，γ值越大，表示對(duì)當(dāng)前獎(jiǎng)勵(lì)越重視，本文兩個(gè)階段都取值0.9。

(4)知識(shí)經(jīng)驗(yàn)參數(shù)ε0表示蟻群利用經(jīng)驗(yàn)知識(shí)和隨機(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)境獎(jiǎng)勵(lì)系數(shù)ER代表環(huán)境對(duì)最優(yōu)解的獎(jiǎng)勵(lì)。本文統(tǒng)一設(shè)置ER為500。

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

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

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

本實(shí)驗(yàn)采用NICE測(cè)試集中的nice5問(wèn)題進(jìn)行矩形優(yōu)化排樣問(wèn)題研究。為保證任務(wù)之間的相似性，便于遷移動(dòng)作的展開，本文中的源任務(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%。

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

由圖6可以發(fā)現(xiàn)，ACO在初期搜尋和后期收斂階段的尋優(yōu)性能均劣于其他3種算法，并且陷入了局部最優(yōu)。這是由于目標(biāo)任務(wù)缺乏經(jīng)驗(yàn)知識(shí)，只得在與環(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)越多，遷移知識(shí)被利用的程度越高，因而減少了目標(biāo)任務(wù)在線尋優(yōu)的盲目性。因此，為提高遷移性能，應(yīng)盡可能選擇重疊率高的源任務(wù)進(jìn)行知識(shí)遷移。

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

(11)

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

表2 不同型號(hào)板材遷移效果對(duì)比 %

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

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é)果與無(wú)遷移的ACO算法以及單源遷移最優(yōu)算法KTS1進(jìn)行比較，如圖7所示。

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

表3 遷移性能對(duì)比

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

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

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

遺傳算法和狼群算法作為經(jīng)典和新興智能算法的代表，在求解組合優(yōu)化問(wèn)題上獲得了廣泛的應(yīng)用，同時(shí)在矩形優(yōu)化排樣問(wèn)題上也展現(xiàn)出優(yōu)異的性能。為驗(yàn)證KTAQ算法的有效性，現(xiàn)將基于復(fù)合因子評(píng)價(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é)果對(duì)比

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

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

5 結(jié)束語(yǔ)

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

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

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

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

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

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