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