基于博弈的自適應(yīng)高效遺傳改進(jìn)算法研究

李鋮

（河南省機(jī)場集團(tuán)有限公司，河南 鄭州 451161）

基于博弈的自適應(yīng)高效遺傳改進(jìn)算法研究

李鋮

（河南省機(jī)場集團(tuán)有限公司，河南 鄭州 451161）

融合博弈論的信道分配方法中存在納什均衡收斂性問題，針對納什均衡的收斂速度問題引入了遺傳算法，由于傳統(tǒng)遺傳算法存在收斂速率慢和早熟的問題，提出了自適應(yīng)高效遺傳改進(jìn)算法，對傳統(tǒng)遺傳算法的遺傳操作進(jìn)行了改進(jìn)。經(jīng)過仿真實(shí)驗(yàn)，驗(yàn)證了該算法的有效性，加速了納什均衡的收斂速率。

博弈 遺傳算法 收斂性 互聯(lián)變異

1 無線信道分配中的博弈

在實(shí)際的無線通信過程中，由于干擾[1]的存在，導(dǎo)致信道資源具有局限性。多個(gè)節(jié)點(diǎn)同時(shí)與某幾個(gè)節(jié)點(diǎn)通信時(shí)就牽涉到信道分配的問題。如何合理有效地使信道競爭具有公平性，就需要有效的博弈[2]方法。每個(gè)節(jié)點(diǎn)通過各自的博弈策略來進(jìn)行信道的選擇，以達(dá)到各自的收益最大而進(jìn)行博弈。

就無線Mesh網(wǎng)絡(luò)[3]而言，信道分配算法目標(biāo)以實(shí)現(xiàn)最大化吞吐量為目的。信道分配模型大體上可以抽象為一個(gè)動(dòng)態(tài)博弈模型G={N, {Si}, {Ui}, i∈N}，其中N為節(jié)點(diǎn)的集合，Si是相對于博弈者i的策略集，主要是信道選擇策略，S-i是其博弈對手采取的策略，Ui則是收益函數(shù)集，其不僅包含節(jié)點(diǎn)本身的收益還包括對其他節(jié)點(diǎn)的收益影響?；诓┺恼摰男诺婪峙渌惴╗4]追求的目的是實(shí)現(xiàn)網(wǎng)絡(luò)吞吐量的最大化。網(wǎng)絡(luò)吞吐量的大小取決于網(wǎng)絡(luò)中的信道容量C，信道容量越大，節(jié)點(diǎn)進(jìn)行通信時(shí)網(wǎng)絡(luò)的吞吐量也就越大[5]。信道容量可根據(jù)香農(nóng)公式求出，定義收益函數(shù)Ui(si, s-i)為：

博弈收斂性分析是利用博弈論分析無線Mesh網(wǎng)信道分配[6]必不可少的步驟，主要包括分配方法收斂性和收斂結(jié)果達(dá)標(biāo)性的驗(yàn)證。驗(yàn)證算法的收斂性主要是指驗(yàn)證博弈的各個(gè)局中人的策略選擇是否都達(dá)到均衡狀態(tài)[7]。單驗(yàn)證算法的收斂性還是不夠的，因?yàn)榧词顾惴ㄟ_(dá)到了收斂，但得到的收斂結(jié)果不一定就能達(dá)到預(yù)期的目標(biāo)。

2 博弈的收斂性分析

基于博弈論的信道分配算法是一個(gè)重復(fù)博弈的算法，在每次循環(huán)中弈者通過si來選擇自身的策略以達(dá)到改善Ui的目的。如果Ui可被節(jié)點(diǎn)i改變，整個(gè)系統(tǒng)進(jìn)入一個(gè)新的循環(huán)。為了防止網(wǎng)絡(luò)中的震蕩，每個(gè)循環(huán)中只有一個(gè)弈者可以做出改變，每個(gè)節(jié)點(diǎn)包含一個(gè)用于循環(huán)計(jì)數(shù)的標(biāo)志W(wǎng)。W的初始值為網(wǎng)絡(luò)中節(jié)點(diǎn)的總個(gè)數(shù)N，循環(huán)博弈直至W=0時(shí)結(jié)束算法。即使W無法收斂到0，但至少有一個(gè)節(jié)點(diǎn)策略能夠改善收益Ui，由于網(wǎng)絡(luò)中節(jié)點(diǎn)策略是有限的，所以Ui不可能無限改善，W能收斂到0。因此一定存在納什平衡。循環(huán)從W到0的過程就是基于博弈論的信道分配算法的收斂過程，W=0時(shí)也就收斂至博弈中的一個(gè)納什均衡點(diǎn)。

針對少數(shù)參與者的博弈，可以采用依次檢驗(yàn)執(zhí)行對策產(chǎn)生的結(jié)果是否最優(yōu)，找到納什平衡點(diǎn)。但是如果博弈競爭中的參與者很多，顯然逐一檢測每個(gè)博弈者的對策是不合適的，必須選擇一種高效、快捷的方法找到納什均衡點(diǎn)。所以，鑒于遺傳算法能夠通過快速搜索來尋求最優(yōu)解的特性，把遺傳算法運(yùn)用到信道分配問題中[8]，快速尋求最優(yōu)解（即博弈的納什平衡點(diǎn)），加快算法效率。

3 自適應(yīng)高效遺傳改進(jìn)算法

對傳統(tǒng)的遺傳算法[9]收斂速度慢，而且容易發(fā)生早熟的問題進(jìn)行改進(jìn)，提出一種自適應(yīng)高效的遺傳算法（Adaptive Efficient Genetic Algorithm，AEGA）。自適應(yīng)高效的遺傳算法首先對傳統(tǒng)遺傳算法的選擇過程進(jìn)行了改進(jìn)，防止優(yōu)良基因的流失，增強(qiáng)了收斂的效率；其次對交叉操作進(jìn)行了優(yōu)化，克服了以往的單點(diǎn)交叉，使交叉具備自適應(yīng)性；最后改進(jìn)了變異過程，使種群的多樣性得以延續(xù)，防止早熟現(xiàn)象的發(fā)生。自適應(yīng)高效的遺傳算法與傳統(tǒng)的遺傳算法同樣經(jīng)過編碼、種群初始化、對優(yōu)良個(gè)體的選擇、優(yōu)良父代的雜交以及雜交后代的變異等步驟。自適應(yīng)高效的遺傳算法的流程圖如圖1所示：

圖1 AEGA算法的運(yùn)算步驟流程圖

（1）編碼

遺傳算法的編碼方式有很多種，常用的有二進(jìn)制編碼、格雷碼、Delta碼、量子比特編碼等。這些編碼方式相比較，二進(jìn)制編碼只使用了{(lán)0,1}方式進(jìn)行編碼，簡潔，便于操作，容易實(shí)現(xiàn)，幾乎可以適應(yīng)所有問題。本文也使用二進(jìn)制編碼方式對個(gè)體進(jìn)行編碼。

（2）種群初始化

初始化操作一般都是按照規(guī)定的種群規(guī)模來隨機(jī)產(chǎn)生符合要求的種群個(gè)體。本文也同傳統(tǒng)的遺傳算法一樣，隨機(jī)生成若干個(gè)個(gè)體構(gòu)成種群。

（3）適應(yīng)度函數(shù)

定義適應(yīng)度函數(shù)為fitness(i)。適應(yīng)度函數(shù)的設(shè)計(jì)是遺傳算法至關(guān)重要的一部分，是衡量算法效果的直接反映。在遺傳算法中，適應(yīng)度函數(shù)往往與目標(biāo)函數(shù)有著直接或是間接的關(guān)系，適應(yīng)度函數(shù)的好壞可能會(huì)影響個(gè)體的早熟。有的算法中適應(yīng)度函數(shù)與目標(biāo)函數(shù)互為倒數(shù)關(guān)系。在本文的信道分配中，要觀察吞吐量的多少，因此適應(yīng)度函數(shù)定為信干比，目標(biāo)函數(shù)與信道容量即適應(yīng)度函數(shù)的關(guān)系為：f(i)=fitness(i)。

（4）精英選擇

精英，即具備優(yōu)良基因的個(gè)體。選擇過程就是從種群中擇出精英作為父代將優(yōu)良基因傳遞給后代的過程。傳統(tǒng)的遺傳算法采用輪盤法[11]計(jì)算個(gè)體的適應(yīng)度來進(jìn)行選擇，這種隨機(jī)的選擇可能會(huì)遺漏一些優(yōu)良個(gè)體。本文的選擇過程不同于傳統(tǒng)遺傳算法，分別設(shè)定兩個(gè)閾值，即精英閾值f＋(i)和淘汰閾值f ˉ(i)。如果個(gè)體的適應(yīng)度值大于精英閾值，即fitness(i)＞f ˉ(i)，則個(gè)體直接被選中，無需進(jìn)行交叉、變異等遺傳過程。如果個(gè)體的適應(yīng)度值小于淘汰閾值，即fitness(i)＜f ˉ(i)，則表明個(gè)體不適宜環(huán)境而無法存活，直接被淘汰。剩下的個(gè)體就是介于精英與淘汰之間的個(gè)體（f ˉ(i)＜fitness(i)＜f＋(i)），選擇這部分個(gè)體來作為父代，進(jìn)行遺傳過程。這樣的選擇方式剔除了不良基因?qū)?yōu)良基因的干擾，同時(shí)也避免了優(yōu)良基因在種群遺傳過程中的流失，提高了遺傳算法的效率，能夠促進(jìn)收斂速度的提升。保證了每代種群的多樣性，降低了個(gè)體之間的相似度，使高適應(yīng)度的父代個(gè)體能夠直接進(jìn)入子代，進(jìn)化后的較優(yōu)個(gè)體也可以進(jìn)入子代，克服了標(biāo)準(zhǔn)遺傳算法中經(jīng)過若干代后種群內(nèi)個(gè)體高度相似的缺點(diǎn)，使種群可以收斂到全局最優(yōu)解。精英選擇過程可以用圖2來表示：

圖2 AEGA算法的選擇過程

（5）自適應(yīng)交叉

交叉是遺傳算法的關(guān)鍵步驟，與算法收斂速率直接相關(guān)。父代按照交叉概率Pc進(jìn)行雜交產(chǎn)生新的個(gè)體，Pc越大產(chǎn)生新個(gè)體的速度就越快。但是Pc如果過大，就會(huì)影響高適應(yīng)度的個(gè)體遺傳，進(jìn)而對其產(chǎn)生破壞。相反地Pc越小，可能會(huì)阻礙種群的進(jìn)化。傳統(tǒng)的自適應(yīng)遺傳算法[10]對Pc的定義如公式(2)所示：

其中，Pc0為初始設(shè)定的交叉概率，Pc0∈(0.1,0.9)，fmax和fave分別為種群的最大適應(yīng)度和平均適應(yīng)度，f′為兩交叉?zhèn)€體適應(yīng)度較大的個(gè)體適應(yīng)度。種群進(jìn)化過程中遺傳停止時(shí)，Pc會(huì)自適應(yīng)變大，搜索新空間來尋求最優(yōu)，避免早熟現(xiàn)象的發(fā)生。

遺傳算法交叉的方式[12]有很多，比如單點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉以及均勻交叉等，但是這些交叉方式比較固定，在個(gè)體進(jìn)行交叉的時(shí)候可能會(huì)破壞優(yōu)良基因的組織結(jié)構(gòu)，本文提出的自適應(yīng)交叉的交叉方式可以根據(jù)優(yōu)良基因位置，通過計(jì)算權(quán)重來決定交叉點(diǎn)的位置，例如染色體長度為L，交叉點(diǎn)在第i個(gè)基因處，前i個(gè)基因的長度為Li，則權(quán)重ω=Li/L，ω∈(0,1)。子代與父代的交叉方式可以用式(3)表達(dá)：

式中，GA和GB分別表示個(gè)體A和B的父代，GA＇和GB＇代表父代交叉后產(chǎn)生的后代，ω為交叉點(diǎn)在染色體的位置，圖3可以清晰地展示各變量的關(guān)系：

圖3 AEGA算法的自適應(yīng)交叉過程

這種改進(jìn)的自適應(yīng)交叉方式可以隨著種群的進(jìn)化動(dòng)態(tài)地變化交叉點(diǎn)的位置，雜交的兩個(gè)個(gè)體按照自適應(yīng)交叉概率Pc進(jìn)行交叉，對交叉點(diǎn)隨著優(yōu)良基因的變化而動(dòng)態(tài)調(diào)整，使個(gè)體更能適應(yīng)環(huán)境變化，保留優(yōu)良基因，防止遺傳止步于局部最優(yōu)解。

（6）自適應(yīng)變異

本文的變異概率Pm也采取自適應(yīng)遺傳算法的方式。如表達(dá)方式(4)所示：

其中，Pm0為初始設(shè)定的變異概率，Pm0∈(0.01,0.1)，fmax和fave分別為種群的最大適應(yīng)度和平均適應(yīng)度，f為個(gè)體的適應(yīng)度。使用自適應(yīng)變異可以使得f大的個(gè)體Pm小，使f小的個(gè)體Pm變大，這樣可以有效防止優(yōu)良基因因變異遭到破壞而流失，加快收斂效率。

本算法的變異過程是按照Pm概率，遵循以下變異方式進(jìn)行的。本算法的變異需要兩條染色體在滿足彼此相關(guān)聯(lián)的條件下才發(fā)生變異，此算子稱為互聯(lián)變異算子（Interconnected Mutation Operator）。設(shè)定變異前的個(gè)體為GC和GD，彼此通過同或運(yùn)算和異或運(yùn)算變異產(chǎn)生新個(gè)體GC＇和GD＇，如公式(5)所示：

比如說，GC=01110011，GD=11110101，則變異后產(chǎn)生后代GC＇=01111001，GD＇=10000110。隨著進(jìn)化代數(shù)的不斷增加，越來越接近終止代數(shù)，變異概率Pm也會(huì)越來越小。

4 仿真及結(jié)果分析

本文以系統(tǒng)總吞吐量作為博弈的收益函數(shù)，這也是遺傳算法的目標(biāo)函數(shù)，通過AEGA算法的特性，精英選擇，自適應(yīng)交叉和自適應(yīng)變異，不斷進(jìn)化，高效并在全局范圍內(nèi)搜索最優(yōu)解。采用0-1二進(jìn)制編碼方式進(jìn)行編碼，編碼長度為節(jié)點(diǎn)數(shù)n，表示一個(gè)節(jié)點(diǎn)的一個(gè)信道選擇策略，有N條信道就有N×n長度的染色體，表示一個(gè)節(jié)點(diǎn)的信道分配，隨機(jī)選取種群數(shù)。適應(yīng)度選取所有節(jié)點(diǎn)的適應(yīng)度之和，即系統(tǒng)總吞吐量。分別采用兩種遺傳算法進(jìn)行測試，選取種群數(shù)為100，最大進(jìn)化代數(shù)為300，傳統(tǒng)遺傳算法的初始交叉概率Pc0設(shè)置為0.6，初始的變異概率Pm0為0.01。當(dāng)信道數(shù)為K=3，K=6和K=9時(shí)，分別對兩種算法的收斂速度進(jìn)行對比。收斂速度定義為進(jìn)化到最優(yōu)解的進(jìn)化代數(shù)。

圖4 傳統(tǒng)遺傳算法的收斂效果和AEGA算法的收斂效果（K=3）

圖4中（a）圖和（b）圖是在信道數(shù)為3的情況下兩種算法的對比。從圖中可以看出，采用傳統(tǒng)遺傳算法達(dá)到均衡時(shí)的代數(shù)是57，而采用本文的AEGA算法達(dá)到均衡時(shí)的代數(shù)是48，很明顯AEGA算法使收斂的速度加快，從而更加高效。

圖5是在信道數(shù)為6的情況下兩種算法的對比。從圖5可以看出，采用傳統(tǒng)遺傳算法達(dá)到均衡時(shí)的代數(shù)是218，而采用本文的AEGA算法達(dá)到均衡時(shí)的代數(shù)是136。同樣地，AEGA算法加快了收斂的速度，并且隨著可用信道數(shù)的增加，吞吐量也在增大。

圖5 傳統(tǒng)遺傳算法的收斂效果和AEGA算法的收斂效果（K=6）

圖6則是在信道數(shù)為9的情況下兩種算法的對比。從圖6可以看出，采用傳統(tǒng)遺傳算法達(dá)到均衡時(shí)的代數(shù)是247，而采用本文的AEGA算法達(dá)到均衡時(shí)的代數(shù)是232。AEGA算法加快了收斂的速度，并且隨著可用信道數(shù)的增加，吞吐量也在增大。

從以上幾種情況的收斂曲線對比來看，傳統(tǒng)的遺傳算法不能收斂到最優(yōu)，而陷入局部最優(yōu)。AEGA算法由于使用了改進(jìn)的交叉算子和變異算子，在進(jìn)化過程中不斷地進(jìn)行自適應(yīng)變化，根據(jù)取值的不同而動(dòng)態(tài)地進(jìn)行自適應(yīng)調(diào)整，在進(jìn)化前期充分地進(jìn)行分散勘探，以發(fā)現(xiàn)全局最優(yōu)點(diǎn)所在區(qū)域，在進(jìn)化后期群體向全局最優(yōu)點(diǎn)區(qū)域聚集，進(jìn)行集中開采以求收斂到全局最優(yōu)，并且提高了到達(dá)均衡的速度。

圖6 傳統(tǒng)遺傳算法的收斂效果和AEGA算法的收斂效果（K=9）

傳統(tǒng)遺傳算法與AEGA算法在不同可用信道數(shù)條件下達(dá)到均衡狀態(tài)的進(jìn)化代數(shù)對比如表1所示：

表1 兩種算法不同信道下達(dá)到平衡的進(jìn)化代數(shù)對比

5 結(jié)束語

博弈的最終結(jié)果是達(dá)到納什均衡以及如何使信道分配在最短的時(shí)間內(nèi)達(dá)到穩(wěn)定狀態(tài)。針對這個(gè)問題本文采取了遺傳算法來解決納什均衡的收斂問題。由于遺傳算法具有能在廣闊空間中快速搜索并找到最優(yōu)解的特點(diǎn)，可以使信道分配更快地收斂到穩(wěn)定狀態(tài)，也就是納什平衡狀態(tài)。但是傳統(tǒng)的遺傳算法可能會(huì)導(dǎo)致早熟問題，因此本文對傳統(tǒng)遺傳算法的選擇、交叉和變異進(jìn)行了相應(yīng)的改進(jìn)，解決了傳統(tǒng)遺傳算法收斂慢的問題，并且避免了早熟現(xiàn)象。

[1]姬文江,馬建峰,張俊偉,等. 多接口多信道無線mesh網(wǎng)中一種基于信號干擾監(jiān)測的路由度量機(jī)制[J]. 通信學(xué)報(bào),2013(4): 158-164.

[2]羅伯特吉本斯. 博弈論基礎(chǔ)[M]. 北京: 中國社會(huì)科學(xué)出版社, 1999.

[3]Akyildiz I, Wang X. A survey on wireless mesh networks[J]. IEEE Communications Magazine,2005,43(9): 23-30.

[4]Yu Q, Chen J, Fan Y, et a1. Multi-channel assignment in wireless sensor networks: A game theoretic approach[C]//Proc of INFOCOM’10, San Diego, CA: IEEE, 2010: 1-9.

[5]鄭鵬宇,何世彪,戴昊峰,等. 一種基于博弈論的無線mesh網(wǎng)絡(luò)信道分配算法[J]. 電信與科學(xué), 2013(7): 59-65.

[6]馮林涵,錢志鴻,金冬成. 增強(qiáng)型的無線mesh網(wǎng)絡(luò)信道分配方法[J]. 通信學(xué)報(bào), 2012(10): 44-50.

[7]于敏,須文波,孫俊. 納什均衡解及其QPSO算法求解[J].計(jì)算機(jī)工程與應(yīng)用, 2007,43(10): 48-51.

[8]劉耀中,余旭濤. 基于遺傳算法的多信道無線網(wǎng)絡(luò)信道分配方案[J]. 計(jì)算機(jī)工程, 2013(6): 115-123.

[9]李敏強(qiáng). 遺傳算法的基本理論與應(yīng)用[M]. 北京: 科學(xué)出版社, 2002.

[10]Srinivas M, Patamaik L M. Adaptive Probabilities of Crossover and Mutation in Genetic Algorithm[J].IEEE Transactions on System, Man and Cybernetics,1994,24(4): 656-667.

[11]魏全新,劉賢鋒,黃鏘,等. 遺傳算法選擇方法的比較分析[J]. 通訊與計(jì)算機(jī), 2008,5(8): 61-65.

[12]李書全,孫雪,孫德輝,等. 單遺傳算法中的交叉算子的述評[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012,48(1): 36-39.

中國電信推動(dòng)5G試驗(yàn)落地：6城市啟動(dòng)創(chuàng)新示范網(wǎng)

在2017年9月20日舉行的“2017中國無線技術(shù)與應(yīng)用大會(huì)”上，中國電信集團(tuán)公司技術(shù)部副總經(jīng)理沈少艾表示，作為中國IMT-2020（5G）推進(jìn)組創(chuàng)始成員和核心成員，中國電信正在推動(dòng)5G新型網(wǎng)絡(luò)架構(gòu)、研發(fā)關(guān)鍵技術(shù)、驗(yàn)證5G技術(shù)方案。同時(shí)推動(dòng)5G技術(shù)標(biāo)準(zhǔn)化和技術(shù)方案試驗(yàn)落地，制定企業(yè)技術(shù)規(guī)范，為中國引入5G移動(dòng)組網(wǎng)提供技術(shù)指導(dǎo)，全面支撐中國5G發(fā)展。

沈少艾介紹了中國電信5G研發(fā)創(chuàng)新合作示范網(wǎng)試驗(yàn)整體步驟：2016—2018年，原型無線組網(wǎng)能力驗(yàn)證階段；2019年，商用產(chǎn)品、預(yù)商用網(wǎng)絡(luò)階段；2020年，規(guī)模商用階段。目前中國電信5G創(chuàng)新示范網(wǎng)試驗(yàn)啟動(dòng)城市包括蘭州、成都、深圳、雄安、蘇州、上海6個(gè)城市，每個(gè)城市6~8站，目前主要為3.5 GHz頻段的無線組網(wǎng)能力和方案驗(yàn)證。

同時(shí)，中國電信聯(lián)合垂直行業(yè)合作伙伴，合作研發(fā)5G創(chuàng)新示范應(yīng)用，提供面向垂直行業(yè)的5G創(chuàng)新解決方案。中國電信已經(jīng)建立了5G聯(lián)合開放實(shí)驗(yàn)室，通過開放實(shí)驗(yàn)室聯(lián)合合作伙伴，從業(yè)務(wù)、技術(shù)和網(wǎng)絡(luò)部署等多個(gè)層面研究和推進(jìn)，共同打造5G生態(tài)鏈。此外，中國電信已經(jīng)建成了全球最大的NB-IoT網(wǎng)絡(luò)，面向物聯(lián)網(wǎng)應(yīng)用持續(xù)發(fā)展。（C114中國通信網(wǎng)）

Research on Adaptive and Efficient Genetic Improved Algorithm Based on Game

LI Cheng
(Henan Airport Group Co., Ltd., Zhengzhou 451161, China)

There is the convergence problem of Nash equilibrium in the channel allocation method based on the integrated game theory. The genetic algorithm was introduced according to the convergence speed of Nash equilibrium. In view of the slow convergence speed and the precocity in the conventional genetic algorithms, an adaptive and efficient genetic algorithm was proposed, which improves the genetic operation in the conventional genetic algorithms.Simulation results verify the effectiveness of the algorithm that the convergence speed of Nash equilibrium is really accelerated.

game theory genetic algorithm convergence associated mutation

10.3969/j.issn.1006-1010.2017.18.015

TP393

A

1006-1010(2017)18-0085-06

李鋮. 基于博弈的自適應(yīng)高效遺傳改進(jìn)算法研究[J]. 移動(dòng)通信, 2017,41(18): 85-90.

2017-07-23

責(zé)任編輯：劉妙 liumiao@mbcom.cn

李鋮：工程師，碩士畢業(yè)于昆明理工大學(xué)，現(xiàn)任職于河南省機(jī)場集團(tuán)有限公司信息技術(shù)中心，主要從事TETRA集群通信和LTE等無線通信領(lǐng)域的研究工作。