软计算课件遗传算法ga-pengjing.pptx

软计算专题1：遗传算法;参考书目;遗传算法起源;提纲;一、遗传算法概述 ——问题的提出 ;微分法求 f(x) 最大值 显然，上式有无穷多个解。 i为奇数时，xi对应局部极大值点，i为偶数时，xi对应局部极小值点。;区间 [-1,2]内最大值为x19 ;问题的解决——智能优化算法;常用的智能优化算法（1）;常用的智能优化算法（2）;常用的智能优化算法（3）;遗传算法的有哪些信誉好的足球投注网站机制 ;;基本遗传算法（SGA）的组成 ;编码;SGA对于本例的编码 ;几个术语 ; SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。 ;适应度函数 ; 遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。 ;轮盘赌选择方法;轮盘赌选择方法的实现步骤;交叉算子 ;单点交叉运算 ;变异算子 ;基本位变异算子;基本位变异算子的执行过程 ;运行参数 ;基本遗传算法（SGA）的框图 ;问题：求下述二元函数的最大值 求最大值？;;3、遗传算法的特点 ;二、遗传算法原理;1、遗传算法的数学基础;模式; ; 遗传算法中串的运算实际上是模式的运算。如果各个串的每一位按等概率生成0或1，则模式为n的种群模式种类总数的期望值为： 如果独立的考虑种群中的各个串，则仅能得到n条信息，然而当把适应值与各个串结合考虑，发掘串群体的相似点，就可得到大量的信息来帮助指导有哪些信誉好的足球投注网站，相似点的大量信息包含在规模不大的种群中。;种群最多可以同时处理 个模式 例：一个个体（种群中只有一个），父个体011 要通过变异变为子个体001，其可能影响的模式为： 被处理的模式总数为8个，8=1*23;两个定义;模式的阶和定义距的含义;模式定理;当采用非重叠的n个串的种群替代种群A(t),可以得到下式： 其中： ，表示在t 时模式H的平均适应度 若用 表示种群平均适应度，则前式可表示为：;上式表明：一个特定的模式按照???平均适应度值与种群的平均适应度值之间的比率生长，换句话说就是：那些适应度值高于种群平均适应度值的模式，在下一代中将会有更多的代表串处于A(t+1)中，因为在 时有 m(H,t+1)m(H,t)。 假设从t=0开始，某一特定模式适应度值保持在种群平均适应度值以上 ，c为常数c0, 则模式选择生长方程为： 上式表明，在种群平均值以上（以下）的模式将按指数增长（衰减）的方式被复制。;例：对串A分别在下面指定点上与H1模式和H2模式进行交叉 A 0111000 H1 *1****0 (被破坏概率： ；生存率：1/6) H2 ***10** (被破坏概率： ；生存率：5/6) 显然A与H1交叉后， H1被破坏，而与H2交叉时， H2不被破坏。 一般地有：模式H被破坏的概率为 ，故交叉后模式H生存的概率为 （l:串长；δ（H）：模式H的定义阶）;考虑到交叉本身是以随机方式进行的，即以概率Pc进行交叉，故对于模式H的生存概率Pc可用下式表示： 同时考虑选择交叉操作对模式的影响，（选择交叉互相独立不影响）则子代模式的估计： 上式表明模式增长和衰减依赖于两个因素：一是模式的适应度值f(H)与平均适应度值的相对大小；另一个是模式定义阶的大小（当Pc一定， L一定时）。;变异操作是以概率Pm随机地改变一个位上的值，为了使得模式H可以生存下来，所有特定的位必须存活。因为单个等位基因存活的概率为（1-Pm）,并且由于每次变异都是统计独立的，因此，当模式H中O(H)个确定位都存活时，这时模式H才能被保留下来，存活概率为： （为0.01以下） 上式表明O(H)个定位值没有被变异的概率。;由此我们可得到： ：在t+1代种群中存在模式H的个体数目 ：在t代种群中存在模式H的个体数目 ：在t代种群中包含模式H的个体平均适应度 ：t代种群中所有个体的平均适应度 ：个体长度 ：交叉概率 ：变异概率 对于k点交叉时，上式可表示为：;模式定理;积木块假设 ;模式定理的缺点;2、遗传机制的几何表示;问题？;3. Walsh模式变换（一种平均适应度函数）;Walsh函数;例：l=3的Walsh函数的计算;Walsh函数离散值计算。0，1;Walsh函数的正交性 定