A construction of the minimum volume ellipsoid containing a set of points using BRKGA metaheuristic
DOI:
https://doi.org/10.5540/03.2021.008.01.0339Keywords:
Minimum Volume Ellipsoid, BRKGA, Lõwner-John Ellipsoid, Optimization, Python.Abstract
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.
Downloads
References
Alsabeh, R. A.- and Salhi, A. An Evolutionary Approach to Constructing the Minimum Volume Ellipsoid Containing a Set of Points and the Maximum Volume Ellipsoid Embedded in a Set of Points, Journal of Physics: Conf Series, volume 1530, pages 1-15, 2020. DOI: 10.1088/1742-6596/1530/1/012087.
Gonçalves, J. F. and Resende, M. G. C. Biased random-key genetic algorithms for combinatorial optimization, Journal of Heuristics, volume 17, pages 487-525, 2011. DOI: 10.1007/sl0732-010-9143-1.
Grant, M. and Boyd, S. The CVX Users’ Guide Release 2.2, CVX Research, 2020.
John, F. Extremum problems with inequalities as subsidiary condition, Studies and Essays Presented to R. Courant on his 60th Birthday, Wiley Interscience, New York, pages 187-204, 1948.
Python Software Foundation. The Python Tutorial. [Online]. Available: https://docs.python.Org/3/tutorial/index.html, 2021.
Raposo, A. A. M., Rodrigues, A. B., and Da Silva, M. G. Alocação Ótima de Medidores para a Estimação de Estado Considerando a Reconfiguração da Rede de Distribuição, Anais do XXII Congresso Brasileiro de Automática, João Pessoa, pages 1-8, 2018.
Raposo, A. A. M., Rodrigues, A. B., and Da Silva, M. G. Robust meter placement for state estimation considering distribution network reconfiguration for annual energy loss reduction, Electric Power Systems Research, volume 182, pages 1-9, 2020. DOI: doi.org/10.1016/j.epsr.2020.106233.
Raposo, A. A. M. Reconfiguração e Alocação de Medidores em Redes de Distribuição. Tese de Doutorado, PPGEE/UFMA, 2020.
Sun, P. and Freund, R. M. Computation of Minimum-Volume Covering Ellipsoids, Operations Research, pages 690-706, 2004. DOI: 10.1287/opre. 1040.0115.
