基于博弈的自適應高效遺傳改進算法研究

李鋮

（河南省機場集團有限公司，河南 鄭州 451161）

基于博弈的自適應高效遺傳改進算法研究

李鋮

（河南省機場集團有限公司，河南 鄭州 451161）

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

博弈 遺傳算法 收斂性 互聯變異

1 無線信道分配中的博弈

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

就無線Mesh網絡[3]而言，信道分配算法目標以實現最大化吞吐量為目的。信道分配模型大體上可以抽象為一個動態博弈模型G={N, {Si}, {Ui}, i∈N}，其中N為節點的集合，Si是相對于博弈者i的策略集，主要是信道選擇策略，S-i是其博弈對手采取的策略，Ui則是收益函數集，其不僅包含節點本身的收益還包括對其他節點的收益影響。基于博弈論的信道分配算法[4]追求的目的是實現網絡吞吐量的最大化。網絡吞吐量的大小取決于網絡中的信道容量C，信道容量越大，節點進行通信時網絡的吞吐量也就越大[5]。信道容量可根據香農公式求出，定義收益函數Ui(si, s-i)為：

博弈收斂性分析是利用博弈論分析無線Mesh網信道分配[6]必不可少的步驟，主要包括分配方法收斂性和收斂結果達標性的驗證。驗證算法的收斂性主要是指驗證博弈的各個局中人的策略選擇是否都達到均衡狀態[7]。單驗證算法的收斂性還是不夠的，因為即使算法達到了收斂，但得到的收斂結果不一定就能達到預期的目標。

2 博弈的收斂性分析

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

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

3 自適應高效遺傳改進算法

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

圖1 AEGA算法的運算步驟流程圖

（1）編碼

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

（2）種群初始化

初始化操作一般都是按照規定的種群規模來隨機產生符合要求的種群個體。本文也同傳統的遺傳算法一樣，隨機生成若干個個體構成種群。

（3）適應度函數

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

（4）精英選擇

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

圖2 AEGA算法的選擇過程

（5）自適應交叉

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

其中，Pc0為初始設定的交叉概率，Pc0∈(0.1,0.9)，fmax和fave分別為種群的最大適應度和平均適應度，f′為兩交叉個體適應度較大的個體適應度。種群進化過程中遺傳停止時，Pc會自適應變大，搜索新空間來尋求最優，避免早熟現象的發生。

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

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

圖3 AEGA算法的自適應交叉過程

這種改進的自適應交叉方式可以隨著種群的進化動態地變化交叉點的位置，雜交的兩個個體按照自適應交叉概率Pc進行交叉，對交叉點隨著優良基因的變化而動態調整，使個體更能適應環境變化，保留優良基因，防止遺傳止步于局部最優解。

（6）自適應變異

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

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

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

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

4 仿真及結果分析

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

圖4 傳統遺傳算法的收斂效果和AEGA算法的收斂效果（K=3）

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

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

圖5 傳統遺傳算法的收斂效果和AEGA算法的收斂效果（K=6）

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

從以上幾種情況的收斂曲線對比來看，傳統的遺傳算法不能收斂到最優，而陷入局部最優。AEGA算法由于使用了改進的交叉算子和變異算子，在進化過程中不斷地進行自適應變化，根據取值的不同而動態地進行自適應調整，在進化前期充分地進行分散勘探，以發現全局最優點所在區域，在進化后期群體向全局最優點區域聚集，進行集中開采以求收斂到全局最優，并且提高了到達均衡的速度。

圖6 傳統遺傳算法的收斂效果和AEGA算法的收斂效果（K=9）

傳統遺傳算法與AEGA算法在不同可用信道數條件下達到均衡狀態的進化代數對比如表1所示：

表1 兩種算法不同信道下達到平衡的進化代數對比

5 結束語

博弈的最終結果是達到納什均衡以及如何使信道分配在最短的時間內達到穩定狀態。針對這個問題本文采取了遺傳算法來解決納什均衡的收斂問題。由于遺傳算法具有能在廣闊空間中快速搜索并找到最優解的特點，可以使信道分配更快地收斂到穩定狀態，也就是納什平衡狀態。但是傳統的遺傳算法可能會導致早熟問題，因此本文對傳統遺傳算法的選擇、交叉和變異進行了相應的改進，解決了傳統遺傳算法收斂慢的問題，并且避免了早熟現象。

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

[2]羅伯特吉本斯. 博弈論基礎[M]. 北京: 中國社會科學出版社, 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網絡信道分配算法[J]. 電信與科學, 2013(7): 59-65.

[6]馮林涵,錢志鴻,金冬成. 增強型的無線mesh網絡信道分配方法[J]. 通信學報, 2012(10): 44-50.

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

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

[9]李敏強. 遺傳算法的基本理論與應用[M]. 北京: 科學出版社, 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]. 通訊與計算機, 2008,5(8): 61-65.

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

中國電信推動5G試驗落地：6城市啟動創新示范網

在2017年9月20日舉行的“2017中國無線技術與應用大會”上，中國電信集團公司技術部副總經理沈少艾表示，作為中國IMT-2020（5G）推進組創始成員和核心成員，中國電信正在推動5G新型網絡架構、研發關鍵技術、驗證5G技術方案。同時推動5G技術標準化和技術方案試驗落地，制定企業技術規范，為中國引入5G移動組網提供技術指導，全面支撐中國5G發展。

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

同時，中國電信聯合垂直行業合作伙伴，合作研發5G創新示范應用，提供面向垂直行業的5G創新解決方案。中國電信已經建立了5G聯合開放實驗室，通過開放實驗室聯合合作伙伴，從業務、技術和網絡部署等多個層面研究和推進，共同打造5G生態鏈。此外，中國電信已經建成了全球最大的NB-IoT網絡，面向物聯網應用持續發展。（C114中國通信網）

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

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

2017-07-23

責任編輯：劉妙 liumiao@mbcom.cn

李鋮：工程師，碩士畢業于昆明理工大學，現任職于河南省機場集團有限公司信息技術中心，主要從事TETRA集群通信和LTE等無線通信領域的研究工作。