蚁群算法公式

第１１卷第３６期２０１１年１２月　１６７ｌ一１８１５（２０１１）３６—９０８０—０５　科学技术与工程　Ｓｃｉｅｎｃｅ　Ｔｅｃｈｎｏｌｏｇｙ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｖ０１．１１　Ｎｎ　３６　Ｄｅｃ．２０１１　＠２０１　１　Ｓｃｉ．Ｔｅｃｈ．Ｅｎｇｒｇ．　

计算机技术　

蚁群算法参数分析　

陈一昭　姜麟　

（昆明理工大学理学院，昆明６５００５０）　

摘要介绍了蚁群算法的基本原理。确定了蚁群算法中的主要参数，这些参数对蚁群算法的寻优能力的影响非常之大，有　启发因子　，期望启发因子　，蚁群数量ｍ，信息强度口和信息素会发因子Ｐ等参数，以旅行商问题为例优化以上参数，研究这　些参数的组合情况。首先根据数值试验选定［０，／３，ｍ，Ｑ，ｐ］＝［１．５，４．２，３０，２００，０．５］。固定四个参数，改变一个参数进行数　值试验。得到ａ∈［０．７，１．１］，口Ｅ［３．８，４．５］，Ｑ∈［４００，９５０］和Ｐ∈［０．７，０．９］能得到稳定的全局最优解。　关键词蚁群算法　参数　旅行商问题　中图法分类号ＴＶ３０１．６；　文献标志码Ａ　

蚁群算法是受生物进化论的影响产生的，２０世　

纪９０年代初，意大利学者Ｍ　Ｄｏｒｉｇｏ等人提出了最基　

本的蚁群算法（Ａｎｔ　Ｃｏｌｏｎｙ　Ａｌｇｏｒｉｔｈｍ，ＡＣＡ），他们受　到真实世界的蚁群的行为的影响，在观察蚁群集体觅　

食的过程中，发现蚁群寻找食物的特征，能迅速有效　

地找到食物，和我们所研究的寻优类问题极其相似，　

有助于对这类问题的求解。通过研究蚁群觅食得出　的蚁群算法虽然能有效地找到问题的最优解和它比　

较强的鲁棒性，但是还存在着很多不足，比如收敛速　度较陧、容易出现停滞等现象，基于上述问题，不少学　者提出了改进的蚁群算法。由于算法当中涉及到多　

类参数，这些参数的数值对该算法的影响非常之大，　

一直得不到最佳的参数组合，这个问题困扰了不少学　者，现对蚁群算法中所涉及的各个参数进行分析，以　

探寻解决旅行商问题的最优参数组，找到最佳的参数　组合，使算法运行效率更高　Ｊ。　

蚁群算法java实现以及TSP问题蚁群算法求解

1. 蚁群算法简介

蚁群算法（Ant Clony Optimization， ACO）是一种群智能算法，它是由一群无智能或有轻微智能的个体（Agent）通过相互协作而表现出智能行为，从而为求解复杂问题提供了一个新的可能性。蚁群算法最早是由意大利学者Colorni

A., Dorigo M. 等于1991年提出。经过20多年的发展，蚁群算法在理论以及应用研究上已经得到巨大的进步。

蚁群算法是一种仿生学算法，是由自然界中蚂蚁觅食的行为而启发的。在自然界中，蚂蚁觅食过程中，蚁群总能够按照寻找到一条从蚁巢和食物源的最优路径。图（1）显示了这样一个觅食的过程。

图（1）蚂蚁觅食

在图1（a）中，有一群蚂蚁，假如A是蚁巢，E是食物源（反之亦然）。这群蚂蚁将沿着蚁巢和食物源之间的直线路径行驶。假如在A和E之间突然出现了一个障碍物（图1（b）），那么，在B点（或D点）的蚂蚁将要做出决策，到底是向左行驶还是向右行驶？由于一开始路上没有前面蚂蚁留下的信息素（pheromone），蚂蚁朝着两个方向行进的概率是相等的。但是当有蚂蚁走过时，它将会在它行进的路上释放出信息素，并且这种信息素会议一定的速率散发掉。信息素是蚂蚁之间交流的工具之一。它后面的蚂蚁通过路上信息素的浓度，做出决策，往左还是往右。很明显，沿着短边的的路径上信息素将会越来越浓（图1（c）），从而吸引了越来越多的蚂蚁沿着这条路径行驶。

2. TSP问题描述

蚁群算法最早用来求解TSP问题，并且表现出了很大的优越性，因为它分布式特性，鲁棒性强并且容易与其它算法结合，但是同时也存在这收敛速度慢，容易陷入局部最优（local optimal）等缺点。

TSP问题（Travel Salesperson Problem，即旅行商问题或者称为中国邮递员问题），是一种，是一种NP-hard问题，此类问题用一般的算法是很大得到最优解的，所以一般需要借助一些启发式算法求解，例如遗传算法（GA），蚁群算法（ACO），微粒群算法（PSO）等等。

蚁群算法综述

摘要：群集智能作为一种新兴的演化计算技术已成为越来越多研究者的关注焦点, 其理论和应用得到了很大的发展。作为群集智能的代表方法之一,蚁群算法ACO (Ant Colony

Optimization, 简称ACO) 以其实现简单、正反馈、分布式的优点得到广泛的应用。蚁群算法是由意大利学者M. Dorigo 提出的一种仿生学算法。本文主要讨论了蚁群算法的改进及其应用。在第一章里介绍了蚁群算法的思想起源及研究现状。第二章详细的介绍了基本蚁群算法的原理及模型建立，并简要介绍了几种改进的蚁群优化算法。第三章讨论了蚁群算法的最新进展和发展趋势展望。

关键词：群集智能，蚁群算法，优化问题

1 引 言

1.1 概述

人类的知识都来自于对自然界的理解和感悟，如天上的闪电，流淌的河流，挺拔的高山，汪洋的大海，人们从中学会了生存，学会了征服自然和利用自然。自然界中也存在着很多奇特的现象，水中的鱼儿在发现食物时总能成群结队，天上的鸟儿在迁徙时也是组成很多复杂的阵型，蚂蚁在发现食物时总能找到一条最短的路径。无论鱼儿，飞鸟或是蜜蜂，蚂蚁他们都有一个共同的特点好像有一种无形的力量将群体中的每个个体组织起来，形成一个统一的整体。看似庞杂的种群却又有着莫大的智慧，让他们能够完成一个个体所无法完成的使命。整个群体好像一个社会，形成一个有机整体，这个整体对单个个体要求不高，诸多个体组合起来数量庞大，却极具协调性和统一性，这就是群智能。

群智能算法是利用其个体数量上的优势来弥补单个个体的功能缺陷，使整个群体看起来拥有了个体所无法企及的能力和智慧。单个个体在探索过程的开始都是处于一种盲目的杂乱的工作状态，因此这些个体所能找到的最优解，对于群体而言却并非是最优的而且这些解也都是无规则的，随着越来越多的个体不断探索，单个个体受到其他成员的影响，大量的个体却逐渐趋向于一个或一条最优的路线，原本杂乱的群体渐渐呈现一种一致性，这样整个群体就具有了寻找最优解的能力。我们称这样一个群体是具有收敛特性的。群体智能具有很好的协作性、分布性、鲁棒性的特点。它属于计算机技术的一种演化方式，因此被广大学者不断关注，与人工生命，进化算法，和遗传算法有着广泛的联系。群智能理论的研究主要涵盖两方面的内容:蚁群算法和粒子群优化算法。蚁群算法是对自然界中蚂蚁觅食规则的一种模仿，主要用来解决离散域的优化问题，尤其是在二次优化问题上其应用非常广泛;粒子群优化算法也是群智能算法的一个分类，也是通过模仿自然界中鸟群觅食的过程演化而来的，后来也被广大学者证明是一种很好的优化工具。

蚁群优化算法及其理论进展

摘 要:蚁群优化算法作为一种新的智能计算模式,近年来在理论研究上取得了丰硕成果。本文主要阐述蚁群优化算法的研究成果,论述了算法在离散域、连续域问题上的理论进展,然后对收敛性研究做了介绍。最后,阐述了蚁群优化算法的发展趋势。

关键词:蚁群算法 离散域 连续域 收敛性

中图分类号:tp301.6 文献标识码:a 文章编号:1674-098x(2012)04(a)-0032-02

1 引言

意大利学者dorigo[1]等人根据真实蚂蚁觅食行为,提出了蚁群优化算法的(aco)最早形式—蚂蚁系统(as),并应用在tsp旅行商问题中。该算法采用分布式并行计算机制,易与其他方法结合,具有较强的鲁棒性。as算法提出之后,其应用范围逐渐广泛,已经由单一的tsp领域渗透到了多个应用领域[2],算法本身也不断完善和改进,形成了一系列改进aco算法。

2 蚁群算法理论研究

2.1 基本蚂蚁算法

与真实蚂蚁觅食行为类似,基本蚁群算法主要包括路径选择和信息素更新两个步骤。以蚁群算法求解tsp问题为例[1]:tsp问题可表述成,旅行商走完n个城市有多种走法,每周游完所有城市可得长度为i的路径,它们构成解的集合

。而每个解是依次走过n个城市的路径距离构成的集合,可表示为。

设是在第g次周游中城市i上的蚂蚁数。在算法周游过程中,每只蚂蚁根据概率转换规则生成一个有n步过程的行动路线,整个算法的周游过程以g为刻度,。其中是预先设定的算法最大周游次数,当所有蚂蚁移动一次后,周游次数计数器加1。经过次周游,基本可找到一条最短路径。设,np为算法中总蚂蚁数。

基本步骤为:算法开始时,每条路径上初始信息素设置为常数,并对每只蚂蚁设置随机起始城市。蚂蚁移动过程中,从城市i选择移动到城市j主要是根据概率启发公式(1)来完成,每次选择的城市都是从可选城市列表中取出。

(1)

其中为启发优先系数且。可以改变信息素与启发优先系数的相对重要性。如果则最近的城市容易被选择,这类似经典的随机贪婪算法。如果则只有信息素放大机制在独自工作,这将导致算法迅速收敛于一个可能是非最优的解。