Um indicador adaptativo baseado em KKT para avaliação da convergência em otimização multiobjetivo

Thiago Santos; Sebastião Xavier

doi:10.22481/recic.v8i1.18743

Autores

Thiago Santos Universidade Federal de Ouro Preto https://orcid.org/0000-0002-2435-2786
Sebastião Xavier Universidade Federal de Ouro Preto https://orcid.org/0009-0004-2765-0764

DOI:

https://doi.org/10.22481/recic.v8i1.18743

Palavras-chave:

Otimização multiobjetivo, Indicadores de convergência, Condições KKT, Normalização por quantis, Avaliação de desempenho

Resumo

Os indicadores de desempenho orientam a avaliação empírica de algoritmos de otimização multiobjetivo; contudo, as métricas clássicas dependentes de referências perdem eficácia em cenários com muitos objetivos (m ≥ 4). O hipervolume apresenta sobrecarga computacional exponencial, enquanto os indicadores baseados em distância dependem fortemente da uniformidade geométrica das fronteiras de referência externas. Indicadores fundamentados nas condições de otimalidade de Karush–Kuhn–Tucker (KKT) oferecem uma alternativa intrínseca ao quantificar a estacionariedade de primeira ordem diretamente no espaço de decisão. Entretanto, as formulações KKT existentes de tipo entrópico empregam constantes de saturação estáticas que comprimem distribuições populacionais heterogêneas. Apresentamos um indicador KKT adaptativo (Hadap) que substitui limiares fixos pela winsorização baseada em quantis empíricos. A análise teórica confirma que Hadap é limitado ao intervalo [0, 1/e] e estritamente invariante à escala sob reescalonamentos uniformes das funções objetivo. Experimentos sistemáticos com os problemas de referência DTLZ, com m = 12 objetivos, demonstram que o indicador adaptativo preserva a capacidade de discriminação diagnóstica em diferentes regimes de estacionariedade nos quais as métricas convencionais se degeneram.

Downloads

Não há dados estatísticos.

Biografia do Autor

Thiago Santos, Universidade Federal de Ouro Preto

Graduação em Matemática na Universidade Federal de Sergipe em 2005. Mestre em Matemática pela Universidade Federal de Alagoas em 2006. Doutorado em Matemática pela Universidade Federal de Minas Gerais (2012). Professor adjunto na Universidade Federal de Ouro Preto, onde me dedico à pesquisa e ao ensino da Matemática, com especialização em Otimização. Meu trabalho foca principalmente em estratégias evolutivas, otimização multiobjetivo não linear e metodologias inovadoras no ensino de matemática.

Sebastião Xavier, Universidade Federal de Ouro Preto

Licenciado em matemática pela Universidade Federal de Minas Gerais atuou como professor do ensino médio e fundamental em escolas de Belo Horizonte e região metropolitana. Possui Doutorado em Matemática pela Universidade Federal de Minas Gerais com experiência na área de Sistemas Dinâmicos com ênfase em folheações reais. Atualmente é Professor na Universidade Federal de Ouro Preto e tem-se interessado pelo estudo de Otimização trabalhando com os seguintes temas: otimização multiobjetivo e estrategias evolutivas.

Referências

Audet, C., Bigeon, J., Cartier, D., Le Digabel, S., & Salomon, L. (2021). Performance indicators in multiobjective optimization. European Journal of Operational Research, 292(2), 397–422. https://doi.org/10.1016/j.ejor.2020.11.016

Li, H., Deb, K., Zhang, Q., & Suganthan, P. N. (2019). Comparison between MOEA/D and NSGA-III on many-objective optimization problems. IEEE Transactions on Evolutionary Computation, 23(3), 394–409. https://doi.org/10.1109/TEVC.2018.2865459

Wang, R., Purshouse, R. C., & Fleming, P. J. (2016). Preference-inspired coevolutionary algorithms for many-objective optimization. IEEE Transactions on Evolutionary Computation, 20(3), 373–386. https://doi.org/10.1109/TEVC.2015.2450984

Beume, N., & Naujoks, B. (2016). On the complexity of computing the hypervolume indicator. IEEE Transactions on Evolutionary Computation, 20(3), 387–402. https://doi.org/10.1109/TEVC.2015.2458973

Guerreiro, A. P., Fonseca, C. M., López-Ibáñez, M., Paquete, L., & Vahrenhold, J. (2021). The Hypervolume Indicator: Computational problems and algorithms. ACM Computing Surveys, 54(6). https://doi.org/10.1145/3453474

Ishibuchi, H., Masuda, H., & Nojima, Y. (2016). Sensitivity of performance evaluation results by inverted generational distance to reference points. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC) (pp. 1107–1114). https://doi.org/10.1109/CEC.2016.7743912

Ishibuchi, H., Masuda, H., Tanigaki, Y., & Nojima, Y. (2018). Difficulty of specifying reference points for performance evaluation in many-objective optimization. IEEE Transactions on Evolutionary Computation, 22(4), 626–641. https://doi.org/10.1109/TEVC.2017.2754274

Abouhawwash, M., & Deb, K. (2016). Karush–Kuhn–Tucker proximity measure for multi-objective optimization. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) (pp. 525–532). https://doi.org/10.1145/2908812.2908893

Deb, K., Abouhawwash, M., & Seada, H. (2017). A computationally fast convergence measure for multi-objective optimization. IEEE Transactions on Emerging Topics in Computational Intelligence, 1(4), 280–293. https://doi.org/10.1109/TETCI.2017.2719707

Eichfelder, G., Martin, A., & Otto, A. (2021). Proximity measures based on KKT points for constrained multi-objective optimization. Journal of Global Optimization, 79, 593–617. https://doi.org/10.1007/s10898-020-00971-3

Abouhawwash, M., Jameel, M. A., & Deb, K. (2020). A smooth proximity measure for optimality in multi-objective optimization. Computers & Operations Research, 117, 104900. https://doi.org/10.1016/j.cor.2020.104900

Jameel, M. A., & Abouhawwash, M. (2024). A new proximity metric based on optimality conditions for single and multi-objective optimization: Method and validation. Expert Systems with Applications, 241, 122677. https://doi.org/10.1016/j.eswa.2023.122677

Zhang, Q., Li, H., & Zhou, A. (2022). Indicator-based performance analysis for many-objective optimization. Swarm and Evolutionary Computation, 65, 101018. https://doi.org/10.1016/j.swevo.2021.101018

Li, Y., Wang, H., & Jin, Y. (2023). Robust performance assessment in evolutionary multi-objective optimization. Information Sciences, 620, 1–18. https://doi.org/10.1016/j.ins.2022.12.021

Santos, T., & Xavier, S. (2018). A convergence indicator for multi-objective optimisation algorithms. TEMA – Tendências em Matemática Aplicada e Computacional, 19(3), 347–366. https://doi.org/10.5540/tema.2018.019.03.0347

Deb, K., & Jain, H. (2013). An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints. IEEE Transactions on Evolutionary Computation, 18(4), 577–601. https://doi.org/10.1109/TEVC.2013.2261531

Tian, Y., Cheng, R., Zhang, X., & Jin, Y. (2017). PlatEMO: A MATLAB platform for evolutionary multi-objective optimization. IEEE Computational Intelligence Magazine, 12(4), 73–87. https://doi.org/10.1109/MCI.2017.2704842

Hua, Y., Liu, Q., & Hao, K. (2024). Adaptive normal vector guided evolutionary multi- and many-objective optimization. Complex & Intelligent Systems, 10, 3709–3726. https://doi.org/10.1007/s40747-024-01353-y

Chen, J., Wang, Y., Shao, Z., Zeng, H., & Zhao, S. (2025). Dual-population cooperative correlation evolutionary algorithm for constrained multi-objective optimization. Mathematics, 13(9), 1441. https://doi.org/10.3390/math13091441