●●● ●●●● ●●●●● ●●●● 蚂蚁系统 ●●0●● ●●●0 多里戈在其博士论文中提出了一种蚂蚁系 统( ANT SYSTEM AS),以解决旅行商 问题(TSP) 个售货员希望去访问若干个城市,开始 和结束于同一城市,每两个城市之间都有 条直接通路,怎样行走才能使走过的路 径最短?
蚂蚁系统 ⚫ 多里戈在其博士论文中提出了一种蚂蚁系 统（ANT SYSTEM AS）,以解决旅行商 问题（TSP） ⚫ 一个售货员希望去访问若干个城市，开始 和结束于同一城市，每两个城市之间都有 一条直接通路，怎样行走才能使走过的路 径最短？
●●● ●●●● ●●●●● ●●●● 蚁群算法 ●●0●● ●●●0 ●蚂蚁在两个城市之间移动 ●两个城市之间的信息素越多,蚂蚁就越有可 能选择它们之间的路径 °能够成功完成遍历的蚂蚁会在路径上留下信 息素,路径越短留下的信息素会越多
蚁群算法 ⚫蚂蚁在两个城市之间移动 ⚫两个城市之间的信息素越多，蚂蚁就越有可 能选择它们之间的路径 ⚫能够成功完成遍历的蚂蚁会在路径上留下信 息素，路径越短留下的信息素会越多
●●● ●●●● ●●●●● ●●●● 蚁群算法原理 ●●0●● ●●●0 ●基于蚂蚁觅食时的最优路径选择问题,可以构造人工 蚁群,来解决最优问题。 人工蚁群中把具有简单功能的工作单元看作蚂蚁 人工蚂蚁与自然蚁群 相似之处:优先选择信息素浓度大的路径 ●区别:人工蚂蚁有一定的记忆能力,能够记忆已经访 问过的节点 ●人工蚁群在选择下一条路径的时候是按一定的算法有 意识的寻找最短路径,而不是盲目的
蚁群算法原理 ⚫ 基于蚂蚁觅食时的最优路径选择问题，可以构造人工 蚁群，来解决最优问题。 ⚫ 人工蚁群中把具有简单功能的工作单元看作蚂蚁 ⚫ 人工蚂蚁与自然蚁群 ⚫ 相似之处：优先选择信息素浓度大的路径 ⚫ 区别：人工蚂蚁有一定的记忆能力，能够记忆已经访 问过的节点 ⚫ 人工蚁群在选择下一条路径的时候是按一定的算法有 意识的寻找最短路径，而不是盲目的
●●● ●●●● ●●●●● ●●●● 蚁群算法中的各种行为因子 ●●0●● ●●●0 范围:蚂蚁观察到的范围是一个方格世界,蚂蚁有一个 参数为速度半径,那么它能观察到的范围以及能够移动的 范围都会发生在这样的一个范围之内 环境:蚂蚁所在的环境是一个虚拟的世界,其中有障碍 物,有其他的蚂蚁,还有信息素,信息素可以设计为单 种类也可以多种类(如两种),一种是找到食物的蚂蚁撒 下的食物信息素,另外一种是找到食物的蚂蚁洒下的蚁窝 的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。 同时环境也以一定的速率让信息素消失
蚁群算法中的各种行为因子 范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个 参数为速度半径，那么它能观察到的范围以及能够移动的 范围都会发生在这样的一个范围之内 环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍 物，有其他的蚂蚁，还有信息素，信息素可以设计为单一 种类也可以多种类（如两种），一种是找到食物的蚂蚁撒 下的食物信息素，另外一种是找到食物的蚂蚁洒下的蚁窝 的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。 同时环境也以一定的速率让信息素消失