人工智能java坦克机器人系列

《人工智能java坦克机器人系列》由会员分享，可在线阅读，更多相关《人工智能java坦克机器人系列（18页珍藏版）》请在金锄头文库上搜索。

1、人工智能 Java 坦克机器人系列: 遗传算法遗传算法（Genetic Algorithm, GA）是近几年发展起来的一种崭新的全局优化算法。本文 将讲解这种算法，并介绍如何 Robocode Java 坦克机器人中采用此算法以实现机器人进 化。 遗传算法遗传算法 遗传算法（Genetic Algorithm, GA）是近几年发展起来的一种崭新的全局优化算法。1962 年霍兰德(Holland)教授首次提出了 GA 算法的思想，它借用了仿真生物遗传学和自然选择 机理，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。从某种程 度上说遗传算法是对生物进化过程进行的数学方式仿真。 这

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

3、解带有应用前景的一些问题，例如遗传程序设计、函数优化、排序问题、 人工神经网络、分类系统、计算机图像处理和机器人运动规划等。 术语说明术语说明 由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中会用到很多 生物遗传学知识，下面是我们将会用来的一些术语说明： 一、染色体一、染色体(Chronmosome) 染色体又可以叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中 个体的数量叫做群体大小。 二、基因二、基因(Gene) 基因是串中的元素，基因用于表示个体的特征。例如有一个串 S1011，则其中的 1，0，1，1 这 4 个元素

4、分别称为基因。它们的值称为等位基因(Alletes)。 三、基因地点三、基因地点(Locus) 基因地点在算法中表示一个基因在串中的位置称为基因位置(Gene Position)，有时也简称 基因位。基因位置由串的左向右计算，例如在串 S1101 中，0 的基因位置是 3。 四、基因特征值四、基因特征值(Gene Feature) 在用串表示整数时，基因的特征值与二进制数的权一致；例如在串 S=1011 中，基因位置 3 中的 1，它的基因特征值为 2；基因位置 1 中的 1，它的基因特征值为 8。 五、适应度五、适应度(Fitness) 各个个体对环境的适应程度叫做适应度(fitness)。

5、为了体现染色体的适应能力，引入了对 问题中的每一个染色体都能进行度量的函数，叫适应度函数. 这个函数是计算个体在群体 中被使用的概率。 操作算法操作算法 霍兰德(Holland)教授最初提出的算法也叫简单遗传算法，简单遗传算法的遗传操作主要有 三种：选择(selection)、交叉(crossover)、变异(mutation)这也是遗传算法中最常用的三种 算法：1选择选择(selection) 选择操作也叫复制操作，从群体中按个体的适应度函数值选择出较适应环境的个体。一般 地说，选择将使适应度高的个体繁殖下一代的数目较多，而适应度较小的个体，繁殖下一 代的数目较少,甚至被淘汰。最通常的实现方

6、法是轮盘赌(roulette wheel)模型。令 fi 表示 群体的适应度值之总和，fi 表示种群中第 i 个染色体的适应度值，它被选择的概率正好为其 适应度值所占份额 fifi。如下图表中的数据适应值总和 fi=6650,适应度为 2200 变选择 的可能为 fifi=2200/6650=0.394.图图 1. 轮盘赌模型轮盘赌模型Fitness 值：22001800 1200950400 100选择概率：33310.2710.18 0.1430.060.0152交叉交叉(Crossover) 交叉算子将被选中的两个个体的基因链按一定概率 pc 进行交叉，从而生成两个新的个体， 交叉位置

7、pc 是随机的。其中 Pc 是一个系统参数。根据问题的不同，交叉又为了单点交叉 算子（Single Point Crossover）、双点交叉算子（Two Point Crossover）、均匀交叉算子 (Uniform Crossover)，在此我们只讨论单点交叉的情况。 单点交叉操作的简单方式是将被选择出的两个个体 S1 和 S2 作为父母个体，将两者的部分 基因码值进行交换。假设如下两个 8 位的个体：S11000 1111S21110 1100产生一个在 1 到 7 之间的随机数 c，假如现在产生的是 2，将 S1 和 S2 的低二位交换：S1 的高六位与 S2 的低六位组成数串 10

8、001100，这就是 S1 和 S2 的一个后代 P1 个体；S2 的高六位与 S1 的低二位组成数串 11101111，这就是 S1 和 S2 的一个后代 P2 个体。其 交换过程如下图所示：Crossover11110000 Crossover11110000S11000 1111S21110 1100P11000 1100P21110 11113变异变异(Mutation) 这是在选中的个体中，将新个体的基因链的各位按概率 pm 进行异向转化，最简单方式是 改变串上某个位置数值。对二进制编码来说将 0 与 1 互换：0 变异为 1，1 变异为 0。 如下 8 位二进制编码：1110110

9、0随机产生一个 1 至 8 之间的数 i，假如现在 k=6，对从右往左的第 6 位进行变异操作，将原 来的 1 变为 0，得到如下串：11001100整个交叉变异过程如下图：图图 2. 交叉变异过程交叉变异过程4精英主义精英主义 （Elitism） 仅仅从产生的子代中选择基因去构造新的种群可能会丢失掉上一代种群中的很多信息。也 就是说当利用交叉和变异产生新的一代时，我们有很大的可能把在某个中间步骤中得到的 最优解丢失。在此我们使用精英主义（Elitism）方法，在每一次产生新的一代时，我们首 先把当前最优解原封不动的复制到新的一代中，其他步骤不变。这样任何时刻产生的一个 最优解都可以存活到遗传

10、算法结束。 上述各种算子的实现是多种多样的，而且许多新的算子正在不断地提出，以改进 GA 某些 性能。比如选择算法还有分级均衡选择等等。 遗传算法的所需参数遗传算法的所需参数 说简单点遗传算法就是遍历搜索空间或连接池，从中找出最优的解。搜索空间中全部都是 个体，而群体为搜索空间的一个子集。并不是所有被选择了的染色体都要进行交叉操作和 变异操作，而是以一定的概率进行，一般在程序设计中交叉发生的概率要比变异发生的概 率选取得大若干个数量级。大部分遗传算法的步骤都很类似，常使用如下参数： Fitness 函数：见上文介绍。 Fitnessthreshold（适应度阀值）：适合度中的设定的阀值，当最优

11、个体的适应度达到给定 的阀值，或者最优个体的适应度和群体适应度不再上升时(变化率为零)，则算法的迭代过 程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体， 并返回到选择操作处继续循环执行。 P：种群的染色体总数叫种群规模，它对算法的效率有明显的影响，其长度等于它包含的 个体数量。太小时难以求出最优解，太大则增长收敛时间导致程序运行时间长。对不同的 问题可能有各自适合的种群规模，通常种群规模为 30 至 160。 pc：在循环中进行交叉操作所用到的概率。交叉概率（Pc）一般取 0.6 至 0.95 之间的值， Pc 太小时难以向前搜索，太大则容易破坏高适应值的结构。

12、 Pm：变异概率，从个体群中产生变异的概率，变异概率一般取 0.01 至 0.03 之间的值变异 概率 Pm 太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。 另一个系统参数是个体的长度，有定长和变长两种。它对算法的性能也有影响。由于 GA 是一个概率过程，所以每次迭代的情况是不一样的,系统参数不同，迭代情况也不同。 遗传步骤遗传步骤 了解了上面的基本参数，下面我们来看看遗传算法的基本步骤。 基本过程为： 1.对待解决问题进行编码,我们将问题结构变换为位串形式编码表示的过程叫编码； 而相反将位串形式编码表示变换为原问题结构的过程叫译码。 2.随机初始化群体 P(0)：=(p1,

13、p2, pn)； 3.计算群体上每个个体的适应度值(Fitness) 4.评估适应度,对当前群体 P(t)中每个个体 Pi 计算其适应度 F(Pi)，适应度表示了该个 体的性能好坏 5.按由个体适应度值所决定的某个规则应用选择算子产生中间代 Pr(t) 6.依照 Pc 选择个体进行交叉操作 7.仿照 Pm 对繁殖个体进行变异操作 8.没有满足某种停止条件，则转第 3 步，否则进入 9 9.输出种群中适应度值最优的个体 程序的停止条件最简单的有如下二种：完成了预先给定的进化代数则停止；种群中的最优 个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。 根据遗传算法思想可以画出如右

14、图所示的简单遗传算法框图： 图图 3. 简单遗传算法框图简单遗传算法框图下面伪代码简单说明了遗传算法操作过程：choose an intial population For each h in population,compute Fitness(h) While(max Fitness(h) best_fit) best_fit = populationcur_guy.fitness; best_guy = cur_guy; return populationbest_guy.genome; 交叉操作：通过从字符串中取子串的方法达到交叉操作：public static String cros

15、sover (String g1, String g2) int num_points = (int) Math.round (Math.random() * 4f); int point = (int) (g1.length() * Math.random(); return g1.substring (0, point) + g2.substring (point);变异操作：此部分先把基因转换为字符串流，通过 setCharAt 函数从指定的位置取反字符 而达到变异：public static String mutate (String genome, double p_mutation

16、) StringBuffer genome_b = new StringBuffer (genome); if (genome_b.charAt (point) = 1)genome_b.setCharAt(point, 0); else genome_b.setCharAt (point, 1); return new String (genome_b);BrainWorld： BrainWorld 直接嵌入到 Robocode 控制器中，通过实现 RobocodeListener 接口来完成遗 传的实例化。其最重要的有两个方法，计算最优适应度和产生遗传后代。 1. 实例化 GeneticAlgorithm：genome_size = num_events * num_boxes * (input_bits * 2 + func_bits); int population_size = Integer.parseInt (in.readLine(); ga =