论文部分内容阅读
多目标背包问题是对有限资源竞争问题的抽象,如投资组合问题、项目选择问题、货物装载问题等,具有广泛的工程背景,一直是科学和工程研究领域的难点和热点。当背包数量大于或者等于4的时候,多目标背包问题又称之为高维目标背包问题。在求解复杂高维目标背包问题时,现有的多目标进化算法遇到了一系列的挑战。随着背包数目的增多,帕累托占优型进化算法容易失去选择压力而难以产生接近帕累托前沿的解,指标型进化算法在运行时间上将急剧增长而变得不太可行。相比之下,分解型进化算法计算高效且其有效性在高维目标背包问题的求解上得到验证。但是分解型进化算法仍然存在不足之处。它在进化的过程中容易存留冗余的个体且存在个体与子问题不相匹配的现象,最终造成种群多样性和收敛性的退化。此外,现有的多目标进化算法几乎都是基于交叉变异的重组操作去产生新个体,这导致算法具有较大的不确定性。为了有效地解决高维目标背包问题,本文将在经典分解型进化算法MOEA/D的基础上,提出分解占优协作式机制,设计基于交叉变异的分解占优协作式进化算法,初步提高算法的性能。在此基础上,用神经进化的重组操作替换交叉变异的重组操作,设计基于神经进化的分解占优协作式进化算法,更进一步提高算法的性能。本文主要研究的工作总结如下:1)提出分解占优协作式机制,分为占优存档的生成与更新、分解种群的修复及存档与种群融合阶段。占优存档的生成主要借助于分解的种群,在更新阶段筛选出精英个体。分解种群的修复则借助于存档中的精英个体以实现种群的进化。最后,在种群融合阶段筛选出分解种群和占优存档中的精英个体,得到最优的种群。2)针对经典分解型进化算法MOEA/D的不足,在分解占优协作式机制的基础上,设计基于交叉变异的分解占优协作式进化算法,解决MOEA/D中容易存留冗余的个体且存在个体与子问题不相匹配的问题,避免种群收敛性和多样性的退化,从而提高解集质量。3)在基于交叉变异的分解占优协作式进化算法的基础上,加入神经进化的思想,设计基于神经进化的分解占优协作式进化算法。在种群的初始化阶段,每个个体将唯一地绑定一个神经网络模型。在重组阶段,与当前子问题相对应的个体的神经网络模型参数被更新,该神经网络的输出为新个体。由于神经网络具备学习能力,在进化的过程中,学习能力逐步增强,这样进一步提高分解占优协作式进化算法获得的解集质量。4)分别在随机型、相关型、依赖型三种高维目标背包测试例上对本文设计的分解占优协作式进化算法进行有效性测试。先是结合几种优秀的多目标进化算法作为对比,验证基于交叉变异的分解占优协作式进化算法的初步效果,然后加入神经进化思想设计分解占优协作式进化算法,进一步验证算法效果。在复杂高维目标背包测试例上的实验结果表明,本文设计的基于交叉变异的分解占优协作式进化算法能够改善经典分解型进化算法MOEA/D的性能,而进一步设计的基于神经进化的分解占优协作式进化算法则取得更优的实验效果,很好地解决了复杂高维目标背包问题。