TY - JOUR

T1 - Multiobjectivization by decomposition of scalar cost functions

AU - Handl, Julia

AU - Lovell, Simon C.

AU - Knowles, Joshua

PY - 2008

Y1 - 2008

N2 - The term 'multiobjectivization' refers to the casting of a single-objec-tive optimization problem as a multiobjective one, a transformation that can be achieved by the addition of supplementary objectives or by the decomposition of the original objective function. In this paper, we analyze how multiobjectivization by decomposition changes the fitness landscape of a given problem and affects search. We find that decomposition has only one possible effect: to introduce plateaus of incomparable solutions. Consequently, multiobjective hillclimbers using no archive 'see' a smaller (or at most equal) number of local optima on a transformed problem compared to hillclimbers on the original problem. When archived multiobjective hillclimbers are considered this effect may partly be reversed. Running time analyses conducted on four example functions demonstrate the (positive and negative) influence that both the multiobjectivization itself, and the use vs. non-use of an archive, can have on the performance of simple hillclimbers. In each case an exponential/polynomial divide is revealed. © 2008 Springer-Verlag Berlin Heidelberg.

AB - The term 'multiobjectivization' refers to the casting of a single-objec-tive optimization problem as a multiobjective one, a transformation that can be achieved by the addition of supplementary objectives or by the decomposition of the original objective function. In this paper, we analyze how multiobjectivization by decomposition changes the fitness landscape of a given problem and affects search. We find that decomposition has only one possible effect: to introduce plateaus of incomparable solutions. Consequently, multiobjective hillclimbers using no archive 'see' a smaller (or at most equal) number of local optima on a transformed problem compared to hillclimbers on the original problem. When archived multiobjective hillclimbers are considered this effect may partly be reversed. Running time analyses conducted on four example functions demonstrate the (positive and negative) influence that both the multiobjectivization itself, and the use vs. non-use of an archive, can have on the performance of simple hillclimbers. In each case an exponential/polynomial divide is revealed. © 2008 Springer-Verlag Berlin Heidelberg.

U2 - 10.1007/978-3-540-87700-4_4

DO - 10.1007/978-3-540-87700-4_4

M3 - Article

SN - 0302-9743

VL - 5199

SP - 31

EP - 40

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -