[發明專利]一種基于鳥類物種進化機制的路徑優化方法

有效

• 申請號: 201410849285.6
• 申請日: 2014-12-30
• 公開（公告）號: CN104504477B
• 公開（公告）日: 2018-01-09
• 發明（設計）人: 何兆成;周亞強
• 申請（專利權）人: 中山大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 廣州粵高專利商標代理有限公司44102
• 代理人: 林麗明

技術領域

本發明涉及網絡路徑優化領域，更具體地，涉及一種基于鳥類物種進化機制的路徑優化方法。

背景技術

最短路徑問題是網絡優化中最基本的問題，在多跳網絡的路由分配以及在事故搶修、交通指揮、GPS導航等行業應用中使用的非常廣泛，快速的路徑尋優算法能使系統可以充分的利用網絡資源，滿足客戶需求。

(1)求解單源最短路徑的取值非負問題，最經典的方法為Dijkstra算法，Dijkstra算法又稱為單源最短路徑，它能求從一個頂點出發，到所有可到達頂點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法的優點是100％能得出最短路徑的最優解，但由于它遍歷計算的節點很多，所以有效率低的缺點。

(2)Chang Wook Ahn等提出利用遺傳算法求解最短路徑問題，該方法把可行路徑分解成若干段，在保證路段拓撲連通性的前提下，利用交叉算子交互可變路段，利用變異算子引入新的路段，不斷迭代直到算法收斂得到最短路徑。該法的主要缺點有兩個：一是算法對新空間的探索能力是有限的，容易收斂到局部最優解。二是算法屬于隨機類算法，需要多次運算，結果的可靠性差，不能穩定的得到解。

鳥類是世界上最大的四足類脊椎動物，鳥類繁殖進化的過程與優化問題有很多共通之處，鳥類共有5種繁殖方式，包括單性生殖，單配制，一夫多妻制，一妻多夫制度，多夫多妻制，每只鳥類將按照其自身的方式繁衍后代。

發明內容

為了克服上述現有路徑尋找方法存在的不足，本發明提出一種基于鳥類物種進化機制的路徑優化方法，尋找出最短的路徑，該方法模仿了鳥類物種特有的衍化后代的方式，通過模仿鳥類的繁殖進化方式來求解圖論中的最短路徑問題，能夠提高尋優效率和收斂速度。

為了解決上述的不足，本發明的技術方案為：

一種基于鳥類物種進化機制的路徑優化方法，包括：

S1.隨機生成若干條可行路徑，每一條路徑對應一只鳥類的染色體，每一個節點對應染色體上的一個基因，基因長度為路徑長度，基因順序為路徑節點順序；

S2.確定經過可行路徑所需的花費作為適應性函數；

S3.根據經過每條可行路徑花費的多少對可行路徑進行排序，并對其進行分類，其具體分類方式如下：

1)根據花費的多少將可行路徑分為雌性類和雄性類，其中，花費小于等于閾值A時，則對應的可行路徑屬于雌性類，否則屬于雄性類；

2)對屬于雌性類的可行路徑進行分類，根據花費將其分為單性生殖類和一妻多夫制類，其中，花費小于等于閾值B時，則對應的可行路徑屬于單性生殖類，否則屬于一妻多夫制類；

對屬于雄性類的可行路徑進行分類，根據花費將其分為單配制類、一夫多妻制類和多夫多妻制類，其中，花費小于等于閾值C時，則對應的可行路徑屬于單配制類，花費大于閾值C且小于等于閾值D時，則屬于一夫多妻制類，花費大于閾值D時，則屬于多夫多妻制類；

其中A>B，D>C>A；

S4.計算屬于多夫多妻制類的可行路徑的數目為E，并重新隨機生成αE個新可行路徑，0<α<1，替代屬于多夫多妻制類的αE個可行路徑；

S5.對各條可行路徑按照其所屬鳥類物種進化方式進行繁殖重構，完成繁殖重構后，比較父代個體與子代個體的路徑長度，保留花費少的可行路徑；

S6.重復步驟S3到S5直到到達設定的迭代次數閾值，獲取若干條可行路徑；

S7.對步驟S6獲取的可行路徑中選取花費最少的路徑作為優選路徑。

優選的，所述步驟S5中所述的各條可行路徑按照其所屬鳥類物種進化方式進行繁殖重構的具體方式如下：

當可行路徑屬于單性生殖類時，其繁殖重構方式為：

101)為每個節點生成一個節點變異概率rn_i，當rn_i大于節點變異概率閾值時，則該節點發生變異，兩個變異節點間的基因片段為待變異基因片段；

102)為每個待變異基因片段生成一個基因變異概率rpv_j，當rpv_j大于基因片段變異概率閾值時，該基因片段發生變異，根據該段基因的首尾節點重新生成一條可行路徑替換掉對應的待變異基因片段；

當可行路徑屬于單配制類時，則與屬于單性生殖類或一妻多夫制類的可行路徑進行繁殖重構獲取子代個體，其具體方式為：

201)搜索兩條可行路徑間相同的節點，并以首尾節點相同的部分路段集作為待交換基因片段；