Computer EngineeringComputer Engineeringand and NetworksNetworks LaboratoryLaboratory

Do Additional Objectives Make a Problem Do Additional Objectives Make a Problem Harder?Harder?

Dimo Brockhoff, Tobias Friedrich,Dimo Brockhoff, Tobias Friedrich,Nils Hebbinghaus, Christian Klein,Nils Hebbinghaus, Christian Klein,

Frank Neumann, Eckart ZitzlerFrank Neumann, Eckart Zitzler

GECCO 2007GECCO 2007, 11 JulyJuly 20072007

Do Additional Objectives Make a Problem Harder? 2© Systems Optimization Group ETH Zurich

Starting Point

Most optimization problems are multiobjective in nature…→ Include as many objective as possible would be desirable

~1995: formulated as single-objective problem

~2005: formulated as two- or three-objective problem

Today: many-objective problems

Are the algorithms bad or are the problems more difficult or both?

We haven't understood yet how additional objectives affects the problem complexity!

Wagner et al. (2007)

Do Additional Objectives Make a Problem Harder? 3© Systems Optimization Group ETH Zurich

Adding Objectives: What Is Known Today…

problems may become harder

Fonseca and Fleming (1995), Deb (2001), Coello et al. (2002), and others:

conflicts between objectivesPareto front size # incomparable solutions

Winkler (1985):theoretical work for random objectives

problems may become easier

Knowles et al. (2001):multiobjectivization

Jensen (2004):helper-objectives

Scharnow et al. (2002), Neumann and Wegener (2006):

theoretical investigations2D faster than 1Ddecomposition

Statements are contradictory: some studies say that…

Do Additional Objectives Make a Problem Harder? 4© Systems Optimization Group ETH Zurich

Given:single-objective problemalgorithm for single- and multiobjective optimization: SEMO - (1+1)EA

Now:add an objective, but keep the search space the same

Question:What is the runtime complexity to generate all Pareto optima in comparison to the original problem?

Note:single-objective optimum is part of the Pareto-optimal set

Question Addressed In This Study

Do Additional Objectives Make a Problem Harder? 5© Systems Optimization Group ETH Zurich

General Considerations On Adding Objectives

Weak Pareto-dominance relation illustrated as relation graph

comparable

incomparable

Do Additional Objectives Make a Problem Harder? 6© Systems Optimization Group ETH Zurich

A Simple Evolutionary Multiobjective Optimizer

initially 1 solution

all solutions in P incomparablestandard bit mutation

with 1 objective: SEMO ≅ (1+1)EA

Do Additional Objectives Make a Problem Harder? 7© Systems Optimization Group ETH Zurich

Overview of the Problem Scenario & Basic Idea

1110

1111

1101 1011 0111

1100 1010 1001 0110 0101 0011

1000 0100 0010 0001

0000

AddFaster:

AddSlower:

Do Additional Objectives Make a Problem Harder? 8© Systems Optimization Group ETH Zurich

1110

1111

1101 1011 0111

1100 1010 1001 0110 0101 0011

1000 0100 0010 0001

0000

Adding ONEMAX

1110

1111

1101 1011 0111

1100 1010 1001 0110 0101 0011

1000 0100 0010 0001

0000

1110

1111

1101 1011 0111

1100 1010 1001 0110 0101 0011

1000 0100 0010 0001

0000

combine

Do Additional Objectives Make a Problem Harder? 9© Systems Optimization Group ETH Zurich

1110

1111

1101 1011 0111

1100 1010 1001 0110 0101 0011

1000 0100 0010 0001

0000

Adding ONEMAX (Proof)

|Population| Initial point :

to reach Initial point :

SEMO produces trade-off solutionsexpected steps

necessary to increase maximal number of ones by one

Pareto-optimal

Do Additional Objectives Make a Problem Harder? 10© Systems Optimization Group ETH Zurich

1110

1111

1101 1011 0111

1100 1010 1001 0110 0101 0011

1000 0100 0010 0001

0000

Adding ZEROMAX

1110

1111

1101 1011 0111

1100 1010 1001 0110 0101 0011

1000 0100 0010 0001

0000

combine1110

1111

1101 1011 0111

1100 1010 1001 0110 0101 0011

1000 0100 0010 0001

0000

Do Additional Objectives Make a Problem Harder? 11© Systems Optimization Group ETH Zurich

Wait a minute…

Results:Added simple problem to a more difficult problem→ combination less complex ( + → )Other perspective: added difficult problem to an easy one→ more complex ( + → )

Question:What happens if we combine two equally complex problems?

In other words:Combination more complex or even less complex?

Do Additional Objectives Make a Problem Harder? 12© Systems Optimization Group ETH Zurich

1110

1111

1101 1011 0111

1100 1010 1001 0110 0101 0011

1000 0100 0010 0001

0000

Combining Objectives: Easier

1110

1111

1101 1011 0111

1100 1010 1001 0110 0101 0011

1000 0100 0010 0001

0000

combine1110

1111

1101 1011 0111

1100 1010 1001 0110 0101 0011

1000 0100 0010 0001

0000

Harder already shown: Laumanns et al. (2002)

Do Additional Objectives Make a Problem Harder? 13© Systems Optimization Group ETH Zurich

Conclusions

General result:gained general understanding of how problem structure changes with

additional objectives (introducing plateaus, deceptive/helping)Introducing incomparable solutions is not always a problemPerformance of EA depends on the objectives chosen

Specific Results:Running time analyses for simple EAs

One and the same plateau function can become harder and easier with an additional objectiveExample, where the combination of two problems as a bi-objective problem is easier than solving the single problems individually

All proofs also for an asymmetric mutation operator

Do Additional Objectives Make a Problem Harder? 14© Systems Optimization Group ETH Zurich

10

100

1000

10000

100000

0 50 100 150 200 250

runt

ime

[gen

erat

ions

]

bitstring length

Making comparable solutions incomparable

modified LOTZ with additional function (iii)2-dimensional modified LOTZ

modified LOTZ with additional function (iv)

More Objectives…

Brockhoff and Zitzler: "Offline and Online Objective Reduction in Evolutionary Multiobjective

Optimization Based on Objective Conflicts",TIK report no. 269, May 2007

www.tik.ee.ethz.ch/sop/