蚂蚁算法在组合优化问题中的应用研究

摘要

组合优化问题是优化领域中的重要分支.组合优化问题有很强的工程背景,例如任务分配问题和Job-Shop问题.虽然求解组合优化问题的方法层出不穷,但这些方法都有各自的缺点和局限性,目前还不能满足实际应用的需要.蚂蚁算法作为一种新近出现的启发式算法,它具有正反馈、分布式计算和具有贪婪的启发式等特点.蚂蚁算法已经成功地应用于求解货郎担问题TSP(traveling salesman problem),引起了广泛的关注.但是由于蚂蚁算法出现的时间很短,它的应用研究还处于初步阶段,在许多组合优化问题上蚂蚁算法的研究还处于空白,例如任务分配问题和Job-Shop问题.该文将蚂蚁算法应用于求解任务分配问题和Job-Shop问题,并且针对求解过程中出现的问题,提出了改进的蚂蚁算法,并且通过大量的仿真试验加以验证,取得了很好的结果.在第一章中,主要介绍了最优化技术的基本理论和发展历史、启发式算法的定义和设计方法以及该文的创新点.在该文的第二章中,主要介绍了组合优化的概述和常用的求解方法.在第三章中,主要介绍了蚂蚁算法,包括:蚂蚁算法的仿生原型、蚂蚁系统、改进的蚂蚁算法以及目前国内外的研究现状.在第四章中,将蚂蚁算法应用于求解任务分配问题.针对蚂蚁算法使用了局部搜索法,易于陷入局部极小陷阱,因此作者对蚂蚁算法作了改进,在选择概率中加入混沌函数扰动,使算法在一定程度上接受恶化解,以跳出局部极小的陷阱,并通过仿真试验加以验证.在第五章中,作者将蚂蚁算法应用于求解Job-Shop问题.针对采用传统信息造成机床加工时间的大量浪费,作者提出了一种新的启发信息:最早允许开始时间(EAPT),可以使未加工的工序填入到机床上的空闲时间段内加工,缩短了总的加工时间,同时在算法中加入了适量的随机信息,扩大了算法的解空间,避免了陷入局部极小的陷阱,通过大量的仿真试验验证了新算法的有效性.在该文的最后,作者还对算法的两个主要参数与仿真结果的关系作了研究.论文的第六章总结了全文的工作,并对未来的研究工作提出了展望.

目录

文摘

英文文摘

独创性声明及学位论文版权使用授权书

第一章绪论

1.1选题背景与研究意义

1.2启发式算法概述

1.3本文主要研究内容

第二章组合优化问题的概述和常用解决方法

2.1引言

2.2组合优化问题的基本理论

2.2.1最优化理论

2.2.2组合优化问题

2.2.3优化算法及其分类

2.3 P类问题，NP类问题和NP-complete类问题

2.4常用的传统方法

2.5启发式算法

2.5.1模拟退火算法

2.5.2遗传算法

2.5.3禁忌搜索

2.5.4人工神经网络

2.5.5其他启发式算法

2.6仿生算法

2.7本章小结

第三章蚂蚁算法概述

3.1引言

3.2仿生原型

3.3蚂蚁系统

3.4蚂蚁算法

3.5蚂蚁算法的发展

3.6蚂蚁算法的应用

3.7本章小结

第四章改进后的蚂蚁算法求解任务分配问题

4.1引言

4.2任务分配问题的数学模型

4.3用蚂蚁算法求解任务分配问题

4.4蚂蚁算法的改进

4.5仿真试验

4.6研究存在的不足之处和算法的特点

4.7本章小结

第五章蚂蚁算法在Job-Shop问题中应用与研究

5.1引言

5.2排序问题

5.3 Job-Shop问题的数学描述

5.4用蚂蚁算法求解Job-Shop问题

5.4.1基本算法的设计

5.4.2标志量的设计

5.4.3本章算法的特点

5.4.4算法的具体设计

5.5仿真试验

5.6对算法主要参数的研究

5.7本章小结

第六章总结与展望

参考文献

发表论文和科研情况说明

致谢