摘要: 现实世界的很多优化问题都是由多个互相作用且互相冲突的目标组成的，它的最优解不是一个解，而是一组均衡解，这组解被称为Pareto最优解集。进化算法作为一种群体智能搜索方法十分适合用来求解多目标优化问题。从20世纪80年代中期开始，进化算法就被... 展开 现实世界的很多优化问题都是由多个互相作用且互相冲突的目标组成的，它的最优解不是一个解，而是一组均衡解，这组解被称为Pareto最优解集。进化算法作为一种群体智能搜索方法十分适合用来求解多目标优化问题。从20世纪80年代中期开始，进化算法就被应用于求解多目标优化问题。近年来涌现出大量的多目标进化算法，其中一些已成功应用到工程实践中，进化多目标优化也因此成为目前进化计算和多目标优化领域的一个研究热点。多目标0/l背包问题是经典的组合优化问题，具有重要的理论研究和工程应用价值，并且常常被用来测试多目标进化算法的性能。 本文旨在通过对多目标进化算法进行深入的探索和研究，针对多目标0/1背包问题设计高效的求解策略，并进行相应的实验和理论分析。本论文的研究内容主要包括以下几个方面： (1)针对多目标0/1背包问题，提出了两种新的加权修复策略。自Zitzler等人提出SPEA算法以来，多目标进化算法被广泛地用于求解多目标0/1背包问题。多目标0/1背包问题必须满足容量约束，然而进化算法在求解过程中会产生超出容量的不可行解。最直接最有效的方法之一是通过修复操作将不可行解变成可行解，而目前最常用的基于最大化利率的修复策略并没有全面考虑物品对各个包的影响。因此，本文提出了两种新的加权修复策略，分别基于背包容量和个体约束违反程度。将这两种新的修复策略分别应用到经典算法SPEA2中来求解多目标0/1背包问题，实验结果表明新的修复策略不仅在2到4个目标的样本上收敛性有较大提高，并且分布性也有一定的改善。与此同时，在目标数超过4个的高维多目标0/1背包问题上性能也有明显提高。 (2)针对多目标优化问题，基于Minkowski距离和对各个目标值进行加权，提出了多种新的密度评估策略。多目标优化的目标就是找到一个解集。这个解集要满足两个要求，即收敛性和分布性。收敛性就是要使得到的解集在目标空间上与真正Pareto最优前沿的距离尽可能小，而分布性则是要使这个解集在目标空间尽可能均匀分布。当前多目标进化算法的设计正是围绕着这两个要求来进行的。引入Pareto支配关系是为了尽可能保证算法的收敛性，而密度函数的引入则主要是为了尽可能保证算法有更好的分布性。当然，这两方面是相互关联、相互影响的。当非支配解的数目超过归档群体大小时，就需要根据密度函数删除一部分个体。而在遗传选择时，大量支配关系相同的个体就要根据密度函数来决定其优劣。因此，密度评估策略对多目标进化算法的性能是很重要的，但对于高维多目标问题，现有密度评估策略的可扩展性却存在一定问题。为此，本文更全面地考虑目标空间上各个子目标的影响，基于Minkowski距离和对各个子目标值进行加权，提出了几种新的密度评估策略。在4到9个目标的多目标0/1背包问题样本上的实验结果表明，使用新的密度评估策略的多目标进化算法能更有效的收敛到Pareto前沿。然后，将其与本文提出的修复策略相结合，实验结果表明二者结合后使得算法收敛性有更大提高。此外，进一步将已有的基于欧氏距离与随机距离的密度评估策略相结合提出了混合密度评估策略，并用实验验证了它的有效性。 (3)针对多目标进化算法，提出了多种新的遗传选择策略。遗传选择是多目标进化算法的一个重要步骤。现有的多目标进化算法在进行遗传选择时，大都是从外部群体中来选择父代个体，并且基本是采用基于局部竞争的选择方法，如锦标赛选择等。竞争获胜的标准一般是根据适应度的大小来判断，而适应度的大小通常由个体间的Pareto支配关系和个体信息（比如密度函数）来共同决定。当目标数增多时，非支配解的数目急剧增加，外部群体中的大多数个体均为非支配解，此时哪个个体获胜完全依赖于密度函数的值，偏向于保持解集的分布性，这显然不够合理。因此，通过在锦标赛选择时加入考虑两个体间各子目标值的具体对比情况，本文提出了多种新的遗传选择策略。实验结果表明，使用新的遗传选择策略的多目标进化算法在求解超过4个目标的多目标0/1背包问题时性能有很大提高。然后，将其与本文提出的修复策略相结合，实验结果表明二者结合后对于算法收敛性有更大提高，对于算法的分布性也并没有不利的影响。 本论文以多目标优化问题为背景，对多目标0/1背包问题的修复策略、多目标进化算法中的密度评估策略、遗传选择策略进行了较为深入的研究。这不仅对多目标进化算法的研究有着重要的意义，也对多目标优化的实际应用有着重要的意义。 收起