《遗传算法GeneticAlgorithm.ppt》由会员分享，可在线阅读，更多相关《遗传算法GeneticAlgorithm.ppt（22页珍藏版）》请在三一办公上搜索。
1、遗传算法课件,遗传算法：Genetic Algorithm,遗传算法,一、概述二、GA的工过程三、GA的基本操作四、模式定理,一、概述,由美国J.Holland提出，搜索不依赖于梯度信息。解析法：连续导数存在。优化问题：枚举法：指数爆炸。随机法：模拟还火、GA,一、概述,GA的特点：GA是对参数的编码进行操作，而不是对参数本身。GA是从许多初始点开始并行操作，而不是一个点开始，防止搜索过程收敛于局部最优解，而且有较大的可能求得 全局最优解。GA通过目标函数计算适配值，不需要其它的推导对问题 的依赖性较少。GA使用概率的转变规则，而不是确定性的规则。GA是一种启发式搜索。GA对寻优的函数基本无限
2、制，不要求连续可导。GA只有并行计算的特点，提高适度。GA更适合大规模复杂问题的优化。,遗传算法,一、概述二、GA的工过程三、GA的基本操作四、模式定理,二、GA的工过程,遗传算法,一、概述二、GA的工过程三、GA的基本操作四、模式定理,三、GA的基本操作,复制（reproduction）交叉（crossover）变异（mutation）例：整数，五位二进制编码：种串：,三、GA的基本操作,复制：,三、GA的基本操作,复制后：3号被淘汰交叉：在0,1产生随机数r，若 则该串参加交叉操 作，如此选出参加交叉的一组后，随机配对。交叉概率。设串的长度为l，且l个数字位之间的空隙为1，2，l-1。在l
3、，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 交叉操作 遗传算法的有效性主要来自复制和交叉操作，尤其是交叉在遗传算法中起着核心的作用。比如，人们在社会生活中的思想交流、学术交流、多学科交汇形成的交叉学科等。,三、GA的基本操作,本质上
4、都是观念和思想上的交叉，而这种交叉是富于成果的。新的思想、观念、发明或发现正是来源于此。若把一个位串看成一个完整的思想，则这个位串上的不同位置中的不同的值的众多有效的排列组合，形成了一套表达思想的观点。位串交叉就相应于不同观念的重新组合，而新思想就是在这种重新组合中产生的，遗传搜索的威力也正在于此。表4.3列出了交叉操作之后的结果数据。从表4.3中可以看出交叉操作的具体过程。首先随机地将匹配池中的个体配对，位串1和位串2配对，位串3和位串4配对；然后，随机地选取交叉点，设位串1(01101)和位串2(11000)的交叉点为k=4，二者只交换最后一位，从而生成两个新的位串,即(01100)和(1
5、1001)位串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，所产生的能描述某 些结构的相似性的0，1字符串的字符串集的 字符串称为模式。0，1 模式 0001
6、10001 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进行随机变换，对于单位置存活的概率为(1-pm)。特别模式存活概率为：综合复制、交叉、变异 模式定理：在遗传算子选择、交叉和变异作用下，具有低阶 短定义长度及高于群体平均适应度的模式在后代 中呈指数增长。,
