一种动态多目标背包问题及其算法研究

摘要

现实世界中很多优化问题通常具有一些复杂特性，比如多目标性、动态性等，这些复杂特性无疑会给问题的求解带来了极大难度，传统优化方法可能无法获得满意的效果。由于所采纳基于自然选择和种群迭代寻优机制具有很强的适应性，使得众多学者对利用进化算法来解决各种多目标优化或者动态优化问题产生广泛的兴趣，随之衍生的研究领域通常可以称为进化多目标优化、进化动态优化等等。值得注意的是，很多实际应用问题往往同时具有多种复杂特性，而现有的相关研究工作大多数仅仅考虑一种特性。近年来，具有多种复杂特性优化问题的求解开始成为进化计算领域的新的研究热点，其中利用进化算法来解决动态多目标优化问题就是一个新兴的研究主题。 基于此，本论文采纳系统工程和控制工程的思想，运用运筹学、计算科学以及应用数学等领域的理论和方法，围绕求解动态多目标背包问题的进化算法从问题产生和算法设计两个方面展开具体的研究工作，以期提出一种新的动态多目标测试问题并进一步通过仿真实验分析现有算法思想在这种新测试问题上的有效性。本论文的具体研究工作主要包括如下三个方面:(1)通过对传统多目标优化理论、进化动态优化以及动态多目标优化问题的研究工作进行综述，深入了解进化动态多目标优化目前处于的研究阶段;(2)通过对多目标背包问题以及动态优化问题产生方法相关研究的总结分析，提出一种基于XOR算子的动态多目标背包问题的构造方法;(3)将三种不同的策略分别引入到两种经典的多目标进化算法即NSGA-Ⅱ和MOEA/D的算法框架，使其能够求解所构造的动态多目标背包问题，并进一步利用一系列随机产生的测试算例检验所提出算法求解这种动态多目标背包问题的有效性。 通过上述研究，能够发现本论文所提出的动态多目标背包问题产生方法能够构造鲁棒的测试算例，同时所提出的各种策略对于环境的不同动态特性也表现出较好的适应能力。

目录

声明

摘要

1．1研究背景及意义

1．2研究内容与技术路线

1．3本文章节安排

第2章相关工作介绍

2．1多目标优化理论

2．1．1优化模型

2．1．2相关概念

2．1．3传统方法的多目标优化方法

2．2进化多目标优化

2．2．1进化算法简述

2．2．2多目标进化算法分类

2．2．3几种经典的多目标进化算法

2．3动态多目标优化问题研究

2．3．1数学描述

2．3．2评价指标

2．3．3相关研究工作简述

2．4本章小结

第3章动态多目标背包问题构造方法研究

3．1多目标背包问题

3．1．1基本背包问题数学模型

3．1．2多目标背包问题的数学模型

3．2动态多目标背包问题构造方法研究

3．2．1动态优化问题构造方法介绍

3．2．2 XOR算子介绍

3．2．3基于XOR算子的动态多目标背包问题构造

3．3本章小结

第4章算法实现与仿真实验分析

4．1利用NSGA-II求解动态多目标背包问题的算法实现过程

4．2利用MOEA／D求解动态多目标背包问题的算法实现过程

4．3仿真实验分析

4．3．1测试算例的产生

4．3．2实验设计

4．3．3基本实验结果分析

4．3．4不同策略对同一算法性能影响程度分析

4．3．5同一策略下不同算法性能比较

4．4本章小结

5．1总结

5．2研究展望

参考文献

致谢