[發明專利]一種基于動態閾值搜索算法的內生系統關鍵節點識別方法

在審

• 申請號: 202310046778.5
• 申請日: 2023-01-31
• 公開（公告）號: CN116128054A
• 公開（公告）日: 2023-05-16
• 發明（設計）人: 孫雯;王鑄清;李文龍;胡愛群;陳超凡;吳自豪
• 申請（專利權）人: 東南大學
• 主分類號: G06N5/01
• 分類號: G06N5/01
• 代理公司: 南京眾聯專利代理有限公司 32206
• 代理人: 葉涓涓

1.一種基于動態閾值搜索算法的內生系統關鍵節點識別方法，其特征在于，包括如下步驟：

步驟1，通過約簡規則簡化問題

給定圖G＝(V,E)，采用三種精確約簡規則將其簡化為G＝(V₀,E₀)；

步驟2，貪心構造初始解

將頂點集v₀劃分為關鍵頂點集C₀與非關鍵頂點集U₀，采用一個排列π保存U₀中的頂點，貪心地選擇一個頂點加入π中，保證其不會增加π中的環數，重復此操作直到沒有頂點可以被加入，所得π即為初始解；

步驟3，利用局部搜索優化初始解

通過動態閾值搜索階段將搜索擴展到未開發的區域，通過下降搜索階段尋找新的局部最優解，兩個搜索階段交替進行，直到連續ω輪局部搜索都無法進一步改進最佳解為止；

步驟4，采用擾動方法，跳出局部最優區域

當搜索被困在一個深度局部最優時，啟動擾動過程，將一些特定識別的頂點在U₀和C₀之間移動從而跳出搜索陷阱，然后采用擾動后的解開始下一輪局部搜索過程；

步驟5執行恢復程序獲取完整反饋頂點集

算法循環執行步驟3與步驟4，如果在連續γ輪循環之后，迄今為止發現的最佳解無法改進，則結束循環，終止搜索，執行恢復程序，恢復程序將在搜索過程中找到的最小關鍵頂點集記為將其投影回原圖G＝(V,E)的反饋頂點集，從而得到最終的輸出解。

2.根據權利要求1所述的基于動態閾值搜索算法的內生系統關鍵節點識別方法，其特征在于，所述步驟1具體包括如下過程：

記約簡過程中被移除的頂點為冗余頂點集V_r，其中冗余關鍵頂點集記為C_r，冗余非關鍵頂點集記為U_r；遍歷給定圖G＝(V,E)中的所有頂點，遵循以下三個規則進行圖約簡過程：

規則1：如果頂點v的入度或出度為0，即v是一個非關鍵頂點，則可以刪除v及其所有連接的邊，而不遺漏圖G的任何最優反饋頂點；這些頂點被加入到冗余非關鍵頂點集U_r中；

規則2：如果頂點v的入度或出度為1，且不存在自環，則頂點v與唯一的前驅或后繼頂點合并，而不會遺漏圖G的任何最優反饋頂點；將v加入到冗余非關鍵頂點集U_r中；

規則3：如果頂點v存在自循環，則v及其所有連接的邊可以被刪除并恢復為反饋頂點集的一部分，而不會丟失圖G的任何最優反饋頂點；這些頂點被添加到冗余關鍵頂點集C_r中；

刪除集合U_r和C_r，剩下的頂點集V₀＝V\(U_r∪C_r)，縮減子圖G＝(V₀,E₀)，E₀＝(V₀×V₀∩E)；在得到約簡圖G后，利用貪婪初始化生成其初始解。

3.根據權利要求2所述的基于動態閾值搜索算法的內生系統關鍵節點識別方法，其特征在于，所述規則2中，合并過程是所有與頂點v相連的邊都鏈接到唯一的前驅或后繼頂點。