[發明專利]基于層級結構學習自動機的隨機最短路徑實現方法

有效

• 申請號: 201710054545.4
• 申請日: 2017-01-24
• 公開（公告）號: CN106953801B
• 公開（公告）日: 2020-05-05
• 發明（設計）人: 李生紅;郭穎;馬穎華;湯璐
• 申請（專利權）人: 上海交通大學
• 主分類號: H04L12/721
• 分類號: H04L12/721;H04L12/733;H04L12/801
• 代理公司: 上海交達專利事務所 31201
• 代理人: 王毓理;王錫麟

1.一種基于層級結構學習自動機的隨機最短路徑實現方法，其特征在于，通過層級結構的學習自動機網絡逐層更新收斂，當任一層網絡達到收斂條件時，通過剔除該層最優節點除外的節點及其子節點進行層級結構修剪，從而將選擇最短路徑的問題轉換為定位最優節點的問題，最終得到的最短路徑即從第一層到最后一層的最優節點組成的序列；

所述的學習自動機網絡中，源節點作為父節點，目標節點作為葉子節點；所述的層級結構具體是指：隨機網絡G＝(V,E,F)，其中：V＝{1,2,…，n}表示節點的集合，表示邊的集合，F是n×n的矩陣，n等于節點V的個數，每個元素F_i,j指邊(i,j)的長度L_ij的概率分布函數；該層級結構網絡的源節點為v_s，目標節點為v_d，每個節點的父節點均逐一指向源節點v_s；

所述的逐層更新，具體包括以下步驟：

①選取層級結構中的當前路徑中相鄰節點的隨機路徑依次相加，得到當前路徑的代價值L_φ；

②用動態閾值T_K表示目前為止的所有采樣路徑的均值：當路徑代價L_φ小于動態閾值T_K時，獎勵路徑φ上的所有學習自動機；否則懲罰路徑φ上的所有學習自動機；

③學習自動機根據Lri學習算法更新自身的概率向量；

④更新動態閾值其中：k表示迭代次數；

所述的收斂是指：當父節點v_p的最大概率大于預先設定的閾值P_m時該層更新終止，移動父節點v_p至最大概率對應的行為所在的節點，即概率最大的子節點，并進行下一層更新，直到父節點v_p到達目標節點v_d，完整整個網絡更新。

2.根據權利要求1所述的實現方法，其特征是，所述的層級結構具體通過以下方式實現初始化：從源節點v_s出發，在v_s上部署一個學習自動機，該學習自動機行為的個數等于v_s的出度；從v_s的各個鄰居節點v₂出發，在各個v₂上分別部署一個學習自動機，其行為個數等于v₂的出度；再從v₂的各個鄰居節點v₃出發，逐層按相同方式部署學習自動機，直到目標節點v_d的學習自動機部署完成；最后刪去未部署學習自動機的節點，由此形成了學習自動機的分布式網絡；每個學習自動機各自完成初始化工作，初始化各自的概率向量為均勻分布；設置當前節點為父節點，逐層依次選擇下一節點，所有節點組成當前路徑φ。

3.根據權利要求1所述的實現方法，其特征是，所述的Lri學習算法是指：學習自動機在環境獎勵時更新概率向量，在環境懲罰時不更新概率向量的機制，具體是指：p(k+1)＝T(p(k))ifβ＝1,p(k+1)＝p(k)，其中：T為更新機制。