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.