Multi-objectivization in Evolutionary Algorithms

Multi-objectivization is the process of reformulating a single-objective problem into a multi-objective problem and solving it with a multi-objective method in order to provide a solution to the original single-objective problem. This work investigates Evolutionary Algorithms (EAs) in both a general categorical sense and as they are applied to multi-objectivization. A diversity classification framework for EAs is proposed. Furthermore, multi-objectivization techniques are examined. Through study of an abstract problem, job-shop scheduling problems, and the Traveling Salesman Problem, principles governing the design decisions for multi-objectivization are identified. Two ways in which multi-objectivization creates beneficial search results are theorized. Prevalent multi-objectivization techniques are compared both analytically and through these experiments. A third, more general version of the studied techniques is proposed with results showing robust performance across a variety of computational budgets.