Optimisation de fonctions à haut coûtUlysse Côté Allard, GabrielDubé, Richard Khoury, Luc
Lamontagne, Benoit Gosselin etFrançois Laviolette.

Time Adaptive dual
particle swarm optimization

ButMinimisation globale d’une fonction quelconque.
Tour d’horizon des algos PSO et présentation de celui que nous avons développé.

Particle Swarm Optimization
Méthode d’optimisation basée sur le mouvement des groupes d’oiseaux/poissons.
Proposé par Kennedy en 1995.

Terminologie
Fonction d’évaluation : La fonction à minimiser. Elle prend un vecteur de D dimensions
Position : Point dans l’espace de recherche. C’est l’entrée de la fonction d’évaluation.
Aptitude (fitness) : Résultat de la fonction d’évaluation en un point
Maison: Meilleure position trouvée par une particule (fitness la plus basse)
Particule : Un ensemble comportant la position actuelle, la fitness actuelle, la maison
et la meilleure fitness trouvée ainsi qu’une vélocité.
Population : Regroupement de particules
Maison du « rich kid »: Meilleure position trouvée par l’ensemble de la swarm

Exemplar: Une position vers laquelle une créature se dirige.

Particle Swarm Optimization
Générer N particules avec des positions et vélocité aléatoires. Évaluer leur fitness.
À chaque itération: Calculer la nouvelle vélocité:

Vn+1 = c*Vn + confiance_personnelle*rand()*Maison + confiance_swarm*rand()*Rich_Kid_maisonc, confiance_personnelle, confiance_swarm: des nombres réels.
Rand() un nombre aléatoire pigé d’une distribution uniforme entre 0 et 1.

Mettre à jour la position de la créature avec la vélocité.

Topologie(Comment les particules communiquent)Global: Toutes les particules se voient et se parlent.

Local: Une particule ne peut voir que son voisin d’index de droite, de gauche et elle-même
dans la population. (Topologie anneau)
Global (-G): Convergence plus rapide. Plus grand risque d’être bloqué dans un minimum
local.
Local (-L): Convergence plus lente. Reste moins facilement bloqué dans un minimum local.

En pratique: Impossible de savoir d’avance quelle topologie est meilleure.

W-PSOExactement comme le PSO, mais remplace c par W, un réel, qui diminue linéairement
avec le temps.
Compromis Exploration/Exploitation.
En pratique: mieux que PSO.

Problèmes avec PSO/w-pso
Utilisation de deux exemplars (maison et maison du « rich kid »)Deux problèmes:1) Oscillation
2) Deux pas en avant, un pas en arrière.

Comprehensive learning particle swarm
optimization (CLPSO)
But: enlever les problèmes associés aux deux exemplars.

CLPSO
Nouvelle équation pour la vélocité:

Vn+1 = w*Vn + confiance*rand()*clpso_exemplar
Confiance: Un nombre réel constantClpso_exemplar: Un vecteur position.

CLPSO-Clpso_exemplar n’est pas très informatif.
-Pas de topographie locale explicite. L’exemplar fait une émulation d’une topographielocale.

OLPSOMême idée que CLPSO. Mais la conception de l’exemplar se fait de façon « intelligente » en utilisantl’orthogonal learning (OL).
Considérer la maison (1) de la créature et la maison du « rich kid » (2) de la population.
Trouver pour chaque dimension si la particule se dirige vers (1) ou (2).
Approche exhaustive: Tester toutes les combinaisons (2^D FE).
L’OL permet d’estimer pour chaque dimension la valeur parmis ces deux positions qui est la plus
prometteuse (2D FE).
Avantage: Exemplar beaucoup plus intelligent et meilleure convergence.
Désavantage: Calcul exemplar coȗteux.

OLPSO
Avantages: Exemplar beaucoup plus intelligent et meilleure convergence.
Désavantages: Calcul exemplar coûteux. Qualité de la solution finale dépends de la topologie.

Time adaptive dual
particle swarm optimization(TAD-PSO)

Contribution

TAD-PSO (Contribution)
Idée: Séparer l’exploration et l’exploitation en deux populations (PopulationPrincipale (exploration) et Population Auxiliaire (exploitation) respectivement).
Par rapport à OLPSO: N’est plus dépendant à l’hyperparamètre de la topologie(comme CLPSO).

Par rapport à CLPSO: Exemplar calculé de façon beaucoup plus intelligente.

Main population
Topologie globale.

Utilise OLPSO, mais l’exemplar est calculé entre la maison et l’exemplar de CLPSO.
Calculer un nouvel exemplar à toutes les N générations sans amélioration.
Favorise l’exploration. Utilise l’information de l’ensemble de la population.

Main population
Calcul exemplar = 2*D.

Explosion du nombre d’évaluations lorsque la population converge.
Désactivation des particules pendant l’optimisation (favoriser l’exploitation).

Auxiliary population
Utilise un algorithme nommé PSO-TVAC.

Comme W-PSO:
Vn+1 = w*Vn + confiance_personnelle*rand()*Maison + confiance_swarm*rand()*meilleure_maison_swarm

Mais confiance_personnelle diminue dans le temps et confiance swarm augmente dans le temps.
Algorithme qui converge extrêmement rapidement (presque pas d’exploration) et est mauvais lorsqu’utilisé
seul.

Topologie meta-globale (connexion globale sur sa population et sur la main population)

Benchmarks

10 dimensions

30 Dimensions

100 Dimensions

Test statistiqueFriedman -> Post Hoc (Holm).
Changement de dimensions -> Change benchmark.

Giant Squid Swarm Optimization

Optimisation de fonctions à hautcoûts (Work in progress)

Fonctions à haut coûts
Une fonction qui nécessite beaucoup de ressources à évaluer (temps, argent, éthique).

Algorithmes d’optimisation normaux mal adaptés (e.g. descente de gradient,Algorithmes évolutionnaires, PSO).
Alternative: Grid Search, Random Search, « Expert » Guessing

Random SearchBayésien Optimisation

State of the artProcessus Gaussien

17-2-2

Fonctions à haut coûts (State of the art)
Optimisation bayésienne (e.g. Spearmint, SigOpt)

Avec un peu de chance…
Giant Squid Swarm Optimization (Notre Algorithme)

Philosophie
Comme la fonction est inconnue. On utilise un régresseur pour l’approximer (ProcessusGaussien).
Processus Gaussien:
On traite la fonction comme une fonction aléatoire et on y appose un aprioris. (PriorGaussien).
On évalue un point. On update l’aprioris qui devient un postériore de la fonction. Onutilise la distribution à postériori pour créer une fonction d’acquisition qui permetd’évaluer le prochain point.
Avantage: Mesure d’incertitude sur les prédictions, calcul de gradient facile.
Désavantage: Hypothèses forte. Mesure d’incertitude « weird »Optimisation bayésienne
1. Représenter la fonction inconnue par un processus Gaussien.
2. Fonction de fitness (e.g. Expected Improvement, Upper Confidence Bound, Improvement Probabilty)
3. Descente de gradient pour trouver le minimum.

4. Évaluation du point
5. Ré-entraînement du GP
6. Retour #3 jusqu’à nombre max itérations.

SigOpt
Une librairie pour l’optimisation bayésien comme Spearmint.
Compare favorablement à Spearmint. Entre autre, meilleur sur la fonction de Branin(nous y viendrons).

(A stratified analysis of Bayesian Optimization Methods. Dwancker et al.)Résultats avant présentation algorithmes.

Branin-Hoo2 dimensions-5.0 <= x <= 10.0
0.0 <= y <= 15.0
3 Minimum globaux = 0.397887

Schwefel

X entre -500 et 500,minimisation, D-dimensions
1 Minimum global = 0.0

0Giant Squid Swarm

Pseudo-Code
1. Initialisation: Générer N positions aléatoires. K-means avec K = 2. Évaluer les centres trouver.
2. Déterminer exploration/exploitation. Construire le régresseur approprié avec tout les points
réellement évalué.
3. Initialiser TAD-PSO pour trouver le minimum de la régression.
4. Évalué le minimum trouvé par TAD-PSO et l’évalué avec la fonction à haut coût.
5. Retour à #2 jusqu’au nombre max d’itérations atteint.

Nerf de la guerre
Exploitation

Exploration

But: Trouver un point à évaluer qui
permettra au régresseur de mieuxévaluer la function

But: Trouver une nouvelle position sur lafonction à haut coût qui soit meilleur quecelle trouvé jusqu’à maintenant

Exploitation
Observation. Le régresseur est à son plus fiable proche des points déjà évalués.
Idée: Créer N TAD-PSO initialisé autour des meilleurs points trouvé et de X autres
points aléatoirement choisit.
De plus, restreindre l’aire de recherche pour avoir une certaine assurance du point
qu’on évaluera avec la fonction à haut coût.

Exploitation (work in progress++)
Calcul aire de recherche:
1. Fixe une variance maximal.
2. Trouver le point réellement évalué le plus proche de notre point de départ (qui est lui aussi un point
réellement évalué).
3. Tracer un segment L entre les deux points.
4. Utiliser le régresseur pour calculer la variance à la moitié entre les deux points.

5. Si variance < variance maximal: éloigner le point
Sinon: rapprocher le point.

Exploration
Aire de recherche: L’aire complete de la function à optimiser.

Augmenter le nombre d’évaluations sur la fonction d’approximation.
Utiliser un régresseur beaucoup plus « smooth » (changer noyau/algorithme régression).

Questions ?