一、步骤：
二、重点：
1、编码
由于遗传算法不能直接处理问题空间的数据，所以我们必须将问题空间的数据映射成遗传空间的基因型串结构数据，而算法程序是可以处理遗传空间的基因型串结构数据的。比如现在要计算北京、天津、广东、新疆这四个城市的一条最优路径，但算法程序不能够直接处理北京、天津、广东、新疆这些数据，所以我们得给它们编上号，北京（0）、天津（1）、广东（2）、新疆（3），路径（天津->新疆->北京->广东）可以表示成基因型串结构数据（1302），这样算法程序只要直接处理它们的编号就行了。
（1）二进制编码，基因用0或1表示（常用于解决01背包问题）
如：基因A：00100011010 (代表一个个体的染色体)
（2）互换编码（用于解决排序问题，如旅行商问题和调度问题）
如旅行商问题中，一串基因编码用来表示遍历的城市顺序，如：234517986，表示九个城市中，先经过城市2，再经过城市3，依此类推。
（3）树形编码（用于遗传规划中的演化编程或者表示）
如问题：给定了很多组输入和输出。请你为这些输入输出选择一个函数，使得这个函数把每个输入尽可能近地映射为输出。
编码方法：基因就是树形结构中的一些函数。
（4）值编码 （二进制编码不好用时，解决复杂的数值问题）（源代码中使用类似此方法）
在值编码中，每个基因就是一串取值。这些取值可以是与问题有关任何值：整数，实数，字符或者其他一些更复杂的东西。
遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。
如TSP问题，遍历各城市路径之和越小越好，这样可以用可能的最大路径长度减去实际经过的路径长度，作为该问题的适应度函数。
3、选择在进化中，适者生存，所以在遗传算法运行过程中，会不断地选择优者保留下来，同时也不断地选择劣者淘汰下去。选择算子有很多种方法，以下是比较简单常见的方法：
（1）排序选择方法（源代码中使用类似此方法）
排序选择方法是指在计算每一个个体的适应度（源代码中将路径总长度当适应度）之后，根据适应度大小对个体排序，然后按照事先设置好的概率表按序分配给个体，作为个自的选择概率。
（2）适应度比例方法
适应度比例方法是目前遗传算法中最基本也是最常用的选择方法，即各个个体的选择概率和其适应度值成正比。
（3）最佳个体保留方法
即把群体中适应度最高的个体不进行交叉而直接复制到下一代。
4、交叉
生物进化的核心作用是生物遗传基因的重组，相对应，遗传算法的核心操作是交叉算子，所谓交叉是指两个或两个以上的父代个体的部分结构加以替换重组而生成新个体的操作。
（1）单交叉点法 （用于二进制编码）
选择一个交叉点,子代在交叉点前面的基因从一个父代基因那里得到,后面的部分从另外一个父代基因那里得到。
如：交叉前：
00000|01110000000010000
11100|00000111111000101
交叉后：
00000|00000111111000101
11100|01110000000010000
（2）双交叉点法 （用于二进制编码）
选择两个交叉点,子代基因在两个交叉点间部分来自一个父代基因,其余部分来自于另外一个父代基因.
如：交叉前：
01 |0010| 11
11 |0111| 01
交叉后：
11 |0010| 01
01 |0111| 11
（3）基于“ 与/或 ”交叉法 （用于二进制编码）
对父代按位"与”逻辑运算产生一子代A;按位”或”逻辑运算产生另一子代B。该交叉策略在解背包问题中效果较好 .
如：交叉前：
01001011
11011101
交叉后：
01001001
11011111
（4）单交叉点法 （用于互换编码）
选择一个交叉点，子代的从初始位置出发的部分从一个基因复制，然后在另一个基因中扫描，如果某个位点在子代中没有，就把它添加进去。
如：交叉前：
87213 | 09546
98356 | 71420
交叉后：
87213 | 95640
98356 | 72104
（5）部分匹配交叉（PMX）法（用于互换编码）
先随机产生两个交叉点，定义这两点间的区域为匹配区域，并用交换两个父代的匹配区域。
父代A：872 | 130 | 9546
父代B：983 | 567 | 1420 变为：
TEMP A: 872 | 567 | 9546
TEMP B: 983 | 130 | 1420
对于 TEMP A、TEMP Ｂ中匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行替换。匹配关系：1<——>５ ３<——>６ ７<——>０
子代Ａ：802 | 567 | 9143
子代Ｂ：986 | 130 | 5427
（6）顺序交叉法(OX) （用于互换编码）
从父代Ａ随机选一个编码子串，放到子代Ａ的对应位置；子代Ａ空余的位置从父代Ｂ中按Ｂ的顺序选取（与己有编码不重复）。同理可得子代Ｂ。
父代A: 872 | 139 | 0546
父代B: 983 | 567 | 1420
交叉后：
子代A: 856 | 139 | 7420
子代B: 821 | 567 | 3904
（7）循环交叉（CX）（用于互换编码）
CX同OX交叉都是从一个亲代中取一些城市，而其它城市来自另外一个亲代，但是二者不同之处在于：OX中来自第一个亲代的编码子串是随机产生的，而CX却不是，它是根据两个双亲相应位置的编码而确定的。
父代A：1 2 3 4 5 6 7 8 9
| | | | |
父代B：5 4 6 9 2 3 7 8 1
可得循环基因：1->5->2->4->9->1
用循环的基因构成子代Ａ，顺序与父代Ａ一样
1 2 4 5 9
用父代Ｂ剩余的基因填满子代Ａ：
1 2 6 4 5 3 7 8 9
子代Ｂ的编码同理。（循环基因 5->1->9->4->2->5）
（8）两交换启发交叉(HGA)
两交换启发交叉方法的基本思想如下:
以8个城市的旅行商问题为例：设N个城市为1,2,3,4,5,6,7,8
随机选出一对未匹配的双亲如下:
A = 3 7 2 6 4 8 1 5
B = 4 8 3 2 1 7 5 6
随机选出初始城j=1(位置号),Sj=1(城市号),右转动使1成为两双亲的第一位置城市如下:
A1 = 1 5 3 7 2 6 4 8
B1 = 1 7 5 6 4 8 3 2
O1 = 1 × × × × × × ×
判断因为d(1,5)＞d(1,7)则A1以7为中心右转得如下中间代:
A2 = × 7 2 6 4 8 5 3
B2 = × 7 5 6 4 8 3 2
O2 = 1 7 × × × × × ×
从第2位开始继续重复上述过程
判断因为d(7,5)=d(7,2)则可任选5或2,A2以5为中心右转得如下中间代:
A3 = × 7 5 3 2 6 4 8
B3 = × 7 5 6 4 8 3 2
O3 = 1 7 5 × × × × ×
如此反复得出
O = 1 7 5 3 2 6 4 8
（9）三交换启发交叉(THGA)（源代码中使用类似此方法）
三交换启发交叉方法的基本思想如下:
选3个参加交配的染色体作为父代,以8个城市为例来说明这一过程,其中dij由前面的表1给出,父代染色体为
A ＝ 3 2 1 4 8 7 6 5
B ＝ 2 4 6 8 1 3 5 7
C ＝ 8 7 5 6 4 3 2 1
SUM1＝42,SUM2＝40,SUM3＝46(SUM1，SUM2，SUM3分别为这3种排法所走的距离总和数).
随机选出初始城市j=1,Sj=3右转动，使3成为3父代的第1位置.
A ＝ 3 2 1 4 8 7 6 5
B ＝ 3 5 7 2 4 6 8 1
C ＝ 3 2 1 8 7 5 6 4
由于d(3,2)＞d(3,5),所以有:
A ＝ × 5 2 1 4 8 7 6
B ＝ × 5 7 2 4 6 8 1
C ＝ × 5 6 4 2 1 8 7
由此规则计算可得:
O ＝ 3 5 7 6 8 4 2 1
5、变异变异是指依据变异概率将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。GA中的变异运算是产生新个体的辅助方法，它决定了GA的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。
注：变异概率Pm不能太小，这样降低全局搜索能力；也不能太大，Pm > 0.5，这时GA退化为随机搜索。
（1）基本位变异算子（用于二进制编码）
基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。
变异前：
000001110000000010000
变异后：
000001110001000010000
（2）逆转变异算子（用于互换编码）（源代码中使用类似此方法）
在个体中随机挑选两个逆转点，再将两个逆转点间的基因交换。
变异前：
1346798205
变异后：
1246798305
GA运行时选择的参数应该视解决的具体问题而定，到目前为止，还没有一个适用于GA所有应用领域的关于算法参数的理论。下面是一般情况下使用GA时推荐的参数：
（1）交叉率
交叉率一般来说应该比较大，推荐使用80％-95％。
（2）变异率
变异率一般来说应该比较小，一般使用0.5％-1％最好。
（3）种群的规模
种群规模指的是群体中个体的个数。实验发现，比较大的种群的规模并不能优化遗传算法的结果。种群的大小推荐使用20-30，一些研究表明，种群规模的大小取决于编码的方法，具体的说就是编码串（Encoded String）的大小。也就是说，如果说采用32位为基因编码的时候种群的规模大小最好为32的话，那么当采用16位为基因编码时种群的规模相应应变为原来的两倍。
（4）遗传运算的终止进化代数
