基于带Path-Relinking的GRASP的超启发式方法

论文摘要

超启发式算法的目标是设计一种选取启发式算子的启发式策略,以解决复杂多样的问题。提出超启发式算法这个概念的主要动机是泛化启发式方法解决问题的能力,使其能解决不同领域问题,而不是传统意义上的同种类型问题。作为启发式方法里的一个分类,大部分超启发式方法吸取了已经存在的元启发式方法的经验,比如基于模拟退火的超启发式方法和基于遗传算法的超启发式方法。然后超启发方法的种类远远小于元启发式方法的种类,这些方法的短缺极大的限制了超启发式方法的发展。在这篇论文中我们提出了基于带Path-Reliking的GRASP的超启发式算法（HyGrasPr）。HyGrasPr使用迭代的方法生成低层次启发式算子序列（LLH sequence）来求得问题的解。HyGrasPr超启发式算法由三个主要步骤组成：构造LLH序列阶段,局部搜索阶段和Path-Relinking阶段。LLH序列是由带Path-Relinking的GRASP的每一次迭代过程产生的。在HyGrasPr中,我们先在GRASP构造阶段生成固定长度的LLH序列。然后我们搜索这个LLH序列的的领域找到局部最优的LLH序列。最后我们用当前最优的LLH序列和得到的局部最优LLH序列进行Path-Relinking的过程。为了验证我们HyGrasPr超启发式算法的性能,我们在护士调度问题和一维装箱问题做为案例进行实验。我们实现了已经提出的基于模拟退火的超启发式算法,并把它作为基准进行对比。实验结果显示HyGrasPr在相同的运行时间的条件下可以取得更好的解,Path-Relinking这个阶段在算法中也是非常有效的。

论文目录

• 摘要
• Abstract
• 引言
• 1 预备知识
• 1.1 元启发式方法
• 1.1.1 启发式算法概念
• 1.1.2 元启发式算法
• 1.2 超启发方法
• 1.2.1 超启发式方法的分类
• 1.2.2 高层次启发式方法（High Level Heuristic）
• 1.2.3 低层次启发式方法（Low Level Heuristic）
• 1.3 GRASP（Greedy Randomized Adaptive Search Procedure）
• 1.3.1 GRASP的简介
• 1.3.2 GRSP中的两个重要的参数
• 1.4 Path-Relinking
• 1.5 GRASP with Path-Relinking
• 2 基于GRASP和Path-Relinking的超启发算法
• 2.1 算法的总体框架
• 2.2 GRASP过程
• 2.2.1 GRASP构建过程
• 2.2.2 GRASP局部搜索过程
• 2.3 Path-Relinking过程
• 3 护士调度问题上的实验
• 3.1 护士调度问题简介
• 3.2 护士调度问题上用到的LLH
• 3.3 HyGrasPr在护士调度问题上的实验结果
• 4 一维装箱问题上的实验
• 4.1 一维装箱问题的描述
• 4.2 初始解的生成和评估函数
• 4.3 一维装箱问题上用到的LLHs
• 4.4 HyGrasPr在护士调度问题上的实验结果
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢