[發(fā)明專利]基于黏菌覓食行為的交通網(wǎng)絡(luò)脆弱性問題仿生優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 201910483086.0
• 申請日: 2019-06-04
• 公開（公告）號: CN110288131B
• 公開（公告）日: 2021-10-12
• 發(fā)明（設(shè)計）人: 蔡政英;熊澤平;萬鯤鵬;胥帆;徐雅琦
• 申請（專利權(quán)）人: 三峽大學(xué)
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/26;G06N3/00
• 代理公司: 宜昌市三峽專利事務(wù)所 42103
• 代理人: 王玉芳

1.一種基于黏菌覓食行為的交通網(wǎng)絡(luò)脆弱性問題仿生優(yōu)化方法，其特征在于，所述方法采用黏菌覓食行為對交通網(wǎng)絡(luò)脆弱性問題進行仿生優(yōu)化，使用單只黏菌的多條黏變形體并行求解不同方向上的交通網(wǎng)絡(luò)路線，將交通網(wǎng)絡(luò)節(jié)點模擬成外部食物源，將交通網(wǎng)絡(luò)中兩個節(jié)點之間的線路模仿成黏變形體，將交通網(wǎng)絡(luò)模擬成覆蓋所有外部食物源的黏菌原質(zhì)團，將交通運輸模擬成體內(nèi)營養(yǎng)物質(zhì)的運輸，將交通網(wǎng)絡(luò)脆弱性優(yōu)化問題模擬成黏菌覓食網(wǎng)絡(luò)優(yōu)化問題，具體優(yōu)化方法包括以下步驟：

步驟一為覓食階段，交通網(wǎng)絡(luò)能夠模仿黏菌覓食階段的原質(zhì)團擴張操作，使用單只黏菌的多條黏變形體在不同方向上進行分布式搜索，黏變形體的搜索是概率性的，不同的黏變形體能夠共享找到的外部食物源信息和傳輸線路信息，以多地尋找外部食物源，即交通網(wǎng)絡(luò)覆蓋解空間上所有網(wǎng)絡(luò)節(jié)點，實現(xiàn)網(wǎng)絡(luò)節(jié)點數(shù)量最大化；

具體為，將單只黏菌的細(xì)胞核置于交通網(wǎng)絡(luò)核心節(jié)點上，模仿黏菌的覓食不能脫離細(xì)胞核而存在，交通網(wǎng)絡(luò)的優(yōu)化也不能脫離中心城市而四處擴張；單只黏菌的多條黏變形體隨機向四周擴張進行覓食，在交通網(wǎng)絡(luò)的擴張覓食階段，黏菌原質(zhì)團只能以細(xì)胞核為中心四處活動；黏菌通過多條黏變形體與交通網(wǎng)絡(luò)節(jié)點的接觸來確定外界食物，一條黏變形體能夠連接兩個和兩個以上交通網(wǎng)絡(luò)節(jié)點，通過黏變形體中營養(yǎng)物質(zhì)運輸量來傳遞交通線路的重要性信息；單條黏變形體不需要遍歷所有節(jié)點或邊，只需要遍歷離本黏變形體最近的節(jié)點或邊，不同黏變形體可以共享某一節(jié)點或某條邊；多條黏變形體在交通網(wǎng)絡(luò)的所有外部食物源節(jié)點間不斷移動，以期找到更多交通網(wǎng)絡(luò)節(jié)點；單只黏菌的多條黏變形體共同協(xié)作完成所有交通網(wǎng)絡(luò)節(jié)點的分布式搜索，并增加較脆弱的交通網(wǎng)絡(luò)線路的連接方式；被多條黏變形體共享的某條線路具有較高的脆弱性，多條黏變形體通過不同方式連接某個節(jié)點能夠降低線路的脆弱性，即對該線路的脆弱性評估計算可根據(jù)該線路失效時，受影響的黏變形體長度或網(wǎng)絡(luò)線路長度來衡量；

該長度越大，表明該線路越脆弱，受到影響的黏變形體越長，即該線路的失效容易造成整個交通網(wǎng)絡(luò)的較大延遲；反之，該長度越小，表明該線路的強度和魯棒性越好，受到影響的黏變形體越短，即該線路因脆弱而失效時，對整個交通網(wǎng)絡(luò)的延遲影響較小；

覓食階段包括三個子步驟：

子步驟1-1：初始化，設(shè)置仿生算法的迭代計數(shù)器，初始化待求解交通網(wǎng)絡(luò)優(yōu)化問題的有向圖G＝(N,V)，其中，N表示交通網(wǎng)絡(luò)圖G中節(jié)點座標(biāo)矩陣，包括交通網(wǎng)絡(luò)中心節(jié)點和非中心節(jié)點在內(nèi)共有n個節(jié)點的座標(biāo)矩陣N＝[(x_i,y_i)]_n，n表示交通網(wǎng)絡(luò)圖G中的節(jié)點總數(shù)，(x_i,y_i)表示交通網(wǎng)絡(luò)圖G中的第i個節(jié)點的橫座標(biāo)和縱座標(biāo)；V表示交通網(wǎng)絡(luò)圖G中邊矩陣，所有節(jié)點之間的聯(lián)系構(gòu)成邊矩陣V＝{v_ij|i,j∈N}，v_ij表示交通網(wǎng)絡(luò)圖G中的第i個節(jié)點和第j個節(jié)點之間的邊；節(jié)點之間的距離矩陣表示為d_ij表示交通網(wǎng)絡(luò)圖G中的第i個節(jié)點和第j個節(jié)點之間邊v_ij的長度|v_ij|；

本方法使用概率搜索方法，在步驟一覓食階段將黏菌初始化為以細(xì)胞核為中心，隨機產(chǎn)生多條(m≥n)黏變形體，m表示黏變形體總數(shù)；在覓食階段，黏菌原質(zhì)團擴張和收縮的速度參數(shù)分別表示為e⁺，e^-，且原質(zhì)團擴張時有e⁺≥e^-，原質(zhì)團收縮時有e⁺＜e^-；假設(shè)時間參數(shù)為t，覓食開始的時間t＝0，m條黏變形體走過的節(jié)點集合初始化為空集L＝[L_k]_m＝[{}]_m，L_k表示第k(1≤k≤m)條黏變形體經(jīng)過的節(jié)點序列，D_k表示第k(1≤k≤m)條黏變形體經(jīng)過的邊的總長度，各黏變形體的長度初始化為D_k(0)＝0；設(shè)置體內(nèi)營養(yǎng)物質(zhì)在邊V＝{v_ij|i,j∈N}上運輸?shù)臐舛染仃嚍棣樱絒τ_ij]_n×n，τ_ij表示第i個節(jié)點和第j個節(jié)點之間邊上營養(yǎng)物質(zhì)的濃度；其中，設(shè)置初始值為τ_ij(0)＝0，即所有路線尚未開始運輸營養(yǎng)物質(zhì)；

初始化交通網(wǎng)絡(luò)節(jié)點的親和性矩陣：ξ＝[ξ_i]_n；其中，ξ_i表示與交通網(wǎng)絡(luò)節(jié)點親和性有關(guān)的參數(shù)，ξ_i≥0，即營養(yǎng)越豐富的交通網(wǎng)絡(luò)節(jié)點，ξ_i越大；反之，則ξ_i越小；對于非食物源交通網(wǎng)絡(luò)節(jié)點，ξ_i＝0；

并初始化原質(zhì)團對營養(yǎng)物質(zhì)的消耗速度矩陣：ζ＝[ζ_ij]_n×n；其中，ζ_ij表示與原質(zhì)團消耗能力有關(guān)的參數(shù)，ζ_ij≥0，即原質(zhì)團運動量越大的邊v_ij上消耗營養(yǎng)物質(zhì)越快，ζ_ij越大；反之，則ζ_ij越小；

初始化運輸路線的解表示為w＝(1,2,…,n)，并初始化網(wǎng)絡(luò)脆弱性矩陣表示為

子步驟1-2：原質(zhì)團擴張，設(shè)置原質(zhì)團擴張速度大于收縮速度，即e⁺≥e^-，原質(zhì)團以細(xì)胞核為中心由近及遠(yuǎn)不斷進行擴張操作，多條(m≥n)黏變形體能夠以概率搜索方式進行分布式搜索，由近及遠(yuǎn)遍歷所有交通網(wǎng)絡(luò)節(jié)點或邊，尋找周邊的所有交通網(wǎng)絡(luò)節(jié)點；原質(zhì)團的擴張操作必須在自身的細(xì)胞核周圍進行，并且在自身的體內(nèi)營養(yǎng)物質(zhì)和能量的限制下進行，而不能無限擴張；

假設(shè)i＝1～n-1為交通網(wǎng)絡(luò)節(jié)點，i＝n為細(xì)胞核節(jié)點，第k(1≤k≤m)條黏變形體走過的節(jié)點共有c_k個，c_k表示第k(1≤k≤m)條黏變形體經(jīng)過的節(jié)點總數(shù)，則L_k路線上的邊集合為：表示第k(1≤k≤m)條黏變形體經(jīng)過第l-1個節(jié)點和第l個節(jié)點之間的邊；其中，L_k為邊V＝{v_ij|i,j∈N}的子集的一個排列，最后一個節(jié)點c_k為細(xì)胞核節(jié)點i＝n；可知第k(1≤k≤m)條黏變形體路線總長度為:表示第k(1≤k≤m)條黏變形體經(jīng)過交通網(wǎng)絡(luò)圖G中的第l-1個節(jié)點和第l個節(jié)點之間的邊的長度則黏菌覓食的路線總和，為所有m條黏變形體路線總長度，并減去黏變形體重疊的路線長度：其中，D_Σm表示黏菌覓食的所有路線長度總和，D_k表示第k(1≤k≤m)條黏變形體路線總長度，d_ij|_重疊路線表示重疊的黏變形體長度；

在時間t時，表示時間t時邊v_ij∈V是否被選入排列L_k；當(dāng)選擇一個節(jié)點加入候選路線時，表示時間t時邊v_ij∈V被選入排列L_k；否則，表示時間時邊v_ij∈V未被選入排列L_k；則L_k的邊選擇矩陣為：給候選路線中新加入的一條邊v_ij∈V賦體內(nèi)營養(yǎng)物質(zhì)的值，即開始有營養(yǎng)物質(zhì)在邊v_ij上流動，其中，t表示當(dāng)前時間，τ_ij表示第i個節(jié)點和第j個節(jié)點之間邊上營養(yǎng)物質(zhì)的濃度，d_ij表示交通網(wǎng)絡(luò)圖G中的第i個節(jié)點和第j個節(jié)點之間邊v_ij的長度|v_ij|，表示時間t時邊v_ij∈V是否被選入第k(1≤k≤m)條黏變形體的線路L_k，表示第k(1≤k≤m)條黏變形體上的第i個交通網(wǎng)絡(luò)節(jié)點的親和性參數(shù)，D_k表示k(1≤k≤m)條黏變形體路線總長度，表示第k(1≤k≤m)條黏變形體上第i個節(jié)點和第j個節(jié)點之間的邊的營養(yǎng)物質(zhì)消耗能力參數(shù)；其中，m條黏變形體都將營養(yǎng)物質(zhì)從其所連接的外部食物源節(jié)點運輸往黏菌內(nèi)部細(xì)胞核，被多條黏變形體共享的運輸路線會重復(fù)增強體內(nèi)營養(yǎng)物質(zhì)濃度+τ_ij(t)，從而增強兩個節(jié)點v_ij間的連接概率；營養(yǎng)物質(zhì)值增加的程度取決于食物源節(jié)點的親和性和傳輸距離長度倒數(shù)1/d_ij，即食物源越豐富的路線和距離較短的交通網(wǎng)絡(luò)路線其營養(yǎng)物質(zhì)濃度越大，可能形成更多的連接方式增強網(wǎng)絡(luò)結(jié)構(gòu)；黏變形體在運輸營養(yǎng)物質(zhì)過程中也需要消耗營養(yǎng)物質(zhì)值-τ_ij(t)，從而減少兩個節(jié)點v_ij間的連接概率；營養(yǎng)物質(zhì)值消耗程度取決于黏菌形體的消耗能力和傳輸距離占比d_ij/D_k，消耗能力越大的路線和節(jié)點間距離占比d_ij/D_k較大的路線其營養(yǎng)物質(zhì)消耗越大；

子步驟1-3：食物確認(rèn)，原質(zhì)團在由內(nèi)向外擴張過程中，可能找到了可行的交通網(wǎng)絡(luò)節(jié)點，對其位置做出標(biāo)定，并為下一步的進食階段作好準(zhǔn)備；原質(zhì)團在擴張過程中，也可能沒有找到可行的交通網(wǎng)絡(luò)節(jié)點，或遇到了不可行的交通網(wǎng)絡(luò)節(jié)點，則原質(zhì)團需要離開該節(jié)點所在區(qū)域，并標(biāo)記位置不再進入該區(qū)域；

待求解的目標(biāo)函數(shù)為運輸所有交通網(wǎng)絡(luò)節(jié)點的最短路線集合，即用最短黏變形體找到最多交通網(wǎng)絡(luò)節(jié)點，為：其中，D_Σm表示黏菌覓食的所有路線長度總和，D_k表示第k(1≤k≤m)條黏變形體路線總長度，d_ij|_重疊路線表示重疊的黏變形體長度；黏菌使用多條黏變形體并行搜索能遍歷所有網(wǎng)絡(luò)節(jié)點的最短路線，即為交通網(wǎng)絡(luò)脆弱性優(yōu)化問題的目標(biāo)函數(shù)；由于本算法求解過程與初始條件無關(guān)，覓食階段結(jié)束后，可得到m條黏變形體遍歷所有節(jié)點的一個最短路線排列表示為：

如果在黏菌自身體內(nèi)營養(yǎng)物質(zhì)和能量的限制下，所有外部食物源均已確認(rèn)，表示滿足覓食階段的停止規(guī)則，則停止覓食階段計算并輸出計算得到的全部外部食物源信息；可得到外部食物源及細(xì)胞核的各節(jié)點的度數(shù)r_i，r_i表示與節(jié)點i相連接的鄰居節(jié)點數(shù)量，則所有節(jié)點所連接的邊數(shù)：R＝[r_i]_n；進一步地，該覓食網(wǎng)絡(luò)的平均度數(shù)：通過覓食網(wǎng)絡(luò)的平均度數(shù)，可以直觀地評估整個覓食網(wǎng)絡(luò)的連接強度或脆弱性，即節(jié)點平均通過多少條邊與其他節(jié)點相連，從而為交通網(wǎng)絡(luò)脆弱性優(yōu)化提供候選節(jié)點；平均度數(shù)越高的交通網(wǎng)絡(luò)，其魯棒性越好，抗失效的能力越強，當(dāng)然路線總長度也可能相應(yīng)增加；反之，平均度數(shù)越低的交通網(wǎng)絡(luò)，其拓?fù)浣Y(jié)構(gòu)越脆弱，在某條重要的線路或邊失效時表現(xiàn)出明顯的脆弱性，具有較短的路線總長度；

待求解的目標(biāo)函數(shù)之一為遍歷所有網(wǎng)絡(luò)節(jié)點的交通網(wǎng)絡(luò)線路集合，為：其中，表示第i_l-1個節(jié)點和第i_l個節(jié)點之間的邊長度；待求解的目標(biāo)函數(shù)之二為脆弱性指數(shù)，即某條線路V＝{v_ij|i,j∈N}失效后，遍歷所有網(wǎng)絡(luò)節(jié)點的交通網(wǎng)絡(luò)線路的長度為：其中，v_ij表示交通網(wǎng)絡(luò)圖G中的第i個節(jié)點和第j個節(jié)點之間的邊，表示第i_l-1個節(jié)點和第i_l個節(jié)點之間的邊長度；通常覓食階段所求的交通網(wǎng)絡(luò)為遍歷所有節(jié)點的最短線路，由于本算法求解過程與初始條件無關(guān)，可初始化w＝(i₁,i₂,…,i_n)為節(jié)點{1,2,...,n}的一個最短連接方式排列，其中，i₁,i₂,…,i_n分別表示排列w中的節(jié)點編號，i_n+1＝i₁；

步驟二為進食階段，交通網(wǎng)絡(luò)能夠模仿黏菌進食階段的原質(zhì)團收縮操作，每條黏變形體在交通網(wǎng)絡(luò)上連接了不同的外部食物源節(jié)點，并向交通網(wǎng)絡(luò)中心的細(xì)胞核運輸營養(yǎng)物質(zhì)，黏變形體選擇和搜索運輸路線是概率性的；在交通網(wǎng)絡(luò)運輸過程中，在較短的線路上容易聚集濃度較高的體內(nèi)營養(yǎng)物質(zhì)，在較長的線路上體內(nèi)營養(yǎng)物質(zhì)濃度也較低，從而黏變形體逐漸收縮到體內(nèi)營養(yǎng)物質(zhì)濃度較高的交通網(wǎng)絡(luò)線路上；整只黏菌根據(jù)交通網(wǎng)絡(luò)上營養(yǎng)物質(zhì)運輸?shù)臐舛确植级粩鄡?yōu)化黏變形體連接方式，體內(nèi)營養(yǎng)物質(zhì)在重要的運輸線路上因為正反饋而越聚越多，導(dǎo)致黏變形體不斷加強重要路線的網(wǎng)絡(luò)連接強度，即交通網(wǎng)絡(luò)以最優(yōu)的拓?fù)浣Y(jié)構(gòu)連接交通網(wǎng)絡(luò)節(jié)點，減少線路的脆弱性。