遗传算法及应用6.1遗传算法的原理与特点6.1.1遗传算法的基本原理6.1.1遗传算法的基本原理6.1.1遗传算法的基本原理6.1.1遗传算法的基本原理6.1.2遗传算法的特点函数优化组合优化生产调度自动控制机器人学图像处理机器视觉6.2遗传算法的基本操作与模式理论6.2.1.1复制操作种群的初始串及对应的适配度经复制后的新的种群为01101110001100010011串1被复制了一次串2被复制了两次串3被淘汰串4也被复制了一次种群的初始串及对应的适配度交叉(Crossover)操作可分为两步：第一步—将新复制产生的匹配池中的成员随机两两匹配。第二步—进行交叉繁殖。设串的长度为l，则串的l个数字位之间的空隙标记为1，2，…，l-１。随机地从[1，l-1]中选取一整数位置k，则将两个父母串中从位置k到串末尾的子串互相交换，而形成两个新串。本例中初始种群的两个个体假定从１到４间选取随机数，得到k＝４，那么经过交叉操作之后将得到如下两个新串新串号变异(Mutation)是以很小的概率随机地改变一个串位的值。变异的概率通常是很小的，一般只有千分之几。变异操作相对于复制和交叉操作而言，是处于相对次要的地位，其目的是为了防止丢失一些有用的遗传因子，变异操作可以起到恢复串位多样性的作用。在经过一次复制、交叉和变异操作后，最优的和平均的目标函数值均有所提高。种群的平均适配度从293增至439，最大的适配度从575增至729。可见每经过这祥的一次遗传算法步骤，问题的解便朝着最优解方向前进了一步。编码初始种群生成适应度评价遗传算子选择运算交叉运算变异运算基本遗传算法的运行参数种群大小、进化代数、交叉概率、变异概率6.2.1遗传算法的基本操作6.2.1遗传算法的基本操作编码二进制编码的特点1）编码、解码操作简单2）交叉、变异等遗传操作便于实现；3）便于利用模式定理对算法进行理论分析4）对于连续问题局部搜索能力差编码-格雷码编码方法编码-格雷码编码方法二进制编码存在的问题1）连续空间离散化带来的误差；举例：用二进制编码处理100个决策变量的优化问题，每个变量的取值范围为[-100,100],要求精确到小数点后5位，每个决策变量需要的二进制编码位数为？浮点数编码个体的每个基因值用某一范围内的一个浮点数来表示，个体的编码长度等于其决策变量的个数。举例：有一个5个决策变量的优化问题，一个基因型为：X=[5.2，2.6,3.5,6.8,9.0]T6.2.1遗传算法的基本操作初始种群的产生适应度评价适应度评价适应度尺度变换线性尺度变换乘幂尺度变换6.2.1遗传算法的基本操作6.2.1遗传算法的基本操作6.2.1遗传算法的基本操作6.2.1遗传算法的基本操作随机遍历抽样法:为需要选择的个体数目等距离的选择个体.6.2.1遗传算法的基本操作6.2.1遗传算法的基本操作6.2.1遗传算法的基本操作6.2.1遗传算法的基本操作交叉操作：遗传算法中的交叉运算是指两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉概率的选择并不是配对后的染色体对一定会交叉。操作时只有随机数大于交叉概率的个体才进行交叉。交叉概率选择原则：1）不要太多破坏个体编码串中优良性状个体模式。2）能有效产生一些新个体。单点交叉：随机设置一个交叉点，交换自交叉点到编码串尾部的染色体。双点交叉：随机产生两个交叉点；交叉两个随机点之间的部分染色体多点交叉均匀交叉：每个基因座上的个体都以相同的概率进行交换形成新的个体。算数交叉：由两个个体线性组合产生新的个体。变异操作：将个体编码串中的某些基因座上的基因值用该基因座上的其他等位基因来替代，从而形成新的个体。作用：(1)改善遗传算法局部搜索能力(2)维持种群多样性，防止早熟二进制编码的变异操作（个体在变异位上的基因值取反）浮点数编码的变异操作（随机数替换）符号编码的变异操作（随机字符替换）基本位变异：以变异概率Pm随机指定某一位或某几位基因座上的基因值进行变异。01001100——选中第4位——01011100均匀变异：6.2.1遗传算法的基本操作6.2.2遗传算法的模式理论称一个模式与一个特定的串相匹配是指：该模式中的1与串中的1相匹配模式中的0与串中的0相匹配模式中的*可以匹配串中的0或1例如模式00*00匹配两个串：00100，00000模式*11*0匹配四个串：01100，01110，11100，11110对于前面例子中的5位字串，由于模式的每一位可取0、1或*，因此总共有种模式。对一般的问题，若串的基为k，长度为l，则总共有种模式。可见模式的数量要大于串的数量。一般地，一个串中包含种模