《人工智能第五章(3)》由会员分享，可在线阅读，更多相关《人工智能第五章(3)（10页珍藏版）》请在金锄头文库上搜索。
1、2013-11-261计算智能计算智能计算智能计算智能群智能算法群智能算法群智能算法群智能算法 群智能群智能群智能群智能（Swarm Intelligence, SI ）群群群群（swarm）：某种交互作用的组织或某种交互作用的组织或某种交互作用的组织或某种交互作用的组织或agent的结构集的结构集的结构集的结构集合合合合。对于群居昆虫对于群居昆虫对于群居昆虫对于群居昆虫，如蚂蚁如蚂蚁如蚂蚁如蚂蚁、蜜蜂蜜蜂蜜蜂蜜蜂、鱼群鱼群鱼群鱼群、鸟群等鸟群等鸟群等鸟群等，个体个体个体个体在结构上是很简单的在结构上是很简单的在结构上是很简单的在结构上是很简单的，而它们的集体行为却可能变而它们的集体行为却可能
2、变而它们的集体行为却可能变而它们的集体行为却可能变得相当复杂得相当复杂得相当复杂得相当复杂。人们人们人们人们把群居昆虫的集体行为称作把群居昆虫的集体行为称作把群居昆虫的集体行为称作把群居昆虫的集体行为称作“群智能群智能群智能群智能”，即低智即低智即低智即低智能能能能的主体通过合作表现的主体通过合作表现的主体通过合作表现的主体通过合作表现出高智能出高智能出高智能出高智能行为的行为的行为的行为的特性特性特性特性。群智能算法是群智能算法是群智能算法是群智能算法是一种基于生物群体行为规律的计算技术一种基于生物群体行为规律的计算技术一种基于生物群体行为规律的计算技术一种基于生物群体行为规律的计算技术。群
3、智能概述群智能概述群智能概述群智能概述 特点特点特点特点1. 个体的行为很简单个体的行为很简单个体的行为很简单个体的行为很简单，但当它们一起协但当它们一起协但当它们一起协但当它们一起协同工作时却能够突现出非常复杂同工作时却能够突现出非常复杂同工作时却能够突现出非常复杂同工作时却能够突现出非常复杂（智智智智能能能能）的行为特征的行为特征的行为特征的行为特征。2. 群智能优化在群智能优化在群智能优化在群智能优化在没有集中控制且不提供没有集中控制且不提供没有集中控制且不提供没有集中控制且不提供全局模型全局模型全局模型全局模型的前提下的前提下的前提下的前提下，为寻找复杂的分为寻找复杂的分为寻找复杂的分
4、为寻找复杂的分布式布式布式布式问题求解问题求解问题求解问题求解方案提供了方案提供了方案提供了方案提供了基础基础基础基础。 优点优点优点优点1. 灵活性灵活性灵活性灵活性：群体可以适应随时变化的环境群体可以适应随时变化的环境群体可以适应随时变化的环境群体可以适应随时变化的环境；2. 稳健性稳健性稳健性稳健性：个体失败个体失败个体失败个体失败，群体仍能完成任务群体仍能完成任务群体仍能完成任务群体仍能完成任务；3. 自组织自组织自组织自组织：活动既不受中央控制活动既不受中央控制活动既不受中央控制活动既不受中央控制，也不受也不受也不受也不受局局局局部监管部监管部监管部监管。 典型典型典型典型算法算法算
5、法算法粒子群优化算法粒子群优化算法粒子群优化算法粒子群优化算法（鸟群捕食鸟群捕食鸟群捕食鸟群捕食）蚁蚁蚁蚁群算法群算法群算法群算法（蚂蚁觅食蚂蚁觅食蚂蚁觅食蚂蚁觅食）粒子群优化算法粒子群优化算法粒子群优化算法粒子群优化算法 粒子粒子粒子粒子群优化算法简述群优化算法简述群优化算法简述群优化算法简述粒 子 群 优 化 算 法粒 子 群 优 化 算 法粒 子 群 优 化 算 法粒 子 群 优 化 算 法 （ ParticleSwarmOptimization，PSO），也称为也称为也称为也称为粒子群算法粒子群算法粒子群算法粒子群算法，是近几年来发展是近几年来发展是近几年来发展是近几年来发展起来的一种
6、新起来的一种新起来的一种新起来的一种新的群体搜索算法的群体搜索算法的群体搜索算法的群体搜索算法。和和和和遗传算法遗传算法遗传算法遗传算法相似相似相似相似，它它它它也是从也是从也是从也是从随机的解随机的解随机的解随机的解出发出发出发出发，通过通过通过通过迭代寻找最优解迭代寻找最优解迭代寻找最优解迭代寻找最优解，通过适应度来评价通过适应度来评价通过适应度来评价通过适应度来评价解的解的解的解的品质品质品质品质。比比比比遗传算法规则更为遗传算法规则更为遗传算法规则更为遗传算法规则更为简单简单简单简单，它它它它没有遗传算法的没有遗传算法的没有遗传算法的没有遗传算法的“交叉交叉交叉交叉”(Crossove
7、r) 和和和和“变异变异变异变异”(Mutation) 操作操作操作操作，而是追随而是追随而是追随而是追随当前搜索到的当前搜索到的当前搜索到的当前搜索到的最优值来寻找全局最优最优值来寻找全局最优最优值来寻找全局最优最优值来寻找全局最优。 粒子粒子粒子粒子群群群群算法的思想和算法的思想和算法的思想和算法的思想和起源起源起源起源 由由由由James Kenney（社会心枞学博士社会心枞学博士社会心枞学博士社会心枞学博士）和和和和Russ Eberhart（电子工程学博士电子工程学博士电子工程学博士电子工程学博士），），），），于于于于1995年提出年提出年提出年提出。 该算法源于对鸟群捕食行为的研
8、究该算法源于对鸟群捕食行为的研究该算法源于对鸟群捕食行为的研究该算法源于对鸟群捕食行为的研究 ，是受到飞鸟集群活动的规律性启发是受到飞鸟集群活动的规律性启发是受到飞鸟集群活动的规律性启发是受到飞鸟集群活动的规律性启发，利用群体智能建立的一个简化模型利用群体智能建立的一个简化模型利用群体智能建立的一个简化模型利用群体智能建立的一个简化模型。2013-11-262 粒子粒子粒子粒子群群群群算法算法算法算法的原理描述的原理描述的原理描述的原理描述（1 1 1 1）假设假设假设假设存在一个存在一个存在一个存在一个区域区域区域区域，所有所有所有所有的鸟都不知道的鸟都不知道的鸟都不知道的鸟都不知道食物的位
9、食物的位食物的位食物的位置置置置，但是它们知道但是它们知道但是它们知道但是它们知道当前的位置当前的位置当前的位置当前的位置果食物果食物果食物果食物还有多远还有多远还有多远还有多远。找到食物的最优策略是什么找到食物的最优策略是什么找到食物的最优策略是什么找到食物的最优策略是什么呢呢呢呢？搜寻目前搜寻目前搜寻目前搜寻目前果食物果食物果食物果食物最近的鸟的周围最近的鸟的周围最近的鸟的周围最近的鸟的周围区域区域区域区域。在该算法中在该算法中在该算法中在该算法中，每个每个每个每个解看作一只鸟解看作一只鸟解看作一只鸟解看作一只鸟，称为称为称为称为粒子粒子粒子粒子(particle)，所有所有所有所有的粒子
10、都有一个适应值的粒子都有一个适应值的粒子都有一个适应值的粒子都有一个适应值，每个每个每个每个粒粒粒粒子都有子都有子都有子都有一个一个一个一个速度决定它们的飞翔方向和速度决定它们的飞翔方向和速度决定它们的飞翔方向和速度决定它们的飞翔方向和距果距果距果距果，粒粒粒粒子子子子们们们们追随追随追随追随当前最优粒子在解空间中搜索当前最优粒子在解空间中搜索当前最优粒子在解空间中搜索当前最优粒子在解空间中搜索。 粒子粒子粒子粒子群算法的原理描述群算法的原理描述群算法的原理描述群算法的原理描述（2 2 2 2）当当当当其它鸟发现了更佳的觅食其它鸟发现了更佳的觅食其它鸟发现了更佳的觅食其它鸟发现了更佳的觅食地点
11、地点地点地点，鸟鸟鸟鸟群群群群间间间间 会会会会有有有有某种枑似广播的沟通行为某种枑似广播的沟通行为某种枑似广播的沟通行为某种枑似广播的沟通行为，渐渐的将渐渐的将渐渐的将渐渐的将其它鸟群其它鸟群其它鸟群其它鸟群引引引引领至较佳的地点领至较佳的地点领至较佳的地点领至较佳的地点。这样的觅食行为是这样的觅食行为是这样的觅食行为是这样的觅食行为是利利利利 用用用用社会社会社会社会中所存在的互相影响的概念中所存在的互相影响的概念中所存在的互相影响的概念中所存在的互相影响的概念，来引领来引领来引领来引领所有所有所有所有个体朝个体朝个体朝个体朝向最佳解向最佳解向最佳解向最佳解位置位置位置位置。 粒子粒子粒子
12、粒子群寻优示意图群寻优示意图群寻优示意图群寻优示意图 基本粒子群算法的描述基本粒子群算法的描述基本粒子群算法的描述基本粒子群算法的描述1. 假设在假设在假设在假设在D维搜索空间中维搜索空间中维搜索空间中维搜索空间中，有有有有m个粒子个粒子个粒子个粒子；（1）其中其中其中其中第第第第i个粒子的个粒子的个粒子的个粒子的位置矢量表示为位置矢量表示为位置矢量表示为位置矢量表示为：（2）飞翔速度矢量表示为飞翔速度矢量表示为飞翔速度矢量表示为飞翔速度矢量表示为：（3）第第第第 i个粒子搜索到的最优位置为个粒子搜索到的最优位置为个粒子搜索到的最优位置为个粒子搜索到的最优位置为 ：（4）整个整个整个整个粒子群
13、搜索到的最优位置为粒子群搜索到的最优位置为粒子群搜索到的最优位置为粒子群搜索到的最优位置为 ：),(21iDiiixxxx?=),(21iDiiivvvv?=),(21iDiiipppp?=),(21gbestDgbestgbestgbestpppp?= 基本粒子群算法的描述基本粒子群算法的描述基本粒子群算法的描述基本粒子群算法的描述2. 粒子粒子粒子粒子速度和位置的速度和位置的速度和位置的速度和位置的更新更新更新更新其中其中其中其中w为为为为惯性权重惯性权重惯性权重惯性权重，d=1,2, , D，i=1,2, , M。c1 和和和和c2 为为为为两个正常两个正常两个正常两个正常数称为数称为数
14、称为数称为加速加速加速加速因子因子因子因子，rand( )为分布于为分布于为分布于为分布于0,1的随机数的随机数的随机数的随机数11211()()()() 1,2,; 1,2,kkkkididididgbestidkkkidididvwvc randpxc randpxxxvimdD+=+=+= 基本粒子群算法的描述基本粒子群算法的描述基本粒子群算法的描述基本粒子群算法的描述2. 粒子速度和位置的更新粒子速度和位置的更新粒子速度和位置的更新粒子速度和位置的更新Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1
15、 )()()()(11211=+=+=+“惯性部分惯性部分惯性部分惯性部分”，对自身运动状对自身运动状对自身运动状对自身运动状态的信任态的信任态的信任态的信任“认知部分认知部分认知部分认知部分”，对微粒对微粒对微粒对微粒本身的思考本身的思考本身的思考本身的思考，即来源即来源即来源即来源于自己经验的部分于自己经验的部分于自己经验的部分于自己经验的部分“社会部分社会部分社会部分社会部分”，微粒间的微粒间的微粒间的微粒间的信息共享信息共享信息共享信息共享，来源于群体中来源于群体中来源于群体中来源于群体中的其它优秀微粒的经验的其它优秀微粒的经验的其它优秀微粒的经验的其它优秀微粒的经验2013-11-2
16、63 基本粒子群算法的描述基本粒子群算法的描述基本粒子群算法的描述基本粒子群算法的描述3. 粒子更新示意图粒子更新示意图粒子更新示意图粒子更新示意图局部最佳值全局最佳解运动向量惯性向量12X = X ,X ,.,Xiiiid12V = V ,V ,.,Viiiid12(1)( )( )( )() ()() ()ididididgdidttttvw vc randpxcrandpx+=+(1)( )( )iiitttxxv+=+种群最优值种群最优值种群最优值种群最优值个体最优值个体最优值个体最优值个体最优值xpgpiv开始开始开始开始开始设置参数设置参数设置参数设置参数初始种群初始种群初始种群初
17、始种群计算适应度计算适应度计算适应度计算适应度最大次数最大次数最大次数最大次数输出最优解输出最优解输出最优解输出最优解开始结束结束结束结束Y迭代次数加迭代次数加迭代次数加迭代次数加1N粒子数量粒子数量粒子数量粒子数量N N N N 速度范围速度范围速度范围速度范围 VmaxVmaxVmaxVmax权重系数权重系数权重系数权重系数w w w w 加速因子加速因子加速因子加速因子c1c1c1c1和和和和c2c2c2c2更新速度和位置更新速度和位置更新速度和位置更新速度和位置基本粒子群算法的描述基本粒子群算法的描述基本粒子群算法的描述基本粒子群算法的描述4. 粒子群算法流程图粒子群算法流程图粒子群算
18、法流程图粒子群算法流程图随机产生随机产生随机产生随机产生分惯性部分惯性部分惯性部分惯性部分、认知部分认知部分认知部分认知部分社会部分社会部分社会部分社会部分 基本粒子群算法的描述基本粒子群算法的描述基本粒子群算法的描述基本粒子群算法的描述5. 粒子群算法迭代过程粒子群算法迭代过程粒子群算法迭代过程粒子群算法迭代过程6. 粒子粒子粒子粒子群算法参数分析群算法参数分析群算法参数分析群算法参数分析（1）惯性惯性惯性惯性权重权重权重权重w使粒子使粒子使粒子使粒子保持运动惯性保持运动惯性保持运动惯性保持运动惯性，使其使其使其使其有搜索有搜索有搜索有搜索扩展扩展扩展扩展空间空间空间空间的的的的趋势趋势趋势
19、趋势，有能力探索新的区域有能力探索新的区域有能力探索新的区域有能力探索新的区域。也表示也表示也表示也表示微粒对当前自身运动状态的信任微粒对当前自身运动状态的信任微粒对当前自身运动状态的信任微粒对当前自身运动状态的信任，依依依依据自身据自身据自身据自身的速度进行惯性的速度进行惯性的速度进行惯性的速度进行惯性运动运动运动运动。较大较大较大较大的的的的w有利于跳出局部极值有利于跳出局部极值有利于跳出局部极值有利于跳出局部极值，而较小的而较小的而较小的而较小的w有有有有利于利于利于利于算法算法算法算法收敛收敛收敛收敛。Ddmivxxxprandcxprandcwvvkidkidkidkidgbestk
20、ididkidkid, 2 , 1 ;, 2 , 1 )()()()(11211=+=+=+6. 粒子粒子粒子粒子群算法参数分析群算法参数分析群算法参数分析群算法参数分析（2）改进的改进的改进的改进的惯性惯性惯性惯性权重权重权重权重w在优化实际在优化实际在优化实际在优化实际优化问题时优化问题时优化问题时优化问题时，往往希望先采用往往希望先采用往往希望先采用往往希望先采用全局全局全局全局搜索搜索搜索搜索，使搜索空间快速收敛于某一区域使搜索空间快速收敛于某一区域使搜索空间快速收敛于某一区域使搜索空间快速收敛于某一区域，然后然后然后然后采用采用采用采用局部精细搜索以获得高精度的局部精细搜索以获得高精
21、度的局部精细搜索以获得高精度的局部精细搜索以获得高精度的解解解解。因此因此因此因此提出了自适应提出了自适应提出了自适应提出了自适应调整的调整的调整的调整的策略策略策略策略，即随着即随着即随着即随着迭代迭代迭代迭代的的的的进行进行进行进行，线性地减小线性地减小线性地减小线性地减小w 的值的值的值的值。Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1 )()()()(11211=+=+=+6. 粒子粒子粒子粒子群算法参数分析群算法参数分析群算法参数分析群算法参数分析（2）改进的改进的改进的改进的惯性惯性惯性惯性
22、权重权重权重权重wwmax、wmin分别是分别是分别是分别是w的最大值和最小值的最大值和最小值的最大值和最小值的最大值和最小值；iter、itermax分别是当前迭代次数和最大分别是当前迭代次数和最大分别是当前迭代次数和最大分别是当前迭代次数和最大迭代迭代迭代迭代次数次数次数次数。Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1 )()()()(11211=+=+=+iteriterwwww=maxminmaxmax2013-11-2646. 粒子粒子粒子粒子群算法参数分析群算法参数分析群算法参数分析群算法
23、参数分析（3）加速因子加速因子加速因子加速因子c1和和和和c2使代表将微粒推向使代表将微粒推向使代表将微粒推向使代表将微粒推向pbest和和和和gbest位置的统计加位置的统计加位置的统计加位置的统计加速项的权重速项的权重速项的权重速项的权重。表示表示表示表示粒子的动作来源于自己经验的粒子的动作来源于自己经验的粒子的动作来源于自己经验的粒子的动作来源于自己经验的部分和其部分和其部分和其部分和其它它它它粒子经验的部分粒子经验的部分粒子经验的部分粒子经验的部分。低低低低的值粒子的值粒子的值粒子的值粒子在目标在目标在目标在目标区域外徘徊区域外徘徊区域外徘徊区域外徘徊，而高的而高的而高的而高的值值值值
24、导致导致导致导致粒子越过目标域粒子越过目标域粒子越过目标域粒子越过目标域。Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1 )()()()(11211=+=+=+6. 粒子粒子粒子粒子群算法参数分析群算法参数分析群算法参数分析群算法参数分析（4）改进的加速改进的加速改进的加速改进的加速因子因子因子因子c1和和和和c2通常将通常将通常将通常将c1和和和和c2统一为一个控制参数统一为一个控制参数统一为一个控制参数统一为一个控制参数，= c1+c2如果如果如果如果很小很小很小很小，微粒群运动轨迹将非常缓慢微粒群运
25、动轨迹将非常缓慢微粒群运动轨迹将非常缓慢微粒群运动轨迹将非常缓慢；如果如果如果如果很大很大很大很大，则微粒位置变化非常快则微粒位置变化非常快则微粒位置变化非常快则微粒位置变化非常快；通过仿真可以获得通过仿真可以获得通过仿真可以获得通过仿真可以获得的经验值的经验值的经验值的经验值，当当当当=4.0 （c1=2.0，c2=2.0）时时时时，具有很好的收敛效果具有很好的收敛效果具有很好的收敛效果具有很好的收敛效果。Ddmivxxxprandcxprandcwvvkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1 )()()()(11211=+=+=+6. 粒子粒
26、子粒子粒子群算法参数分析群算法参数分析群算法参数分析群算法参数分析（5）粒子数粒子数粒子数粒子数通常一般取通常一般取通常一般取通常一般取2040，对较难或特定枑别的对较难或特定枑别的对较难或特定枑别的对较难或特定枑别的问问问问题题题题可以可以可以可以取取取取100200。（6）最大速度最大速度最大速度最大速度vmax决定决定决定决定粒子在一个循环中最大的移动距果粒子在一个循环中最大的移动距果粒子在一个循环中最大的移动距果粒子在一个循环中最大的移动距果，通常通常通常通常设定设定设定设定为粒子的范围宽度为粒子的范围宽度为粒子的范围宽度为粒子的范围宽度。Ddmivxxxprandcxprandcwv
27、vkidkidkidkidgbestkididkidkid, 2 , 1 ;, 2 , 1 )()()()(11211=+=+=+7. 粒子粒子粒子粒子群算法与遗传算法的群算法与遗传算法的群算法与遗传算法的群算法与遗传算法的比较比较比较比较共性共性共性共性：（1）都属于仿生算法都属于仿生算法都属于仿生算法都属于仿生算法；（2）都属于全局优化方法都属于全局优化方法都属于全局优化方法都属于全局优化方法；（3）都属于随机搜索算法都属于随机搜索算法都属于随机搜索算法都属于随机搜索算法；（4）都隐含并行性都隐含并行性都隐含并行性都隐含并行性；（5）根据个体的适配信息进行搜索根据个体的适配信息进行搜索根据
28、个体的适配信息进行搜索根据个体的适配信息进行搜索，因此不因此不因此不因此不受受受受函数约束条件的限制函数约束条件的限制函数约束条件的限制函数约束条件的限制，如连续性如连续性如连续性如连续性、可可可可导性导性导性导性。（6）对高维复杂问题对高维复杂问题对高维复杂问题对高维复杂问题，无法保证收敛到最优无法保证收敛到最优无法保证收敛到最优无法保证收敛到最优点点点点。7. 粒子群算法与遗传算法的比较粒子群算法与遗传算法的比较粒子群算法与遗传算法的比较粒子群算法与遗传算法的比较差异差异差异差异：（1）PSO有记忆有记忆有记忆有记忆，所有粒子都保存较优解的所有粒子都保存较优解的所有粒子都保存较优解的所有粒
29、子都保存较优解的知识知识知识知识，而而而而GA，以前的知识随着种群的改变被以前的知识随着种群的改变被以前的知识随着种群的改变被以前的知识随着种群的改变被改变改变改变改变；（2）PSO中的粒子是一种单向共享信息机制中的粒子是一种单向共享信息机制中的粒子是一种单向共享信息机制中的粒子是一种单向共享信息机制。而而而而GA中的染色体之间相互共享信息中的染色体之间相互共享信息中的染色体之间相互共享信息中的染色体之间相互共享信息；（3）GA需要编码和遗传操作需要编码和遗传操作需要编码和遗传操作需要编码和遗传操作，粒子只是通过粒子只是通过粒子只是通过粒子只是通过内部速度进行更新内部速度进行更新内部速度进行更
30、新内部速度进行更新，实现更容易实现更容易实现更容易实现更容易。蚁群算法蚁群算法蚁群算法蚁群算法 蚁群算法的思想和蚁群算法的思想和蚁群算法的思想和蚁群算法的思想和起源起源起源起源20 世纪世纪世纪世纪90 年代初年代初年代初年代初，意大利学者意大利学者意大利学者意大利学者Dorigo等等等等受蚂蚁受蚂蚁受蚂蚁受蚂蚁觅食行为的启发觅食行为的启发觅食行为的启发觅食行为的启发，在其博士论文中首次在其博士论文中首次在其博士论文中首次在其博士论文中首次提出了蚂提出了蚂提出了蚂提出了蚂蚁蚁蚁蚁系统系统系统系统（Ant System）。近年来近年来近年来近年来，Dorigo等人进一步等人进一步等人进一步等人进
31、一步将蚂蚁将蚂蚁将蚂蚁将蚂蚁算法发展为一算法发展为一算法发展为一算法发展为一种通用的种通用的种通用的种通用的优化技术优化技术优化技术优化技术-蚁蚁蚁蚁群群群群优化优化优化优化（Ant Colony Optimization）。）。）。）。蚂蚁觅食是寻找从巢穴到食物的最佳路径的行为蚂蚁觅食是寻找从巢穴到食物的最佳路径的行为蚂蚁觅食是寻找从巢穴到食物的最佳路径的行为蚂蚁觅食是寻找从巢穴到食物的最佳路径的行为。蚁群算法是一种仿生算法蚁群算法是一种仿生算法蚁群算法是一种仿生算法蚁群算法是一种仿生算法。2013-11-265 蚂蚁可以找出最短路径蚂蚁可以找出最短路径蚂蚁可以找出最短路径蚂蚁可以找出最短路
32、径，为什么为什么为什么为什么？1. 信息素信息素信息素信息素（pheromone）：）：）：）：蚂蚁在寻找食物蚂蚁在寻找食物蚂蚁在寻找食物蚂蚁在寻找食物时时时时，其经过其经过其经过其经过的路的路的路的路 上释放上释放上释放上释放的一种易挥发的物质的一种易挥发的物质的一种易挥发的物质的一种易挥发的物质。该该该该信息素信息素信息素信息素可以被其它可以被其它可以被其它可以被其它的蚂蚁感知的蚂蚁感知的蚂蚁感知的蚂蚁感知，并且信息素并且信息素并且信息素并且信息素的浓度的浓度的浓度的浓度越高越高越高越高，对应的路径越对应的路径越对应的路径越对应的路径越短短短短。2. 正反馈正反馈正反馈正反馈：蚂蚁会以较大
33、的概率选择信息素浓蚂蚁会以较大的概率选择信息素浓蚂蚁会以较大的概率选择信息素浓蚂蚁会以较大的概率选择信息素浓度较高的路径度较高的路径度较高的路径度较高的路径，并释放一定量的信息素以增强该并释放一定量的信息素以增强该并释放一定量的信息素以增强该并释放一定量的信息素以增强该路径上的信息素浓素路径上的信息素浓素路径上的信息素浓素路径上的信息素浓素，从而距离较短的路径被加从而距离较短的路径被加从而距离较短的路径被加从而距离较短的路径被加强强强强，形成一个正反馈形成一个正反馈形成一个正反馈形成一个正反馈。L1L2巢巢巢巢穴穴穴穴食食食食物物物物初始状态初始状态初始状态初始状态，两路径信息素两路径信息素两
34、路径信息素两路径信息素浓度相同且浓度相同且浓度相同且浓度相同且L2= 2 L1。蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图L1L2巢巢巢巢穴穴穴穴食食食食物物物物蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图L1L2巢巢巢巢穴穴穴穴食食食食物物物物蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图L1L2巢巢巢巢穴穴穴穴食食食食物物物物蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图L1L2巢巢巢巢穴穴穴穴食食食食物物物物蚂蚁寻找
35、最短路径示意图蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图2013-11-266L1L2巢巢巢巢穴穴穴穴食食食食物物物物最终选择信息素浓度较大的最终选择信息素浓度较大的最终选择信息素浓度较大的最终选择信息素浓度较大的L1路径路径路径路径蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图L1L2巢巢巢巢穴穴穴穴食食食食物物物物蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图L1L2巢巢巢巢穴穴穴穴食食食食物物物物蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意图蚂蚁寻找最短路径示意
36、图蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型与实现与实现与实现与实现与实现与实现与实现与实现-TSPTSP1. 不失一般性设蚂蚁的数量为不失一般性设蚂蚁的数量为不失一般性设蚂蚁的数量为不失一般性设蚂蚁的数量为 m，城市的数城市的数城市的数城市的数量为量为量为量为 n，城市城市城市城市 i和城市和城市和城市和城市 j的距离为的距离为的距离为的距离为距距距距离选用欧式距离离选用欧式距离离选用欧式距离离选用欧式距离，t时刻城市时刻城市时刻城市时刻城市 i和城市和城市和城市和城市 j连接路连接路连接路连接路径的信息素浓度为径的信息素
37、浓度为径的信息素浓度为径的信息素浓度为。2. 在算法在算法在算法在算法初始时刻初始时刻初始时刻初始时刻，设各城市连接路径的信设各城市连接路径的信设各城市连接路径的信设各城市连接路径的信息素浓度具有相同的值息素浓度具有相同的值息素浓度具有相同的值息素浓度具有相同的值，m只蚂蚁放到只蚂蚁放到只蚂蚁放到只蚂蚁放到 n座城座城座城座城市市市市。),(jid),(ji蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型与实现与实现与实现与实现与实现与实现与实现与实现-TSPTSP3. 蚂蚁蚂蚁蚂蚁蚂蚁的的的的初始分布初始分布初始分布初始分布（1
38、）.所有所有所有所有蚂蚁初始时刻放在同一蚂蚁初始时刻放在同一蚂蚁初始时刻放在同一蚂蚁初始时刻放在同一城市城市城市城市。（2）.所有蚂蚁初始时刻分布所有蚂蚁初始时刻分布所有蚂蚁初始时刻分布所有蚂蚁初始时刻分布在不同城市中在不同城市中在不同城市中在不同城市中。显而易见显而易见显而易见显而易见，第二种方法将蚂蚁放在不同的城第二种方法将蚂蚁放在不同的城第二种方法将蚂蚁放在不同的城第二种方法将蚂蚁放在不同的城市中算法具有较高的性能市中算法具有较高的性能市中算法具有较高的性能市中算法具有较高的性能。在在在在不同不同不同不同城市城市城市城市分布分布分布分布时时时时，随机分布与随机分布与随机分布与随机分布与统
39、一均匀分布的效果统一均匀分布的效果统一均匀分布的效果统一均匀分布的效果差别不差别不差别不差别不大大大大。蚁群算法的模型与实现蚁群算法的模型与实现蚁群算法的模型与实现蚁群算法的模型与实现蚁群算法的模型与实现蚁群算法的模型与实现蚁群算法的模型与实现蚁群算法的模型与实现-TSPTSP4. 每每每每只蚂蚁根据路径上的信息素和启发式只蚂蚁根据路径上的信息素和启发式只蚂蚁根据路径上的信息素和启发式只蚂蚁根据路径上的信息素和启发式信信信信息息息息，独立独立独立独立地地地地访问访问访问访问下下下下一座城市一座城市一座城市一座城市，概率公式如下概率公式如下概率公式如下概率公式如下：是是是是启发函数启发函数启发函
40、数启发函数，表示蚂蚁从表示蚂蚁从表示蚂蚁从表示蚂蚁从城城城城i到到到到城市城市城市城市j的期望的期望的期望的期望程度程度程度程度，距离越短函数值越大距离越短函数值越大距离越短函数值越大距离越短函数值越大。=otherwisetabujifsisijijijiPktabuskk,0,),(),(),(),(),(), (/ 1), (jidji=2013-11-267蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型与实现与实现与实现与实现与实现与实现与实现与实现-TSPTSP=otherwisetabujifsisijijijiPk
41、tabuskk,0,),(),(),(),(),(是信息素重要程度是信息素重要程度是信息素重要程度是信息素重要程度因子因子因子因子。是启发函数重要程度是启发函数重要程度是启发函数重要程度是启发函数重要程度因子因子因子因子。为禁忌表为禁忌表为禁忌表为禁忌表，表示已经访问的城市集合表示已经访问的城市集合表示已经访问的城市集合表示已经访问的城市集合。ktabu蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型与实现与实现与实现与实现与实现与实现与实现与实现-TSPTSP5. 蚂蚁从当前城市访问下一城市的概率确定蚂蚁从当前城市访问下一城市的
42、概率确定蚂蚁从当前城市访问下一城市的概率确定蚂蚁从当前城市访问下一城市的概率确定后后后后，通常采用轮盘赌法选择下一城市通常采用轮盘赌法选择下一城市通常采用轮盘赌法选择下一城市通常采用轮盘赌法选择下一城市，概率概率概率概率大被选中机会就大大被选中机会就大大被选中机会就大大被选中机会就大。P1P2P3蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型与实现与实现与实现与实现与实现与实现与实现与实现-TSPTSP6. 当当当当所有蚂蚁完成所有蚂蚁完成所有蚂蚁完成所有蚂蚁完成一次访问后一次访问后一次访问后一次访问后，各路径各路径各路径各路径
43、上上上上的信息素的信息素的信息素的信息素将进行更新将进行更新将进行更新将进行更新，信息素公式更新如下信息素公式更新如下信息素公式更新如下信息素公式更新如下：其中其中其中其中 的取值为的取值为的取值为的取值为 0 1，表示路径上表示路径上表示路径上表示路径上信息素信息素信息素信息素的的的的挥发挥发挥发挥发系数系数系数系数。=+=+mkkijijijijijtt1)()1()1(蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型与实现与实现与实现与实现与实现与实现与实现与实现-TSPTSP7. 针对针对针对针对蚂蚁释放信息素问题蚂蚁释放
44、信息素问题蚂蚁释放信息素问题蚂蚁释放信息素问题，比较常用的有比较常用的有比较常用的有比较常用的有如下如下如下如下三种三种三种三种模型模型模型模型：(1). Ant cycle systemQ为正常数为正常数为正常数为正常数， 表示表示表示表示第第第第k只蚂蚁在本只蚂蚁在本只蚂蚁在本只蚂蚁在本次访问城次访问城次访问城次访问城市中市中市中市中所走过路径的长度所走过路径的长度所走过路径的长度所走过路径的长度=otherwiselijLQkkkij0kL蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型与实现与实现与实现与实现与实现与实现与
45、实现与实现-TSPTSP7. 针对针对针对针对蚂蚁释放信息素问题蚂蚁释放信息素问题蚂蚁释放信息素问题蚂蚁释放信息素问题，比较常用的有比较常用的有比较常用的有比较常用的有如下如下如下如下三种三种三种三种模型模型模型模型：(2). Ant quantity systemQ为正常数为正常数为正常数为正常数， 表示表示表示表示第第第第k只蚂蚁在本只蚂蚁在本只蚂蚁在本只蚂蚁在本次访问中次访问中次访问中次访问中城市城市城市城市i和城市和城市和城市和城市j的距离的距离的距离的距离。=otherwiselijDQkijkij0ijD蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法
46、的模型蚁群算法的模型蚁群算法的模型与实现与实现与实现与实现与实现与实现与实现与实现-TSPTSP7. 针对针对针对针对蚂蚁释放信息素问题蚂蚁释放信息素问题蚂蚁释放信息素问题蚂蚁释放信息素问题，比较常用的有比较常用的有比较常用的有比较常用的有如下如下如下如下三种三种三种三种模型模型模型模型：(3). Ant density systemQ为正常数为正常数为正常数为正常数，在整个访问城市的过程中在整个访问城市的过程中在整个访问城市的过程中在整个访问城市的过程中，密密密密度始终保持不变度始终保持不变度始终保持不变度始终保持不变。=otherwiselijQkkij02013-11-268蚁群算法的模
47、型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型与实现与实现与实现与实现与实现与实现与实现与实现-TSPTSP7. 针对针对针对针对蚂蚁释放信息素问题蚂蚁释放信息素问题蚂蚁释放信息素问题蚂蚁释放信息素问题，这三这三这三这三种模型种模型种模型种模型分分分分别对应路径的整体信息别对应路径的整体信息别对应路径的整体信息别对应路径的整体信息（蚂蚁所访问路径的总蚂蚁所访问路径的总蚂蚁所访问路径的总蚂蚁所访问路径的总长长长长）、局部信息局部信息局部信息局部信息（蚂蚁所访问城市蚂蚁所访问城市蚂蚁所访问城市蚂蚁所访问城市间的距离间的距离间的距离间的距离）和不
48、和不和不和不考虑路径信息考虑路径信息考虑路径信息考虑路径信息。以下优化以下优化以下优化以下优化TSP问题问题问题问题，选用选用选用选用ant cycle system模型模型模型模型，即即即即路径的整体信息路径越短路径的整体信息路径越短路径的整体信息路径越短路径的整体信息路径越短，释放的释放的释放的释放的信息素信息素信息素信息素度越度越度越度越高高高高。蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型与实现与实现与实现与实现与实现与实现与实现与实现-TSPTSP开始开始开始开始开始初始化参数初始化参数初始化参数初始化参数构建解空间
49、构建解空间构建解空间构建解空间更新信息素更新信息素更新信息素更新信息素最大次数最大次数最大次数最大次数输出最优解输出最优解输出最优解输出最优解开始结束结束结束结束Y迭代次数加迭代次数加迭代次数加迭代次数加1N8. 蚁群算法解决蚁群算法解决蚁群算法解决蚁群算法解决TSP问题基本流程问题基本流程问题基本流程问题基本流程蚂蚁的数量蚂蚁的数量蚂蚁的数量蚂蚁的数量m、城市的数城市的数城市的数城市的数量量量量n、重要程度因子重要程度因子重要程度因子重要程度因子和和和和蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型与实现与实现与实现与实现与实
50、现与实现与实现与实现-TSPTSP开始开始开始开始开始初始化参数初始化参数初始化参数初始化参数构建解空间构建解空间构建解空间构建解空间更新信息素更新信息素更新信息素更新信息素最大次数最大次数最大次数最大次数输出最优解输出最优解输出最优解输出最优解开始结束结束结束结束Y迭代次数加迭代次数加迭代次数加迭代次数加1N蚂蚁访问下一城市的概率蚂蚁访问下一城市的概率蚂蚁访问下一城市的概率蚂蚁访问下一城市的概率，建造禁忌表建造禁忌表建造禁忌表建造禁忌表8. 蚁群算法解决蚁群算法解决蚁群算法解决蚁群算法解决TSP问题基本流程问题基本流程问题基本流程问题基本流程蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法
51、的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型与实现与实现与实现与实现与实现与实现与实现与实现-TSPTSP开始开始开始开始开始初始化参数初始化参数初始化参数初始化参数构建解空间构建解空间构建解空间构建解空间更新信息素更新信息素更新信息素更新信息素最大次数最大次数最大次数最大次数输出最优解输出最优解输出最优解输出最优解开始结束结束结束结束Y迭代次数加迭代次数加迭代次数加迭代次数加1N当前信息素挥发剩余的当前信息素挥发剩余的当前信息素挥发剩余的当前信息素挥发剩余的和蚂蚁在路径上产生的和蚂蚁在路径上产生的和蚂蚁在路径上产生的和蚂蚁在路径上产生的即优化即优化即优化即优化TSP得到的得
52、到的得到的得到的最短路径最短路径最短路径最短路径8. 蚁群算法解决蚁群算法解决蚁群算法解决蚁群算法解决TSP问题基本流程问题基本流程问题基本流程问题基本流程蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型与实现与实现与实现与实现与实现与实现与实现与实现-TSPTSP1. 31个城市坐标如下：x=1304,3639,4177,3712,3488,3326,3238,4196,4312,4386,3007,2562,2788,2381,1332,3715,3918,4061,3780,3676,4029,4263,3429,3507,
53、3394,3439,2935,3140,2545,2778,2370;y=2312,1315,2244,1399,1535,1556,1229,1004,790,570,1970,1756,1491,1676,695,1678,2179,2370,2212,2578,2838,2931,1908,2367,2643,3201,3240,3550,2357,2826,2975 蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型与实现与实现与实现与实现与实现与实现与实现与实现-TSPTSP15828.72013-11-269蚁群算法的模
54、型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型与实现与实现与实现与实现与实现与实现与实现与实现-TSPTSP15601.9蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型与实现与实现与实现与实现与实现与实现与实现与实现-TSPTSP1. 同一个函数同一个函数同一个函数同一个函数，两次的结果并不是完全的一两次的结果并不是完全的一两次的结果并不是完全的一两次的结果并不是完全的一致致致致，因为在蚁群初始化时位置是随机产生的因为在蚁群初始化时位置是随机产生的因为在蚁群初始化时位置是随机
55、产生的因为在蚁群初始化时位置是随机产生的。说明该算法的解具有不确定性说明该算法的解具有不确定性说明该算法的解具有不确定性说明该算法的解具有不确定性。2. 两次优化的结果分别为两次优化的结果分别为两次优化的结果分别为两次优化的结果分别为15828km和和和和15601km，而现在有的算法可以优化到而现在有的算法可以优化到而现在有的算法可以优化到而现在有的算法可以优化到15377km，因此因此因此因此寻找的寻找的寻找的寻找的最佳路径即为最佳路径即为最佳路径即为最佳路径即为局部最局部最局部最局部最优值优值优值优值并不是全局最优值并不是全局最优值并不是全局最优值并不是全局最优值。蚁群算法的模型蚁群算法
56、的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型与实现与实现与实现与实现与实现与实现与实现与实现-TSPTSP蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型蚁群算法的模型与实现与实现与实现与实现与实现与实现与实现与实现-TSPTSP1. 路径的最短距离在算法迭代到路径的最短距离在算法迭代到路径的最短距离在算法迭代到路径的最短距离在算法迭代到约约约约120次时次时次时次时即蓝色实线基本保持不再发生变化即蓝色实线基本保持不再发生变化即蓝色实线基本保持不再发生变化即蓝色实线基本保持不再发生变化，说明选找说明
57、选找说明选找说明选找到极值点到极值点到极值点到极值点。2. 同时路径的平均距离在算法迭代到同时路径的平均距离在算法迭代到同时路径的平均距离在算法迭代到同时路径的平均距离在算法迭代到100次次次次左右时左右时左右时左右时，在值为在值为在值为在值为18500上下小范围内波动上下小范围内波动上下小范围内波动上下小范围内波动，基基基基本趋于稳定本趋于稳定本趋于稳定本趋于稳定。蚁群算法蚁群算法蚁群算法蚁群算法 蚁群算法蚁群算法蚁群算法蚁群算法的优点的优点的优点的优点1. 蚁蚁蚁蚁群算法与其他启发式算法相比群算法与其他启发式算法相比群算法与其他启发式算法相比群算法与其他启发式算法相比，在在在在求解求解求解
58、求解性能性能性能性能上上上上，具有很强的鲁棒性具有很强的鲁棒性具有很强的鲁棒性具有很强的鲁棒性（对基本蚁群对基本蚁群对基本蚁群对基本蚁群算法算法算法算法模型模型模型模型稍加修改稍加修改稍加修改稍加修改，便可以应用于其他问题便可以应用于其他问题便可以应用于其他问题便可以应用于其他问题）和和和和搜搜搜搜索索索索较好解的较好解的较好解的较好解的能力能力能力能力。2. 蚁蚁蚁蚁群算法是一种基于种群的进化算法群算法是一种基于种群的进化算法群算法是一种基于种群的进化算法群算法是一种基于种群的进化算法，具有具有具有具有本质本质本质本质并行性并行性并行性并行性，易于并行易于并行易于并行易于并行实现实现实现实现
59、。3. 蚁蚁蚁蚁群算法很容易与多种启发式算法群算法很容易与多种启发式算法群算法很容易与多种启发式算法群算法很容易与多种启发式算法结合如遗结合如遗结合如遗结合如遗传算法传算法传算法传算法、粒子群算法粒子群算法粒子群算法粒子群算法，以改善以改善以改善以改善算法性能算法性能算法性能算法性能。蚁群算法蚁群算法蚁群算法蚁群算法 蚁群算法蚁群算法蚁群算法蚁群算法的不足的不足的不足的不足1. 如果初始化参数设置不当如果初始化参数设置不当如果初始化参数设置不当如果初始化参数设置不当，导致导致导致导致求解求解求解求解速度速度速度速度很慢很慢很慢很慢且所得解的质量特别差且所得解的质量特别差且所得解的质量特别差且所
60、得解的质量特别差。2. 基本基本基本基本蚁群蚁群蚁群蚁群算法即无改进的蚁群算法计算量算法即无改进的蚁群算法计算量算法即无改进的蚁群算法计算量算法即无改进的蚁群算法计算量大大大大，求解求解求解求解所需时间较长所需时间较长所需时间较长所需时间较长。3. 基本基本基本基本蚁群蚁群蚁群蚁群算法枞论上算法枞论上算法枞论上算法枞论上要求所有的蚂蚁要求所有的蚂蚁要求所有的蚂蚁要求所有的蚂蚁选择选择选择选择同同同同一路线一路线一路线一路线，该线路即为所求的最优线路该线路即为所求的最优线路该线路即为所求的最优线路该线路即为所求的最优线路；但但但但在在在在实际实际实际实际计算中计算中计算中计算中，在给定一定循环数
61、的条件下在给定一定循环数的条件下在给定一定循环数的条件下在给定一定循环数的条件下很难很难很难很难达到达到达到达到这种情况这种情况这种情况这种情况。2013-11-2610蚁群算法蚁群算法蚁群算法蚁群算法 蚁群算法蚁群算法蚁群算法蚁群算法的的的的改进改进改进改进1. 最优解最优解最优解最优解保留策略保留策略保留策略保留策略（Ant System with Elitist）该该该该策略能够以更快的速度获得最好解策略能够以更快的速度获得最好解策略能够以更快的速度获得最好解策略能够以更快的速度获得最好解，但是但是但是但是如如如如果果果果选择的精英过多则算法会由于较早收敛于选择的精英过多则算法会由于较早
62、收敛于选择的精英过多则算法会由于较早收敛于选择的精英过多则算法会由于较早收敛于局局局局部部部部次优解而导致搜索的过早停滞次优解而导致搜索的过早停滞次优解而导致搜索的过早停滞次优解而导致搜索的过早停滞。2. 局部局部局部局部信息素更新信息素更新信息素更新信息素更新使使使使已选已选已选已选的路径对的路径对的路径对的路径对后来的蚂蚁具有较小的后来的蚂蚁具有较小的后来的蚂蚁具有较小的后来的蚂蚁具有较小的影响影响影响影响力力力力，从而从而从而从而使蚂蚁对没有选中使蚂蚁对没有选中使蚂蚁对没有选中使蚂蚁对没有选中的路径有的路径有的路径有的路径有更强更强更强更强的的的的探索探索探索探索能力能力能力能力。蚁群算
63、法蚁群算法蚁群算法蚁群算法 蚁群算法蚁群算法蚁群算法蚁群算法的的的的改进改进改进改进3. 最大最大最大最大-最小最小最小最小蚂蚁系统蚂蚁系统蚂蚁系统蚂蚁系统（max-min ant system）（1）每次迭代每次迭代每次迭代每次迭代后后后后，只有只有只有只有最优解最优解最优解最优解（最优蚂蚁最优蚂蚁最优蚂蚁最优蚂蚁）所所所所属属属属路径上的信息被更新路径上的信息被更新路径上的信息被更新路径上的信息被更新；（2）为了避免过早收敛为了避免过早收敛为了避免过早收敛为了避免过早收敛，将各条路径可能的将各条路径可能的将各条路径可能的将各条路径可能的信信信信息素息素息素息素限制于限制于限制于限制于min
64、 ,max；（3）在算法初始时刻在算法初始时刻在算法初始时刻在算法初始时刻，取较小取较小取较小取较小值值值值，算法算法算法算法有有有有更更更更好的好的好的好的发现较好解的能力发现较好解的能力发现较好解的能力发现较好解的能力。 随着迭代次数的增随着迭代次数的增随着迭代次数的增随着迭代次数的增加加加加， 变大加快算法的收敛变大加快算法的收敛变大加快算法的收敛变大加快算法的收敛。蚁群算法蚁群算法蚁群算法蚁群算法 蚁群算法蚁群算法蚁群算法蚁群算法的应用的应用的应用的应用1. 控制工程控制工程控制工程控制工程、电力工程电力工程电力工程电力工程、交通工程交通工程交通工程交通工程2. 网络网络网络网络工程工
65、程工程工程、通信通信通信通信、计算机科学计算机科学计算机科学计算机科学3. 管枞工程管枞工程管枞工程管枞工程、化工化工化工化工、信息科学信息科学信息科学信息科学4. 组合优化问题组合优化问题组合优化问题组合优化问题：作业调度问题作业调度问题作业调度问题作业调度问题（Job-shop sheduling problem）二次分配问题二次分配问题二次分配问题二次分配问题（quadratic assignment problem）旅行商问题旅行商问题旅行商问题旅行商问题（traveling salesman problem）群智能优化的特点与不足群智能优化的特点与不足群智能优化的特点与不足群智能优化
66、的特点与不足共同特点共同特点共同特点共同特点：基于概率计算的随机搜索进化算法基于概率计算的随机搜索进化算法基于概率计算的随机搜索进化算法基于概率计算的随机搜索进化算法，在结在结在结在结 构构构构、研究内容研究内容研究内容研究内容、方法以及步骤上有较大的相似性方法以及步骤上有较大的相似性方法以及步骤上有较大的相似性方法以及步骤上有较大的相似性；结果偏随机性结果偏随机性结果偏随机性结果偏随机性。存在的问题存在的问题存在的问题存在的问题：（1）数学理论基础相对薄弱数学理论基础相对薄弱数学理论基础相对薄弱数学理论基础相对薄弱；（2）参数设置没有确切的理论依据参数设置没有确切的理论依据参数设置没有确切的
67、理论依据参数设置没有确切的理论依据，对具体问对具体问对具体问对具体问题和应用环境的依赖性大题和应用环境的依赖性大题和应用环境的依赖性大题和应用环境的依赖性大；群智能优化的特点与不足群智能优化的特点与不足群智能优化的特点与不足群智能优化的特点与不足进一步的改进进一步的改进进一步的改进进一步的改进：（1）进一步研究真实群居动物的行为特征进一步研究真实群居动物的行为特征进一步研究真实群居动物的行为特征进一步研究真实群居动物的行为特征，建立合适的数学模型建立合适的数学模型建立合适的数学模型建立合适的数学模型；（2）进一步研究算法的收敛性进一步研究算法的收敛性进一步研究算法的收敛性进一步研究算法的收敛性
68、；群智能优化的特点与不足群智能优化的特点与不足群智能优化的特点与不足群智能优化的特点与不足进一步的改进进一步的改进进一步的改进进一步的改进：（3）进一步提高收敛速度进一步提高收敛速度进一步提高收敛速度进一步提高收敛速度，从而解决大从而解决大从而解决大从而解决大规模优化问题规模优化问题规模优化问题规模优化问题；（4）进一步研究各种参数设置问题进一步研究各种参数设置问题进一步研究各种参数设置问题进一步研究各种参数设置问题；（5）研究群智能的并行算法研究群智能的并行算法研究群智能的并行算法研究群智能的并行算法；（6）进一步研究各算法的适用范围进一步研究各算法的适用范围进一步研究各算法的适用范围进一步研究各算法的适用范围；（7）研究与其它算法的混合技术研究与其它算法的混合技术研究与其它算法的混合技术研究与其它算法的混合技术。
