Analysis of a simple evolutionary algorithm for the multiobjective shortest path problem

Loading...
Thumbnail Image

Date

2008-12

Journal Title

Journal ISSN

Volume Title

Publisher

Alternative Title(s)

Abstract

We present a natural fitness function f for the multiobjective shortest path problem, which is a fundamental multiobjective combinatorial optimization problem known to be NP-hard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomial-time randomized approximation scheme (FPRAS) for the problem under consideration, which exemplifies how EAs are able to find good approximate solutions for hard problems.

Description

Table of contents

Keywords

Subjects based on RSWK

Citation