《《蚁群算法实验室》流程图》由会员分享,可在线阅读,更多相关《《蚁群算法实验室》流程图(2页珍藏版)》请在金锄头文库上搜索。
1、蚁群算法实验室流程图蚁群算法计算主流程(该流程在用户控制下可在没达到指定循环次数时停止或暂停)目前蚁群算法主要用在组合优化方面,基本蚁群算法的思路是这样的:1. 在初始状态下,一群蚂蚁外出,此时没有信息素,那么各自会随机的选择一条路径。2. 在下一个状态,每只蚂蚁到达了不同的点,从初始点到这些点之间留下了信息素,蚂蚁继续走,已经到达目标的蚂蚁开始返回,与此同时,下一批蚂蚁出动,它们都会按照各条路径上信息素的多少选择路线(selection),更倾向于选择信息素多的路径走(当然也有随机性) 。开始读入城市数据初始化各种图表初始化算法参数及公共变量绘制城市位置为每只蚂蚁建立一条路径对每只蚂蚁经过的
2、路径执行局部更新规则选出最好的蚂蚁执行全局更新规则刷新结果显示达到指定计 算次数?否是结束循环次数加一3. 又到了再下一个状态,刚刚没有蚂蚁经过的路线上的信息素不同程度的挥发掉了(evaporation),而刚刚经过了蚂蚁的路线信息素增强(reinforcement)。然后又出动一批蚂蚁,重复第 2 个步骤。每个状态到下一个状态的变化称为一次迭代,在迭代多次过后,就会有某一条路径上的信息素明显多于其它路径,这通常就是一条最优路径。关键的部分在于步骤 2 和 3:步骤 2 中,每只蚂蚁都要作出选择,怎样选择呢?selection 过程用一个简单的函数实现:蚂蚁选择某条路线的概率该路线上的信息素所
3、有可选择路线的信息素之和假设蚂蚁在 i 点,p(i,j) 表示下一次到达 j 点的概率,而 (i,j)表示 ij 两点间的信息素,则:p(i,j)(i,j)/(i)(如果所有可选路线的信息素之和(i)0,即前面还没有蚂蚁来过,概率就是一个0,1上的随机值,即随机选择一条路线)步骤 3 中,挥发和增强是算法的关键所在(也就是如何数学定义信息素的)evaporation 过程和 reinforcement 过程定义了一个挥发因子,是迭代次数 k 的一个函数(k)1lnk/ln(k+1)最初设定每条路径的信息素 (i,j,0)为相同的值然后,第 k+1 次迭代时,信息素的多少对于没有蚂蚁经过的路线:(i,j,k+1)(1 (k)(i,j,k) ,显然信息素减少了有蚂蚁经过的路线:(i,j,k+1)(1 (k)(i,j,k) (k)/|W|,W 为所有点的集合为什么各个函数要如此定义,这个问题很难解释清楚,这也是算法的精妙所在。如此定义信息素的挥发和增强,以及路径选择,根据马尔可夫过程(随机过程之一)能够推导出,在迭代了足够多次以后,算法能够收敛到最佳路径。