论文标题
背包问题的单目标和多目标进化算法以及动态变化的约束
Single- and Multi-Objective Evolutionary Algorithms for the Knapsack Problem with Dynamically Changing Constraints
论文作者
论文摘要
进化算法是生物启发的算法，可以轻松适应不断变化的环境。运行时分析区域的最新结果指出，诸如（1+1）和全局SEMO之类的算法可以在动态统一约束下有效地重视线性函数。在这项研究的激励下，我们研究了经典背包问题的单目标基线进化算法，其中背包的能力会随着时间而变化。 我们建立了不同的基准方案，其中容量根据统一或正常分布改变了每一个$τ$迭代。我们的实验研究根据所选分布的参数，由$τ$确定的频率以及所考虑的Knapsack实例类别来分析我们算法的行为。我们的结果表明，使用人群来满足动态变化的种群的多目标方法在许多基准的情况下都具有明显的优势，而当变化的频率不高。此外，我们证明了在流行的进化多目标算法（例如NSGA-II和SPEA2）中使用的多样性机制并不一定会导致更好的性能，甚至与我们简单的多目标方法相比，还会导致较差的结果。
Evolutionary algorithms are bio-inspired algorithms that can easily adapt to changing environments. Recent results in the area of runtime analysis have pointed out that algorithms such as the (1+1)~EA and Global SEMO can efficiently reoptimize linear functions under a dynamic uniform constraint. Motivated by this study, we investigate single- and multi-objective baseline evolutionary algorithms for the classical knapsack problem where the capacity of the knapsack varies over time. We establish different benchmark scenarios where the capacity changes every $τ$ iterations according to a uniform or normal distribution. Our experimental investigations analyze the behavior of our algorithms in terms of the magnitude of changes determined by parameters of the chosen distribution, the frequency determined by $τ$, and the class of knapsack instance under consideration. Our results show that the multi-objective approaches using a population that caters for dynamic changes have a clear advantage on many benchmarks scenarios when the frequency of changes is not too high. Furthermore, we demonstrate that the diversity mechanisms used in popular evolutionary multi-objective algorithms such as NSGA-II and SPEA2 do not necessarily result in better performance and even lead to inferior results compared to our simple multi-objective approaches.
