科研動(dòng)態(tài)
基于圖指針網(wǎng)絡(luò)的分層課程強(qiáng)化學(xué)習(xí)方法求解穿梭油輪調(diào)度問(wèn)題
中文題目：基于圖指針網(wǎng)絡(luò)的分層課程強(qiáng)化學(xué)習(xí)方法求解穿梭油輪調(diào)度問(wèn)題
論文題目：Graph Pointer Network Based Hierarchical Curriculum Reinforcement Learning Method Solving Shuttle Tankers Scheduling Problem
錄用期刊/會(huì)議： Complex System Modeling and Simulation (CAA A類(lèi)期刊)
原文DOI： 10.23919/CSMS.2024.0017
原文鏈接：https://ieeexplore.ieee.org/document/10820942/
錄用/見(jiàn)刊時(shí)間：2024年12月31日
作者列表：
1）高小永 中國(guó)石油大學(xué)（北京）自動(dòng)化系 教師
2）楊一旭 中國(guó)石油大學(xué)（北京）自動(dòng)化系 碩21
3）彭 雕 中國(guó)石油大學(xué)（北京）自動(dòng)化系 碩21
4）李尚赫 中國(guó)石油大學(xué)（北京）自動(dòng)化系 博23
5）檀朝東 中國(guó)石油大學(xué)（北京）自動(dòng)化系 教師
6）李菲菲 山東預(yù)見(jiàn)智能科技有限公司
7）陳 韜 英國(guó)薩里大學(xué)過(guò)程與化學(xué)工程系 教師
文章簡(jiǎn)介:
海上石油生產(chǎn)離不開(kāi)穿梭油輪進(jìn)行拉油作業(yè)，穿梭油輪調(diào)度問(wèn)題是個(gè)經(jīng)典的組合優(yōu)化問(wèn)題，當(dāng)較大規(guī)模需要考慮時(shí)求解難度很大。為此，本文首次將GPN引入STSP領(lǐng)域，提出了一種新穎的 HCRL 優(yōu)化框架來(lái)解決 STSP 的復(fù)雜性，并將 STSP 劃分為航行和操作階段，以及一種異步訓(xùn)練策略來(lái)解決航行階段和操作階段之間的耦合問(wèn)題。實(shí)驗(yàn)對(duì)比結(jié)果顯示，所提出的HCRL方法所得解更優(yōu)，約12%的耗時(shí)降低。
摘要:
穿梭油輪調(diào)度是海上油氣運(yùn)輸過(guò)程中的重要任務(wù)，涉及操作時(shí)間窗口的滿(mǎn)足、最優(yōu)運(yùn)輸規(guī)劃以及恰當(dāng)?shù)膸?kù)存管理。然而，傳統(tǒng)的混合整數(shù)線(xiàn)性規(guī)劃（MILP）或元啟發(fā)式算法往往因運(yùn)行時(shí)間過(guò)長(zhǎng)而難以勝任。本文提出了一種基于圖指針網(wǎng)絡(luò)（GPN）的分層課程強(qiáng)化學(xué)習(xí)（HCRL）方法來(lái)解決穿梭油輪調(diào)度問(wèn)題（STSP）。該模型經(jīng)過(guò)訓(xùn)練，能夠?qū)TSP分解為航程和操作階段，并依次生成航線(xiàn)和庫(kù)存管理決策。為解決各階段之間的耦合問(wèn)題，開(kāi)發(fā)了一種異步訓(xùn)練策略。對(duì)比實(shí)驗(yàn)表明，所提出的HCRL方法與啟發(fā)式算法相比，平均行程長(zhǎng)度縮短了12%。另外的實(shí)驗(yàn)驗(yàn)證了其對(duì)未見(jiàn)過(guò)實(shí)例的泛化能力和對(duì)更大實(shí)例的可擴(kuò)展性。
背景與動(dòng)機(jī):
針對(duì)組合優(yōu)化問(wèn)題的傳統(tǒng)強(qiáng)化訓(xùn)練策略在復(fù)雜的約束條件和過(guò)多的影響因素下往往失效。要解決 STSP 問(wèn)題，決策者必須確保時(shí)間窗的滿(mǎn)足，避免庫(kù)存容量超限，并考慮包括浮式生產(chǎn)儲(chǔ)卸油船（FPSOs）的存儲(chǔ)容量、生產(chǎn)率、運(yùn)行率和運(yùn)行時(shí)間窗、穿梭油輪的庫(kù)存容量以及 FPSOs 與陸上終端之間的距離等因素來(lái)優(yōu)化石油運(yùn)輸成本。為了解決這個(gè)問(wèn)題，引入了被稱(chēng)為課程學(xué)習(xí)（CL）和分層強(qiáng)化學(xué)習(xí)（HRL）的策略。一方面，獎(jiǎng)勵(lì)函數(shù)首先設(shè)計(jì)為包括時(shí)間窗的滿(mǎn)足和庫(kù)存控制，并在滿(mǎn)足一定條件后納入成本優(yōu)化，這類(lèi)似于神經(jīng)網(wǎng)絡(luò)模型的課程設(shè)置。另一方面，穿梭油輪船隊(duì)的決策將分為兩個(gè)連續(xù)的階段，以便在航行階段首先生成路徑?jīng)Q策，然后將其反饋給網(wǎng)絡(luò)作為輸入，這在 HRL 范例中被稱(chēng)為一種選擇，以在操作階段生成庫(kù)存管理決策。
設(shè)計(jì)與實(shí)現(xiàn):
1.基于GPN的HRL策略
提出了一種基于GPN的HRL策略來(lái)解決STSP。該策略將STSP分為航行和操作階段，并依次生成路徑規(guī)劃和庫(kù)存管理決策，這將大大降低穿梭油輪調(diào)度的復(fù)雜性。該模型的基本結(jié)構(gòu)如圖1所示。在編碼器中，穿梭油輪的特征將通過(guò)LSTM進(jìn)行編碼，LSTM的隱藏狀態(tài) h 將作為查詢(xún)向量 q1 傳遞給解碼器中的Ptr-Net 1。節(jié)點(diǎn)的特征將通過(guò)GNN進(jìn)行嵌入，輸出的高層向量上下文將分別用作兩個(gè) Pet-Nets 的參考向量 r1 和 r2，而向量 r2 是基于 Ptr-Net 1 生成的 （s,n） 決策從向量 r1 中提取的片段。
在解碼器中，Ptr-Net 1 負(fù)責(zé)根據(jù)第一個(gè)生成的概率分布 P（s,n） 為其選擇一個(gè)油輪 s 和一個(gè)節(jié)點(diǎn) n 以供其訪(fǎng)問(wèn)。然后，s 和 n 的信息將從整個(gè)上下文向量中提取出來(lái)，以簡(jiǎn)化 Ptr-Net 2 的計(jì)算過(guò)程。Ptr-Net 2 負(fù)責(zé)根據(jù)由 Ptr-Net 第二層生成的概率分布 P(t) 為航程（s，n）生成運(yùn)行時(shí)間 t。（s，n，t）是基于 MDP 上下文下當(dāng)前狀態(tài)選擇的操作，并將反饋給環(huán)境以更新穿梭油輪和節(jié)點(diǎn)的特征。（s，n，t）是油輪 s 整個(gè)計(jì)劃的一部分，這意味著油輪 s 從當(dāng)前位置航行到節(jié)點(diǎn) n 并運(yùn)行時(shí)間 t，而聚合（S，N，T）是穿梭油輪的整體時(shí)間表。
圖1 HCRL 模型的圖示
2.針對(duì) STSP 的 CL 策略
由于穿梭油輪路徑規(guī)劃問(wèn)題中路由與庫(kù)存管理之間的緊密耦合，穿梭油輪路徑規(guī)劃問(wèn)題的約束比典型的車(chē)輛路徑問(wèn)題（VRP）或旅行商問(wèn)題（TSP）問(wèn)題框架要復(fù)雜得多，其解空間也受到約束相關(guān)參數(shù)的極大影響。如果解空間（即強(qiáng)化學(xué)習(xí)范例下的動(dòng)作空間）過(guò)于復(fù)雜和不規(guī)則，神經(jīng)網(wǎng)絡(luò)模型的訓(xùn)練過(guò)程將會(huì)耗時(shí)，甚至無(wú)法收斂。為了解決這個(gè)問(wèn)題，一些策略被提出，例如傳統(tǒng)組合優(yōu)化中常用的懲罰函數(shù)法，以及將一些復(fù)雜的約束放松到損失函數(shù)中，以確保神經(jīng)網(wǎng)絡(luò)訓(xùn)練過(guò)程中動(dòng)作空間的基本穩(wěn)定性。
然而，這種策略將約束的復(fù)雜性轉(zhuǎn)移到了損失函數(shù)中，這也使得在訓(xùn)練過(guò)程中難以收斂。為了解決這個(gè)問(wèn)題，本文引入了 CL 策略。該策略將整個(gè)訓(xùn)練過(guò)程分為幾個(gè)階段。首先是確保解決方案是可行的，然后尋找最優(yōu)解。
圖2 分層強(qiáng)化學(xué)習(xí)策略下的遞歸過(guò)程
整個(gè)訓(xùn)練過(guò)程將被劃分為若干層，每一層都有不同的損失函數(shù)。后一層的損失函數(shù)包含前一層的損失函數(shù)。在較低層，約束組將被轉(zhuǎn)化為幾個(gè)懲罰函數(shù)，并添加到損失函數(shù)中。在前一層的強(qiáng)化學(xué)習(xí)層訓(xùn)練完成后，相應(yīng)的模型，也稱(chēng)為前一層的策略，將被保存并用于為所有后續(xù)層生成參考隱藏輸出向量。每一層都會(huì)根據(jù)當(dāng)前的狀態(tài)轉(zhuǎn)移概率模型（MDP）以及前一層的參考隱藏向量生成自己的輸出向量。該策略的詳細(xì)示意圖如圖2所示。
通過(guò)這種方式，在將包括油輪庫(kù)存能力懲罰、浮式生產(chǎn)儲(chǔ)卸油船庫(kù)存能力懲罰和時(shí)間窗口懲罰在內(nèi)的所有懲罰函數(shù)添加到損失函數(shù)中，并學(xué)習(xí)將其最小化為零之后，解決方案的可行性將得到保證。然后，將數(shù)學(xué)模型中的原始目標(biāo)函數(shù)作為最高強(qiáng)化學(xué)習(xí)層損失函數(shù)的最后一項(xiàng)引入。
實(shí)驗(yàn)結(jié)果及分析:
在我們的實(shí)驗(yàn)中，為了降低不必要的代碼復(fù)雜性，除了原始特征嵌入?yún)?shù)外，GNN、LSTM 和 Ptr-Net 中的所有可學(xué)習(xí)參數(shù)都被設(shè)置為Rd×d，其中 d = 128。穿梭油輪包含五個(gè)原始特征，而浮式生產(chǎn)儲(chǔ)卸油船（FPSOs）則包含八個(gè)原始特征，這意味著原始特征嵌入?yún)?shù)分別被設(shè)置為R5×d和R8×d。
1.變比例 STSP 實(shí)驗(yàn)
我們使用不同大小的多選擇背包問(wèn)題實(shí)例對(duì)模型進(jìn)行了訓(xùn)練，并在一個(gè)配備 R7-4800H CPU 和單個(gè) NVIDIA GTX 1660Ti GPU 的平臺(tái)上運(yùn)行了對(duì)比測(cè)試。為了評(píng)估所提出的模型，我們將所提出的 HCRL 模型的性能與通過(guò) Gurobi 10.0.1 求解的多選擇背包問(wèn)題模型以及改進(jìn)的人工魚(yú)群算法（AFSA）進(jìn)行了比較。人工魚(yú)的數(shù)量設(shè)置為20，并且Gurobi的時(shí)間限制被設(shè)定為1800秒。
基于CL架構(gòu)，我們將訓(xùn)練過(guò)程分為兩組迭代。在前五個(gè)迭代中，神經(jīng)網(wǎng)絡(luò)的參數(shù)在損失函數(shù)的約束下進(jìn)行初始化和更新，該損失函數(shù)將油輪庫(kù)存能力懲罰、浮式生產(chǎn)儲(chǔ)卸油船庫(kù)存能力懲罰和時(shí)間窗口懲罰相加，旨在確保生成解決方案的可行性。在接下來(lái)的十五個(gè)迭代中，總行程長(zhǎng)度將被添加到損失函數(shù)中，并訓(xùn)練神經(jīng)網(wǎng)絡(luò)生成一個(gè)可行且最優(yōu)的解決方案。我們?cè)?艘穿梭油輪與5艘浮式生產(chǎn)儲(chǔ)卸油船、8艘穿梭油輪與12艘浮式生產(chǎn)儲(chǔ)卸油船以及10艘穿梭油輪與16艘浮式生產(chǎn)儲(chǔ)卸油船的規(guī)模下進(jìn)行了實(shí)驗(yàn)。不同規(guī)模的STSP的兩個(gè)訓(xùn)練階段的成本曲線(xiàn)如圖3所示。
表1 不同方法下變比例 STSP 的比較
圖3 不同規(guī)模的 STSP 的懲罰階段和優(yōu)化階段的成本曲線(xiàn)。
在相同的隨機(jī)生成的原始數(shù)據(jù)下，不同方法的總路徑長(zhǎng)度和運(yùn)行時(shí)間的比較結(jié)果列于表1中。加粗的結(jié)果為最短的路徑長(zhǎng)度和運(yùn)行時(shí)間。蟻群算法的求解時(shí)間是首次在表中獲得最優(yōu)解所需的時(shí)間。表1顯示，在小規(guī)模問(wèn)題上，HCRL方法的求解結(jié)果與MILP方法接近，但其求解速度比MILP方法快得多。隨著問(wèn)題規(guī)模的增加，HCRL方法的求解結(jié)果逐漸不如MILP方法，而AFSA方法的求解性能隨著問(wèn)題規(guī)模的增加下降得比HCRL方法快，其求解速度也與HCRL方法存在一定差距。
2.HRL 結(jié)構(gòu)的異步優(yōu)化策略
由于所提出的模型依賴(lài)于兩個(gè) Ptr-Net，在生成一個(gè)整體動(dòng)作的結(jié)構(gòu)中，Ptr-Net 1 和 Ptr-Net 2 之間不可避免地存在強(qiáng)耦合，這可能會(huì)減緩收斂速度，甚至在極端情況下導(dǎo)致發(fā)散。為了解決這個(gè)問(wèn)題，開(kāi)發(fā)了一種基于采樣和貪心方法的異步優(yōu)化策略。
驗(yàn)證實(shí)驗(yàn)是在具有 10 艘穿梭油輪和 16 艘浮式生產(chǎn)儲(chǔ)卸油船規(guī)模的 STSP 上進(jìn)行的。結(jié)果如圖 4 所示。
圖4 一批 S10F16 STSP 實(shí)例在不同優(yōu)化策略下的懲罰層成本曲線(xiàn)
3.CL 策略驗(yàn)證
對(duì)于高度受限的問(wèn)題，如CVRPTW或MIRP，約束的滿(mǎn)足往往與目標(biāo)函數(shù)的優(yōu)化相沖突。當(dāng)這兩個(gè)組成部分從一開(kāi)始就納入損失函數(shù)時(shí)，確定梯度下降算法的方向就變得具有挑戰(zhàn)性。圖5所示的CL架構(gòu)的驗(yàn)證結(jié)果證明，引入的CL策略顯著提高了HRL 模型的性能。
圖5 不同學(xué)習(xí)策略下的一批 S10F16 STSP 實(shí)例的優(yōu)化層的成本曲線(xiàn)
結(jié)論:
我們提出了一種基于 GPN 的 HCRL 模型來(lái)解決 STSP 問(wèn)題。為了處理穿梭油輪艦隊(duì)內(nèi)部的交互，我們使用 LSTM 來(lái)嵌入穿梭油輪的特征。此外，引入圖神經(jīng)網(wǎng)絡(luò)來(lái)嵌入浮式生產(chǎn)儲(chǔ)卸油船（FPSOs）的特征。為了解決航程中路由決策之間的強(qiáng)耦合在運(yùn)營(yíng)階段的階段和庫(kù)存管理決策中，我們提出了一種異步優(yōu)化策略，并通過(guò)合理的實(shí)驗(yàn)驗(yàn)證了其有效性。實(shí)驗(yàn)表明，所提出的 HCRL 方法優(yōu)于傳統(tǒng)的元啟發(fā)式算法，并且在更短的時(shí)間內(nèi)產(chǎn)生了接近精確方法的令人滿(mǎn)意的結(jié)果。此外，對(duì)比性能分析實(shí)驗(yàn)驗(yàn)證了我們提出模型的可擴(kuò)展性。
除了本文已經(jīng)考慮的場(chǎng)景外，一些實(shí)際案例可能需要將建模范圍擴(kuò)大到包括多個(gè)港口和可變需求。另一方面，為穿梭油輪及其目的地提出的順序決策過(guò)程引入了一個(gè)潛在的不公平或偏好的問(wèn)題，因?yàn)橥ǔ］^早被選擇的穿梭油輪通常會(huì)獲得更大的行動(dòng)空間。
通訊作者簡(jiǎn)介:
高小永，人工智能學(xué)院副院長(zhǎng)，教授，博士生導(dǎo)師，石大學(xué)者，校青年拔尖人才，自動(dòng)化專(zhuān)業(yè)及控制科學(xué)與工程學(xué)科建設(shè)負(fù)責(zé)人，擔(dān)任北京自動(dòng)化學(xué)會(huì)常務(wù)理事、中國(guó)自動(dòng)化學(xué)會(huì)過(guò)程控制專(zhuān)業(yè)委員會(huì)委員、中國(guó)自動(dòng)化學(xué)會(huì)教育工作委員會(huì)委員、中國(guó)化工學(xué)會(huì)信息技術(shù)應(yīng)用專(zhuān)業(yè)委員會(huì)副秘書(shū)長(zhǎng)、中國(guó)系統(tǒng)工程學(xué)會(huì)過(guò)程系統(tǒng)工程專(zhuān)業(yè)委員會(huì)委員等。研究領(lǐng)域?yàn)閺?fù)雜石油石化工業(yè)過(guò)程智能制造，主要方向有：機(jī)理與數(shù)據(jù)驅(qū)動(dòng)的故障診斷、復(fù)雜工業(yè)過(guò)程建模與優(yōu)化控制、工業(yè)過(guò)程計(jì)劃與調(diào)度優(yōu)化等。主持國(guó)家自然科學(xué)基金項(xiàng)目2項(xiàng)、北京市自然科學(xué)基金面上項(xiàng)目1項(xiàng)、校企聯(lián)合項(xiàng)目20多項(xiàng)，發(fā)表SCI/EI等各類(lèi)論文50多篇。
Email：[email protected]