Campus Event Calendar

Event Entry

What and Who

Making problems easier by multi-objective optimization (in evolutionary computation)

Frank Neumann
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience
-- Not specified --

Date, Time and Location

Friday, 8 June 2007
-- Not specified --
E1 4


Evolutionary algorithms have been shown to be good problem solvers for several optimization problems. Considering at least two objective functions that have to be optimized at the same time, we are dealing with multi-objective optimization problems. Often it is assumed that more objectives make a problem harder as the number of different trade-offs may increase with the number of objectives that are considered. In this talk, we examine how solving single-objective problems can be made easier by multi-objective optimization.

First, we consider the effect of adding objectives to a given problem. Experimental studies show that additional objectives may change the runtime behavior of evolutionary algorithms drastically. We illustrate the effect of adding objectives by considering simple functions and point out by theoretical analyses that this may be both beneficial and obstructive.
Later on, we consider the approximation ability of evolutionary algorithms for the class of covering problems and compare single-objective and multi-objective models for such problems.
We show that optimal solutions can be approximated within a factor of log n, where $n$ is the problem dimension, using a multi-objective approach while the approximation quality obtainable by a corresponding single-objective one may be arbitrarily bad.


Frank Neumann
--email hidden
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

evolutionary computation, multi-objective optimization

Frank Neumann, 06/05/2007 14:38
Frank Neumann, 05/29/2007 15:41
Frank Neumann, 05/09/2007 20:47
Frank Neumann, 05/08/2007 15:18 -- Created document.