[發明專利]一種基于蟻群算法的最小開銷路由生成方法

有效

• 申請號: 202011046528.4
• 申請日: 2020-09-28
• 公開（公告）號: CN112149788B
• 公開（公告）日: 2023-04-07
• 發明（設計）人: 閆鈺龍;梁龍飛;環宇翔;鄒卓;鄭立榮
• 申請（專利權）人: 復旦大學;上海新氦類腦智能科技有限公司
• 主分類號: G06N3/006
• 分類號: G06N3/006;G06Q10/047
• 代理公司: 無錫經誠知識產權代理事務所(普通合伙) 32504
• 代理人: 丁雨燕

1.一種基于蟻群算法的最小開銷路由生成方法，包括至少一個神經元，每個所述神經元對應單次多播路由，在單次多播路由中，確定源芯片和目的地芯片，所述源芯片與所述目的地芯片之間包括至少一個用于構成路徑的可選芯片；其特征在于：在所述單次多播路由中，初始化蟻群算法參數，自定義蟻群規模及重復次數：

步驟(1)以所述源芯片為起點釋放第一只螞蟻，所述第一只螞蟻以每個所述可選芯片被選擇的概率為基準進行路徑訪問，至所述目的地芯片訪問完成，生成訪問路徑，并對每個所述可選芯片被選擇的概率進行更新；

步驟(2)以所述源芯片為起點釋放第二只螞蟻，按所述步驟(1)操作，至所述蟻群規模對應的所有螞蟻完成訪問；

步驟(3)以自定義重復次數對所述步驟(1)～步驟(2)進行迭代計算，取全局負載最低訪問路徑為單次多播路由路徑；為避免陷入局部最優，蟻群算法還需將上述過程重復K次，每次清空所有路徑上的信息素重新釋放m只螞蟻，即重復執行上述步驟；K次重復中記錄每次的全局負載，K次完成后取得所有過程中全局負載最低的一次作為最優解，視作蟻群算法的解；

步驟(4)以所述神經元的數量對所述步驟(1)～步驟(3)進行遍歷，直至生成所有神經元的多播路由；

所述蟻群算法參數包括：重復次數K、蟻群規模m、信息素濃度Q、揮發速度ρ、信息素啟發因子α和距離啟發因子β；

所述可選芯片被選擇的概率為p(i)，公式如下：

p(i)＝q(i)^α×d(i)^-β

其中，q(i)為第i個芯片累計的信息素濃度，d(i)為第i個芯片與螞蟻當前位置之間的距離；所述信息素濃度q(i)公式如下：

q(i)＝(1-ρ)×q(i)+Q/d_sum

其中，d_sum＝∑d(i)為該只螞蟻走過的路徑距離之和。