lecture05_遗传算法简介.ppt

1、遗传算法简介,数学与计算机科学系 2009,关于优化方法,比较：,传统的优化方法,1、依赖于初始条件； 2、与求解空间有紧密关系，促使较快地收敛到局部 解，但同时对解域有约束，如可微或连续。利用 这些约束，收敛速度快； 3、有些方法，直接依赖至少一阶导数；共轭梯度法 隐含地依赖于梯度。,传统的优化方法（局部优化）：导数法、单纯形方法等； 全局优化方法：漫步法、模拟退火法、GA。,全局优化方法,1、不依赖于初始条件； 2、不与求解空间有紧密关系，对解域，无可微或连续的要求。求解稳健，但收敛速度慢。能获得全局最优。适合于求解空间不知的情况。,比较：,遗传算法,遗传算法简称GA (Genetic A

2、lgorithm)遗传算法是受达尔文的生物进化论的影响并与计算机相结合产生的一种全局的模糊优化算法，很适合于解决传统搜索算法难以解决的问题，包括多变量复杂的问题、非线性问题等。 遗传算法首次出现在20世纪50年代末60年代初，以1968年提出的模式定理为基础，于1975年正式确立。它虽然经过一次蓬勃发展时期，期间有两本分别由美国伊利诺大学的和著的著作问世同时更多的国际会议也出现了，但目前它还处于年轻时代，仍需要学者们的深入学习与推广。,遗传算法的特点,1、遗传算法从问题解的中集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入

3、局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优； 2、遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题；,3、遗传算法有极强的容错能力。遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力； 4、遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。这说明遗传算法是采用随机方法进行最优解搜索，

4、选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖； 5、遗传算法具有隐含的并行性。,遗传算法的特点, 选择算子 交换算子 变异算子,遗传算法的基本算子,遗传算法基本原理,模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量染色体，向量的每个元素称为基因。通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。,选择算子：从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交换、变异，产生新的染色体作准备。,方法：适应度比例法（轮盘赌选择法）、精英法、竞争法； 按各染色体适应度大小比例来决定其被选择数目的多少。 某染色体被

5、选的概率Pc：,xi 为种群中第i个染色体。,具体步骤,1、计算各染色体适应度值； 2、累计所有染色体适应度值，记录中间累加值S - mid 和最 后累加值 sum = f (xi)； 3、产生一个随机数 N，0 N sum； 4、选择对应中间累加值S - mid 的第一个染色体进入交换集 5、重复3和4，直到获得足够的染色体。,染色体的 适应度和所占的比例,用转轮方法 进行选择,例1： 有6个染色体的二进制编码、适应度值、Pc累计值。,适应度/50,染色体被选的概率,被选的染色体个数,例：10个染色体种群按比例的选择过程,交换算子,方法：随机选择二个染色体(双亲染色体)，随机指定一点或多点，

6、进行交换，可得二个新的染色体(子辈染色体)。,子辈染色体：染色体 A 11010001 染色体 B 01011110,复制不能创新，交换解决染色体的创新,变异算子,模拟生物在自然界环境变化，引起基因的突变。在染色体二进制编码中，1变成0，或0变成1。突变产生染色体的多样性，避免进化中早期成熟，陷入局部极值点，突变的概率很低。,GA的流程,简单遗传算法的基本参数,种群规模 n：参与进化的染色体总数，一般为30160， n太小时难以求出最优解，太大则增长收敛时间 ； 代沟G：二代之间不相同的染色体数目比，无重叠时， G = 1；有重叠时， 0 G 1； 选择方法：轮盘赌法、精英选择法、竞争法； 交

7、换率：Pc 一般为0.250.75， Pc太小时难以向前搜索， 太大则容易破坏高适应值的结构 ； 变异率：Pm 一般为0.010.2， Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索 ；,初始种群和它的适应度值,例:,变异率取0.001,染色体的交换算子,2个,例：,步骤1）编码：确定二进制的位数；组成个体（染色体）,对于例子，自变量 x 和 y 取值范围都在08之间， 所以，qmax = 8，qmin=0,步骤2）选择种群数n 和初始个体，计算适应度值，n = 20；,步骤3）确定选择方法；交换率PC；变异率Pm。 选择方法用竞争法； PC = 0.7, Pm = 0.05

8、,计算结果： 8代后，f ( x,y ) =0.998757, 41代后，f ( x,y ) =1.00000, x =3.000290, y =2.999924. 160次适应度计算，达到最优值。,图式定理,(1) 图式概念：一个基因串用符号集0, 1, *表示，则称为一个因式；其中*可以是 0 或1。例如：H=1*0*是一个图式。 (2) 图式的阶和长度：图式中0和1的个数称为图式的阶，并用 O(H)表示。图式中第1位符号和最后位符号间的距离称为图式的长度，并用(H)表示。,遗传算法的理论基础,（*为通配符）,图式定理的推导,、图式在选择过程中的增加。,经过选择,在 t +1代,图式 H 的数量m (H,t +1)为：,图式在交换中的破坏,图式在变异中的破坏,图式定理,图式定理：在选择、交换、变异的作用下，阶次低、定义长度短、适应度高的图式（模块）将按指数增长的规律，一代一代地增长。,经过选择、交换、变异后在 t +1中，图式H的数量：,图式定理,遗传算法在应用中的一些基本问题,1）知识的编码：二进制和十进制的比较，二进制有更多图式和