李铖

（河南省机场集团有限公司，河南 郑州 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等无线通信领域的研究工作。