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

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

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.


Palavras-chave


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

Texto completo:

PDF (English)

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.




DOI: https://doi.org/10.5540/03.2021.008.01.0339

Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato