遗传算法GeneticAlgorithm.ppt

《遗传算法GeneticAlgorithm.ppt》由会员分享，可在线阅读，更多相关《遗传算法GeneticAlgorithm.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、制，不要求连续可导。GA只有并行计算的特点，提高适度。GA更适合大规模复杂问题的优化。遗传算法一、概述二、GA的工过程三、GA的基本操作四、模式定理 二、GA的工过程 初始种群计算适配值 复制1 交叉 变异 选择 遗传算法一、概述二、GA的工过程三、GA的基本操作四、模式定理 三、GA的基本操作复制（reproduction）交叉（crossover）变异（mutation）n例：整数，五位二进制编码：种串：三、GA的基本操作n复制：编号串适配值占整体的百分数10110116914.421100057649301000645.541001136130.9总计1170100 三、GA的基本操作

3、复制后：3号被淘汰n交叉：在0,1产生随机数r，若 则该串参加交叉操 作，如此选出参加交叉的一组后，随机配对。交叉概率。设串的长度为l，且l个数字位之间的空隙为1，2，l-1。在l，l-1的范围内，随机地选取一个整数值k。则将两个父母串中从位置K到串末尾的字串相互换，而形成两个新串。三、GA的基本操作n例如在表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

5、配对，位串3和位串4配对；然后，随机地选取交叉点，设位串1(01101)和位串2(11000)的交叉点为k=4，二者只交换最后一位，从而生成两个新的位串,即(01100)和(11001)位串3(11000)和位串4(10011)。三、GA的基本操作n交叉点为k=2，二者交换后三位。结果生成两个新的位串，即(11011)和(10000)。表4.交叉操作之后的各项数据新串号复制后的匹配池(“”为交叉点)配对对象(随机选择)交叉点（随机选择)新群体x值f(x)=x21011014011001214421100041100125625311|000211011277294100112100001625

6、6总 计1754平 均439最 大 值729 三、GA的基本操作n变异：对每一串中的每一位产生0,1间的随机数 r，若rpm,，则该位变异，pm:变异概率。变异是以很少的概率随机地改变一个串位值，由10，01。变异概率很小：pm=0.001。遗传算法一、概述二、GA的工过程三、GA的基本操作四、模式定理 四、模式定理n模式：基于三值字符集0，1，所产生的能描述某 些结构的相似性的0，1字符串的字符串集的 字符串称为模式。0，1 模式 000110001 00001 10 01000 01010 01100 01110 11000 11010 11100 11110 四、模式定理模式阶：模式H中

7、确定位置的个数称为该模式的阶，记 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、交叉对模式的影响：破坏概率：四、模式定理n存活概率：n考虑交叉概率Pc 则 n综合考虑 四、模式定理n3、变异对模式的影响：变异是对串中的单个位置以概率pm进行随机变换，对于单位置存活的概率为(1-pm)。特别模式存活概率为：n综合复制、交叉、变异n 模式定理：在遗传算子选择、交叉和变异作用下，具有低阶 短定义长度及高于群体平均适应度的模式在后代 中呈指数增长。