RL

• 通用超參數(shù)

DQN改進

Duel Structure

VS→該state在當前policy下的value

QSA→該state進行這個action在當前policy下的value

advantage = VS - QSA

裁剪區(qū)域的確定？

34194按行輸出min，33193min為90*90

Replay buffer

background knowledge

[bisect Module]
python自帶的二分查找的包

重要函數(shù)

基本使用

bisect.bisect_left(2)//返回2左端index
bisect.bisect()//與bisect_right()相同
bisect.bisect_right()//返回右端index

bisect with list

在一個increasing array插入一個元素并仍保持有序

def list_insert(arr,num):
	ind = bisect.bisect_left(arr,num)
	arr.insert(ind,num)

a = [0,1,2,2,2,3,4]
list_insert(a,2.1)

[Sum Tree]
概念

Sum Tree 線段樹，結(jié)構(gòu)是二叉樹，父節(jié)點是子節(jié)點的和，且只有度為0和2的情況。

可以認為葉結(jié)點表示一個相連的區(qū)間，每個葉節(jié)點的數(shù)值表示該區(qū)間長度，此時可以輕易找到任意值的對應區(qū)間的葉節(jié)點

Basic Replay Buffer

• 記錄新加入的transition→存儲在list中
• 忘記太久之前的transition→用deque數(shù)據(jù)自動遺忘，也可以覆蓋list中已存在的transition
• 從存儲的記憶中抽樣→用random.sample()抽樣

Proportion-based Replay Buffer

Sum Tree用于記錄和更新cumulative weight以進行快速采樣，時間復雜度為O（logn）新功能：

• 一個Sum Tree儲存和更新每個transition的weight
• 更新Sum Tree的方法

Rank-based Repley buffer

需要知道每個transition的td_error的rank1以調(diào)整weight，基于該rank需要計算和儲存分割點，從而進行抽樣，復雜度為o（n），新功能：

• 1.對于所有transition TD_error及對應rank的存儲
• 2.更新rank的方法

由于訓練過程中有大量TDerror變更，以及新加入的transition，快速更新rank需要一直維持記錄一個排好序的所有TD-error的序列，這樣才能在o（logn）的時間內(nèi)確定rank，否則每個新樣本加入時更新rank都需要O（n）的時間

快速抽樣的方法是在有序TD-error的序列上抽樣在對應到具體的transition，此處有倆種存儲方式

• 將transition與TD-error一起儲存在tuple中
• 將transition儲存在list中，將其index和TD-error一起存儲到tuple中

第一鐘方式缺點：當我們刪除transition時，會需要O（n）時間尋找應該刪除的rank和TD-error。選擇第二種存儲方式，locate時間復雜度為o（1），具體如下

• 與之前的方式類似，建立一個list存儲transition
• 建立另一個list存儲transition對應rank
• 建立第三個list儲存TD-error，transition index的tuple

刪改操作時間復雜度O（n）

• gnn meets rl

  https://github.com/knowledgedefinednetworking/DRL-GNN/blob/master/DQN/README.md

• sp

  OSPF：OSPF 即開路最短路徑優(yōu)先，依據(jù)該規(guī)則，網(wǎng)絡會把數(shù)據(jù)流轉(zhuǎn)發(fā)在長度最短的路徑上，

  由于沒有考慮鏈路的傳輸能力，個別鏈路容易陷入擁塞。

  MCFCSP：多物網(wǎng)絡流流約束最短路徑方案將鏈路的傳輸能力作為約束條件，在保證網(wǎng)絡不出現(xiàn)

  擁塞的條件下傳輸數(shù)據(jù)流。

  KSP：k 路最短路徑方案會在兩節(jié)點對間選擇前 k 條最短的路徑作為路由路徑對數(shù)據(jù)流完成轉(zhuǎn)發(fā)操作。

  多路徑路由(ECMP)**：**在多個傳輸路徑上均勻地分配流量

• rsir

  

• 牽引控制

  DRL算法分類：基于下一跳控制的 DRL 路由方案、基于逐個數(shù)據(jù)流路徑調(diào)整的 DRL 路由方案和基于全網(wǎng)鏈路權(quán)重調(diào)整的路由方案

  通過分析網(wǎng)絡拓撲特征，結(jié)合牽引控制理論，選取部分鏈路作為代表鏈路，DRL對代表鏈路生成控制信號，結(jié)合網(wǎng)絡路由算法擴展到全網(wǎng)路由。

  優(yōu)點：避免輸出動作空間過大，解決DRL維度災難問題，策略更加健壯

  牽引鏈路選?。河捎跔恳刂评碚撃壳吧形磳碗s網(wǎng)絡的具體牽引控制元素選擇做出選擇，設(shè)計啟發(fā)式算法選取牽引節(jié)點

  • 在線路由策略部署階段主要分為 3 個環(huán)節(jié)：

    1. 網(wǎng)絡信息收集

       OpenFlow端口數(shù)據(jù)量統(tǒng)計字段結(jié)合采集間隔,近似計算相應端口的數(shù)據(jù)吞吐量,形成牽引鏈路的流量視圖,作為DRL 神經(jīng)網(wǎng)絡的輸入?yún)?shù)

    2. 智能策略生成：每個輸出層對應于一個牽引鏈路的權(quán)重

    3. 策略執(zhí)行

       默認將所有鏈路權(quán)重設(shè)置為 1，用DRL輸出更新相應鏈路權(quán)重，通過 Floyd-Warshall 算法計算路由。

  DRL算法： TD3

  state為網(wǎng)絡中鏈路的吞吐量信息

  action對應于牽引鏈路的權(quán)重

  reward綜合考慮路由策略在平均時延、負載均衡和抖動等

• Scalable DRL

  中心性的概念類似于描述一個頂點與其他頂點的關(guān)系的圖中的度的概念，該鏈路與其他鏈路共享更多的轉(zhuǎn)發(fā)路徑，即具有較高的中心性。

  在ScaleDRL中，我們根據(jù)每個鏈路的中心性來選擇關(guān)鍵鏈路。根據(jù)所有鏈路的中心性值按降序排序，并從排序的鏈路列表中選擇中間的k個鏈路作為關(guān)鍵鏈路。

  • DRL：ACKTR

    行為網(wǎng)絡以網(wǎng)絡狀態(tài)作為輸入，其輸出作為動作a

    批評網(wǎng)絡以網(wǎng)絡狀態(tài)和臨時動作a作為輸入，對臨時策略生成評價值。獎勵r用于更新批評者網(wǎng)絡。

    狀態(tài)：每個鏈路上的流量強度分布

    動作：a^|L|·d，表示關(guān)鍵鏈接的數(shù)量，其中|L|表示關(guān)鍵鏈接的數(shù)量，d表示每個流的候選路徑數(shù)。

    獎勵：使用平均端到端延遲作為評估TE策略的度量標準。

• Scalable Routing

  優(yōu)點：提高路由性能和對拓撲變化的彈性。

  ScaleDeep將網(wǎng)絡的節(jié)點分為兩類：驅(qū)動節(jié)點和跟隨節(jié)點。驅(qū)動節(jié)點是可以模擬網(wǎng)絡運行的關(guān)鍵節(jié)點，采用釘扎控制理論進行選擇，其余節(jié)點為跟隨節(jié)點。

  通過從驅(qū)動節(jié)點輪詢網(wǎng)絡信息，DRL代理可以有一個近似的網(wǎng)絡全局視圖。調(diào)整驅(qū)動節(jié)點的鏈路權(quán)值，以動態(tài)更新路由策略。

  驅(qū)動節(jié)點選擇的啟發(fā)式算法：以不同的選擇概率分配不同程度的節(jié)點，然后根據(jù)選擇概率選擇驅(qū)動節(jié)點。根據(jù)節(jié)點的程度分配（分類？）不同概率的節(jié)點，然后根據(jù)其概率選擇驅(qū)動節(jié)點。

  DRL：ddpg

  DRL框架使用了兩種類型的神經(jīng)網(wǎng)絡：門控遞歸單元(GRU)和前饋神經(jīng)網(wǎng)絡。GRU是一種先進的遞歸神經(jīng)網(wǎng)絡(RNN)，善于從輸入數(shù)據(jù)中提取與時間相關(guān)的信息。

  狀態(tài)：狀態(tài)是網(wǎng)絡狀態(tài)信息表示的吞吐量矩陣大小t×n，其中t表示時間步長的長度，d表示流類型的數(shù)量，和n表示總數(shù)的交通強度

  獎勵r：網(wǎng)絡中所有流的平均流完成時間

• 基于深度強化學習的軟件定義網(wǎng)絡 QoS 優(yōu)化

  優(yōu)點：保證了端到端傳輸時延和分組丟失率，而且提高了 22.7%的網(wǎng)絡負載均衡程度，增加了 8.2%的網(wǎng)絡吞吐率。

  解決：基于啟發(fā)式算法的 QoS 優(yōu)化方案因參數(shù)與網(wǎng)絡場景不匹配出現(xiàn)性能下降的問題

  方案：首先將網(wǎng)絡資源和狀態(tài)信息統(tǒng)一到網(wǎng)絡模型中，然后通過長短期記憶網(wǎng)絡提升算法的流量感知能力，最后基于深度強化學習生成滿足 QoS 目標的動態(tài)流量調(diào)度策略。

  狀態(tài)：某一次網(wǎng)絡測量時網(wǎng)絡中的流請求信息和所有鏈路的時延和利用率信息

  動作：各節(jié)點對之間可用轉(zhuǎn)發(fā)路徑的分流比重

  獎賞：優(yōu)化目標是最小化網(wǎng)絡使用率U。r=-U。

  LSTM 網(wǎng)絡負責對網(wǎng)絡狀態(tài)信息 s 進行預處理生成隱含狀態(tài) h，并將該隱含狀態(tài)傳輸給 Actor 和 Critic 架構(gòu)中的神經(jīng)網(wǎng)絡，提高神經(jīng)網(wǎng)絡的決策的效率和準確性；Actor 和 Critic 架構(gòu)中的神經(jīng)網(wǎng)絡依據(jù)LSTM網(wǎng)絡提供的網(wǎng)絡狀態(tài)數(shù)據(jù)生成動作，并更新內(nèi)部網(wǎng)絡參數(shù)。文章來源地址http://www.zghlxwxcb.cn/news/detail-849948.html

到了這里，關(guān)于強化學習-DQN改進及一些強化學習路由優(yōu)化論文筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！