【作者】 黄林峰；

【导师】 王煦法； 罗文坚；

【作者基本信息】 中国科学技术大学 ， 计算机应用技术， 2009， 博士

【摘要】 现实世界的很多优化问题都是由多个互相作用且互相冲突的目标组成的,它的最优解不是一个解,而是一组均衡解,这组解被称为Pareto最优解集。进化算法作为一种群体智能搜索方法十分适合用来求解多目标优化问题。从20世纪80年代中期开始,进化算法就被应用于求解多目标优化问题。近年来涌现出大量的多目标进化算法,其中一些已成功应用到工程实践中,进化多目标优化也因此成为目前进化计算和多目标优化领域的一个研究热点。多目标0/1背包问题是经典的组合优化问题,具有重要的理论研究和工程应用价值,并且常常被用来测试多目标进化算法的性能。本文旨在通过对多目标进化算法进行深入的探索和研究,针对多目标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背包问题的修复策略、多目标进化算法中的密度评估策略、遗传选择策略进行了较为深入的研究。这不仅对多目标进化算法的研究有着重要的意义,也对多目标优化的实际应用有着重要的意义。更多还原

【Abstract】 Many optimization problems in the real world are composed of several conflict objectives. Its optimal solution is not one but a set of solutions, and they are called the Pareto Optimal Set. As population-based global search methods, Evolutionary Algorithms (EAs) are very promising to solve the multiobjective optimization problems (MOPs). Since the mid 1980s, EAs have been applied to solve MOPs. Recently many Evolutionary Multioptimization Algorithms have been proposed, and some of them have been successfully applied in engineering. Therefore, the research of evolutionary multiobjective optimization (EMO) has become a hot research field in Evolutionary Computation community. The Multiobjective 0/1 Knapsack Problem (MOKP) is one of the most traditional combinatorial problems. It is important for theoretic research and engineering applications, and is often used to test the performance of EMOs.The aim of this dissertation is to explore the theories and mechanisms of EMOs and to design effective strategies for MOKP, and to do the corresponding theoretic and experimental analyses. The main research works in this dissertation consist of the following aspects.(1) For Multiobjective 0/1 knapsack problem, two novel weighted repair strategies are proposed. Since Zitzler proposed SPEA, EMO has been widely used to solve MOKP. The capacity constraints must be satisfied in MOKP but infeasible solutions will come into being when MOKP is solved by EAs. One of the most useful methods is repair strategy which can change infeasible solutions to feasible ones. However, the most widely used repair strategy which is based on maximum profit/weight ratio can not involve the different impacts of each item on all knapsacks. In this paper, two novel repair strategies are proposed, which are based on knapsack capacities and constraint violations respectively. These two novel strategies are applied in SPEA2 to solve MOKP. The experimental results show that SPEA2 with the novel repair strategies not only have much better convergence to the Pareto-optimal front but also better distribution on the test cases with two to four objectives. Meanwhile, the performance of SPEA2 with the novel repair strategies is significantly improved.(2) For Multiobjective optimization problem, several novel density estimation strategies are proposed which are based hybrid Minkowski distances and weighted scalar sub objective values. The aim of multiobjective optimization is to find a solution set which has good convergence and distribution. Good convergence means the distance from the solution set to the Pareto optimal front is as small as possible and good distribution means the solutions are as uniform as possible. Now the design of multiobjective optimization evolutionary algorithms is to satisfy these two conditions. Pareto domination guarantees good convergence and density estimation guarantees good distribution in EMO. However, these two strategies associate and influence each other. If the number of non-dominated solutions exceeds the size of archive set, some solutions will be deleted according to the density. The solutions with the same pareto domination will be judged by their density in the genetic selection. So the density estimation strategy is very important in EMO but the scalability of currently used strategies are not good when the number of objectives becomes more than four. In this paper, the different impacts of each sub objective are much more generally considered and several novel density estimation strategies are proposed which are based Minkowski distance and weighted scalar sub objective values. The experimental results on MOKP cases with four to nine objectives show that EMO with new density estimation strategies have better convergence to the Pareto optimal front. Then they are combined with the novel repair strategies and the performance of the algorithm is obviously enhanced. Moreover, a novel hybrid density estimation strategy is proposed which is combined by Euclid distance and random distance. The experimental results also show its validity.(3) For evolutionary multiobjective algorithm, several novel selection strategies are proposed. Genetic selection is an important step in EMO. Parent individuals are mostly selected from the archive set and the selection is usually based on competition, e.g. tournament selection. The criterion of winner depends on its fitness value which is determined by pareto relation and individual information, e.g. density function. When the objective number becomes larger, the number of non-dominated solutions will increase quickly and most of the solutions in the archive set are non-dominated. So which one will be chosen as parent just depends on density information and it is not reasonable to mainly consider its distribution. In this paper, several novel selection strategies are proposed by adopting comparison of each sub objective for two individuals. The experimental results on MOKP test cases with four to nine objectives demonstrate that the convergence of the algorithm is greatly improved by novel selection strategies. Then they are combined with the novel repair strategies to SPEA2 and the convergence of the algorithm becomes much better and the distribution is not worse.In this dissertation, with the studies in evolutionary multiobjective optimization and multiobjective 0/1 knapsack problem, two novel repair strategies are designed for MOKP, several novel density estimation strategies and several novel genetic selection strategies are proposed for Evolutionary Multiobjective Optimization. The works in this dissertation are very important not only to the research of the multiobjective optimization evolutionary algorithms but also to the optimization applications of EMOs in the real world.更多还原