遗传算法与蚁群算法简介概述.ppt

遗传算法与群智能优化算法简介;主要内容;智能优化算法简介;智能优化算法简介 - 问题的NP-完全特性;北京交通大学计算机与信息技术学院;北京交通大学计算机与信息技术学院;北京交通大学计算机与信息技术学院;智能优化算法简介 -常用的智能优化算法;主要内容;遗传算法(Genetic Algorithm);遗传算法-简单遗传算法;北京交通大学计算机与信息技术学院;遗传算法-选择;遗传算法-交叉;遗传算法-交叉（续）;遗传算法-交叉（续）;遗传算法-交叉（续）;遗传算法-交叉（续）;遗传算法-变异;遗传算法-函数优化示例;;交叉过程（假设使用单点交叉，交叉概率pc = 0.95） 位串1、2： 0 1 1 | 0 1 0 1 1 | 0 0 1 1 0 | 0 0 1 1 0 | 0 1 位串2、4： 1 1 0 | 0 0 1 1 0 | 1 1 1 0 0 | 1 1 1 0 0 | 0 0 变异过程（假设变异概率pm = 0.05，且此处无变异） 评价第二代种群;遗传算法-数学解释;遗传算法-改进;遗传算法-欺骗问题;遗传算法-欺骗问题举例;遗传算法-主要特点;主要内容;群智能优化算法;;主要内容;蚁群优化算法(Ant Colony Optimization);问题的描述：n个城市N = {1, 2, …, n}，任两城市的边 A = {(i, j) | i, j ∈ N}，城市间的距离为D = (dij)n×n 设有m只蚂蚁，其出发城市可随机确定 路径的构造 为TSP图中的每一条弧(i, j)赋信息素初值τij(0)，通常的做法是随机生成一个解，设其目标值为f0，则τij(0) =1/f0 设置城市间的启发式信息ηij ，通常ηij = 1/dij 设第k只蚂蚁在城市i，则其根据下面的概率选择下一个城市： 其中 另外，每一蚂蚁有一个表list，用于记录其访问过的城市；当访问了所有的城市后，就可以在其经过的路径上更新信息素;信息素更新策略 （局部更新）所有蚂蚁周游完成后更新信息素：首先以一定的比例(1 - ρ)减少每条边上的信息素（ 表示信息素的挥发），然后更新各自路径上的信息素，即更新信息素的方式为 其中信息素的挥发机制可以避免信息素大量积累，也体现了生物界的“遗忘”现象； 表示蚂蚁k在边(i, j)上留下的信息素，如果蚂蚁没有经过该边，则其留下的信息素为0，即 其中， 表示蚂蚁k构造的路径的长度，Q是一常数（比如1） 此机制体现了：构造的路径越短，蚂蚁留下的信息素越多；某边经过的蚂蚁越多，其上积累的信息素也就越多;全局更新：对于一次迭代中最好的那只蚂蚁，单独更新其 经过路径上的信息素 上面的蚁群优化算法的不足 信息素的累积造成“停滞”现象：蚂蚁基本上走同一条路径 要得到更好的优化能力往往需要与局部有哪些信誉好的足球投注网站算法结合：对最好的路径执行局部有哪些信誉好的足球投注网站 蚁群算法的改进 精英策略：对已发现的最好路径给予额外的增强，从而增大较好路径的选择概率 负反馈机制：蚂蚁走过一条边时，立即减少该边上的信息素，以减少该边再次被选中的概率 Max-Min蚂蚁系统：将信息素的浓度限制在[min, max]的范围内，避免有哪些信誉好的足球投注网站停滞[T. Stutzle, H. Hoos, MAX-MIN Ant System, FGCS, 2000, 16:889-914] ;蚁群优化算法-较成功的算法;蚁群优化算法-较成功的应用;蚁群优化算法-较成功的应用(续);主要内容;粒子群优化算法(Particle Swarm Optimization); 设第i个粒子表示为Xi = (xi1, xi2, …, xiD)，有最好适应值的位置记为Pi = (pi1, pi2, …, piD)，也称为Pbest。设符号g表示群体中所有粒子经历过的最好位置，也称为gbest。设Vi =(vi1, vi2, …, viD)表示粒子i的速度。在每一代，粒子i的第d维(1 ? d ? D)根据如下方程变化： vid = w·vid + c1·rand1()(pid - xid) + c2·rand2()(pgd - xid) xid = xid + vid 其中w为惯性权重，c1和c2为加速常数，rand1()和rand2()为在[0, 1]内选取的随机函数。此外，微粒的速度vid的上限为Vmax。;(1)初始化：随机生成一群规模为m的微粒，包括位置和速度 (2)评价：计算每个微粒的适应度 (3)更新Pbest：对每个微粒，将其适应值与其经历