González Begoña, Rossit Daniel A, Méndez Máximo, Frutos Mariano
Universidad de Las Palmas de Gran Canaria (ULPGC), Instituto Universitario SIANI, Spain.
Engineering Department, Universidad Nacional del Sur, INMABB UNS CONICET, Argentina.
Math Biosci Eng. 2022 Jan 25;19(4):3369-3401. doi: 10.3934/mbe.2022156.
Overlapping solutions occur when more than one solution in the space of decisions maps to the same solution in the space of objectives. This situation threatens the exploration capacity of Multi-Objective Evolutionary Algorithms (MOEAs), preventing them from having a good diversity in their population. The influence of overlapping solutions is intensified on multi-objective combinatorial problems with a low number of objectives. This paper presents a hybrid MOEA for handling overlapping solutions that combines the classic NSGA-II with a strategy based on Objective Space Division (OSD). Basically, in each generation of the algorithm, the objective space is divided into several regions using the nadir solution calculated from the current generation solutions. Furthermore, the solutions in each region are classified into non-dominated fronts using different optimization strategies in each of them. This significantly enhances the achieved diversity of the approximate front of non-dominated solutions. The proposed algorithm (called NSGA-II/OSD) is tested on a classic Operations Research problem: the Multi-Objective Knapsack Problem (0-1 MOKP) with two objectives. Classic NSGA-II, MOEA/D and Global WASF-GA are used to compare the performance of NSGA-II/OSD. In the case of MOEA/D two different versions are implemented, each of them with a different strategy for specifying the reference point. These MOEA/D reference point strategies are thoroughly studied and new insights are provided. This paper analyses in depth the impact of overlapping solutions on MOEAs, studying the number of overlapping solutions, the number of solution repairs, the hypervolume metric, the attainment surfaces and the approximation to the real Pareto front, for different sizes of 0-1 MOKPs with two objectives. The proposed method offers very good performance when compared to the classic NSGA-II, MOEA/D and Global WASF-GA algorithms, all of them well-known in the literature.
当决策空间中的多个解映射到目标空间中的同一个解时，就会出现重叠解的情况。这种情况威胁到多目标进化算法（MOEA）的探索能力，使其种群缺乏良好的多样性。重叠解对目标数量较少的多目标组合问题的影响更为严重。本文提出了一种用于处理重叠解的混合多目标进化算法，该算法将经典的NSGA-II与基于目标空间划分（OSD）的策略相结合。基本上，在算法的每一代中，利用从当前代解计算得到的最低点解将目标空间划分为若干区域。此外，使用不同的优化策略将每个区域中的解分类为非支配前沿。这显著提高了非支配解近似前沿所实现的多样性。所提出的算法（称为NSGA-II/OSD）在一个经典的运筹学问题上进行了测试：具有两个目标的多目标背包问题（0-1 MOKP）。使用经典的NSGA-II、MOEA/D和全局WASF-GA来比较NSGA-II/OSD的性能。对于MOEA/D，实现了两个不同的版本，每个版本都有不同的指定参考点的策略。对这些MOEA/D参考点策略进行了深入研究并提供了新的见解。本文深入分析了重叠解对多目标进化算法的影响，研究了不同规模的双目标0-1 MOKP的重叠解数量、解修复数量、超体积指标、达成表面以及与真实帕累托前沿的近似程度。与文献中广为人知的经典NSGA-II、MOEA/D和全局WASF-GA算法相比，所提出的方法具有非常好的性能。
