Este documento presenta un primer análisis matemático del tiempo de ejecución del PAES-25, una versión mejorada de la estrategia de evolución archivada de Pareto (PAES) original, surgida del estudio de problemas de telecomunicaciones hace más de dos décadas para comprender la dinámica de búsqueda local de MOEAs en paisajes de aptitud de muchos objetivos. Derivamos límites estrictos de tiempo de ejecución esperado del PAES-25 con mutación de un bit sobre m-LOTZ hasta que se encuentra todo el frente de Pareto: Θ(n³) iteraciones si m=2, Θ(n³²(n)) iteraciones si m=4 y Θ(n(2n/m)^(m/2)(n/m)) iteraciones si m>4 donde n es el tamaño del problema y m el número de objetivos. Hasta donde sabemos, estos son los primeros límites de tiempo de ejecución estrictos conocidos para un MOEA que supera el mejor límite superior conocido de O(n^(m+1)) para (G) SEMO en m-LOTZ cuando m es al menos 4. También mostramos que los archivadores, como el Archivador de Rejilla Adaptativa (AGA), el Archivador de Hipervolumen (HVA) o el Archivador de Rejilla Multinivel (MGA), ayudan a distribuir el conjunto de soluciones de manera eficiente a lo largo del frente de Pareto de m-LOTZ. También mostramos que el PAES-25 con mutación de bits estándar optimiza el benchmark bi-objetivo LOTZ en un tiempo de ejecución esperado de O(n⁴) iteraciones, y discutimos sus limitaciones en otros benchmarks como OMM o COCZ.
Andre Opris (Viernes) estudió esta cuestión.