《机器人路径规划的蚁群算法设计与实现毕业论文.pdf》由会员分享，可在线阅读，更多相关《机器人路径规划的蚁群算法设计与实现毕业论文.pdf（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、XXX大学 毕业设计（论文）机器人路 径规 划的 蚁 群 算 法设 计 与实现学院名称 信息与通信工程学院专业名称 自动化学生学号 XXXXXX学生姓名 学生姓名指导教师 教授姓名助理指导老师 老师姓名202X年X月摘要机器人路 径规 划是指机器人按照某一指令来搜索 一条从起 始状 态到目 标状 态的 最优路 径或近 似最优的 无碰 路 段，它是实现 机器人控制与导航 的 基础。本文 研 究 的 是用 蚁 群 算 法来求解 机器人最优路 径规 划的 方法。建立 一个机器人路 径规 划的 模型，并模拟仿真。实验 仿真 结 果验 证 了算 法的 有效性，即使处于复杂的 障 碍 物 的 环 境下，也
2、能 很快的 找出最优路 径。关键 词：蚁 群 算 法；机器人；路 径规 划2ABSTRACTRobot robot path planning refers to an optimal path from th e initial state to a target state or approximate optimal path with out touch ing th e search path according to a performance index,wh ich is one of th e basic robot control and navigation.Th is
3、article is based on ant colony algorith m for robot optimal path planning meth ods.Build a robot path planning based on th is model,and simulation by MATLAB.Th e simulation results sh ow th e effectiveness of th e algorith m,even in complex geograph ical obstacles,using th e algorith m can quickly w
4、ork out th e optimal path.Keywords:antcolony optimizatio；robot；path planning3目录摘要.2ABSTRACT.31绪 论.52蚁 群 算 法.82.1基本蚁群算法的原理.82.2蚁群算法的系统学特征.92.3蚁群算法的优点.103机器人路 径规 划的 蚁 群 算 法设 计.123.1机器人路径规划问题.123.2蚁群算法的流程设计.123.3蚁群算法实现.143.3.1主程序模块.143.3.2初始化模块.153.3.3解搜索模块.163.3.4保优与信息素更新模块.174蚁 群 算 法实验 分析.124.1关键参数介绍
5、.184.2算法参数设置.184.2.1信息素挥发系数.184.2.2蚂蚁数量.184.2.3信息激素物质的浓度和能见度.194.2.4启发式因子.194.3实验结果分析.195总结 和展望.27参考 文献.28致 谢.29附 录.3041绪论自 然界 中，我们总是可以发现 蛆 蚁 所发现 的 食 物 总是随 机的 出现 在巢穴 附 近。经 过 仔细 的 观 察，我们就可以发现，过 了一段时间，蛆 蚁 们就能 找到食 物，而 且 它们从巢穴 对食 物 源之间 的 路 段总是最短 的。蛆 蚁 虽 小，且个体能 力有限，但是 通 过 分工、合作，它们可以完成不论 那 个蛆 蚁 都 无法独 自 完成
6、的 复杂工作，例如 蛆 蚁 在寻找食 物 的 进 程 中，他们通 过 相 互协同工作，总是能 找到一条从食 物 到自 己巢穴 的 相 对最短 路 段。在现 实自 然生 活中，我们可以通 过 观 察，就会发现 几乎所有的 蛆 蚁 所走 过 的 食 物 到自 己巢穴 的 路 线 都 近 似于一条直 线，而 不是什么曲线 等 其他形状 的 线 或 者 图形。蛆 蚁 这 种 群 体虽 然个小，但是不仅能 完成比较 复杂的 工作，而 且还 能 很 快的 适 应环 境的 变化，比如突 然出现 在蚂 蚁 去向的 路 径上的 障 碍 物，一开始各只 蛆 蚁 行 走 的 分布是均匀的，不管 是路 线 的 长 与
7、短，蛆 蚁 总是会按照同等 概率 选 择 各自 要 走 的 路 径，在蛆 蚁 行 走 进 程 中，凡是蛆 蚁 所经 过 的 地方都 会留 下一种 物 质，并且能 感知 这 种 信息素 的 存在以及它的 强度，并通 过 此信息素 来指导自 己行 走 的 方向，它们会朝着 信息素 浓度较 高 的 方向移 动。在同等 时间 内，较 短 路 径上的 信 息素 的 量 遗 留 得越 多，则会选 择行 走 较 短 路 径蛆 蚁 的 数量 也就会越 大。显而 易见，由 于大多数蛆 蚁 的 集 体活动表 现 出一种 信息的 正反馈 现 象，就是某一路 径上行 走 过 的 蛆 蚁 数越 多，则后来的 蛆 蚁 选
8、 择信息素 浓度大的 路 径的 概率 就越 大，蚁 群 通 过 这 种 信息素 进 行 信息交流，并凭借此来寻找食 物，所走 的 路 段总是最短 的 路 段。1989年著 名的“双桥”实验，就表 明了：从蛆 蚁 的 蚁 巢到食 物 目 的 地的 最短 的 路 线 总谁 是蛆 蚁 种 群 的 最终 选 择。意大利学家根据蛆 蚁 的“寻找食 物”的 这 一群 体活动的 现 象，在1999年，在人工生 命会议 上提出了有关蚁 群 算 法的 基本模型；第 二年，蚁 群 算 法的 主要 核心思想，又被 意大利学家进 一步的 阐 明了。蚁 群 算 法 源于蛆 蚁 寻找食 物 的 活动而 被 提出的。在蚁
9、群 算 法中，该 算 法的 最基本单元就是 蛆 蚁 个体本身。蛆 蚁 所拥有的 知 识 来源于其他蛆 蚁 信息以及对周边 的 认 识，因此，知 识 的 积 累 是蛆 蚁 个体的 一个动态进 程。蛆 蚁 个体通 过 随 机决策 和相 互协调 自 适 应的 做出并完成自 身 的 评 价，蚁 群 算 法所研 究 的 焦点就是这 种 蛆 蚁 个体之间 的 分 布性和协作性。很强的 自 学习本领 是蚁 群 算 法所具有的，它可根据情况的 改变和 已产生 的 活动对自 身 的 知 识 库或组 织 布局进 行 再组 织，进 而 达 到算 法求解 能 力的 加强，恰是算 法自 身 学习本领 与情况变化的 相
10、互作用 孕育 了这 类 进 化，同时该 算 法的 不可预 测性也由 环 境变化的 不确 定性与算 法机理 的 复杂性的 影响而 加强了。自1991年来，Dorigo M等 学家提出蚁 群 算 法后的 近5年内，该 算 法在国际 学术界 并没有引起 广泛关注，也没有取得任何突 破 的 进 展。直 到了 1996年,Dorigo 5M 等 本身 在IEEE Transactions on Systems,Man,and Cybennetics-Patr B上发 表 了Ant systems：optimization by a colony of cooperation agents”一文，在文中，
11、Dorigo M等 学家不仅更加详 细 的 说 明了蚁 群 算 法的 基本原理 和数学模型，还 将 蚁 群 算 法与多种 算 法进 行 仿真 实验 并进 行 系 统 详 细 的 比较，且对蚁 群 算 法中的 初 始化参数对其机能 评 估的 影响做了初步探究，这 是蚁 群 算 法发展历史上的 又一篇 奠基性作品。从已经 公开发表 的 有关蚁 群 算 法的 文章 来说，其中大部 分的 论 文都 将这 篇 章 或者 Dorigo M 在 1991 年发表 的distributed optimization by ant colonies,一文用 来当作参考 的 文献。然而 持续 高 涨的 对蚁 群
12、算 法的 研 究 热情，直 接导致 了 在国际 上，首 届蚁 群 算 法探讨 会的 召开，地点就在当时的 比利时布鲁 塞尔，这 场 会议 组 织 负 责 人就是蚁 群 算 法的 创始人Dorigo Mo第 一届探讨 会就吸引了 50多 位研 究 者，他们都 是来自 五湖四海的 研 究 蚁 群 算 法的 爱 好者，随 后每三年，蚁 群 算 法探讨 会都 会在在布鲁 塞尔被 召开一次，历届的 论 文集 都 是由 著 名的 Lecture Notes in computer science 收集 再出版。2000 年，在nature上出现 了一篇 关于蚁 群 算 法的 综 述，该 篇 文章 就是由d
13、origo m和bonabeau E等 学家所 发表 的。经 过 此次文章 发表 之后，对蚁 群 算 法的 这 一领 域的 研 究，成为了国际 学 术界 的 前沿课 题。21世纪 后的 几年里，蚁 群 算 法不断的 出现 颇 硕 的 研 究 成果，顶 级 学术刊物nature又多次对这 些研 究 成果进 行 了特 别的 报道，Future generationcomputer systems禾 口IEEE transactions on evolutionary computation 也相 继 的 出版 了有关该 算 法的 特 别刊登。现 在，在许 多学术期刊和会议 上包括国 内以及国外的，
14、蚁 群 算 法已经 成为了研 究 热点，深受广大研 究 者 的 关注。对于 收敛性的 证 明，是由Gutiah rwj证 明的，他所发表 的 两篇 学术论 文同样对算 法发 展的 历史上有着 独 特 的 作用。Gutjah rwj用 有向图的 行 走 来比作蚁 群 的 这 一活动,并从有向图的 角 度分析，对于一种 能 改进 收敛性展开了详 细 的 理 论 分析证 明 了在合理 充分的 假设 理 想条件下，所要 求问 题 的 最优解 答 能 被GBAS能 以一定 的 概率 收敛而 得到。对蚁 群 算 法的 钻 研，我国算 是起 步较 晚，从曾经 公开公布的 文章 的 时间 来看,在国内，东北大
15、学的 张纪 会与徐心和是研 究 蚁 群 算 法的 先驱 研 究 者。在国内众多 研 究 蚁 群 算 法的 研 究 者 中，最令人惊讶 的 是年仅17岁的 高 二学生 陈 桦在2001 年在计 算 机工程这 书上发表 了“带杂交算 子的 蚁 群 算 法”一文，并通 过Visual Basic开发了一个功能 全、界 面 好的“蚁 群 算 法实验 室”，受到了业界 广大蚁 群 算 法爱 好者 以及研 究 者 的 热烈关注，就像计 算 机工程“编 者 按”所说 那 样：“一 个高 中生 能 写出这 样的 论 文实属不易”。回首 蚁 群 算 法从创立 到现 在的 发展历史，研 究 者 对蚁 群 算 法这
16、 一算 法的 研 究 已由 单一的TSP领 域拓展到多个领 域。由 一维 静 态优化转 变到多维 动态组 合优 6化，由 离 散域范 围到连 续 域范 围，以及基于蚁 群 算 法的 硬 件，在实现 上也取得了 突 破 性的 进 展，同时对蚁 群 算 法的 模型的 改进 及与其他仿生 优化算 法的 相 应融 合 也取得了颇 富的 研 究 成果，使的 这 种 仿生 算 法展现 出未曾有过 的 生 机，并已经 成 为一种 完全可媲美 遗 传算 法的 仿生 算 法。72蚁群算法2.1基本蚁群算法的原理人们根据大自 然的 蛆 蚁 觅 食 这 一行 为，模拟出了蚁 群 算 法，该 算 法具有正反 馈、并行
17、 性、适 应环 境的 特 点。仿生 学家从长 期的 研 究 中发现：蛆 蚁 虽 然没有视 觉，但是它们在移 动过 程 中，会在路 上释 放一种 特 别的 分泌物（信息素），并依 据该 种 信息素 来辨 别所要 行 走 的 方向。当它们来到一个未曾走 的 路 口时，他们会 随 机的 选 择一条路 前进，并在所走 的 路 上释 放信息素，该 信息时与所走 的 路 段的 长 短 有关，路 段越 长，信息素 的 释 放量 就会越 小。当后来的 蛆 蚁 走 到这 个交叉路 口时,信息素 浓度较 高 的 路 被 选 择的 可能 性较 高，正反馈 就在这 是形成了。此后，最有路 段上的 信息素 就会越 来越
18、 大，而 其他路 段上的 信息素 则会慢慢减小，这 样,最优路 段就会被 整个蚁 群 发现。由 此可见，在寻找路 径的 整个进 程，虽 然单个蛆 蚁 本身 选 择路 径的 能 力有限 的，但是通 过 所释 放的 信息素 的 反馈 作用，使得蚁 群 的 群 体活动具有很高 的 自 组 织 性，蛆 蚁 间 通 过 交换各自 路 径信息，蚁 群 最终 通 过 群 体的 自 催化活动找到了最优的 路 径。通 过 模拟蛆 蚁 的 活动而 得到的 蚁 群 算 法，是以新的 计 算 机模式来引入的，基 于以下假设：蛆 蚁 们凭借一种 分泌物（信息素）来达 到与环 境进 行 交流的 目 的，每只蛆 蚁 根据自
19、 身 周边 环 境作出反应，也只能 对其本身 周围的 环 境有所作用。蛆 蚁 自 身 内部 决定了蛆 蚁 对环 境的 而 做出回应。它是基因生 物 体，蛆 蚁 自 身 的 行 为 实际 上就是基因对环 境适 应性的 表 现，是一种 反应适 应性的 生 物 主体。就个体而 言，蛆 蚁 仅根据自 身 周边 环 境做出选 择；而 对群 体而 言，单只蛆 蚁 的 行 为是随 机 的，但是群 体的 行 为可凭借系 统 的 自 组 织 性来形成高 度有序的 集 体行 为。由 上可见，蚁 群 算 法的 寻求最优解 机制包含两阶 段：适 应阶 段、协作阶 段。适 应阶 段,各种 解 依据堆积 的 信息来调 整
20、自 身 的 结 构，在路 线 上，走 的 蛆 蚁 越 多，信息量 越 大，被 选 择的 可能 性就越 大，时间 长 了，信息量 就减小；合作阶 段，各 种 解 通 过 信息交流，然后产生 更好的 解。蚁 群 算 法属于智能 的、多主体的 系 统，自 组 织 使得蚁 群 算 法简 便易用，不需 要 对所要 求的 解 的 各个方面 都 有所了解。自 组 织 属于动态型，在没有外界 的 干扰 作用 下，可使得系 统 嫡增加，表 现 出由 无序到有序的 变化过 程。用 规 范 的 格式来 使组 合优化问 题 规 范 化，运 用 蚁 群 算 法的“探索”和“利用”，依据信息素 这 载 体决 定决策 点，
21、与此同时按照信息是更新规 则对每只蛆 蚁 的 信息素 进 行 增量 构建，从 整体的 角 度规 划出整个蚁 群 的 动向，反复进 行，就可以求的 最优解。82.2蚁群算法的系统学特征系 统 学是门 比较 新的 学科，其特 点是强调 整体性。不同的 学科 的 研 究 重 点和 范 围有区别，所以对系 统 的 也是因此而 异。在基础 层次，创始人给 定的 定义是：“系 统 为处于一定关系 中并和环 境的 各组 成部 分的 综 合体”。该 定义更精 确 的 表 述 是：如果对象S满足 下面 条件：S中至 少包含两个有区别的 对象，S中的 对象 按 照一定的 方式关系 到在一起，则可以称S为一个系 统
22、,S中的 个体为系 统 的 元素。自 然界 的 蚁 群 恰好具备了系 统 的 三个特 征，相 关性、多元性和整体性，就是 一个完整的 系 统。在这 个系 统 中，各个蛆 蚁 本身 的 各自 活动就是系 统 的 组 成元素,系 统 的 相 关性则体现 在蛆 蚁 个体之间 的 相 互影响关系，而 系 统 的 完整性则由 蚁 群 可完成蛆 蚁 个体间 完成不了的 工作的 这 样现 象 体现 出来，从而 显现 出系 统 整体大 于部 分之和的 特 性原理。蚁 群 算 法作为蛆 蚁 群 体寻找食 物 这 一活动的 抽象 算 法，如果视 蚁 群 算 法本身 为一个系 统、一个整体，那 么就会发现 该 算
23、法就符 合了系 统 的 三个基本特 征，这 是仿生 优化选 法重 要 特 征之一。对传统 算 法而 言，比如求无约 束的 解 析法，由 于 算 法各部 分之和等 于最终 和，因此不能 看 作一个系 统。而 蚁 群 算 法，整体远 好于 个体之和，无加和性，因此蚁 群 算 法是一个系 统。作为系 统，它还 具备了一些更 为重 要 的 特 征，使得它具有了更加深刻的 研 究 意义。自 然界 的 蚁 群 活动具备了分布式。如果蚁 群 要 完成某项 工作时，大部 分蛆 蚁 凭借共同目 的 来完成工作，不会因为某个蛆 蚁 的 缺 失而 使得整个工作终 止。作为 蛆 蚁 觅 食 行 为的 抽象 算 法，蚁
24、 群 算 法也表 现 出分布式特 征。每只人工蛆 蚁 在空 间 问 题 的 多个点上，一同开始构造 问 题 解，而 求解 过 程 是不会因为某只人工蛆 蚁 无 法获 得解 而 受到影响。自 组 织 也是蚁 群 算 法的 重 要 特 征。自 组 织 是随 着 系 统 学的 发展而 建立 的。通 常分为自 组 织、他组 织。其区别是在于组 织 力或组 织 指令是源于内部 还 是外部，源于内部 称 为自 组 织，源于外部 则为他组 织。自 组 织 是系 统 在获 得时间 上的、空 间 上的 或者 功能 上的 结 构进 程 中，不受到外界 的 特 定干预 的。生 物 体就是典型的 自 组 织 系 统，
25、类 似蛆 蚁、蜜 蜂 这 类 昆虫，个体本身 作用 简 单，但是个体之间 的 协作的 作用 尤其明显，因而 就把它们视 为一个整体来探究,甚 至 是独 立 完整的 生 物 体。在这 类 群 落 中，个体相 互作用，共同完成某项 指标的 工作，自 然就体现 出较 强的 自 组 织 的 特 殊性质。而 从抽象 意义上来说，如果没有 外界 的 作用 影响，系 统 嫡有所增长 的 进 程 就是所谓 的 自 组 织。基本的 蚁 群 算 法就 正好体现 了这 一进 程。自 组 织 使得算 法的 鲁 棒性得到了增强，传统 算 法是针 对某一问 题 设 的，这 是 建立 在对该 问 题 有了全面 认 识 的
26、基础 上，所以很难 适 应其他类 型的 问 题，而 相 对 9自 组 织 的 蚁 群 算 法来说，就不需 要 对所要 求的 问 题 的 各个方面 都 要 有所认 识 了解,比较 容易使用 到这 一类 问 题 之中。控制理 论 中的 另一个的 重 要 概念就是反馈，它代表 着 信息输 出受到着 信息输 入的 影响。在系 统 学上认 为，反馈 就是现 在的 作为对未来的 活动的 起 到影响的 原 因。有正反馈、负 反馈 之分，前者 是通 过 现 在活动来加强未来活动，而 后者 则是 通 过 以现 在活动去消弱未来活动。由 真 实的 自 然界 的 蛆 蚁 寻找食 物 活动可见，蛆 蚁 最终 能 找到
27、最短 路 径，是因 为在最短 路 径上的 信息素 的 积 累，而 这 是个正反馈 进 程。对蚁 群 算 法而 言，起 初 蛆 蚁 在环 境中信息素 的 释 放量 是相 同的，产生 了微小扰动，使得各边 的 信息量 不 同，构造 的 解 就存在了好坏之分。算 法采 用 的 反馈 方式，是在较 优解 的 路 段留 下 更多信息素，这 样又吸引更多的 蛆 蚁，这 进 程 正是正反馈 进 程，使得初始值不断 扩大，同时促使系 统 向最优解 的 方向进 行。系 统 的 自 组 织 是无法靠 单一的 正反馈 或者 负 反馈 来实现 的。利用 正、负 两种 反馈 的 结 合，以达 到系 统 的 自 我创造
28、和自 我更新的 目 的。负 反馈 机制同样存在蚁 群 算 法中，它主要 体现 在概率 搜索 技术，蚁 群 算 法在寻求解 的 进 程 中会使用 到概 率 搜索 技术，通 过 该 技术而 生 成解 的 随 机性大大增长。随 机性的 影响在于接受一 定程 度上的 退 化，使得在一段时间 内，搜索 范 围保持足 够大。这 样就使得正反馈 的 搜索 范 围减小，从而 保证 了算 法是朝着 最优解 答 的 方向前进，而 负 反馈 则使得 搜索 范 围保持不变，从而 避 免了算 法的 过 早收敛于不佳的 结 果。正是由 于正负 反 馈 的 共同影响下，使得蚁 群 算 法可以以自 组 织 形式进 化，从而
29、寻得问 题 在一定方 向上的 最优解 答。以上是从系 统 科 学的 观 点出发，分析了蚁 群 算 法的 基本原理，由 此可见，蚁 群 算 法这 类 仿生 算 法体现 出许 多异于其他的 常规 算 法的 新思路，当然，基本蚁 群 算 法的 研 究 意义所在之处就是此点。2.3蚁群算法的优点研 究 表 明，蚁 群 算 法具有较 强的 能 找到更优解 的 能 力，这 不仅是因为该 算 法 具有正反馈 原理，一定程 度上，可加速 进 化进 程，而 且是个大生 的 并行 算 法，具 有以下优点：（1）通 用 性。它可用 于解 同类 型的 优化问 题，从TSP问 题 到ATSP只需 作直 接（2）扩展即可
30、实现。（3）鲁 棒性。很小的 改动，就可用 于解 其他组 合优化问 题。（4）群 体性。这 是一种 基于群 体的 方法很有趣，因为它允许 采 用 正反馈 作为搜 索 机制。10（5）并行 性。适 用 于并行 操作，在求解 大规 模优化问 题 时，可从算 法本身 的 优 化出发来提高 求解 效率，也可从算 法的 执行 模式出发来进 行 研 究。113机器人路径规划的蚁群算法设计3.1机器人路径规划问题机器人是一种 具有高 度灵活性的 自 动化的 机器，与其他不同的 是这 种 机器具 备人或者 生 物 相 类 似的 智能 能 力，如感知 能 力、规 划能 力、动作能 力、和协同能 力等 等。机器人
31、技术是20世纪 人类 最伟大的 发明之一，到现 在经 历了 40余年的 发展历史。机器人路 径规 划是指机器人按照某一性能 指标或者 某一要 求，寻找到一条从 初状 态到末状 态的 最优或者 近 似于最优的 无碰 撞进 程 的 路 径，这 也是达 成机器人 控制以及导航 的 基础。机器人的 路 径规 划，一般 可分为局部 规 划以及全局规 划这 两类。多个机器人系 统 是一个分布式的 系 统，该 系 统 结 构松散，但是其优点在于 既可独 立 工作，又可以根据需 要 进 行 协作工作。在未知 的 任务、未知 的 环 境下，确 定哪些任务需 要 多个机器人协作完成，是一个重 要 而 艰 巨的 问
32、 题。3.2蚁群算法的流程设计如果把森林中的 入口、出口用 来表 示 出发点、目 的 地，把机器人所经 过 的 路 线 表 示 为弧，把森林中的 湖、山峰等 属性表 示 为障 碍 物，就可以被 抽象 成为一个 带权的 有向图。给 定一个带权的 有向图G=(U,E),其中V是包含n个节 点的 节 点集，E是包含h条弧的 弧集，i,J是E中从节 点i至J的 弧，是弧i,J 的 非 负 权值。设s,t分别为U中的 出发点和目 的 地，则所谓 的 路 径规 划问 题 其 实就是指在带有权的 有向图G中，寻找从所指定的 出发点s到目 的 地t的 一条具 有最小权值的 总和的 路 径。给 定个有n个节 点
33、的 森林的 路 径规 划问 题，把指定的 出发点s进 行 假设 为人工蚁 群(下面 统 称 为蚁 群)的 巢穴，把目 的 地t假设 为要 寻找的 食 物 源，那 么这 个路 径 规 划问 题 随 即就可以转 化为简 单的 蚁 群 寻找食 物 的 寻优路 径问 题 了。假设 给 定的 人工蛆 蚁(下面 统 称 为蛆 蚁)的 数量 为m只，那 么每只蛆 蚁 个体的 活动就需 要 适 合以下的 规 则：(1)蛆 蚁 能 够释 放两类 信息素，即“食 物”类 信息素 与“巢穴”类 信息素；(2)据当前节 点信息素 的 浓度以及路 径长 度，然后随 机性的 选 取下一节 点；(3)蛆 蚁 所走 过 的
34、不再选 择，不会做为下一节 点，这 个可以通 过 结 构数组 功 能 来实现；(4)蛆 蚁 在觅 食 时，通 过 先前所释 放的“食 物”类 信息来找下一节 点，并且同时 释 放“巢穴”类 信息素，(5)在找巢穴 时，通 过 先前所释 放的“巢穴”类 信息素 来寻找下一节 点，与此同 12时就要 释 放“食 物”类 相 应信息素；(6)根据所走 路 径的 长 度释 放来所对应的 信息素 的 浓度，信息素 的 释 放会随 时间 而 逐 渐减少，用 弓*)来表 示t时刻，此时路 径(i,j)上的 所积 累 的 信息素 的 浓 度，则f+1时刻所积 累 的 信息素 的 浓度为：%。+1)=(1-),
35、。)+星(9(式 1)m(式 2)k=iP：信息素 的 挥发系 数，1一夕：信息素 的 残留 因子，Q值越 大则表 示 信息素 挥发的 比较 慢，反之就会越 快。Q值越 大则表 示 示 信息素 挥发的 就越 慢，反之就会越 快。为了防 止无限 积 累，Q的 范 围为：QUO,1)Mj(t)表 示 信息素 在此次循环 中的 路 径(i,j)上的 增量，初始时刻小功(0)二0，表 示 第k只蛆 蚁 此次在路 径(i,j)上循环 中释 放出的 信息量。这 里 采 用ant-quantity来实现 苛 的 算 法，2仰=*，若 在t和+1之间，第k只蛆 蚁 经 过(i,j)(式3)其中，Q为常量，表
36、示 每只蛆 蚁 所释 放出的 信息素 总量，4表 示 从节 点i到节 点 J这 两点之间 的 路 线 长 度。定义：在t时刻，位于节 点i上的，第j只蛆 蚁 选 取节 点J为下一个目 标节 点的 转 移 概率为与。（0 血（，）若.r,/、E 命，右7 e allowed,0,否则（式4）suallowedka I I okvCd-t a 0表 示 蚂 蚁k下一步准许 选 取的 城市；a为信息启发式 的 因子，所表 示 的 是轨 迹 的 重 要 性；为期望启发式的 因子，所表 示 的 是能 见 度 的 重 要 性;为.为启发函数，表 达 式如下：13/、1 为。)=厂%.表 示 相 邻 两个点
37、之间 的 距 离。对蚂 蚁k而 言，.越 小，则为.越 大，也 就P%)越 大。参数的 最佳数值由 实验 来决定。求解 步骤：(1)在初始时刻，蛆 蚁 种 群 产生 移 动路 径。(2)调 整信息素：对所产生 的 可移 动路 径，计 算 路 径长 度，计 算 所对应信 息素 的 变量，利用 信息素 更新公式，对路 线 上的 各个点所相 对应的 信息素 进 行 更 新。(3)对产生 的 可行 的 路 径进 行 修正处理：将蛆 蚁 所经 过 的 弯曲的、不规 则 的 路 径变换拉直 为一条有直 线 段相 连 接的 可行 的 路 径，将可行 路 径和目 前已经 记 录的 最短 的 路 径进 行 比较
38、 分析，如果该 路 径的 长 度相 对更短，那 么就将该 路 径作 为最短 路 径，然后对所有路 径上的 所有的 节 点的 信息素 进 行 跟 新，按照第(2)步的 方法进 行 更新。如果当前就已经 达 到了预 先已经 设 定的 终 止时刻，那 么则跳 转 到第(5)步。(4)下一时间 路 径的 生 成：在信息和基于过 渡态的 概率 的 概率 使用 当前的 距 离 启发式信息，产生 从初始状 态到一个可行 的 路 径树的 状 态，然后就跳 转 到第(2)步。(5)算 法结 束：将当前的 最优路 径作为输 出。3.3蚁群算法实现3.3.1主程 序模块clearload datalROUTES,P
39、L,Tau=ACASP(G,ones(400,400),50,30,1,400,1,15,0.95,1)%data1%load data2%ROUTES,PL,Tau=ACASP(G,ones(1024,1024),50,30,65,1019,1,15,0.95,1)%data214%load data2%ROUTES,PL,Tau=ACASP(G,ones(1024,1024),50,30,65,1019,1,15,0.95,1)%data33.3.2初始化模块function ROUTES,PL,Tau=ACASP(G,Tau,K,M,S,E,Alph a,Beta,Rh o,Q)%-%A
40、CASP.m%ACS for Path Planning%-%input parameters%Ggragh,wh ich is 01 matrix,1 represents obstcles%Tauinitial ph eromone matrix 初始信息素 矩 阵%Kiterative times迭 代次数（指蚂 蚁 出动多少波）%Mant number for once iteration蛆 蚁 个数（每一波蛆 蚁 有多少个）%SStart Point%EGoal point%Alph aparameter indicates th e importance of ph eromone
41、 表 征信息素 重要 程 度的 参数%Betaparameter indicates th e importance of visibility 表 征启发式因子重 要 程 度的 参数%Rh oph eromone evaporation rate 信 息素 蒸 发系 数%Qph eromone accumulation parameter 信息素 增长 强度系 数%output parameters%ROUTES th e route th at every ant in every iteration%passes%PL th e length th at every ant in eve
42、ry iteration%passes%Tau output叩dated ph eromone输 出动态修正过 的 信息素15%-variableinitialization-D=G2D(G);N=size(D,l);%N is th e peoblem scale(pixel number)MM=size(G,l);a=l;%edge length of pixelEx=a*(mod(E,MM)-0.5);%goal point coordinateif Ex=-0.5Ex=MM-0.5;endEy=a*(MM+0.5-ceil(E/MM);%Y coordinate of goal poi
43、ntEta=zeros(l,N);%construct th e initialization matrixfor i=l:Nix=a*(mod(i,MM)-0.5);ifix=-0.5ix=MM-0.5;endiy=a*(MM+0.5-ceil(i/MM);ifi 二EEta(1,i)=1/(ix-Ex)A2+(iy-Ey)A2)A0.5;elseEta(l,i)=100;endendROUTES=cell(K,M);%use cell construct to load th e passing route of every ant for every iterationPL=zeros(
44、K,M);%use matrix to load th e passing length of every ant for every iteration3.3.3解 搜索 模块ROUTESk,m=Path;if Path(end)=EPL(k,m)=PLkm;else16PL(k,m)=inf;end3.3.4保优与信息素 更新模块Delta_Tau=zeros(N,N);%更新量 初始化for m=l:MifPL(k,m)=l&yl=l j=(xl-l)*N+yl;D(i,j)=1.414*a;D(j,i)=1.414*a;end x2=x-l;y2=y;if x2=lj=(x2-l)*N
45、+y2;D(i,j)=a;D(j,i)=a;end x3=x-l;y3=y+l;if x3=l&x3=lj=(x4-l)*N+y4;31D(i,j)=a;D(j,i)=a;endx5=x;y5=y+l;ify5=Nj=(x5-l)*N+y5;D(i,j)=a;D(j,i)=a;endx6=x+l;y6=y-l;if x6=1j=(x6-l)*N+y6;D(i,j)=1.414*a;D(j,i)=1.414*a;endx7=x+l;y7=y;ifx7=Nj=(x7-l)*N+y7;D(i,j)=a;D(j,i)=a;endx8=x+l;y8=y+l;if x8=N&y8 100;endendRO
46、UTES=cell(K,M);PL=zeros(K,M);for k=l:Kdisp(k);for m=l:MW=S;Path=S;PLkm=0;34TABUkm=ones(1,N);TABUkm(S)=O;DD=D;DW=DD(W,:);DWl=find(DWinf);forj=l:length(DWl)if TABUkm(DWl(j)=ODW(j)=inf;endendLJD=find(DW=lPP=zeros(,Len_LJD);for i=l:Len_LJDPP=(Tau(W,LJD(i)AAlph a)*(Eta(LJD(i)ABeta);endPP=PP/(sum(PP);Pcum
47、=cumsum(PP);Select=find(Pcum=rand);to_visit=LJD(Select(l);Path=Path,to_visit;PLkm=PLkm+DD(W,to_visit);W=to_visit;for kk=l:NifTABUkm(kk)=ODD(W,kk)=inf;DD(kk,W)=inf;endendTABUkm(W)=0;DW=DD(W,:);DWl=find(DWinf);forj=l:length(DWl)35if TABUkm(DW 1)=0DW(j)=inf;endendLJD=find(DWinf);Len_LJD=length(LJD);end
48、ROUTES k,m=Path;if Path(end)=EPL(k,m)=PLkm;elsePL(k,m)=inf;endendDelta_Tau=zeros(N,N);for m=l:MifPL(k,m)infROUT=ROUTESk,m;TS=length(ROUT)-l;PL_km=PL(k,m);for s=l:TSx=ROUT(s);y=ROUT(s+l);Delta_Tau(x,y)=Delta_Tau(x,y)+Q/PL_km;Delta_Tau(y,x)=Delta_Tau(y,x)+Q/PL_km;endendendTau=(l-Rh o).*Tau+Delta_Tau;e
49、ndplotif=l;if plotif=lmeanPL=zeros(1,K);minPL=zeros(1,K);36for i=l:KPLK=PL(i,:);Nonzero=find(PLKinf);PLKPLK=PLK(Nonzero);meanPL(i)=mean(PLKPLK);minPL(i)=min(PLKPLK);endfigure(l)plot(minPL);h old onplot(meanPL);grid ontitle(收敛曲线(平均路 径长 度和最小路 径长 度),)；xlabelC迭 代次数)；ylabel(路 径长 度);%Plot Passing Graphfig
50、ure(2)axis(0,MM,0,MM)for i=l:MMforj=l:MMif G(i,j)=lxl=j-l;yl=MM-i;x2=j;y2=MM-i;x3=j；y3=MM-i+l;x4=j-1;y4=MM-i+l;fill(xl,x2,x3,x4,yl,y2,y3,y4,0.2,0.2,0.2)；h old onelsexl=j-l;yl=MM-i;x2=j;y2=MM-i;x3=j;y3=MM-i+l;x4=j-1;y4=MM-i+l;fill(x 1,x2,x3,x4,y 1,y 2,y 3,y4,1,1,1);h old on37endendendh old onROUT=ROU