[發明專利]一種基于量子遺傳策略的QG-OLSR路由方法

有效

• 申請號: 201611190752.4
• 申請日: 2016-12-21
• 公開（公告）號: CN106658639B
• 公開（公告）日: 2020-05-12
• 發明（設計）人: 張德干;葛輝;馬震;趙德新;劉冰
• 申請（專利權）人: 天津理工大學
• 主分類號: H04W40/10
• 分類號: H04W40/10;H04W84/18
• 代理公司: 天津佳盟知識產權代理有限公司 12002
• 代理人: 顏濟奎

1.一種基于量子遺傳策略的QG-OLSR路由方法，其特征在于該方法主要包括如下步驟：

第1、QGA基本原理模型結構：

第1.1、基本遺傳算法采用比例選擇策略；

第1.2、在基本遺傳算法中，階次低，定義長度短且適應度超過平均適應度值的模式的數據以指數級增長，適應度小于平均適應度值的模式的數據以指數級減小；

第1.3、量子遺傳算法能收斂到全局最優解；

第2、改進QGA算法模型：

第2.1、初始化節點基因鏈；

第2.2、修復最優個體集合；

第3、編碼及初始化：

第3.1、針對OLSR的量子遺傳算法的基因鏈，采用0-1方式進行編碼，考慮全局性及基因交叉變異問題，設定染色體長度等于網路拓撲中節點總個數；

第3.2、初始化群體中，將群體中所有個體的染色體基因位的概率振幅的“0”和“1”狀態位初始化為

第4、初始群體的選擇：

第4.1、啟發式規則選擇節點i的MPR集合；

第4.2、適應度函數選擇節點i的MPR集合；

第5、基因鏈交叉和變異：

第5.1、基因鏈交叉操作，針對網絡拓撲高度動態性的特點，選擇量子交叉策略；

第5.2、基因鏈變異操作，先對個體層次發生變異的概率進行判斷，再判斷個體基因鏈的基因位發生變異的概率；

第6、基因鏈更新：

動態調整量子旋轉門的旋轉角度，根據遺傳代數的不同，將旋轉角度的值的大小在0.1π和0.05π之間動態調整；

第7、修復策略：

對節點i的MPR集合中的節點進行維護，使用啟發式規則；對于節點i的兩跳鄰居表中一個節點j，若該節點j沒有被新個體的任何一個節點覆蓋，則在節點i的一跳鄰居節點表中指定一個覆蓋j的且覆蓋能力最強的節點進入節點i的MPR集合中。

2.如權利要求1所述的基于量子遺傳策略的QG-OLSR路由方法，其特征在于該方法中，步驟第1.1中基本遺傳算法采用比例選擇策略，交叉概率和變異概率分別為P_c和P_m，且取值最小，模式H的定義長度為δ(H)，階為ο(H)，第t+1代種群Q(t+1)含有H中的元素個數為m(H,t+1)，則以下不等式成立：

第1.2、在基本遺傳算法中，階次低，定義長度短且適應度超過平均適應度值的模式的數據以指數級增長，適應度小于平均適應度值的模式的數據以指數級減小；在選擇算子的租用下，當模式H的平均適應度f大于群體Q的平均適應度時，模式H以指數級增長，同理可知，當模式H的平均適應度小于群體Q的平均適應度時，模式H以指數級減小。

3.如權利要求1所述的基于量子遺傳策略的QG-OLSR路由方法，其特征在于該方法中，步驟第2.1中，初始化節點基因鏈，QGA利用量子比特位保存種群中個體的染色體基因；在第t代時，種群可以表示為其中n是第t代時種群中個體總數，表示第i個個體，每個個體表示該節點的MPR集合，且個體的染色體基因鏈表示如下：

其中i＝1,2,...m，m是量子比特位的個數，為量子染色體基因鏈的長度；α和β表示這兩個相應狀態的概率振幅，利用基因位將單個比特位表示為一組(α,β)集合，表示為

4.如權利要求1所述的基于量子遺傳策略的QG-OLSR路由方法，其特征在于該方法中，步驟第3.2中，初始化群體中，將群體中所有個體的染色體基因位的概率振幅的“0”和“1”狀態位初始化為即對于節點i來說，它的初始化染色體基因鏈表示為：

其中，i＝1,2,…m，m為該網絡拓撲結構中節點總個數；染色體基因鏈的一個量子位代表了對所有可能狀態以相同概率的一個線性疊加，表示公式如下：

其中，S_k是第k個狀態，由二進制串＜x₁,x₂,...x_n＞表示，x_i是0或1，m是染色體基因鏈長度，i＝1,2,…m。