禁忌搜索及其并行化研究

论文摘要

禁忌搜索(Tabu Search或Taboo Search，TS)是一种新的智能优化算法，由美国科罗拉多大学系统科学家Glover教授于1986年正式提出。TS与模拟退火(SA)、进化计算(EC)、蚁群算法(ACS)、粒子群优化(PSO)、人工免疫系统(AIS)等一样，都属于自然计算(Natural Computation，NC)的研究范畴。TS以其灵活的存储结构和相应的禁忌准则来避免迂回搜索，在智能优化算法中独树一帜，受到了自然计算领域学者的广泛关注，在组合优化及函数优化领域中得到了广泛的应用。 本文在前人成果及前期工作的基础上，重点研究了禁忌搜索在TSP问题、前向神经网络和多维背包问题中的应用，并就如何实现禁忌搜索的并行化提出了三种并行策略，论文的主要创新点可以归纳如下： (1)针对禁忌搜索中集中性搜索与多样性搜索之间的矛盾，提出了一种自适应搜索策略。该策略将邻域中的元素划分为两部分，即集中性元素和多样性元素，分别用于集中性搜索和多样性搜索，然后根据搜索的进程，自适应地调整候选集中的集中性元素与多样性元素的数量，以协调此矛盾。以TSP问题为例做了仿真实验，结果显示，该策略具有框架灵活、通用性较强、与具体问题无关等优点，可推广应用于其它问题的求解。与神经网络方法的对比显示，基于该策略的禁忌搜索算法具有更高的求解质量。 (2)针对前向神经网络中BP算法的不足，提出了一种前向神经网络的自适应禁忌搜索训练算法，主要解决了如何实现连续变化函数值的禁忌操作、上述

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 禁忌搜索的提出
• 1.3 禁忌搜索的研究现状
• 1.3.1 理论研究
• 1.3.2 应用研究
• 1.4 研究意义
• 1.5 本文的具体工作及内容安排
• 1.5.1 本文的具体工作
• 1.5.2 本文的内容安排
• 1.5.3 本文工作的创新点
• 第二章 禁忌搜索原理及算法描述
• 2.1 禁忌搜索原理
• 2.2 算法描述
• 2.3 禁忌搜索的关键参数及其操作
• 2.4 禁忌搜索与认知心理学
• 第三章 并行计算基础
• 3.1 并行计算机分类
• 3.2 并行计算软件环境
• 3.2.1 PVM并行计算环境
• 3.2.2 MPI并行计算环境
• 3.3 并行算法的基本设计技术
• 第四章 禁忌搜索在TSP问题中的应用
• 4.1 TSP问题简介
• 4.2 旅行商问题的禁忌搜索求解
• 4.2.1 一种新颖的集中性与多样性的自适应搜索策略
• 4.2.2 算法基本流程
• 4.3 仿真实验
• 4.4 本章小结
• 4.4.1 与其它算法的比较
• 4.4.2 小结
• 第五章 禁忌搜索在神经网络中的应用
• 5.1 神经网络简介
• 5.2 多层前向神经网络的禁忌搜索训练
• 5.3 仿真实验
• 5.3.1 异或问题仿真
• 5.3.2 函数逼近仿真
• 5.5 本章小结
• 第六章 禁忌搜索在多维背包问题中的应用
• 6.1 多维背包问题简介
• 6.2 基于双禁忌表的禁忌搜索
• 6.2.1 基本思想
• 6.2.2 算法设计
• 6.3 仿真实验
• 6.4 本章小结
• 第七章 禁忌搜索的并行化
• 7.1 并行禁忌搜索简介
• 7.1.1 并行禁忌搜索的分类
• 7.1.2 并行禁忌搜索的应用研究
• 7.1.3 关于并行禁忌搜索的实现与说明
• 7.2 基于遗传交叉操作的并行禁忌搜索
• 7.2.1 算法设计
• 7.2.2 仿真实验及分析
• 7.3 基于解空间划分的并行禁忌搜索
• 7.3.1 算法设计
• 7.3.2 仿真实验及分析
• 7.4 基于邻域空间划分的并行禁忌搜索
• 7.4.1 算法设计
• 7.4.2 仿真实验及分析
• 7.5 本章小结
• 第八章 总结与展望
• 8.1 总结
• 8.2 展望
• 参考文献
• 附录一 攻博期间发表的论文
• 附录二 攻博期间参加的科研项目
• 致谢