第四章遗传算法3精选PPT.ppt
( 4.5 )《第四章遗传算法3精选PPT.ppt》由会员分享，可在线阅读，更多相关《第四章遗传算法3精选PPT.ppt（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第四章遗传算法3第1页，此课件共76页哦w教学重点 理解改进的遗传算法 掌握遗传算法解决简单优化问题 掌握遗传算解决简单的STP问题w教学难点 遗传算解决简单的STP问题第2页，此课件共76页哦4.1 遗传算法简介遗传算法简介 4.1.1 4.1.1 遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展遗传算法的产生与发展 4.1.2 4.1.2 生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识生物进化理论和遗传学的基本知识 4.1.3 4.1.3 遗传算法的思路与特点遗传算法的思路与特点遗传算法的思路与特点遗传算法的思路与特点 4.1.4 4
2、.1.4 遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作遗传算法的基本操作 4.1.5 4.1.5 遗传算法的应用遗传算法的应用遗传算法的应用遗传算法的应用 4.2 基本遗传算法基本遗传算法 4.2.1 4.2.1 简单函数优化的实例简单函数优化的实例简单函数优化的实例简单函数优化的实例 4.2.2 4.2.2 遗传基因型遗传基因型遗传基因型遗传基因型 4.2.3 4.2.3 适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换适应度函数及其尺度变换 4.2.4 4.2.4 遗传操作遗传操作遗传操作遗传操作选择选择选择选择 4.2.5 4.2.5 遗传操作遗传操作遗传操作
3、遗传操作交叉交叉交叉交叉/基因重组基因重组基因重组基因重组 4.2.6 4.2.6 遗传操作遗传操作遗传操作遗传操作变异变异变异变异 4.2.7 4.2.7 算法的设计与实现算法的设计与实现算法的设计与实现算法的设计与实现 4.2.8 4.2.8 模式定理模式定理模式定理模式定理 智能优化计算智能优化计算数学与统计学院 2013年 第3页，此课件共76页哦4.3 遗传算法的改进遗传算法的改进 4.3.1 CHC4.3.1 CHC算法算法算法算法 4.3.2 4.3.2 自适应遗传算法自适应遗传算法自适应遗传算法自适应遗传算法 4.3.3 4.3.3 基于小生境技术的遗传算法基于小生境技术的遗传
4、算法基于小生境技术的遗传算法基于小生境技术的遗传算法4.4 遗传算法的应用遗传算法的应用 4.4.1 4.4.1 解决带约束的函数优化问题解决带约束的函数优化问题解决带约束的函数优化问题解决带约束的函数优化问题 4.4.2 4.4.2 解决多目标优化问题解决多目标优化问题解决多目标优化问题解决多目标优化问题 4.4.3 4.4.3 解决组合优化问题解决组合优化问题解决组合优化问题解决组合优化问题 4.4.4 4.4.4 遗传算法在过程建模中的应用遗传算法在过程建模中的应用遗传算法在过程建模中的应用遗传算法在过程建模中的应用 4.4.5 4.4.5 遗传算法在模式识别中的应用遗传算法在模式识别中
5、的应用遗传算法在模式识别中的应用遗传算法在模式识别中的应用智能优化计算智能优化计算数学与统计学院 2013年 第4页，此课件共76页哦4.3 遗传算法的改进遗传算法的改进 智能优化计算智能优化计算数学与统计学院 2013年w改进的途径改进的途径w改变遗传算法的组成成分；改变遗传算法的组成成分；w采用混合遗传算法；采用混合遗传算法；w采用动态自适应技术；采用动态自适应技术；w采用非标准的遗传操作算子；采用非标准的遗传操作算子；w采用并行遗传算法等。采用并行遗传算法等。第5页，此课件共76页哦4.3 遗传算法的改进遗传算法的改进 智能优化计算智能优化计算数学与统计学院 2013年w改进思路改进思路
6、w1991年年Eshelman提出的一种改进遗传算法；提出的一种改进遗传算法；wC：跨世代精英选择（：跨世代精英选择（Cross generational elitist selection）策略；策略；wH：异物种重组（：异物种重组（Heterogeneous recombination）；）；wC：大变异（：大变异（Cataclysmic mutation）。）。4 4.3.1 CHC.3.1 CHC算法算法算法算法 第6页，此课件共76页哦4.3 遗传算法的改进遗传算法的改进 智能优化计算智能优化计算数学与统计学院 2013年w选择选择w上一代种群与通过新的交叉方法产生的个体群混合起上一
7、代种群与通过新的交叉方法产生的个体群混合起来，从中按一定概率选择较优的个体；来，从中按一定概率选择较优的个体；w即使交叉操作产生较劣个体偏多，由于原种群大多数即使交叉操作产生较劣个体偏多，由于原种群大多数个体残留，不会引起个体的评价值降低；个体残留，不会引起个体的评价值降低；w可以更好地保持遗传多样性；可以更好地保持遗传多样性；w排序方法，克服比例适应度计算的尺度问题。排序方法，克服比例适应度计算的尺度问题。4.3.1 CHC.3.1 CHC算法算法算法算法 第7页，此课件共76页哦4.3 遗传算法的改进遗传算法的改进 智能优化计算智能优化计算数学与统计学院 2013年 w交叉交叉w均匀交叉的
8、改进：当两个父个体位值相异的位数为均匀交叉的改进：当两个父个体位值相异的位数为m时，时，从中随机选取从中随机选取m/2个位置，实行父个体位值的交换；个位置，实行父个体位值的交换；w确定一阈值，当个体间距离低于该阈值时，不进行交确定一阈值，当个体间距离低于该阈值时，不进行交叉操作。进化收敛的同时，逐渐地减小该阈值。叉操作。进化收敛的同时，逐渐地减小该阈值。4 4.3.1 CHC.3.1 CHC算法算法算法算法 第8页，此课件共76页哦4.3 遗传算法的改进遗传算法的改进 智能优化计算智能优化计算数学与统计学院 2013年 w变异变异w在进化前期不采取变异操作，当种群进化到一定收敛时在进化前期不采
9、取变异操作，当种群进化到一定收敛时期，从最优个体中选择一部分个体进行初始化；期，从最优个体中选择一部分个体进行初始化；w初始化：选择一定比例（扩散率，一般初始化：选择一定比例（扩散率，一般0.35）的基因）的基因座，随机地决定它们的位值。座，随机地决定它们的位值。4 4.3.1 CHC.3.1 CHC算法算法算法算法 第9页，此课件共76页哦4.3 遗传算法的改进遗传算法的改进 智能优化计算智能优化计算数学与统计学院 2013年 w参数分析参数分析w交叉概率交叉概率Pc和变异概率和变异概率Pm的选择是影响遗传算法行为和的选择是影响遗传算法行为和性能的关键，直接影响算法的收敛性；性能的关键，直接
10、影响算法的收敛性；wPc越大，新个体产生的速度就越快，但过大会使优秀个越大，新个体产生的速度就越快，但过大会使优秀个体的结构很快被破坏；体的结构很快被破坏；Pc过小，搜索过程缓慢，以至停过小，搜索过程缓慢，以至停止不前；止不前；wPm过小，不易产生新个体结构，过小，不易产生新个体结构，Pm过大，变成纯粹的过大，变成纯粹的随机搜索；随机搜索；4 4.3.2 自适应遗传算法自适应遗传算法 第10页，此课件共76页哦4.3 遗传算法的改进遗传算法的改进 智能优化计算智能优化计算数学与统计学院 2013年w自适应策略自适应策略wSrinvivas等提出一种自适应遗传算法，等提出一种自适应遗传算法，Pc
11、和和Pm能够随适能够随适应度自动改变：应度自动改变：w当种群各个体适应度趋于一致或趋于局部最优时，使当种群各个体适应度趋于一致或趋于局部最优时，使Pc和和Pm增加；而当群体适应度比较分散时，使增加；而当群体适应度比较分散时，使Pc和和Pm减减少；少；w对于适应度较高的个体，对应于较低的对于适应度较高的个体，对应于较低的Pc和和Pm；而较低；而较低适应度的个体，对应于较高的适应度的个体，对应于较高的Pc和和Pm。4 4.3.2 自适应遗传算法自适应遗传算法 第11页，此课件共76页哦4.3 遗传算法的改进遗传算法的改进 智能优化计算智能优化计算数学与统计学院 2013年 w自适应方法自适应方法
12、fmax群体中最大的适应度值；群体中最大的适应度值；favg每代群体的平均适应度值；每代群体的平均适应度值；f要交叉的两个个体中较大的适应度值；要交叉的两个个体中较大的适应度值；f要交叉或变异的个体适应度值；要交叉或变异的个体适应度值；4 4.3.2 .3.2 自适应遗传算法自适应遗传算法自适应遗传算法自适应遗传算法 k1、k2、k3、k4取取(0,1)的值的值第12页，此课件共76页哦4.3 遗传算法的改进遗传算法的改进 智能优化计算智能优化计算数学与统计学院 2013年w自适应方法进一步改进自适应方法进一步改进w适用于进化后期，不适于进化前期，因为前期的优秀适用于进化后期，不适于进化前期，
13、因为前期的优秀个体有可能是局部最优点；个体有可能是局部最优点；w使最大适应度个体的交叉概率和变异概率由使最大适应度个体的交叉概率和变异概率由0提高到提高到Pc2和和Pm2；w采用精英选择策略；采用精英选择策略；4.3.2 .3.2 自适应遗传算法自适应遗传算法自适应遗传算法自适应遗传算法 第13页，此课件共76页哦4.3 遗传算法的改进遗传算法的改进 智能优化计算智能优化计算数学与统计学院 2013年 w自适应方法进一步改进自适应方法进一步改进 4 4.3.2 .3.2 自适应遗传算法自适应遗传算法自适应遗传算法自适应遗传算法 第14页，此课件共76页哦4.3 遗传算法的改进遗传算法的改进 智
14、能优化计算智能优化计算数学与统计学院 2013年 w小生境概念小生境概念w小生境（小生境（niche）：生物学中，特定环境中的一种组织）：生物学中，特定环境中的一种组织功能；功能；w在在SGA中，容易中，容易“近亲繁殖近亲繁殖”；wNGA（Niche Generic Algorithm），将每一代个体划分为），将每一代个体划分为若干类，每类选出优秀个体组成一个种群；若干类，每类选出优秀个体组成一个种群；w优势：保持解的多样性，提高全局搜索能力，适合复杂多优势：保持解的多样性，提高全局搜索能力，适合复杂多峰函数的优化。峰函数的优化。4.3.3 基于小生境技术的遗传算法基于小生境技术的遗传算法 第
15、15页，此课件共76页哦4.3 遗传算法的改进遗传算法的改进 智能优化计算智能优化计算数学与统计学院 2013年w选择策略选择策略w预选择机制、排挤机制、分享机制；预选择机制、排挤机制、分享机制；w预选择（预选择（preselection,1970）机制）机制w当子个体的适应度超过其父个体适应度时，子个体才可以当子个体的适应度超过其父个体适应度时，子个体才可以替代父个体，否则父个体仍保留；替代父个体，否则父个体仍保留；w有效维持种群多样性，造就小生境进化环境。有效维持种群多样性，造就小生境进化环境。4 4.3.3 .3.3 基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算
16、法基于小生境技术的遗传算法 第16页，此课件共76页哦4.3 遗传算法的改进遗传算法的改进 智能优化计算智能优化计算数学与统计学院 2013年w排挤（排挤（crowding,1975）机制）机制w设置排挤因子设置排挤因子CF（CF=2或或3），随机选取），随机选取1/CF个个体组成个个体组成排挤成员，排挤与其相似（用距离来度量）的个体；排挤成员，排挤与其相似（用距离来度量）的个体；w个体之间的相似性可用个体编码串之间的海明距离来度量。个体之间的相似性可用个体编码串之间的海明距离来度量。4.3.3 .3.3 基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的
17、遗传算法 第17页，此课件共76页哦4.3 遗传算法的改进遗传算法的改进 智能优化计算智能优化计算数学与统计学院 2013年w共享（共享（sharing,1987）机制）机制w通过个体之间的相似性程度的共享函数来调整各个体通过个体之间的相似性程度的共享函数来调整各个体的适应度；的适应度；w共享函数的目的：将搜索空间的多个峰值在地理上区共享函数的目的：将搜索空间的多个峰值在地理上区分开来，每一个峰值处接受一定比例数目的个体，比分开来，每一个峰值处接受一定比例数目的个体，比例数目与峰值高度有关；例数目与峰值高度有关；4.3.3 .3.3 基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技
18、术的遗传算法基于小生境技术的遗传算法 第18页，此课件共76页哦4.3 遗传算法的改进遗传算法的改进 智能优化计算智能优化计算数学与统计学院 2013年w共享（共享（sharing,1987）机制）机制w共享函数的值越大，表明个体之间越相似，记为共享函数的值越大，表明个体之间越相似，记为Sh(dij)，dij为两个个体为两个个体i和和j之间的距离；之间的距离；share是是niche的半径，由使用者给定。的半径，由使用者给定。4 4.3.3 .3.3 基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法 第19页，此课件共76页哦4.3 遗传算法的改
19、进遗传算法的改进 智能优化计算智能优化计算数学与统计学院 2013年w共享（共享（sharing,1987）机制）机制w共享法将个体的适应度降低，即适应度值共享法将个体的适应度降低，即适应度值fi除以一个除以一个niche计数计数mi：w在距离为在距离为share的范围内的个体彼此削减适应度，这些个的范围内的个体彼此削减适应度，这些个体将收敛在一个体将收敛在一个niche内，避免了整个种群的收敛。内，避免了整个种群的收敛。4 4.3.3 .3.3 基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法基于小生境技术的遗传算法 第20页，此课件共76页哦4.4 遗传算法的应用遗
20、传算法的应用 智能优化计算智能优化计算数学与统计学院 2013年w约束最优化约束最优化问题（问题（Constrained Optimization Problems）的表述的表述 4 4.4.1 .4.1 解决带约束的函数优化问题解决带约束的函数优化问题解决带约束的函数优化问题解决带约束的函数优化问题 第21页，此课件共76页哦4.4 遗传算法的应用遗传算法的应用 智能优化计算智能优化计算数学与统计学院 2013年 w解决途径解决途径w将有约束问题转化为无约束问题（罚函数法，将有约束问题转化为无约束问题（罚函数法，penalty function method），历史较长；），历史较长；w改进
21、无约束问题的方法，使之能用于有约束的情况改进无约束问题的方法，使之能用于有约束的情况（梯度投影算法），发展较晚。（梯度投影算法），发展较晚。w遗传算法解决有约束问题的关键是对约束条件的处理（直遗传算法解决有约束问题的关键是对约束条件的处理（直接按无约束问题处理是接按无约束问题处理是行不通行不通的：随机生成的初始点中可的：随机生成的初始点中可能有大量不可行解；遗传算子作用于可行解后可能产生能有大量不可行解；遗传算子作用于可行解后可能产生不可行解）。不可行解）。4 4.4.1 .4.1 解决带约束的函数优化问题解决带约束的函数优化问题解决带约束的函数优化问题解决带约束的函数优化问题 第22页，此课
22、件共76页哦4.4 遗传算法的应用遗传算法的应用 智能优化计算智能优化计算数学与统计学院 2013年 w一般方法一般方法w罚函数法罚函数法 将罚函数包含到适应度评价中：将罚函数包含到适应度评价中：关键是如何设计罚函数，需要谨慎地在过轻或过重惩罚关键是如何设计罚函数，需要谨慎地在过轻或过重惩罚之间找到平衡，针对不同问题设计罚函数。之间找到平衡，针对不同问题设计罚函数。4.4.1 .4.1 解决带约束的函数优化问题解决带约束的函数优化问题解决带约束的函数优化问题解决带约束的函数优化问题 第23页，此课件共76页哦4.4 遗传算法的应用遗传算法的应用 智能优化计算智能优化计算数学与统计学院 2013
23、年w一般方法一般方法w协同进化遗传算法（协同进化遗传算法（Coevolutionary Genetic Algorithm,1997）以食物链关系、共生关系等为基础的生物进化现象称为协以食物链关系、共生关系等为基础的生物进化现象称为协同进化；同进化；一个种群由问题的解组成，另一个种群由约束组成，两一个种群由问题的解组成，另一个种群由约束组成，两个种群协同进化，较好的解应满足更好的约束，较优的个种群协同进化，较好的解应满足更好的约束，较优的约束则被更多的解所违背。约束则被更多的解所违背。4 4.4.1 解决带约束的函数优化问题解决带约束的函数优化问题 第24页，此课件共76页哦w罚函数法罚函数法
24、w评价函数的构造：评价函数的构造：加法加法 乘法乘法4.4 遗传算法的应用遗传算法的应用 智能优化计算智能优化计算数学与统计学院 2013年 4 4.4.1 .4.1 解决带约束的函数优化问题解决带约束的函数优化问题解决带约束的函数优化问题解决带约束的函数优化问题 第25页，此课件共76页哦w罚函数法罚函数法w罚函数分类：罚函数分类：定量惩罚定量惩罚简单约束问题简单约束问题 变量惩罚变量惩罚复杂约束问题，包含两个部分：复杂约束问题，包含两个部分：可变惩罚率可变惩罚率和违反约束的惩罚量。和违反约束的惩罚量。4.4 遗传算法的应用遗传算法的应用 智能优化计算智能优化计算数学与统计学院 2013年
25、4 4.4.1 .4.1 解决带约束的函数优化问题解决带约束的函数优化问题解决带约束的函数优化问题解决带约束的函数优化问题 违反约束程度违反约束程度随违反约束程度变得严重而增加惩罚压力，随违反约束程度变得严重而增加惩罚压力，静态惩罚；静态惩罚；进化迭代次数进化迭代次数随着进化过程的进展而增加惩罚压力，随着进化过程的进展而增加惩罚压力，动态惩罚。动态惩罚。第26页，此课件共76页哦w罚函数法罚函数法w交叉运算：设父个体为交叉运算：设父个体为x=x1,x2,xn和和y=y1,y2,yn 简单交叉简单交叉 单点算术交叉单点算术交叉 整体算术交叉整体算术交叉 基于方向的交叉：基于方向的交叉：x=r(x
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 第四 遗传 算法 精选 PPT
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
限制150内