自适应遗传算法求解运动员最佳配对问题*

段明秀，李 钰，赖鹏飞，廖嘉琪

(吉首大学信息科学与工程学院，湖南 吉首 416000)

遗传算法基于“适者生存”的生物进化自然法则，广泛应用于函数优化、组合优化、遗传编程和机器学习等领域，在求解旅行商问题、背包问题和装箱问题等各种非确定性多项式(Non-Deterministic Polynomia,NP)难度的组合优化问题时效果显著.运动员最佳配对问题是一个NP完全问题，在问题规模较大、搜索空间急剧扩张时，用回溯法[1]求解较困难.因此，笔者考虑采用带自适应调节参数的遗传算法来进行求解.

1 基本问题描述

设一个羽毛球队有男女运动员各n人，给定2个n×n矩阵P和Q，其中Pij表示男运动员i和女运动员j配对组成混合双打的男运动员竞赛优势，Qij表示女运动员i和男运动员j配对组成混合双打的女运动员竞赛优势.受技术配合和心理状态等因素的影响，Pij不一定等于Qji.男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为PijQji.问题：设计一个男女运动员的最佳配对方法,使得各组男女双方竞赛优势乘积的总和达到最大.

2 遗传算法解决运动员最佳配对问题原理

运动员最佳配对问题是组合优化问题，即在给定的配对集合中寻找最优配对.对于这类问题，许多学者将主要的精力集中在寻求满意解上.遗传算法是寻找满意解的有力工具.在给定的种群中，遗传算法通过选择、交叉和变异操作进化种群，在一定的进化代数内收敛于一个适应度值较高的个体[2-3].

采用遗传算法求解运动员最佳配对问题，主要需要确定编码和适应度函数.遗传算法不能直接处理问题空间的参数，必须将它们转换成遗传空间的由基因按一定结构组成的染色体或个体(即编码).适应度函数是个体适应度的量化评价方法，是种群进化的依据.

编码：个体的基因为女运动员的编号1～N(所有编号不重复)，相应的位置数为男运动员的编号.例如，值为2,3,1的染色体，表示女运动员2与男运动员1配对、女运动员3与男运动员2配对和女运动员1与男运动员3配对.染色体的特征值与运动员总数是相等的，如值为2,3,1的染色体，运动员总数为3.

适应度函数：问题最终求解的是男女运动员双方竞赛优势的最大总和，因此将一次匹配的竞赛优势总和作为个体的适应度.适应度值越大，表示竞赛优势总和越大，该个体越接近最优解.

3 自适应调整参数

遗传算法在初始化时需要设定种群规模、交叉概率和变异概率等参数.参数对遗传算法的性能的影响较大，关系到精度、可靠性和计算时间等.基于参数应随着遗传进化而适应变化的观点，刘瑞国等[4]提出了自适应算子概率方法，即利用种群的最大适应度与平均适应度的差来自适应调整交叉概率和变异概率.

自适应算子概率方法用fmax表示种群的最大适应度，favg表示种群的平均适应度，fmax-favg表示种群的收敛程度.当fmax-favg减小时，表示favg向fmax靠拢，即向最优解靠拢，说明种群在进化.

种群进化初期，解空间较分散，为了快速搜索解空间，应使交叉概率增大；同时，为了防止有效基因被破坏，应使变异概率减小.进化后期，种群中的个体彼此非常接近，为了避免不必要的近亲繁殖，应使交叉概率减小，变异概率增大.

引入进程因子kshift和收敛因子kc，

其中fmax-avg表示到目前为止fmax-favg的最大值.那么，交叉概率和变异概率分别为

其中：fcurr表示要交叉的2个个体的适应度值中较大的一个；k1，k2，k3，k4是[0，1]之间取值的常数.

4 对比实验

为了验证自适应遗传算法求解运动员最佳配对问题的有效性，在不同规模下对比其与回溯法的最优值求解运行时间.自适应遗传算法中k2,k4取0.5，k1,k3取1.运行时间对比结果见表1.

表1 回溯法和自适应遗传算法的运行时间对比结果Table 1 Comparison of Running Time of Backtracking Method and Genetic Algorithm s

从表1可以看出，由于自适应遗传算法引入了进程因子，使种群在不同进化阶段采取不同的进化方式，引入了收敛因子对种群的整体交叉和变异概率进行自适应调整,因此采用其求解运动员最佳配对问题，在保持群体多样性和全局收敛性的同时,能有效地提高收敛速度，算法效率明显高于回溯法.

5 结语

引入进程因子和收敛因子，对遗传算法进行自适应调节.当运动员最佳配对问题的规模增大时，采用自适应遗传算法仍然能快速地得到一个满意解.但是，种群数目参数的调整依然缺乏自适应性.交叉概率和变异概率决定算法是否会陷入局部最优，而种群数目直接决定算法的效率，因此，下一步笔者将会研究种群数目与种群收敛程度的关联性.