[發(fā)明專利]基于多智能體遺傳算法的電力運(yùn)輸網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710195081.9
• 申請(qǐng)日: 2017-03-29
• 公開(kāi)（公告）號(hào): CN107066709B
• 公開(kāi)（公告）日: 2019-05-21
• 發(fā)明（設(shè)計(jì)）人: 劉靜;焦李成;安柏慧
• 申請(qǐng)（專利權(quán)）人: 西安電子科技大學(xué)
• 主分類號(hào): G06F17/50
• 分類號(hào): G06F17/50;G06N3/12
• 代理公司: 陜西電子工業(yè)專利中心 61205
• 代理人: 韋全生;王品華

1.一種基于多智能體遺傳算法的電力運(yùn)輸網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)方法，其特征在于包括如下步驟：

(1)設(shè)定多智能體遺傳算法參數(shù)，并將多智能體遺傳算法獲取的種群作為待設(shè)計(jì)電力運(yùn)輸網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，其中設(shè)定的參數(shù)包括多智能體遺傳算法的種群大小Ω、鄰域競(jìng)爭(zhēng)概率P₀、鄰域交叉概率P_c、變異概率P_m、局部搜索概率P_l和最大迭代次數(shù)N；

(2)對(duì)多智能體遺傳算法的種群進(jìn)行初始化，得到初始化種群，并計(jì)算該初始化種群中每個(gè)個(gè)體的魯棒值，實(shí)現(xiàn)步驟為：

(2a)設(shè)定多智能體遺傳算法種群的初始大小為1，從該種群個(gè)體中隨機(jī)選擇節(jié)點(diǎn)l,k之間的連接邊e_lk和節(jié)點(diǎn)m,n之間的連接邊e_mn，并刪除所選的這兩條邊，在節(jié)點(diǎn)k,m之間重新建立連接邊e_km，在節(jié)點(diǎn)l,n之間重新建立連接邊e_ln，得到多智能體遺傳算法中間種群，將該中間種群記為臨時(shí)電力運(yùn)輸網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；

(2b)判斷臨時(shí)電力運(yùn)輸網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是否連通，若是，將該臨時(shí)電力運(yùn)輸網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)作為新種群，并給新種群的大小加1，執(zhí)行步驟(2c)；否則，刪除節(jié)點(diǎn)k，m之間新建立的連接邊e_km和節(jié)點(diǎn)l,n之間新建立的連接邊e_ln，并還原步驟(2a)隨機(jī)選擇的節(jié)點(diǎn)l,k之間的連接邊e_lk和節(jié)點(diǎn)m,n之間的連接邊e_mn，執(zhí)行步驟(2a)；

(2c)判斷新種群大小是否等于多智能體遺傳算法的種群大小Ω，若是，將新種群作為多智能體遺傳算法的初始化種群，并采用適應(yīng)度函數(shù)公式，計(jì)算初始化種群中每個(gè)個(gè)體的魯棒值，執(zhí)行步驟(3)；否則，執(zhí)行步驟(2a)；

(3)對(duì)多智能體遺傳算法的初始化種群進(jìn)行鄰域競(jìng)爭(zhēng)，并計(jì)算鄰域競(jìng)爭(zhēng)種群中每個(gè)個(gè)體的魯棒值，實(shí)現(xiàn)步驟為：

(3a)按照均勻分布概率在0-1之間產(chǎn)生一個(gè)隨機(jī)數(shù)u；

(3b)判斷隨機(jī)數(shù)u是否小于鄰域競(jìng)爭(zhēng)概率P₀，若是，執(zhí)行步驟(3c)，否則執(zhí)行步驟(3a)；

(3c)遍歷多智能體遺傳算法的初始化種群，從多智能體遺傳算法初始化種群中每次選擇一個(gè)個(gè)體，并判斷所選擇個(gè)體的魯棒值是否優(yōu)于該個(gè)體鄰域內(nèi)魯棒值最好個(gè)體的魯棒值，若是，則所選擇個(gè)體可以繼續(xù)存活，用存活下來(lái)的個(gè)體替換多智能體遺傳算法初始化種群中的對(duì)應(yīng)個(gè)體，得到鄰域競(jìng)爭(zhēng)種群，并執(zhí)行步驟(3d)，否則，用鄰域內(nèi)魯棒值最好的個(gè)體替換多智能體遺傳算法初始化種群中選擇的個(gè)體，得到鄰域競(jìng)爭(zhēng)種群，并執(zhí)行步驟(3d)；

(3d)采用適應(yīng)度函數(shù)公式，計(jì)算鄰域競(jìng)爭(zhēng)種群中每個(gè)個(gè)體的魯棒值；

(4)對(duì)鄰域競(jìng)爭(zhēng)種群進(jìn)行鄰域交叉，得到鄰域交叉種群，實(shí)現(xiàn)步驟為：

(4a)按照均勻分布概率在0-1之間產(chǎn)生一個(gè)隨機(jī)數(shù)v；

(4b)判斷隨機(jī)數(shù)v是否小于鄰域交叉概率P_c；若是，執(zhí)行步驟(4c)；否則，執(zhí)行步驟(4a)；

(4c)遍歷鄰域競(jìng)爭(zhēng)種群，從鄰域競(jìng)爭(zhēng)種群中每次選擇一個(gè)個(gè)體，將所選擇個(gè)體與其鄰域內(nèi)魯棒值最好的個(gè)體進(jìn)行鄰域交叉，得到多個(gè)鄰域交叉?zhèn)€體，并用鄰域交叉?zhèn)€體替換從鄰域競(jìng)爭(zhēng)種群中選擇的對(duì)應(yīng)個(gè)體，得到鄰域交叉種群；

(5)對(duì)鄰域交叉種群進(jìn)行變異，得到變異種群，實(shí)現(xiàn)步驟為：

(5a)按照均勻分布概率在0-1之間產(chǎn)生一個(gè)隨機(jī)數(shù)i；

(5b)判斷隨機(jī)數(shù)i是否小于變異概率P_m；若是，執(zhí)行步驟(5c)，否則，執(zhí)行步驟(5a)；

(5c)遍歷鄰域交叉種群，從鄰域交叉種群中每次選擇一個(gè)個(gè)體，計(jì)算所選擇個(gè)體中的總邊數(shù)；

(5d)判斷所選擇個(gè)體中總邊數(shù)是否為偶數(shù)，若是，選出總邊數(shù)中一定數(shù)量的邊，選擇總邊數(shù)中一定數(shù)量邊的1/2對(duì)邊進(jìn)行交換，得到多個(gè)變異個(gè)體，并執(zhí)行步驟(5e)；否則，選出總邊數(shù)中一定數(shù)量的邊，取接近總邊數(shù)中一定數(shù)量邊的最大偶數(shù)，選取總邊數(shù)中一定數(shù)量邊的1/2對(duì)邊進(jìn)行交換，得到多個(gè)變異個(gè)體，并執(zhí)行步驟(5e)；

(5e)用多個(gè)變異個(gè)體替換鄰域交叉種群中的對(duì)應(yīng)個(gè)體，得到變異種群；

(6)對(duì)變異種群進(jìn)行局部搜索，得到局部搜索種群，實(shí)現(xiàn)步驟為：

(6a)遍歷變異種群，從變異種群中每次選取一個(gè)個(gè)體，計(jì)算所選個(gè)體中節(jié)點(diǎn)個(gè)數(shù),并設(shè)置初始局部搜索迭代數(shù)為1；

(6b)按照均勻分布概率在0-1之間產(chǎn)生一個(gè)隨機(jī)數(shù)j；

(6c)判斷隨機(jī)數(shù)j是否比種群局部搜索概率P_l小，若是，執(zhí)行步驟(6d)，否則，執(zhí)行步驟(6b)；

(6d)采用適應(yīng)度函數(shù)公式，計(jì)算所選變異種群中每個(gè)個(gè)體的魯棒值R^initial；

(6e)判斷表達(dá)式|d_a-d_c|+|d_b-d_d|＜α×(|d_a-d_b|+|d_c-d_d|)是否成立，若是，從變異種群中選擇的個(gè)體中隨機(jī)選擇節(jié)點(diǎn)a,b之間的連接邊e_ab和節(jié)點(diǎn)c,d之間的連接邊e_cd，刪除所選的兩條邊e_ab和e_cd，在節(jié)點(diǎn)a,c之間建立新的連接邊e_ac，在節(jié)點(diǎn)b,d之間建立新的連接邊e_bd，得到多個(gè)局部搜索個(gè)體,執(zhí)行步驟(6f)，否則，執(zhí)行步驟(6a)，其中，d_a是節(jié)點(diǎn)a的度，d_b是節(jié)點(diǎn)b的度，d_c是節(jié)點(diǎn)c的度，d_d是節(jié)點(diǎn)d的度，α是調(diào)節(jié)因子，其取值范圍為[0,1]；

(6f)采用適應(yīng)度函數(shù)公式，計(jì)算局部搜索后每個(gè)個(gè)體的魯棒值R^new，判斷魯棒值R^new是否大于魯棒值R^initial，若是，用局部搜索個(gè)體替換從變異后種群中選擇的對(duì)應(yīng)個(gè)體，得到局部搜索種群，并執(zhí)行步驟(6g)，否則，執(zhí)行步驟(6d)；

(6g)局部搜索迭代數(shù)加1，判斷局部搜索迭代數(shù)是否累計(jì)達(dá)到所選擇的變異種群中個(gè)體的節(jié)點(diǎn)數(shù)，若是，執(zhí)行步驟(6h)，否則，執(zhí)行步驟(6d)；

(6h)判斷當(dāng)前迭代次數(shù)是否等于設(shè)定的最大迭代次數(shù)N，若是，將局部搜索種群作為所要設(shè)計(jì)的電力網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，并輸出，否則，執(zhí)行步驟(3)。

2.根據(jù)權(quán)利要求1所述的基于多智能體遺傳算法的電力運(yùn)輸網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)方法，其特征在于，步驟(2c)、步驟(3d)、步驟(6d)和步驟(6f)中所述的適應(yīng)度函數(shù)公式，其表達(dá)式為：

其中，R表示網(wǎng)絡(luò)魯棒值，N表示網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)，s(q)表示在刪除q個(gè)節(jié)點(diǎn)時(shí)，剩余網(wǎng)絡(luò)的最大連通子分量與網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N的比值，q表示刪除節(jié)點(diǎn)的個(gè)數(shù)，∑表示求和操作。