Some Issues on the Implementation of Local Search in Evolutionary Multiobjective Optimization
Some Issues on the Implementation of Local Search in Evolutionary Multiobjective Optimization
复制标题
DOI：
10.1007/978-3-540-24854-5_120
复制
发表时间：
2004-06
期刊：
影响因子：
--
通讯作者：
H. Ishibuchi;Kaname Narukawa
中科院分区：
文献类型：
--
作者：
H. Ishibuchi;Kaname Narukawa
本文讨论了进化多目标优化(EMO)算法中局部搜索的实现，以设计一个简单但功能强大的EMO算法。首先，我们提出了一个模因EMO算法的基本框架，它是一种NSGA-II和局部搜索的混合算法。在模因EMO算法的世代更新过程中，下一个种群由三个种群构成：当前种群、通过遗传操作产生的子代种群和通过局部搜索从子代种群获得的改进种群。我们以与NSGA-II相同的方式使用帕累托排序和拥挤的概念来选择好的解决方案，以从这三个种群中构建下一个种群。为了在我们的模因EMO算法中实现局部搜索，我们研究了文献中经常使用的两种方法：一种是基于Pareto排名的方法，另一种是基于加权标量适应度函数的方法。帕累托排序法的主要困难在于，目前的局部搜索算法的可移动区域很小。另一方面，加权标量方法的主要困难是通过局部搜索来退化子代种群。用我们的EMO算法对多目标背包问题进行了计算实验，清楚地展示了这些困难。我们的实验结果表明，加权标量方法比Pareto排序法获得了更好的结果。为了进一步改进加权标量方法，我们研究了一些可以用来克服其困难的技巧。
This paper discusses the implementation of local search in evolutionary multiobjective optimization (EMO) algorithms for the design of a simple but powerful memetic EMO algorithm. First we propose a basic framework of our memetic EMO algorithm, which is a hybrid algorithm of the NSGA-II and local search. In the generation update procedure of our memetic EMO algorithm, the next population is constructed from three populations: the current population, its offspring population generated by genetic operations, and an improved population obtained from the offspring population by local search. We use Pareto ranking and the concept of crowding in the same manner as in the NSGA-II for choosing good solutions to construct the next population from these three populations. For implementing local search in our memetic EMO algorithm, we examine two approaches, which have been often used in the literature: One is based on Pareto ranking, and the other is based on a weighted scalar fitness function. The main difficulty of the Pareto ranking approach is that the movable area of the current solution by local search is very small. On the other hand, the main difficulty of the weighted scalar approach is that the offspring population can be degraded by local search. These difficulties are clearly demonstrated through computational experiments on multiobjective knapsack problems using our memetic EMO algorithm. Our experimental results show that better results are obtained from the weighted scalar approach than the Pareto ranking approach. For further improving the weighted scalar approach, we examine some tricks that can be used for overcoming its difficulty.