遗传算法（genetic algorithm (GA)）是用于解决最优化的搜索算法，是进化算法的一种。遗传算法基于自然选择和遗传学的思想。这是随机搜索的智能化优化，可将搜索引导到解决方案空间中性能更好的区间。其优点是原理和操作简单、通用性强、不受限制条件的约束，全局解搜索能力，而且天生具有并行性，代码很容易放到集群上进行分布式并行处理，它们通常用于优化问题和搜索问题，提供比较有效的解决方案。
遗传算法就是模拟自然选择的过程，物竞天择，适者生存，只有适应环境的种群才能繁殖并进入下一代。简而言之，他们在连续几代人中模拟“适者生存”，以解决问题。每一代都由一群人组成，每个人代表搜索空间和可能解决方案中的一个点。在程序中我们可以用字符串，整数，浮点数或者位来表示每一个人，类似于染色体都是独一无二的解。下面我们一起认识遗传算法的解题思路和几个相关概念。
遗传算法的基本思路是模拟种群染色体的遗传结构和行为，大家想一想动物是怎样择偶的。
（1）个体在有限的资源里面争取资源和交配权力。
（2）那些最强壮的个体（适应者）就有更多交配权，产生更多的后代。我们知道在猩猩，狮子，狼等群居动物，一般只有一只雄性拥有交配权，它也是通过打败其他雄性对手才能做到这个领地的王者。
（3）优秀父母的基因会传播给他们下一代，下一代很有可能超越父母成为更好的后代。
（4）通过这样的方式每一代都会更适合这个生活环境。
染色体怎样表示呢？它和问题的解有什么关系？
每个个体是搜索空间中的一个解，它们会被编码，编码的长度取决于问题的可变成分，因此一条染色体（个体）由几个基因组成，如图所示。
image.png
如何判断哪些是适应者？
当然我们要构建一个适应能力评分函数，计算每一个个体的适用能力，从中挑选最佳适应者。遗传算法可维护n个个体（染色体或问题的一个解）的种群及其适应能力评分，适应能力评分较高的个体比其他个体具有更多的繁殖机会。这些个体通过结合父母的染色体而交配并产生更好的后代。个体总是不变的，因此必须为新生命开辟空间。因此，当上一代的所有交配机会都用尽时，一些个体就会死亡并被新生命代替，最终创造了新一代。算法总是希望在新生代中找到更好的解决方案，同时使最不适合的个体死亡。
一般情况下，每个新一代都比前几代有更多好基因。因此，每个新生代都有比前几代更好的“部分解决方案”。一旦产生的后代与前几代的适应能力没有显着差异，该种群便已经完全适应了这个环境，也就是说该算法已收敛到该问题的一组解决方案了。
怎样模拟种群的繁衍？两个个体基因怎样遗传给下一代？
盘古开天，创建初生代后，然后算法将使用以下操作来模拟演化。
（1）选择操作：挑选优秀适应者（适应能力评分高的个体），让他们将基因传递给后代。一般的遗传算法都有一个交配概率，范围一般是0.6~1，这个交配概率反映两个被选中的个体进行交配的概率。例如，交配概率为0.8，则80%的“夫妻”会生育后代。
（2）交叉操作：模拟个体之间的交配，使用选择操作挑选两个个体，并随机选择交叉位置。然后交换这些交换位置的基因，从而创造出一个全新的个体（后代）。如下图6-26所示，分别挑选两个个体不同部分，组合为一个新个体。
注意：图中红色交换位置是随机产生的，可以是染色体的任意位置，不一定是连续，可以间隔挑选。
（3）突变操作：模拟自然界中的基因突变，在后代中插入随机基因以保持种群的多样性。一般遗传算法都有一个固定的突变常数（又称为变异概率），通常是0.1或者更小，这代表变异发生的概率。根据这个概率，新个体的染色体随机的突变，通常就是改变染色体的一个字节，如图6-27所示。
image.png
遗传算法看上去就像拥有生命的算法，多么神奇，那么它的实际效果如何呢？，什么问题适合使用呢？适应能力评估函数，交配概率，突变概率需要怎样设置？下面我们通过一个具体例子来深入了解。
吊死鬼游戏
有一个小游戏叫吊死鬼游戏（hangman），在我们学习英语的时候，可能都在课堂上玩过。老师给定一个英文单词，同学们就猜是什么单词，猜错一次老师就画一笔，如果把吊死鬼画出来就没有机会猜了，游戏结束。现在我们不限猜测的次数，让电脑也来玩一下，看它要多久才能猜中。
（1）把背景剥离，找出问题核心，简化问题。
对于计算机来说，最简单就是盲目搜索，穷举所有情况，直到猜中为止。这样的穷举算法有兴趣的读者可以尝试用代码实现。这里我们当然要用刚学习的遗传算法，根据前面的介绍的算法思路，结合实际情况，我们来设置几个关键要素。
- 字符从a至z视为基因，由这些字符生成的字符串被认为是染色体（个体），也就是一个解。
- 适应能力得分就是用个体字符串与目标字符串比较，相同位置有相同字符的个数。 因此，具有较高适应值的个体（猜中更多字母的解）将获得更多的繁殖权力。
- 设置种群大小（一代个体的个数），初始种群的数量很重要，如果初始种群数量过多，算法会占用大量系统资源；如果初始种群数量过少，算法很可能忽略掉最优解。这次我们设置种群的数量为100，同一代会有一百个体。
- 设置下一代组成，适应能力前10%直接进入下一代，这称为精英模式，适应能力前50%的个体拥有繁衍权力，则交配概率为50%，也就是必然产生下一代。我们一般取较大的交配概率，因为交配操作可以加快解区间收敛，使解达到最有希望的最佳解区域，但交配概率太高也可能导致过早收敛，则称为早熟，只找到局部最优解就停止进化。还有突变概率，这里设置为0.1，也就是说在组合新一代的每一个基因，有45%来自父亲基因，有45%来自母亲基因，有10%发生变异，随机产生一个基因。
- 终止条件是适应能力值等于单词长度，也就是找到了目标单词。
（2）估算数据规模，算法复杂度
如果用穷举算法，我们可以估算时间复杂度，就是每一个位置尝试一遍26个字母，所以时间复杂度O(26^n)，n为单词的长度。但对于遗传算法来说，这是它的一个缺点，由于太多不确定性，遗传算法的精度、可行度、计算复杂性等方面参数还没有有效的定量分析方法。
（3）动手写代码
import random
GENES = 'abcdefghijklmnopqrstuvwxyz' # 基因
class Individual(object):
'''此类代表种群中的个体'''
def __init__(self, target, chromosome=None):
self.target = target
if chromosome: # 个体染色体，也就是所猜的单词解
self.chromosome = chromosome
else: # 若没有，创建一个随机的染色体
self.chromosome = self.create_gnome()
self.fitness = self.cal_fitness() # 此个体的适用能力值
@classmethod # 修饰符对应的函数不需要实例化，不需要 self 参数，但第一个参数需要是表示自身类的 cls 参数
def mutated_genes(cls):
# 基因突变，也就是从a-z中随机挑选一个字母
global GENES
gene = random.choice(GENES)
return gene
def create_gnome(self):
# 初始化个体基因
gnome_len = len(self.target) # 根据目标单词长度随机构建一个字符串
return [self.mutated_genes() for _ in range(gnome_len)]
def mate(self, parent, mutation=0.1):
# 进行繁衍，产生新一代
pass
def cal_fitness(self):
# 计算适应能力值，记录正确的字符数量
fitness = 0
for gs, gt in zip(self.chromosome, self.target):
if gs == gt: fitness+= 1
return fitness
class GeneticAlgorithm(object):
'''遗传算法'''
def __init__(self, target, population_size=100,
proba_elitism=10, proba_crossover=50,
mutation=0.1, max_generation=100):
pass
def init_population(self):
# 初始化第一代个体
for _ in range(self.population_size):
self.population.append(Individual(self.target))
def main(self):
# 主函数
self.init_population() # 产生第一代个体
# 若没有找到答案，并且没有达到最大进化代数，继续下一代演化
pass
这里有两个类【Individual】是代表个体，【GeneticAlgorithm】是代表遗传算法。【Individual】个体在实例化的时候会先判断是否有染色体，如果没有就通过create_gnome()函数随机生成一个染色体，然后马上通过cal_fitness()函数计算它的适应能力值。mate()函数负责繁衍下一代新个体和mutated_genes()函数负责模拟基因突变。【GeneticAlgorithm】在实例化的时候就要设定遗传算法的各种配置，其中目标单词【target】是必要参数，其他参数是可选参数，都已经设定了默认值。然后通过调用main()函数来启动算法运行，在运算过程中我们把每一代适应能力值最大的个体打印出来，一起观察种群的进化过程。现在通过一些例子来验证算法是否可行。
ga = GeneticAlgorithm('generation')
ga.main()
# ---------结果-----------
ga = GeneticAlgorithm('generation')
第1代 单词: eikehaviro 适应值: 3
第2代 单词: eikehaviro 适应值: 3
第3代 单词: toneibxinn 适应值: 4
第4代 单词: binagavion 适应值: 5
第5代 单词: binagavion 适应值: 5
第6代 单词: emnenahion 适应值: 6
第7代 单词: emnenahion 适应值: 6
第8代 单词: emnenahion 适应值: 6
第9代 单词: ltneratton 适应值: 7
第10代 单词: eenaration 适应值: 8
第11代 单词: eeneration 适应值: 9
第12代 单词: eeneration 适应值: 9
第13代 单词: generation 适应值: 10
从打印在的屏幕的信息中我们看到刚开始的适应能力值非常低，通过不断进化，适应值也逐步上升，到第十三代就找到答案，粗略估算每次100个个体，那么一共尝试了13*100=13000次就找到结果，效果还是不错的。因为遗传算法是具有不定性，当然不可能每次都是在第十三代就能得到结果，大家可以多尝试几次就会知道。同时你们可以尝试调整其他默认参数，看看对结果有什么影响。比如下面，我们测试不同大小种群，看一下有什么变化。
target = 'announcement'
for p in range(100, 1000, 100): # 种群大小，每次增加100
generate = 0
for _ in range(10): # 每一种种群经过10次运算
ga = GeneticAlgorithm(target, population_size=p)
ga.main()
generate += ga.generation # 统计总共经过多少次进化
print('种群数量为%d, 总进化代数为%d, 平均每次通过%.1f进化得到结果' % (p, generate, generate/10))
# ---------结果-----------
种群数量为100, 总进化代数为199, 平均每次通过19.9进化得到结果
种群数量为200, 总进化代数为144, 平均每次通过14.4进化得到结果
种群数量为300, 总进化代数为132, 平均每次通过13.2进化得到结果
种群数量为400, 总进化代数为128, 平均每次通过12.8进化得到结果
种群数量为500, 总进化代数为131, 平均每次通过13.1进化得到结果
种群数量为600, 总进化代数为121, 平均每次通过12.1进化得到结果
种群数量为700, 总进化代数为115, 平均每次通过11.5进化得到结果
种群数量为800, 总进化代数为118, 平均每次通过11.8进化得到结果
种群数量为900, 总进化代数为118, 平均每次通过11.8进化得到结果
从结果我们看到，适当增加种群的个体数量，可以更快地获得结果。对于其他参数，大家都可以通过同样的方法进行测试，以下是其他参数的测试结果汇总到表6-28，每一次只改变一个参数的值，其他参数按默认值。
| 参数 | 数值 | 结果（平均进化代数） |
|---|---|---|
| 突变概率 | 0.1 | 21.6 |
| 突变概率 | 0.15 | 20.4 |
| 突变概率 | 0.2 | 31.2 |
| 突变概率 | 0.25 | 61.7 |
| 突变概率 | 0.3 | 91.3 |
| 突变概率 | 0.35 | 100 |
| 突变概率 | 0.4 | 100 |
| 突变概率 | 0.45 | 100 |
| 繁衍权力 | 10 | 23.3 |
| 繁衍权力 | 20 | 14.6 |
| 繁衍权力 | 30 | 15.5 |
| 繁衍权力 | 40 | 13.9 |
| 繁衍权力 | 50 | 17.7 |
| 繁衍权力 | 60 | 23.1 |
| 繁衍权力 | 70 | 30.2 |
| 繁衍权力 | 80 | 45.4 |
| 繁衍权力 | 90 | 59.5 |
从结果中我们知道，突变概率确实不能太大，越大需要更多次进化，并且在大于0.35就不能求出结果，因为我们设置了最大迭代次数就100。查看繁衍权力这个参数，当它在40时候，也就是种群前40%的个体能够有机会繁衍下一代，得到进化代数结果是最小的。在解决实际问题的时候大家也可以通过这样的调试方式，找到合适的参数值。现在我们再用调试过的参数，种群数是400，突变概率是0.15，繁衍权力是40，重新测试一下，看是否真的能提高效率。
ga = GeneticAlgorithm('generation', population_size=400,
proba_crossover=40, mutation=0.15)
ga.main()
# ---------结果-----------
第1代 单词: uedpwxdkon 适应值: 3
第2代 单词: uedpwxdkon 适应值: 3
第3代 单词: gefzrbvbin 适应值: 4
第4代 单词: gexewgticx 适应值: 5
第5代 单词: oeteravign 适应值: 6
第6代 单词: xeneratijn 适应值: 8
第7代 单词: xeneratijn 适应值: 8
第8代 单词: xeneratijn 适应值: 8
第9代 单词: generation 适应值: 10
看来调优过的参数果然起作用，比刚才少了4代，在第九代就找到答案了。也许这只是一个意外，那么我们来做一个更严谨的测试，同样运行10次，看一下是否真实提高效率。
generate1 = 0
generate2 = 0
for _ in range(10): # 经过10次运算
ga = GeneticAlgorithm(target)
ga.main()
generate1 += ga.generation
ga = GeneticAlgorithm(target, population_size=400, proba_crossover=40, mutation=0.15)
ga.main()
generate2 += ga.generation
print('默认参数：总进化代数为%d, 平均每次通过%.1f进化得到结果' % (generate1, generate1/10))
print('调优参数：总进化代数为%d, 平均每次通过%.1f进化得到结果' % (generate2, generate2 / 10))
# ---------结果-----------
默认参数：总进化代数为148, 平均每次通过14.8进化得到结果
调优参数：总进化代数为101, 平均每次通过10.1进化得到结果
网友评论