[發明專利]基于Q學習的異構平臺任務調度方法及系統

有效

• 申請號: 202011284585.6
• 申請日: 2020-11-17
• 公開（公告）號: CN112256422B
• 公開（公告）日: 2023-08-04
• 發明（設計）人: 高博;李娜;謝宗甫;岳春生;張鋒印;董春宵;馬金全;余果;郭璐
• 申請（專利權）人: 中國人民解放軍戰略支援部隊信息工程大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50;G06N3/086;G06N3/006
• 代理公司: 鄭州大通專利商標代理有限公司 41111
• 代理人: 周艷巧

1.一種基于Q學習的異構平臺任務調度方法，其特征在于，包含如下內容：

將所有任務作為Q學習的狀態空間，處理器集合作為動作空間，等待分配的任務作為當前狀態，依據Q學習中任務映射到動作空間所需要的的執行時間來獲取任務初始映射方案；

創建遺傳算法模型，對任務初始映射方案進行適應度評估，并依據適應度設定遺傳算法模型中復制到下一代種群中的個體，對保留個體進行交叉變異，確定新種群優化效率及最小閾值；依據遺傳算法模型獲取模型中任務到處理器映射的近似最優解；

將模型近似最優解轉換為蟻群信息初始信息分布，根據信息分布并通過蟻群算法迭代搜索輸出最優路徑來獲取任務調度最優方案；

系統應用模型表示為G＝{V,E,C,L}，目標系統模型表示為P＝{N,H,W,T}，V為任務集合，E為有依賴關系有向邊集合，C為任務計算量集合，L為子任務間通信量，N為處理器集合，H為處理器特征，W為計算開銷，T為任務在處理器間的通信開銷，依據系統應用模型和目標系統模型兩者中的任務集合和處理器集合來獲取Q學習的狀態空間和動作空間，并采取ε-greedy策略平衡智能體對狀態空間的搜索和對已獲得信息的利用；

將任務集合V構成狀態空間S，處理器集合N作為動作空間A，將等待分配的任務v_i作為當前狀態s，當前狀態的執行動作n_i為a；

Q學習智能體根據ε-greedy行為策略在當前狀態下執行動作，得到任務映射到處理器的Q值，并獲得立即獎勵，轉移到新狀態；以每次動作執行完成的Q值最小為目標，在新狀態下選擇具有最小Q值的動作執行，并存儲，衰減學習率，將下一狀態賦予當前狀態，根據ε-greedy行為策略選擇下一狀態下的動作，來迭代執行，以根據存儲情況獲得任務初始映射方案；

創建遺傳算法模型中，對任務初始映射方案進行編碼，將任務映射到對應處理器上；并依據適應度評價函數進行適應度評估，將滿足適應度值的個體復制直接進入下一代種群，對原保留個體進行交叉變異；利用遺傳算法的迭代過程，將每一后代的種群優化效率與最小閾值比較來確定當前種群優化效率，直到連續設定代的后代種群優化效率均比最小閾值小，終止迭代，獲取遺傳算法模型關于任務與處理器映射的近似最優解集；

適應度評價函數表示為：其中，Q(s,a)表示任務s映射在處理器a的執行時間，t表示迭代代數。

2.根據權利要求1所述的基于Q學習的異構平臺任務調度方法，其特征在于，每次迭代中，依據新種群的優化效率設定最小閾值，若每一后代的種群優化效率小于該最小閾值，則將該最小閾值的大小替換為當前種群優化效率。

3.根據權利要求1所述的基于Q學習的異構平臺任務調度方法，其特征在于，蟻群算法中，依據任務在處理器所需執行時間長短來確定螞蟻釋放信息素的多少；根據已選擇處理器，在禁忌表中記錄螞蟻當前時刻已走過路徑；通過迭代輸出螞蟻最優路徑來得到任務到處理器的最優分配及任務執行最短時間。

4.一種基于Q學習的異構平臺任務調度系統，其特征在于，基于權利要求1所述的方法實現，包含：初始映射模塊、適應度評估模塊和最優輸出模塊，其中，

初始映射模塊，用于將所有任務作為Q學習的狀態空間，處理器集合作為動作空間，等待分配的任務作為當前狀態，依據Q學習中任務映射到動作空間所需要的的執行時間來獲取任務初始映射方案；

適應度評估模塊，用于創建遺傳算法模型，對任務初始映射方案進行適應度評估，并依據適應度設定遺傳算法模型中復制到下一代種群中的個體，對保留個體進行交叉變異，確定新種群優化效率及最小閾值；依據遺傳算法模型獲取模型中任務到處理器映射的近似最優解；

最優輸出模塊，用于將模型近似最優解轉換為蟻群信息初始信息分布，根據信息分布并通過蟻群算法迭代搜索輸出最優路徑來獲取任務調度最優方案。

5.一種計算機可讀存儲介質，其上存儲有計算機程序，其中，該程序被處理器執行時執行權利要求1～3任一項所述的方法。

6.一種計算機設備，包含處理器和存儲器，所述存儲器存儲有能夠被所述處理器執行的機器可執行指令，所述處理器執行所述機器可執行指令以執行權利要求1～3任一項所述的方法。