Optimisation des extremums

L’optimisation extrême est inspirée du modèle de Bak-Sneppen de criticité auto-organisé de la co-évolution du domaine de la physique statistique. Le modèle de criticité auto-organisé suggère que certains systèmes dynamiques ont un point critique en tant qu’attracteur, où les systèmes présentent des périodes de mouvement lent ou d’accumulation suivies de courtes périodes d’avalanche ou d’instabilité. Des exemples de tels systèmes comprennent la formation des terres, les tremblements de terre et la dynamique des tas de sable. Le modèle de Bak-Sneppen prend en compte ces dynamiques dans les systèmes de co-évolution et dans le modèle d’équilibre ponctué, qui est décrit comme de longues périodes d’état suivies de courtes périodes d’extinction et de grands changements évolutifs.

La dynamique du système se traduit par l’amélioration constante d’une solution candidate avec des plantages soudains et importants de la qualité de la solution candidate. Ces dynamiques permettent deux phases principales d’activité dans le système: 1) exploiter des solutions de meilleure qualité de manière locale, et 2) échapper à des optima locaux possibles avec un crash de population et explorer l’espace de recherche pour un nouveau domaine de solutions de haute qualité .

L’objectif de la stratégie de traitement de l’information est d’identifier de manière itérative les composants les moins performants d’une solution donnée et de les remplacer ou de les échanger avec d’autres composants. Ceci est réalisé grâce à l’allocation des coûts aux composants de la solution en fonction de leur contribution au coût global de la solution dans le domaine. Une fois les composants évalués, ils peuvent être classés et les composants les plus faibles remplacés ou remplacés par un composant sélectionné au hasard.

La sélection déterministe du pire composant dans la fonction SelectWeakComponent et le remplacement dans la fonction SelectReplacementComponent est un EO classique. Si ces décisions sont probabilistes en utilisant le paramètre τ, on parle alors d’optimisation τ-Extremal.

L’optimisation des extrêmums a été conçue pour les problèmes d’optimisation combinatoire, bien que des variations aient été appliquées à l’optimisation continue des fonctions. La sélection de la pire composante et de la composante de remplacement à chaque itération peut être déterministe ou probabiliste, cette dernière étant appelée optimisation τ -extremal étant donné l’utilisation d’un paramètre τ. La sélection d’une fonction de notation appropriée des composants d’une solution est la partie la plus difficile à appliquer à la technique. Pour l’optimisation τ-Extremal, de faibles valeurs τ (telles que τ dans [1.2; 1.6]) se sont avérées efficaces pour le TSP.