简述
在一个种群繁衍的过程中，存在着自然选择，交配繁衍，基因突变等生物进化过程，遗传算法便是模拟这样的一个过程。与上面进化过程相对应的一个数据集在每一次迭代过程中都要经过选择操作，交换操作，突变操作。通过模式定理和积木块假设可以证明算法有获得最优解的可能性，以及有能力获得最优解。
基础理论
选择操作
在生物进化的过程中，一个种群中会受到自然选择的作用从而达到优胜略汰。在遗传算法中，选择操作便是一个淘汰过程。它可很直接的选择适应度前50%的个体，也可以按照个体适应值的占比有概率的选择，书中介绍的选择算法是轮盘赌算法
轮盘赌算法
即如图所示，一个个体数为10的种群，上面是随机生成的分块，下面是种群中个体适应值占总适应值的比重，且总和均为1。
轮盘赌的算法如下（类python的一种伪代码）：
gen_index, p_index, a_index = 0
p_sum = p[p_index]
a_sum = a[a_index]
while gen_index < length:
if p_sum <= a_sum:
new_gen[gen_index++] = old_gen[a_index]
p_sum += p[++p_index]
else:
a_sum += a[++a_index]
依照算法一轮下来，新的一代个体分别是{a2，a3，a5，a6，a6，a7，a8，a9，a10，a10}，其中a1和a4因为个体适应度太小被淘汰掉了。
交叉操作
基于概率的两个个体的基因交换
举个例子两个个体为a1 = [2, 3, 5, 6, 7], a2=[1, 4, 5, 6, 8]
a1_index, a2_index = 0
pc = 0.2 ##交叉概率
for i in len(a1):
for j in len(a2):
if rand < pc:
swap(a1[i], a2[j])
选择操作需要注意特定问题的个体特性，如旅行商问题就是一个不能重复的数组，那么交叉操作就需要成对进行。交叉不一定是两个相邻的个体进行的，也可以指定特定个体（如当前适应度最优个体），与其他个体交换。
变异操作
基于概率的个体的基因随机变化
举例个体为a=[1, 2, 3, 4, 5]
pm = 0.1
for i in len(a):
if rand < pm:
a[i] = randint(lower_bound, upper_bound)
模式定理
模式定义：模式是描述种群在位串的某些确定位置上具有相似性质的位串子集的相似性模板
模式阶定义：模式H中确定位置的个数称作该模式的模式阶，记作O(H)
定义距定义：模式H第一个确定位置和最后一个确定位置的距离为定义距，记作D(H)
模式定理：在遗传算法选择、交叉和变异算子的作用下，具有低阶、短定义距、并且其平均适应度高于种群平均适应度的模式在子代中将呈指数级增长。
举例说明：一个种群中的个体是由{0，1，*}构成,0和1是具体的数值，*表示为通配符，那么0100，01**，00**等都可以表示为模式，0100的模式阶就为4，01**的模式阶就为2，0100的定义距为4，01**的定义距为2。
现在假如一个初始种群的有两个个体{00000000，11111111} ，在经过遗传计算（淘汰先不管）后，种群改为{00001111，11110000，00000000，11111111}这时候就会明显发现，00000000这种长定义距的模式只有一个，0000****这种较低阶的，且定义距短的模式有两个，在经过n次遗传计算后，种群中形如这样的0*******一阶定义距为1模式将会是数量最多的，那么基于这些模式就有可能组成最优解，这也是最优解产生的必要条件。（ps:肯定有具体的证明过程了，这只是一个初步的理解xp）
积木块假设
积木块：具有低阶、短定义距的模式以及高水平的模式
积木块假设：个体的积木块通过选择、交叉、变异等遗传算子的作用，能够结合在一起形成高阶，长距、高适应度的个体代码串
这也不难理解，多种模式的个体，可以相互结合形成，特定的个体，这也就说明了，遗传算法是有能力形成最优解的
遗传算法流程
- 初始化：随机生成种群NP，迭代计数器g = 0
- 个体评价：计算种群中个体的适应度
- 遗传运算：选择运算 交叉运算 变异运算
- 终止条件判断：g > G 停止计算，输出结果；g < G，g++
遗传算法的缺点
具体的收敛速度什么的没找到具体数据，我水平又一般，复杂算法就不太会分析了，只知道他是可以收敛的。但是做了几道题之后发现，遗传算法容易提前收敛，遗传运算过程中种群多样性变低，再想进化的话，完全靠变异，也就是被困在局部最优解。
网友评论