求解动态优化问题的Memetic算法研究及应用

摘要

动态优化问题的研究在现实生产和生活中具有非常广泛的意义。例如，接连到达的工件需要被加入到原有的调度中;机器可能会发生随机故障或逐渐磨损;原材料的性能可能会随时间发生改变;生产过程中需要考虑生产限度的影响等。近些年来，动态环境中优化问题的求解已经引起了学者的广泛关注。
　　本文提出一种新的求解动态优化问题的Memetic算法。Memetic算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体。因而Memetic算法成为解决各种优化问题的很好的方法。然而算法随着迭代的进行，种群会逐渐收敛，失去了对环境变化的适应能力，这是Memetic算法在动态环境中所面临的主要挑战。因此，在全局搜索策略中为了避免种群出现过早收敛的现象，本文引入原对偶映射移民策略（Primal-Dual based Immigrants，PDI）来保持种群多样性，增强其对动态环境的适应能力。在局域搜索(Local Search，LS)策略中，每一种LS方法可能针对某些问题特别有效而对于另外一些问题效果却并不明显，为了改善局域搜索策略，本文提出一种自适应的LS方法，使不同的LS方法可以通过互相协作来改善解的质量。通过仿真实验验证了本文提出的算法对求解动态优化问题非常的有效并且优越于其他算法。
　　本文遵循综述—算法研究—算法应用的思路，针对求解动态优化问题的Memetic算法进行了研究。具体研究内容如下:
　　(1)对遗传算法，Memetic算法以及动态环境下算法的相关研究进行了综述。
　　(2)设计求解动态优化问题的Memetic算法，包括局域搜索的设计以及保持种群多样性策略的设计。
　　(3)构建动态TSP问题，并测试算法的性能。
　　(4)构建动态单机调度问题，并用本文提出的算法进行求解，证明算法的可行性。

目录

声明

摘要

第1章 前言

1．1 课题的背景和意义

1．2 本文主要研究内容

1．3论文的主要工作

第2章 相关研究工作

2．1 前言

2．2 遗传算法及在动态环境中的应用

2．2．1 遗传算法

2．2．2 遗传算法在动态环境中的应用

2．3 Memetic算法及其应用

2．3．1 Memetic算法

2．3．2 Memetic算法的发展

2．3．3 Memetic算法的应用

2．4 本章小结

第3章 求解动态优化问题的Memetic算法

3．1 求解动态优化问题的Memetic算法的基本框架

3．2 保持种群多样性方法

3．3 局域搜索

3．3．1 基于2-opt的局域搜索

3．3．2 基于Insert的局域搜索

3．3．3 基于Swap的局域搜索

3．4 本文提出的求解动态优化问题的Memetic算法(MPDIGA)

3．5 本章小结

第4章 Memetic算法在动态TSP问题中的应用

4．1 TSP问题和动态TSP问题

4．2 构造动态TSP测试问题

4．3 仿真算例及分析

4．3．1 仿真设置

4．3．2 保持种群多样性策略的实验

4．3．3 算法加入不同局域搜索(LS)的实验

4．4 本章小结

第5章 Memetic算法在动态单机调度问题中的应用

5．1 调度问题

5．2 单机调度问题

5．3 动态单机调度问题

5．4 仿真算例及分析

5．5 本章小结

第6章 结束语

参考文献

致谢