For a copy of this paper, either
Abstract
This paper addresses global convexity in multiobjective combinatorial
optimization: a phenomenon that has previously been studied and shown to exist i
n a number of single objective combinatorial problems. Global convexity can impl
y that local optima are concentrated in a very small region of the solution spac
e when distance is measured according to the topology of a neighborhood function
. Global convexity is therefore not an absolute characteristic of an optimizatio
n problem, but refers of the topology that has been induced in the solution spac
e. Local search based heuristics can exploit global convexity by choosing neighb
orhood functions that tend to concentrate the search in these regions and it has
been claimed that global convexity plays an important role in the recent succes
ses of many metaheuristics.
This report generalizes and extends those investigations for the case where mult
iple objectives exist by analyzing several points where global convexity might p
lay a role. This analysis builds on generating local optima for well known scala
rizing functions, covering the entire set of weights. We study the heuristic con
centration of local optima, the distance between local optima for different weig
hts over the non-dominated frontier and the stability of local optima for small
weight variations. If global convexity can be established over local areas of th
e non-dominated frontier, it must also be exploitable in new metaheuristics for
MOCO optimization.
We consider the 2-OPT neighborhood function on a three objective traveling sales
man problem and use both the weighted sums program and the augmented Tchebycheff
program. The results indicate that there indeed exists global convexity and for
esee the development of new local search heuristics for approximating the non-do
minated frontier in MOCO.
Last
modified June 04, 1998