蚂蚁算法AntColonyOptimization蚂蚁算法蚂蚁的生物特征图2-1蚂蚁从蚁穴（Nest）移至食物源(Food)图2-2在巢穴与食物源之间出现障碍物时蚂蚁收敛到最短路径的过程蚂蚁算法的原理蚂蚁算法的特点蚂蚁算法符号的定义蚂蚁算法符号的定义蚂蚁算法求解的一般步骤AS模型（AntSystem简称AS）按的不同取法,可形成三种类型的蚂蚁算法模型:(1)蚂蚁密度模型（AntDensity）：(2)蚂蚁数量模型（AntQuantity）：(3)蚂蚁圈模型（AntCycle）：其中:可行结点集合，具体应用中经常用表示，为第k只蚂蚁在第i结点出发下一步的可行结点集（TSP问题应去掉第k只蚂蚁已经过的结点），为第k只蚂蚁在本次循环中所走的路径的长度。上述三种模型中，蚂蚁密度模型和蚂蚁数量模型利用的是局部信息，而蚂蚁圈模型利用的是全局信息，对全局优化较好。Ant-Q模型（2）Pseudo-Random-Proportional规则：V按照下面概率选择（3）Random-Proportional规则：设置为0,基于概率分布进行所有的决策。信息素轨迹更新方程为：这里，在初始化或求解最好结果路径上信息素增量，下一状态增加信息素相对最大值的比例是。ACS（AntColonySystem）模型LocalUpdating(onlineupdating):GlobalUpdating(offlineupdating):这里的可以是，，0。仅对最短路径的信息素增加量。局部更新用于每一时刻每一蚂蚁的每一步移动之中，而全局更新是所有的蚂蚁都完成一个周期的搜索之后最好的搜索结果进行信息素轨迹更新。MMAS(Max-MinAntSystem)模型ANTS模型几种模型的评价AS(AntSystem)模型的优点ACS与AS的主要区别MMAS模型特点表2蚂蚁算法及其应用表2蚂蚁算法及其应用（续）蚂蚁算法可研究问题举例1：遗传算法与蚂蚁算法的融合遗传算法的基本原理种群#位串适应值排序101101101138.33110001110043.72011101010154.51011001001034.64遗传算法的特点遗传算法与蚂蚁算法的融合思想GAAA算法总体框架与流程图3-3GAAA算法详细流图GAAA中遗传算法的模型选择定义交叉算子：采用Davis提出的顺序交叉方法，先进行常规的双点交叉，在进行维持原有相对访问顺序的巡回路线修改。具体交叉如下：（1）随机在父串上选择一个交配区域，如两父串选定为：old1=12|3456|789,old2=98|7654|321（2）将old2的交配区域加到old1前面，将old1的交配区域加到old2的前面：old1’=7654|123456789,old2’=3456|987654321（3）依次删除old1’，old2’中与交配区相同的数码，得到最终的两子串：new1=765412389,new2=345698721变异算子：采用逆转变异方法，所谓“逆转”，如染色体(1—2—3—4—5—6)在区间2—3和区间5—6处发生断裂，断裂片段又以反向顺序插入，于是逆转后的染色体变为(1—2—5—4—3—6)。这里的“进化”，是指逆转算子的单方向性，只有经逆转后，适应值有提高的才接受下来，否则逆转无效。GAAA中蚂蚁算法模型选择GAAA中遗传算法与蚂蚁算法对接仿真实验分析表3-1GAAA算法优化解数据逼近过程表3-2GAAA算法随机求解的30个优化解值分布图3-4GAAA算法一次随机遗传变异后产生的信息素分布(TSP30)图3-6GAAA算法一次随机迭代求得最好结果（TSP30,d=424.46）图3-8GAAA算法一次随机迭代求得最好结果（TSP30,d=424.69）图3-10GAAA算法找到的最优路径(CHN144,d=30351)图3-11GAAA算法一次随机迭代求得最好结果(CHN144,d=30354)表3-3:GAAA算法的实验结果表3-4:基本蚂蚁算法的实验结果图3-12GAAA一次随机求解过程（TSP30）算法及实例仿真结论：