[發(fā)明專利]一種基于人工魚群算法的車聯(lián)網(wǎng)路側(cè)單元優(yōu)化部署方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201510304713.1
• 申請(qǐng)日: 2015-06-05
• 公開(kāi)（公告）號(hào): CN104951832B
• 公開(kāi)（公告）日: 2017-07-11
• 發(fā)明（設(shè)計(jì)）人: 高振國(guó);朱涵;陳丹杰;陳炳才;姚念民;盧志茂;譚國(guó)真
• 申請(qǐng)（專利權(quán)）人: 大連理工大學(xué)
• 主分類號(hào): G06N3/00
• 分類號(hào): G06N3/00
• 代理公司: 大連理工大學(xué)專利中心21200
• 代理人: 梅洪玉

1.一種基于人工魚群算法的車聯(lián)網(wǎng)路側(cè)單元部署方法，其特征在于如下步驟：

步驟1：建立路網(wǎng)模型：將某個(gè)路段e表示為e(v_h,v_t,f_t,f_w)，其中v_h為路段e的起點(diǎn)，v_t為路段e的終點(diǎn)，f_t為路段e的路線函數(shù)，f_w為路段e的權(quán)重函數(shù)，表示路段e的軌跡上各點(diǎn)處的權(quán)重密度，該權(quán)重密度值表征該點(diǎn)若被路側(cè)單元覆蓋所能獲得的收益；

步驟2：建立效益模型：將路網(wǎng)部署總效益B_n表示如下：

$B_n=\underset{e\∈U}{\Σ}\underset{e}{\∫}{f}_w(x,y)ds+\underset{M_e\∈S}{\Σ}\underset{M_e}{\∫}{f}_w(x,y)ds---\left(1\right)$

其中符號(hào)U為n個(gè)路側(cè)單元的全覆蓋路段的集合，符號(hào)S為其部分覆蓋路段的集合，符號(hào)M_e為路段e在路網(wǎng)中所有路側(cè)單元的覆蓋區(qū)域內(nèi)的部分；

步驟3：利用人工魚群算法對(duì)路側(cè)單元部署問(wèn)題進(jìn)行優(yōu)化求解，步驟如下：

步驟3.1：構(gòu)造個(gè)體

每條人工魚可作為一個(gè)可行解組成魚群；可行解F表示如下：

假設(shè)路網(wǎng)中需要部署n個(gè)路側(cè)單元，每個(gè)路側(cè)單元在路網(wǎng)中的位置信息為f(x,y)，則n個(gè)路側(cè)單元構(gòu)成一個(gè)位置序列F(f₁(x,y),f₂(x,y),...,f_n(x,y))；位置序列F(f₁(x,y),f₂(x,y),...,f_n(x,y))和可行解F是一一對(duì)應(yīng)的關(guān)系；每個(gè)可行解由兩部分組成，即魚的位置和適應(yīng)度值；則第i條人工魚個(gè)體結(jié)構(gòu)表示為：

$\begin{array}{c}Fish\left(i\right)=\{\\ Location\[\]\\ fitness\\ \}\end{array}---\left(2\right)$

人工魚的位置編碼結(jié)構(gòu)表示為：

Fish(i).Location[]＝F(f₁(x,y),f₂(x,y),...,f_n(x,y)) (3)

步驟3.2：魚群初始化

隨機(jī)生成m個(gè)位置序列F(f₁(x,y),f₂(x,y),...,f_n(x,y))，并初始化對(duì)應(yīng)的適應(yīng)度值，組成m個(gè)人工魚，分別記為F₁,F₂,...,F_m；每個(gè)F是一個(gè)個(gè)體，m個(gè)個(gè)體組成一個(gè)初始魚群；

步驟3.3：計(jì)算適應(yīng)度值

因?yàn)槁穫?cè)單元的部署效益越大部署效果越好，所以可以用式(1)路網(wǎng)部署總效益B_n作為適應(yīng)度值；因此，人工魚的適應(yīng)度值可以記為：

Fish(i).fitness＝B_n (4)

步驟3.4：位置更改

嘗試聚群算子：在當(dāng)前魚(X_i,Y_i)可見(jiàn)范圍內(nèi)進(jìn)行搜索，得到魚的聚群中心X_center和聚群中心的適應(yīng)度值Y_center；如果滿足Y_center>Y_i且Y_center/n_f<δ*Y_i(δ<1)，其中n_f為感知范圍內(nèi)的人工魚個(gè)數(shù)，表明伙伴中心有很多食物且不擁擠，則按照(5)式向著該中心位置方向前進(jìn)一步；

$X_{next}=X_i+rand\left(\right)*step*\frac{X_{center}-X_i}{\left|\right|X_{center}-X_i\left|\right|}---\left(5\right)$

嘗試追尾算子：在當(dāng)前魚(X_i,Y_i)可見(jiàn)范圍內(nèi)對(duì)每條魚進(jìn)行搜索，并找到適應(yīng)度值最高的魚(X_max,Y_max)；如果Y_max>Y_i，以X_max為中心搜索其感知范圍內(nèi)的人工魚，數(shù)目為n_f，并且滿足Y_max>Y_i且Y_max/n_f<δ*Y_i(δ<1)，則表明該位置較優(yōu)且其周圍不太擁擠，按照(6)式向著適應(yīng)度值最大的伙伴X_max的方向前進(jìn)一步；

$X_{next}=X_i+rand\left(\right)*step*\frac{X_{max}-X_i}{\left|\right|X_{max}-X_i\left|\right|}---\left(6\right)$

比較兩種行為結(jié)果，選擇適應(yīng)度值最高的結(jié)果作為真實(shí)移動(dòng)的結(jié)果；如果聚群算子和追尾算子都未能成功，則執(zhí)行覓食算子：在可見(jiàn)范圍內(nèi)隨意找一個(gè)位置，公式為X_j＝X_i+rand()*visual，并計(jì)算其適應(yīng)度值；如果X_j處適應(yīng)度值大于當(dāng)前魚的適應(yīng)度值，則向X_j處移動(dòng)；如果在達(dá)到最大嘗試次數(shù)前未能成功執(zhí)行覓食算子，則執(zhí)行隨機(jī)算子；

步驟3.5：算法步驟

基于前面提出的構(gòu)造個(gè)體方法及適應(yīng)度值計(jì)算策略，使用人工魚群算法來(lái)求解的步驟如下：

(1)設(shè)置相關(guān)參數(shù)

初始化人工魚個(gè)數(shù)、移動(dòng)步長(zhǎng)、可見(jiàn)范圍、擁擠度因子、覓食算子嘗試次數(shù)及最大迭代次數(shù)；

(2)魚群初始化

隨機(jī)生成包含若干個(gè)體的初始魚群M₁，迭代次數(shù)i＝1；

(3)個(gè)體適應(yīng)度值計(jì)算

按照步驟3.3計(jì)算初始魚群適應(yīng)度值；個(gè)體適應(yīng)度值越大，說(shuō)明該個(gè)體越接近最優(yōu)解；

(4)循環(huán)每條人工魚，進(jìn)行位置更改；

對(duì)當(dāng)前魚分別嘗試執(zhí)行聚群算子和追尾算子，比較兩種行為結(jié)果，選擇適應(yīng)度值最高的結(jié)果作為真實(shí)移動(dòng)的結(jié)果；否則，執(zhí)行覓食算子；

(5)計(jì)算新位置的適應(yīng)度值并更新最優(yōu)解；

對(duì)第i代魚群M_i，按照步驟3.3計(jì)算每個(gè)人工魚的適應(yīng)度值；

(6)更新迭代次數(shù)

(7)判斷是否滿足算法終止條件

算法的終止條件是，魚群進(jìn)化代數(shù)超過(guò)設(shè)定的最大迭代次數(shù)，轉(zhuǎn)步驟(8)；否則，轉(zhuǎn)步驟(4)；

(8)輸出最優(yōu)解。