Running Time Analysis of a Multiobjective Evolutionary Algorithm on Simple and Hard Problems
Running Time Analysis of a Multiobjective Evolutionary Algorithm on Simple and Hard Problems
复制标题
DOI：
10.1007/11513575_7
复制
发表时间：
2005-01
期刊：
影响因子：
--
通讯作者：
Rajeev Kumar;N. Banerjee
中科院分区：
文献类型：
--
作者：
Rajeev Kumar;N. Banerjee
在本文中，我们提出了一个多目标的进化算法的基础上限制交配池（REMO）与一个单独的档案存储剩余的人口。这种基于存档的算法已被用于解决现实世界的应用，然而，没有理论结果。在本文中，我们提出了一个严格的运行时间复杂性分析的算法上的两个简单的离散伪布尔函数和多目标背包问题，这是已知的NP-完全。我们使用两个众所周知的简单函数LOTZ（领先的零：尾随的）和二次函数。对于背包问题，我们形式化的（1+ε）-近似集的约束下的项目的权重。然后，我们推广的想法，通过消除的限制的基础上的原则，划分的项目成块和分析REMO上。我们使用一个简单的策略，基于划分的决策空间到健身层的分析。
In this paper, we suggest a multiobjective evolutionary algorithm based on a restricted mating pool (REMO) with a separate archive for storing the remaining population. Such archive based algorithms have been used for solving real-world applications, however, no theoretical results are available. In this paper, we present a rigorous running time complexity analysis for the algorithm on two simple discrete pseudo boolean functions and on the multiobjective knapsack problem which is known to be NP-complete. We use two well known simple functions LOTZ (Leading Zeros: Trailing Ones) and a quadratic function. For the knapsack problem we formalize a ( 1+ε)-approximation set under a constraint on the weights of the items. We then generalize the idea by eliminating the constraints based on a principle of partitioning the items into blocks and analyze REMO on it. We use a simple strategy based on partitioning of the decision space into fitness layers for the analysis.