|
Authors: | Marco Laumanns, Lothar Thiele, Eckart Zitzler |
Group: | Computer Engineering |
Type: | Article |
Title: | Running Time Analysis of Evolutionary Algorithms on a Simplified Multiobjective Knapsack Problem |
Year: | 2004 |
Pub-Key: | LTZ2004b |
Journal: | Natural Computing |
Volume: | 3 |
Number: | 1 |
Pages: | 37-51 |
Keywords: | EMO |
Abstract: | In this paper, the expected running time of two multiobjective evolutionary algorithms, SEMO and FEMO, is analyzed for a simple instance of the multiobjective 0/1 knapsack problem. The considered problem instance has two profit values per item and cannot be solved by one-bit mutations. In the analysis, we make use of two general upper bound techniques, the decision space partition method and the graph search method. The paper demonstrates how these methods, which have previously only been applied to algorithms with one-bit mutations, are equally applicable for mutation operators where each bit is flipped independently with a certain probability. |
Resources: | [BibTeX] [Paper as PDF] |