Edge-Rotated Cone Orders in Multi-objective Evolutionary Algorithms for Improved Convergence and Preference Articulation

摘要

The Pareto dominance relation is a special case of a cone order. Cone orders and the Pareto order are translation invariant and also multiplication invariant by any positive real. Employment of more general cone orders instead of the Pareto order gives rise to interesting exploration opportunities for algorithm design. In this paper, the standard Pareto dominance relation has been extended to cone dominance with a pointed convex obtuse cone, a superset of the Pareto dominance cone, i.e., the non-negative orthant, by rotating the edges of the Pareto order cone. The basic idea is in line with earlier work on cone-orders in multicriteria decision making and here, in particular, the cone-order is used (1) to increase solutions’ dominance area and hence improve the convergence speed of the algorithm and (2) to formulate trade-off constraints. The minima of the obtuse cone order are also Pareto optimal. However, not all minima of the Pareto order are also minima of the obtuse cone order. Therefore we use the edge-rotated cone in an alternating manner with the standard Pareto cone to guarantee coverage of the entire Pareto front. The edge-rotated cones have been integrated in several state-of-the-art multi-objective evolutionary algorithms (MOEAs) and proven to be able to improve the performance of MOEAs on multi-objective optimization problems with the linear, concave, convex and disconnected Pareto front. Furthermore, when the edges of the cone are rotated by different angles, the algorithm obtains solution sets located in different areas of the Pareto front. This behavior can be used to take the preference of the targeted region on the Pareto front into the algorithm. In particular, by using obtuse cones, regions where trade-off is very unbalanced can be discarded. This is quantified by showing a relationship between the angle and the trade-off rate corresponding to this angle.