使用遗传算法进行简单寻路

仿照AI IN GAME里的例子写了一遍
程序下载
（note:编辑config.txt来编写地图，第一二行：长，宽，第三四行：出发点，目的地，其余：地图，1表示障碍物）
简单的寻路问题如下所述:
地图为有限大小的矩形,由小方格组成,其中一些小方格不可以通过,给它命名叫障碍点,给定起点和终点求解一条连接两点的路线

(不 通过障碍点).由于是简单的寻路问题,不要求找到最优解.设想一个实际情况就像一个人在走棋盘迷宫,每次只能走一步,只能往前后左右四个方向走，某些位置 上有障碍.给定一个目的地， 如果可达则给出一条通路.图论中有经典的算法解决这个问题，但是遗传算法为解决这个问题提供了一个新的思路，结合这两种方法可以在令人满意的时间内解决规 模较小的寻路问题。
现在来抽象这个问题。用一个二维数组表示地图
bool map[width][height];
true表示有障碍，false表示没有.
初始点和结束点为地图中的两个坐标.
vector2 src;
vector2 dst;
给定这三个条件的情况下求解此问题。
在这个问题中我们将染色体编码定义为每一步所走的方向，因为只有一个方向log2(4)=2位编码可以确定方向。
按染色体所指示的方向移动，生成一个群体，一代一代的选择。

(左图为初始地图，红色表示出发点和目的地，黑色表示障碍物，白色表示无障碍地区。)
(右图为结果图，灰色表示寻找到的路径）
实际上遗传算法为这种问题的求解提供了一种完全不同的思路，就是说与图论不同的思路。
而是把线路看作”基因”(Gene)，形成一个随机的初始解的群体（种群），然后像生物界里所进行的一样，基因杂交，编译，生物优胜劣汰，一代一代的自然选择，最后得到一个比较优的解。（实际上遗传算法不能保证一定可以找到最优解，甚至不能保证找到解）。