[發明專利]基于差分進化和捕食搜索策略的胖樹型片上網絡映射方法

有效

• 申請號: 201110276587.5
• 申請日: 2011-09-19
• 公開（公告）號: CN102325089A
• 公開（公告）日: 2012-01-18
• 發明（設計）人: 顧華璽;張碧霞;楊銀堂;王琨;鄧植
• 申請（專利權）人: 西安電子科技大學
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L29/06
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 王品華;朱紅星

1.一種基于差分進化和捕食搜索策略的胖樹型片上網絡映射方法，包括如下步驟：

(1)初始化操作

對映射結果進行初始化：隨機選擇一個映射排序作為映射結果s的初始解，令當前最優映射結果b＝s；

對限制數組進行初始化：定義解空間內以任意一個解作為中心的周圍的多個解組成限制數組，該數組中每個元素對應于該中心的一個鄰域的限制范圍，然后，在當前最優映射結果b的周圍設置限制總數為T的限制數組：R[0]，R[1]，...，R[T-1]，其中T取自然數，給定一個解b和一個限制R[i]，將圍繞b的一個受限鄰域表示為A(b，R[i])；

對中間變量進行初始化：令當前局部搜索所在的限制級數i₁＝0，當前限制級數內的搜索次數i₂＝0；

(2)將當前局部搜索所在的限制級數與設定的限制總數進行比較，如果當前局部搜索所在的限制級數i₁＜設定的限制總數T，則進行局部搜索，并初始化M個種群個體，利用差分進化方法對該初始種群迭代N次，其中N為所設定的差分進化的總迭代次數，將迭代得到的最優映射結果記為p，并轉步驟(3)；否則，將當前最優映射結果b作為最佳映射結果，并輸出；

(3)判斷迭代得到的最優映射結果是否在當前最優映射結果的受限鄰域內，如果迭代得到的最優映射結果p在當前最優映射結果b的受限鄰域A(b，R[i₁])內，則令映射結果s＝迭代得到的最優映射結果p，并轉步驟(4)；否則轉步驟(5)；

(4)將迭代得到的最優映射結果對應的能耗與當前最優映射結果對應的能耗進行比較，如果迭代得到的最優映射結果p對應的能耗優于當前最優映射結果b對應的能耗，則進行更新，重新開始計算，即令當前最優映射結果b＝s，當前局部搜索所在的限制級數i₁＝0，當前限制級數內的搜索次數i₂＝0，然后在當前最優映射結果b的周圍重新計算限制數組，轉步驟(2)；否則轉步驟(5)；

(5)將當前限制級數內的搜索次數與每一限制等級內的最大搜索次數進行比較，令當前限制級數內的搜索次數i₂＝i₂+1，如果i₂＞每一限制等級內的最大搜索次數C，令當前局部搜索所在的限制級數i₁＝i₁+1，當前限制級數內的搜索次數i₂＝0，并轉步驟(6)；否則轉步驟(2)；

(6)將當前局部搜索所在的限制級數與終止局部搜索的限制級數進行比較，如果當前局部搜索所在的限制級數i₁＝終止局部搜索的限制級數L，則將當前局部搜索所在的限制級數i₁設置為終止局部搜索的限制級數L與設定的限制總數T之間的一個限制級數值L_high，即令i₁＝L_high，轉步驟(2)；否則直接轉步驟(2)。

2.根據權利要求1所述的基于差分進化和捕食搜索策略的胖樹型片上網絡映射方法，其中步驟(1)所述的在當前最優映射結果b的周圍設置限制總數為T的限制數組，按如下步驟進行：

1a)在當前最優映射結果b的周圍利用2-opt算法搜索T-1次，其中T表示設定的限制總數，得到T-1個映射結果及其對應的能耗值，并將該T-1個映射結果所對應的能耗值按照升序排列；

1b)把排序后的這T-1個能耗值依次賦給限制數組R[1]，R[2]，...，R[T-1]，而R[0]取為當前最優映射結果b所對應的能耗值。

3.根據權利要求1所述的基于差分進化和捕食搜索策略的胖樹型片上網絡映射方法，其中步驟(2)所述的利用差分進化方法，包括變異操作、交叉操作和選擇操作：

所述的變異操作，是采取兩種變異操作模式進行的，即DE/best/1和DE/rand/1模式，通過下面公式進行變異得到新個體：

DE/best/1模式：vik+1=xik+F×(xr1k-xr2k)if rand(0,1)<γxik+F×(xgk-xr2k)otherwise]]>

DE/rand/1模式：vik+1=xr1k+F×(xr2k-xr3k)]]>

其中r₁，r₂，r₃∈{1，2，L，M}，表示任意選取的三個種群個體，r₁≠r₂≠r₃，M為種群個數，為第k代種群中第i個個體，為第k代種群中的最優個體，g標示種群中的最優個體，rand(0，1)為0-1之間的隨機數，決策概率γ＝(1-k/N)²，此處N為差分進化方法設定的總迭代次數，變異因子F采用自適應變異算子：

F＝F_min+rand(0，1)×(F_max-F_min)

其中F_max和F_min分別表示所設定的變異因子的上下限，取值范圍為0-2，rand(0，1)為0-1之間的隨機數；

所述的交叉操作，是在變異產生的第i個新個體和種群中的第i個個體之間進行交叉，得到交叉個體：

uik+1=vik+1if(rand(0,1)≤CR)xikif(rand(0,1)>CR)]]>

其中rand(0，1)為0-1之間的隨機數，交叉因子CR采用自適應交叉算子：

CR＝CR_min+i×(CR_max-CR_min)/N

其中CR_max和CR_min分別表示所設定的交叉因子的上下限，取值范圍為0-1，N為差分進化方法設定的總迭代次數；

所述的選擇操作，是將交叉操作后得到的新個體對應的能耗值與原個體對應的能耗值進行比較，把能耗值較低的作為下一代個體。