Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Evolutionary algorithms and multi-objectivization for the travelling salesman problem

: Jähne, M.; Li, X.; Branke, J.


Association for Computing Machinery -ACM-:
GECCO 2009, Genetic and Evolutionary Computation Conference : Montreal, Canada, July 8-12, 2009
New York: ACM, 2009
ISBN: 978-1-60558-325-9
Genetic and Evolutionary Computation Conference (GECCO) <11, 2009, Montreal>
Conference Paper
Fraunhofer IAIS ()
multi-objective optimization; multi-objectivization; Travelling Salesman Problem; genetic algorithm

This paper studies the multi-objectivization of single-ob- jective optimization problems (SOOP) using evolutionary multi-objective algorithms (EMOAs). In contrast to the single-objective case, diversity can be introduced by the multi-objective view of the algorithm and the dynamic use of objectives. Using the travelling salesman problem as an example we illustrate that two basic approaches, a) the ad- dition of new objectives to the existing problem and b) the decomposition of the primary objective into sub-objectives, can improve performance compared to a single-objective ge- netic algorithm when objectives are used dynamically. Based on decomposition we propose the concept\Multi-Objectiviza- tion via Segmentation" (MOS), at which the original prob- lem is reassembled. Experiments reveal that this new strat- egy clearly outperforms both the traditional genetic algo- rithm (GA) and the algorithms based on existing multi- objective approaches even without changing objectives.