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

关键词：Java

_Robocode 行为事件

坦克的主要都定义在一个主循环中，我们在程序中定义为上面四个策略定义四种战略如Move, Radar,Power,Target，当某一事件发生，基于这个事件而定的行为就会触发。而每个战略中都有不同的行为处理方式。这些行为通过遗传算法触发，遗传算法将调用这些基本动作并搜索这些策略的最佳组合。基于这些基本动作将有4224 (=4*11*4*3*8)种可能发生。在Robocode AdvancedRobot 类下有如下的移动函数：

setAhead和ahead：让机器人向前移动一定距离.

setBack和back：让机器人向后移动一定距离

setMaxTurnRate：设置机器人最大的旋转速度

setMaxVelocity：设置机器人最大的运动速度

setStop和stop：停止移动或暂停机器人，并记住停止的位置

setResume和resume：重新开始移动停止的机器人

setTurnLeft和turnLeft：向左旋转机器人

setTurnRight和turnRight：向右旋转机器人

下面是 doMove 移动方法中使用部分程序代码：

Random：

switch(Math.random()*2) {
	case 0：	setTurnRight(Math.random()*90);
break;
case 1：	setTurnLeft(Math.random()*90);
	break;	}
	execute();

Linear：

ahead(200);
setBack(200);

Circular：

setTurnRight(1000);
setMaxVelocity(4);
ahead(1000);

anti gravity：

	double forceX = 0;
		double forceY = 0;
		for (int i=0; i<targetInfo.size(); i++){
				TargetInformation ti = (TargetInformation)targetInfo.get(i);
				double targetToMeX = getX()-ti.x;
				double targetToMeY = getY()-ti.y;
				double targetDistance = Math.sqrt(ti.x * ti.x + ti.y * ti.y);
				forceX += (targetToMeX/(ti.distance * ti.distance));
				forceY += (targetToMeY/(ti.distance * ti.distance));
		}
		forceX += 1/(getX());
		forceY += 1/(getY());
		forceX += 1/(getX()-getBattleFieldWidth());
		forceY += 1/(getY()-getBattleFieldHeight());
		double forceMagnitude = Math.sqrt(forceX*forceX+forceY*forceY);
		forceX*=8/forceMagnitude;
		forceY*=8/forceMagnitude;
		desiredX = getX() + forceX;
		desiredY = getY() + forceY;
…

这里我们用遗传算法来控制机器人移动位置。这些策略是基于下面几点：机器人人自己的位置、速度和方位;对手的位置（x,y坐标）、速度、方位以及相对角;所有机器人和子弹位置，方位及速度;场地大小等参数。

当上面的信息在下一回移动中使用时，出输出一对坐标值，根据这对坐标在Robocode就能得到距离和角度。要想让移动实现遗传必须要让它实现在线学习：所以我们的代码必须做下面几件事：要有一个函数收集适应度值，在Robocode运行过程中要运用到遗传操作，遗传后代要在Robocode运行中产生，而不是事后由手写入代码。

_遗传操作

本例中遗传算法为实现移动用到两个类GA和MovePattern。此处的GA比较简单主要完成数据和群体的定义，以及这些定义的读写文件操作。基中包括如下参数：群体大小、交叉概率、变异概率、精英概率（既告诉从当前群体到下一代中有多少移动不需要改变）、方程式中使用的加权系数大小，它通过一个主循环完成MovePattern的封装。MovePattern类中实现交叉、变异方法等方法，完成移动模式操作。而所有的输出保存在一个vector函数当中。Vector函数拥有一对实数数组，一个用于计算x坐标，另一个用于计算y坐标。通过对x,y坐标的计算，从而得到距离、角度等值，并产生相就在移动策略。如下，MovePattern包含三个参数，grad表示vector函数排列顺序，input即表示算法给出的输入编号，rang是加权的范围。

public class MovePatteren implements Comparable {
	private int grad, input;
	private double range;
	protected double fitness=0;
	protected double[] weightsX, weightsY;    
… }

交叉操作：每一个交叉操作执行如下步骤，先在交叉操作中产生一个特征码。这个特征码是个0到1之间的变量数组。有关交叉的基本原理可参考上面部分。最后通过遍历vector函数，把相应的加权值进行交叉操作。

protected MovePatteren crossOver(MovePatteren mate, boolean[] maskx, boolean[] masky) {
		double[] wx= new double[weightsX.length];
		double[] wy= new double[weightsX.length];
		for(int mask=0; mask<maskx.length; mask++) {
			for(int g=0; g<=grad; g++) {
				int i=mask*(grad+1)+g;
				wx[i]=(maskx[mask]?this：mate).weightsX[i];
				wy[i]=(masky[g]?this：mate).weightsY[i];
			}
		}
		return new MovePatteren(grad, input, range, wx, wy);
	}

这里的变异操作比较简单。把加权范围内的随机数值去代替0到数组长之间的随机数并保存到移动模式中。则完成整个数组的变异过程：

protected void mutate() {
weightsX[(int)(Math.random()*weightsX.length)]=Math.random()*range*2-range;
weightsY[(int)(Math.random()*weightsX.length)]=Math.random()*range*2-range;
}

从上面的例子我们知道了遗传算法的大概实现，但并没有告诉我们这些组件是如何一起工作的。当 Robocode开始时，如果文件中没有数据，所以系统会依照输入的策略随机生成一个移动模式，如果文件中有数据，则加载这些数据。每一个移动模式在开始都会给出了一个适应度值。当所有的移动模式都接收到适应度值，并完成各自的编号后，下面的操作将开始执行：

对所有的移动模式依据它们的适应度值进行分级处理

执行精英操作

执行交叉操作

应用变异操作

保存加权

算法重新开始

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

ROBOT & AI

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