A construction of the minimum volume ellipsoid containing a set of points using BRKGA metaheuristic
Antonio Adolpho Martins Raposo, Valeska Martins de Souza, Luís Roberto Almeida Gabriel Filho · Proceeding Series of the Brazilian Society of Computational and Applied Mathematics · 2021
The problem of obtaining a Minimum Volume Enclosing Ellipsoid (MVEE) of a given point set C = {#i,..., xn} Ç Rn is found in several practical applications. This paper proposes an alternative methodology to build these ellipsoids of minimum volume through a metaheuristic based on the Biased Random-Keys Genetic Algorithm (BRKGA) in order to reduce the computational cost in solving n-dimensional MVEE problems. The formulation was implemented in Python and compared with the CVX package implemented in MATLAB for 10 two-dimensional instances. The results showed that BRKGA generated solutions with a high levei of accuracy and low computational cost.