科技信息。本刊重稿ｏ
ｓｃ皿ＮＣＥ＆ＴＥＣⅢ帕ＬｏＧＹ矾ｆＤ砌姒ＴＩＯＮ
２００７年第２８期
蚁群算法的应用研究与发展
杨海１１２王洪国３徐卫志１
（１．山东师范大学信息科学与工程学院山东济南２５００１４：
２．山东交通学院信息工程系山东济南２５００２３；３．山东省科技厅山东济南２５００１１）
【摘要】蚁群算法是一种新兴的模拟进化算法．由于其具有鲁棒性、正反馈、并行分布式计算等特点，迅速得到广泛的应用和发展。本文首
先介绍了蚁群算法的原理和实现方法，进而又对其研究进展和实际应用做了较详细的综述，并对其前景和发展方向进行了展望。
【关键词】蚁群算法；组合优化；进化计算；信息素；人工蚂蚁
Ａ（沁ｎｅｒａＪ
ｏｖｅｒｖｉｅｗ帆Ａｎｔ
ａ
Ｃｏｌｏｎｙ
ＡＩ霉。一ｔ岫ａｎｄ
ｉ缸ＡｐｐＵｃａｔｉｏｎ
【Ａｂｓｔｒａｃｔ】１１Ｉｅ枷６ｃｉａｌ
Ａｎｔ
Ｃｏｌ彻ｙＡ１９０ｒｉｔｈｍ（ＡＣＡ）ｉｓｎｅｗｔｙｐｅ
ｄｅｖｅｌｏｐｅｄ釉ｄｗｉｄｅｌｙｕ８ｅｄｔ｝ｌｅ８ｅｙｅａ玛．ＡＣＡｈａｓｔ｝Ｉｅｆｂａｔｕｒｅｓｏｆｄｅｖｅｌ叩ｍｅｎｔｏｆＡＣＡ印ｐｌｉｃａｔｉ∞∞ｄｉｔｓｆｕｔｕｒｅｐｍｓｐｅｃｔ．
【ｌ【ｅｙｗｏｒｄｓ】锄ｔｃｏｌｏｎｙａ１９０ｒｉｔｈｍ（ＡｃＡ）；ｃ伽ｐｌｉｃ日ｔｅ叩ｔｉｍｉｚａｔｉ∞；ｓｉｍｕｌａｔｅｄｅｖｏｌｕｔｉｏｎａｒｙａ１９０ｒｉｔｈＩＩｌ；ｐｈｅｍｍ∞ｅ；ａｎ访ｃｉａｌ蚰ｔ
ｉｍｉ吼ｉＩｌｇｅｖｏｌｕｔｉｏｎａｒｙｏｐｔｉＩｌｌｉｚａｔｉ蚰ａｌｇｏｒｉｔｈｍｗｈｉｃｈｈ鹅ｂ∞ｎｒ印ｉｄｌｙ
ｍｂｕｓｔ，ｐ∞ｉｔｉｖｅｆｂｅｄｂａｃｋ肌ｄｃ０Ｕａｔｅｒａｌ．Ｔｈｉｓｏｖｅｒｖｉｅｗｉ８ｍａｄｅ∞ｔｌｌｅｔｌｌ∞ｒｙ．
ｏｆ
１．引言
在计算机自动控制领域中，控制和优化始终是两个重要问题。使用计算机进行控制和优化本质上都表现为对信息的某种处理。随着问题规模的日益庞大，特性上的非线性及不确定性等。人们难以建立精确的“数学模型”。于是人们就从生命科学和仿生学中受到启发。提出了许多智能优化方法，为解决复杂优化问题（ＮＰ“ａＴｄ问题）提供了新途径。
蚁群算法是一种优秀高效的组合优化算法。本文将在介绍蚁群算法原理的基础上，进一步对其研究应用现状及发展前景进行比较详细的阐述。
２．基本蚁群算法２．１蚁群算法原理
蚁群算法（ＡｎｔＣｏｌｏｎｙＡｌｇ耐ｔｈｍ，ＡＣＡ）是Ｄ耐ｇｏＭ等人于１９９１年提出的。经观察发现，蚂蚁个体之间是通过一种称之为信息素（ｐｈｅｍｍｏｎｅ）的物质进行信息传递的。在运动过程中，蚂蚁能够在它所经过的路径上留下该种信息素，而且能够感知信息素的浓度．并以此指导自己的运动方向，倾向于朝着信息素浓度高的方向移动。因此，蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。
２．２蚁群算法基本模型
中：
△％。（ｔ）：ｆＱ～，若蚂蚁。在本次循环中经过点ｉ和点’（４）一’【Ｏ．ｏｔｈｅｒｗｉｓｅ
其中Ｑ为常数，ｋ为蚂蚁ｋ在本次循环中所走路径的长度。２．３蚁群算法流程
步骤１：ｎｃ＝Ｏ（ｎｃ为迭代步数或搜索次数）；每条边上的７《（ｏ）＝ｃ（常数），并且△ｆ“＝ｏ；放置ｍ个蚂蚁到ｎ个城市上。
步骤２：将各蚂蚁的初始出发点置于当前解集ｔａｂｕ。（ｓ）中；对每个蚂蚁ｋ（ｋ＝１，…，ｍ），按概率ｍ‘（ｔ）移至下一城市ｊ；将城市ｊ置于ｔａｂｕｋ（ｓ）中。
步骤３：经过ｎ个时刻，蚂蚁ｋ可走完所有的城市。完成一次循环。计算每个蚂蚁走过的总路径长度ｋ。更新找到的最短路径。
步骤４：更新每条边上的信息量嘶＋ｎ）
步骤５：对每一条边置如“－ｏ；ｎｃ＝ｎｃ＋１
步骤６：若ｎｃ＜预定的迭代次数ＮＣ。，则转步骤２；否则，打印出
最短路径，终止整个程序。
２．４影响蚁群算法效果的因素
（１）局部搜索策略人工蚂蚁在选择将要行走的路线时，所采用的策略是随机的局部搜索策略。这个策略主要基于以下两点：①蚂蚁个体保留的“经验”；（爹问题中公开可用的信息素轨迹和局部信息。（２）蚂蚁的内部状态内部状态主要保留了对决策有用的信息，用于计算生成解的价值、优劣度和每个执行步的贡献。
（３）信息素轨迹由于信息素轨迹的正反馈机制。选择某路径的蚂蚁越多，一个执行步得到的回报就越多。该路径对于后继蚂蚁的吸引力也就越大。
（４）蚂蚁决策策略蚂蚁的决策策略是由信息素函数与启发信息函数共同决定的，即概率表。利用基于概率的原理再配合信息紊挥发机制．避免了所有蚂蚁都过早地早熟收敛。
３．基本蚁群算法与其他启发算法的比较
以图论中具有代表性的偈Ｐ问题为例，设有ｎ个城市。蚂蚁数量
为ｍ，ｄ＃（ｉＪ＝ｌ，２，…，ｎ）表示城市ｉ和ｊ之间的距离，ｂ（ｔ）表示在ｔ时刻城市ｉ和ｊ之间的路径上残留的信息量，来模拟实际蚂蚁的信息素浓度。
初始化时，ｍ个蚂蚁被放置在不同的城市上．并赋予每条边上的信息量为％（０）。蚂蚁ｋ的ｔａｂｕ。（禁忌表）的第一个元素赋值为它所在的城市。
ｐ：（ｔ）：｛－ｊｉ：‰Ｊ
｝ｏ．。ｔｌＩ。。“。
知（ｔ＋ｎ）＝（１一ｐ）・７＃（ｔ）＋△ｆｉｊ（ｔ）其中：
用ｐ；义ｔ）表示在ｔ时刻蚂蚁ｋ由城市ｉ转移到城市ｊ的概率，则
Ｅ
ａｕ０１ｗｅｄｔ
（１）
我们用基本蚁群算法求解偈Ｐ问题。将其实验结果与其他几种启
发算法相对比，可以很清楚的发现基本蚁群算法的优点与不足。用于对比的优化算法有：遗传算法（ＧｅｎｅｔｉｃＡｌ蜀ｏｒｉｔｈｍ，ＧＡ）、进化计算Ｐｍ印ｍｌｌｌｉｎｇ，ＥＰ），模拟退火（ＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉｎｇ，ＳＡ），
模拟退火与遗传算法相结合的混合算法（ＡＧ）。蚁群算法参数设为ｍ＝１０，Ｂ＝２，Ｑ＝０．９，ａ＝ｐ＝Ｏ．１，ｔｊ（ｏ）＝（ｎ・Ｌｍｎ）一。
表中迭代次数指获得最优解所需的代数，圆括号内数据为非整数最优解。实验表明．蚁群算法几乎在所有问题上的性能都是最好的。
（Ｅｖｏｌｕｔｉｏｎａｒｙ
其中ａｌｌｏｗｅｄｔ表示蚂蚁ｋ下一步允许走过的城市的集合．它随蚂蚁ｋ的行进过程而动态改变；信息量下ｉｉ（ｔ）随时间的推移会逐步衰减，用ｐ表示信息素挥发系数；ｄ，ｐ分别表示蚂蚁在运动过程中所积累的信息量及启发式因子在蚂蚁选择路径中所起的不同用；１＃（ｔ）为由城市ｉ转移到城市ｉ的期望程度，可根据某种启发算法而定。
经过ｎ个时刻，蚂蚁ｋ走完所有的点，完成一次循环。此时，要根据下面公式更新各路径上的信息量：
（２）
４．蚁群算法的发展
２０世纪９０年代初．蚁群算法首先成功应用于求解旅行商问题。实验证明该算法不但具有智能搜索、全局优化能力。而且具有鲁棒性、正反馈、并行分布式计算等特点，引起了许多学者的关注，不断对算法的收敛速度、搜索能力等方面进行改进，使蚁群算法广泛地应用在国民经济和军事等领域．成为研究热点之一。并不短提出新的改进算法。大部分改进算法主要是从局部搜索策略、蚂蚁内部状态、信息素轨迹更新策略、选择策略四个方面进行改进，都取得了良好的效果。例如：
△％（ｔ）＝∑△％‘（ｔ）
ｋ＝ｌ
（３）
△寸（ｔ）表示蚂蚁ｋ在本次循环中在点ｉ和点ｊ之间留下的信息
量，其计算方法根据计算模型而定，在最常用的ｍｔ
ｃｙｃｌｅ
ｓｙｓｔｅｍ模型
１３
科技信息。本刊重稿ｏ
ＳＣｍＮＣＥ＆ＴＥｃＩ矾０ＬＯＧＹⅨＦＯＲＭＡｌｌ０Ｎ
２００７年第２８期
最大最小蚁群系统ＭＭＡＳ（Ｍ联一ＭｉｎＡｎｔＳｙｓｔｅｍ）、基于排序的蚂蚁系
统（ＡＳｍｋ）、具有变异特征的蚁群算法、自适应蚁群算法等。此外，蚁群
算法还同其他仿生优化算法相融合。诸如蚁群算法与遗传算法的融合、与人工神经网络的融合、与微粒群算法的融合、与人工免疫算法的融合等，都提高了算法的效率。
表１
问题名称
０ｈｖｅｒ３０
ＡＣＳ４２０
（１）目前大部分改进的蚁群算法都是针对于特定问题。普适性不强。同时蚁群算法模型也不能直接应用于实际优化问题。虽然正反馈机制就是一个很好的普合性模型。但还远远不够。因此．急需设计一种通用的蚁群算法普适性模型。
（２）现阶段的蚁群算法还只是模拟了自然蚂蚁很少一部分社会性，例如：信息素机制。仍然有很大的空间去提出更加智能化的蚁群行为。
（３）蚁群算法目前还带有明显的经验性，很多结果只是建立在实验的基础之上。需要逐步奠定其理论基础。
（４）蚁群算法本身具有分布式计算的特性，但其并行化研究还是停留在初步阶段。一旦并行化有了显著的提高，算法的效率将会有极大地提高。
ＴＳＰ问题的多种优化算法对比
ＧＡ４２ｌ
ＥＰ４２０
ＳＡ４２４
ＡＧ４２０
Ｏｐｔｉｍｍ
４２０
（３０城市）迭代次数
Ｅｉｌ５０
（４２０．３７１）［１４７０】
４３２
（Ｎ，Ａ）【３２００】
４２８
（４２３．７４）【４００００】
４２６
科｝的【２４６１７】
４４３
＠，Ａ）【１２６２０】
４３６
（４２０．３７１）
４２６
（５０城市）迭代次数
Ｅｉｌ７５
（４３２．１７２）【２４１２】
５４０
心｜Ａ＝）ｆ２５０００】
５４５
（４２６．８６）【１０００００】
５４２
（Ｎ，Ａ）［６８５１２】
５８０
（Ｎ，Ａ）【２８ｌｌｌ】
５６１
（４２６．８６）
（５）仿生硬件是并行计算环境下的产物，蚁群算法的硬件实现是仿生硬件研究领域中的一个新分支。虽然蚁群算法的硬件实现在理论
和实验方面都取得了进展，但是还存在许多问题需要解决。Ｄ
５４０
【参考文献】
［１］ＤｏｒｉｇｏＭ．，ＱＬＩＩｌｈａｒｄｅｌｌａ
Ａｐｐ加ａｃｈ
ｔｏ
（７５城市）迭代次数
（５４Ｊｏ．３８４）【４３９３】
（Ｎ，Ａ）【８００００】
（５４９．１８）【３２５０００】
（Ｎ，Ａ）【１７３２５０】
蹬｜吣［９５５０６Ｊ
（５４０．３８４）ＬＭ．Ａｍ
ＣｏｌｏｎｙＳｙｓｔｅｍ：ＡＩＥＥＥ
ｃｏｏｐｅｍｔｉｖｅ【棚埘ｉＩＩｇ
Ｏｎ
ｔｈｅＴｈｖｅＫｎｇ
Ｓａｌｅ哪蛐ＰｆＤｂｌｅｍ．ＡｌｇｏｒｉｔＩＩｍ
Ｔｒ蚰８．
ｃｏｍｐｕｔａｔｉ∞，１９９７，ｌ（１）：５３确．
［２］Ｄｏｒｉｇｏ
ＥＶ０１ｕ６０Ｉ唧
Ｉｊｆｅ，
５．蚁群算法的应用
蚁群算法从提出到现在，只有短短的十几年。尽管还没有严格的理论基础，但其研究领域已经得到了极大的拓广。由一维静态优化问题发展到了多维动态优化问题．由离散域问题拓展到了连续域范围内的研究。
（１）蚁群算法应用于静态组合优化问题，其典型代表有旅行商问
Ｍ，ｃ啪Ｇ
Ｄｉ．ＡｍｆｏｒＤｉ∞”ｔｅ
・
ｏｐｔｉｎｌｉｚａｔｉ衄．Ａｒｔｊ矗ｃｉａｌ
ｓｅ８ｒｃｈ
１９９９，５（３）：１３７一１７２．
［３］Ｄ耐ｇｏＭ，Ｍ明ｉｅｚ∞Ｖ，ＡＴ抚ｈＩｌｉｃａｌＲｅ∞ｒｔ９１～１０６．
［４］Ｂ蹄甜ｅｍ：Ａ
ＣｏｌｏｒＩｌｉ．ＰｏＢｉ６ｖｅＦｅｅｄｂａｃｋ鼬ａ
Ｓ妇ｔｅ盯．
ＢＩｌｌｌｌｌｌｌｅｉｍ％ＲＦＨ叭ｌ，ＣＳｔ叫鹪．ＡＮ删Ｒ锄ｄｋ－ｂ粕ｅｄｖｅ雎ｉ∞ｏｆ１１ｌｅ枷
Ｃ咖ｐｕｔａｔｉｏｎａｌＳｔｕｄｙ．Ｔｔ！ｃｈｎｉｃａｌＲｅｐｏｒｔＰＯＭ—０３，９７，Ｉ珊６ｔｕｔｅｏｆ
ｆｈ
Ｍ蚰ａｇｅｎ驰ｎｔｓｃｉｅｎｃｅ，ＵＩｌｉｖｅ商竹０ｆＶｉｅｎｎａ’１９９７．Ａｃｃ印ｔｅｄ
Ｃｅｎｔｒａｌ
Ｐｌｌｂｌｉｃ以佣ｉＩｌ吐陀
题（俺Ｐ）、二次分配问题（ＱＡＰ）、车间调度问题、车辆路径问题等。在动
态优化问题中的应用主要集中在通讯网络方面。这主要是由于网络优化问题的特殊性，如分布计算，随机动态性，以及异步的网络状态更新等．这砦与蚁群算法的特性匹配得较好。例如将蚁群算法应用于ＱＯＳ组播路由问题上，就得到了优于模拟退火（ＳＡ）和遗传算法（ＧＡ）的效果。
（２）在图像处理方面，蚁群算法的离散性和并行性特点对于离散数字图像非常适用。可用于图像分割。还可以对彩色图像进行颜色ｔ化，根据图像特点。设置初始聚类中心，进行聚类分析。
（３）数据聚类。聚类分析通常被用于模式识别、颜色量化和图像分类。它可以帮助用户从海量的数据中辨别数据结构，简化数据的复杂度。使用蚁群算法可以自动搜索任意数据集中的聚类中心。这种方法非常简单有效，它可以避免陷入局部最小值。
（４）学习模糊规则问题：Ｊ．Ｃ∞ｉｌｌ∞等人利用蚁群算法，已经成功从组成系统模糊语言规则的数据中自动地学习模糊规则。
（５）在智能交通系统（ｒｒＳ）中的应用：智能匹配、运输调度、路径选择、多物流配送中心选址问题等．都是智能交通系统中的常见问题。求解上述问题时，蚁群算法由于具有正反馈机制。有比遗传算法、模拟退火更快的收敛速度，具有很强的寻优能力。
６．蚁群算法的展望
蚁群算法的研究与应用还是一个全新的课题。很多方面都需要进一步完善和发展。
Ｅｕｒｏｑ）ｅ帅Ｊｏｕｍａｌｆｏｒ０ｐｅｍｔｉｏ哪Ｒｅｓｅａｒｃｈａｎｄ
Ａｎａｌｏｇｕｅ
Ａｐｐｍａｃｈ
Ｅｋｏｎ砌ｃｓ．
ｔｏ
［５］ＲＤｕｒｂｊｎ，Ｄ
Ｗｉｕ８ｈ洲．Ａｎ
ｔｈｅ
Ｔｒ盯ｅｌｌｉＩｌｇ
Ｓａｌ船Ⅱ啪
ＰＩｏｂｌｅｍ
ｕ８ｉＩｌｇ柚Ｅｌａ８ｔｉｃＮｅｔＭｅｔｈｏｄ．Ｎｇ山他，１９８７（３２６）：６８９撕９１．
［６］丁建立、陈增强、袁著址．遗传算法与蚂蚁算法的融合［Ｊ］．计算机研究与发展，２００３，４０（９）：１５３ｌ—１５３６．
［７］吴庆洪、张纪会、徐心和．具有变异特征的蚁群算法［Ｊ］．计算机研究与发展，
１９９９。３“ｌｏ）：１２４叽１２４５．
［８］顾军华等．基于蚂蚁算法的Ｑｏｓ组播路由问题求解［Ｊ］．河北工业大学学报．２００２，３１（４）：１９—２４．
［９］段海滨．《蚁群算法原理及其应用》［Ｍ］．科学出版杜，２∞５年１２月第ｌ版．
［１０］李士勇等．《蚁群算法及其应用’［Ｍ］．哈尔滨工业大学出版社，２００４年９月第ｌ版．
［１１］姜长圆．蚁群算法的理论及应用［Ｊ］．计算机时代，２００４，（６）：ｌ一３．
［１２】徐精明等．多态蚁群算法［Ｊ］冲国科学技术大学学报，２００５，３５（１）：５９撕５．作者简介：杨海（１９８０－），男，硕士研究生，主要从事优化算法和智能交通系统的研究。
王洪国，博士后，教授，硕士生导师。徐卫志，硕士研究生。
※基金项目：山东省自然科学基金（Ｑ２００６Ｇ０３）。
【责任编辑：韩铭】
（上接第２８页）究培养教育科研师资：北京师范大学外语系已把行动研究列入教师职前教育课程中：北京外国语大学中国外语教育研究中心也把教学行动研究作为高校外语师资培养重要途径的课题。列入其重点研究课题中。
３．结论
教学行动研究肯定了教师作为研究者的主体身份，重新定位了教师与学生在研究性学习中的角色。同时从研究目的与方向。具体过程途径上帮助教师循序渐进地提高教学水平和研究质量，最后将其纳入到学校课程管理与评价体系有利于教师研究的可持续发展。在解决英语课程教学理论与实践相脱节的问题的同时满足了广大英语教师进行研究的需要，使教师不仅仅成为课程实践者。并且也成为研究者即研究型教师。教师在行动研究过程中通过对自己教学行为不间断的、直接或间接的观察与反思。通过与专业研究人员或其他合作者的交流不断地加深对自身的认知、对教学实践的理解。这样，行动研究就超越
展”的一个过程并最终促成了新型“学校文化”的建立。我们英语教师应该积极地开展或参与教学行动研究，使自己增强反思意识和能力。提高教学质量，逐步走上自我指导和专业化可持续发展之路，接受新
时期对我们提出的挑战。１２１，
【参考文献ｌ
［１］蔡基刚．大学英语教学：回顾、反恩和研究【Ｍ】．上海：复旦大学出版社，２００６．［２］黄远振．新课程英语教与学．福建：福建教育出版社，２００３．
［３］刘良华墩育行动研究ｍ．教育理论与实践，２００ｌ，（３）．
［４］裴娣娜．教育研究方法导论【Ｍ１．安徽：安徽教育出版社．１９９５．［５］王蔷．英语教师行动研究ｆＭｌ．北京：外语教学与研究出版社，２００２．［６］吴宗杰．行动研究：外语师资教育新途径［Ｊ】．外语教学研究，１９９５，（２）．［７］钟启泉．现代课程论【Ｍ】．上海：上海教育出版社，２００３．
了传统上对“研究”功能的界定——真理知识的增加。而成为“人的发
１４
【责任编辑：翟成梁】
蚁群算法的应用研究与发展
作者：作者单位：
杨海， 王洪国， 徐卫志
杨海(山东师范大学信息科学与工程学院,山东,济南,250014;山东交通学院信息工程系,山东,济南,250023)， 王洪国(山东省科技厅,山东,济南,250011)， 徐卫志(山东师范大学信息科学与工程学院,山东,济南,250014)科技信息（科学·教研）
SCIENCE & TECHNOLOGY INFORMATION2007，""(28)1次
刊名：英文刊名：年，卷(期)：被引用次数：
参考文献(12条)
1. Dorigo M. Gambardella L M Ant Colony System:A Cooperative Learning Approach to the TravelingSalesman Problem 1997(01)
2. Dorigo M. Caro G Di Ant Algorithms for Discrete Optimization 1999(03)
3. Dorigo M. Maniezzo V. A Colorni Positive Feedback as a Search Strategy[Technical Report 91～106]4. B Bullnheimer. R F Hartl. C Strauss A New Randk-based Version of The ant System:A ComputationalStudy[Technical Report POM-03/97] 1997
5. R Durbin. D Willshaw An Analogue Approach to the Travelling Salesman Problem Using an Elastic NetMethod 1987(326)
6. 丁建立. 陈增强. 袁著址 遗传算法与蚂蚁算法的融合[期刊论文]-计算机研究与发展 2003(09)7. 吴庆洪. 张纪会. 徐心和 具有变异特征的蚁群算法[期刊论文]-计算机研究与发展 1999(10)8. 顾军华 基于蚂蚁算法的QoS组播路由问题求解[期刊论文]-河北工业大学学报 2002(04)9. 段海滨 蚁群算法原理及其应用 200510. 李士勇 蚁群算法及其应用 2004
11. 姜长圆 蚁群算法的理论及应用[期刊论文]-计算机时代 2004(06)12. 徐精明 多态蚁群算法[期刊论文]-中国科学技术大学学报 2005(01)
相似文献(10条)
1.期刊论文 许刚. 张土乔. 吕谋. 吴小刚. XU Gang. ZHANG Tu-qiao. LU Mou. WU Xiao-gang 给水管网管径组合优化的极大极小蚁群算法 -哈尔滨工业大学学报2006,38(5)
蚁群算法作为模仿蚂蚁寻找食物的进化算法已经成功的应用于许多组合优化领域.针对其在给水管网管径组合优化设计过程中的计算时间长,易陷入局部极小点等问题,提出了单只蚂蚁更新外激素值,并使外激素值限定在一定范围内的基于二进制编码的极大极小蚁群改进算法,并编制了相应的程序代码.将该方法运用到某小区管网的管径组合优化,结果表明,改进的蚁群算法与基本的蚁群算法相比,更容易实现全局最优解,且计算时间较短.
2.学位论文 曾艳 蚁群算法在组合优化中的应用 2006
组合优化中的许多问题是NP-完全问题，也是科学和工程计算中重要和基本的问题，这类问题的求解一直是算法研究领域的热点问题。对于NP-完全的组合优化问题，至今尚无很好的解析算法，一般采用启发式算法来解决。蚁群算法作为一种新的启发式算法，它具有正反馈、分布式计算以及结构性的贪心启发等特点，使其能够成功地解决许多NP-完全的组合优化问题。本文在详细介绍蚁群算法原理的基础上，对蚁群算法在组合优化问题中的应用进行分析和研究，主要将蚁群算法应用于求解最大团和最大割两个经典的NP-完全组合优化问题，本文主要做了以下工作：
1、在研究已有的最大团问题的蚁群算法以及对蚁群算法深入分析的基础上，根据最大团问题的特点，提出了最大团问题的新型蚁群算法，通过大量的仿真试验证明，算法的性能明显提高了。
2、以最大团问题为例，对蚁群算法的参数进行了深入研究，并提出了使用动态局部启发信息的改进策略。仿真试验证明，该方案使算法的性能得到一定的提高。
3、在研究了组合优化问题基础上，提出了最大割问题的蚁群算法方案。大量的仿真试验证明，该方案能较成功地解决最大割问题。
3.期刊论文 邓玉芬. 向凤红. Deng Yufen. Xiang Fenghong 蚁群算法在组合优化中的应用 -电子测量技术2007,30(1)
本文介绍了崭新的求解复杂优化问题的启发式算法-蚁群算法以及它的基本原理.该算法是通过模拟蚁群搜索食物的过程,达到求解此类问题的目的.它具有智能搜索、全局优化、稳健性强、分布式计算、易与其他方法结合等优点.文章还介绍了该算法在静态组合优化,如旅行商、二次分配、车间任务调度、车辆路线、图着色、有序排列,以及动态组合优化中的应用.文章最后展望了蚁群算法所具有的广阔应用前景.
4.期刊论文 孙泽宇. 邢萧飞 求解自适应组合优化蚁群算法的研究 -计算机工程与应用2009,45(35)
,提出了自适应组合优化蚁群算法.通过对改变信息素的迭代、参数选择的分析和增加对信息素局部更新方式,提高了整个系统运算速度及收敛速度,扩充了优化的范围,克服了无用迭代码的产生,减少了停滞现象的出现.通过该算法对旅行商问题进行仿真实验,其结果表明了该算法的可行性和有效性.
5.期刊论文 马烁. 王安平. 赵天玉. MA Shuo. WANG An-ping. ZHAO Tian-yu 蚁群算法及其在组合优化中的应用 -咸阳师范学院学报2008,23(2)
蚁群算法是近年来新出现的一种启发式仿生算法,该算法为求解复杂的组合优化问题提供了一种新思路,引起众多学者的研究兴趣.本文首先介绍了蚁群算法的原理和实现方法,进而又对其在组合优化中的实际应用做了较详细的研究,并对其前景及发展方向进行了展望.
6.学位论文 陈佑健 蚁群算法的研究及在网络路由优化上的应用 2005
蚁群算法是一种新型的用于求解组合优化或函数优化问题的元启发式算法,其基本思想是借用生物界的蚂蚁群体觅食机理,将每个蚂蚁看作一个智能体,作为智能群体的蚁群,其觅食过程显现出高度的并行性、正反馈性和鲁棒性,以此为基础的蚁群算法也具有这样一些特点.因此,蚁群算法的研究无论从理论上还是实用上,都具有较高的价值.本文首先分析了蚁群算法的原理与模型,介绍了算法的特点和研究现状,通过实验分析了算法中几个关键参数的选择.针对基本蚁群算法的主要缺陷,如收敛速度慢和易于陷入局部最优等问题,将用于求解组合优化问题的基本蚁群算法进行了改进.首先,在概率选择上采用了确定性与随机性相结合的选择原则;其次,由于基本蚁群算法初期时各条路径上的信息素数量相同,导致算法的初期求解速度缓慢,因此提出了分区搜索的思想,使各条路径上的信息素在初期有所差别,加速算法的收敛;第三,结合局部与全局信息素调整策略对路径上的信息素进行动态更新;第四,对与信息素相关的一些参数进行了自适应改变;最后,引入遗传算法中的变异思想,以扩大解的搜索空间.针对蚁群算法在求解连续优化问题上相对较弱的特点,提出了基于网格划分的蚁群算法,将传统的用于求解离散空间优化问题的蚁群算法进行了扩展.在应用研究上,分析了网络路由优化问题,研究了基于蚁群算法的IP网络QoS单播路由;讨论了基于蚁群算法的一些其它应用.通过算例对所提出的改进的蚁群算法进行了仿真验证,实验结果表明,本文提出的改进算法是有效和可行的;在连续函数优化上和基于蚁群算法的网络路由优化等应用上也进行了实验仿真.本课题旨在为推进蚁群算法的理论研究和应用研究起到一定的作用.
7.期刊论文 何幼林. 欧福军. 魏华实. 徐健. 张雍吉 蚁群算法的原理及其在组合优化中的应用 -黑龙江科技信息2008,""(1)
蚁群优化算法是近年来出现的一种新的启发式搜索算法.首先介绍了蚁群算法的基本原理,然后讨论了其在组合优化中的应用,最后分析了蚁群算法的一些基本特点.
8.学位论文 于永彪 基于混合蚁群算法的离散变量结构截面优化方法研究 2007
结构优化设计是近四十年发展起来的一门新技术，与传统设计相比，由于其具有设计合理、节省原材料等特点日益受到国内外工程界的广泛重视。结构优化设计可以降低结构重量和材料成本，改进结构的强度、刚度、振动特性、屈曲稳定性等性能，是现代设计制造领域的重要研究方向。随着结构优化设计理论和方法的迅速发展，离散变量结构优化设计越来越得到关注。离散变量结构优化设计在数学上属于组合优化的范畴，组合优化问题属于NP完全类问题，其求解算法属于NP困难问题。
社会性动物的群体活动往往能产生惊人的自组织行为，个体行为显得盲目的蚂蚁在组成蚁群后能够发现从蚁巢到食物的最短路径。生物学家经过仔细研究发现蚂蚁之间通过一种称之为“信息素”的物质进行间接通讯、相互协作来发现最短路径。受其启发，意大利学者Dorigo.M等于1991年提出一种群体智能算法一蚁群算法(ACO)，该算法自提出以来在计算机科学领域和优化领域中受到广泛关注，在求解旅行商、二次分配、生产安排调度、网络路由、函数优化等问题方面得到了广泛应用，显示了该算法在求解组合优化问题方面的优越性。 本文围绕蚁群算法在离散变量结构截面优化设计中的应用，进行了如下工作：
1、提出了一种混合蚁群算法。在系统地学习研究蚁群算法的原理、数学模型和组合优化应用的基础上，分析三种寻优模式，提出了混合蚁群算法，综合三种不同的寻优模式，调整不同寻优模式蚁群数量的比例，使算法在保持较高搜索能力的同时，避免出现停滞现象。对算法的程序实现进行了研究。
2、分析和研究了混合蚁群算法的参数设置。对该算法应用时的参数选择原则进行了探讨，用于指导参数设置。进行了算法的对比分析和测试函数的验证，表明了混合蚁群算法的良好性能。
3、将混合蚁群算法应用于离散变量结构截面优化设计。针对离散变量结构截面优化设计的性质与特点，对该算法应用时的设计变量、目标函数和约束条件作了概要的分析与研究，拓宽了蚁群算法的应用领域。
4、编制优化程序。运用FORTlRAN语言编制了混合蚁群结构截面优化设计程序，将优化设计程序与大型结构有限元分析软件ALGOR相连接，由该软件完成结构优化程序中的结构分析，使优化设计与结构分析融为一体，从而增强了程序的可靠性，拓宽了ALGOR的使用范围，实现了用ALGOR验证优化设计结果的目的。
5、对优化设计程序在结构中的应用进行了验证。对该程序应用于桁架、框架、网架、网壳结构截面优化设计时的数学模型、约束条件处理及控制参数的选择作了概要的分析与研究。算例结果对比表明该程序是可行的和高效的。
9.期刊论文 李万庆. 李彦苍. LI Wan-qing. LI Yan-cang 求解复杂优化问题的基于信息熵的自适应蚁群算法 -数学的实践与认识2005,35(2)
针对基本蚁群算法存在收敛速度慢、易陷入局部最优、计算复杂且不易求解连续优化问题等缺陷,提出了一种基于信息熵的改进自适应蚁群算法,采用由信息熵控制的路径选择及随机扰动策略实现了算法的自适应调节,克服了基本蚁群算法的不足.典型的NP-hard问题的计箅实例表明,该方法具有较好的收敛性、稳定性和鲁棒性,可用于离散及连续的组合优化问题求解中,其不失为求解复杂组合优化问题的一种较好的方法.
10.学位论文 秦映波 指导变异蚁群算法及其应用 2009
优化技术在许多工程领域有广泛的应用，如系统控制、人工智能、模式识别、生产调试以及计算机工程等。为了克服传统优化方法的不足，人们提出了智能优化方法如遗传算法、模拟退火算法、禁忌搜索算法等。
蚁群算法是一种模拟进化算法，通过模拟蚂蚁在协作搜索食物时的搜索行为来寻求最优解。蚁群算法提出后在组合优化中获得广泛的应用，如调度、二次分配和网络路由等。基于蚁群算法在组合优化实验中的优异性能，改进蚁群算法将其应用到连续问题优化以获得其在离散优化问题上同样优异的性能，成为目前的一个研究热点，也是本文的主要研究内容。
本文在已有的研究基础上将指导变异的思想引入蚁群算法，并将改进后的蚁群算法应用到PID控制器优化以及模糊规则产生。主要工作有：
（1）对连续优化问题，采用十进制编码进行离散化，将待优化问题定义域变成一个矩阵，使蚁群算法构造候选解的过程简单化。
（2）在定义域各维相同子区间内随机取值构成候选解，依据候选解的目标函数值来对各维子区间进行信息素的初始化，以便对各维子区间有一个大致的“印象”。
（3）在搜索过程中引入变异，利用搜索过程中的积累的关于各个节点上的最优目标函数信息来指导变异。
（4）对连续空间优化，将蚁群优化与步长加速法相结合，以便以较少的计算量获得满意的计算精度。
（5）用函数优化测试实例进行测试，并与遗传算法进行比较，结果说明本文算法能有效逼近全局最优解，并且计算复杂性大大减少。
（6）将本文算法并应用于PID控制器优化、模糊规则产生，并给出仿真实验对比结果，结果说明指导变异蚁群算法能减少上升时间和调节时间，减小系统误差。
引证文献(1条)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_kjxx200728007.aspx
授权使用：宁波工程学院图书馆(nbgcxy)，授权号：209fe5a3-c754-42d1-8e4a-9dd300e233b1
下载时间：2010年8月15日
科技信息。本刊重稿ｏ
ｓｃ皿ＮＣＥ＆ＴＥＣⅢ帕ＬｏＧＹ矾ｆＤ砌姒ＴＩＯＮ
２００７年第２８期
蚁群算法的应用研究与发展
杨海１１２王洪国３徐卫志１
（１．山东师范大学信息科学与工程学院山东济南２５００１４：
２．山东交通学院信息工程系山东济南２５００２３；３．山东省科技厅山东济南２５００１１）
【摘要】蚁群算法是一种新兴的模拟进化算法．由于其具有鲁棒性、正反馈、并行分布式计算等特点，迅速得到广泛的应用和发展。本文首
先介绍了蚁群算法的原理和实现方法，进而又对其研究进展和实际应用做了较详细的综述，并对其前景和发展方向进行了展望。
【关键词】蚁群算法；组合优化；进化计算；信息素；人工蚂蚁
Ａ（沁ｎｅｒａＪ
ｏｖｅｒｖｉｅｗ帆Ａｎｔ
ａ
Ｃｏｌｏｎｙ
ＡＩ霉。一ｔ岫ａｎｄ
ｉ缸ＡｐｐＵｃａｔｉｏｎ
【Ａｂｓｔｒａｃｔ】１１Ｉｅ枷６ｃｉａｌ
Ａｎｔ
Ｃｏｌ彻ｙＡ１９０ｒｉｔｈｍ（ＡＣＡ）ｉｓｎｅｗｔｙｐｅ
ｄｅｖｅｌｏｐｅｄ釉ｄｗｉｄｅｌｙｕ８ｅｄｔ｝ｌｅ８ｅｙｅａ玛．ＡＣＡｈａｓｔ｝Ｉｅｆｂａｔｕｒｅｓｏｆｄｅｖｅｌ叩ｍｅｎｔｏｆＡＣＡ印ｐｌｉｃａｔｉ∞∞ｄｉｔｓｆｕｔｕｒｅｐｍｓｐｅｃｔ．
【ｌ【ｅｙｗｏｒｄｓ】锄ｔｃｏｌｏｎｙａ１９０ｒｉｔｈｍ（ＡｃＡ）；ｃ伽ｐｌｉｃ日ｔｅ叩ｔｉｍｉｚａｔｉ∞；ｓｉｍｕｌａｔｅｄｅｖｏｌｕｔｉｏｎａｒｙａ１９０ｒｉｔｈＩＩｌ；ｐｈｅｍｍ∞ｅ；ａｎ访ｃｉａｌ蚰ｔ
ｉｍｉ吼ｉＩｌｇｅｖｏｌｕｔｉｏｎａｒｙｏｐｔｉＩｌｌｉｚａｔｉ蚰ａｌｇｏｒｉｔｈｍｗｈｉｃｈｈ鹅ｂ∞ｎｒ印ｉｄｌｙ
ｍｂｕｓｔ，ｐ∞ｉｔｉｖｅｆｂｅｄｂａｃｋ肌ｄｃ０Ｕａｔｅｒａｌ．Ｔｈｉｓｏｖｅｒｖｉｅｗｉ８ｍａｄｅ∞ｔｌｌｅｔｌｌ∞ｒｙ．
ｏｆ
１．引言
在计算机自动控制领域中，控制和优化始终是两个重要问题。使用计算机进行控制和优化本质上都表现为对信息的某种处理。随着问题规模的日益庞大，特性上的非线性及不确定性等。人们难以建立精确的“数学模型”。于是人们就从生命科学和仿生学中受到启发。提出了许多智能优化方法，为解决复杂优化问题（ＮＰ“ａＴｄ问题）提供了新途径。
蚁群算法是一种优秀高效的组合优化算法。本文将在介绍蚁群算法原理的基础上，进一步对其研究应用现状及发展前景进行比较详细的阐述。
２．基本蚁群算法２．１蚁群算法原理
蚁群算法（ＡｎｔＣｏｌｏｎｙＡｌｇ耐ｔｈｍ，ＡＣＡ）是Ｄ耐ｇｏＭ等人于１９９１年提出的。经观察发现，蚂蚁个体之间是通过一种称之为信息素（ｐｈｅｍｍｏｎｅ）的物质进行信息传递的。在运动过程中，蚂蚁能够在它所经过的路径上留下该种信息素，而且能够感知信息素的浓度．并以此指导自己的运动方向，倾向于朝着信息素浓度高的方向移动。因此，蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。
２．２蚁群算法基本模型
中：
△％。（ｔ）：ｆＱ～，若蚂蚁。在本次循环中经过点ｉ和点’（４）一’【Ｏ．ｏｔｈｅｒｗｉｓｅ
其中Ｑ为常数，ｋ为蚂蚁ｋ在本次循环中所走路径的长度。２．３蚁群算法流程
步骤１：ｎｃ＝Ｏ（ｎｃ为迭代步数或搜索次数）；每条边上的７《（ｏ）＝ｃ（常数），并且△ｆ“＝ｏ；放置ｍ个蚂蚁到ｎ个城市上。
步骤２：将各蚂蚁的初始出发点置于当前解集ｔａｂｕ。（ｓ）中；对每个蚂蚁ｋ（ｋ＝１，…，ｍ），按概率ｍ‘（ｔ）移至下一城市ｊ；将城市ｊ置于ｔａｂｕｋ（ｓ）中。
步骤３：经过ｎ个时刻，蚂蚁ｋ可走完所有的城市。完成一次循环。计算每个蚂蚁走过的总路径长度ｋ。更新找到的最短路径。
步骤４：更新每条边上的信息量嘶＋ｎ）
步骤５：对每一条边置如“－ｏ；ｎｃ＝ｎｃ＋１
步骤６：若ｎｃ＜预定的迭代次数ＮＣ。，则转步骤２；否则，打印出
最短路径，终止整个程序。
２．４影响蚁群算法效果的因素
（１）局部搜索策略人工蚂蚁在选择将要行走的路线时，所采用的策略是随机的局部搜索策略。这个策略主要基于以下两点：①蚂蚁个体保留的“经验”；（爹问题中公开可用的信息素轨迹和局部信息。（２）蚂蚁的内部状态内部状态主要保留了对决策有用的信息，用于计算生成解的价值、优劣度和每个执行步的贡献。
（３）信息素轨迹由于信息素轨迹的正反馈机制。选择某路径的蚂蚁越多，一个执行步得到的回报就越多。该路径对于后继蚂蚁的吸引力也就越大。
（４）蚂蚁决策策略蚂蚁的决策策略是由信息素函数与启发信息函数共同决定的，即概率表。利用基于概率的原理再配合信息紊挥发机制．避免了所有蚂蚁都过早地早熟收敛。
３．基本蚁群算法与其他启发算法的比较
以图论中具有代表性的偈Ｐ问题为例，设有ｎ个城市。蚂蚁数量
为ｍ，ｄ＃（ｉＪ＝ｌ，２，…，ｎ）表示城市ｉ和ｊ之间的距离，ｂ（ｔ）表示在ｔ时刻城市ｉ和ｊ之间的路径上残留的信息量，来模拟实际蚂蚁的信息素浓度。
初始化时，ｍ个蚂蚁被放置在不同的城市上．并赋予每条边上的信息量为％（０）。蚂蚁ｋ的ｔａｂｕ。（禁忌表）的第一个元素赋值为它所在的城市。
ｐ：（ｔ）：｛－ｊｉ：‰Ｊ
｝ｏ．。ｔｌＩ。。“。
知（ｔ＋ｎ）＝（１一ｐ）・７＃（ｔ）＋△ｆｉｊ（ｔ）其中：
用ｐ；义ｔ）表示在ｔ时刻蚂蚁ｋ由城市ｉ转移到城市ｊ的概率，则
Ｅ
ａｕ０１ｗｅｄｔ
（１）
我们用基本蚁群算法求解偈Ｐ问题。将其实验结果与其他几种启
发算法相对比，可以很清楚的发现基本蚁群算法的优点与不足。用于对比的优化算法有：遗传算法（ＧｅｎｅｔｉｃＡｌ蜀ｏｒｉｔｈｍ，ＧＡ）、进化计算Ｐｍ印ｍｌｌｌｉｎｇ，ＥＰ），模拟退火（ＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉｎｇ，ＳＡ），
模拟退火与遗传算法相结合的混合算法（ＡＧ）。蚁群算法参数设为ｍ＝１０，Ｂ＝２，Ｑ＝０．９，ａ＝ｐ＝Ｏ．１，ｔｊ（ｏ）＝（ｎ・Ｌｍｎ）一。
表中迭代次数指获得最优解所需的代数，圆括号内数据为非整数最优解。实验表明．蚁群算法几乎在所有问题上的性能都是最好的。
（Ｅｖｏｌｕｔｉｏｎａｒｙ
其中ａｌｌｏｗｅｄｔ表示蚂蚁ｋ下一步允许走过的城市的集合．它随蚂蚁ｋ的行进过程而动态改变；信息量下ｉｉ（ｔ）随时间的推移会逐步衰减，用ｐ表示信息素挥发系数；ｄ，ｐ分别表示蚂蚁在运动过程中所积累的信息量及启发式因子在蚂蚁选择路径中所起的不同用；１＃（ｔ）为由城市ｉ转移到城市ｉ的期望程度，可根据某种启发算法而定。
经过ｎ个时刻，蚂蚁ｋ走完所有的点，完成一次循环。此时，要根据下面公式更新各路径上的信息量：
（２）
４．蚁群算法的发展
２０世纪９０年代初．蚁群算法首先成功应用于求解旅行商问题。实验证明该算法不但具有智能搜索、全局优化能力。而且具有鲁棒性、正反馈、并行分布式计算等特点，引起了许多学者的关注，不断对算法的收敛速度、搜索能力等方面进行改进，使蚁群算法广泛地应用在国民经济和军事等领域．成为研究热点之一。并不短提出新的改进算法。大部分改进算法主要是从局部搜索策略、蚂蚁内部状态、信息素轨迹更新策略、选择策略四个方面进行改进，都取得了良好的效果。例如：
△％（ｔ）＝∑△％‘（ｔ）
ｋ＝ｌ
（３）
△寸（ｔ）表示蚂蚁ｋ在本次循环中在点ｉ和点ｊ之间留下的信息
量，其计算方法根据计算模型而定，在最常用的ｍｔ
ｃｙｃｌｅ
ｓｙｓｔｅｍ模型
１３
科技信息。本刊重稿ｏ
ＳＣｍＮＣＥ＆ＴＥｃＩ矾０ＬＯＧＹⅨＦＯＲＭＡｌｌ０Ｎ
２００７年第２８期
最大最小蚁群系统ＭＭＡＳ（Ｍ联一ＭｉｎＡｎｔＳｙｓｔｅｍ）、基于排序的蚂蚁系
统（ＡＳｍｋ）、具有变异特征的蚁群算法、自适应蚁群算法等。此外，蚁群
算法还同其他仿生优化算法相融合。诸如蚁群算法与遗传算法的融合、与人工神经网络的融合、与微粒群算法的融合、与人工免疫算法的融合等，都提高了算法的效率。
表１
问题名称
０ｈｖｅｒ３０
ＡＣＳ４２０
（１）目前大部分改进的蚁群算法都是针对于特定问题。普适性不强。同时蚁群算法模型也不能直接应用于实际优化问题。虽然正反馈机制就是一个很好的普合性模型。但还远远不够。因此．急需设计一种通用的蚁群算法普适性模型。
（２）现阶段的蚁群算法还只是模拟了自然蚂蚁很少一部分社会性，例如：信息素机制。仍然有很大的空间去提出更加智能化的蚁群行为。
（３）蚁群算法目前还带有明显的经验性，很多结果只是建立在实验的基础之上。需要逐步奠定其理论基础。
（４）蚁群算法本身具有分布式计算的特性，但其并行化研究还是停留在初步阶段。一旦并行化有了显著的提高，算法的效率将会有极大地提高。
ＴＳＰ问题的多种优化算法对比
ＧＡ４２ｌ
ＥＰ４２０
ＳＡ４２４
ＡＧ４２０
Ｏｐｔｉｍｍ
４２０
（３０城市）迭代次数
Ｅｉｌ５０
（４２０．３７１）［１４７０】
４３２
（Ｎ，Ａ）【３２００】
４２８
（４２３．７４）【４００００】
４２６
科｝的【２４６１７】
４４３
＠，Ａ）【１２６２０】
４３６
（４２０．３７１）
４２６
（５０城市）迭代次数
Ｅｉｌ７５
（４３２．１７２）【２４１２】
５４０
心｜Ａ＝）ｆ２５０００】
５４５
（４２６．８６）【１０００００】
５４２
（Ｎ，Ａ）［６８５１２】
５８０
（Ｎ，Ａ）【２８ｌｌｌ】
５６１
（４２６．８６）
（５）仿生硬件是并行计算环境下的产物，蚁群算法的硬件实现是仿生硬件研究领域中的一个新分支。虽然蚁群算法的硬件实现在理论
和实验方面都取得了进展，但是还存在许多问题需要解决。Ｄ
５４０
【参考文献】
［１］ＤｏｒｉｇｏＭ．，ＱＬＩＩｌｈａｒｄｅｌｌａ
Ａｐｐ加ａｃｈ
ｔｏ
（７５城市）迭代次数
（５４Ｊｏ．３８４）【４３９３】
（Ｎ，Ａ）【８００００】
（５４９．１８）【３２５０００】
（Ｎ，Ａ）【１７３２５０】
蹬｜吣［９５５０６Ｊ
（５４０．３８４）ＬＭ．Ａｍ
ＣｏｌｏｎｙＳｙｓｔｅｍ：ＡＩＥＥＥ
ｃｏｏｐｅｍｔｉｖｅ【棚埘ｉＩＩｇ
Ｏｎ
ｔｈｅＴｈｖｅＫｎｇ
Ｓａｌｅ哪蛐ＰｆＤｂｌｅｍ．ＡｌｇｏｒｉｔＩＩｍ
Ｔｒ蚰８．
ｃｏｍｐｕｔａｔｉ∞，１９９７，ｌ（１）：５３确．
［２］Ｄｏｒｉｇｏ
ＥＶ０１ｕ６０Ｉ唧
Ｉｊｆｅ，
５．蚁群算法的应用
蚁群算法从提出到现在，只有短短的十几年。尽管还没有严格的理论基础，但其研究领域已经得到了极大的拓广。由一维静态优化问题发展到了多维动态优化问题．由离散域问题拓展到了连续域范围内的研究。
（１）蚁群算法应用于静态组合优化问题，其典型代表有旅行商问
Ｍ，ｃ啪Ｇ
Ｄｉ．ＡｍｆｏｒＤｉ∞”ｔｅ
・
ｏｐｔｉｎｌｉｚａｔｉ衄．Ａｒｔｊ矗ｃｉａｌ
ｓｅ８ｒｃｈ
１９９９，５（３）：１３７一１７２．
［３］Ｄ耐ｇｏＭ，Ｍ明ｉｅｚ∞Ｖ，ＡＴ抚ｈＩｌｉｃａｌＲｅ∞ｒｔ９１～１０６．
［４］Ｂ蹄甜ｅｍ：Ａ
ＣｏｌｏｒＩｌｉ．ＰｏＢｉ６ｖｅＦｅｅｄｂａｃｋ鼬ａ
Ｓ妇ｔｅ盯．
ＢＩｌｌｌｌｌｌｌｅｉｍ％ＲＦＨ叭ｌ，ＣＳｔ叫鹪．ＡＮ删Ｒ锄ｄｋ－ｂ粕ｅｄｖｅ雎ｉ∞ｏｆ１１ｌｅ枷
Ｃ咖ｐｕｔａｔｉｏｎａｌＳｔｕｄｙ．Ｔｔ！ｃｈｎｉｃａｌＲｅｐｏｒｔＰＯＭ—０３，９７，Ｉ珊６ｔｕｔｅｏｆ
ｆｈ
Ｍ蚰ａｇｅｎ驰ｎｔｓｃｉｅｎｃｅ，ＵＩｌｉｖｅ商竹０ｆＶｉｅｎｎａ’１９９７．Ａｃｃ印ｔｅｄ
Ｃｅｎｔｒａｌ
Ｐｌｌｂｌｉｃ以佣ｉＩｌ吐陀
题（俺Ｐ）、二次分配问题（ＱＡＰ）、车间调度问题、车辆路径问题等。在动
态优化问题中的应用主要集中在通讯网络方面。这主要是由于网络优化问题的特殊性，如分布计算，随机动态性，以及异步的网络状态更新等．这砦与蚁群算法的特性匹配得较好。例如将蚁群算法应用于ＱＯＳ组播路由问题上，就得到了优于模拟退火（ＳＡ）和遗传算法（ＧＡ）的效果。
（２）在图像处理方面，蚁群算法的离散性和并行性特点对于离散数字图像非常适用。可用于图像分割。还可以对彩色图像进行颜色ｔ化，根据图像特点。设置初始聚类中心，进行聚类分析。
（３）数据聚类。聚类分析通常被用于模式识别、颜色量化和图像分类。它可以帮助用户从海量的数据中辨别数据结构，简化数据的复杂度。使用蚁群算法可以自动搜索任意数据集中的聚类中心。这种方法非常简单有效，它可以避免陷入局部最小值。
（４）学习模糊规则问题：Ｊ．Ｃ∞ｉｌｌ∞等人利用蚁群算法，已经成功从组成系统模糊语言规则的数据中自动地学习模糊规则。
（５）在智能交通系统（ｒｒＳ）中的应用：智能匹配、运输调度、路径选择、多物流配送中心选址问题等．都是智能交通系统中的常见问题。求解上述问题时，蚁群算法由于具有正反馈机制。有比遗传算法、模拟退火更快的收敛速度，具有很强的寻优能力。
６．蚁群算法的展望
蚁群算法的研究与应用还是一个全新的课题。很多方面都需要进一步完善和发展。
Ｅｕｒｏｑ）ｅ帅Ｊｏｕｍａｌｆｏｒ０ｐｅｍｔｉｏ哪Ｒｅｓｅａｒｃｈａｎｄ
Ａｎａｌｏｇｕｅ
Ａｐｐｍａｃｈ
Ｅｋｏｎ砌ｃｓ．
ｔｏ
［５］ＲＤｕｒｂｊｎ，Ｄ
Ｗｉｕ８ｈ洲．Ａｎ
ｔｈｅ
Ｔｒ盯ｅｌｌｉＩｌｇ
Ｓａｌ船Ⅱ啪
ＰＩｏｂｌｅｍ
ｕ８ｉＩｌｇ柚Ｅｌａ８ｔｉｃＮｅｔＭｅｔｈｏｄ．Ｎｇ山他，１９８７（３２６）：６８９撕９１．
［６］丁建立、陈增强、袁著址．遗传算法与蚂蚁算法的融合［Ｊ］．计算机研究与发展，２００３，４０（９）：１５３ｌ—１５３６．
［７］吴庆洪、张纪会、徐心和．具有变异特征的蚁群算法［Ｊ］．计算机研究与发展，
１９９９。３“ｌｏ）：１２４叽１２４５．
［８］顾军华等．基于蚂蚁算法的Ｑｏｓ组播路由问题求解［Ｊ］．河北工业大学学报．２００２，３１（４）：１９—２４．
［９］段海滨．《蚁群算法原理及其应用》［Ｍ］．科学出版杜，２∞５年１２月第ｌ版．
［１０］李士勇等．《蚁群算法及其应用’［Ｍ］．哈尔滨工业大学出版社，２００４年９月第ｌ版．
［１１］姜长圆．蚁群算法的理论及应用［Ｊ］．计算机时代，２００４，（６）：ｌ一３．
［１２】徐精明等．多态蚁群算法［Ｊ］冲国科学技术大学学报，２００５，３５（１）：５９撕５．作者简介：杨海（１９８０－），男，硕士研究生，主要从事优化算法和智能交通系统的研究。
王洪国，博士后，教授，硕士生导师。徐卫志，硕士研究生。
※基金项目：山东省自然科学基金（Ｑ２００６Ｇ０３）。
【责任编辑：韩铭】
（上接第２８页）究培养教育科研师资：北京师范大学外语系已把行动研究列入教师职前教育课程中：北京外国语大学中国外语教育研究中心也把教学行动研究作为高校外语师资培养重要途径的课题。列入其重点研究课题中。
３．结论
教学行动研究肯定了教师作为研究者的主体身份，重新定位了教师与学生在研究性学习中的角色。同时从研究目的与方向。具体过程途径上帮助教师循序渐进地提高教学水平和研究质量，最后将其纳入到学校课程管理与评价体系有利于教师研究的可持续发展。在解决英语课程教学理论与实践相脱节的问题的同时满足了广大英语教师进行研究的需要，使教师不仅仅成为课程实践者。并且也成为研究者即研究型教师。教师在行动研究过程中通过对自己教学行为不间断的、直接或间接的观察与反思。通过与专业研究人员或其他合作者的交流不断地加深对自身的认知、对教学实践的理解。这样，行动研究就超越
展”的一个过程并最终促成了新型“学校文化”的建立。我们英语教师应该积极地开展或参与教学行动研究，使自己增强反思意识和能力。提高教学质量，逐步走上自我指导和专业化可持续发展之路，接受新
时期对我们提出的挑战。１２１，
【参考文献ｌ
［１］蔡基刚．大学英语教学：回顾、反恩和研究【Ｍ】．上海：复旦大学出版社，２００６．［２］黄远振．新课程英语教与学．福建：福建教育出版社，２００３．
［３］刘良华墩育行动研究ｍ．教育理论与实践，２００ｌ，（３）．
［４］裴娣娜．教育研究方法导论【Ｍ１．安徽：安徽教育出版社．１９９５．［５］王蔷．英语教师行动研究ｆＭｌ．北京：外语教学与研究出版社，２００２．［６］吴宗杰．行动研究：外语师资教育新途径［Ｊ】．外语教学研究，１９９５，（２）．［７］钟启泉．现代课程论【Ｍ】．上海：上海教育出版社，２００３．
了传统上对“研究”功能的界定——真理知识的增加。而成为“人的发
１４
【责任编辑：翟成梁】
蚁群算法的应用研究与发展
作者：作者单位：
杨海， 王洪国， 徐卫志
杨海(山东师范大学信息科学与工程学院,山东,济南,250014;山东交通学院信息工程系,山东,济南,250023)， 王洪国(山东省科技厅,山东,济南,250011)， 徐卫志(山东师范大学信息科学与工程学院,山东,济南,250014)科技信息（科学·教研）
SCIENCE & TECHNOLOGY INFORMATION2007，""(28)1次
刊名：英文刊名：年，卷(期)：被引用次数：
参考文献(12条)
1. Dorigo M. Gambardella L M Ant Colony System:A Cooperative Learning Approach to the TravelingSalesman Problem 1997(01)
2. Dorigo M. Caro G Di Ant Algorithms for Discrete Optimization 1999(03)
3. Dorigo M. Maniezzo V. A Colorni Positive Feedback as a Search Strategy[Technical Report 91～106]4. B Bullnheimer. R F Hartl. C Strauss A New Randk-based Version of The ant System:A ComputationalStudy[Technical Report POM-03/97] 1997
5. R Durbin. D Willshaw An Analogue Approach to the Travelling Salesman Problem Using an Elastic NetMethod 1987(326)
6. 丁建立. 陈增强. 袁著址 遗传算法与蚂蚁算法的融合[期刊论文]-计算机研究与发展 2003(09)7. 吴庆洪. 张纪会. 徐心和 具有变异特征的蚁群算法[期刊论文]-计算机研究与发展 1999(10)8. 顾军华 基于蚂蚁算法的QoS组播路由问题求解[期刊论文]-河北工业大学学报 2002(04)9. 段海滨 蚁群算法原理及其应用 200510. 李士勇 蚁群算法及其应用 2004
11. 姜长圆 蚁群算法的理论及应用[期刊论文]-计算机时代 2004(06)12. 徐精明 多态蚁群算法[期刊论文]-中国科学技术大学学报 2005(01)
相似文献(10条)
1.期刊论文 许刚. 张土乔. 吕谋. 吴小刚. XU Gang. ZHANG Tu-qiao. LU Mou. WU Xiao-gang 给水管网管径组合优化的极大极小蚁群算法 -哈尔滨工业大学学报2006,38(5)
蚁群算法作为模仿蚂蚁寻找食物的进化算法已经成功的应用于许多组合优化领域.针对其在给水管网管径组合优化设计过程中的计算时间长,易陷入局部极小点等问题,提出了单只蚂蚁更新外激素值,并使外激素值限定在一定范围内的基于二进制编码的极大极小蚁群改进算法,并编制了相应的程序代码.将该方法运用到某小区管网的管径组合优化,结果表明,改进的蚁群算法与基本的蚁群算法相比,更容易实现全局最优解,且计算时间较短.
2.学位论文 曾艳 蚁群算法在组合优化中的应用 2006
组合优化中的许多问题是NP-完全问题，也是科学和工程计算中重要和基本的问题，这类问题的求解一直是算法研究领域的热点问题。对于NP-完全的组合优化问题，至今尚无很好的解析算法，一般采用启发式算法来解决。蚁群算法作为一种新的启发式算法，它具有正反馈、分布式计算以及结构性的贪心启发等特点，使其能够成功地解决许多NP-完全的组合优化问题。本文在详细介绍蚁群算法原理的基础上，对蚁群算法在组合优化问题中的应用进行分析和研究，主要将蚁群算法应用于求解最大团和最大割两个经典的NP-完全组合优化问题，本文主要做了以下工作：
1、在研究已有的最大团问题的蚁群算法以及对蚁群算法深入分析的基础上，根据最大团问题的特点，提出了最大团问题的新型蚁群算法，通过大量的仿真试验证明，算法的性能明显提高了。
2、以最大团问题为例，对蚁群算法的参数进行了深入研究，并提出了使用动态局部启发信息的改进策略。仿真试验证明，该方案使算法的性能得到一定的提高。
3、在研究了组合优化问题基础上，提出了最大割问题的蚁群算法方案。大量的仿真试验证明，该方案能较成功地解决最大割问题。
3.期刊论文 邓玉芬. 向凤红. Deng Yufen. Xiang Fenghong 蚁群算法在组合优化中的应用 -电子测量技术2007,30(1)
本文介绍了崭新的求解复杂优化问题的启发式算法-蚁群算法以及它的基本原理.该算法是通过模拟蚁群搜索食物的过程,达到求解此类问题的目的.它具有智能搜索、全局优化、稳健性强、分布式计算、易与其他方法结合等优点.文章还介绍了该算法在静态组合优化,如旅行商、二次分配、车间任务调度、车辆路线、图着色、有序排列,以及动态组合优化中的应用.文章最后展望了蚁群算法所具有的广阔应用前景.
4.期刊论文 孙泽宇. 邢萧飞 求解自适应组合优化蚁群算法的研究 -计算机工程与应用2009,45(35)
,提出了自适应组合优化蚁群算法.通过对改变信息素的迭代、参数选择的分析和增加对信息素局部更新方式,提高了整个系统运算速度及收敛速度,扩充了优化的范围,克服了无用迭代码的产生,减少了停滞现象的出现.通过该算法对旅行商问题进行仿真实验,其结果表明了该算法的可行性和有效性.
5.期刊论文 马烁. 王安平. 赵天玉. MA Shuo. WANG An-ping. ZHAO Tian-yu 蚁群算法及其在组合优化中的应用 -咸阳师范学院学报2008,23(2)
蚁群算法是近年来新出现的一种启发式仿生算法,该算法为求解复杂的组合优化问题提供了一种新思路,引起众多学者的研究兴趣.本文首先介绍了蚁群算法的原理和实现方法,进而又对其在组合优化中的实际应用做了较详细的研究,并对其前景及发展方向进行了展望.
6.学位论文 陈佑健 蚁群算法的研究及在网络路由优化上的应用 2005
蚁群算法是一种新型的用于求解组合优化或函数优化问题的元启发式算法,其基本思想是借用生物界的蚂蚁群体觅食机理,将每个蚂蚁看作一个智能体,作为智能群体的蚁群,其觅食过程显现出高度的并行性、正反馈性和鲁棒性,以此为基础的蚁群算法也具有这样一些特点.因此,蚁群算法的研究无论从理论上还是实用上,都具有较高的价值.本文首先分析了蚁群算法的原理与模型,介绍了算法的特点和研究现状,通过实验分析了算法中几个关键参数的选择.针对基本蚁群算法的主要缺陷,如收敛速度慢和易于陷入局部最优等问题,将用于求解组合优化问题的基本蚁群算法进行了改进.首先,在概率选择上采用了确定性与随机性相结合的选择原则;其次,由于基本蚁群算法初期时各条路径上的信息素数量相同,导致算法的初期求解速度缓慢,因此提出了分区搜索的思想,使各条路径上的信息素在初期有所差别,加速算法的收敛;第三,结合局部与全局信息素调整策略对路径上的信息素进行动态更新;第四,对与信息素相关的一些参数进行了自适应改变;最后,引入遗传算法中的变异思想,以扩大解的搜索空间.针对蚁群算法在求解连续优化问题上相对较弱的特点,提出了基于网格划分的蚁群算法,将传统的用于求解离散空间优化问题的蚁群算法进行了扩展.在应用研究上,分析了网络路由优化问题,研究了基于蚁群算法的IP网络QoS单播路由;讨论了基于蚁群算法的一些其它应用.通过算例对所提出的改进的蚁群算法进行了仿真验证,实验结果表明,本文提出的改进算法是有效和可行的;在连续函数优化上和基于蚁群算法的网络路由优化等应用上也进行了实验仿真.本课题旨在为推进蚁群算法的理论研究和应用研究起到一定的作用.
7.期刊论文 何幼林. 欧福军. 魏华实. 徐健. 张雍吉 蚁群算法的原理及其在组合优化中的应用 -黑龙江科技信息2008,""(1)
蚁群优化算法是近年来出现的一种新的启发式搜索算法.首先介绍了蚁群算法的基本原理,然后讨论了其在组合优化中的应用,最后分析了蚁群算法的一些基本特点.
8.学位论文 于永彪 基于混合蚁群算法的离散变量结构截面优化方法研究 2007
结构优化设计是近四十年发展起来的一门新技术，与传统设计相比，由于其具有设计合理、节省原材料等特点日益受到国内外工程界的广泛重视。结构优化设计可以降低结构重量和材料成本，改进结构的强度、刚度、振动特性、屈曲稳定性等性能，是现代设计制造领域的重要研究方向。随着结构优化设计理论和方法的迅速发展，离散变量结构优化设计越来越得到关注。离散变量结构优化设计在数学上属于组合优化的范畴，组合优化问题属于NP完全类问题，其求解算法属于NP困难问题。
社会性动物的群体活动往往能产生惊人的自组织行为，个体行为显得盲目的蚂蚁在组成蚁群后能够发现从蚁巢到食物的最短路径。生物学家经过仔细研究发现蚂蚁之间通过一种称之为“信息素”的物质进行间接通讯、相互协作来发现最短路径。受其启发，意大利学者Dorigo.M等于1991年提出一种群体智能算法一蚁群算法(ACO)，该算法自提出以来在计算机科学领域和优化领域中受到广泛关注，在求解旅行商、二次分配、生产安排调度、网络路由、函数优化等问题方面得到了广泛应用，显示了该算法在求解组合优化问题方面的优越性。 本文围绕蚁群算法在离散变量结构截面优化设计中的应用，进行了如下工作：
1、提出了一种混合蚁群算法。在系统地学习研究蚁群算法的原理、数学模型和组合优化应用的基础上，分析三种寻优模式，提出了混合蚁群算法，综合三种不同的寻优模式，调整不同寻优模式蚁群数量的比例，使算法在保持较高搜索能力的同时，避免出现停滞现象。对算法的程序实现进行了研究。
2、分析和研究了混合蚁群算法的参数设置。对该算法应用时的参数选择原则进行了探讨，用于指导参数设置。进行了算法的对比分析和测试函数的验证，表明了混合蚁群算法的良好性能。
3、将混合蚁群算法应用于离散变量结构截面优化设计。针对离散变量结构截面优化设计的性质与特点，对该算法应用时的设计变量、目标函数和约束条件作了概要的分析与研究，拓宽了蚁群算法的应用领域。
4、编制优化程序。运用FORTlRAN语言编制了混合蚁群结构截面优化设计程序，将优化设计程序与大型结构有限元分析软件ALGOR相连接，由该软件完成结构优化程序中的结构分析，使优化设计与结构分析融为一体，从而增强了程序的可靠性，拓宽了ALGOR的使用范围，实现了用ALGOR验证优化设计结果的目的。
5、对优化设计程序在结构中的应用进行了验证。对该程序应用于桁架、框架、网架、网壳结构截面优化设计时的数学模型、约束条件处理及控制参数的选择作了概要的分析与研究。算例结果对比表明该程序是可行的和高效的。
9.期刊论文 李万庆. 李彦苍. LI Wan-qing. LI Yan-cang 求解复杂优化问题的基于信息熵的自适应蚁群算法 -数学的实践与认识2005,35(2)
针对基本蚁群算法存在收敛速度慢、易陷入局部最优、计算复杂且不易求解连续优化问题等缺陷,提出了一种基于信息熵的改进自适应蚁群算法,采用由信息熵控制的路径选择及随机扰动策略实现了算法的自适应调节,克服了基本蚁群算法的不足.典型的NP-hard问题的计箅实例表明,该方法具有较好的收敛性、稳定性和鲁棒性,可用于离散及连续的组合优化问题求解中,其不失为求解复杂组合优化问题的一种较好的方法.
10.学位论文 秦映波 指导变异蚁群算法及其应用 2009
优化技术在许多工程领域有广泛的应用，如系统控制、人工智能、模式识别、生产调试以及计算机工程等。为了克服传统优化方法的不足，人们提出了智能优化方法如遗传算法、模拟退火算法、禁忌搜索算法等。
蚁群算法是一种模拟进化算法，通过模拟蚂蚁在协作搜索食物时的搜索行为来寻求最优解。蚁群算法提出后在组合优化中获得广泛的应用，如调度、二次分配和网络路由等。基于蚁群算法在组合优化实验中的优异性能，改进蚁群算法将其应用到连续问题优化以获得其在离散优化问题上同样优异的性能，成为目前的一个研究热点，也是本文的主要研究内容。
本文在已有的研究基础上将指导变异的思想引入蚁群算法，并将改进后的蚁群算法应用到PID控制器优化以及模糊规则产生。主要工作有：
（1）对连续优化问题，采用十进制编码进行离散化，将待优化问题定义域变成一个矩阵，使蚁群算法构造候选解的过程简单化。
（2）在定义域各维相同子区间内随机取值构成候选解，依据候选解的目标函数值来对各维子区间进行信息素的初始化，以便对各维子区间有一个大致的“印象”。
（3）在搜索过程中引入变异，利用搜索过程中的积累的关于各个节点上的最优目标函数信息来指导变异。
（4）对连续空间优化，将蚁群优化与步长加速法相结合，以便以较少的计算量获得满意的计算精度。
（5）用函数优化测试实例进行测试，并与遗传算法进行比较，结果说明本文算法能有效逼近全局最优解，并且计算复杂性大大减少。
（6）将本文算法并应用于PID控制器优化、模糊规则产生，并给出仿真实验对比结果，结果说明指导变异蚁群算法能减少上升时间和调节时间，减小系统误差。
引证文献(1条)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_kjxx200728007.aspx
授权使用：宁波工程学院图书馆(nbgcxy)，授权号：209fe5a3-c754-42d1-8e4a-9dd300e233b1
下载时间：2010年8月15日