蚁群优化算法

mypro334

蚁群优化算法
蚁群优化(AntcofonyOpti而zation,AcO)是Mare。Dorign等学者在真实蚂蚁觅食行为的启发下提出的一种具有高度创新性的元启发式算法。这种新型的优化算法已经得到广泛的认可,其应用从TSP问题扩展到了优化问题领域的各个方面,算法设计得到不断的改进,逐渐构筑起一套成熟的算法框架。目前,蚁群优化己经成为组合优化领域最具有潜力的算法之一,成为众多学者的研究焦点。
1 蚂蚁的觅食行为及其优化过程
蚂蚁群体,或者是具有更普遍意义的群居昆虫群体,都可以看作一个分布式系统。虽然系统中的个体都非常简单,但是整个系统却呈现出一种高度结构化的群体组织。正是由于这个群体组织的存在,蚂蚁群体才得以完成一些远远超出单只蚂蚁个体能力负荷的复杂工作。
很多种类的蚂蚁所具有的视觉感知系统都是发育不全的,甚至有些种类的蚂蚁是完全没有视觉的。事实上,关于蚂蚁行为的早期研究表明,群体中的个体之间以及个体与环境之间的信息传递大部分都是依赖于蚂蚁产生的化学物质进行的。人们把这种化学物质称为信息素伊heromone)。蚂蚁这种特有的信息传递方法,不同于人类以及其他高级种群之间所使用的以视觉和听觉为主的感知方式。对于某些蚂蚁来说,在它们的群居生活中,最重要的是路径信息素(Trailpheromone)的使用。这是一种特殊的信息素,某些种类的蚂蚁,例如Lasiusniger或阿根廷蚂蚁Iridomynnexhumilis,使用路径信息素来标记地面上的路径,例如从食物源到蚁穴之间的路径等。蚂蚁正式通过感知由其他蚂蚁释放的路径信息素来沿途找到食物的所在地。这种根据其他蚂蚁所释放的化学物质信息来影响蚂蚁群体的路径选择的行为方式正是ACO算法的灵感来源。
很多种类的蚂蚁在觅食时,都是以信息素作为媒介而间接进行信息传递的。当蚂蚁从食物源走到蚁穴,或者从蚁穴走到食物源时,都会在经过的地面上释放信息素,从而形成了一条含有信息素的路径。蚂蚁可以感知路径上信息素的浓度大小,并且以更高的概率选中信息素浓度最高的路径。
目前己有学者对某些种类的蚂蚁通过信息素浓度选择路径的行为进行过可监控的试验。其中最为巧妙的是由Deneubourg及其同事设计完成的双桥试验。他们使用了一个双桥来连接阿根廷蚂蚁I.humilis的蚁穴和食物源。他们在试验的过程中测试了一组不同比例的r=ll/ls值,其中r是双桥上两个分支之间的长度比例,ll是较长分支的长度,而Is是较短分支的长度。双桥试验的试验设置如图4.3所示。
在第一个试验中,桥上的两个分支长度相同,如图4.3(a)所示。开始的时候蚂蚁可以自由地在蚁穴和食物源之间来回移动,试验目的就是观测蚂蚁随时间选择两条分支中某一条的百分比。试验的最终结果显示尽管最初蚂蚁通常随机选择某一条分支,但是最后所有的蚂蚁都会选择同一条分支。这个试验结果可以用一下方法进行解释。由于刚开始时两条分支上都不存在信息素,因此蚂蚁对这两条分支的选择就不存在任何偏向性,以相同的概率在这两条分之间进行选择。然而由于随机波动的出现,选择某一条分支的蚂蚁数量可能会比另一条多。正式因为蚂蚁在移动的过程中会释放信息素,那么当有更多的蚂蚁选择某条分支时,将会导致这条分支上的信息素总量比另外一条多;而这种更高浓度的信息素将会促使更多的蚂蚁再次选择这一条分支,这个过程一直进行,直到最后所有蚂蚁都集中到某一条分支路径上。这种正反馈的过程,实际上就是蚂蚁实现自组织行为的一个例子,一种宏观模式的出现来自于微观层次上的过程与交互作用。在试验中,蚂蚁的路径集中到某一条分支上的过程显示的是宏观上的群体行为,此行为可以通过蚂蚁的微观行为得到解释,也就是通过群体中个体之间的局部交互过程来解释。同时这也是媒介质通信的一个例子:蚂蚁在移动的过程中,利用周围环境的变化信息间接进行信息传递,从而调整他们自身的群体行为。



在第二个试验中,两条分支的长度比例设定为r=2,因此较长的那条分支的长度是较短那条的两倍,如图4.3(a)所示。在这种设置条件下,大部分试验结果显示,经过一段时间后所有的蚂蚁都会选择较短的那条分支。与第一个试验一样,蚂蚁离开蚁穴探索环境,他们到达了一个决策点,在这里需要在两条分支间做出选择。一开始两条分支对蚂蚁来说都是一样的,因此他们会随机选择两条中的一条。正因为这样,尽管有时会由于出现一些随机摆动而使得某一条分支比另外一条分支上的蚂蚁数量多,但平均而言,我们仍然可以期望会有一半的蚂蚁选择较短的分支,而另外一半选择较长的分支。然而,此试验由于一条分支比另外一条分支短,选择了较短分支的那些蚂蚁会首先到达食物源,并开始返回他们的巢穴。当返回的蚂蚁需要在短分支和长分支之间作出选择时,短分支上的高浓度信息素将会影响它们的决定。正因为短分支上的信息素积累速度要比长分支的快,根据先前提到的正反馈过程,最终所有蚂蚁都会选择较短的那条分支。与两条分支长度相同的试验相比,在本试验中初始随机波动的影响大大减少,起作用的主要是媒介质、正反馈和差异路径长度等机制。另外,根据观察,虽然较长的分支是短分支长度的两倍,但并不是所有蚂蚁都会使用较短的分支,相反有很小比例的蚂蚁会选择较长的分支。这种情况可以解释为一种“路径探索”行为。
2 求解旅行商问题的基本ACO算法
旅行商问题(Taveling salesman problem,TSP)是一个为学术界广泛研究的问题,在ACO算法的研究中,TSP同样起着重要的作用,第一个ACO算法—蚂蚁系统(Antsystem),以及随后提出的大量的ACO算法,都是首先在TSP上进行测试的。选择TSP作为诠释ACO算法的平台原因众多:它是一个涉及多种实际应用领域的重要NP-难优化问题;也是一个便于使用ACO算法解答的问题;更是一个易于理解的问题,因此算法的行为不会被具体的应用技术细节所掩盖;它还是新算法思想的标准测试平台—一个算法能够在TSP上展示出良好的性能往往称为该算法有效性的证明。此外,ACO算法的发展历程告诉我们,应用于TSP上最有效的ACO算法,通常也是解决其他各种各样问题的最有效的算法。
(l)旅行商问题
直观的说,TSP就是指一位商人,从自己的家乡出发,希望能找到一条最短路径,途经给定的城市集合中的所有城市,最后返回家乡,并且每个城市都被访问一次且仅一次。形式上,TSP可以用一个带权完全图G=（N,A）来描述,其中N是城市的结点集合,



(2)蚂蚁系统
最初蚂蚁系统(AS有3个不同的版本,分别称为蚂蚁密度(ant-density)、蚂蚁数量(ant-quantlty)和蚂蚁周期(ant-cycle)。在蚂蚁密度和蚂蚁数量这两个版本中,蚂蚁从一个城市移动到邻近的城市后就直接更新信息素。然而,在蚂蚁周期这个版本中,只有所有蚂蚁都构建出一条路径之后才执行信息素的更新动作,而且每只蚂蚁所释放的信息素量与它所构建出的路径的好坏密切相关。现在我们所提到的AS实质上是指蚂蚁周期这一个版本的AS,另外两个版本的AS因为其低劣的性能己经遭到淘汰。ACO算法的伪代码如图4.4所示。其中关键的两个步骤是蚂蚁构建问题的解和信息素的更新。
对于AS来说,一种好的初始化信息素的启发方法,就是把信息素的初始值设为略高于每一次迭代中蚂蚁释放的信息素大小的期望值。在AS中,m只蚂蚁并行地构建TSP的路径。最初蚂蚁被分别随机放置到随机选择出来的城市中。在路径构建的每一步中,蚂蚁k按照一个称为随机比例规则的概率选择规则,来决定下一步将移动到哪一个城市。如,当前位于城市i的蚂蚁k选择j作为下一个访问城市的概率是



其中, ηij=1/dij代表一个预先给定的启发式信息,α和β是两个参数,它们分别决定了信息素和启发式信息的相对影响力,Nik代表了位于城市i的蚂蚁k可以直接到达的相邻城市的集合,也就是指所有还没有被蚂蚁k访问的城市的集合。在这个概率规则下,选择某一条边的概率由该边所对应的信息素以及启发式信息决定。参数α和β的作用如下,如果α=0,则最靠近i的城市将很有可能被选出,这相当于一个经典的随机贪心算法。如果β=0,那么就只有信息素的放大系数在起作用,也就是说,算法只使用了信息素,而没有利用任何启发式信息带来的偏向性。这将使得算法的性能变的十分糟糕,特别适当α>1时,算法很快陷入停滞的局面,此时所有的蚂蚁都按照同一路线移动,最后构建出同一条路径,而这条路径却常常与优化目标相距甚远。



信息素更新是AS的另一个重要步骤。当所有的蚂蚁都构建好路径后,各边上的信息素将会被更新。首先,所有边上的信息素都会减少一个常量因子的大小,然后在蚂蚁经过的边上增加信息素。信息素的蒸发根据下面的式子执行





3 对AS算法的改进
随着测试规模的不断扩大,与其他元启发式算法相比,AS算法的性能下降的十分严重。因而大量的ACO的研究工作集中在如何改进AS算法上。表4.1列出了几种主要的ACO算法。下面介绍几种主要的改进算法。





Dorigo等的文章列举的计算结果表明,在EAS中选取一个适当的。值将使得AS算法不但可以得到更好的解路径,而且能够在更少的迭代次数下得到一些更好的解。基于排序的As(简称AS耐)中,蚂蚁释放的信息素大小随着蚂蚁在排列中的先后次序逐渐减少。在信息素更新之前,蚂蚁根据它们构建出来的路径长度按递增的顺序排列,而蚂蚁将要释放的信息素大小的权值由该蚂蚁的排列次序;决定。此外与EAS算法类似,通常至今最优蚂蚁都会在每次迭代中释放更多的信息素。Bullnhelme:等人的试验结果表明,ASrank的性能稍稍优于EAS,而明显优于AS。



上述几种算法都是在AS算法整体结构的基础上进行少量修改的ACO算法,其性能都比AS有明显的提高。另外还有一些特殊的ACO算法,其主要灵感来源于AS算法,但它们使用了未出现在AS中的一些新机制,这些算法如蚁群系统(Ant colony system,ACS)、近似非确定性树搜索(Approximate nondeterministic tree search，ANTS)等。
4 基于蚁群聚类的RBF网络模型
建立RBF网络的关键在于选择合适的基函数中心,RBF网络中心的常用选择方法有K-means聚类法、正交最小二乘法以及进化优化方法。由于多参数反演的输入输出数据维数较多,所需要的隐节点较多,宜采用聚类法确定。K-means聚类法具有简单和速度快等优点,但也存在两个缺点:对初始聚类中心的依赖和收敛到局部最优。蚁群算法是一种全局优化算法,具有分布式、自组织、信息素通信、合作等性能,己经在组合优化、通信网络、机器人等领域取得大量的成果。将蚁群算法用于选择RBF网络基函数中心,提出一种用于复杂问题反演的蚁群聚类RBF(ACCRBF)网络模型。
1 蚁群聚类算法
蚂蚁在觅食等活动中,能够在它所经过的路径上留下称之为信息素的物质,而且能够感知信息素的存在及其强度,并以此引导自己的运动方向。借鉴该原理将数据视为具有不同属性的蚂蚁,聚类中心看作是蚂蚁所要寻找的“食物源”,聚类过程就可以看作蚂蚁寻找食物源的过程。





常用的聚类性能评价函数为类间离散度和:



2 蚁群聚类RBF网络
在RBF网络中共有五个参数需要确定:基函数个数,基函数类型,基函数中心位置,各基函数的扩展常数,输出单元权值矩阵。本文基函数采用常用的高斯函数,对于给定的基函数个数和扩展常数,基函数中心采用蚁群聚类算法确定,权值矩阵计算采用最小二乘法。具体步骤如下:


《来源科技文献，经本人分析整理，以技术会友，广交天下朋友》

闲鱼技术01

大佬牛逼！！！[赞][赞][赞]期末复习有着落了[捂脸]