基于区域分解的高维多目标进化算法及其应用

摘要

进化算法是一类模拟生物自然选择与自然进化的随机搜索算法，因其适用于求解高度复杂的非线性问题而得到了非常广泛的应用，同时它又具有较好的通用性。在解决较少目标的复杂优化问题时，进化算法的优势得到了充分的展现。然而，现实生活中的优化问题通常是涉及到很多个目标（至少3个以上），在这种情况下，高维多目标进化算法应运而生。
　　基于上述的背景，本文分别提出了基于相关性选择的高维多目标进化算法和基于区域划分的高维多目标进化算法，另外，在对组合多目标优化问题的研究下，将基于区域划分的高维多目标进化算法的改进版本用来处理背包问题。本文具体工作如下：
　　1．提出了基于相关性选择的高维多目标进化算法。算法首先给出了参考点和个体的相关性概念；接着提出了基于相关性的变异选择机制，该机制通过参考点的相关个体的数目保证了种群的多样性；然后提出了基于相关性的环境选择机制，该机制在进一步保证种群多样性的前提下，又通过标量函数保证了种群的收敛性。通过对3至15个目标的DTLZ1、DTLZ2、DTLZ3和DTLZ4优化函数的测试，实验结果表明在IGD指标上同NSGA-III算法和MOEA/D算法有很大的竞争性，并且运行时间快于其他算法。
　　2．提出了基于区域划分的高维多目标优化算法。算法首先将目标空间分解成一组子区域，并为每个子区域定义了两个重要属性；接着提出了基于区域属性的变异选择机制，该机制通过子区域的两个属性选择目标空间中比较稀疏区域的个体，从而保证种群的多样性；然后又提出了基于区域属性的种群更新机制，该机制通过子区域的一个属性进一步保证种群多样性的前提下，再通过标量函数保证种群的收敛性。该算法同NSGA-III算法和MOEA/D算法一起应用到一组高维多目标优化问题上，尽管两种对比算法在某些问题上能够取得很好的结果，但新算法却几乎在所有测试问题上均能取得最好的结果。
　　3．提出了用于背包问题的高维多目标优化算法。该算法主要是基于区域划分的高维多目标优化算法的改进版本。在该改进算法中，当第一个待变异个体被选择之后，根据预先设定的概率值决定是从整个种群中还是从第一个待变异个体的邻近个体中选择一个个体作为另一个待变异个体。为了更好地处理组合优化问题，我们还将参考点近似映射到了最优 Pareto前端附近。通过对2至4个目标的250、500和750元素的背包问题的测试，实验结果表明，新算法在所有测试问题上的多样性均比MOEA/D算法好，并且在大部分测试问题上收敛性也是最好的。除此之外，新算法的鲁棒性也比MOEA/D算法好。

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

符号对照表

缩略语对照表

目录

第一章 绪论

1.1课题背景及意义

1.2国内外研究现状

1.3本论文的主要工作及内容安排

第二章 基于相关性选择的高维多目标分解进化算法

2.1引言

2.2相关理论背景

2.3基于相关性选择的高维多目标进化分解算法

2.4实验结果与分析

2.5本章小结

第三章 基于区域划分的高维多目标分解进化算法

3.1引言

3.2相关理论背景

3.3基于区域划分的高维多目标分解进化算法

3.4实验结果与分析

3.5本章小结

第四章 用于背包问题的高维多目标优化算法

4.1引言

4.2背包问题的数学模型

4.3 RD-EMO算法在背包问题上的应用

4.4实验结果与分析

4.5本章小结

第五章 总结与展望

5.1论文总结

5.2研究展望

参考文献

致谢

作者简介