[發(fā)明專利]一種基于改進(jìn)強(qiáng)化學(xué)習(xí)的復(fù)雜網(wǎng)絡(luò)局部破壞的自改進(jìn)恢復(fù)策略

在審

• 申請(qǐng)?zhí)枺?/td>: 201810375758.1
• 申請(qǐng)日: 2018-04-25
• 公開(kāi)（公告）號(hào): CN108573303A
• 公開(kāi)（公告）日: 2018-09-25
• 發(fā)明（設(shè)計(jì)）人: 馮強(qiáng);吳其隆;任羿;孫博;楊德真
• 申請(qǐng)（專利權(quán)）人: 北京航空航天大學(xué)
• 主分類號(hào): G06N3/04
• 分類號(hào): G06N3/04;G06N3/08
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

本發(fā)明公開(kāi)了一種基于改進(jìn)強(qiáng)化學(xué)習(xí)的復(fù)雜網(wǎng)絡(luò)局部破壞的自改進(jìn)恢復(fù)策略方法，解決了復(fù)雜網(wǎng)絡(luò)進(jìn)行集群維修的恢復(fù)策略生成的問(wèn)題。步驟如下：1根據(jù)局部破壞信息建立復(fù)雜網(wǎng)絡(luò)的集群維修狀態(tài)矩陣。2基于初始集群維修狀態(tài)生成復(fù)雜網(wǎng)絡(luò)鄰接矩陣。3基于神經(jīng)網(wǎng)絡(luò)模型預(yù)測(cè)集群的先驗(yàn)維修狀態(tài)轉(zhuǎn)移概率和維修策略價(jià)值。4基于蒙特卡洛樹(shù)搜索算法遍歷集群的維修策略解空間，并選擇當(dāng)前時(shí)刻全局最佳維修動(dòng)作。5基于集群維修狀態(tài)的變化更新復(fù)雜網(wǎng)絡(luò)鄰接矩陣。6基于集群維修狀態(tài)和鄰接矩陣計(jì)算并檢驗(yàn)復(fù)雜網(wǎng)絡(luò)的恢復(fù)程度。7基于強(qiáng)化學(xué)習(xí)經(jīng)驗(yàn)參數(shù)訓(xùn)練神經(jīng)網(wǎng)絡(luò)參數(shù)。8基于恢復(fù)策略自改進(jìn)過(guò)程的一系列最佳維修動(dòng)作生成一個(gè)完整的維修恢復(fù)方案。

所屬技術(shù)領(lǐng)域

本發(fā)明提供一種基于改進(jìn)強(qiáng)化學(xué)習(xí)的復(fù)雜網(wǎng)絡(luò)局部破壞狀態(tài)下的自改進(jìn)恢復(fù)策略(Self-improvement Recovery Strategy，SIRS)方法，尤其涉及一種考慮網(wǎng)絡(luò)節(jié)點(diǎn)組成單元特征，基于改進(jìn)的強(qiáng)化學(xué)習(xí)算法，實(shí)現(xiàn)自改進(jìn)求解復(fù)雜網(wǎng)絡(luò)多節(jié)點(diǎn)集群維修的恢復(fù)策略方法，屬于維修性工程領(lǐng)域。

背景技術(shù)

自改進(jìn)恢復(fù)策略(SIRS)是指復(fù)雜網(wǎng)絡(luò)發(fā)生局部破壞后，破壞位置出現(xiàn)多節(jié)點(diǎn)集中不可用的情況，通過(guò)集群維修的方式快速搶修至整體可用狀態(tài)。但目前國(guó)內(nèi)外關(guān)于集群維修的研究一般不考慮時(shí)序。隨著維修性越來(lái)越受到重視，對(duì)復(fù)雜網(wǎng)絡(luò)開(kāi)展集群維修策略的研究提出了更高的要求，即充分考慮集群維修的時(shí)序和收益不確定特征，以及問(wèn)題整體的NP-hard特征，提供一種高效的集群維修策略方法。

本發(fā)明基于維修狀態(tài)轉(zhuǎn)移概率的神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)模型和蒙特卡洛樹(shù)搜索(MonteCarlo Tree Search，MCTS)算法，發(fā)明了一種基于改進(jìn)強(qiáng)化學(xué)習(xí)的新型的自改進(jìn)恢復(fù)策略(SIRS)方法，解決了復(fù)雜網(wǎng)絡(luò)局部破壞狀態(tài)下的集群維修策略生成的問(wèn)題。

發(fā)明內(nèi)容

本發(fā)明的目的是為局部破壞狀態(tài)下的復(fù)雜網(wǎng)絡(luò)提供一種新型的自改進(jìn)恢復(fù)策略(SIRS)方法，旨在解決傳統(tǒng)集群維修策略方法未充分考慮集群維修的時(shí)序和收益不確定特征，以及問(wèn)題整體的NP-hard特征等問(wèn)題。

本發(fā)明提出了一種基于神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)模型和蒙特卡洛樹(shù)搜索(MCTS)算法的SIRS方法，主要包含以下步驟：

步驟一：基于局部破壞建立復(fù)雜網(wǎng)絡(luò)的集群維修狀態(tài)矩陣。

將復(fù)雜網(wǎng)絡(luò)局部破壞恢復(fù)策略視為多節(jié)點(diǎn)的集群維修問(wèn)題展開(kāi)研究。首先，構(gòu)建復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)集合K＝{k₁,k₂,…,k_i,…,k_j,…,k_n}(其中n為節(jié)點(diǎn)的個(gè)數(shù))，將各節(jié)點(diǎn)的組成進(jìn)行拆解，建立其單元集合U＝{u₁,u₂,…,u_m}。以此為基礎(chǔ)，建立m×n的“節(jié)點(diǎn)-單元”矩陣，并根據(jù)局部破壞信息，用“0”表示待維修的局部破壞空間中的故障單元，“1”表示正常單元，對(duì)矩陣中元素賦值，形成維修狀態(tài)矩陣S。

步驟二：基于初始集群維修狀態(tài)生成復(fù)雜網(wǎng)絡(luò)鄰接矩陣。

將一個(gè)復(fù)雜網(wǎng)絡(luò)抽象為一個(gè)由節(jié)點(diǎn)集K＝{k₁,k₂,…,k_i,…,k_j,…,k_n}和連接(邊)集組成的圖G＝(K,E)。用一個(gè)n×n的鄰接矩陣A描述復(fù)雜網(wǎng)絡(luò)中n個(gè)節(jié)點(diǎn)之間的連接關(guān)系(邊)，且不考慮自環(huán)。當(dāng)復(fù)雜網(wǎng)絡(luò)中所有單元均正常時(shí)，鄰接矩陣記為A*。

將節(jié)點(diǎn)k_i的單元集U_i＝{u₁,u₂,…,u_m}分為三類單元集則表示單元集中的所有節(jié)點(diǎn)均為破壞空間中的故障單元，同理可以對(duì)和兩類單元集進(jìn)行描述?；谏鲜龇诸悾怨?jié)點(diǎn)k_i為例，假設(shè)維修狀態(tài)矩陣S中元素與鄰接矩陣A中元素的映射關(guān)系f_S→A為