2021年遗传算法.ppt

遗传算法定义（1/2）
遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。
遗传算法
2021/1/15
1
遗传算法定义(2/2)
因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。
遗传算法
2021/1/15
2
遗传算法共同特征
遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。搜索算法的共同特征为：
　　① 首先组成一组候选解；
　　② 依据某些适应性条件测算这些候选解的适应度；
　　③ 根据适应度保留某些候选解，放弃其他候选解；
　　④ 对保留的候选解进行某些操作，生成新的候选解。
遗传算法
2021/1/15
3
遗传算法工作过程
首先，确定一种编码方法。将问题的任何一个潜在可行解能够编码表示成为一个“数字”染色体。
创建一个由随机的染色体（不同的候选解）组成的初始群体，并以强适应性为目的培育后代个体，进行进化。
进化过程中要加入少量变异。
直到找到解或者无法进化。
遗传算法
2021/1/15
4
遗传算法结果
可能最终收敛到最优解
可能得到的不是最优解
也可能得不到解
遗传算法
2021/1/15
5
遗传算法
1）检查每个染色体，看它解决问题的性能怎样，并相应的为它分配一个适应性分数。
2）从当前群体选出2个成员，选出的概率正比于染色体的适应性，适应分愈高，被选中的概率愈大。常用方法是赌轮选择法（roulette wheel selection）
3）按照预先设定的杂交率（crossover rate），从每个选中染色体一个随机确定的点上进行杂交（crossover）
4）按照预定的变异率（mutation rate），通过对被选染色体的位的循环，把相应的位实行翻转（flip）
5）重复2，3，4步，直到新的群体被创建出来。
遗传算法
2021/1/15
6
算法说明：
把包含5步的一次循环称为一个世代或代（generation）
把整个循环称为一个时代（epoch）
可行解用二进制位进行编码。每个染色体是一组随机的二进制位。二进制位长度在整个群体中一样。例如：
011100110**********
通过译码就代表当前问题的一个解。初始群体通常情况比较糟。
遗传算法
2021/1/15
7
遗传算法的核心
选择：
　　根据各个个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下 一代群体P(t+1)中；
交叉：
　　将群体P(t)内的各个个体随机搭配成对，对每一对个体，以某个概率(称为交叉概率）交换它们之间的部分染色体；
变异：
对群体P(t)中的每一个个体，以某一概率(称为变异概率)改变某一个或某一些基因座上的基因值为其他基因值。
遗传算法
2021/1/15
8
赌轮选择法
染色体被选中的几率和它们的适应性分数成比例，适应性分数越高的染色体，被选中的概率也越大。
但不保证适应性分数最高的染色体成员一定能选入下一代，仅说明它有最大的概率被选中。
全体成员的适应性分数由一张类似于赌博所用的转轮形状饼图来表示
遗传算法
2021/1/15
9
每个染色体按适应性分数分得相应的一个扇区，适应性分数越高，所占区域面积越大。
旋转***，并把一个小球抛入其中，直到***停止时，看小球停在哪一部分，就选中它对应的那个染色体。
遗传算法
2021/1/15
10