人工智能 Java 坦克机器人系列: 遗传算法－机器与智能网

关键词：Java

适应度值在进行运算过程中由机器人程序不断调整，以找到最优适应度。

限于篇副其他的一些策略本文不与详细说明，上面所有提到的策略和行为程序都可在网上或IBM的开发杂志上找到成熟的讲解和例子机器人。有兴趣的朋友可以把这些策略都加入到自己的遗传算法中来。我们取群体大小为50，选择概率为0.7，交叉概率为0.6，变异概率为0.3，与Robocode部分例子机器人测试，经过150代后你会发现系统产生了很多有趣的策略。比如撞击策略，这些策略都不在我们定义的策略之中。

_{中间解释程序进化机器人}

遗传算法可被看做任意基因组字符串。但是你必须决定这些字符所代表的意义，也就是说如何解释每一个基因组。最简单的方法是把每一个基因组视为java代码，编译并运行它们。但是这些程序编译都很困难，所以也就有可能不能工作。Jacob Eisenstein设计了一种机器翻译语言TableRex来解决这个问题。在java中，TableRex被用于进化和解释动行时的Robocode 机器人。通过测试，只要我把TableRex解释程序作为文件放入Robocode控制器目录中，这些控制器就会读取文件并开始战斗。TableRex是一些最适合遗传算法的二进制编程。只要符合TableRex程序文法，每个程序都能被解释。

_编码

下表中显示了TableRex编码结构，它由一个行动作函数，二个输入和一个输出组成。如行6的值，这是个布尔型的表达式“值 line4 小于 90”，这个结果会在最后一行输出布尔为1的值。

Function	Input 1	Input 2	Output
1. Random	ignore	ignore	0,87
2. Divide	Const_1	Const_2	0,5
3. Greater Than	Line 1	Line 2	1
4. Normalize Angle	Enemy bearing	ignore	-50
5. Absolute Value	Line 4	ignore	50
6. Less Than	Line 4	Const_90	1
7. And	Line 6	Line 3	1
8. Multiply	Const_10	Const_10	100
9. Less Than	Enemy distance	Line 8	0
10. And	Line 9	Line 7	0
11. Multiply	Line 10	Line 4	0
12 Output	Turn gun left	Line 11	0

输入的函数我们依照Robocode定义而定。如下表：

velocity
energy
heading
gunHeading
gunHeat
distance to west wall
distance to north wall
distance to east wall
distance to south wall
constant: 1
constant: 2
constant: 10
constant: 90
enemyVelocity
enemyEnergy
enemyHeading
enemyBearing
enemyDistance

TableRex有三个设计标准：

它是一种解释程序，能更快的进化程序,基于TableRex设计的机器人能有效的读写遗传数据；
拥有一个容易编码的固定基因组,使遗传中更容易交叉操作；
只要给TableRex一个简单的输入，它就很容易通过操作命令输出要的命令序列。如上表的最后输出左转炮管；

而整个TableRex解释程序由三部分组成：

SmallBrain：TableRex的实现部分,此部分直接写在例子机器人处，也即自己写的测试机器人；
BrainWorld：这是实现遗传算法的主方法，直接写入Robocode控制器当中，在Robocode运行当中运行；
GeneticAlgorithm：这是遗传算法的定义部分，里面直接定义了所要用到的遗传操作函数；

下面我们来分析一个机器人如何通过TableRex达到遗传。

_{GeneticAlgorithm：}

主要是声明选择、交叉、变异的方法。

GeneticAlgorithm是一个静态类，其中定义了遗传所要的基本参数，如下：

public abstract class GeneticAlgorithm {
    public int population_size;  // 群体长度
    public int genome_size;    //基因个体长度
    public GFPair population[];  //产生的群体
    public int best_index;  
    public double best_fitness = Double.MIN_VALUE;  //最优适应度
    public double mutation = 0.03;  //变异概率
public double crossover = 0.9;   //交叉概率
public double copy = 0.1;
public int tourney_size = 3;
…

其中变异概率取0.03, 交叉概率取0.9，最优适应度为实型的最小。此部分是从保存的文件中读取各个基本参数遗传初始化群体。

依照适应度值选择群体中个体：

public String tourneySelect (){
	double best_fit = -1;
	int best_guy = -1;
	for (int i = 0; i < tourney_size; i++){
	    int cur_guy = (int) (Math.random() * population.length);	
	    if (population[cur_guy].fitness > best_fit){
		best_fit = population[cur_guy].fitness;
		best_guy = cur_guy;
	    }
	}
	…
	return population[best_guy].genome;
}

交叉操作：通过从字符串中取子串的方法达到交叉操作：

public static String crossover (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){
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 = new GeneticAlgorithm (population_size, genome_size);

2. 通过文件读取操作从遗传保存文件中读取参数到遗传类中，文件格式如下所示：

       Robocode Location
       Storage_directory
       population_size
       elitism
       crossover
       copy
       base_mutation
       ...

3. 计算最优适应度：

protected void evaluateAll (){
	ga.best_fitness = Double.MIN_VALUE;
	ga.worst_fitness = Double.MAX_VALUE;
   …
	for (int i = 0; i < ga.population_size; i++){
	    ga.population[i].fitness = 0;
	    for (int j = 0; j < rspecs.length; j++){
		ga.population[i].fitness += 
		    Math.pow (2.0, (all_results[i][j] - all_means[j]) / all_stdevs[j]);  
	    }
	    ga.mean_fitness += ga.population[i].fitness;
	    if (ga.population[i].fitness > ga.best_fitness) {
		ga.best_fitness = ga.population[i].fitness;
		ga.best_index = i;
	    }
	   …
	}
	…
    }

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

ROBOT & AI

人工智能 Java 坦克机器人系列: 遗传算法