[發明專利]一種城市突發事件緊急救援方法

有效

• 申請號: 202110790568.8
• 申請日: 2021-07-13
• 公開（公告）號: CN113408823B
• 公開（公告）日: 2022-12-13
• 發明（設計）人: 石美鳳;肖詩川;楊海;廖鑫;馮欣;陳媛
• 申請（專利權）人: 重慶理工大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/00;G06N3/12
• 代理公司: 重慶晟軒知識產權代理事務所(普通合伙) 50238
• 代理人: 王海鳳

1.一種城市突發事件緊急救援方法，其特征在于，構建一種基于蟻群遺傳的分布式約束優化問題求解方法，該方法包括如下步驟:

S100:用一個四元組＜A,X,D,F＞來表示分布式約束優化問題，其中：

A＝{a₁,...,a_n}是agent的集合；

X＝{x₁,...,x_m}是變量的集合，m≤n；

D＝{D₁,...,D_m}是值域的集合，每個x_i的值域為D_i，每個Agent從值域D_i中取值為變量x_i賦值，表示x_i的第t個值；

F＝{f₁,...,f_p}是約束代價函數的集合，約束是從任意β個變量的賦值組合到一個非負代價的映射；

設一個agent只控制一個變量且所有的約束關系都是二元關系，則DCOP的解表示為：

將DCOP表示為約束圖，在約束圖中，每個節點都代表一個agent，每兩個節點之間的連線代表這兩個節點之間存在約束關系；

S200：對蟻群算法和遺傳算法的參數初始化，將約束圖轉化為廣度優先生成的偽樹，一個節點對應一個agent，節點與節點之間的連線代表約束，偽樹的值消息傳遞方向為上層節點傳給下層節點，同層節點根據優先級或節點命名字母順序來傳遞，消息傳遞方向即agent的優先級和螞蟻的前進方向；

初始化路徑上的信息素濃度；

S300：采用蟻群算法對n個agent進行一次遍歷：如果當前a_i已經從其所有較高優先級的鄰居處接收到值消息，則a_i為每只螞蟻在x_i對應的值域中根據選擇概率選擇一個值，根據當前取值，計算a_i與其所有高優先級鄰居取值之間的代價和，與之前算的代價和進行累加，得到當前螞蟻的代價；

S400：生成隨機概率q，若q小于擴展概率p，則轉至S500，否則轉至S900；

所述擴展概率p采用公式(12)計算：

式中maxCycle為最大迭代輪次，curCycle為當前所在輪次；

S500：設蟻群算法中共有K只螞蟻，每只螞蟻根據S300對n個agent進行一次遍歷得到一個集合，該集合認為是一條染色體，通過S300針對K只螞蟻則得到K條染色體，將該K條染色體作為遺傳算法的父代染色體；

S600：計算前一步驟中獲得的每條父代染色體的適應值，計算每條染色體的適應值在所有染色體適應值之和中的占比，將K條染色體中適應值最大的染色體直接復制保存到第一代子代染色體集合中，然后計算每條染色體的選擇概率，每條染色體的選擇概率等于該條染色體的適應值與所有染色體適應值之和之比，根據所述染色體的選擇概率采用輪盤賭選擇第一代子染色體集合K-1條染色體；

輪盤賭選擇：計算出每條染色體的累計選擇概率，p[k]稱為染色體k的累計選擇概率，即前k-1條染色體的選擇概率之和；令η＝1，生成K-1個隨機數在新的父代染色體集合中，按照染色體的排序，當一條染色體的累計選擇概率大于等于則將該染色體復制保存到第一代子代染色體集合中，并令η＝η+1，繼續在新的父代染色體集合中，按照染色體的排序選擇，依次重復直至η＝K-1時停止，此時選擇了K-1條第一代子代染色體；

S700：染色體交叉、變異：

染色體交叉：

設置交叉概率，對第x條第一代子代染色體生成一個交叉隨機概率，q_x表示第x條第一代子代染色體的交叉隨機概率，x＝1,2，...K-1，當q_x小于交叉概率時，則將第x條第一代子代染色體和第x-1條第一代子代染色體對應的交叉位置進行交叉，所述交叉位置隨機生成；

需要進行染色體交叉的第一代子代染色體完成染色體交叉后復制保存到新的第一代子代染色體集合中，不需要染色體交叉的第一代子代染色體復制保存到新的第一代子代染色體集合中，第一代子代染色體集合中的染色體稱為新的第一代子代染色體；

染色體變異：

設置變異概率，對于新的第一代子代染色體上的n個位置分別生成一個變異隨機概率，表示第γ條新的第一代子代染色體第ε個位置的變異隨機概率，當小于變異概率時，則將第γ條新的第一代子代染色體第ε個位置上的取值進行變異，變異方法為從值域中隨機選擇一個值對該位置重新賦值；

需要進行染色體變異的新的第一代子代染色體完成染色體變異后復制保存到第二代子代染色體集合中，不需要進行染色體變異的新的第一代子代染色體復制保存到第二代子代染色體集合中，第二代子代染色體集合中的染色體稱為第二代子代染色體；

S800：判斷遺傳算法是否迭代結束，若達到遺傳算法運行的最大迭代次數表示滿足終止條件，則輸出當前第二代子代染色體集合中的第二代子代染色體并轉至S900，否則采用第二代子代染色體更新父代染色體并轉至S600；

S900：更新路徑上的信息素濃度和局部信息下文預估值；

局部信息下文預估值即對a_i與其低優先級鄰居之間的最小代價和的估計，符號表示為est_i(d_i)；生成隨機概率q，當q小于擴展概率p時，使用第二代子代染色體集合中的每條染色體的代價更新信息素濃度，否則使用S500中K條染色體的代價更新信息素濃度，并使用所述K條染色體對每個agent和其鄰居間約束的信息素濃度進行更新；

對每個agent更新局部信息下文預估值，對于取值d_i∈D_i，當變量x_i＝d_i時，計算當前agent與其低優先級鄰居節點之間產生的約束代價的平均值，再將上一輪agent得到的局部信息下文預估值和所求平均值再次求平均得到更新的預估值；

所述S900中計算每條第二代子代染色體的代價的方法如下：

對于第k條二代子代染色體，將每個agent和其鄰居之間約束對應的代價相加即得第k條二代子代染色體的代價cos t_k；

所述S900中對每個agent更新est_i(d_i)的過程如下：首先當x_i＝d_i時，計算a_i與其低優先級鄰居之間產生的約束代價之和的平均值，然后將上次迭代求得的est_i(d_i)值與當前求得的均值求平均值，用該平均值更新est_i(d_i)的值；

S1000：判斷蟻群算法是否迭代結束，若達到蟻群算法運行的最大迭代次數表示滿足終止條件，輸出當前代價最小的染色體對應的代價和n個變量的取值，否則返回步驟S300；

將所述基于蟻群遺傳的分布式約束優化問題求解方法應用于城市突發事件緊急救援問題：

給定問題交通路網G(C,E)，C表示路網中的節點，E表示兩節點間的連線，即路段，同時將城市突發事件可通行路徑規劃構建為DCOP模型，記為城市突發事件的DCOP模型，模型具體描述如下：

A＝{car₁,...,car_n}為agent的集合，一輛車表示一個agent；

X＝{x₁,...,x_m}為變量的集合，一個agent控制一個變量x_i；

D＝{S₁,...,S_m}為值域的集合，每個變量x_i的值域為S_i，S_i中為可行路徑的集合，一條可行路徑是變量x_i的一個取值；

F＝{f₁,...,f_p}是約束代價函數的集合，f_ij為兩輛車行駛路徑之間的約束，即兩條可行路徑之間的路徑重合度小于30％，由于每兩輛車之間的行駛路徑要滿足約束，則抽象出的城市突發事件的DCOP模型的約束圖為全連接約束圖。