Difficulty in Evolutionary Multiobjective Optimization of Discrete Objective Functions with Different Granularities
Difficulty in Evolutionary Multiobjective Optimization of Discrete Objective Functions with Different Granularities
复制标题
DOI：
10.1007/978-3-642-37140-0_20
复制
发表时间：
2013-03
期刊：
影响因子：
--
通讯作者：
H. Ishibuchi;M. Yamane;Y. Nojima
中科院分区：
文献类型：
--
作者：
H. Ishibuchi;M. Yamane;Y. Nojima
组合优化中的目标函数是离散的。一般来说，离散目标的可能值的数量因问题而异。即离散目标在不同的问题中具有完全不同的粒度（本文中的“粒度”是指离散化区间的宽度）。在组合多目标优化中，一个问题有多个不同粒度的离散目标。一些目标可能具有许多可能值的精细粒度，而另一些目标可能具有非常粗糙的粒度，只有几个可能值。对于这种组合多目标问题的处理在EMO社区中还没有得到积极的讨论。在我们之前的研究中，我们发现粗粒度的离散目标减慢了NSGA-II、SPEA2、MOEA/D和SMS-EMOA在双目标问题上的搜索速度。在本文中，我们首先讨论了为什么这种离散目标会降低那些EMO算法的搜索能力。接下来，我们提出在NSGA-II中使用强帕累托优势来提高其搜索能力。然后，我们研究了离散目标对四种EMO算法在多目标问题上性能的影响。一个有趣的观察结果是，粗粒度离散目标提高了NSGA-II和SPEA2在多目标问题上的搜索能力，而降低了它们在双目标问题上的搜索能力。MOEA/D和SMS-EMOA的性能通常会因为离散的粗粒度物镜而变差。本文从以下两个角度对这些观察结果进行了讨论：一是基于Pareto支配的EMO算法的多目标问题的难度，二是离散目标与ε-支配概念之间的关系。
Objective functions are discrete in combinatorial optimization. In general, the number of possible values of a discrete objective is totally different from problem to problem. That is, discrete objectives have totally different granularities in different problems (In this paper, “granularity” means the width of discretization intervals). In combinatorial multiobjective optimization, a single problem has multiple discrete objectives with different granularities. Some objectives may have fine granularities with many possible values while others may have very coarse granularities with only a few possible values. Handling of such a combinatorial multiobjective problem has not been actively discussed in the EMO community. In our former study, we showed that discrete objectives with coarse granularities slowed down the search by NSGA-II, SPEA2, MOEA/D and SMS-EMOA on two-objective problems. In this paper, we first discuss why such a discrete objective deteriorates the search ability of those EMO algorithms. Next we propose the use of strong Pareto dominance in NSGA-II to improve its search ability. Then we examine the effect of discrete objectives on the performance of the four EMO algorithms on many-objective problems. An interesting observation is that discrete objectives with coarse granularities improve the search ability of NSGA-II and SPEA2 on many-objective problems whereas they deteriorate their search ability on two-objective problems. The performance of MOEA/D and SMS-EMOA is always deteriorated by discrete objectives with coarse granularities. These observations are discussed from the following two viewpoints: One is the difficulty of many-objective problems for Pareto dominance-based EMO algorithms, and the other is the relation between discrete objectives and the concept ofε-dominance.