Garanties de temps d'exécution prouvées pour la façon dont le calcule le front de Pareto à partir des solutions des sous-problèmes

L'algorithme évolutif multi-objectifs basé sur la décomposition (MOEA/D) n'optimise pas directement une fonction multi-objectifs donnée f, mais optimise plutôt N + 1 sous-problèmes à objectif unique de f de manière co-évolutive. Il maintient une archive de toutes les solutions non dominées trouvées et la sort comme approximation du front de Pareto. Une fois que le MOEA/D a trouvé tous les optima des sous-problèmes (les g-optima), il peut encore manquer des optima de Pareto de f. L'algorithme est alors chargé de trouver les optima de Pareto restants directement en mutant les g-optima. Dans ce travail, nous analysons pour la première fois comment le MOEA/D avec seulement des opérateurs de mutation standard calcule l'ensemble du front de Pareto du benchmark OneMinMax lorsque les g-optima sont un sous-ensemble strict du front de Pareto. Pour la mutation binaire standard, nous prouvons un temps d'exécution attendu de O (n N n + n^n / (2N) N n). En particulier pour la seconde phase, plus intéressante, lorsque l'algorithme commence avec tous les g-optima, nous prouvons un temps d'exécution attendu de (n^(1/2) (n/N + 1) N 2^-n/N). Ce temps d'exécution est super-polynomial si N = o (n), car cela laisse de grands écarts entre les g-optima, nécessitant des mutations coûteuses pour les couvrir. Pour la mutation de loi de puissance avec un exposant (1, 2), nous prouvons un temps d'exécution attendu de O (n N n + n^n) évaluations de fonctions. Le terme O (n^n) provient de la seconde phase débutant avec tous les g-optima et il est indépendant du nombre de sous-problèmes N. Cela conduit à un énorme gain de temps par rapport à la limite inférieure pour la mutation binaire standard. En général, notre limite globale pour la loi de puissance suggère que le MOEA/D fonctionne le mieux pour N = O (n^-1), ce qui aboutit à une limite de O (n^n). Contrairement à la mutation binaire standard, de plus petites valeurs de N sont meilleures pour la mutation de loi de puissance, car elle est capable de créer facilement des solutions manquantes.