具有变异特征的蚁群算法_吴庆洪

蚁群算法的研究现状Current Status of Re search on Ant Colony Algorithm吴　斌　赵燕伟(浙江工业大学机电学院,杭州　310032)摘　要　蚁群算法是一种新型的模拟进化算法,研究表明该算法具有很好的通用性和鲁棒性,在离散的组合优化问题中实验,取得了良好的效果。

介绍了蚁群算法的原理,对目前蚁群算法的研究进展情况进行了分析,同时对比国内外的研究状况提出了自己的观点,以推动该算法在更广阔的领域内得到应用。

关键词　蚁群算法　研究　现状　蚁群系统　组合优化　TSPAbstract　Ant colony alg orithm is a kind of new emulated ev olution alg orithm.The research shows that this alg orithm can be comm only used and offers very g ood robustness,excellent result is obtained in the experiment of discrete combined optim ization.The principle of ant colony alg orithm is introduced and current progress in research of this alg orithm is analyzed.The situation of the research at home and abroad are com pared and the view point of author is given.The application of this alg orithm in wider area is prom oted.K ey　w ords　Ant colony alg orithm　Research　Current status　Ant colony system　C ombined optim ization　TSP0　引言很早人们就知道模仿生物的一些特性,来更好地为人类服务。

式中，$为起始节点，g为目标点，切为起始点$到节 点/之间的距离，血为节点/到目标点g之间的距离。这一 改进增强了蚂蚁搜索的目的性，降低了算法陷入局部最优解 的概率。
3.2信息素浓度更新规则的改进 传统蚁群算法是在蚂蚁遍历所有路径后再对信息素浓度
进行更新，并且信息素挥发因子是常数，这样容易导致蚂蚁 在前期搜索时的盲目性较大，在后期搜索时的收敛速度较慢。
作者简介：张小龙(1998-),男，河南周口人，硕士研究生。 研究方向：移动机器人路径规划研究。
63
信!g与电脑 China Computer & Communication
2021年第8期
1环境建模
移动机器人环境建模方法主要有栅格法、自由空间法、 构型空间法等，其中以栅格法最为常用。栅格法环境建模的 基本原理是将移动机器人的工作环境划分成很多小网格，每 个网格的大小是由机器人的步长决定的。机器人工作环境分 为可行区域与非可行区域，因此网格也是由可行网格与障碍 网格组成。可行网格用白色网格表示，非可行网格用黑色网 格表示。图1是20*20的机器人环境建模网格，机器人需要 从起始点（0, 0）到达终点（19, 19）,中间每一段路径都 有8个方向可供选择，同时机器人也要躲避网格中的黑色障 碍物，以顺利到达终点。
Abstract: Aiming at the problems of traditional ant colony algorithm such as low efficiency, slow convergence speed, and easy to fall into local optimal solution, the author proposes an improved ant colony algorithm. The algorithm introduces a distance heuristic factor into the heuristic function, which makes the ants have the orientation in the path search process, and makes the algorithm not easy to fall into the local optimal solution. The research results show that the proposed improved ant colony algorithm can find the optimal path efficiently and quickly, and the quality of the path is better than the path planned by the traditional ant colony algorithm.

软件开发118蚁群算法及其在智能交通中的应用◆◆吴鸣◆摘要：随着经济的快速发展，人们的生活水平也得到了一定的提高，私人汽车拥有量在不断的增加。

随着私有汽车的数量不断的提高，交通问题也在日益严重，交通问题现在已经成为了城市发展的重要阻碍。

智能交通系统可以有效的去解决现在社会对于交通的需求，同时也能解决消费者之间的供给问题。

智能交通系统主要是以人工智能技术为支撑，可以有效的缓解交通拥挤的现状。

关键词：智能交通系统；蚁群算法；算法改进；车辆路径问题1◆◆蚁群算法及其研究现状1.1 蚁群算法蚁群算法简单来说就是利用以群搜索食物的过程，结合著名的旅行商问题，成功的运用在求解tsp问题上。

蚁群算法其实是一种模拟进化算法，但是这种算法仅仅局限于种群之间，在一定程度上具有随机搜索的特点。

多个可行解之间可以组成许多种群，各个种群之间所出现的问题都会得到最优化的解决，并且根据长期的生活经验可以不断的调整自身的结构。

在协作的阶段，大多数会进行简单的信息交流，这样才可以形成新一轮的可行解。

蚂蚁之间会留下一种特殊的信息素，这些信息在长时间之后会得到挥发，挥发之后在日后的搜索中就寻找不出来。

这些特性使得蚁群算法体现出了明显的自组织机制，完全不会受到外界的干扰，从开始的无组织状态会演化到有序状态。

1.2 蚁群算法的特点和研究现状蚁群算法本身具有智能搜索的优势，可以将全局的能力进行整体优化，进行正反馈计算。

在搜索路径的过程中，蚂蚁所采用的信息素可以成为一种特殊的通信机制，并且这种机制非常容易扩展到人工多主题模型。

人工主体指挥将访问状态增加变量信息，通过正反馈机制将评估进行合理的优化，在一定程度上可以提高问题的解效率。

当蚁群在完成一项工作时，会和其他的蚂蚁共同协作来完成工作的目标，所以在任务实施的过程中，并不会有与个体的能力不足所受到影响。

蚁群算法一直作为一种模拟种群的进化算法，在现实生活中具有一定的可实施性，对于模型也会进行细微的修改。

蚁群算法综述控制理论与控制工程09104046 吕坤一、蚁群算法的研究背景蚂蚁是一种最古老的社会性昆虫，数以百万亿计的蚂蚁几乎占据了地球上每一片适于居住的土地，它们的个体结构和行为虽然很简单，但由这些个体所构成的蚁群却表现出高度结构化的社会组织，作为这种组织的结果表现出它们所构成的群体能完成远远超越其单只蚂蚁能力的复杂任务。

就是他们这看似简单，其实有着高度协调、分工、合作的行为，打开了仿生优化领域的新局面。

从蚁群群体寻找最短路径觅食行为受到启发，根据模拟蚂蚁的觅食、任务分配和构造墓地等群体智能行为，意大利学者M.Dorigo等人1991年提出了一种模拟自然界蚁群行为的模拟进化算法——人工蚁群算法，简称蚁群算法(Ant Colony Algorithm,ACA)。

二、蚁群算法的研究发展现状国内对蚁群算法的研究直到上世纪末才拉开序幕，目前国内学者对蚁群算法的研究主要是集中在算法的改进和应用上。

吴庆洪和张纪会等通过向基本蚁群算法中引入变异机制，充分利用2-交换法简洁高效的特点，提出了具有变异特征的蚊群算法。

吴斌和史忠植首先在蚊群算法的基础上提出了相遇算法，提高了蚂蚁一次周游的质量，然后将相遇算法与采用并行策略的分段算法相结合。

提出一种基于蚁群算法的TSP问题分段求解算法。

王颖和谢剑英通过自适应的改变算法的挥发度等系数，提出一种自适应的蚁群算法以克服陷于局部最小的缺点。

覃刚力和杨家本根据人工蚂蚁所获得的解的情况，动态地调整路径上的信息素，提出了自适应调整信息素的蚁群算法。

熊伟清和余舜杰等从改进蚂蚁路径的选择策略以及全局修正蚁群信息量入手，引入变异保持种群多样性，引入蚁群分工的思想，构成一种具有分工的自适应蚁群算法。

张徐亮、张晋斌和庄昌文等将协同机制引入基本蚁群算法中，分别构成了一种基于协同学习机制的蚁群算法和一种基于协同学习机制的增强蚊群算法。

随着人们对蚁群算法研究的不断深入，近年来M.Dorigo等人提出了蚁群优化元启发式(Ant-Colony optimization Meta Heuristic，简称ACO-MA)这一求解复杂问题的通用框架。

好行程 的选择机会。 这种改进型算法 能够以更快的速度获得更
好 的解 ， 是该算法 会较早的收敛于局 部次优 解， 但 导致搜 索的
过 早停 滞 。 针对 Ａ 中暴 露 出 的问题 ， ａ ｂ ｒ ｅ ｌ Ｌ Ｍ Ｄ ｒ ｇ Ｍ Ｓ Ｇ ｍ ａ ｄ ｌａ ， ｏ ｉｏ ”
提 出了蚁群系统 （ｎ ｏｏ ｙ ｓ ｓ ｅ ，Ａ Ｓ 。 Ａ ｔ ｃ ｌｎ ｙ ｔｍ Ｃ ） 该文作者较早提
ｗ 啦
（ ４ ）
ｒ ＝ｌ 其 中， ｏ ｅ ｛，， ｎ １＿ａ ｕ 表 示 蚂 蚁 ｋ ａ ｌｗ ｄ ＝Ｏ１…，一 ｝ｔ ｂ 下一 步允 许 式中的排 序加 权处 理确 定， 其中 ＝ｉ， （ － ｍ 每 次 选 择 的城 市 ， 实 际 蚁 群 不 同 ， 工 蚁 群 系 统 具 有 记 忆 功 能 ， ｌ ｎ 为 ｅ ： 与 人
ｏｐ ｍｉ ａｔｉ ｉ ｂｕｉ ｔ ｆ ｓ ｖｉ ｔ ｔ ｔｉ ｚ ｏｎ ｓ ｌ ｏｒ ｏｌ ｎｇ ｈｅ ｒａｖ ｉ ｓ ｅ ｍａ ｐ ｅｌ ｎｇ ａｌ ｓ ｎ ｒｏｂ ｅ ｌ ｍ ｂａｓ ｏｎ ｅｄ ＭＡＴ ＡＢ ａ ｆｉ Ｌ ， ｎｄ ｎａｌ ｔｈｒ ｇｈ ｔ ｙ ｏｕ ｈｅ ｓｉ ｍｕｌ ｉ ｎ ａｔ ｏ ｔｏ ｂｔ ｎ ｈｅ ｏ ａｉ ｔ ｂｅｓ ｓ ｕｔ ｏ ｗｈｉ ｈ ｓ ｈｅ ｔ ｏｌ ｉ ｎ ｃ ｉ ｔ ｂｅ ｔ ｓ ｏｎ ｃ ｅ ｕｒｒ ｔ ｙ ｅｎ ｌ ．
Ｋ ｗｏｒ ｅｙ ｄｓ： ｎ ｏ ｏ ｙ Ｏ ｔ ｍ ｚ ｔ ｏ Ａ ｔ Ｃ ｌ ｎ ｐ ｉ ｉ ａ ｉ ｎ；Ｔ ａ ｅ ｉ ｇ Ｓ ｌ ｓ ａ ｒ ｂ ｅ ｒ ｖ ｌ ｎ ａ ｅ ｍ ｎ Ｐ ｏ ｌ ｍ；Ｍ Ｔ Ａ ＡＬＢ
１ 意 义和 目标
息素被表 达为一个函数 ， 该函数反映了相应 的行程 质量 。 过 通

本栏目责任编辑：唐一东人工智能及识别技术基于蚁群算法的智能图像识别应用研究肖宇(常州工程职业技术学院，江苏常州213164)摘要：由于受到干扰因素的影响，在图像识别过程中很多图像识别算法的效果都不太理想。

蚁群算法能通过区分图像像素的灰度，有效地对图像像素进行聚焦，从而实现智能图像识别。

本文在对蚁群算法进行综合分析的基础上提出了一种改进的蚁群算法，能够有效消除传统蚁群算法工作中存在的停滞现象，为其他相关研究提供理论参考。

关键词：蚁群算法；图像识别；图像分割中图分类号：TP18文献标识码：A文章编号：1009-3044(2019)31-0212-03开放科学(资源服务)标识码(OSID)：随着计算机技术的不断发展，图像识别技术在计算机技术的帮助下取得了突破性进展并在现实生活中得到了广泛应用。

目前常见的图像处理算法有很多种，各有优缺点，蚁群算法作为目前比较流行一种图像处理算法在图像分割、图像边缘检测和图像识别等方面都具有一定优势[1]，因此本文对蚁群算法进行了研究，分析了蚁群算法在智能图像识别中的应用，并总结了对蚁群算法进行改进的方法，希望对相关研究有所帮助。

蚁群算法是一种仿生学算法，其本质在于模仿蚂蚁在寻找食物的过程中选择路径。

起源于1992年意大利学者MarcoDo⁃figo 在他的博士论文中提出的一种基于蚂蚁觅食行为的算法模型[2]，到1996年，MarcoDofigo 在其论文中再次对蚁群算法做了详细概述，并对蚁群算法的优点进行了综合分析。

从那时起，国际学者关于蚁群算法的研究热情不断高涨，促进了蚁群算法理论的不断改进和应用。

在我国的发展蚁群算法虽然起步要晚于国外，但发展得很快。

1999年，吴庆洪在原有蚁群算法的基础上，提出了一种具有变异策略的蚁群算法，通过改变变异方式，克服了传统蚁群算法收敛速度慢的缺点[3]。

2001年，吴斌提出了一种问题分段的求解蚁群算法。

2005年，袁立提出了一种多线程蚁群算法，重点分析了蚁群在觅食过程中的策略选择和搜索能力，将该算法用于求解TSP 问题，其结果表明该算法具有很好的全局寻优能力。

科技创新与应用 Ｉ ２ ０ １ ５ 年 第８ 期
工 业 技 术
浅 谈机 械优 化设 计
李彩 凤
（ 牡丹江石油工具有限责任公 司， 黑龙 江 牡丹江 １ ５ ７ ０ ０ ０ ）
摘 要： 经 济的 高速 发 展 带动 了科 学的进 步 ， 比如机 械 优 化设 计 就是 最 近 出现 的 一 类全 方 面 的 学科 知识 ， 它 能 够处 理 那 些过 去 无
法处理的设计项 目。文章重点分析 了该项设计方法， 同时还简述 了其原理和应 用区域以及今后 的发展趋势。
关键 词 ： 优 化设 计 ； 约 束特 点 ； 函数 该设 计 最初 形 成 是在 上 个 世 纪 的 中后 期 ， 它将 最 优 化 理念 和 电 脑科技有效 的结合到一起 。通过这种措施 ， 能够有效 的提升设计 的 效率 以及 品质 。 最 终获 取 最为 合理 的设计 。 具体 来讲 ， 它涵 盖 两点 内 容 。一 是怎 么把 设 计 方 面 的问 题 变 为简 单 的模 型 ， 而且 要 保证 能 够 精准 的反馈 问题 的根 本 。 而建 立 模 型指 的 是选 择 正 确 的 变量 ， 提 出 优化 的制约要素以及相应 的函数 。 二是怎么获取上述模 型的最为合 理的方案。机械优化设计就是在特定 的环境条件 中， 在机械产品的 几何尺寸关 系、 形态和其他限制因素条件内， 以机械系统的强度 、 功 能、 经济性等为优化对象 ， 选取设计变量 、 建立约束条件 、 目标 函数 ， 并使 目标函数获得最优值一种现代设计方法。 因此优化设计是可广 泛应 用 于各 工 业 部 门的现 代 设计 理 论 和方 法 。 １设计 方 法 该 设计 方 法 被大 量 的应 用 到 机 械工 程 中 ， 主 要 是 因为 它 可 以在 特定 的背景 中确保方案最 为合理 ，而且 不需要使 用太 多的人力 物 力 。该 方 法从 最初 的数 值 法 到后 来 的数 值 分 析 ， 最 后过 渡 到 非数 值 分 析 。最 近几 年 由 于 电脑 技术 的广 泛应 用 ， 在 设 计 的 时候 可 以通过 合 理 的选 取设 计 数值 进 而 得 到最 为 优 秀 的方 案 ， 而 且还 能够 大 大 的 缩 短用 时 。将 该 方法 和电 脑科 技 有 效 的融 会 到 一起 ， 是 时代 发 展 的 产物 ， 必将 得 到发 扬 。 ２ 类 型 和特 征简 介 路布线设计 、 有 序 排 列 问题 、 二次分配 、 车 间 任 务 调 度 等 问题 的 求 解。 虽然蚁群算法具有并行计算 、 正反馈选择和群体合作等优点 ， 但 也存 在 着 容易 出现 “ 停滞” 现象 和需 要 较 长 的搜 索 时间 两个 缺 陷 。 吴 庆 洪 等提 出 了应 用 改进 型 蚁 群算 法 解 决 有序 排 列 问题 ， 运用 新 的状 态 转移 规 则 ， 讨论 不 同 的轨 迹 更 新规 则 对 仿 真结 果 的影 响 的一 种 具 有变异特征的蚁群算法 ， 并通过统计数据验证了相对于标准的蚁群 优 化算 法 中 ， 改进 型蚁 群算 法 的优 势 所在 。 ２ ． ５模 拟 退火 算 法 模 拟 退 火 算 法 ，最 早 在 １ ９ ５ ３年 由 Ｍｅ ｔ ｒ ｏ ｐ ｏ ｌ ｉ ｓ 提出 ， １ ９ ８ ３年 Ｋ ｉ ｒ ｋ ｐ ａ ｔ ｒ ｉ ｅ ｋ 成 功 地应 用 在组 合 最优 化 问题 。模 拟退 火 算法 是 一种 通 用 的优 化 算 法 ， 用 以 求解 不 同 的非 线 性 问 题 ； 能 够 发 挥 出 良好 的收 敛性特征 ， 而 且 适 应 能力 很 是 强 大 ； 对 不 可 微 甚 至不 连 续 的 函数 优 化， 能以较大概率求得全局优化解 ； 能处理不 同类型 的优化设计变 量； 并且对 目标 函数和约束 函数没有任何要求 ； 不需要任何 的辅助 信 息 。目前 已经 广泛 的应 用于 ： 神 经 网络 、 图像 处理 、 控制工程、 数值 分 析 和生 产 调度 等 。这个 方 法 虽然 有 很 多 的优 点 ， 不过 它 也存 在一 些缺点 ， 比如 它 的效 果 不是 很 好 ， 而且 整个 运 算 活动 耗 费 的 时 间 非 常久 。通 过上 文的 分 析我 们 得 知 了 这几 种 算 法本 身 的 优 点 和缺 陷 ， 应 该 尽量 的避 免其 缺 陷 ， 将 优 势 结合 到 一 一 起， 对 其 进 行完 善 。 ３合 理选 取 方 法 ２ ． １无 约 束优 化 设计 法 通过 上 文 中对 设 计 特征 的分 析 ，我 们 得 知要 想 保 证设 计合 理 ， 具 体 的说 分 成 两个 类 型 ， 一 种是 像 共 轭 梯度 法 、 最速下降法、 牛 就 要 正 确 的选 取优 化 方法 。 这 主 要是 因为 即使 是一 个 完 全 相 同 的内 顿法等方法 ， 它是利用 目标函数的一阶或二阶导数的无约束优化方 容 它 也会 存 在 很多 不 一样 的 解决 措 施 。 然 而并 非是 并 存 的 这几 个措 法。 另一种是像单形替换法 、 坐标轮换法等， 利用 目标 函数值 的无约 施 都 能够 将 问 题解 决 得 天衣 无缝 。 比如 一些 措 施会 使 得 设计 的最终 束优化方法。 结果和我们 当初的设置不符 。要想避免这种现象 ， 就需要我们牢牢 ２ ． ２遗传算法 此遵守四个基础原则。 第一 ， 要保证可靠性好 ， 第二要保证使用 的计 该方 法 是对 随 机群 体 不 断 的演 变 选择 ， 进 而获 取 最 为合 理 的 方 算 程 序 是合 理 的 ， 第 三要 确 保 其 稳定 ， 最 后 要 保 证 效率 。除 此之 外 ， 法 。它非 常 的类 似 于 自然 界 的 淘 汰法 则 ， 适 应社 会 发 展 的必 然 得 到 还需 要 工 作 者 的 工 作 经 验 丰 富 ，只 有 这 样 才 可 以 分 析 相 关 的 函 数 发展 ， 而 落后 的必然 会 被 遗弃 。 该 方法 有 两大 特 点 ， 即 能够 起 到优 化 值 ， 结合 复 杂性 等 要 素 对其 进 行 合理 的选 取判 断 。优 化设 计 的选 择 整体 的作 用 ， 同时还 有 很好 的适应 能 力 。 它被 应 用 到很 多 领域 中 ， 比 取决 于 数 学模 型 的特 点 ，对 于只 含 线性 约束 的非 线性 规 划 问题 ， 最 如 问题诊 断 等 等 。 最 近 几年 它 在工 程 方 面也 体现 出了 自身 的 巨大 价 适 应采 用 梯度 投 影法 ； Байду номын сангаас于 约 束 函数 和 目标 函数 均 为 显 函数 且 设 计 值。接下来就具体 的展开论述。第一是它能够论述可靠性问题 。第 变 量个 数 较 少 的 问 题 ， 采 用 惩 罚 函 数法 较 好 ； 针 对 那 些 求 导 有 难 度 二是能够辨别参数 。它能够大体的分辨结论数值 ， 明确了大体 的区 的要使用直接解法 ； 对于高度非线性的函数 ， 就要选取那些较为稳 间之后 ，再通过遗传措施对设定的数值 以及结论数值一起优化处 定 的措 施 。 理 。第 三 ， 能够 设计 机 械方 案 。为 了和 目前 的编 码 体 系保 持一 致 ， 其 ４ 结束 语 设置了一 系列的遗传方法 ， 通过这些方法掌控它的搜索活动 ， 而且 在 当前 社 会 ， 该 设 计 方 法是 一 个 非 常合 理 的方 法 ， 它 能 够 确 保 通过复制等活动不断的迭代 ， 进而得到最为优秀的方案。 除此之外 ， 机 械产 品 朝着 更 高 的 品质 发 展 。加 之 电 脑科 技 的 融 人 ， 使 得设 计 变 它还 可 以应 用 到很 多 的其他 行 业 中 ， 比如节 能 设 计 以及 数 控 加工 误 得 更 为 科 学 合理 ， 其 未来 是 非 常 乐 观 的 。在 现 阶段 ， 科 技 不 断 的发 差等。 展， 产 品之 间 的竞 争 日益 残 酷 ， 该 设 计 的 出现 在 很 大 程 度 上 给 机 械 上文讲述 了很多它的优点 ， 不过它也并非是完美的。比如 目前 工 程行 业 注 入 了无 限 活力 。要想 确 保 行 业有 所 发 展 ， 就 要 切实 的把 还无法优 化其 自身 的数值 ， 无法通过新 的设置来提升效率 ， 目前 的 力 学 知 识 以 及项 目实 践 活 动 和 电 脑科 技 等 相 关 知 识 紧密 的联 系到 操作 方 法 还不 是 很完 善 等 等的 一些 问题 。 一般 采 用惩 罚 函数 法 求解 起。 约 束优 化 问题 时 ， 其 难 点是 如 何 选 择合 适 的惩 罚 因子 。该 因子 太 大 参 考文 献 的话 ， 会使 得 搜索 工 作 变得 困难 ， 但 是 如果 设 置 得太 小 的话 ， 可 能造 【 １ ］ 张鄂 ． 机 械 与 工程优 化 设 计［ Ｍ ］ ． 科 学 出版社 ， ２ ０ ０ ８ ． 成 整个 惩 罚 函数 的极 小 解 不是 原 目标 函数 的极 小解 。 『 ２ １ 吴庆 明 ， 何 小新 ． 工程机 械 设 计『 Ｍ １ ， 武 汉 大 学 出版社 ， ２ ０ ０ ６ ． ２ ． ３ 约束 优化 设 计 法 ［ ３ 】 孙靖 民． 机械 优 化 设计 ［ Ｍ］ ． 机械 工业 出版 社 ， ２ ０ ０ ４ ． 根据处理约束条件 的方法不同可分为间接法和直接法 。 间接法 ｆ ４ １ － Ｙ － 国 强． 机 械优 化 设 计］ ＭＩ ． 机械 工业 出版 社 ， ２ ０ ０ ９ ． 常见 的有 增 广乘 子 法 、 惩 罚 函数 法 。 它是 将 非线 性 优 化 问题 转 化 成 ｆ ５ １ 陈秀 宁． 机 械优 化 设 计Ｉ Ｍ１ ． 浙 江 大 学 出版 社 ， ２ ０ １ ０ ． 线性规划 问题或是将约束优化问题转化成无约束优化问题来求解 。 『 ６ １ 黄 杰． 机 械 制 图与 Ｃ Ａ Ｄ ］ Ｍ］ ． 科 学 出版 社 ， ２ ０ ０ ９ ． 直接

一种优化的蚁群算法夏显清（绍兴托普信息职业技术学院，浙江绍兴312000）摘要：蚁群算法是一种新型的启发式算法，它具有许多优良性质，被广泛用于求解组合优化问题，但基本蚁群算法也存在诸多不足。

为使蚊群算法对应TSP 问题的解更加优良，提出了一种改进的蚁群算法并对它进行了试验，结果表明改进算法是有效的，这也为蚁群算法的优化提供了一个新的途径。

关键词：蚁群算法；组合优化；TSP 问题中图分类号：TP312文献标识码：A文章编号：1672-7800（2010）08－0065－021蚁群算法概述1.1定义蚁群算法（Ant Colony Algorithm ）是由意大利学者MacroDorigo 等人在上世纪90年代提出来的，是继遗传算法、人工神经网络等算法之后用于解决组合优化问题的又一种启发式算法，它借鉴蚂蚁通过自组织的合作能力所产生的群体智能来解决组合优化问题。

1.2人工蚁群与自然界蚁群的异同两者的相似之处：优先选择路径的机制、信息传递的方式。

两者的区别在于：人工蚁群的记忆能力、一定的算法规律。

1.3算法的数学模型表述蚁群算法有3种不同的模型：ant－cycle system 、ant－quanti－ty system 、ant－density system ，为充分利用整体信息，本文采用的是ant－cycle system 。

算法中有几个数学公式是很重要的：一个是蚂蚁根据概率大小选择路径的公式，另一个是路径上的信息素更新的公式。

1.3.1路径选择的数学公式S＝［τij （t ）］α［ηij ］β／∑j ∈allowed ［τij （t ）］α［ηij ］β若j ∈allowed 或＝0若j￠allowed 1.3.2信息素更新的数学公式τij （t＋1）＝ρ×τij （t ）＋Δτij （t ，t＋1）Δτij （t ，t＋1）＝∑［Δτij k （t ，t＋1）］Δτij k （t ，t＋1）＝Q ／L k （t ，t＋1）若蚂蚁k 在本次循环中经过ij路径或＝0若蚂蚁k 在本次循环中未经过ij 路径1.4关键参数的设置蚁群算法中α、β、ρ、m 等参数对算法性能有很大的影响。

电脑编程技巧与维护群智能算法高性能计算平台探究罗琼（四川化工职业技术学院，四川泸州646005）摘要：近年来，各研究学者通过基于生物学在动物等群体研究成果的基础上，提出了群智能的概念。

群智能技术主要针对生物在群体的社会性活动的理论抽象的基础上，通过进行模拟，以期解决目前遇到到各种结构方案的优化症结。

阐述了当前在群智能算法领域的一些主流的算法，并在分析的基础上，对蚂蚁优化算法在高性能计算平台的硬件实施方面提出了一些探究性意见与看法。

关键词：群智能算法；蚂蚁算法；硬件实现The Swarm Intelligence Algorithm for High Performance ComputingPlatform ResearchLUO Qiong（Sichuan College of Chemical Technology,Sichuan Luzhou646005,China）Abstract:in recent years,the scholars based on biology in animal groups basis of research results,proposed the concept of group intelligence.Swarm intelligence technology on biological in groups of social activity theory based on abstract,through simulation,in order to solve at present to meet various structure scheme optimization problem.The main contents of this pa－per include the in swarm intelligence algorithms in the field of some mainstream algorithms,and based on the analysis,the ant optimization algorithm in high performance computing platform hardware implementation are some exploratory ideas and comments.Key words:swarm intelligence algorithm;ant algorithm;hardware implementation1引言在开始进入正文之前，有必要先解析一下相关概念，以便使读者能更全面、更好地认识和理解群智能算法及其实现。

蚁群算法综述控制理论与控制工程09104046 吕坤一、蚁群算法的研究背景蚂蚁是一种最古老的社会性昆虫，数以百万亿计的蚂蚁几乎占据了地球上每一片适于居住的土地，它们的个体结构和行为虽然很简单，但由这些个体所构成的蚁群却表现出高度结构化的社会组织，作为这种组织的结果表现出它们所构成的群体能完成远远超越其单只蚂蚁能力的复杂任务。

就是他们这看似简单，其实有着高度协调、分工、合作的行为，打开了仿生优化领域的新局面。

从蚁群群体寻找最短路径觅食行为受到启发，根据模拟蚂蚁的觅食、任务分配和构造墓地等群体智能行为，意大利学者M.Dorigo等人1991年提出了一种模拟自然界蚁群行为的模拟进化算法——人工蚁群算法，简称蚁群算法(Ant Colony Algorithm,ACA)。

二、蚁群算法的研究发展现状国内对蚁群算法的研究直到上世纪末才拉开序幕，目前国内学者对蚁群算法的研究主要是集中在算法的改进和应用上。

吴庆洪和张纪会等通过向基本蚁群算法中引入变异机制，充分利用2-交换法简洁高效的特点，提出了具有变异特征的蚊群算法。

吴斌和史忠植首先在蚊群算法的基础上提出了相遇算法，提高了蚂蚁一次周游的质量，然后将相遇算法与采用并行策略的分段算法相结合。

提出一种基于蚁群算法的TSP问题分段求解算法。

王颖和谢剑英通过自适应的改变算法的挥发度等系数，提出一种自适应的蚁群算法以克服陷于局部最小的缺点。

覃刚力和杨家本根据人工蚂蚁所获得的解的情况，动态地调整路径上的信息素，提出了自适应调整信息素的蚁群算法。

熊伟清和余舜杰等从改进蚂蚁路径的选择策略以及全局修正蚁群信息量入手，引入变异保持种群多样性，引入蚁群分工的思想，构成一种具有分工的自适应蚁群算法。

张徐亮、张晋斌和庄昌文等将协同机制引入基本蚁群算法中，分别构成了一种基于协同学习机制的蚁群算法和一种基于协同学习机制的增强蚊群算法。

随着人们对蚁群算法研究的不断深入，近年来M.Dorigo等人提出了蚁群优化元启发式(Ant-Colony optimization Meta Heuristic，简称ACO-MA)这一求解复杂问题的通用框架。

52% ； " $ 57 +6 ； $ $ +678( # 52 +6 ； $ +6786 $ $ （ +6 ） （ +( 52 9 867+( % +678(
:;"( 8678(7+(2" ； :;"( 867+(7" ； :;"( +(78(2" ；
） ； "<* " （; ）
!$!
规则后剪枝
路径节点的重复选择可能会带来分类规则对样例的过度
基于蚁群算法的分类规则挖掘算法
! 吴正龙 %，
王儒敬 !
滕明贵 !
许梅生 %
% （解放军炮兵学院， 合肥 !?""!% ） ! （中国科学院合肥智能机械研究所， 合肥 !?""!% ）
DC38)0： :29-10/-1EF+82//$G/3$G摘 要 提出了一种基于蚁群算法的分类规则挖掘算法。算法实质上是一种序列覆盖算法： 蚁群搜索一个规则， 移去它
（*+>,E7F% ） ； NIG*-,
&’()*+,--*， .$/ 等 0%"1 采 用 一 种 基 于 信 息 论 的 方 法 来 构 造 启
发式函数， 每一个属性节点的启发式函数值与其分类样例的能 力成正比。 基于信息论的属性选择已经被证明倾向于选出取值 多但每个取值内的例子不多的属性，这被称为算法的偏见 。而在其 后 的 增 益 比 率 属 性 选 择 041则 可 能 会 对 属 性 选 择 （2*’3） 造成误导， 即选择被属性的信息熵决定， 而不是被信息增益决 定。这往往是错误的。为此 5’+6’(’3 于 %44% 年提出基于距离 的属性选择法， 有效克服以上问题， 并且证明了基于距离的属 性选择法， 可以产生出比增益比率属性选择法更小的决策树。 这里根据基于距离的属性选择法来构造启发式函数， 定义 每个属性节点 !"#$%& 的启发式函数值 !%& 为： （/0 ， !%&7 8!"#$%&8 -. /1 ） 8!#’%(%()*"+,

蚂蚁是自然界中常见的一种生物，在昆虫世界，蚂蚁是一种群居的世袭大家庭，我们称之为蚁群（ant colony）。

蚁群具有高度组织的社会性，彼此间的沟通不仅可以借助触觉、视觉的联系，在大规模的协调行动上可以借助外激素（pheromone）之类的生产化信息介质。

蚁群的觅食行为是最易观察的，每只蚂蚁具有如下的职能：平时在巢穴附近作无规则行走，一旦发现食物，如果独自能搬的就往回搬，否则就回巢搬兵，一路上它会留下外激素的嗅迹，其强度通常与食物的品质和数量成正比；若其他蚂蚁遇到嗅迹，就会循迹前进，但也会有一定的走失率，走失率与嗅迹的强度成反比，从而相互协作，完成复杂的任务。

1991年意大利学者M.Dorigo等人首先提出了蚁群算法(ant colony algorithm)，人们开始了对蚁群的研究：相对弱小，功能并不强大的个体是如何完成复杂的工作的，因此在此基础上，蚁群算法从对蚁群行为的研究中产生且逐渐发展起来。

蚁群算法是一种随机搜索算法。

诸多研究证明，蚁群算法具有很强的寻优能力，不仅利用正反馈原理，在一定程度上加快了寻优过程，而且是一种本质并行算法，不同个体之间进行信息交流和传递，从而相互协作，有利于发现更好解。

它具有以下优点[3]：（1）较强的通用性：对基本蚁群算法模型稍加修改，便可以应用于其他问题。

（2）分布式计算：蚁群算法是一种基于种群的进化算法，具有本质并行性，易于并行实现。

（3）易于与其它方法结合：蚁群算法很容易与多种启发式算法结合，以改善算法的性能。

蚁群算法也有一些缺陷：（1）需要较长的搜索时间：由于蚁群中多个个体的运动是随机的，虽然通过信息的交流能够向着最优路径进化，但是当群体规模较大时，很难在短时间内从复杂无章的路径中找出一条较好的路径。

（2）容易出现停滞现象（stagnation behavior）：即在搜索进行到一定程度后，所有个体所发现的解完全一样，不能对解空间进一步进行搜索，不利于发现更好的解。

赵
伟等 ： 一 种 基 于 惩 罚 函数 和 新 信 息 素 更 新 方 式 的蚁 群 算 法
１ Ｏ ７
附 中文参 考文献 ：
［ １ ］ 冀俊忠 ， 黄振 ， 刘椿年． 一 种快速求解 旅行商 问题的蚁群 算法
作者 简 介 ：
赵伟 （ １ ９ ６ ７一 ） ， 男， 吉林 长 春 人 ， 博 士
黄 金 海岸 ， 澳大利亚 （ Ｇ ｏ ｌ ｄ Ｃ ｏ ａ ｓ ｔ ， Ａｕ ｓ ｔ ｒ ａ ｌ ｉ ａ ）
２ ０ １ ３ 年 ４月 １ ４日～ ２ ０ １ ３年 ４月 １ ７日
ｈ ｔ ｔ ｐ： ／ ／ ｐ ａ ｋ ｄ ｄ ２ ０ １ ３ ． ｐ ａ ｋ ｄ ｄ ． ｏ ｒ ｇ ／
Ｉ ｍｐ ｏ ｒ ｔ ａ ｎ ｔ Ｄａ ｔ ｅ ｓ
Ｐ ａ ｐ ｅ ｒ ｓ ｕ ｂ ｍｉ ｓ ｓ ｉ ｏ ｎ ｄ ｕ ｅ ：Ｏｃ ｔ ．１ （ Ｍｏ ｎ ） ．２ ０ １ ２ Ｎｏ ｔ ｉ ｉｃ ｆ ａ ｔ ｉ ｏ ｎ ｔ ｏ ａ ｕ ｔ ｈ ｏ ｒ ：Ｄｅ ｃ ．１ ９ （ Ｗｅ ｄ ） ．２ ０ １ ２
Ｃａ ｍｅ ｒ ａ ｒ ｅ ａ ｄ ｙ ｄ ｕ ｅ ：Ｊ ａ ｎ ．６
算机研究与发展 ， ２ ０ ０ ３ ， ４ ０ （ ９ ） ： １ ３ ５ １ － １ ３ ５ ６ ．
ｐ ｒ ｏ ｆ ｅ ｓ ｓ ｏ ｒ ， ＣＣＦ ｍｅ ｍｂ ｅ ｒ （ Ｅ２ ０ ０ ０ １ ３ ７ ０ ３ Ｓ） ， ｈ ｉ ｓ ｒ ｅ ｓ ｅ ａ ｒ ｃ ｈ ｉ ｎ ｔ ｅ ｒ — ｅ ｓ ｔ ｓ ｉ ｎ ｃ ｌ ｕ ｄ ｅ ｖ ｉ ｒ ｔ ｕ ａ ｌ ｒ ｅ ａ ｌ ｉ ｔ ｙ ａ ｎ ｄ ｄ ａ ｔ ａ ｂ ａ ｓ ｅ ｔ ｅ ｃ ｈ ｎ ｏ ｌ ｏ ｇ ｙ， ａ ｒ ｔ ｉ ｆ ｉ ｃ ｉ ａ ｌ ｉ ｎ ｔ ｅ ｌ ｌ ｉ ｇ ｅ ｎ ｃ ｅ ，ａ ｎ ｄ ｉ ｍａ ｇ ｅ ｐ ｒ ｏ ｃ ｅ ｓ ｓ ｉ ｎ ｇ ．

1
基本 ACO 原理
为了说明 A CO 模型 , 这里引入旅行商问题 ( T SP) , 它是一类经典的 组合优化 问题 , 即 在给定城 市个数和各 城市之 间距
离的条件下 , 要找到 1 条遍历所有城市当且仅当 1 次最短的线路 .
n
为模拟真实蚂蚁的行为 , 首先引入如下标记 : m 是蚁群的规模 ; bi ( t) 是 t 时刻位于城市 i 的蚂蚁数 量 , m =
i= 1
bi ( t) ; d ij
是两城市 i 和 j 之间的距离 ; 运行中保持不变 ;
ij
ij
是由城市 i 转移 到城市 j 的可见度 , 反映城市 i 转移到城市 j 的启发信息 , 这个量在 A CO 的
ij
是边 ( i, j ) 上的信息素轨迹强度 ;
是蚂蚁 k ij 是蚂蚁 k 的转移概
实际工程问题常具有复杂性、 非线性等特 点 , 而 它的解决 通常也 是一种 寻求最 优决策 的过程 , 因此 寻求一 种适合 大规 模并行、 具有智能特征的优化算法已经成为引 人注目的 研究方 向 . 目前 , 除了业 已得到 公认的 遗传算 法、 模 拟退火 算法、 禁 忌搜索算法等热门进化算法 , 蚁群优化算法 [ 1- 3] ( A nt Colony Optimization A lgo rithm, ACO , 也称蚂蚁系统 ) 正在开始崭露头 角 , 为复杂的系统优化问题提供了新 的具有竞争力的求解算法 . A CO 是 由意大利学者 M . Do rigo 等人于 1991 年首先提出来 一种新兴模拟生物智能的算法 , 在短期内得到 了迅速的发展 , 除了 用于大 批经典 优化问 题的求 解 , 如 二次分 配问题 ( Q uad r atic A ssig nment P roblem, Q A P) 、 有序排列问题 ( Sequential O rdering Pro blem, SO P) [ 2- 16] 等 , 在实际工程领域也得到广泛的 应用 .

关于蚁群算法的探讨张玉春;程春英【摘要】Ant colony algorithm which is a new heuristic algorithm with characteristics of robustness and global search has been widely applied in the fields of artificial intelligence,system control and pattern recognition etc.This paper elaborates the foundational theory on ant colony algorithm and states improved algorithm.It also points out the perspective of ant colony algorithm.%蚁群算法是一种新型的启发式算法,具有正反馈、分布式计算和用于贪婪搜索的特点,因而具有较强的鲁棒性和搜索性,已广泛地应用于人工智能、系统控制、模式识别等工程领域,本文阐述了蚁群算法的基本原理,给出了现有的各种改进的算法,并展望了蚁群算法的发展方向.【期刊名称】《内蒙古民族大学学报（自然科学版）》【年(卷),期】2011(026)006【总页数】3页(P656-658)【关键词】蚁群算法;信息素;改进【作者】张玉春;程春英【作者单位】内蒙古民族大学计算机科学与技术学院,内蒙古通辽028043;内蒙古民族大学计算机科学与技术学院,内蒙古通辽028043【正文语种】中文【中图分类】TP1831 引言蚁群算法〔1〕是一种仿生随机优化算法.在20世纪90年代，由意大利学者M.Dorig〔1〕等人从生物进化的机理中受到启发，通过仿真自然界的蚂蚁行为，提出的一种仿真进化算法.该算法已被成功应用于旅行商问题〔2〕、二次分配〔3〕、路径规划〔4〕、车间作业调度问题、车辆调度〔5〕等问题的求解.蚁群算法具有正反馈、分布式计算和用于贪婪搜索的特点.正反馈有助于快速找到问题较好的解；分布式计算可避免在地带过程中出现早熟现象；蚁群算法是继模拟退火、遗传算法、禁忌搜索等之后的又一启发式智能优化算法，具有很强的通用性和鲁棒性.蚁群算法提出到现在，因其在求解组合优化问题中突出表现，吸引了人们极大的关注.但是蚁群算法也存在一些缺陷，如需要较长的搜索时间，易于陷入局部最小值等.所以出现了大量的改进的蚁群算法.2 蚁群算法基本原理2.1 蚁群算法的特性蚁群算法是模拟自然界中蚁群的觅食行为而形成的一种模拟进化算法.大量的研究发现，蚂蚁个体之间信息的传递是通过一种称为信息素的化学物质进行的〔6〕.当蚁群在觅食过程中会释放一定量的信息素，而且蚂蚁在运动过程中会感知信息素强度，并以此指导自己运动方向.当一条路径上信息素浓度越高就表明该路径上通过的蚂蚁数量也就越多，其它蚂蚁选择该路径的可能性也就越大.这种大量蚂蚁组成的蚁群的集体行为表现出一种信息反馈现象：某一路径经过的蚂蚁越多，该路径的信息素强度就越大，其它蚂蚁选择该路径的概率就会越大. 通过对蚁群算法的原理的研究，可以得出蚁群算法的一些基本的特征.（1）正反馈性.（2）强启发性.（3）协调性与并行性.2.2 蚁群算法的数学模型（1）蚂蚁个体.由于蚁群算法是对自然界中真实蚂蚁觅食行为的一种模拟，因此首先必须对真实蚂蚁进行抽象，而不可能也没有必要对蚂蚁个体进行完全的再现.这样抽象出来的人工蚂蚁可以看作是一个简单的智能体，能够完成所求问题解的构造过程.（2）寻找路径.蚂蚁在觅食过程中主要按照所处环境中的信息量来决定其前进的方向，因此可以把觅食过程抽象成算法中解的构造过程，将信息素抽象为存在于图的边上的轨迹.用任意两个节点分别表示蚂蚁的巢穴和食物源，人工蚂蚁从巢穴点按照一定状态转移概率选择下一个节点，依次类推，最终选择行走到食物源节点，这样便得到了所求问题的一个可行解.（3）信息素.蚂蚁总是在所经过的路径上连续不断的留下信息素，而信息素也会随着时间的推移而连续不断地挥发.由于计算机处理的是离散事件，所以必须使信息素的挥发也是离散发生的.一般采取的做法是：当蚂蚁完成从一个节点到下一个节点的移动后，即经过一个时间单位之后，进行一个信息素的挥发，而这种在离散时间点进行信息素挥发的方式与蚂蚁觅食过程的机理是一致的.（4）启发因子.在决定蚂蚁在行走方向的状态转移概率时，引入了一个随机搜索的过程，即引入了启发因子，在根据所求问题空间的具体特征，给蚁群算法一个初始的引导，这个过程极大的增加了算法的时间有效性，从而使蚁群算法的有效应用成为可能.下面简单介绍一下TSP问题的基本蚁群算法求解.假设n个城市，m个蚂蚁，任意两城市r，s之间的距离为d（r，s），T（r，s）表示两个城市间信息素的浓度，△T（r，s）k表示第k个蚂蚁访问过支路（r，s）后释放的信息素浓度.Pk（r，s）表示第k个蚂蚁的转移概率：式中:s表示未访问过的城市;Z表示已经访问过城市的集合;（r，s）等于l/d（r，s），称为边弧的能见度;α为信息素浓度的重要程度;β为可见度的相对重要程度.α—为信息启发式因子，表示轨迹的相对重要性，它反映了蚂蚁在运动过程中所积累的信息素在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，表明蚂蚁之间协作性越强.β—为期望启发式因子，表示期望值的相对重要程度，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，则该状态转移概率越接近于贪婪规则.信息素浓度更新公式为式中:表示信息素浓度挥发后的剩余浓度：式中Q为一个常数，表示蚂蚁完成一次完整的路径搜索后释放的信息素的总量Lk 表示路径总长度.3 蚁群算法的改进与发展近年来，关于蚁群优化算法的研究目标主要集中在如何改善蚁群算法的性能方面.具体地，改进的途径集中在以下几方面：（1）改进信息素轨迹的更新机制.①精华蚂蚁系统（EAS）.精华蚂蚁系统是对基本蚁群算法的第一次改进，其核心思想是将每次循环中找到局部最优路径的蚂蚁称为精英蚂蚁，增大其释放的信息素量.Dorigo〔2〕等人对精华蚂蚁系统求解TSP问题进行了试验，结果表明比基本蚁群算法有着更快的进化速度.②基于排列的蚂蚁系统（ASrank）.基于排列的蚂蚁系统的核心思想是：根据每只蚂蚁所生成的问题解决方案的优劣进行排序，并对信息素轨迹量的更新进行加权更新.B Bullnheimer等人通过试验表明基于排列的蚂蚁算法比AS和EAS有着更高的寻有能力和更快的求解速度.③孙泽宇等人提出了改变局部信息素的迭代更新规则和改进伞局更新策略，并对相应参数做动态设置，进而抑制早熟现象出现，减少了冗余码的产生，提高了全局的搜索能力，加快了系统的收敛速度.（2）自适应调蚁群算法.张纪会〔7〕等人从选择策略方面进行修改，采用确定性选择和随机选择相结合的选择策略，并且在搜索过程中动态地调整作确定性选择的概率当进化到一定代数后，再对路径上信息量作动态调整，缩小最好和最差路径上的信息量的差距，并且适当加大随机选择的概率，以利于对解空间的更完全搜索，从而可以有效地克服基本蚁群算法的两个不足我们的方法，属于自适应方法，此算法按照下式确定蚂蚁k由i转多到的下一城市s:夏鸿斌〔8〕等人提出了一种具有自适应并行机制的选择和搜索策略.该策略通过将蚁群划分为若干个子群，不同子群的蚂蚁释放不同类型的信息素，引入了吸引因子和排斥因子，实现了一种多蚁群并行选择策略，以加强其全局搜索能力.（3）将蚁群算法与其他智能优化算法相结合①修春菠〔9〕等人将蚁群算法与鱼群算法相结合，将鱼群算法中拥挤度的概念引入到蚁群算法中.该算法在寻优初期具有较强的遍历寻优能力，能够较快发现全局最优解的存在，而寻优后期，算法利用信息素正反馈的作用保持了较快的收敛速度.仿真结果验证了该方法的有效性.② 翁国栋〔10〕等人将蚁群算法与遗传算法结合，形成一种时间效率和求解效率都比较好的新的启发式算法.将其应用于TSP问题上，通过仿真实验验证了该方法的有效性.③ 吴建辉〔2〕等人将蚁群算法与免疫算法相结合，提出了一种新的融合优化方法：结合抗体小窗口局部搜索算法的蚁群和克隆选择融合算法（ACLA）.针对TSP实验结果表明，该算法在收敛速度与求解精度上均取得了较好的效果.④吴庆洪〔11〕等人提出了具有变异特性的蚁群算法该算法为了克服AS的收敛较慢的问题，采用逆转变异方式，随机地进行变异，以增大进化时所需的信息量.因而具有较快的收敛速度.4 结束语蚁群算法在应用上取得了巨大的成就，但是，其本身没有一个固定的数学模型支撑，还处于实验论证阶段，因此，对其改进还有很大的空间.（1）蚁群算法理论的研究.目前对蚁群算法的研究，有算法意义上的研究，还有从仿真模型角度的研究.但现阶段对蚁群算法的研究还只是停留在仿真阶段，尚未能提出一个完善的理论分析，对它的有效性也没有给出严格的数学解释.因此，对蚁群算法的理论进行研究非常重要.（2）将蚁群算法和其它算法的融合.现阶段，蚁群算法与模拟退火算法、遗传算法、微粒群算法、人工免疫算法等的融合已有不少成果.但是，蚁群算法与人工鱼群算法和蜂群算法等一些新的仿生优化算法之间的融合还是很少.（3）加强蚁群算法应用的研究.在蚁群算法的研究方面还存在许多问题需要进一步的解决，比如选择初始化参数的问题、信息素分配的问题和收敛速度等问题.参考文献【相关文献】〔1〕A Colorni,M Dorigo,V Maniezzo.Distributed optimization by antcolonies〔J〕.Pronceedings of 1st European Conference on Artificial Life,1991:134-142.〔2〕吴建辉，张兢，刘超华.基于蚁群算法和免疫算法融合的TSP问题求解〔J〕.湖南大学学报（自然科学版），2009,36（10）:82-87.〔3〕V Maniezzo.Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem〔J〕.INFROMS Journal on computing,1999,11（4）:358-369.〔4〕王旭,崔平远,陈阳舟.基于蚁群算法求路径规划问题的新方法及仿真〔J〕.计算机仿真，2005,22（7）:60-62.〔5〕R S.Parpimization algorithm〔J〕.IEEE Trans on Evolutionary computation,2002,6（4）:31-38.〔6〕M Dorigo,E Bonabeau,G Theraulaz.Ant algorithm and stigmery〔J〕.Future Generation Computer Systems,2000,16（8）:851-871.〔7〕张纪会，高齐圣，徐心和.自适应蚁群算法.控制理论与应用，2000，17（1）:1-3.〔8〕夏鸿斌，须文波，刘渊.自适应并行机制的改进蚁群算法〔J〕.系统工程与电子技术，2009，31（12）:2973-2976.〔9〕修春菠，张雨虹.基于蚁群与鱼群的混合优化算法〔J〕.计算机工程，2008,34（14）:206-208.〔10〕翁国栋.蚁群算法与遗传算法在TSP问题上的融合〔J〕.福建电脑，2006（2）:115-116. 〔11〕吴庆洪，张纪会，徐心和.具有变异特征的蚁群算法〔J〕.计算机研究与发展，1999，36（10）:1240-1245.。

蚁群算法的原理与运用摘要：意大利学者通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法——蚁群算法。

该算法已经在组合优化、函数优化、系统辨识、网络路由、机器人路径规划等领域获得了广泛应用，并取得了较好结果。

本文围绕蚁群算法的原理、理论及其应用，就TSP(旅行商问题）、以及OPP(最优路径问题）在matlab 中进行仿真并分析其结果。

关键词：蚁群算法；旅行商问题；最短路径问题；仿真Abstract:A population-based simulated evolutionary algorithm called ant colony algorithm(ACA for short)was proposed by Italian researchers. The algorithm has been widely applied to the fields of combinatorial optimization , function optimization, system identification, network routing, path planning of robot, good effects of application are gained. This paper focuses on the principles, theory, and application of ACA, trying to solve the the traveling salesman problem and the optimal path problems by simulating in matlab to analyze the result.Keywords:ant colony algorithm; traveling salesman problem; shortest path problem ; simulation1绪论1.1引言各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。

蚁群算法及其在序列比对中的应用研究综述摘要：蚁群算法是一种新颖的仿生进化算法。

作为一种全局搜索的方法，蚂蚁算法具有正反馈性、并行性、分布性、自组织性等特点，自提出以来，便在求解复杂组合优化问题上显示出了强大的优势。

序列比对是生物信息学的基础，通过在比对中获得大量的序列信息，可以推断基因的结构、功能和进化关系。

本文首先详细阐述了蚁群算法的基本原理、各种改进技术及收敛性分析，然后对蚁群算法在双序列比对和多序列比对的应用研究进行了综述和评价，最后指出了下一步的研究方向。

关键词：蚁群算法；序列比对；信息素Abstract: Ant colony algorithm (ACA) is a novel bionic evolutionary algorithm. As a global searching approach，ACA has some characteristic，such as positive feedback, distributing，paralleling, self-organizing, etc，and from it was introduced, it has been used to solve all kinds of complex optimization problem. Sequence alignment is the basement of Bioinformatics. With the wealth of sequence information obtained from sequence alignment, one can infers the structure, function and evolutionary relationship of genes. In this paper, the basic principles of ACA are introduced at length, and various improvements and convergence Analysis of ACA are also presented. Then the current study of double sequence alignment and multiple sequence alignment based on ant colony algorithm are reviewed and evaluated. Finally, some future research directions about ACA are proposed.Key words: Ant Colony Algorithm; Sequence Alignment; Pheromone1 引言蚁群算法(Ant Algorithm)是一种源于大自然中生物世界的新的仿生类算法，作为通用型随机优化方法，它吸收了昆虫王国中蚂蚁的行为特性，通过其内在的搜索机制，在一系列困难的组合优化问题求解中取得了成效。