|
ble[] adaptiveva lue = new double[initSetsNum];
for (int i = 0; i < initSetsNum; i++) {
adaptiveva lue[i] = calFitness(initCodes.get(i));
sumFitness += adaptiveva lue[i];
}
// 转成概率的形式，做归一化操作
for (int i = 0; i < initSetsNum; i++) {
adaptiveva lue[i] = adaptiveva lue[i] / sumFitness;
}
for (int i = 0; i < initSetsNum; i++) {
randomNum = random.nextInt(100) + 1;
randomNum = randomNum / 100;
//因为1.0是无法判断到的，,总和会无限接近1.0取为0.99做判断
if(randomNum == 1){
randomNum = randomNum - 0.01;
}
sumFitness = 0;
// 确定区间
for (int j = 0; j < initSetsNum; j++) {
if (randomNum > sumFitness
&& randomNum <= sumFitness + adaptiveva lue[j]) {
// 采用拷贝的方式避免引用重复
resultCodes.add(initCodes.get(j).clone());
break;
} else {
sumFitness += adaptiveva lue[j];
}
}
}
return resultCodes;
}
/**
* 交叉运算
*
* @param selectedCodes
* 上步骤的选择后的编码
* @return
*/
private ArrayList crossOperate(ArrayList selectedCodes) {
int randomNum = 0;
// 交叉点
int crossPoint = 0;
ArrayList resultCodes = new ArrayList<>();
// 随机编码队列，进行随机交叉配对
ArrayList randomCodeSeqs = new ArrayList<>();
// 进行随机排序
while (selectedCodes.size() > 0) {
randomNum = random.nextInt(selectedCodes.size());
randomCodeSeqs.add(selectedCodes.get(randomNum));
selectedCodes.remove(randomNum);
}
int temp = 0;
int[] array1;
int[] array2;
// 进行两两交叉运算
for (int i = 1; i < randomCodeSeqs.size(); i++) {
if (i % 2 == 1) {
array1 = randomCodeSeqs.get(i - 1);
array2 = randomCodeSeqs.get(i);
crossPoint = random.nextInt(stepNum - 1) + 1;
// 进行交叉点位置后的编码调换
for (int j = 0; j < 2 * stepNum; j++) {
if (j >= 2 * crossPoint) {
temp = array1[j];
array1[j] = array2[j];
array2[j] = temp;
}
}
// 加入到交叉运算结果中
resultCodes.add(array1);
resultCodes.add(array2);
}
}
return resultCodes;
}
/**
* 变异操作
*
* @param crossCodes
* 交叉运算后的结果
* @return
*/
private ArrayList variationOperate(ArrayList crossCodes) {
// 变异点
int variationPoint = 0;
ArrayList resultCodes = new ArrayList<>();
for (int[] array : crossCodes) {
variationPoint = random.nextInt(stepNum);
for (int i = 0; i < array.length; i += 2) {
// 变异点进行变异
if (i % 2 == 0 && i / 2 == variationPoint) {
array[i] = (array[i] == 0 ? 1 : 0);
array[i + 1] = (array[i + 1] == 0 ? 1 : 0);
break;
}
}
resultCodes.add(array);
}
return resultCodes;
}
/**
* 根据编码计算适值
*
* @param code
* 当前的编码
* @return
*/
public double calFitness(int[] code) {
double fintness = 0;
// 由编码计算所得的终点横坐标
int endX = 0;
// 由编码计算所得的终点纵坐标
int endY = 0;
// 基于片段所代表的行走方向
int direction = 0;
// 临时坐标点横坐标
int tempX = 0;
// 临时坐标点纵坐标
int tempY = 0;
endX = startPos[0];
endY = startPos[1];
for (int i = 0; i < stepNum; i++) {
direction = binaryArrayToNum(new int[] { code[2 * i],
code[2 * i + 1] });
// 根据方向改变数组做坐标点的改变
tempX = endX + MAZE_DIRECTION_CHANGE[direction][0];
tempY = endY + MAZE_DIRECTION_CHANGE[direction][1];
// 判断坐标点是否越界
if (tempX >= 0 && tempX < mazeData.length && tempY >= 0
&& tempY < mazeData[0].length) {
// 判断坐标点是否走到阻碍块
if (mazeData[tempX][tempY] != -1) {
endX = tempX;
endY = tempY;
}
}
}
// 根据适值函数进行适值的计算
fintness = 1.0 / (Math.abs(endX - endPos[0])
+ Math.abs(endY - endPos[1]) + 1);
return fintness;
}
/**
* 根据当前编码判断是否已经找到出口位置
*
* @param code
* 经过若干次遗传的编码
* @return
*/
private boolean ifArriveEndPos(int[] code) {
boolean isArrived = false;
// 由编码计算所得的终点横坐标
int endX = 0;
// 由编码计算所得的终点纵坐标
int endY = 0;
// 基于片段所代表的行走方向
int direction = 0;
// 临时坐标点横坐标
int tempX = 0;
// 临时坐标点纵坐标
int tempY = 0;
endX = startPos[0];
endY = startPos[1];
for (int i = 0; i < stepNum; i++) {
direction = binaryArrayToNum(new int[] { code[2 * i],
code[2 * i + 1] });
// 根据方向改变数组做坐标点的改变
tempX = endX + MAZE_DIRECTION_CHANGE[direction][0];
tempY = endY + MAZE_DIRECTION_CHANGE[direction][1];
// 判断坐标点是否越界
if (tempX >= 0 && tempX < mazeData.length && tempY >= 0
&& tempY < mazeData[0].length) {
// 判断坐标点是否走到阻碍块
if (mazeData[tempX][tempY] != -1) {
endX = tempX;
endY = tempY;
}
}
}
if (endX == endPos[0] && endY == endPos[1]) {
isArrived = true;
}
return isArrived;
}
/**
* 二进制数组转化为数字
*
* @param binaryArray
* 待转化二进制数组
*/
private int binaryArrayToNum(int[] binaryArray) {
int result = 0;
for (int i = binaryArray.length - 1, k = 0; i >= 0; i--, k++) {
if (binaryArray[i] == 1) {
result += Math.pow(2, k);
}
}
return result;
}
/**
* 进行遗传算法走出迷宫
*/
public void goOutMaze() {
// 迭代遗传次数
int loopCount = 0;
boolean canExit = false;
// 结果路径
int[] resultCode = null;
ArrayList initCodes;
ArrayList selectedCodes;
ArrayList crossedCodes;
ArrayList variationCodes;
// 产生初始数据集
produceInitSet();
initCodes = initSets;
while (true) {
for (int[] array : initCodes) {
// 遗传迭代的终止条件为是否找到出口位置
if (ifArriveEndPos(array)) {
resultCode = array;
canExit = true;
break;
}
}
if (canExit) {
break;
}
selectedCodes = selectOperate(initCodes);
crossedCodes = crossOperate(selectedCodes);
variationCodes = variationOperate(crossedCodes);
initCodes = variationCodes;
loopCount++;
//如果遗传次数超过100次，则退出
if(loopCount >= 100){
break;
}
}
System.out.println("总共遗传进化了" + loopCount + "次");
printFindedRoute(resultCode);
}
/**
* 输出找到的路径
*
* @param code
*/
private void printFindedRoute(int[] code) {
if(code == null){
System.out.println("在有限的遗传进化次数内，没有找到最优路径");
return;
}
int tempX = startPos[0];
int tempY = startPos[1];
int direction = 0;
System.out.println(MessageFormat.format(
"起始点位置({0},{1}), 出口点位置({2}, {3})", tempX, tempY, endPos[0],
endPos[1]));
System.out.print("搜索到的结果编码：");
for(int value: code){
System.out.print("" + value);
}
System.out.println();
for (int i = 0, k = 1; i < code.length; i += 2, k++) {
direction = binaryArrayToNum(new int[] { code[i], code[i + 1] });
tempX += MAZE_DIRECTION_CHANGE[direction][0];
tempY += MAZE_DIRECTION_CHANGE[direction][1];
System.out.println(MessageFormat.format(
"第{0}步,编码为{1}{2},向{3}移动，移动后到达({4},{5})", k, code[i], code[i+1],
MAZE_DIRECTION_LABEL[direction], tempX, tempY));
}
}
}
算法的调用类Client.java:
?
?
package GA_Maze;
/**
* 遗传算法在走迷宫游戏的应用
* @author lyq
*
*/
public class Client {
public static void main(String[] args) {
//迷宫地图文件数据地址
String filePath = "C:\\Users\\lyq\\Desktop\\icon\\mapData.txt";
//初始个体数量
int initSetsNum = 4;
GATool tool = new GATool(filePath, initSetsNum);
tool.goOutMaze();
}
}
?
算法的输出：
我测了很多次的数据，因为有可能会一时半会搜索不出来，我设置了最大遗传次数100次。
?
总 |