3.3 遗传算法优化赛车AI参数
在赛车AI开发过程中，会引入参数来控制赛车。但是这些参数较多且耦合，靠人工调参很难达到理想的效果。下面介绍如何利用遗传算法进行程序自动化调参，逐步迭代出较为不错的赛车AI参数。
3.3.1 智能优化算法介绍及应用场景
在赛车游戏中，赛道是形态各异的，因此赛车和赛道的建模需要足够的泛化才能适应不同的赛道。但是，泛化带来的问题是参数多且耦合，靠人工调参很难调出较强的AI，无法满足高水平的玩家。
如图3.2所示，通过调整参数，AI可以通过第一个近道，但过不了第二个近道。如果要让AI上窄桥等复杂近道，则需要多次调整参数。
智能优化算法的作用是在当前模型下，找到AI跑得最好的一套参数。调参的过程是在参数空间中搜索最优解的过程。因为参数空间很大，不适合用遍历的搜索方式，所以可以采用启发式优化算法来解决[2]。表3.1对比了一些常用的优化算法。
图3.2 赛车AI调参问题
表3.1 优化算法对比
3.3.2 遗传算法介绍
遗传算法是启发于生物进化的一种优化学习算法，其基本思想是物竞天择、适者生存。该算法通过种群的迭代更新，把种群中的优秀基因遗传下来。遗传算法流程图如图3.3所示。
图3.3 遗传算法流程图
对于赛车AI参数优化问题，可以根据遗传算法流程设计如图3.4所示的训练流程。
（1）随机初始化n套赛车参数作为初始种群。
（2）每套参数放到同一辆车上在赛道上跑，计算成绩（适应度）。
（3）如果有足够优秀的成绩，则输出对应的参数作为结果。
（4）从n套参数中，按成绩的比例权重随机选择2套参数作为母体。
（5）把选中的2套参数进行交叉和变异得到新的2套参数。
（6）把作为母体的2套参数放回原种群，新的2套参数放入新种群。
（7）重复步骤（4）～步骤（6）共n/2次，共得到新的n套参数。
（8）用新的n套参数重复步骤（2）～步骤（7），直到得到符合条件的参数。
图3.4 用遗传算法训练赛车AI的算法流程
3.3.3 遗传算法关键步骤
遗传算法的训练流程涉及基因编码、基因交叉、基因突变、适应度计算等关键步骤。从生物学角度是比较容易理解上述步骤的含义的，下面从计算机模拟的角度介绍如何实现遗传算法的关键步骤。
3.3.3.1 基因编码
为了能把参数按基因的方式遗传迭代，必须把复杂的赛车参数进行基因编码。常用的基因编码方式有值编码和二进制编码。如图3.5所示，值编码是指把参数按顺序排列，组成一个编码串。如图3.6所示，二进制编码是指把参数转成二进制数形成编码串。二进制编码比较通用，而且方便进行交叉和变异，因此使用较为广泛。
图3.5 值编码
图3.6 二进制编码
3.3.3.2 基因交叉
在生物演化中，子代的基因一部分来自父亲，另一部分来自母亲。基因交叉的过程就是模拟上述基因遗传的过程。常用的交叉方式有单点交叉和双点交叉。图3.7所示为参数双点交叉的示意图。
图3.7 参数双点交叉的示意图
3.3.3.3 基因突变
基因突变是个体进化的灵魂。只有突变才可能突破原来基因范畴，获得进化。图3.8所示为参数突变的示意图，随机选中某个参数进行随机更改。
图3.8 参数突变的示意图
3.3.3.4 适应度计算
适应度表示个体在当前环境下的竞争力，个体的适应度越强，个体拥有越优秀的基因。适应度计算是为了快速、准确、量化地计算出AI的能力。在上述赛车AI参数优化过程中，个体的适应度可以用赛车在固定时间内于赛道中行驶的距离来表示。
3.3.3.5 选择函数
在生物进化过程中，越优秀的个体能获得越多的性资源，其基因就更大概率地能遗传给后代。选择函数过程就是模拟上述自然选择过程。常用的选择函数是适应度比例选择，又称轮盘赌选择。图3.9列举了在有5个个体的情况下，适应度比例选择的计算过程。某个体被选中的概率P（k），等于其适应度F（k）在种群所有个体的适应度总和中的占比。
图3.9 适应度比例选择的计算过程
3.3.4 遗传算法方案的简要分析
图3.10左侧所示为多辆赛车AI在赛道中行驶，并行计算AI参数的适应度示意图。图3.10右侧所示为经过多次迭代，不同AI参数的赛车跑出来的胎痕示意图。
图3.10 遗传算法训练过程
图3.11所示为在地图“11城”中，每次迭代的最优个体行驶轨迹的演化过程。随着迭代演化，每代最优秀的赛车AI，在1分钟内所跑的距离越来越远。一开始，AI不能通过11点钟方向的近道，而经过训练后就可以通过该近道。
图3.11 每次迭代的最优个体行驶轨迹的演化过程
遗传算法的鲁棒性较强，可以处理很多优化问题。刚开始使用遗传算法时，可能面临训练不收敛或收敛速度较慢的问题，需要进行一些优化和调整。对于《QQ飞车手游》的赛车AI参数训练过程，因为进行了赛车之间没有碰撞的并行训练，所以没有考虑动态因子的影响。在实际比赛中，赛车AI较少发生碰撞，且碰撞后可以很快恢复到比较合理的路径上。遗传算法只是优化当前AI模型的参数，高阶技巧需要提前建模，否则不管如何训练，AI也不可能自己学会使用这些技巧。高阶技巧使用策略一般比较复杂，引入一种复杂策略往往会影响原有简单策略的使用，导致AI整体能力下降。开发人员可能需要花大量的时间调试和处理AI表现异常的情况。因此，用遗传算法优化AI参数，AI的能力上限取决于AI模型策略的编写。