Title | ||
---|---|---|
Running time analysis of evolutionary algorithms on a simplified multiobjective knapsack problem |
Abstract | ||
---|---|---|
In this paper, the expected running time of two multiobjective evo- lutionary 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. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1023/B:NACO.0000023415.22052.55 | Natural Computing: an international journal |
Keywords | Field | DocType |
decision space partition,evolutionary algorithms,graph search,knapsack problem,multiobjective optimization,Pareto set,running time analysis | Graph,Mathematical optimization,Evolutionary algorithm,Upper and lower bounds,Continuous knapsack problem,Multi-objective optimization,Artificial intelligence,Knapsack problem,Machine learning,Mathematics,Mutation operator,Partition method | Journal |
Volume | Issue | ISSN |
3 | 1 | 1567-7818 |
Citations | PageRank | References |
17 | 1.07 | 8 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Marco Laumanns | 1 | 1452 | 108.63 |
Lothar Thiele | 2 | 14025 | 957.82 |
Eckart Zitzler | 3 | 4678 | 291.01 |