基于工作流技术的蚁群算法性能研究

论文摘要

工作流技术是实现企业业务过程建模、仿真分析、管理与集成,从而实现业务过程的自动化的核心技术。工作流技术的实施是企业完善经营过程、提高自身竞争力的一种重要手段。目前,工作流技术已成为计算机应用研究领域一个重要的分支,本文通过对比工作流和算法之间的相似关系,把工作流技术引入到蚁群算法当中,对蚁群算法的性能进行研究,进一步提高算法的优化效率,提供了一种新的有效途径。本文首先介绍了基本蚁群算法蚂蚁系统（Ant System,简称AS）,及最优保留蚂蚁系统（Ant System with Elitist,简称ASelite）、蚁群系统（Ant Colony System,简称ACS）、最大-最小蚂蚁系统（MAX-MIN Ant System,简称MMAS）和基于排序的蚂蚁系统（Rank-based Version of Ant System,简称ASrank）等改进的蚁群算法,分析和比较了各个算法的特点,并对算法进行了算子设计。其次,对蚁群算法的性能研究不同于传统的针对具体优化对象讨论算法的性能特征,而是针对算法模型的本身,讨论蚁群算法在解决组合优化问题时的优化效率,重点分析算法的优化特性和计算流程。通过熟悉工作流技术的基本概念和理论,从元素映射和流程映射两方面,把蚁群算法映射到工作流中。进程代数和Petri网作为研究离散、并发系统的有利工具,是最主要的两种工作流建模和分析方法。通过分析和比较两种方法的优缺点,本文采用进程代数对算法进行建模,建立了蚁群算法的工作流模型。同时,为了结合进程代数强大的建模能力和Petri网有效的分析能力,给出了蚁群算法的进程代数模型到Petri网模型的转化方法。最后,基于Petri网对蚁群算法模型进行性能分析,实验取得了良好的效果。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• §1-1 本文研究的目的和意义
• §1-2 国内外研究状况和进展
• 1-2-1 旅行商问题描述
• 1-2-2 蚁群算法
• 1-2-3 工作流技术
• §1-3 本文的研究内容及成果
• 第二章 蚁群算法的理论研究
• §2-1 基本的蚁群算法
• 2-1-1 蚂蚁系统
• 2-1-2 蚂蚁系统的流程
• 2-1-3 蚂蚁系统的优点和缺点
• §2-2 改进的蚁群算法
• 2-2-1 最优解保留策略蚂蚁系统
• 2-2-2 蚁群系统
• 2-2-3 最大-最小蚂蚁系统
• 2-2-4 基于排序的蚂蚁系统
• §2-3 蚁群算法的特点
• §2-4 蚁群算法算子设计
• 2-4-1 蚂蚁系统算子设计
• 2-4-2 蚁群系统算子设计
• §2-5 本章小结
• 第三章 基于工作流技术的蚁群算法模型
• §3-1 基本概念和理论
• 3-1-1 工作流
• 3-1-2 进程代数
• 3-1-3 Petri网
• §3-2 蚁群算法到工作流的映射
• 3-2-1 元素映射
• 3-2-2 流程映射
• §3-3 基于进程代数的蚁群算法建模
• 3-3-1 蚂蚁系统的进程代数模型
• 3-3-2 蚁群系统的进程代数模型
• §3-4 蚁群算法的进程代数模型到Petri网模型的转化
• 3-4-1 转化规则
• 3-4-2 蚁群算法的Petri网模型
• §3-5 本章小结
• 第四章 蚁群算法模型的性能分析
• §4-1 算法模型证实
• §4-2 算法模型验证
• §4-3 基于随机Petri网的性能分析
• 4-3-1 随机Petri网
• 4-3-2 性能指标
• §4-4 试验结果
• 4-4-1 计算性能
• 4-4-2 运行性能
• §4-5 本章小结
• 第五章 主要结论和进一步工作
• §5-1 主要结论
• §5-2 进一步工作
• 参考文献
• 致谢
• 攻读学位期间所取得的相关科研成果