基于模擬退火與強(qiáng)化學(xué)習(xí)機(jī)制的任務(wù)分析方法

彭鵬菲，龔 雪，鄭雅蓮，姜 俊

(1.海軍工程大學(xué) 電子工程學(xué)院， 武漢 430033; 2.武漢大學(xué) 水資源與水電工程科學(xué)國家重點(diǎn)實(shí)驗(yàn)室， 武漢 430072; 3.海軍工程大學(xué) 作戰(zhàn)運(yùn)籌與規(guī)劃系， 武漢 430033)

1 引言

任務(wù)分析是開展任務(wù)規(guī)劃的重要前提，針對任務(wù)分析中多方條件限制的任務(wù)序列重組問題，眾多學(xué)者已開展深入研究，總體來說，作戰(zhàn)任務(wù)分析方法可分為三類，一是數(shù)學(xué)解析模型、二是遺傳進(jìn)化方法、三是智能規(guī)劃方法。如在傳統(tǒng)任務(wù)分析算法研究中，董濤和王志亮等人通過耦合任務(wù)集來進(jìn)行任務(wù)解耦，從而達(dá)到任務(wù)序列重構(gòu)的目的；李翠明等從任務(wù)間內(nèi)在機(jī)理的角度定量分析任務(wù)間的聯(lián)系，采用遺傳算法求解任務(wù)最優(yōu)分配方案。在深度強(qiáng)化學(xué)習(xí)基礎(chǔ)上，將任務(wù)放置神經(jīng)網(wǎng)絡(luò)中分析處理。趙曉曉等建立基于多層神經(jīng)網(wǎng)絡(luò)的任務(wù)規(guī)劃智能分析模型，并開展模型的合理性分析。在強(qiáng)化學(xué)習(xí)的基礎(chǔ)上，動(dòng)態(tài)建立任務(wù)間信息交互的環(huán)境，實(shí)現(xiàn)特定環(huán)境下的任務(wù)分析。馬悅等針對現(xiàn)代戰(zhàn)爭快節(jié)奏、高強(qiáng)度和高復(fù)雜性的特點(diǎn)，通過強(qiáng)化學(xué)習(xí)和智能技術(shù)提高了決策自動(dòng)化和自主化水平。上述研究成果，均從任務(wù)細(xì)粒度出發(fā)，并通過對任務(wù)協(xié)同關(guān)系定量分析得出任務(wù)執(zhí)行序列。上述算法在一定程度上能解決任務(wù)分析與規(guī)劃問題，但仍存在許多缺陷，如針對數(shù)學(xué)解析模型算法，該模型由于難以考慮多方面的任務(wù)交互信息，因而易陷入局部最優(yōu)；遺傳算法存在依賴于初始解、參數(shù)復(fù)雜、迭代時(shí)間長、底層存儲機(jī)能和收斂過早等問題；深度強(qiáng)化學(xué)習(xí)算法雖可有效解決參數(shù)復(fù)雜及初始解依賴問題，但算法的數(shù)據(jù)需求量大，存在實(shí)時(shí)完備性較差、時(shí)間延遲等問題。

通過模擬退火(simulated annealing,SA)算法中的降溫迭代，結(jié)合基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)來改進(jìn)算法的當(dāng)前狀態(tài)，并研究退火因子的動(dòng)態(tài)變化。該算法有較好的推廣應(yīng)用前景。

2 基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)算法改進(jìn)

該算法基于強(qiáng)化學(xué)習(xí)的策略選擇機(jī)制，引入狀態(tài)因子，逐步實(shí)現(xiàn)對最優(yōu)狀態(tài)的選擇。

SA是基于Monte迭代求解策略的一種隨機(jī)尋優(yōu)算法，基于物理退火過程與組合優(yōu)化之間的相似性，SA由某一較高溫度開始，利用具有概率突跳特性的Montropolis抽樣策略在解空間中進(jìn)行隨機(jī)搜索，伴隨溫度的不斷下降重復(fù)抽樣過程，最終得到全局最優(yōu)解。

強(qiáng)化學(xué)習(xí)Q算法是基于value-based，在某一時(shí)刻的狀態(tài)下(∈)，采取動(dòng)作(∈)能夠獲得收益的期望，環(huán)境會(huì)根據(jù)agent的動(dòng)作反饋相應(yīng)的獎(jiǎng)勵(lì)，因此Q算法將狀態(tài)與動(dòng)作構(gòu)建成一張Q表來存儲值，然后根據(jù)值來選取能夠獲得最大收益的動(dòng)作。

2.1 基于強(qiáng)化學(xué)習(xí)的動(dòng)作選擇策略

基于模擬退火思想，引入狀態(tài)因子，令=(,)-(,) (式中，為當(dāng)前溫度下的狀態(tài)，為當(dāng)前狀態(tài)下的隨機(jī)動(dòng)作，為當(dāng)前狀態(tài)下最大的動(dòng)作值)，通過尋找最優(yōu)狀態(tài)的最適應(yīng)狀態(tài)因子，Q表隨著狀態(tài)因子適應(yīng)度的改變而不斷更新，最終收斂至最優(yōu)值。同時(shí)，根據(jù)智能體(agent)的運(yùn)動(dòng)時(shí)耗及其運(yùn)動(dòng)狀態(tài)反饋，更新獎(jiǎng)勵(lì)矩陣。agent依據(jù)獎(jiǎng)勵(lì)矩陣做出動(dòng)作選擇，同時(shí)，獎(jiǎng)勵(lì)矩陣隨著agent的選擇不斷更新，直至收斂至最優(yōu)狀態(tài)，獲得最優(yōu)的Q表集合。

在上述行為選擇策略中，可設(shè)計(jì)自適應(yīng)動(dòng)態(tài)探索因子，以提高早期發(fā)現(xiàn)任務(wù)狀態(tài)多樣性的概率，避免陷入局部最優(yōu)。另外，該算法通過模擬退火降溫的過程來降低折扣因子，從而提高算法的收斂速度，模型選擇策略流程如圖1所示，圖1中表示在當(dāng)前溫度下agent在該狀態(tài)下的隨機(jī)動(dòng)作，表示當(dāng)前溫度下agent在該狀態(tài)下的最大動(dòng)作。

圖1 基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法選擇策略流程框圖Fig.1 Improved algorithm selection strategy for reinforcement learning based on simulated annealing selection strategy

該策略的具體執(zhí)行步驟如下：

1) 當(dāng)STATE=時(shí)，隨機(jī)初始化ACTION=，此時(shí)設(shè)置agent的最高獎(jiǎng)勵(lì)值的動(dòng)作ACTION=；

2) 判斷學(xué)習(xí)得到的當(dāng)前狀態(tài)下(為該狀態(tài)下動(dòng)作選擇的擾動(dòng)值)與=e(±((,)-(,)))(為該狀態(tài)下動(dòng)作選擇的擾動(dòng)界定值)之間的大小關(guān)系，若<，則采取隨機(jī)動(dòng)作為當(dāng)前動(dòng)作且計(jì)算兩任務(wù)之間的時(shí)耗，若是在[0,5]，則給予agent獎(jiǎng)勵(lì)，并繼續(xù)更新尋找任務(wù)新解的過程。否則，采取最優(yōu)動(dòng)作為當(dāng)前動(dòng)作。

3) 判斷當(dāng)前狀態(tài)是否為最終狀態(tài)，若“是”則結(jié)束尋找過程，若“否”繼續(xù)尋找。針對任務(wù)分析中任務(wù)動(dòng)態(tài)執(zhí)行序列以及任務(wù)分解的難點(diǎn)，將任務(wù)分析模型引入，對于基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法，其設(shè)計(jì)目標(biāo)包括：動(dòng)態(tài)設(shè)計(jì)最終agent的狀態(tài)；依據(jù)獎(jiǎng)勵(lì)機(jī)制進(jìn)行最優(yōu)任務(wù)序列搜尋；引入任務(wù)空間-時(shí)效評判機(jī)制對agent進(jìn)行獎(jiǎng)勵(lì)或懲罰。

基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法，以模擬退火算法為基礎(chǔ)，引入基于任務(wù)分析的學(xué)習(xí)機(jī)制，在設(shè)置最大的回合數(shù)的基礎(chǔ)上，動(dòng)態(tài)實(shí)現(xiàn)退火過程，在agent不斷學(xué)習(xí)的過程中不斷更新Q表，最終產(chǎn)生任務(wù)序列執(zhí)行圖，解決任務(wù)分析的任務(wù)重構(gòu)問題，算法流程如圖2所示，獎(jiǎng)勵(lì)機(jī)制流程如圖3所示；圖2中Episode表示agent學(xué)習(xí)的回合數(shù)，Steps表示agent探索的最大步數(shù)，表示兩任務(wù)間的信息交互邏輯空間距離，表示兩任務(wù)間的時(shí)耗，表示狀態(tài)因子，表示當(dāng)前溫度下的agent的狀態(tài)；圖3中表示當(dāng)前狀態(tài)下agent獲得的獎(jiǎng)勵(lì)值。

圖2 基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法流程框圖Fig.2 Flow chart of reinforcement learning improvement algorithm based on simulated annealing selection strategy

圖3 獎(jiǎng)勵(lì)機(jī)制流程框圖Fig.3 Flow chart of the reward mechanism

2.2 基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法運(yùn)行環(huán)境設(shè)計(jì)

強(qiáng)化學(xué)習(xí)的定義是：在與環(huán)境交互中，agent通過“試錯(cuò)法”獲得獎(jiǎng)勵(lì)指導(dǎo)，最終最大化agent的學(xué)習(xí)過程。

強(qiáng)化學(xué)習(xí)環(huán)境(強(qiáng)化學(xué)習(xí)系統(tǒng))提供的信號通常是一個(gè)標(biāo)量信號，能評估動(dòng)作執(zhí)行效果，通過獎(jiǎng)勵(lì)反饋實(shí)現(xiàn)最大化agent的目標(biāo)。

因環(huán)境提供的信息有限，agent無法很快定位到目標(biāo)任務(wù)，所以，當(dāng)agent移動(dòng)到任務(wù)，會(huì)對下一個(gè)任務(wù)+1進(jìn)行可移動(dòng)性判別，若不可移動(dòng)，則對agent進(jìn)行懲罰，回到起點(diǎn)并開始下一個(gè)回合；若可移動(dòng)，則對agent進(jìn)行獎(jiǎng)勵(lì)，移動(dòng)并判別；直至達(dá)目標(biāo)任務(wù)，進(jìn)行下一回合。

基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法學(xué)習(xí)機(jī)制如圖4所示。

圖4 基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法學(xué)習(xí)機(jī)制示意圖Fig.4 Learning mechanism diagram for reinforcement learning improvement algorithm based on simulated annealing selection strategy

該機(jī)制原理如下：若agent的某一行為策略使其從環(huán)境中獲得獎(jiǎng)勵(lì)，則會(huì)增加采用該策略的傾向。假設(shè)環(huán)境是一個(gè)狀態(tài)有限的離散馬爾可夫過程，agent在每個(gè)時(shí)刻能從有限操作集中選擇一個(gè)操作。在環(huán)境接受此操作后，將其轉(zhuǎn)移到下一個(gè)狀態(tài)并對上一個(gè)狀態(tài)進(jìn)行評估，基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法學(xué)習(xí)更新Q表的獎(jiǎng)勵(lì)機(jī)制如圖5所示。

圖5 基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法學(xué)習(xí)獎(jiǎng)勵(lì)機(jī)制示意圖Fig.5 Learning reward mechanism for reinforcement learning improvement algorithm based on simulated annealing selection strategy figure

因此，在設(shè)計(jì)基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法運(yùn)行環(huán)境時(shí)，假設(shè)agent需要對個(gè)任務(wù)進(jìn)行處理，且最終的目標(biāo)任務(wù)已知。在初始化時(shí)，agent對任務(wù)進(jìn)行判別，若任務(wù)與任務(wù)+1有信息交互，則記為智能體，此時(shí)，智能體可由任務(wù)到達(dá)任務(wù)+1或由任務(wù)+1到達(dá)任務(wù)，即針對任務(wù)間的信息交互，智能體采用策略選擇機(jī)制尋得最優(yōu)的任務(wù)序列圖。若是任務(wù)與任務(wù)+1間沒有信息交互，則記為智能體無法從任務(wù)到達(dá)任務(wù)+1。另外，設(shè)計(jì)環(huán)境獎(jiǎng)勵(lì)矩陣的依據(jù)為：通過專家評價(jià)，若任務(wù)+1完全依賴于任務(wù)的信息輸出，則計(jì)(state,action)=1；若任務(wù)+1不完全依賴于任務(wù)的信息輸出，則計(jì)(state,action)處于(0,1)的區(qū)間；若任務(wù)+1完全不依賴于任務(wù)的信息輸出，則計(jì)(state,action)為-1；若是以某個(gè)任務(wù)為目標(biāo)任務(wù)，則計(jì)(state,action)處于(100，150)的區(qū)間。

3 基于強(qiáng)化學(xué)習(xí)改進(jìn)的任務(wù)序列重構(gòu)及任務(wù)圖生成

在強(qiáng)化學(xué)習(xí)Q算法的開始階段，溫度較高，智能體(agent)以較高的概率進(jìn)行動(dòng)作選擇。隨著學(xué)習(xí)次數(shù)的增加，根據(jù)模擬退火規(guī)則，溫度會(huì)逐漸下降直至穩(wěn)定。探索因子根據(jù)退火規(guī)則下降，智能體以更高的概率選擇最佳的動(dòng)作。使其能夠跳出局部最優(yōu)解的同時(shí)能夠隨著退火的進(jìn)行不斷收斂到一個(gè)最優(yōu)的Q表集合，從而得到最佳任務(wù)執(zhí)行圖。

3.1 基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法任務(wù)分析模型的構(gòu)建

本文將獎(jiǎng)勵(lì)矩陣的概念引入模型，并對基于矩陣的作戰(zhàn)任務(wù)建模及重組問題進(jìn)行了解決與應(yīng)用拓展。具體模型優(yōu)勢如下：

1) 通過分析任務(wù)間的信息交互，將策略選擇機(jī)制和獎(jiǎng)勵(lì)方法結(jié)合；

2) 通過反饋的獎(jiǎng)勵(lì)值，不斷更新agent的運(yùn)動(dòng)方向。

假設(shè)每單一任務(wù)都是一個(gè)獨(dú)立的方向，并且每一個(gè)任務(wù)都相互獨(dú)立。按如下狀態(tài)，智能體獲得不同的獎(jiǎng)勵(lì)矩陣反饋值：若2個(gè)任務(wù)之間沒有信息交互，則記獎(jiǎng)勵(lì)矩陣對應(yīng)的(狀態(tài)，動(dòng)作)值為負(fù)；若是2個(gè)任務(wù)之間有單方面的信息交互，則記獎(jiǎng)勵(lì)矩陣對應(yīng)的(狀態(tài)，動(dòng)作)值為正值且在[0,1]之間；若是雙方都有信息交互，則記獎(jiǎng)勵(lì)矩陣的對應(yīng)(狀態(tài)，動(dòng)作)值為正值且大于1。

在每一種狀態(tài)下，智能體根據(jù)策略選擇機(jī)制的反饋值采取相應(yīng)的動(dòng)作，隨著學(xué)習(xí)周期增加，不斷豐富agent的學(xué)習(xí)經(jīng)驗(yàn)，最終獲得最優(yōu)Q表。

任務(wù)分析方法的實(shí)現(xiàn)過程，主要分為2個(gè)部分：第1個(gè)部分是Q學(xué)習(xí)模擬退火模型的構(gòu)建，此部分將模擬退火思想中的退火因子與Q學(xué)習(xí)機(jī)制相結(jié)合，進(jìn)行任務(wù)序列重組；第2個(gè)部分是迭代學(xué)習(xí)模型的求解，此部分通過學(xué)習(xí)迭代生成任務(wù)序列圖。具體基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法任務(wù)分析模型的結(jié)構(gòu)如圖6所示。

圖6 基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法任務(wù)分析模型結(jié)構(gòu)框圖Fig.6 Structural diagram of the task analysis model of a reinforcement learning improvement algorithm based on a simulated annealing selection strategy

第1步，將任務(wù)時(shí)間矩陣、任務(wù)間信息交互矩陣輸入Q學(xué)習(xí)模擬退火模型，可得學(xué)習(xí)后的Q表、串行任務(wù)執(zhí)行序列和任務(wù)獎(jiǎng)勵(lì)評價(jià)矩陣。在迭代求解任務(wù)序列的過程，任務(wù)獎(jiǎng)勵(lì)評價(jià)矩陣反作用于Q模擬退火算法生成最優(yōu)的Q表集合。第2步，在進(jìn)行學(xué)習(xí)迭代的過程中，將收斂的Q表和串行任務(wù)序列相結(jié)合，以生成任務(wù)序列圖。

3.2 任務(wù)序列重組

首先，根據(jù)1.1節(jié)的策略選擇機(jī)制，編制任務(wù)序列重組算法，通過任務(wù)信息交互矩陣形成初始任務(wù)空間解。其次，在初始空間解中，根據(jù)任務(wù)間的信息交互進(jìn)行定量分析，生成任務(wù)關(guān)系矩陣。最后，運(yùn)用策略選擇機(jī)制更新任務(wù)關(guān)系矩陣，并反饋對應(yīng)任務(wù)的獎(jiǎng)勵(lì)矩陣。

智能體在學(xué)習(xí)時(shí)將不斷更新任務(wù)空間矩陣和任務(wù)獎(jiǎng)勵(lì)矩陣，且更新的這2個(gè)值又能對智能體進(jìn)行進(jìn)一步反饋，直到其達(dá)到最佳狀態(tài)及最佳溫度，最終生成串行任務(wù)執(zhí)行序列，即完成任務(wù)序列重組。任務(wù)序列重組結(jié)構(gòu)如圖7所示。

圖7 任務(wù)序列重組結(jié)構(gòu)框圖Fig.7 Structure of the task sequence reorganisation

3.3 任務(wù)序列圖生成

根據(jù)上述動(dòng)作選擇策略，將改進(jìn)的基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法引入任務(wù)分析算法中，執(zhí)行過程如圖8所示。

圖8 基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法執(zhí)行流程框圖Fig.8 Execution flow of reinforcement learning improvement algorithm based on simulated annealing selection strategy

具體執(zhí)行步驟如下：

Step 1：初始化任務(wù)時(shí)間矩陣、任務(wù)間信息交互矩陣。

Step 2：運(yùn)用基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法重構(gòu)任務(wù)序列。

① 隨機(jī)產(chǎn)生初始解狀態(tài)，即隨機(jī)解空間，設(shè)置最大回合數(shù)Episode=40 000，設(shè)置最大探索步數(shù)steps=100，初始化最初狀態(tài)值。

② 在當(dāng)前狀態(tài)下，隨機(jī)初始化一個(gè)動(dòng)作值、未來需要執(zhí)行的動(dòng)作集合和未來Q表集合。隨后，計(jì)算任意兩任務(wù)間的信息交互邏輯空間距離、兩任務(wù)間的時(shí)耗。智能體通過不斷選擇任務(wù)序列，反饋邏輯空間距離，持續(xù)更新獎(jiǎng)勵(lì)矩陣，從而推算出最優(yōu)的任務(wù)執(zhí)行序列。

引入狀態(tài)因子，=(,)-(,)，若<0，則計(jì)算=e(,)-(,)；若>0，則計(jì)算=e-(,)-(,)。

判斷和，若<，則取當(dāng)前狀態(tài)下的隨機(jī)動(dòng)作為當(dāng)前動(dòng)作，且若在[0,5]，令表示任務(wù)和任務(wù)+1間的時(shí)耗，若<0，則agent不能從任務(wù)到任務(wù)+1，若是>5，則時(shí)耗太長，效率低下，則給予agent獎(jiǎng)勵(lì)，并尋找任務(wù)新解；若>，取當(dāng)前狀態(tài)下的隨機(jī)動(dòng)作為當(dāng)前動(dòng)作，同樣地，若在[0,5]，則給予agent獎(jiǎng)勵(lì)，并尋找任務(wù)新解。

判斷step是否小于100，若“是”，重新執(zhí)行②，若“否”，執(zhí)行③

③ 運(yùn)用貪婪算法更新Q表，并判別是否到達(dá)最終狀態(tài)(實(shí)現(xiàn)最大目標(biāo))，若“是”，返回①；判斷是否達(dá)到降溫標(biāo)準(zhǔn)，若“是”，結(jié)束，若“否”，開始下一回合。

Step 3：生成任務(wù)執(zhí)行序列及任務(wù)執(zhí)行圖。

4 實(shí)驗(yàn)分析

以15枚TBM來襲事件為例開展實(shí)驗(yàn)分析，將反TBM作戰(zhàn)任務(wù)抽象為15個(gè)任務(wù)，采用任務(wù)序列重組及任務(wù)圖重構(gòu)算法。

仿真實(shí)驗(yàn)平臺為LAPTOP-QEHE6SH7處理器是11th Gen Intel(R) Core(TM) i5-1155G7 @2.50 GHz，64位操作系統(tǒng)，基于x64處理器的聯(lián)想小新筆記本。編程工具為Pycharm，應(yīng)用了Conda環(huán)境。

4.1 基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法參數(shù)設(shè)置

根據(jù)多次實(shí)驗(yàn)，可得基于模擬退火選擇策略強(qiáng)化學(xué)習(xí)改進(jìn)算法的模型參數(shù)，具體如表1所示。

表1 模型參數(shù)Table 1 Model parameter

4.2 基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法有效性仿真分析

與Q算法和SA算法相比，基于模擬退火的Q學(xué)習(xí)任務(wù)分析算法有如下優(yōu)勢：

反TBM作戰(zhàn)任務(wù)包含預(yù)警探測、目標(biāo)截獲、跟蹤識別、火力攔截、殺傷效果評估等方面。

圖9展示了反TBM作戰(zhàn)任務(wù)基于優(yōu)先級任務(wù)序列的排列，且任何一個(gè)作戰(zhàn)資源平臺都無法單獨(dú)承擔(dān)全部作戰(zhàn)任務(wù)，因此需進(jìn)行基于多因素的作戰(zhàn)任務(wù)分析。

圖12所示，基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法與SA算法在空間邏輯距離收斂上均具有良好的效果，當(dāng)達(dá)到第1 500回合左右，基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法已收斂，而SA已陷入局部最小值。

1) 運(yùn)用任務(wù)時(shí)間矩陣考慮多因素對任務(wù)序列的影響，能更加全面地考慮多復(fù)雜因素對任務(wù)信息交互的影響，因而能輕松應(yīng)對各種復(fù)雜因素的變化；

2) Q學(xué)習(xí)任務(wù)分析算法能考慮多樣化輸入，不只是對任務(wù)信息交互矩陣進(jìn)行分析和處理。

通過基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法，經(jīng)任務(wù)序列重組，能獲得最優(yōu)的串行執(zhí)行任務(wù)序列，如圖9所示。

圖9 任務(wù)序列重組后的串行執(zhí)行任務(wù)序列圖Fig.9 Diagram of serial execution of tasks after task sequence reorganisation

基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法，其基于Q算法，經(jīng)迭代學(xué)習(xí)后得到最優(yōu)執(zhí)行任務(wù)序列并行圖，當(dāng)基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法最大回合數(shù)為 40 000、貪婪值為0.4時(shí)，如圖10所示。

圖10 40 000步收斂后的并行執(zhí)行任務(wù)序列圖Fig.10 Task diagram after 40 000 steps of convergence

當(dāng)貪婪值為0.2時(shí)，結(jié)果如圖11所示，最大獎(jiǎng)勵(lì)值無法收斂，因此不可取。當(dāng)貪婪值為0.8時(shí)，達(dá)到最大獎(jiǎng)勵(lì)值后，結(jié)果有向下的趨勢，因此同樣不可取。

圖11 不同貪婪值的最大獎(jiǎng)勵(lì)收斂效果曲線Fig.11 Comparison of the maximum reward convergence effect for different greedy values

圖12 基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法和SA算法各個(gè)回合邏輯空間距離df曲線Fig.12 Comparison of the reinforcement learning improvement algorithm based on simulated annealing selection strategy and the SA algorithm for each round of logical space distance df

4.3 基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法運(yùn)行效率分析

從性能來看，基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法隨著回合數(shù)的不斷增大、退火因子不斷減小，退火因子對任務(wù)獎(jiǎng)勵(lì)機(jī)制的影響越來越小。

最終，當(dāng)算法達(dá)到最優(yōu)時(shí)，退火因子達(dá)到穩(wěn)定狀態(tài)，基于模擬退火的Q學(xué)習(xí)任務(wù)分析算法收斂至最優(yōu)回合數(shù)。對于SA而言，隨著退火的進(jìn)行，算法陷入局部最優(yōu)，因而性能較差。對于傳統(tǒng)Q算法而言，無法自行決策，難以收斂到最優(yōu)狀態(tài)，且迭代速度慢、時(shí)效性較差。

為了驗(yàn)證基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法任務(wù)分析算法在任務(wù)序列重構(gòu)的優(yōu)越性，設(shè)置相同任務(wù)時(shí)間矩陣、任務(wù)間信息交互矩陣，將傳統(tǒng)SA算法、傳統(tǒng)Q算法和基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法在收斂回合數(shù)上進(jìn)行比較，結(jié)果如表2所示。與SA和Q算法相比，在額外加入一個(gè)任務(wù)時(shí)效矩陣輸入的情況下，基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法在第2 629回合達(dá)到收斂，跳出設(shè)定回合制，Q算法無法收斂，SA算法收斂步數(shù)過短，可能已陷入局部最優(yōu)。因此，相比之下，基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法在收斂效果上更具優(yōu)越性。

表2 收斂回合數(shù)Table 2 Convergence table for the number of algorithm episode

最后，基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法在第2 629回合收斂，其比傳統(tǒng)的Q學(xué)習(xí)算法節(jié)省了時(shí)間，且得出了任務(wù)的最優(yōu)串行執(zhí)行序列以及不同初始狀態(tài)下最優(yōu)的并行任務(wù)執(zhí)行圖。與SA算法相比，基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法更容易跳出局部循環(huán)且能迅速地找到不同場景下的任務(wù)執(zhí)行圖。

5 結(jié)論

本文提出的基于模擬退火選擇策略的強(qiáng)化學(xué)習(xí)改進(jìn)算法，通過不斷的降溫迭代和最大回合數(shù)的經(jīng)驗(yàn)學(xué)習(xí)，產(chǎn)生針對各個(gè)回合的Q表，獲取算法至退火收斂時(shí)的最優(yōu)Q表，進(jìn)而實(shí)現(xiàn)基于模擬退火Q學(xué)習(xí)的回合迭代，產(chǎn)生符合不同情景的任務(wù)分析圖。仿真實(shí)驗(yàn)結(jié)果表明，該算法比傳統(tǒng)Q學(xué)習(xí)算法更具操作性，且比傳統(tǒng)的模擬退火算法更能跳出局部最優(yōu)值，快速在一個(gè)相對較好的回合數(shù)收斂，并產(chǎn)生較好的任務(wù)分析圖，具備解決任務(wù)分析問題的人工智能算法性能。

將Q強(qiáng)化學(xué)習(xí)和模擬退火算法結(jié)合，一定程度上解決任務(wù)分析問題。但算法也存在缺點(diǎn)，如Q學(xué)習(xí)算法難以處理連續(xù)問題。因此，可考慮將強(qiáng)化學(xué)習(xí)的sarsa和粒子群算法結(jié)合，開展研究進(jìn)一步的任務(wù)規(guī)劃處理。