基于Q—學(xué)習(xí)的超啟發(fā)式模型及算法求解多模式資源約束項(xiàng)目調(diào)度問(wèn)題

崔建雙，呂 玥，徐子涵

(北京科技大學(xué) 經(jīng)濟(jì)管理學(xué)院，北京 100083)

0 引言

在以人工智能、生物信息科學(xué)以及智能決策為代表的眾多學(xué)科領(lǐng)域中存在著大量的以大規(guī)模、多模態(tài)、非連續(xù)性為特征的組合優(yōu)化問(wèn)題，針對(duì)這類問(wèn)題，傳統(tǒng)的運(yùn)籌優(yōu)化方法難以奏效，因而多采用啟發(fā)式或元啟發(fā)式算法加以解決。這類方法大多基于直觀經(jīng)驗(yàn)或模擬自然現(xiàn)象，通過(guò)嵌入隨機(jī)性因子，利用進(jìn)化、群集、仿生等啟發(fā)式技術(shù)，結(jié)合廣域探查和局域搜索策略，在可接受的時(shí)空條件下獲得問(wèn)題的近優(yōu)解。多年來(lái)先后涌現(xiàn)出許多優(yōu)秀的元啟發(fā)式算法，如遺傳、進(jìn)化、模擬退火、禁忌搜索、蟻群、粒子群、人工蜂群、人工免疫、混合蛙跳、人工魚(yú)群等算法[1]。

在各種優(yōu)化算法的應(yīng)用實(shí)踐中，不難觀察到如下現(xiàn)象：

(1)同一種算法對(duì)于類型相近的問(wèn)題或類型相同但數(shù)據(jù)不同的算例，在效率和效果上差異很大。為達(dá)到理想的優(yōu)化目標(biāo)，人們不得不進(jìn)行算法定制。基于個(gè)人經(jīng)驗(yàn)、嘗試不同的參數(shù)、拓?fù)浣Y(jié)構(gòu)和搜索策略，缺乏理論層次的指導(dǎo)，導(dǎo)致算法應(yīng)用成本居高不下。

(2)雖然不同算法的尋優(yōu)策略各有千秋，但許多算法展現(xiàn)出相同或相似的實(shí)現(xiàn)機(jī)制，例如：受自然現(xiàn)象啟發(fā)、利用群集智能、包含隨機(jī)成分、不使用梯度信息、有若干可調(diào)參數(shù)等。這些現(xiàn)象無(wú)疑為開(kāi)發(fā)通用型算法、實(shí)現(xiàn)算法軟件重用、轉(zhuǎn)換即用型算法等需求提供了契機(jī)。人們有理由提出并嘗試各種算法融合技術(shù)，研發(fā)一類適應(yīng)性更強(qiáng)且結(jié)果令人接受的超啟發(fā)式算法。目前，在優(yōu)化算法研究領(lǐng)域出現(xiàn)的諸如自適應(yīng)技術(shù)[2]、通用算法軟件框架[3]、混合元啟發(fā)式[4]、超啟發(fā)式[5]、優(yōu)化算法推薦[6]、算法合成[7]等方法和技術(shù)無(wú)不以此為目標(biāo)，寄希望于通過(guò)算法的自動(dòng)動(dòng)態(tài)匹配或混合技術(shù)，降低定制成本，改善應(yīng)用效果。其中，超啟發(fā)式(hyper-heuristic)算法與技術(shù)已成為當(dāng)前一大研究熱點(diǎn)。超啟發(fā)式算法通過(guò)自動(dòng)選擇或生成一組啟發(fā)式過(guò)程來(lái)解決各種優(yōu)化問(wèn)題，除了提升算法解決問(wèn)題的效率之外，更重要的是追求算法的通用性和自適應(yīng)性[8]。

本文提出一種基于強(qiáng)化學(xué)習(xí)技術(shù)的超啟發(fā)式模型(Reinforcement Learning based Hyper-Heuristic Model, RLHM)，并在此基礎(chǔ)上實(shí)現(xiàn)了一種基于Q—學(xué)習(xí)的超啟發(fā)式算法。強(qiáng)化學(xué)習(xí)是機(jī)器學(xué)習(xí)的一個(gè)重要分支，通過(guò)與環(huán)境交互獲得經(jīng)驗(yàn)，量化為獎(jiǎng)懲值并根據(jù)獎(jiǎng)懲值來(lái)決定進(jìn)一步的執(zhí)行動(dòng)作。在RLHM中，設(shè)計(jì)了高層啟發(fā)式組件對(duì)低層啟發(fā)式(Low Level Heuristic, LLH)算子的選擇和移動(dòng)接受策略。其中，LLH算子初步選擇了經(jīng)典的禁忌搜索(Tabu Search, TS)、粒子群優(yōu)化(Particle Swarm Optimization，PSO)、人工蜂群(Artificial Bee Colony，ABC)和蟻群系統(tǒng)(Ant Colony System，ACS)四種具有異構(gòu)機(jī)制的元啟發(fā)式算子，并預(yù)留了靈活方便的擴(kuò)展接口，包括同類算法不同參數(shù)的擴(kuò)展和不同算法算子的擴(kuò)展。高層策略使用Q—學(xué)習(xí)通過(guò)獎(jiǎng)懲機(jī)制來(lái)對(duì)LLH算子和狀態(tài)組合進(jìn)行選擇，在本文中，不同的狀態(tài)對(duì)應(yīng)不同的接受準(zhǔn)則，LLH算子為下一步執(zhí)行的動(dòng)作，Q—學(xué)習(xí)作為高層策略選擇的不單是LLH算子，而是狀態(tài)—?jiǎng)幼鹘M合，通過(guò)對(duì)狀態(tài)—?jiǎng)幼鹘M合的選擇，使算法趨向于針對(duì)不同算例選擇適合的動(dòng)作，提高算法應(yīng)用的效果。

本文設(shè)計(jì)的超啟發(fā)式算法在LLH算子選擇上采用元啟發(fā)式算法，而非簡(jiǎn)單的交叉變異算子，因此LLH算子具有相對(duì)獨(dú)立性，同時(shí)具備不依賴于特定問(wèn)題的通用性。首先，其尋優(yōu)機(jī)制的區(qū)別有益于實(shí)現(xiàn)大范圍多樣化搜索，充分利用TS大規(guī)模鄰域搜索能力、大范圍調(diào)節(jié)的PSO粒子飛行速度和位置、ABC良好的個(gè)體淘汰機(jī)制、ACS構(gòu)建性的概率選擇特長(zhǎng)等；其次，不同組合優(yōu)化問(wèn)題的編碼作為低層算子的基本組件可以預(yù)先確定，轉(zhuǎn)換問(wèn)題僅需要變換不同的編碼組件；再次，LLH算子的擴(kuò)充簡(jiǎn)單易行，如增加進(jìn)化算子、模擬退火算子、異參算子等。算法利用Q—學(xué)習(xí)機(jī)制智能化地從低層多種元啟發(fā)式算子中擇優(yōu)使用，充分發(fā)揮算子異構(gòu)機(jī)制的多樣性特征，實(shí)現(xiàn)了超啟發(fā)式的概念。

為檢驗(yàn)RLHM的應(yīng)用效果，從多模式資源約束的項(xiàng)目調(diào)度問(wèn)題(Multi-mode Resource-Constrained Project Scheduling Problem，MRCPSP)標(biāo)桿算例庫(kù)中選取1 608個(gè)不同規(guī)模的問(wèn)題算例，與公開(kāi)文獻(xiàn)計(jì)算結(jié)果進(jìn)行比較。實(shí)驗(yàn)結(jié)果充分表明了RLHM的競(jìng)爭(zhēng)力和推廣價(jià)值。

1 超啟發(fā)式算法與Q—學(xué)習(xí)機(jī)制

1.1 超啟發(fā)式算法文獻(xiàn)綜述

超啟發(fā)式算法的提出源于各類啟發(fā)式和元啟發(fā)式算法存在的不足。正如引言中所指出的那樣，不同算法各有優(yōu)勢(shì)和劣勢(shì)，同時(shí)每一個(gè)具體問(wèn)題都存在著算法“偏好”。超啟發(fā)式算法的動(dòng)機(jī)之一就是開(kāi)發(fā)更普遍適用的算法，通過(guò)自動(dòng)化設(shè)計(jì)和調(diào)整啟發(fā)式算子更高效地解決搜索計(jì)算問(wèn)題[5]。與手動(dòng)算法定制不同，超啟發(fā)式算法可被視為根據(jù)問(wèn)題自動(dòng)化定制算法[9]。因此，一個(gè)重要的目標(biāo)是其通用性，基于一組易于實(shí)現(xiàn)的低級(jí)啟發(fā)式方法生成質(zhì)量可接受的解決方案[10]。

“超啟發(fā)式”一詞最早由DENZINGER等[11]提出，后由COWLING等[12]給出實(shí)質(zhì)性定義。事實(shí)上，上世紀(jì)60年代超啟發(fā)式思想已初露端倪，涉及到運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)和人工智能等研究領(lǐng)域。代表性的研究成果表現(xiàn)在自動(dòng)啟發(fā)式排序[13]、自動(dòng)規(guī)劃系統(tǒng)[14-15]、進(jìn)化算法中的自動(dòng)參數(shù)控制[16]和自動(dòng)學(xué)習(xí)啟發(fā)式方法[17]等。早期階段(2000年之前)的超啟發(fā)式偏重于啟發(fā)式自動(dòng)設(shè)計(jì)，強(qiáng)調(diào)若干啟發(fā)式規(guī)則或方法的組合優(yōu)于僅使用單個(gè)獨(dú)立的規(guī)則或方法。2000年之后，人們對(duì)超啟發(fā)式算法的認(rèn)識(shí)漸趨完善，陸續(xù)出現(xiàn)一些關(guān)于超啟發(fā)式的綜述性文獻(xiàn)，BURKE等[8-9]和DRAKE等[10]歸納了超啟發(fā)式算法的分類及研究現(xiàn)狀(如圖1)。超啟發(fā)式本質(zhì)上具有“學(xué)習(xí)”能力，其“學(xué)習(xí)”的含義在于算法能夠從當(dāng)前運(yùn)行結(jié)果獲得經(jīng)驗(yàn)，并向著有利于解決問(wèn)題的方向調(diào)整。根據(jù)學(xué)習(xí)過(guò)程中反饋信息的來(lái)源，超啟發(fā)式可以分為“在線”和“離線”學(xué)習(xí)。前者依據(jù)即時(shí)狀態(tài)提供的信息決定下一步的搜索走向，后者則依據(jù)以往經(jīng)驗(yàn)決定下一步的搜索走向。

從目前公開(kāi)發(fā)表的文獻(xiàn)來(lái)看，大多數(shù)研究屬于在線擾動(dòng)(或稱移動(dòng))的選擇啟發(fā)式，其模型由兩個(gè)層次組成，如圖2所示。低層包含問(wèn)題的表示、評(píng)估函數(shù)和一組特定于問(wèn)題的LLH算子，通過(guò)啟發(fā)式擾動(dòng)修改當(dāng)前解；高層則控制LLH算子選擇并依據(jù)既定規(guī)則判斷是否接受所作的擾動(dòng)選擇[18-19]?？捎玫腖LH算子選擇方法包括簡(jiǎn)單隨機(jī)、選擇函數(shù)、禁忌搜索和強(qiáng)化學(xué)習(xí)等，而移動(dòng)接受策略則包括僅改進(jìn)、任何移動(dòng)、Metropolis條件、模擬退火、延遲和Naive等[20-23]。在現(xiàn)實(shí)應(yīng)用方面，超啟發(fā)式算法已經(jīng)取得了令人鼓舞的成果。文獻(xiàn)[24]提出基于大洪水(Great Deluge，GD)策略的超啟發(fā)式算法解決考試時(shí)間表問(wèn)題；文獻(xiàn)[25]用于解決城市公交路線問(wèn)題(Urban Transit Routing Problem,UTRP)；文獻(xiàn)[26]提出一種基于隨機(jī)自動(dòng)機(jī)網(wǎng)絡(luò)的超啟發(fā)式方法，該網(wǎng)絡(luò)具有學(xué)習(xí)功能，可控制一組元啟發(fā)式方法展開(kāi)搜索。

1.2 強(qiáng)化學(xué)習(xí)與Q—學(xué)習(xí)

強(qiáng)化學(xué)習(xí)主要解決序貫決策問(wèn)題。Q—學(xué)習(xí)是強(qiáng)化學(xué)習(xí)算法之一，專注于從交互中進(jìn)行以目標(biāo)為導(dǎo)向的學(xué)習(xí)。Q—學(xué)習(xí)過(guò)程主要包含學(xué)習(xí)體的3個(gè)聯(lián)動(dòng)元素：狀態(tài)(state)、動(dòng)作(action)和獎(jiǎng)勵(lì)(reward)，以獲得最多累計(jì)獎(jiǎng)勵(lì)為目標(biāo)。在沒(méi)有任何先驗(yàn)信息的情況下，首先嘗試做出一個(gè)動(dòng)作得到反饋結(jié)果，根據(jù)反饋結(jié)果來(lái)調(diào)整下一步的動(dòng)作，在該過(guò)程中選擇特定情境下得到最大回報(bào)的動(dòng)作。

假設(shè)S= [s1,s2, …,sn]表示學(xué)習(xí)體的n種可能的狀態(tài)；A= [a1,a2,…,am]表示m個(gè)可能的動(dòng)作。學(xué)習(xí)體在時(shí)刻t從狀態(tài)st執(zhí)行動(dòng)作at之后進(jìn)入新?tīng)顟B(tài)st+1，rt+1表示即時(shí)強(qiáng)化信號(hào)，即采取動(dòng)作at后獲得的獎(jiǎng)勵(lì)值(可正可負(fù))。令α∈[0,1]表示用于權(quán)衡舊狀態(tài)影響程度的學(xué)習(xí)率，該值越大，表明越重視以往學(xué)習(xí)的效果；γ∈[0,1]表示折扣因子，用于權(quán)衡獎(jiǎng)勵(lì)值對(duì)于新?tīng)顟B(tài)的影響程度，該值越大，表明越重視當(dāng)前學(xué)習(xí)的效果。Q(st,at) 表示時(shí)刻t的Q值。將每個(gè)狀態(tài)—?jiǎng)幼鲗?duì)執(zhí)行結(jié)束后被給予的Q值，記錄在Q表中，通過(guò)如下Q函數(shù)式計(jì)算獲得：

Qt+1(st,at)=(1-α)Q(st,at)+

α[rt+1+γmaxaQ(st+1,a)]。

Q—學(xué)習(xí)已被廣泛用于各種能夠從反饋中獲得信息的應(yīng)用場(chǎng)合。例如，目標(biāo)轉(zhuǎn)移Q—學(xué)習(xí)(Target Transfer Q-Learning, TTQL)[27]、超啟發(fā)式算法自動(dòng)設(shè)計(jì)[28]、機(jī)器人導(dǎo)航[29]、智能民居能源優(yōu)化管理[30]、智能游戲控制[31]、動(dòng)態(tài)跟蹤控制[32]等。

1.3 超啟發(fā)式與Q—學(xué)習(xí)

把Q—學(xué)習(xí)的獎(jiǎng)懲機(jī)制與超啟發(fā)式思想結(jié)合，通過(guò)評(píng)價(jià)低層算子的表現(xiàn)來(lái)決定下一步的算子選擇，就可以實(shí)現(xiàn)基于Q—學(xué)習(xí)的超啟發(fā)式算法。不少超啟發(fā)式算法文獻(xiàn)用到了Q—學(xué)習(xí)策略，但并未明確提及Q—學(xué)習(xí)。

SIM等[33]提出基于強(qiáng)化學(xué)習(xí)和禁忌搜索的模擬退火超啟發(fā)式算法；?ZCAN等[23]提出一種超啟發(fā)式模型，利用所謂的“大洪水”策略作為移動(dòng)接受方法；ZAMLI等[22]提出一種混合T—路測(cè)試生成策略，采用禁忌搜索作為其高級(jí)元啟發(fā)式，并利用4種低級(jí)元啟發(fā)自適應(yīng)選擇最合適的算法；FERREIRA等[35]提出一種“多臂強(qiáng)盜”選擇機(jī)制策略(Multi-Arm Bandit, MAB)，使用CHeSC 2011[3]挑戰(zhàn)賽改編的方法與其他20種超啟發(fā)式方法進(jìn)行了比較，其結(jié)果可以與挑戰(zhàn)賽中最優(yōu)超啟發(fā)式方法獲得的結(jié)果相媲美；DI GASPERO等[36]也提出了一種遵循Q—學(xué)習(xí)標(biāo)準(zhǔn)的超啟發(fā)式模型，研究了立即強(qiáng)化方案的一些變體以及選擇策略和學(xué)習(xí)函數(shù)的影響，提供了一類獨(dú)特的狀態(tài)和動(dòng)作表示；MOSADEGH等[37]開(kāi)發(fā)了一種超模擬退火算法，該算法使用Q—學(xué)習(xí)策略來(lái)選擇啟發(fā)式；張景玲等[34]設(shè)計(jì)了一種基于強(qiáng)化學(xué)習(xí)的超啟發(fā)算法求解有容量車輛路徑問(wèn)題，算法使用強(qiáng)化學(xué)習(xí)中的深度Q神經(jīng)網(wǎng)絡(luò)算法構(gòu)造選擇策略，總體求解效果優(yōu)于對(duì)比算法。

嚴(yán)格地看，Q—學(xué)習(xí)機(jī)制滿足兩個(gè)重要特征，即通過(guò)試錯(cuò)(trial-and-error)和延遲獎(jiǎng)勵(lì)(delayed reward)反復(fù)探索來(lái)實(shí)現(xiàn)自動(dòng)化的與問(wèn)題無(wú)關(guān)的搜索。相對(duì)于算法定制方法，基于Q—學(xué)習(xí)機(jī)制的超啟發(fā)式算法的效率不一定更好，但其效果往往更佳，最主要的優(yōu)點(diǎn)是摒棄了算法定制，提高了算法通用性水平。

2 RLHM及算法的實(shí)現(xiàn)

RLHM及其算法的實(shí)現(xiàn)基于如下兩個(gè)目標(biāo)：①算法具備不依賴于特定問(wèn)題的通用性；②其尋優(yōu)機(jī)制確保能夠?qū)崿F(xiàn)大范圍、多樣化的全局搜索和小范圍的精細(xì)搜索。這兩個(gè)目標(biāo)都能夠通過(guò)低層算子加以保證，因?yàn)檫@些算子都不是基于特定問(wèn)題的啟發(fā)式算法，而是通用性很強(qiáng)的元啟發(fā)式算法。其搜索機(jī)理可以簡(jiǎn)單地表述為：利用Q—學(xué)習(xí)機(jī)制智能化地從低層元啟發(fā)式算子群中擇優(yōu)使用，充分發(fā)揮群算子異構(gòu)機(jī)制的多樣化。多種優(yōu)秀的元啟發(fā)式算法與反饋—學(xué)習(xí)強(qiáng)化機(jī)制有機(jī)地整合在一起，具備靈活的可擴(kuò)展性。

2.1 RLHM框架

在如圖2所示模型的基礎(chǔ)上，本文引入高層Q—學(xué)習(xí)策略之后得到如圖3所示的RLHM框架。其中：低層預(yù)留了可擴(kuò)展的算子接口，預(yù)設(shè)了多種組合優(yōu)化問(wèn)題編碼和評(píng)估函數(shù)；高層針對(duì)Q表設(shè)計(jì)了可擴(kuò)展的多種接受策略。為了增加多樣性，接受策略采用隨機(jī)選擇方式獲得，一旦選中了一種接受策略，就會(huì)根據(jù)低層評(píng)估函數(shù)提供的計(jì)算結(jié)果和全域最大Q值更新Q表，并進(jìn)入下一輪動(dòng)作(算子)選擇。

2.2 狀態(tài)—?jiǎng)幼鹘M合對(duì)

狀態(tài)和動(dòng)作是強(qiáng)化學(xué)習(xí)的兩個(gè)要素，通過(guò)執(zhí)行狀態(tài)和動(dòng)作的組合獲得獎(jiǎng)勵(lì)，并幫助算法趨向選擇回報(bào)最大的動(dòng)作。將執(zhí)行LLH算子看成是動(dòng)作Action，把執(zhí)行LLH算子之后的改進(jìn)與否看成是狀態(tài)State。僅改進(jìn)接受和Naive接受是兩種接受策略，前者要求計(jì)算結(jié)果有所改進(jìn)才接受，拒絕未改進(jìn)結(jié)果；后者則除了接受改進(jìn)結(jié)果之外，以50%的概率接受未改進(jìn)結(jié)果。如表1所示為RLHM算法中的接受策略。

表1 RLHM的接受策略

2.3 RLHM算法流程

RLHM算法流程參見(jiàn)算法1。為了使算法不陷入局優(yōu)并增加全局搜索能力，在根據(jù)Q值大小選擇狀態(tài)—?jiǎng)幼鹘M合對(duì)時(shí)，采用了有保留的貪婪機(jī)制，即選擇maxQ(S,A)狀態(tài)下對(duì)應(yīng)的動(dòng)作，但若maxQ(S,A)<ε，則隨機(jī)選擇該狀態(tài)下的一個(gè)動(dòng)作，其中ε=0.3。狀態(tài)—?jiǎng)幼鲗?duì)確定后按照選擇的動(dòng)作執(zhí)行優(yōu)化，并及時(shí)更新最優(yōu)值。下一步狀態(tài)的確定根據(jù)執(zhí)行當(dāng)前狀態(tài)—?jiǎng)幼鲗?duì)后得到的解是否有所改進(jìn)作為判斷依據(jù)。Q值的更新按照前面給出的Q函數(shù)式執(zhí)行。若優(yōu)化后的種群得到改進(jìn)，則給予獎(jiǎng)勵(lì)值r=10；否則，令r-2→r。重復(fù)以上迭代過(guò)程，直到可行解數(shù)量達(dá)到規(guī)定值(實(shí)驗(yàn)中設(shè)定為5 000次)為止。

算法1RLHM算法。

1: Initialization()

GlobalValue=min(fitnessinitial)

initial-state()和initial-action()

%隨機(jī)指定一個(gè)初始狀態(tài)和動(dòng)作

2: While !Termination-Criteria Do

3: Select() %根據(jù)當(dāng)前狀態(tài)下Q值大小選擇動(dòng)作

4: Execution() %執(zhí)行狀態(tài)—?jiǎng)幼鹘M合

5: Update-Global-Value() %更新全局目標(biāo)最優(yōu)解

6: Determine-Next-State() %確定下一步狀態(tài)

7: Update Q-value() %根據(jù)Q函數(shù)式更新Q表

8: End While

2.4 可行解數(shù)量的確定

算法1中的Execution()是執(zhí)行LLH算子的過(guò)程。由于不同LLH算子的實(shí)現(xiàn)機(jī)制不同，完整地執(zhí)行一次LLH算子所需時(shí)間不同。為了增加算法的多樣性，使算法不至于過(guò)早收斂或陷入局優(yōu)，每個(gè)LLH算子可設(shè)為運(yùn)行有限的時(shí)間或者迭代次數(shù)。本算法將其設(shè)置為執(zhí)行每個(gè)LLH算子時(shí)記錄生成可行解的數(shù)量，達(dá)到規(guī)定數(shù)量后無(wú)條件跳出執(zhí)行。

為便于與其他文獻(xiàn)結(jié)果作出比較，本文通過(guò)實(shí)驗(yàn)確定無(wú)論執(zhí)行哪一種LLH算子，每次可行解數(shù)量≤100，控制每個(gè)算例累計(jì)總可行解數(shù)量不超過(guò)5 000次。

2.5 LLH算子的設(shè)計(jì)

傳統(tǒng)超啟發(fā)式算法的LLH算子采用簡(jiǎn)單啟發(fā)式序列，多依賴于問(wèn)題，從而影響了算法的廣泛適用性。RLHM的低層LLH算子均采用相對(duì)獨(dú)立模塊化的元啟發(fā)式算法，并可根據(jù)問(wèn)題需要隨時(shí)擴(kuò)充新的算法模塊。例如，可以根據(jù)需要隨時(shí)給定TS算法的不同參數(shù)，一組新的參數(shù)可以看成是一種新的算法。也可以增加新的元啟發(fā)式算子，每一個(gè)新算法都是一個(gè)新的動(dòng)作，Q表的規(guī)模也會(huì)隨之?dāng)U大。針對(duì)相同的問(wèn)題采用相同的編碼格式，可大大提升算法的通用性。

RLHM算法初始集成了TS、PSO、ABC和ACS四種元啟發(fā)式算法模塊，各LLH算法參數(shù)設(shè)計(jì)如下：

(1)TS。TS的基礎(chǔ)是鄰域搜索算法。禁忌對(duì)象2-opt或3-opt鄰域交換；限定鄰域解最大數(shù)量、破禁策略、禁忌表長(zhǎng)等參數(shù)。

(2)PSO。使用標(biāo)準(zhǔn)粒子群算法公式，參數(shù)學(xué)習(xí)因子c1、c2，慣性權(quán)重ω。本文粒子速度和位置的更新方式采用JARBOUI等[38]提出的方法。

(3)ABC。設(shè)計(jì)蜜蜂角色變換上限值Limit參數(shù)是關(guān)鍵，超過(guò)上限值予以淘汰。下一代蜂群的選擇采用輪盤賭方式。

(4)ACS。本文在黃少榮[39]提出的蟻群算法基礎(chǔ)上進(jìn)行了改進(jìn)。參數(shù)ρ、α、β和Q可調(diào)節(jié)，殘留信息素更新采用蟻周模型。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 MRCPSP的定義

minsn+2。

(1)

s.t.

si+di,mi≤sj， ?(i,j)∈E；

(2)

(3)

(4)

mi∈Mi={i=1,…,|Mi|},?i∈N；

(5)

s0=0；

(6)

si=int+，?i∈N。

(7)

其中：式(1)表示最小化項(xiàng)目工期；式(2)表示活動(dòng)之間遵從完成—開(kāi)始時(shí)間約束關(guān)系，式中di,mi為活動(dòng)i取模式mi時(shí)的執(zhí)行時(shí)間；式(3)和式(4)分別表示可再生和不可再生資源約束；式(5)確保每一活動(dòng)僅取一種模式；式(6)要求項(xiàng)目開(kāi)始時(shí)間為0；式(7)假定所有活動(dòng)的開(kāi)始時(shí)間均為非負(fù)整數(shù)。

過(guò)去多年來(lái)，針對(duì)該NP—難問(wèn)題已經(jīng)提出了許多求解方法[41]。SPRECHER等[42]曾使用以分支定界為代表的精確算法求解該問(wèn)題，但受搜索空間的制約，難以在合理的時(shí)間內(nèi)解決規(guī)模較大的問(wèn)題(迄今為止部分活動(dòng)數(shù)量超過(guò)30的問(wèn)題仍處于開(kāi)放狀態(tài))。為此，業(yè)界大多求助于啟發(fā)式[43-45]或元啟發(fā)式算法，如遺傳[46-47]，模擬退火[48-49]，粒子群[38,50]，禁忌搜索[51]，分布估計(jì)[52]，混合蛙跳[53]，差分進(jìn)化[54]，蟻群優(yōu)化[55]，分散搜索[56]，路徑重連[57]等。

3.2 實(shí)驗(yàn)環(huán)境設(shè)置

實(shí)驗(yàn)采用MATLAB R2015b編程實(shí)現(xiàn)。從項(xiàng)目調(diào)度問(wèn)題庫(kù) (Project Scheduling Problem Library, PSPLIB)[58]選取規(guī)模為J10、J20和J30不等的1 608個(gè)(各536個(gè))MRCPSP算例作為實(shí)驗(yàn)數(shù)據(jù)集。采用DELL筆記本電腦，配置為：CPU Intel i7, 主頻2.6 GHz，8 G內(nèi)存。設(shè)計(jì)不同條件下的多個(gè)驗(yàn)證環(huán)節(jié)，并與當(dāng)前公開(kāi)文獻(xiàn)提供的結(jié)果進(jìn)行比較。

3.3 與最新文獻(xiàn)中的計(jì)算結(jié)果的比較

將RLHM實(shí)驗(yàn)結(jié)果與文獻(xiàn)[40]列出的多種用于求解MRCPSP的優(yōu)化算法進(jìn)行對(duì)比。這些算法大多都報(bào)告了J10和J20兩組算例的結(jié)果。為了公平起見(jiàn)，本實(shí)驗(yàn)每組均選取全部536個(gè)算例，總計(jì)1 072個(gè)算例。表2列出了對(duì)比結(jié)果(表中算法名稱以文獻(xiàn)作者姓名縮寫表示)，表中數(shù)據(jù)表示執(zhí)行5 000次可行解得到的平均偏差值。

表2 與文獻(xiàn)[35,40]列出的優(yōu)化算法比較結(jié)果

從實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，RLHM算法是這些算法中表現(xiàn)最好的。由于公開(kāi)文獻(xiàn)缺乏關(guān)于J30算例的進(jìn)一步報(bào)告，針對(duì)J30的536個(gè)算例，在此僅報(bào)告其計(jì)算結(jié)果(如表3)。RLHM算法對(duì)J30算例的計(jì)算結(jié)果表明有多達(dá)41個(gè)算例獲得了比當(dāng)前公開(kāi)文獻(xiàn)報(bào)告的已知最優(yōu)解更好的結(jié)果。

表3 獲得改進(jìn)的J30算例

3.4 與元啟發(fā)式算法計(jì)算結(jié)果的比較

RLHM算法實(shí)現(xiàn)了多種元啟發(fā)式算子的擇優(yōu)使用，針對(duì)不同的算例充分利用了不同算子的優(yōu)勢(shì)。為了驗(yàn)證這一點(diǎn)，從PSPLIB[58]選取的J10、J20和J30算例中每組隨機(jī)選取50個(gè)算例，共計(jì)150個(gè)算例，每個(gè)算例執(zhí)行5 000次可行解，分別取各組算例的偏差均值做出比較。如圖4所示為RLHM算法與分別獨(dú)立執(zhí)行的4種元啟發(fā)式算法(TS、PSO、ABC、ACS)計(jì)算結(jié)果的比較。從圖4可以看出，RLHM算法得到的目標(biāo)偏差在3組算例中均小于其他4種元啟發(fā)式算法，進(jìn)一步驗(yàn)證了RLHM算法的優(yōu)勢(shì)。

3.5 與隨機(jī)選擇超啟發(fā)式算法結(jié)果對(duì)比

RLHM算法高層采用了改進(jìn)接受和Naive接受兩種預(yù)先指定的狀態(tài)，使用Q—學(xué)習(xí)指導(dǎo)LLH算子選擇，與傳統(tǒng)的隨機(jī)機(jī)制選擇(Random Heuristic Selection, RHS)LLH算子相比，效果明顯有所改善?，F(xiàn)設(shè)定兩種算法的有關(guān)參數(shù)(終止迭代次數(shù)，LLH算子相關(guān)參數(shù)設(shè)置等)均一致，算例仍然采用J10，J20和J30不同規(guī)模150個(gè)算例進(jìn)行計(jì)算，結(jié)果對(duì)比曲線如圖5所示。

由圖5可知，RLHM算法比RHS算法平均偏差更小。隨著算例規(guī)模的增大，差距也在拉大。這說(shuō)明RLHM算法中Q—學(xué)習(xí)機(jī)制在選擇LLH算子時(shí)，隨著問(wèn)題規(guī)模越大，能力表現(xiàn)越突出。更主要的是RLHM算法沒(méi)有刻意地去調(diào)整哪個(gè)參數(shù)以適應(yīng)問(wèn)題，而是利用Q—學(xué)習(xí)機(jī)制自動(dòng)地選擇各個(gè)算子，達(dá)到了超啟發(fā)式算法的初衷。

3.6 擴(kuò)充LLH算子及其影響

擴(kuò)充LLH算子意味著增加新算子的數(shù)量，有助于改進(jìn)搜索空間的多樣性，從而增大全局優(yōu)化的可能性。RLHM算法設(shè)計(jì)了兩種增加LLH算子的可行方案：第一種方案是直接通過(guò)適當(dāng)修改現(xiàn)有的元啟發(fā)式算法并集成到低層LLH算子集中，正如圖3低層左側(cè)所示，將模擬退火算法、遺傳算法、鄰域搜索算法、混合蛙跳等元啟發(fā)式算法都集成進(jìn)來(lái)。這樣的集成只需要前一個(gè)算子能夠平滑地把本算子計(jì)算的結(jié)果傳遞給下一個(gè)算子。第二種方案是在現(xiàn)有的各算子基礎(chǔ)上修改算法參數(shù)來(lái)獲得新的算子。如PANDIRI等[59]曾根據(jù)參數(shù)值的不同組合改變算法的特性，有效地求解了k—互連多倉(cāng)庫(kù)多旅行商問(wèn)題。對(duì)于一個(gè)算子的某個(gè)參數(shù)值來(lái)說(shuō)，有時(shí)其可選的范圍很大，也很靈敏，因此，初始可以根據(jù)經(jīng)驗(yàn)選定幾種典型的參數(shù)，作為不同算子使用，當(dāng)然也可以自適應(yīng)地調(diào)整不同參數(shù)的組合。

為了驗(yàn)證增加新LLH算子帶來(lái)的效果，本文在前4個(gè)LLH算子基礎(chǔ)上分別設(shè)計(jì)了兩種實(shí)驗(yàn)方案：第一方案增加了遺傳算子GA和模擬退火算子SA；第二方案改變了TS的禁忌表長(zhǎng)度和PSO的學(xué)習(xí)因子c1,c2和慣性權(quán)重ω的值。

表4列出了不同算子(動(dòng)作)數(shù)量下針對(duì)前述150個(gè)算例的計(jì)算結(jié)果。由表4可知，增加新動(dòng)作帶來(lái)的最重要的變化是縮短了計(jì)算時(shí)間(從4個(gè)算子的計(jì)算時(shí)間210 min下降到8個(gè)算子的107 min)。目標(biāo)值平均偏差均有所下降，說(shuō)明增加算子數(shù)量有助于及時(shí)跳出變化不大的局部搜索環(huán)節(jié)，提升算法效率和效果。

表4 不同算子數(shù)量下目標(biāo)值差均值

3.7 LLH算子調(diào)用頻度分析

一個(gè)算子的調(diào)用頻度定義為執(zhí)行過(guò)程中該算子被調(diào)用的次數(shù)與全體算子被調(diào)用次數(shù)之比。該值越大，說(shuō)明該算子被調(diào)用的概率越大，因而可以說(shuō)明算法對(duì)其依賴程度以及Q—學(xué)習(xí)的效果。如表5所示為執(zhí)行150個(gè)算例時(shí)，LLH算子平均調(diào)用頻度統(tǒng)計(jì)結(jié)果。

表5 LLH算子平均調(diào)用頻度統(tǒng)計(jì)

從表5可以看出，算子從高到低調(diào)用頻度分別是TS>PSO>ABC>ACS。這基本上符合單獨(dú)應(yīng)用這4種元啟發(fā)式算法時(shí)的效果，也間接證明了RLHM算法在LLH算子選擇上使用Q—學(xué)習(xí)進(jìn)行智能選擇的可靠性。其次，隨著問(wèn)題規(guī)模的增加，優(yōu)秀算子被調(diào)用頻率更大，但并沒(méi)有放棄對(duì)其他算子的選擇，從而說(shuō)明了多樣性的Q—學(xué)習(xí)帶來(lái)的靈活性。

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

在優(yōu)化算法研究領(lǐng)域，超啟發(fā)式算法和技術(shù)已經(jīng)成為當(dāng)前一大研究熱點(diǎn)，其目的是解決傳統(tǒng)的元啟發(fā)式算法機(jī)制單一和面向問(wèn)題定制等不足，能夠大大提升解決問(wèn)題的通用性。從這一視角看，超啟發(fā)式算法的研究是比發(fā)明新算法更有意義的一項(xiàng)工作，能夠?qū)崿F(xiàn)領(lǐng)域內(nèi)不同策略和技術(shù)的交叉融合。

本文提出一種基于Q—學(xué)習(xí)的超啟發(fā)式算法RLHM算法。首先，與傳統(tǒng)的超啟發(fā)式算法不同的是，低層算子不再采用簡(jiǎn)單的啟發(fā)式序列，而是使用不同元啟發(fā)式算法作為獨(dú)立算子。元啟發(fā)式算法不依賴于問(wèn)題，而相同的問(wèn)題可在不同元啟發(fā)式算法上統(tǒng)一編碼。其次，作為低層算子的元啟發(fā)式算法可以隨意擴(kuò)充，而常見(jiàn)的組合優(yōu)化問(wèn)題的編碼也可以根據(jù)不同的問(wèn)題隨時(shí)擴(kuò)充，大大增加了算法的靈活性和通用性。再次，算法通過(guò)Q—學(xué)習(xí)的評(píng)價(jià)機(jī)制智能地選擇適當(dāng)狀態(tài)—?jiǎng)幼鹘M合，從而使RLHM算法在LLH算子選擇上具備較高的靈活性和可靠性。實(shí)驗(yàn)結(jié)果證明了RLHM算法的良好特性。未來(lái)的研究中，將繼續(xù)增加高層算子的選擇策略，進(jìn)一步提高低層算子的計(jì)算效率，進(jìn)而提高算法的整體通用性。