遗传算法（Genetic Algorithm, GA）是近几年发展起来的一种崭新的全局优化算法。本文将讲解这种算法，并介绍如何 Robocode Java 坦克机器人中采用此算法以实现机器人进化。

_遗传算法

遗传算法（Genetic Algorithm, GA）是近几年发展起来的一种崭新的全局优化算法。1962年霍兰德(Holland)教授首次提出了GA算法的思想，它借用了仿真生物遗传学和自然选择 机理，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。

这一点体现了自然界中"物竞天择、适者生存"进化过程。与自然界相似，遗传算法对求解问题的本身一无 所知，它所需要的仅是对算法所产生的每个染色体进行评价,把问题的解表示成染色体，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在算 法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群染色体，也即是假设解。然后，把这些假设解置于问题的“环境”中，也即一个适应度函数中 来评价。并按适者生存的原则，从中选择出较适应环境的染色体进行复制, 淘汰低适应度的个体，再通过交叉，变异过程产生更适应环境的新一代染色体群。对这个新种群进行下一轮进化，至到最适合环境的值。

遗传算法已用于求解带有应用前景的一些问题，例如遗传程序设计、函数优化、排序问题、人工神经网络、分类系统、计算机图像处理和机器人运动规划等。

_术语说明

由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中会用到很多生物遗传学知识，下面是我们将会用来的一些术语说明：

一、染色体(Chronmosome)

染色体又可以叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。

二、基因(Gene)

基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。

三、基因地点(Locus)

基因地点在算法中表示一个基因在串中的位置称为基因位置(Gene Position)，有时也简称基因位。基因位置由串的左向右计算，例如在串 S＝1101 中，0的基因位置是3。

四、基因特征值(Gene Feature)

在用串表示整数时，基因的特征值与二进制数的权一致；例如在串 S=1011 中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。

五、适应度(Fitness)

各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数. 这个函数是计算个体在群体中被使用的概率。

_操作算法

霍兰德(Holland)教授最初提出的算法也叫简单遗传算法，简单遗传算法的遗传操作主要有三种：选择(selection)、交叉(crossover)、变异(mutation)这也是遗传算法中最常用的三种算法：

1．选择(selection)

选择操作也叫复制操作，从群体中按个体的适应度函数值选择出较适应环境的个体。一般地说，选择将使适 应度高的个体繁殖下一代的数目较多，而适应度较小的个体，繁殖下一代的数目较少,甚至被淘汰。最通常的实现方法是轮盘赌(roulette wheel)模型。令Σfi表示群体的适应度值之总和，fi表示种群中第i个染色体的适应度值，它被选择的概率正好为其适应度值所占份额fi／Σfi。如 下图表中的数据适应值总和Σfi=6650,适应度为2200变选择的可能为fi／Σfi=2200/6650=0.394.

 

S1	1000  1111	S2	1110  1100

1	1	1	0	1	1	0	0

1	1	0	0	1	1	0	0

4．精英主义 （Elitism）

仅仅从产生的子代中选择基因去构造新的种群可能会丢失掉上一代种群中的很多信息。也就是说当利用交叉 和变异产生新的一代时，我们有很大的可能把在某个中间步骤中得到的最优解丢失。在此我们使用精英主义（Elitism）方法，在每一次产生新的一代时，我 们首先把当前最优解原封不动的复制到新的一代中，其他步骤不变。这样任何时刻产生的一个最优解都可以存活到遗传算法结束。

上述各种算子的实现是多种多样的，而且许多新的算子正在不断地提出，以改进GA某些性能。比如选择算法还有分级均衡选择等等。

_{遗传算法的所需参数}

说简单点遗传算法就是遍历搜索空间或连接池，从中找出最优的解。搜索空间中全部都是个体，而群体为搜 索空间的一个子集。并不是所有被选择了的染色体都要进行交叉操作和变异操作，而是以一定的概率进行，一般在程序设计中交叉发生的概率要比变异发生的概率选 取得大若干个数量级。大部分遗传算法的步骤都很类似，常使用如下参数：

Fitness函数：见上文介绍。

Fitnessthreshold（适应度阀值）：适合度中的设定的阀值，当最优个体的适应度达到给 定的阀值，或者最优个体的适应度和群体适应度不再上升时(变化率为零)，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群 体取代上一代群体，并返回到选择操作处继续循环执行。

P：种群的染色体总数叫种群规模，它对算法的效率有明显的影响，其长度等于它包含的个体数量。太小时难以求出最优解，太大则增长收敛时间导致程序运行时间长。对不同的问题可能有各自适合的种群规模，通常种群规模为 30 至 160。

pc：在循环中进行交叉操作所用到的概率。交叉概率（Pc）一般取0.6至0.95之间的值，Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。

Pm：变异概率，从个体群中产生变异的概率，变异概率一般取0.01至0.03之间的值变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。

另一个系统参数是个体的长度，有定长和变长两种。它对算法的性能也有影响。由于GA是一个概率过程，所以每次迭代的情况是不一样的,系统参数不同，迭代情况也不同。

_遗传步骤

了解了上面的基本参数，下面我们来看看遗传算法的基本步骤。

基本过程为：

对待解决问题进行编码,我们将问题结构变换为位串形式编码表示的过程叫编码；而相反将位串形式编码表示变换为原问题结构的过程叫译码。

随机初始化群体P(0)：=(p1, p2, … pn)；

计算群体上每个个体的适应度值(Fitness)

评估适应度,对当前群体P(t)中每个个体Pi计算其适应度F(Pi)，适应度表示了该个体的性能好坏

按由个体适应度值所决定的某个规则应用选择算子产生中间代Pr(t)

依照Pc选择个体进行交叉操作

仿照Pm对繁殖个体进行变异操作

没有满足某种停止条件，则转第3步，否则进入9

输出种群中适应度值最优的个体

程序的停止条件最简单的有如下二种：完成了预先给定的进化代数则停止；种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。

根据遗传算法思想可以画出如右图所示的简单遗传算法框图：

_{图3. 简单遗传算法框图}

下面伪代码简单说明了遗传算法操作过程：

choose an intial population
For each h in population,compute Fitness(h)
While(max Fitness(h) < Fitnessthreshold)
do selection
    do crossover
do mutation  
 update population
For each h in population,compute Fitness(h)
Return best Fitness

能有效实现遗传算法的应用例子有很多，像西洋双陆棋、国际名模等等都是遗传程序设计学习的工具，但是 Robocode 有着其他几个无可比拟的优势：

它是基于面向对象语言 Java 开发，而遗传算法本身的思想也是存在继承等面向对象概念；

Robocode 是一种基于游戏与编程语言之间的平台，有一个充满竞技与乐趣的坦克战斗平台，你能很快的通过与其他坦克机器比赛而测试自己的遗传算法；

Robocode 社群有 4000 个左右各种策略的例子机器人可供你选择，这些机器人足以让我们模拟真实的遗传环境。而且很多代码可直接开放源代码供我们借鉴 ；

Robocode 是一个开源软件，你可直接上Robocode控制器上加入自己的遗传特点，而加快遗传过程的收敛时间；

Robocoe 是一个很容易使用的机器人战斗仿真器，您在此平台上创建自己的坦克机器人，并与其它开发者开发的机器人竞技。以得分排名的方式判定优胜者。每个 Robocode 参加者都要利用 Java 语言元素创建他或她的机器人，这样就使从初学者到高级黑客的广大开发者都可以参与这一娱乐活动。如果您对Robocode不是很了解，请参考 developerWorks 网站 Java 技术专区文章：“重锤痛击 Robocode”；

在 Robocode 中其实有很多种遗传算法方法来实现进化机器人，从全世界的 Robocode 流派中也发展几种比较成熟的方法，比如预设策略遗传、自开发解释语言遗传、遗传移动我们就这几种方法分别加以介绍。由于遗传算法操作过程都类似，所以前面 二部分都是一些方法的介绍和部分例子讲解，后面部分会给出使用了遗传算法的移动机器人人例子。 在附录中，也提供了机器人仓库中有关遗传算法机器人的下载，大家可参考。

Robocode 坦克机器人所有行为都离不开如移动、射击、扫描等基本操作。所以在此把这些基本操作所用到的策略分别进化如下编码：移动策略move-strategy (MS), 子弹能量bullet-power-strategy (BPS), 雷达扫描radar-strategy (RS), 和瞄准选择策略target- strategy (TS)。由于Robocode爱好者社群的发展，每一种基本操作都发展了很多比较成熟的策略，所有在此我们直接在下面预先定义的这些策略如下表：

下面是基本移动策略的说明：

Random：随机移动主要用来混乱敌人的预测，其最大的一个缺点是有可能撞击到其他机器人

Linear：直线移动,机器人做单一的直线行走

circular：圆周移动，这种移动是以某一点为圆心，不停的绕圈

Perpendicular：正对敌人移动，这是很多人采用的一种移动方式，这在敌人右边， 以随时调整与敌人的相对角

Arbitrary：任意移动

AntiGravity： 假设场地有很多力点的反重力移动，本方法是模拟在重力场作用下，物体总是远离重力势高的点，滑向重力势低的点，开始战场是一个平面然后生成一些势点重力势 大的势点的作用就像是一个山(起排斥作用），其衰减系数与山的坡度对应。重力势小的势点的作用就像是一个低谷（起吸引作用），其衰减系数与谷的坡度对应。 这样使本来的平面变得不平了，从来物体沿着最陡的方向向下滑动

Track：跟踪敌人，敌人移动到哪，机器人也移动到哪，但是总与敌人保持一定最佳躲避子弹距离和角度

Oscillators：重复做一振荡移动

Bullet avoid：每当雷达觉察到敌人时有所动作。机器人保持与敌人成30度倾向角。自身成 90 度角静止并逐渐接近目标。如果机器人觉察到能量下降介于 0.1 和 3.0 之间（火力范围），那么机器人就立即切换方向，向左或向右移动。

wall avoid：这是一种使自己的机器人不会被困在角落里或者不会撞墙的移动方式

瞄准策略说明如下：

Headon：正对瞄准

Linear：直线瞄准

circular：圆周瞄准

nearest robot：接近机器人瞄准

Log：保存每次开火记录

Statistic：统计学瞄准，分析所有打中及未打中的次数，以其中找出最高打中敌人的概率为准则

Angular：找到最佳角度瞄准

Wave：波形瞄准，子弹以波的方式进行探测

共4页 [1] [2] [3] [4] 下一页  第1页第2页第3页第4页