模拟生物进化过程，物竞天择，适者生存。
首先就是要产生一些种群，进行种群的初始化主要有以下三步：
假设现在为栅格图形进行编码，与使用A*与Dijkstra算法操作一致。
现在要从起点0到达终点24这个栅格，可以看到这样一条路径。
就可以用这样一种方法来表示一个个体（指这条路径）。所以说，首先我们就是要产生很多条这种个体（路径），之后再从众多个体当中，选取最优的那一个个体。
与A*等算法一致，其只能在相邻的栅格或者对角栅格当中进行走。以这种方式进行行走的话，每一行都至少会经过一个栅格，所以先把每行必走的一个栅格确认出来。
种群初始化
Q:选择完每行的栅格后，怎么判断相邻栅格之间是否连续呢？
A:为地图建立一个坐标系，为每一个栅格分配一个X，Y上的坐标，若两个相邻的栅格，其X的坐标或者Y的坐标最大值只相差1的话，即：
D
=
max
{
abs
(
x
i
+
1
−
x
i
)
,
abs
(
y
i
+
1
−
y
i
)
}
D=\max \left\{\operatorname{abs}\left(x^{i+1}-x^{i}\right), \operatorname{abs}\left(y^{i+1}-y^{i}\right)\right\}
D=max{abs(xi+1−xi),abs(yi+1−yi)}，就可以直接走过去，就表示两个栅格是相邻的或者对角的。
转换过程
y
=
int
(
N
/
G
size
)
+
1
y=\operatorname{int}\left(N / G_{\text {size }}\right)+1
y=int(N/Gsize )+1
x
=
N
%
(
G
size
)
x=N \%\left(G_{\text {size }}\right)
x=N%(Gsize )+1
直接除取整就知道在第几行，取余数就说明在第几列。+1操作就是想在编程环境中选择从1开始而不是从0开始，从0开始去掉+1就行。
不连续时采取的操作
做法就是插入新的栅格，插入中间新的栅格，比如说6号点的坐标与13号点的坐标，其距离相差2，所以是不连续的，所以插入中间栅格，就是上面两个坐标加一起取平均值，再向下取整，(2+3)/2直接算的话是2.5，进行向下取整的话，那就是2。所以产生的坐标是(3,2)，这样对应的就是7这个栅格，将7加进来，发现6、7就连续了，往后走，发现7和13也是连续的。
然后就产生了这个路径。
若相邻的两个栅格之间的距离比较远，那我们就可以反复执行这个过程，再判断，直到整个路径都连续。
在经过上方的初始化以后，就要进入遗传算法的循环了。
为了看哪个个体的路径更好，就要对每一个个体进行打分。采取了一个适应度的概念（即距离的倒数）。
d
=
∑
i
=
1
e
n
d
−
1
(
x
i
+
1
−
x
i
)
2
+
(
y
i
+
1
−
y
i
)
2
d=\sum_{i=1}^{e n d-1} \sqrt{\left(x_{i+1}-x_{i}\right)^{2}+\left(y_{i+1}-y_{i}\right)^{2}}
d=∑i=1end−1(xi+1−xi)2+(yi+1−yi)2
对越短的路径而言，其适应度越大。
f
i
t
1
=
1
/
d
f i t_{1}=1 / d
fit1=1/d
还有一个就是路径的顺滑性。
以这三点为例，组成了一个三角形，要想路径越顺滑，则这个角更大即可满足。可以用余弦定理进行计算，加入到这个适应度函数。角度越大的话越好。
f i t 2 = arccos ( ( b 2 + c 2 − a 2 ) / 2 b c ) fit _{2}=\arccos \left(\left(b^{2}+c^{2}-a^{2}\right) / 2 b c\right) fit2=arccos((b2+c2−a2)/2bc)
然后分别对两个适应度函数求权重，这个权重可以通过实验来获得。
f
i
t
=
a
f
i
t
1
+
b
f
i
t
2
fit =a f i t_{1}+b f i t_{2}
fit=afit1+bfit2
有了适应度的值，就可以为每个个体计算一个概率。相当于保留这条路径的概率。所以一些好的个体被保留下来的概率越大，但也会有较差的个体，后面可以通过交叉和变异来“发育”的更好。
p i = f i t i / ∑ i = 1 e n d f i t i p_{i}=f i t_{i} / \sum_{i=1}^{e n d} f i t_{i} pi=fiti/∑i=1endfiti
发现两条路径在13这个点上进行交叉。可以通过交换交叉点前后的路径形成新路径。这样就丰富了个体。
关于完备性，起点和终点之间有路径解存在的话，一定可以得到解，但遗传算法并不能保证得到的是最优的一个路径，代码讲解在下一篇Blog，争取早日肝出来。
