前言
遗传(GA)算法是一个非常有意思的算法，因为他利用了生物进化理论的知识进行问题的求解。算法的核心就是把拥有更好环境适应度的基因遗传给下一代，这就是其中的关键的选择操作，遗传算法整体的阶段分为选择，交叉和变异操作，选择操作和变异操作在其中又是比较重要的步骤。
算法在迷宫游戏中的应用
先说说走迷宫游戏要解决的问题是什么， 走迷宫游戏说白了就是给定起点，终点，中间设置一堆的障碍，然后要求可达的路径，注意这里指的是可达路径，并没有说一定是最优路径，因为最优路径一定是用步数最少的，这一点还是很不同的。而另一方面，遗传算法也是用来搜索问题最优解的，所以刚刚好可以转移到这个问题上。用一个遗传算法去解决生活中的实际问题最关键的就是如何用遗传算法中的概念表示出来，比如遗传算法中核心的几个概念，基因编码，基因长度的设置，适应度函数的定义，3个概念每个都很重要。好的，目的要求已经慢慢的明确了，下面一个个问题的解决。
为了能让大家更好的理解，下面举出一个例子，如图所示：
图是自己做的，比较简略，以左边点的形式表示，从图中可以看出，起点位置（4， 4），出口左边为绿色区域位置（1，0），X符号表示的障碍区域，不允许经过，问题就转为搜索出从起点到终点位置的最短路径，因为本身例子构造的不是很复杂，我们按照对角线的方式出发，总共的步数=4-1 + 4-0=7步，只要中间不拐弯，每一步都是靠近目标点方向的移动就是最佳的方式。下面看看如何转化成遗传算法中的概念表示。
个体基因长度
首先是基于长度，因为最后筛选出的是一个个体，就是满足条件的个体，他的基因编码就是问题的最优解，所以就能联想把角色的每一步移动操作看出是一个基因编码，总共7步就需要7个基因值表示，所以基因的长度在本例子中就是7。
基因表示
已经将角色的每一次的移动步骤转化为基因的表示，每次的移动总共有4种可能，上下左右，基因编码是标准的二进制形式，所以可以取值为00代表向上，01向下，10向左，11向右，也就是说，每个基因组用2个编码表示，所以总共的编码数字就是2*7=14个，两两一对。
适应度函数
适应度函数的设置应该是在遗传算法中最重要了吧，以为他的设置好坏直接决定着遗传质量的好坏，基因组表示的移动的操作步骤，给定起点位置，通过基因组的编码组数据，我们可以计算出最终的抵达坐标，这里可以很容易的得出结论，如果最后的抵达坐标越接近出口坐标，就越是我们想要的结果，也就是适应值越高，所以我们可以用下面的公式作为适应度函数：
(x, y)为计算出的适应值的函数值在0到1之间波动，1为最大值，就是抵达的坐标恰好是出口位置的时候，当然适应度函数的表示不是唯一的。
算法的代码实现
算法地图数据的输入mapData.txt：
?
0 0 0 0 0
2 0 0 -1 0
0 0 0 0 0
0 -1 0 0 -1
0 0 0 0 1
就是上面图示的那个例子.
算法的主要实现类GATool.java:
?
?
package GA_Maze;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.Random;
/**
* 遗传算法在走迷宫游戏的应用-遗传算法工具类
*
* @author lyq
*
*/
public class GATool {
// 迷宫出入口标记
public static final int MAZE_ENTRANCE_POS = 1;
public static final int MAZE_EXIT_POS = 2;
// 方向对应的编码数组
public static final int[][] MAZE_DIRECTION_CODE = new int[][] { { 0, 0 },
{ 0, 1 }, { 1, 0 }, { 1, 1 }, };
// 坐标点方向改变
public static final int[][] MAZE_DIRECTION_CHANGE = new int[][] {
{ -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 }, };
// 方向的文字描述
public static final String[] MAZE_DIRECTION_LABEL = new String[] { "上",
"下", "左", "右" };
// 地图数据文件地址
private String filePath;
// 走迷宫的最短步数
private int stepNum;
// 初始个体的数量
private int initSetsNum;
// 迷宫入口位置
private int[] startPos;
// 迷宫出口位置
private int[] endPos;
// 迷宫地图数据
private int[][] mazeData;
// 初始个体集
private ArrayList initSets;
// 随机数产生器
private Random random;
public GATool(String filePath, int initSetsNum) {
this.filePath = filePath;
this.initSetsNum = initSetsNum;
readDataFile();
}
/**
* 从文件中读取数据
*/
public void readDataFile() {
File file = new File(filePath);
ArrayList dataArray = new ArrayList();
try {
BufferedReader in = new BufferedReader(new FileReader(file));
String str;
String[] tempArray;
while ((str = in.readLine()) != null) {
tempArray = str.split(" ");
dataArray.add(tempArray);
}
in.close();
} catch (IOException e) {
e.getStackTrace();
}
int rowNum = dataArray.size();
mazeData = new int[rowNum][rowNum];
for (int i = 0; i < rowNum; i++) {
String[] data = dataArray.get(i);
for (int j = 0; j < data.length; j++) {
mazeData[i][j] = Integer.parseInt(data[j]);
// 赋值入口和出口位置
if (mazeData[i][j] == MAZE_ENTRANCE_POS) {
startPos = new int[2];
startPos[0] = i;
startPos[1] = j;
} else if (mazeData[i][j] == MAZE_EXIT_POS) {
endPos = new int[2];
endPos[0] = i;
endPos[1] = j;
}
}
}
// 计算走出迷宫的最短步数
stepNum = Math.abs(startPos[0] - endPos[0])
+ Math.abs(startPos[1] - endPos[1]);
}
/**
* 产生初始数据集
*/
private void produceInitSet() {
// 方向编码
int directionCode = 0;
random = new Random();
initSets = new ArrayList<>();
// 每个步骤的操作需要用2位数字表示
int[] codeNum;
for (int i = 0; i < initSetsNum; i++) {
codeNum = new int[stepNum * 2];
for (int j = 0; j < stepNum; j++) {
directionCode = random.nextInt(4);
codeNum[2 * j] = MAZE_DIRECTION_CODE[directionCode][0];
codeNum[2 * j + 1] = MAZE_DIRECTION_CODE[directionCode][1];
}
initSets.add(codeNum);
}
}
/**
* 选择操作，把适值较高的个体优先遗传到下一代
*
* @param initCodes
* 初始个体编码
* @return
*/
private ArrayList selectOperate(ArrayList initCodes) {
double randomNum = 0;
double sumFitness = 0;
ArrayList resultCodes = new ArrayList<>();
dou