Evolutionary algorithms and multi-objectivization for the travelling salesman problem

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.