A construction of the minimum volume ellipsoid containing a set of points using BRKGA metaheuristic

Autores

  • Antonio A. M. Raposo
  • Valeska Martins de Souza
  • Luís Roberto A. G. Filho

DOI:

https://doi.org/10.5540/03.2021.008.01.0339

Palavras-chave:

Minimum Volume Ellipsoid, BRKGA, Lõwner-John Ellipsoid, Optimization, Python.

Resumo

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

Não há dados estatísticos.

Biografia do Autor

Antonio A. M. Raposo

Federal Institute of Education, Science and Technology of São Paulo (IFSP), Tupã, SP, Brazil
São Paulo State University (UNESP), School of Sciences and Engineering, Tupã, SP, Brazil

Valeska Martins de Souza

Federal University of Maranhão (UFMA), Mathematics Department, São Luís, MA, Brazil

Luís Roberto A. G. Filho

São Paulo State University (UNESP), School of Sciences and Engineering, Tupã, SP, Brazil

Referências

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.

Downloads

Publicado

2021-12-20

Edição

Seção

Trabalhos Completos