[發明專利]一種兩步式X結構Steiner最小樹構建方法

有效

• 申請號: 202010410094.5
• 申請日: 2020-05-14
• 公開（公告）號: CN111582431B
• 公開（公告）日: 2022-07-08
• 發明（設計）人: 劉耿耿;陳曉華;郭文忠;陳國龍
• 申請（專利權）人: 福州大學
• 主分類號: G06N3/00
• 分類號: G06N3/00
• 代理公司: 福州元創專利商標代理有限公司 35100
• 代理人: 錢莉;蔡學俊

1.一種兩步式X結構Steiner最小樹構建方法，其特征在于：包括以下步驟：

步驟S1：提供X結構模型，進行社會學習離散粒子群搜索階段，通過粒子群優化算法找到一棵具有較短線長的次優X結構Steiner樹；

步驟S2：線長優化階段：設計了一種基于局部拓撲優化的策略用以最小化X結構Steiner樹的線長；從而構建出一棵線長最短的X結構Steiner樹模型，也就是X結構Steiner最小樹；

所述步驟S1具體包括以下步驟：

步驟S11：使用能夠保持粒子最優拓撲信息的邊點對編碼策略；

步驟S12：設計考慮線長的適應度函數；

步驟S13：采用了一種混沌下降變異策略和新的社會學習策略用以設計出新的離散粒子群更新公式；

所述步驟S11的具體內容為：

所述邊點對編碼策略是使用一條生成樹的邊和這條邊的PS點選擇方式來表示候選X結構Steiner樹的一條邊；PS點選擇方式是將生成樹的邊轉化成為X結構Steiner樹的X結構邊；每個PS點選擇方式包含4種選擇，即0選擇、1選擇、2選擇和3選擇；如果一個布線樹有n個引腳，每棵候選X結構Steiner樹包含n-1條生成樹的邊、n-1位PS點選擇方式及一位數字表示粒子的適應度函數值；又由于一條生成樹的邊需要兩位數字表示該邊的兩個引腳，所以每個粒子編碼的總長度為3(n-1)+1；

所述步驟S12的具體內容為：

一棵候選X結構Steiner樹的長度是該布線樹中所有邊線段的長度總和：

其中l(e_i′)表示在布線樹T_x中每個邊線段e_i′的長度；所以粒子的適應度函數設計如下：fitness＝L(T_x) (2)；

步驟S13中所述混沌下降變異策略的具體內容為：

采用Logistic映射來產生混沌變量，其公式如下：

z_t+1＝μ·z_t·(1-z_t),t＝0,1,2,... (3)

其中，z∈(0,1)是混沌變量，混沌變量的初始值z₀≠{0.25,0.5,0.75}，否則產生的隨機序列將具有周期性；μ∈[0,4]是控制參數，如果μ＝4，logistic映射將呈現完全的混沌動力學，混沌變量的軌跡在整個搜索空間內都是稠密的，這意味著其混沌結果的區間為[0,1]；

為了使粒子群優化算法在迭代前期具有強的全局勘探能力，而在后期能夠快速收斂，同時保持粒子在整個迭代過程中變異的隨機性，使用如下具有混沌下降性質的慣性權重：

其中，w_init和w_end分別是慣性權重w的初始值和結束值，Maxiter和iter分別是最大迭代次數的和當前迭代次數，z是混沌變量，遵循公式(3)；這樣，慣性權重既具有混沌特性，同時又能保持原有的變化趨勢；

步驟S13中所述新的社會學習策略的具體內容為：

首先，將當前種群中的所有粒子按適應度函數值大小升序排列，則對于每個粒子，位于其前面的粒子群構成了該粒子的樣例池；然后，粒子在每次迭代時，都會從自身當前的樣例池中隨機選擇一個粒子作為學習對象；當粒子選擇的學習對象是其樣例池中的第一個粒子，則粒子此時的學習對象就是種群最優粒子；接著，粒子通過學習其學習對象的歷史最優經驗，來完成各自的社會學習行為；在這個過程中，不同的粒子，其學習對象不同；而同一個粒子，在不同的迭代即每次社會學習中，其樣例池也不一定相同；因此，粒子的社會學習不再單一地只向種群最優粒子學習，當前種群中任何一個更優秀的粒子都可能成為該粒子的學習對象；這樣的學習過程允許粒子在進化過程中通過不斷學習不同的優秀個體來提升自己，有利于種群的多樣化發展，從而有機會探索到更佳的X結構Steiner樹模型；

所述步驟S2的具體內容為：

基于局部拓撲優化的策略遍歷每個引腳至多q條鄰接邊，并進行調整，其中，1≤q≤Q，Q為布線樹中引腳的最大度數；同時，通過調整參數q的大小，能夠獲得更好的優化效果或更短的運行時間；q值越接近Q，優化效果就越好；每個引腳被賦予兩個屬性，一個是該引腳的度數degree，代表了其鄰接點的個數；另一個是該引腳的鄰接點列表adj_list[]，用來存儲各個鄰接點；該階段具體的實現過程如下：

步驟SA:記錄X結構Steiner樹中每個引腳的度數及其鄰接點列表,對于度數大于q的引腳來說，僅僅記錄該引腳的q個鄰接點；

步驟SB:設置局部拓撲優化的順序為：從度數大的引腳往度數小的引腳優化；通過將所有引腳按度數從大到小排列，同時將每個引腳的鄰接點也按度數從大到小排列，來實現先優化密集區域的拓撲結構，再優化稀疏區域的拓撲結構；

步驟SC:依次優化各個引腳的局部拓撲結構,通過對引腳與各個鄰接點之間邊的選擇方式進行調整，嘗試用除當前選擇方式以外的其余三種選擇方式進行連接，從中保留適應度函數值最小的連接方式；即通過調整X結構Steiner樹中各個引腳的q條鄰接邊的PS點選擇方式，以獲得在當前X結構Steiner樹拓撲下的局部最優結構，最終構建具有最短線長的X結構Steiner樹。