蚁群算法的基本原理和改进 邢晶.pptVIP

蚁群算法的基本原理 及其改进算法 信号与信息处理 邢晶 201020602028 蚁群算法的提出 蚁群算法的基本原理 经研究发现，蚂蚁在觅食过程中分泌一种称之为信息素的物质，这种物质会随时间而挥发，蚂蚁能利用信息素作为媒介与其他蚂蚁进行信息沟通。一条路径上留下的信息素浓度的大小与这条路径上通过的蚂蚁数成正比，当通过的蚂蚁越多，则留下的信息素越多，从而导致后来蚂蚁选择该条路径的概率提高。 基本原理 基本原理 基本原理 基本原理 蚁群算法研究现状　 ＡCＡ是模拟自然界中真实蚁群的觅食行 为而形成 的一种模拟进化算法 。10年多来的研究结果 已经表明：ACA用于组合优化具有很 强的发现较好解 的能力，具有分布式计算 、 易于与其他方法相结合 、鲁棒性强等优点 ， 在动态环境下也表现出高度的灵活性 和健壮性。在求解 ＴSＰ、QAP问题方面，与遗传算法 、模拟退火算法等算法比较,ACA仍是最好的解决方法之一。　 蚁群算法基本模型 我们以求解平面上ｎ个城市的TSP问题（ 1,2，···，ｎ）表示城市号为例说明 ACA的模型。ｎ个城 市的TSP问题就是寻找通过ｎ个城市各一次且最后回到出发点的最短路径。　 蚁群算法基本模型 蚁群算法基本模型 设m只蚂蚁在图的相邻节点间移动，协作异步地得到解。 蚂蚁计算出下一步所有可达节点的一步转移概率，并按此概率实现一步移动，依此往复。 一步转移概率由图中每条边上的两类参数决定：信息素值、可见度(即先验值)。 信息素的更新有2种方式： 挥发——所有路径上信息素以一定比率减少 增强——给评价值“好”(有蚂蚁走过)的边增加信息素 蚁群算法基本模型 STEP 0 对n个城市的TSP问题， 城市间的距离矩阵为：(dij)n?n 给TSP图中的每一条弧(i, j)赋信息素初值：?ij(0)=1/|A| |A|：表示图中弧(i, j)的数目 ，即矩阵(dij)n?n中不为零的数； 设有m只蚂蚁工作，都从同一城市i0出发 当前最好解是：w*=(1, 2, …, n) 目标函数： 蚁群算法基本模型 STEP 1 (外循环) 若满足算法停止规则，停止计算，输出计算得到的最好解 给定外循环的最大数目，表明有足够的蚂蚁工作； 当前最优解连续K次相同而停止，K是给定的整数，表示算法已收敛； 给定优化问题的下界和误差值，当算法得到的目标值同下界之差小于给定的误差值时，算法终止。 否则使蚂蚁s(1?s?m)从起点i0出发，用L(s)表示蚂蚁s行走的城市集合，初始L(s)为空集?。 蚁群算法基本模型 STEP 2 (内循环) 按蚂蚁1?s?m的顺序分别计算 在城市i，若L(s)=N或{l|(i, l)?A, l?L(s)}=?，完成蚂蚁s的计算。 否则，若T={l|(i, l)?A, l?L(s)}-{i0}??，以概率 到达j，L(s)=L(s)?{j}，il=j 若L(s)?N且T=?，则到达i0， L(s)=L(s)?{i0}，il=i0 重复STEP 2 蚁群算法基本模型 STEP 3 对蚂蚁1?s?m， 若L(s)=N，按L(s)中城市的顺序计算路径长度； 若L(s)?N，路径长度置为无穷大(即不可达)。 比较m只蚂蚁的路径长度，记走最短路径的蚂蚁为t。 若f(L(t))f(w*)，则w*=L(t) 蚁群算法的特征 蚁群算法具有群体智能的特点: ①单个个体具有简单性; ②改变环境的能力和系统自调节性; ③无中心控制; ④个体散布性; ⑤可扩充性; ⑥安全性。 蚁群算法的优点 算法的优点有: ①较强的鲁棒性; ②分布式计算; ③易于与其它方法相结合。 算法的缺陷 蚁群寻径是由各路径上的信息素浓度和城巾间的距离来引导的，其最终结果为一近似解，并不是精确解。在求解TSP问题时常存在以下问题: ①容易在还没有得到全局最优解时就收敛，得到的是局部最优解，从而份致算法出现停滞现象; ②有哪些信誉好的足球投注网站时间过长，结果常在局部最优解与全局最优解之间反复。 算法的优化 ①蚁群优化算法(Ant Colony Optimization, ACO):蚂蚁选择节点的规则不同、全局更新规则不同、增加了局部更新规则; ②最人最小蚁样算法(Max-Min Ant System, MMNS);限定了信息素浓度允许值的上下限，并采用了平滑机制; ③蚁群算法与其它算法相结合，可产生多种新的改进型算法; ④具有变异特征的蚁群算法，采用逆转变异的方式，随机地进行变异，以增大进化时所需的信点量，加快算法的收敛速度。 一种新的优化策略 ①将，n只蚂蚁置于m个节点上