An approximate MIP-DoM calculation for multi-objective optimization using affinity propagation clustering algorithm
Abstract
Dominance move (DoM) is a quality indicator that compares two solution sets in a Pareto-optimal sense. The main issue related to DoM is its computational expense. A recent paper proposed a mixed-integer programming (MIP) approach for computing DoM that exhibited a computational complexity that is linear to the number of objectives and polynomial to the number of solutions. Even with this property, considering practical situations, the MIP-DoM calculation on some problems may take many hours. This paper presents an approximation method to deal with the problem using a cluster-based and divide-and-conquer strategy. Some experiments are tested, showing that the cluster based-algorithm is computationally much faster and makes a small percentage error from the original DoM value.
Authors: Claudio Lucio do Val Lopes, Flávio Vinícius Cruzeiro Martins, Elizabeth Fialho Wanner, Kalyanmoy Deb
Published in: Genetic and Evolutionary Computation Conference Companion (GECCO Companion) (2021)