智能控制之蚁群算法
1引言
进入21世纪以来，随着信息技术的发展，许多新方法和技术进入工程化、产品化阶段，这对自动控制技术提出新的挑战，促进了智能理论在控制技术中的应用，以解决用传统的方法难以解决的复杂系统的控制问题。随着计算机技术的飞速发展，智能计算方法的应用领域也越来越广泛。
智能控制技术的主要方法有模糊控制、基于知识的专家控制、神经网络控制和集成智能控制等,以及常用优化算法有:遗传算法、蚁群算法、免疫算法等。
蚁群算法是近些年来迅速发展起来的，并得到广泛应用的一种新型模拟进化优化算法。研究表明该算法具有并行性，鲁棒性等优良性质。它广泛应用于求解组合优化问题，所以本文着重介绍了这种智能计算方法，即蚁群算法，阐述了其工作原理和特点，同时对蚁群算法的前景进行了展望。
2 蚁群算法概述
1、起源
蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
Deneubourg及其同事(Deneubourg et al.,1990; Goss et al.,1989)在可监控实验条件下研究了蚂蚁的觅食行为，实验结果显示这些蚂蚁可以通过使用一种称为信息素的化学物质来标记走过的路径，从而找出从蚁穴到食物源之间的最短路径。
在蚂蚁寻找食物的实验中发现，信息素的蒸发速度相对于蚁群收敛到最短路径所需的时间来说过于缓慢，因此在模型构建时，可以忽略信息素的蒸发。然而当考虑的对象是人工蚂蚁时，情况就不同了。实验结果显示，对于双桥模型和扩展双桥模型这些简单的连接图来说，同样不需要考虑信息素的蒸发。相反，在更复杂的连接图上，对于最小成本路径问题来说，信息素的蒸发可以提高算法找到好解的性能。
2、基于蚁群算法的机制原理
模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的计算智能模式引入的，该算法基于如下假设：
第２２卷第６期 ２０１２年６月 计算机技术与发展
ＣＯＭＰＵＴＥＲ ＩＥＣＨＮＯ【Ｊ０ＧＹ ＡＮＤ ＤＥＶＥＬＯＰＭＥＮＴ ＶｏＩ．２２ Ｎｏ．６ Ｊｕｎｅ ２０ｌ２
基于粗糙集和蚁群算法的特征基因选择方法
黄丹凤，祁云嵩，许姗娜
（江苏科技大学计算机科学与工程学院，江苏镇江２１２００３）
摘要：特征基因选择在微阵列数据分析中占据着非常重要的作用，好的特征选择方法是提高基因表达数据的分类精度 与分类速度的关键之一。联系蚁群算法和粗糙集理论在微阵列数据处理上的优势，文中结合粗糙集理论，对蚁群优化算 法模型进行了改进，并将粗糙集的属性依赖度和属性重要度应用到蚁群算法的路径选择及评估中，提出一种新的基因选 择方法。该方法实现简单，并可以比较快速地获得最优解，最终选择出较小的并且分类性能较强的特征基因子集。通过 对基因数据集的仿真实验表明，该算法是有效可行的。 关键词：特征选择；粗糙集；蚁群算法 中图分类号：ＴＰ３９１ 文献标识码：Ａ 文章编号：１６７３－６２９Ｘ（２０１２）０６－００６８—０３
Ｇｅｎｅ Ｓｅｌｅｃｔｉｏｎ Ｍｅｔｈｏｄ Ｂａｓｅｄ ｏｎ Ｒｏｕｇｈ Ｓｅｔｓ ａｎｄ
Ａｎｔ Ｃｏｌｏｎｙ Ａｌｇｏｒｉｔｈｍ
ＨＵＡＮＧ Ｄａｎ—ｆｅｎｇ Ｉ ＱＩ Ｙｕｎ－ｓｏｎｇ。ＸＵ Ｓｈａｎ－ｎａ
（Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕ￣ｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｊｉａｎｇｓｕ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｚｈｅｎｊｉａｎｇ ２１２００３。Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｇｅｎｅ ｓｅｌｅｃｔｉｏｎ ｔａｋｅｓ ａｌｌ ｉｍｐｏｒｔａｎｔ ｐｌａｃｅ ｉｎ ＤＮＡ ｄａｔｅ ａｎａｌｙｓｉｓ．Ｇｏｏｄ ｆｅａｔｕｒｅ，ｓｅｌｅｃｔｉｏｎ ｍｅｔｈｏｄ ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｋｅｙｓ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｇｅｎｅ ｅｘｐｒｅｓｓｉｏｎ ｄａｔａ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｃｃｕｒａｃｙ ａｎｄ ｓｐｅｅｄ．Ｔａｋｅ ａｄｖａｎｔａｇｅ ｏｆ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ（ＡＣＯ）ａｌｇｏｒｉｔｈｍ ａｎｄ ｒｏｕｇｈ ｓｅｔ ｔｈｅｏｒｙ ｉｎ ｍｉｃｍａｒｒａｙ ｄａｔａ ｐｒｏｃｅｓｓｉｎｇ。ｕｓｅ ｒｏｕｇｈ Ｓｅｔ ｔｈｅｏｒｙ ａｎｄ ＡＣＯ ａｌｇｏｒｉｔｈｍ ｔｏ ｐｕｔ ｆｏｒｗａｒｄ ａ ｇｅｎｅ ｓｅｌｅｃｔｉｏｎ ｍｅｔｈｏｄ．Ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ＵＳｅＳ ｒｏｕｇｈ ｓｅｔ ｄｅｐｅｎｄｅｎｃｙ ａｎｄ ａｔｔｒｉｂｕｔｅｓ ｓ！ｇｎｉｆｉｃａｎｃｅｔｏ ｇｕｉｄｅｔｈｅａｎｔｓｓｅａｒｃｈ ｐｒｏｃｅｓｓａｎｄｆｅａｔｕｒｅ ｇｅｎｅ ｓｕｂｓｅｔａｓｓｅＳＳ．Ｉｔ ｃａｎ ｇｅｔ ａｆｅａｔｕｒｅ ｓｕｂｓｅｔ ｅａｓｉｌｙ ａｎｄ ｑｕｉｃｋｌｙ，ｗｉｔｈ ａ ｓｍａｌｌ ｎｕｍｂｅｒ ｏｆ ｇｅｎｅｓ Ｃａｎ ｇｅｔ ｇｏｏｄ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ａｃｃｕｒａｃｙ．Ｔｈｅ ｇｉｖｅｎ ｅｘａｍｐｌｅｓ ｔｅｓｔｉｎｇ ｉｎ ｒｅａｌ ｄａｔａｓｅｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄｍｅｔｈｏｄｉｓｆｅａｓｉｂｌｅａｎｄ ｅｆｆｅｃｔｉｖｅ． Ｋｅｙ ｗｏｒｄｓ：ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ；ｒｏｕｇｈ ｓｅｔｓ；ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ
蚁群算法
蚁群算法
⽬录1 蚁群算法基本思想 (1)
1.1蚁群算法简介 (1)
1.2蚁群⾏为分析 (1)
1.3蚁群算法解决优化问题的基本思想 (2)
1.4蚁群算法的特点 (2)
2 蚁群算法解决TSP问题 (3)
2.1关于TSP (3)
2.2蚁群算法解决TSP问题基本原理 (3)
2.3蚁群算法解决TSP问题基本步骤 (5)
3 案例 (6)
3.1问题描述 (6)
3.2解题思路及步骤 (6)
3.3MATLB程序实现 (7)
3.1.1 清空环境 (7)
3.2.2 导⼊数据 (7)
3.3.3 计算城市间相互距离 (7)
3.3.4 初始化参数 (7)
3.3.5 迭代寻找最佳路径 (7)
3.3.6 结果显⽰ (7)
3.3.7 绘图 (7)
1 蚁群算法基本思想
1.1 蚁群算法简介
蚁群算法（ant colony algrothrim，ACA）是由意⼤利学者多⾥⼽（Dorigo M）、马聂佐（Maniezzo V ）等⼈于20世纪90初从⽣物进化的机制中受到启发，通过模拟⾃然界蚂蚁搜索路径的⾏为，提出来的⼀种新型的模拟进化算法。该算法⽤蚁群在搜索⾷物源的过程中所体现出来的寻优能⼒来解决⼀些系统优化中的困难问题，其算法的基本思想是模仿蚂蚁依赖信息素，通过蚂蚁间正反馈的⽅法来引导每个蚂蚁的⾏动。
蚁群算法能够被⽤于解决⼤多数优化问题或者能够转化为优化求解的问题，现在其应⽤领域已扩展到多⽬标优化、数据分类、数据聚类、模式识别、电信QoS管理、⽣物系统建模、流程规划、信号处理、机器⼈控制、决策⽀持以及仿真和系统辩识等⽅⾯。
蚁群算法是群智能理论研究领域的⼀种主要算法。1.2 蚁群⾏为分析
B
m=20
t=0 m=10m=10
t=1
1.3 蚁群算法解决优化问题的基本思想
⽤蚂蚁的⾏⾛路径表⽰待优化问题的可⾏解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息量较多，随着时间的推进，较短路径上积累的信息浓度逐渐增⾼，选择该路径的蚂蚁个数愈来愈多。最后，整个蚂蚁会在正反馈的作⽤下集中到最佳路径上，此时对应的便的待优化问题的最优解。1.4 蚁群算法的特点
蚁群算法
同进化算法（进化算法是受⽣物进化机制启发⽽产⽣的⼀系列算法）和⼈⼯神经⽹络算法（神经⽹络是从信息处理⾓度对⼈脑的神经元⽹络
系统进⾏了模拟的相关算法）⼀样，群智能优化算法也属于⼀种⽣物启发式⽅法，它们三者可以称为是⼈⼯智能领域的三驾马车（实际上除
了上述三种算法还有⼀些智能算法应⽤也很⼴泛，⽐如模拟⾦属物质热⼒学退⽕过程的模拟退⽕算法（Simulated Algorithm,简称SA），模
拟⼈体免疫系统在抗原刺激下产⽣抗体过程的⼈⼯免疫系统算法（Artificial Immune System,简称AIS）等，但是相对三者⽽⾔，模拟退⽕算
法和⼈⼯免疫系统算法已逐渐处于低潮期）。群智能优化算法主要是模拟了昆⾍，兽群、鸟群和鱼群的群集⾏为，这些群体按照⼀种合作的
⽅式寻找⾷物，群体中的每个成员通过学习它⾃⾝的经验和其他成员的经验来不断地改变搜索的⽅向。群体智能优化算法的突出特点就是利
⽤了种群的群体智慧进⾏协同搜索，从⽽在解空间内找到最优解。
常见的群体智能优化算法主要有如下⼏类：
蚁群算法（Ant Colony Optimizatio,简称ACO）【1992年提出】；
粒⼦群优化算法（Particle Swarm Optimization,简称PSO）【1995年提出】
菌群优化算法（Bacterial Foraging Optimization，简称BFO）【2002年提出】
蛙跳算法（Shuffled Frog Leading Algorithm,简称SFLA）【2003年提出】
⼈⼯蜂群算法（Artificial Bee Colony Algorithm,简称ABC）【2005年提出】
除了上述⼏种常见的群体智能算法以外，还有⼀些并不是⼴泛应⽤的群体智能算法，⽐如萤⽕⾍算法，布⾕鸟算法，蝙蝠算法以及磷虾群算
法等等。
蚁群算法
蚂蚁寻找⾷物的过程
单只蚂蚁的⾏为及其简单，⾏为数量在10种以内，但成千上万只蚂蚁组成的蚁群却能拥有巨⼤的智慧，这离不开它们信息传递的⽅式———
