档案截断时机的选择:多目标优化中截断频率的影响

When to Truncate the Archive? On the Effect of the Truncation Frequency in Multi-Objective Optimisation

摘要 Abstract

在多目标进化算法(MOEA)的搜索过程中,使用档案存储非支配解是一种有用的做法。然而,由于多目标优化问题的非支配解可能是巨大的甚至是无限多的,因此希望仅向决策者提供档案中所有非支配解的一个小而有代表性的部分,这就需要进行截断操作。此时,一个重要的问题是何时进行档案截断。这可以在生成新解时进行,也可以在一批新解生成后进行,甚至可以使用无界档案保存所有生成的非支配解并在之后进行截断。直观上,最后一种方法可能会得到更好的结果,因为在截断之前我们已经掌握了所有的信息。本文研究了这一问题,并探讨了截断档案时机对结果的影响。我们应用了在MOEA的人口维护过程中常用的截断标准(例如,拥挤距离、超体积指标和分解)。有趣的是,我们发现每次生成新解时就进行截断往往是最优的,而考虑无界档案通常是效果最差的。我们分析并讨论了这一现象。我们的结果显示,在使用大档案时,开发有效的子集选择技术(而非采用MOEA中的种群维护方法)的重要性。

Using an archive to store nondominated solutions found during the search of a multi-objective evolutionary algorithm (MOEA) is a useful practice. However, as nondominated solutions of a multi-objective optimisation problem can be enormous or infinitely many, it is desirable to provide the decision-maker with only a small, representative portion of all the nondominated solutions in the archive, thus entailing a truncation operation. Then, an important issue is when to truncate the archive. This can be done once a new solution generated, a batch of new solutions generated, or even using an unbounded archive to keep all nondominated solutions generated and truncate it later. Intuitively, the last approach may lead to a better result since we have all the information in hand before performing the truncation. In this paper, we study this issue and investigate the effect of the timing of truncating the archive. We apply well-established truncation criteria that are commonly used in the population maintenance procedure of MOEAs (e.g., crowding distance, hypervolume indicator, and decomposition). We show that, interestingly, truncating the archive once a new solution generated tends to be the best, whereas considering an unbounded archive is often the worst. We analyse and discuss this phenomenon. Our results highlight the importance of developing effective subset selection techniques (rather than employing the population maintenance methods in MOEAs) when using a large archive.