研究背景——蚁群算法数学模型

1、蚁群算法研究及其应用蚁群算法研究及其应用主要内容主要内容1:论文研究背景2:本文改进算法3:蚁群算法参数组合优化4:TSP仿真系统介绍5:本文结论6:致谢研究背景研究背景蚁群算法原理蚁群算法原理 蚂蚁算法是一种用来寻找最优解决方案的机率型技术,其灵感来源于蚂蚁在寻找食物过程中发现最短路径的行为.自然蚂蚁寻找食物行为自然蚂蚁寻找食物行为：蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物(信息素)选择其要走的路径。其选择一条路径的概率与该路径上分泌物的强度成正比。因此，由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象：某一条路径走过的蚂蚁越多，后面的蚂蚁选择该路径的可能性就越大

2、。蚂蚁的个体间通过这种信息的交流寻求通向食物的最短路径。这种优化过程的本质这种优化过程的本质:协调机制：协调机制：蚂蚁间实际上是通过分泌物来互相通信、协同工作的。选择机制：选择机制：信息素越多的路径，被选择的概率越大。更新机制：更新机制：路径上面的信息素会随蚂蚁的经过而增长，而且同时也随时间的推移逐渐挥发消失。研究背景研究背景蚁群算法数学模型蚁群算法数学模型(1)初始时刻( )，各条路径上的信息素相等.选择机制：选择机制：在 t( ) 时刻，蚂蚁在运动过程中根据各条路径上信息素和路径长度因素共同决定移动方向，蚂蚁由位置i移动到位置j 的转移概率的计算公式如下: 本文以著名的旅行商问题(TSP)

3、为例，建立蚁群算法数学模型，该问题可以描述为：一个旅行商从n个城市的某一出发个访问其他所有城市一次且仅一次后再回到出发城市，要求找出一条最短的路径；该问题可抽象像为求完全图( n个节点)的最短路径问题。0t0t0)()()()()(kallowedsisisijijkijallowedjiftttttPk更新机制更新机制：在 t+n时刻，此时所有的蚂蚁完成了一次遍历，为了避免残留信息素过多而淹没距离因素，在每只蚂蚁走完一步或者迭代一次后，要对路径上的信息素进行更新操作，各路径上信息素可根据以下公式做调整：根据计算方式不同，有蚁周模型、蚁量模型和蚁密模型三种基本模型，本文的研究都是基于蚁周模型的

4、，其模型为：mkkijijijijijtnt1)()1 ()(elsejikifLQkkij0),(只蚂蚁在本次迭代中过第研究背景研究背景蚁群算法数学模型蚁群算法数学模型(2)研究背景研究背景蚁群算法研究方向蚁群算法研究方向算法理论改进算法理论改进 参数分析参数分析应用推广应用推广数学证明数学证明1:算法易出现局部最优、停滞等不良现象算法易出现局部最优、停滞等不良现象2:在求解较大规模问题时，算法的运行时间过长在求解较大规模问题时，算法的运行时间过长3:算法的收敛速度慢算法的收敛速度慢4:算法参数的设置带有很强的经验性和随机性，没有严格的理论认证算法参数的设置带有很强的经验性和随机性，没有严格

5、的理论认证 研究表明蚁群算法具有较强的鲁棒性、分布式计算、易于与其优化算法结合等优点；但随着问题规模的扩大，算法的运行时间和最优解都不能认人满意，性能明显下降。大量研究表明蚁群算法也存在一些不足，主要有：蚁群算法研究方向蚁群算法研究方向:算法改进算法改进研究背景研究背景 针对蚁群算法存在的不足，国内外学者开展了大量有意义的研究。研究成果主要涉及路径搜索策略、信息素更新策略和最优解保留策略等方面；研究行为主要是进行算法改进或验证。有些改进算法的性能相比基本蚁群算法而言有了较大水平的提高，如最大最小蚁群算法是目前求解TSP问题的最好方法之一；有些已成为主流的蚁群算法,如：蚁群系统，基于排序的蚁群系

6、统，最优最差蚁群系统等。 针对基本蚁群算法的不足，本文在借鉴其他算法优点的基础上提出一种改进的蚁群算法。该算法从以下几个方面对基本蚁群算法进行了改进： 1:初始信息素的改进初始信息素的改进2:路径选择策略的改进路径选择策略的改进3:信息素更新策略的改进信息素更新策略的改进本文算法改进本文算法改进研究过程研究过程(1) 基本蚁群算法中，路径上的初始信息素大小是相同的，蚁群创建的第一条路径所获得的信息主要是城市之间的距离信息，此时，蚁群算法相当于贪婪算法。第一次循环中蚁群在所经过的路径上留下的信息素不一定能反映出最优路径的方向。正反馈的作用会使得这条不是最优解的路径上的信息素得到不应有的增强，阻碍

7、以后的蚂蚁发现更好的全局最优解。为此，本文改进算法在任意两个城市之间安排的信息素是等量的,但是这等量的信息素要平均到两个之间的路径上,由于城市之间的距离是不相同的,所以平均到每一小段上的信息素量就是距离的倒数与分配到这两城市之间的信息素量之积。为提高初始阶段蚂蚁的搜索能力，改进算法将各路径上的初始信息素的值按照最大最小蚁群算法思想限定其大小。所以其数学模型为：1：初始信息素：初始信息素elsejiifdQijij0)0(maxmin)0(ij本文算法改进本文算法改进研究过程研究过程(2)2:路径选择策略的改进路径选择策略的改进相关文献表明，自然蚂蚁无视觉能力，无法感知距离的远近,在节点选择时，

8、仅能依靠信息素浓度。为更好的模拟自然蚂蚁,本文改进算法在选择下一个城市时不再考虑距离因素,仅考虑信息素浓度。同时为有效的提高优化速度,降低局部最优解停滞的可能性,本文采用伪随机性选择策略,并在搜索过程中动态地调整确定性选择的概率。即蚂蚁 在 t时刻有城市 i 到城市 j 的转移概率由下式确定：0maxPqqifPiualloweduk0)(kallowedkikijtabujtpk3:信息素更新策略策略的改进信息素更新策略策略的改进本文算法改进本文算法改进研究过程研究过程(3)两层信息素更新策略：两层信息素更新策略：第1层:原有信息素的挥发第2层:借鉴奖惩蚁群算法思想，在完成每次循环进行信息素

9、挥发后，根据蚂蚁所建立路径的长短，进行排序，只有前w只建立短路径的蚂蚁被挑选出来进行奖励，其他 (m-w )只建立路径的蚂蚁进行惩罚。最大最小蚁群算法思想：最大最小蚁群算法思想：若某段路径弧段的信息素相对其他路径弧段的信息素而言在数量上占据绝对的优势时,会引起算法过早地收敛。对这一不足,本文借鉴MMAS思想,对各路径上的信息素量施加最小最大限制。采用采用两层信息素更新策略两层信息素更新策略和和最大最小蚁群算法思想最大最小蚁群算法思想)()1 ()(tntijijmwrijwrijijmrwifrwmQntwrifrwmQntnt11)(0)()(maxmin)(tij开始开始初始化初始化蚂蚁构

10、建路径蚂蚁构建路径所有蚂蚁结束？所有蚂蚁结束？路径排序路径排序信息素更新信息素更新满足结束条件？满足结束条件？结束结束NYNY本文算法改进本文算法改进算法流程算法流程本文算法改进本文算法改进性能验证性能验证算法算法平均最优解平均最优解平均迭代次数平均迭代次数平均运行时间平均运行时间(s)基本蚁群算法基本蚁群算法449.353512429最大最小蚁群算法最大最小蚁群算法437.96289829本文改进算法本文改进算法443.992710423文献文献48算法算法439.9628未知未知31文献文献49算法算法447.7771未知未知33TSP51问题各算法性能比较表问题各算法性能比较表算法算法平

11、均最优解平均最优解平均迭代次数平均迭代次数平均运行时间平均运行时间基本蚁群算法基本蚁群算法564.649823839最大最小蚁群系统最大最小蚁群系统559.223819834本文改进算法本文改进算法561.341018926 TSP76问题的实验结果问题的实验结果参数组合优化参数组合优化研究背景研究背景 蚁群算法的参数数目众多，参数对算法性能的影响较大。文献表明:蚁群算法参数的合理组合能够在一定程度上提高算法的全局搜索能力和加快算法的收敛速度，但遗憾的是，目前各参数该如何取值只是根据经验来选取合适的参数值。 针对蚁群算法参数空间大、参数选择难的问题，本文对蚁群算法参数的组合优化问题进行了讨论。

12、采用实例仿真法确定各个参数的合理取值区间，采用粒子群算法首次对蚁群算法的五个重要参数的组合优化问题进行了探讨，提出了基于粒子群的蚁群算法参数最优组合优化方案。参数组合优化参数组合优化研究过程研究过程提出问题提出问题:本文将蚁群算法抽象为一个函数，其五个参数为函数的自变量，则有函数 ，那么参数的连续区域优化问题可以定义为：确定蚁群算法五个主要参数 的值，使得函数 取得最优值。由这个定义我们自然地可以将参数的优化看成一个组合优化问题，而且是一个连续域的组合优化问题。选定方法选定方法:粒子群算法，因粒子群优化算法具有很强的全局优化能力，能较快地收敛于可接受解；而且粒子群优化算法参数少，算法简单易实现

13、，效率较高。解决问题解决问题: 实例仿真法：实例仿真法：综合考虑算法的全局搜索能力和收敛速度两项性能指标，确定各参数的合理区间. 采用采用“三步走三步走”策略确定蚁群算法参数的较优组合：策略确定蚁群算法参数的较优组合： (1)利用实例仿真法确定的各个参数的合理区间 (2)利用粒子群优化算法，确定参数的最佳组合 (3)多次结果，求平均),(Qmf结束初始化生成粒子群循环迭代求全局最佳位置以及最优适应度函数值求每个粒子个体最佳位置移动粒子更新粒子速度向量满足循环条件？开始NYYN参数组合优化参数组合优化关键技术关键技术参数组合优化参数组合优化有效性验证有效性验证参数类型参数类型组组次次参数取值参数

14、取值最优路径长度最优路径长度参数最参数最佳组合佳组合11.604.89340.7547544.721.495.10330.7857554.031.055.08300.8057576.141.014.75340.7467614.87参数随参数随机组合机组合51.351.25200.5018027.062.504.90340.187794.673.505.79400.898059.281.005.00280.5047670.495.305.04460.8028205.24mQ应用推广应用推广研究背景研究背景 蚁群算法提出十几年来，取得了丰硕的应用性成果，主要有：物流配送问题、VRP问题、函数优化问

15、题、车间作业调度问题、网络路由问题、电力系统机器人领域、控制参数组合优化问题、聚类分析、数据挖掘、数字图象处理、生命科学化学工业等等。大量有价值的研究成果将陆续发表，不断地拓宽了其应用领域。 本文主要从算法实现方面进行应用推广。 本文采用软件工程思想，利用软件开发技术，设计并实现了蚁群算法参数训练系统及蚁群算法TSP问题仿真系统；通过参数训练仿真系统，用户可以训练得到蚁群算法参数的理想组合；通过蚁群算法仿真系统，用户可以记录并查看算法求解TSP问题过程的中间数据，最优解及最优路径，查看收敛图，路径收敛趋势图及算法间性能比较图。 应用推广应用推广研究方案研究方案采用方法采用方法：软件工程方法，软

16、件工程方法，UML方法方法模块划分模块划分：关键技术关键技术UML关键类图关键类图CAnt成员属性成员属性int *ptabuint m_dLengthint m_iCityCountint *pAllowedCity成员属性成员属性double *m_distancedouble *m_dTrialdouble *m_dDeltTrailCMapInfo成员方法成员方法CMapInfo(int m_iCityCount)CMapInfo()CAntProjectCAntProject成员属性成员属性CAnt *antsdouble m_dLength成员方法成员方法CAntProject(

17、)CAntProject( )int initMap( )int UpdateTrail( )int GetAnt( )int StartSearch( )CAgent成员属性成员属性double dposiAgentDimdouble dbestiAgentDimdouble dviAgentDimdouble m_dFitnessdouble m_dBestFitness成员方法成员方法CAgent( )CAgent( )int UpdateFitness( )int UpdatePos( )成员方法成员方法Cant( )Cant( )int addcity(int city)int Ch

18、ooseNextCity( )int MoveTo(int city)int MoveToLast( )int UpdateResult( )int Clear( )应用推广应用推广研究结果研究结果主界面主界面收敛趋势图收敛趋势图最佳路径图最佳路径图收敛趋势比较图收敛趋势比较图研究结论研究结论在算法研究方面在算法研究方面:本文改进的蚁群算法，理论上更加接近自然蚂蚁行为；仿真结果表明改进算法降低了算法的运行时间，提高算法的收敛速度，该算法能在求解速度和解的质量上取得一个较好的平衡，该算法是一种有效的算法。在算法参数组合优化方面在算法参数组合优化方面:本文采用实例仿真法，全面分析蚁群算法五个重要参数对算法性能的影响，求得各参数的合理区间；结合粒子群算法，首次全面探讨蚁群算法的五个重要参数的组合优化问题，提出蚁群算法参数组优化方案，该方案突了传统取值的局限性。在算法应用推广方面在算法应用推广方面:本文运用软件开发技术，设计并实现蚁群算法仿