An analysis of decomposition approaches in multi-objectivization via segmentation


Abstract

Multi-objectivization via Segmentation (MOS) has been shown to give improved results over other previous multi-objectivization approaches. This paper explores the mechanisms that make different segmentations in MOS successful in the context of the Traveling Salesman Problem (TSP). A variety of new segmentation methods are analyzed and theories regarding their performance are presented. Spatial segmentation methods are compared with other adaptive and static decomposition methods. Insight into why previous adaptive methods performed well is provided. New decomposition methods are proposed and several of these methods are shown to attain better performance than previously known methods of decomposition. The convergence of various degrees of multi-objectivization is examined leading to a new, more general segmentation algorithm, Multi-Objectivization via Progressive Segmentation (MOPS). MOPS combines the single-objective genetic algorithm with multi-objectivization in a general form. In a given run MOPS can progress from a more traditional single objective method to a strong multi-objectivization method. MOPS attempts to improve the ratio of fitness improvements to fitness decrements, signal-to-noise ratio (SNR), over the course of an evolutionary optimization based on the principle that often fitness improvements are generally easier to find early in the run rather than late in the run. It is shown that MOPS provides robust performance across a variety of problem instances and different computational budgets.