遗传算法GeneticAlgorithm课件

1、遗传算法课件,遗传算法：Genetic Algorithm,遗传算法,一、概述 二、GA的工过程 三、GA的基本操作 四、模式定理,一、概述,由美国J.Holland提出，搜索不依赖于梯度信息。 解析法：连续导数存在。 优化问题： 枚举法：指数爆炸。 随机法：模拟还火、GA,一、概述,GA的特点： GA是对参数的编码进行操作，而不是对参数本身。 GA是从许多初始点开始并行操作，而不是一个点开始， 防止搜索过程收敛于局部最优解，而且有较大的可能求得 全局最优解。 GA通过目标函数计算适配值，不需要其它的推导对问题 的依赖性较少。 GA使用概率的转变规则，而不是确定性的规则。 GA是一种启发式搜索

2、。 GA对寻优的函数基本无限制，不要求连续可导。 GA只有并行计算的特点，提高适度。 GA更适合大规模复杂问题的优化,遗传算法,一、概述 二、GA的工过程 三、GA的基本操作 四、模式定理,二、GA的工过程,遗传算法,一、概述 二、GA的工过程 三、GA的基本操作 四、模式定理,三、GA的基本操作,复制（reproduction） 交叉（crossover） 变异（mutation） 例： 整数，五位二进制编码： 种串,三、GA的基本操作,复制,三、GA的基本操作,复制后： 3号被淘汰 交叉：在0,1产生随机数r，若 则该串参加交叉操 作，如此选出参加交叉的一组后，随机配对。 交叉概率。 设串

3、的长度为l，且l个数字位之间的空隙为1，2，l-1。在l，l-1的范围内，随机地选取一个整数值k。则将两个父母串中从位置K到串末尾的字串相互换，而形成两个新串,三、GA的基本操作,例如在表4.2中的两个初始配对个体位串为A1和A2： A1=01101 A2=11000 位串的字符长度l=5，假定在1和4之间随机选取一个值k(k=4，如分隔符“”所示)，经交叉操作后产生了两个新的字符串，即,三、GA的基本操作,一般的交叉操作过程可用图4.2所示的方式进行。 图4.2 交叉操作 遗传算法的有效性主要来自复制和交叉操作，尤其是交叉 在遗传算法中起着核心的作用。比如，人们在社会生活中的思 想交流、学术

4、交流、多学科交汇形成的交叉学科等,三、GA的基本操作,本质上都是观念和思想上的交叉，而这种交叉是富于成果 的。新的思想、观念、发明或发现正是来源于此。若把一个位 串看成一个完整的思想，则这个位串上的不同位置中的不同的 值的众多有效的排列组合，形成了一套表达思想的观点。位串 交叉就相应于不同观念的重新组合，而新思想就是在这种重新 组合中产生的，遗传搜索的威力也正在于此。 表4.3列出了交叉操作之后的结果数据。从表4.3中可以看 出交叉操作的具体过程。首先随机地将匹配池中的个体配对， 位串1和位串2配对，位串3和位串4配对；然后，随机地选取交 叉点，设位串1(01101)和位串2(11000)的交

5、叉点为k=4，二者 只交换最后一位，从而生成两个新的位串,即 (01100)和(11001) 位串3(11000)和位串4(10011,三、GA的基本操作,交叉点为k=2，二者交换后三位。结果生成两个新的位串，即 (11011)和 (10000,表4. 交叉操作之后的各项数据,三、GA的基本操作,变异：对每一串中的每一位产生0,1间的随机数 r，若rpm,，则该位变异，pm:变异概率。 变异是以很少的概率随机地改变一个串位值，由10，01。 变异概率很小： pm=0.001,遗传算法,一、概述 二、GA的工过程 三、GA的基本操作 四、模式定理,四、模式定理,模式：基于三值字符集0，1，所产生

6、的能描述某 些结构的相似性的0，1字符串的字符串集的 字符串称为模式。 0，1 模式 000110001 00001 10 01000 01010 01100 01110 11000 11010 11100 11110,四、模式定理,模式阶：模式H中确定位置的个数称为该模式的阶，记 011*1* 阶=4 0* 阶=1 模式长度：模式H第一个和最后一个确定位之间的距离， 记 。 1、复制对模式的影响 t时刻，种群A(t)包含有m个特定模式H，记为m=m(H，t) 在复制过程中,A(t)中的任何一个位串Ai以概率 被选中 并进行复制。因此在t+1时刻,四、模式定理,特定模式H的数量为： （n群体大小 ） 假设模式H的平均适应度高于群体平均适应度且设高出部 分为 ， c为常数,四、模式定理,则：从t=0开始 2、交叉对模式的影响： 破坏概率,四、模式定理,存活概率： 考虑交叉概率Pc 则 综合考虑,四、模式定理,3、变异对模式的影响： 变异是对串中的单个位置以概率pm进