崔建雙，呂 玥，徐子涵

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

SIM等[33]提出基于強化學(xué)習(xí)和禁忌搜索的模擬退火超啟發(fā)式算法；?ZCAN等[23]提出一種超啟發(fā)式模型，利用所謂的“大洪水”策略作為移動接受方法；ZAMLI等[22]提出一種混合T—路測試生成策略，采用禁忌搜索作為其高級元啟發(fā)式，并利用4種低級元啟發(fā)自適應(yīng)選擇最合適的算法；FERREIRA等[35]提出一種“多臂強盜”選擇機制策略(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ā)式模型，研究了立即強化方案的一些變體以及選擇策略和學(xué)習(xí)函數(shù)的影響，提供了一類獨特的狀態(tài)和動作表示；MOSADEGH等[37]開發(fā)了一種超模擬退火算法，該算法使用Q—學(xué)習(xí)策略來選擇啟發(fā)式；張景玲等[34]設(shè)計了一種基于強化學(xué)習(xí)的超啟發(fā)算法求解有容量車輛路徑問題，算法使用強化學(xué)習(xí)中的深度Q神經(jīng)網(wǎng)絡(luò)算法構(gòu)造選擇策略，總體求解效果優(yōu)于對比算法。

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

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

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

2.1 RLHM框架

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

2.2 狀態(tài)—動作組合對

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

表1 RLHM的接受策略

2.3 RLHM算法流程

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

算法1RLHM算法。

1: Initialization()

GlobalValue=min(fitnessinitial)

initial-state()和initial-action()

%隨機指定一個初始狀態(tài)和動作

2: While !Termination-Criteria Do

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

4: Execution() %執(zhí)行狀態(tài)—動作組合

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

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

2.5 LLH算子的設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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