Algorithms for finding maximum diversity of design variables in multi-objective optimization

Abstract

This paper considers the problem of finding architectures with sufficient multi-objective Pareto optimality and maximum diversity of their design-variable values. This problem has been exclusively addressed to date by Evolutionary Algorithms, which are known to be powerful, and yet, the optimality of their solutions cannot be guaranteed. This paper defines two somewhat dual Maximal Design Diversity (MDD) problems, namely, (1) Primal p-MDD: maximizing a design-variable diversity metric between parchitectures given a margin for compromising Pareto optimality, and (2) Dual p-MDD: minimizing the compromise of Pareto optimality of parchitectures given a lower bound for design-variable diversity. Greedy algorithms for computing both Primal and Dual p-MDD are presented. For the Primal p-MDD the proposed greedy algorithm is proven to be a 2-approximation of the optimal algorithm and an upper bound for the optimality violation is computed, with respect to the efficient frontier in the objective space. For the Dual p-MDD the optimality violation of the proposed greedy algorithm is proven to be at least as good as that of the optimal algorithm when the lower bound on the distance between the solutions in the design-variable space is doubled. Finally, a real-world mixed-integer non-linear programming model with two objectives, dozens of variables and hundreds of constraints is considered as the main use case, taken from the domain of aircraft-engine design. The results validate the fidelity of the algorithm. © 2012 United Technologies Corporation and Elsevier B.V. All rights reserved.