第6章 遗传算法及其应用

人工智能原理及应用第6章进化算法PrinciplesandApplicationsofArtificialIntelligence问题求解策略问题求解：解空间搜索解的表示形式搜索的策略问题求解策略构造式求解:从部分解逐步构造出完整解确定性算法:穷举、动态规划、分支限界…

ABCDCDEEDECECD常常面临组合爆炸问题求解策略构造式求解:从部分解逐步构造出完整解确定性算法:穷举、动态规划、分支限界…

非确定性算法:近似算法、概率算法…

ABCDCDEEDECECD问题求解策略进化式求解:对完整解进行不断改进独立进化:禁忌搜索ABCDEAACBDEA问题求解策略进化式求解:对完整解进行不断改进独立进化:禁忌搜索群体进化:遗传算法、差分进化、粒子群优化…

大多数进化算法属于非确定性算法ABCDEAABCEDAACEDBAACEBDA问题求解策略启发式算法利用问题领域知识:领域相关利用一般性启发信息:领域独立元启发算法问题求解策略启发式算法示例:蚁群优化算法基本思想:模拟蚁群在寻找食物过程中发现路径的行为信息素:蚂蚁会优先选择信息素浓度较大的路径信息素挥发ABCDE。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。群体智能高等智能群体智能高等智能低等智能群体智能高等智能低等智能群体智能高等智能低等智能群智能(涌现智能)群体智能高等智能低等智能群智能(涌现智能)群体智能粒子群优化蚁群优化蜂群优化鱼群优化…问题求解策略构造式求解:从部分解逐步构造出完整解进化式求解:对已有的完整解不断进行改进(进化)借鉴仿生学的思想，模拟自然界的进化思想来求解工程优化问题问题求解策略优化问题组合优化问题连续优化问题“任何控制与决策问题本质上均可归结为优化问题。”——Yu-ChiHo遗传算法的基本概念遗传算法中的基本思想借鉴自然进化中“适者生存、优胜劣汰”的规律，对一组个体（解）进行不断演化，最终得到问题的最优解或近似最优解。遗传算法的基本概念遗传算法的生物学背景染色体：DNA中的主要遗传物质基因：构成染色体的基本元素，能够决定个体的某些特征个体：性状由染色体决定适应度：表示个体对环境的适应程度种群：个体的集合遗传算法的基本概念遗传算法的建模思想染色体(个体)

优化问题的解基因

解向量的组成元素适应度

解的优劣程度种群

问题的一组解集遗传算法的基本概念遗传算法中的建模思想编码:问题的解

染色体解码:染色体

问题的解适应度函数设计遗传算法的基本概念遗传算法中的基本操作选择:从当前群体中选取较优的个体准备进化遗传算法的基本概念选择(selection):适应度越高的个体被选中的概率越大轮盘赌遗传算法的基本概念选择(selection):适应度越高的个体被选中的概率越大轮盘赌锦标赛Elitism策略遗传算法的基本概念遗传算法中的基本操作选择:从当前群体中选取较优的个体准备进化交叉:将父代染色体按一定方式组合生成子代染色体遗传算法的基本概念交叉(crossover):将父代的优秀基因遗传到子代单点交叉01101011001111000110110000110111遗传算法的基本概念交叉(crossover):将父代的优秀基因遗传到子代单点交叉双点交叉01101011001111000111000011101011遗传算法的基本概念交叉(crossover):将父代的优秀基因遗传到子代单点交叉双点交叉多点交叉遗传算法的基本概念遗传算法中的基本操作选择:从当前群体中选取较优的个体准备进化交叉:将父代染色体按一定方式组合生成子代染色体变异:染色体的基因按一定概率发生变化遗传算法的基本概念变异(mutation):引入新的特征位点变异逆转变异互换变异移动变异遗传算法的基本概念遗传算法的一般步骤选择交叉变异适应度评估初始化种群终止？输出最优解YN选择交叉变异遗传算法的应用遗传算法应用示例:背包问题适应度评估初始化种群终止？输出最优解YN选择交叉变异背包容量:35物品重量:10,12,8,7,6,8物品价值:15,13,12,9,8,7110000(28)011000(25)001100(21)000110(17)110000(28)011000(25)110100(37)001000(12)011010(33)110010(36)011100(34)110100(37)110000(28)011110(42)110110(45)011100(34)110110(45)011010(33)遗传算法的应用约束处理不选择违反约束的解惩罚函数:f(x)=v(x)-

(x)修补策略适应度评估初始化种群终止？输出最优解YN选择交叉变异背包容量:35物品重量:10,12,8,7,6,8物品价值:15,13,12,9,8,7遗传算法的应用遗传算法应用示例:旅行商问题编码:节点序列交叉,变异:保持解的有效性47861461532321543546787853212678遗传算法的应用遗传算法应用示例:旅行商问题编码:节点序列交叉,变异:保持解的有效性4582163736487521部分匹配交叉(PMX)4786153232154678遗传算法的应用遗传算法应用示例:旅行商问题编码:节点序列交叉,变异:保持解的有效性478XX53X321X46XX顺序交叉(OX)8XX47X532XX43X168214765327843516遗传算法的应用遗传算法应用示例:旅行商问题编码:节点序列交叉,变异: