 |
|
|||
| Authors: | Marco Laumanns, Lothar Thiele, Eckart Zitzler |
| Group: | Computer Engineering |
| Type: | Article |
| Title: | An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method |
| Year: | 2006 |
| Month: | March |
| Pub-Key: | LTZ2003c |
| Journal: | European Journal of Operational Research |
| Volume: | 169 |
| Number: | 3 |
| Pages: | 932-942 |
| Keywords: | EMO |
| Abstract: | This paper presents a new metaheuristic scheme for generating or approximating the Pareto set of multiobjective optimization problems on the basis of an arbitrary single-objective optimizer. The algorithm is employs the epsilon-constraint method and works for any numbers of objectives $m$. Its time complexity, measured by the number of constrained single-objective sub-problems to be solved, is $O(k^m)$, where $k$ is the number of Pareto-optimal solutions to be found. The new algorithm is therefore insensitive to monotonous transformations of the objectives, which is not the case for the original implementation of the epsilon-constraint method. A simple example problem is shown, where the original epsilon-constraint method has exponential running time for a fixed number of objectives. A proof for the time complexity of the new algorithm is given. |
| Resources: | [BibTeX] [ External LINK ] [Paper as PDF] |
