DE-2LS: Differential Evolution with Late-Stage local-search for Unconstrained Single-Objective Numerical Optimization

Résumé technique : DE-2LS pour l'optimisation numérique mono-objectif non contrainte

Énoncé du problème
L'article traite des problèmes d'optimisation numérique mono-objectif (UCOP) non contraints avec des bornes de variables, un cadre courant dans les compétitions IEEE CEC. Le défi central réside dans l'équilibre entre l'exploration globale, l'exploitation tardive et l'efficacité de l'évaluation des fonctions. Plus précisément, bien que les variantes de l'Évolution Différentielle (DE) comme RDEx (DE reconstruite avec branchement biaisé vers l'exploitation) fassent preuve de performances solides, elles peuvent manquer de la précision nécessaire pour « polir » efficacement les solutions entrantes une fois que la recherche pénètre dans un bassin prometteur. Cette limitation est critique sous la métrique d'évaluation U-score, qui évalue conjointement la qualité de la solution finale et la vitesse de convergence. L'objectif est d'améliorer ces deux métriques sans perturber le comportement de recherche évolutive robuste de l'algorithme de base.

Méthodologie
La méthode proposée, DE-2LS, est une amélioration conservatrice du cadre RDEx. Plut lieu de remplacer le moteur évolutif central de RDEx, DE-2LS introduit deux raffinements de phase tardive conçus pour opérer dans un budget fixe d'évaluations de fonctions :

1. Mise à jour lissée du taux de branchement à biais d'exploitation (EB) :
   Dans la phase tardive de la recherche (après avoir consommé 75 % du budget d'évaluation), le mécanisme met à jour la probabilité de sélectionner la branche biaisée vers l'exploitation. Au lieu de réagir brutalement à la performance immédiate de la branche, la règle de mise à jour applique un lissage pondéré (combinaison linéaire du taux précédent et de l'estimation brute actuelle). Cela stabilise la transition vers une exploitation intensive, empêchant la convergence prématurée ou les changements erratiques de stratégie de recherche.

2. Recherche locale par motif de coordonnées gardée (LS) :
   Un module de recherche locale léger est activé uniquement lorsque des conditions spécifiques sont remplies : la recherche est en phase tardive (après 82 % du budget), la meilleure solution globale a stagné pendant un nombre défini de générations, et la limite d'appels de la recherche locale n'a pas été atteinte.

   • Mécanisme : La LS opère sur la meilleure solution globale actuelle en utilisant une approche par motif de coordonnées. Elle explore une direction de coordonnée à la fois avec une taille de pas initiale proportionnelle aux bornes des variables.
   • Stratégie : Elle emploie une stratégie de « premier meilleur trouvé » ; si un meilleur point est trouvé, le centre est immédiatement mis à jour. Si aucun meilleur point n'est trouvé, la taille du pas est divisée par deux.
   • Contraintes : Le processus est strictement conscient du budget, avec un ratio défini d'évaluations allouées par appel et un nombre maximal d'appels. Elle utilise une acceptation basée uniquement sur l'objectif (puisque le problème est non contraint à l'exception des bornes) et réinjecte les solutions améliorées dans la population sans réinitialiser la mémoire d'historique de succès ou la structure de la population.

Contributions clés

• Conception de l'algorithme : La proposition de DE-2LS, qui augmente la base RDEx avec une mise à jour lissée du taux EB et un module de recherche locale gardé et contrôlé par le budget.
• Étude d'ablation : Une analyse d'ablation rigoureuse et par étapes a été menée pour déterminer la configuration optimale. Cela comprenait l'ajustement du timing et des poids du lissage du taux EB, du taux EB initial, de l'échelle d'échantillonnage gaussien pour la branche standard, des paramètres de pression de sélection et des coefficients de la recherche locale (timing, budget et taille de pas).
• Optimisation du U-score : La conception cible explicitement la métrique U-score, visant à améliorer simultanément les composantes de précision (erreur finale) et de vitesse (trajectoire de convergence).

Résultats expérimentaux
Les expériences ont été menées sur 29 fonctions UCOP (D=30) avec un budget de 10 000D évaluations de fonctions, en utilisant 25 essais indépendants par algorithme. Les performances ont été évaluées à l'aide de la procédure de score U par paire.

• Comparaison avec RDEx : DE-2LS a systématiquement surpassé l'original RDEx. Le U-score est passé de 33 602,0 à 37 448,0, représentant une amélioration de 11,45 %. Ce gain a été porté par une amélioration de 17,25 % de la composante de vitesse et de 5,95 % de la composante de précision.
• Comparaison avec les algorithmes compétitifs : Dans une comparaison plus large contre plusieurs algorithmes compétitifs et lauréats de l'IEEE CEC (incluant LSRTDE, BlockEA, mLSHADE-RL, jSO et IEACOP), DE-2LS a atteint le U-score global le plus élevé de 178 966,5. Ce résultat a surpassé le deuxième meilleur algorithme (RDEx) de 3,17 % et la moyenne des autres concurrents d'environ 34,43 %.
• Performance par fonction : DE-2LS a obtenu le meilleur U-score sur 11 des 29 fonctions, soit le compte le plus élevé parmi tous les algorithmes comparés. Il a démontré une force particulière dans la vitesse de convergence, atteignant des niveaux d'erreur compétitifs plus tôt que ses rivaux sur de nombreuses fonctions.

Signification et affirmations
L'article affirme que DE-2LS démontre qu'une stratégie de recherche locale de phase tardive soigneusement conçue peut considérablement améliorer les performances d'un algorithme DE de base robuste sans compromettre ses capacités de recherche globale. Les auteurs soulignent que le principe de conception « ne pas nuire » (do no harm) — préservant le moteur RDEx original tout en ajoutant un mécanisme de polissage léger et conscient du budget — est efficace pour améliorer à la fois la vitesse de convergence et la qualité de l'objectif final. Les résultats suggèrent que le contrôle lissé du taux EB et la recherche locale gardée fournissent un équilibre robuste entre exploration et exploitation, particulièrement sous le cadre d'évaluation U-score qui pénalise une convergence lente. Le code source de DE-2LS est mis à disposition pour soutenir la reproductibilité.