一种新的进化算法——蚁群算法1
需积分: 0 13 浏览量
2022-08-03
20:52:54
上传
评论
收藏 119KB PDF 举报
１ ９９９年 ３月
ｆ
第 ３期
３ ～ ］，１０７ 『
一
种 新的进 化算 法
张纪会 徐心和
， ＿ －
， — —
一
蚁 群算 法
０Ｚ
（东北大 学控制 仿真 研究 中心 ，辽宁 沈 阳 １１０００６）
摘要 升绍一种崭新的求解组合优化问题的方法一人工蚁群算法．该方法通过模拟蚁群搜索食物的
过程 ，达 到求解 比较 困 难 的组合 优化 之 目的．该方 法 的主 要特 点是 正 反馈 、分 布式计 算 、与 某种 启发
式算 法相 结 合．正反 馈 过程使 得该 方 法 鸵很快 发 现较好 解 ；分 布式计 算 使得 该 方法 易于 并行 实 现 ；与
启发 式算 法相结 合 ，使 得该方 法 易于发现 较 好解．研究 表 明该 方怯是 一种基 于种 群的 鲁棒性 较强 的 算
法 ．
关蕾 词 蚁群系统 模拟进化算法 组合优化
Ａ Ｎｅｗ Ｅｖｏｌｕｔｉｏｎａｒｙ Ａｌｇ０ｒｉｔｈｍ— — Ａｎｔ Ｃｏｌｏｎｙ Ａｌｇｏｒｉｔｈｍ
ＺＨＡＮＧ Ｊｉｈｕｉ ＸＵ Ｘｉｎｈｅ
（Ｃｏｎｔｒｏｌ＆ Ｓｉｍｕｌａｔｉｏｎ Ｃｅｎｔｅｒ，ＮＥＵ ，Ｓｂｅ ｎｙａｎｇ １１０００６）
Ａｂｓｔｒａｃｔ Ａ ｎｅｗ ｔｙｐｅ ｏｆ ｓｉｍ ｕｌａｔｅｄ ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍ ，ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ， ｉｓ
ｉｎｔｒｏｄｕｃｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ． ｗｈｉｃｈ ｉｓ ｕｓｅｄ ｔｏ ｓｏｌｖｅ ｓｏｍｅ ＮＰ ｈａｒｄ ｃｏｍｂｉｎａｔｏｒｉａｌ
ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ｓ ｔｈｒｏｕｇｈ ｓｉｍ ｕｌａｔｉｎｇ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ａｎｔｓ ｓｅａｒｃｈｉｎｇ ｆｏｒ ｆｏｏｄ． Ｔｈｉｓ
ａｌｇｏｒｉｔｈｍ ｈａｓ ｓｅｖｅｒａｌ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｓｕｃｈ ａｓ ｐｏｓｉｔｉｖｅ ｆｅｅｄｂｅ ｃｋ，ｄｉｓｔｒｉｂｕｔｅｄ ｃｏｍ ｐｕｔｉｎｇ
ａｎｄ ｃｏｍ ｂｉｎａｔｉｏｎ ｗｉｔｈ ｃｅｒｔａｉｎ ｈｅｕｒｉｓｔｉｃｓ．Ｐｏｓｉｔｉｖｅ ｆｅｅｄｂａｃｋ ｍ ａｋｅｓ ｉｔ ｅａｓｉｅｒ ｔｏ ｆｉｎｄ ｂｅｔｔｅｒ
ｓｏｌｕｔｉｏｎｓ，Ｓｉｍ ｕｌａｔｉｏｎｓ ｄｅｍ ｏｎｓｔｒａｔｅ ｔｈａｔ ｉｔ ｉｓ ａ ｒｏｂｕｓｔ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｐｏｐｕｌａｔｉｏｎ ａｎｄ
ａ ｐｒｏｍ ｉｓｉｎｇ ｗ ａｙ ｆｏｒ ｏｐｔｉｍ ｉｚａｔｉｏｎ．
Ｋｅｙｗｏｒｄｓ ａｎｔ ｓｙｓｔｅｍ ｌ ｓｉｍ ｕｌａｔｅｄ ｅｖｏｌｕｔｉｏｎａ ｒｙ ａｌｇｏｒｉｔｈｍ ；ｃｏｍｂｉｎａｔｏｒｉａｌ ｏｐｔｉｍｉｚａｔｉｏｎ
１ 引言
组 合优 化 问题很 早就 引起 了人 们的 趣 ，但 是 由于许 多 组合 优化 同题 都 是 ＮＰ 难 的 ，对 于这 类 问题 ，
至 今 尚无很 好的 解决办 法．一般 采用 启 发式 算法 来 解决．近 年 来 ＋随着 计算 技 术 的发 展 ，一 些新 的智 能算 法
（如 遗传 算法 嘲、模 拟 退 火 算 法州 、禁 忌 搜 索 算 法 ）得 到 了迅 速 发 展 和 广泛 应 用．特 别是 模 拟 进 化 算 法
（ＧＡ、ＧＰ、ＥＳ），无 论理 论 研究 还是 应 用研 究都 空前 活跃 ，同时 ，一些 新 的模 拟进 化算 法 也 逐渐 发 展起 来．
本 文 介 绍 的人 工 蚁 群 算 法 就 是 一 种 新 型 的模 拟 进 化 算 法．该 算 法 是 由 意 大 利 学 者 Ｍ．Ｄｏｒｉｇｏ、Ｖ．
Ｍａｎｉｅｚ∞ 、Ａ．Ｃｏｌｏｒｉｎｉ等 人首先提 出的。。 。，称 之为蚁 群 系统（ａｎｔ ｃｏｌｏｎｙ ｓｙｓｔｅｍ），并 应用 该算 法求 解 ＴＳＰ
问 题 、分配 问题 、ｊｏｂ ｓｈｏｐ调 度 问题 Ⅲ ，取 得 了较 好 的结 果 ．受 其 影 响 ，蚁群 系 统 模 型逐 渐 引 起了 其 它
研 究者 的注 意 ，Ｄ．Ｃｏｓｔａ和 Ａ．Ｈｅｒｔｚｃ 在 Ｍ．Ｄｏｒｉｇｏ等 人研 究 成 果 的基础 上 ，提 出了 一种 求 解分 配 类型 问
题 （ａｓｓｉｇｎｍｅｎｔ ｔｙｐｅ ｐｒｏｂｌｅｍ）的一 般模 型 ，井用 来 研 究 图着 色问 题．Ｇ．Ｂｉｌｃｈｅｖ、Ｉ．Ｃ Ｐａｒｍｅｅ 研 究 了求 解
连 续空 间优 化问 题的蚁 群 系统 模型．虽 然这些 成果 仅是 初步 的 ，但 是这 些 研究 已 显示 出蚁 群算 法 的一些 优
点．国 内 目前 尚无这 方 面的 研究 发表 ，因此 我们 在此 介 绍这 种 方 法 的基 本 原理 ，希 望 对 有 关研 究能 有所 启
发 ．
收稿 日期 ：１ ９９ ７ １ ０ １ ４
基金 项 目：本项 目得到 国家 自然科 学基金 与 ８６３高技 术基盎 资助
哔一
维普资讯 http://www.cqvip.com
首席程序IT
- 粉丝: 29
- 资源: 305
最新资源
- JavaScript《基于自动分析数据并给出营业建议的餐厅管理系统（接入AI） 》+源代码+项目说明及资料
- 355670834783295707ad04e-427f-4cde-9589-e578224a8459.zip
- 动态sql解析引擎，类似mybatis动态sql的功能
- EDA365-Skill-V2.5安装包，支持Allegro17.x版本
- C# 常用单词汇总，常用单词汇总
- 【ERP标准流程-标准流程-库内业务管理】（DOC 14页）.doc
- Python《数据库期末作业-餐厅点单系统 》+源代码+设计资料
- 学生成绩管理系统（C++课程设计
- 双指针法判断链表有环-go语言实现
- MyBatis动态SQL是一种强大的特性，它允许我们在SQL语句中根据条件动态地添加或删除某些部分，从而实现更加灵活和高效的数据
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0