Une première analyse de performance de PAES-25 : une variante améliorée de la stratégie d'évolution archivées de Pareto

Cet article présente une première analyse mathématique du temps d'exécution de PAES-25, une version améliorée de la stratégie d'évolution archivées de Pareto (PAES) originale provenant de l'étude des problèmes de télécommunication il y a deux décennies pour comprendre la dynamique de la recherche locale des MOEAs sur des paysages de fitness à nombreux objectifs. Nous dérivons des limites serrées des temps d'exécution attendus de PAES-25 avec mutation sur un bit sur m-LOTZ jusqu'à ce que l'ensemble du front de Pareto soit trouvé : Θ (n³) itérations si m=2, Θ (n³ ² (n) ) itérations si m=4 et Θ (n (2n/m) ^m/2 (n/m) ) itérations si m>4 où n est la taille du problème et m le nombre d'objectifs. À notre connaissance, ce sont les premières limites serrées des temps d'exécution connues pour un MOEA surpassant la meilleure limite supérieure connue de O (n^m+1) pour (G) SEMO sur m-LOTZ lorsque m est au moins 4. Nous montrons également que les archivistes, tels que l'Archiviste de grille adaptatif (AGA), l'Archiviste de volume hyper (HVA) ou l'Archiviste de grille multi-niveau (MGA), aident à distribuer l'ensemble de solutions à travers le front de Pareto de manière efficace. Nous montrons aussi que PAES-25 avec mutation standard optimise le benchmark bi-objectif LOTZ en O (n⁴) itérations attendues, et nous discutons de ses limitations sur d'autres benchmarks tels que OMM ou COCZ.