T.P.  "Optimisation par Essaim Particulaire (OEP)"

Fabien Moutarde, centre de Robotique (CAOR)

Principe du TP

Le but de ce TP est d'abord d'illustrer, sur la recherche de maximum(s) de fonctions à 2 variables, le fonctionnement de l'optimisation par essaim particulaire (OEP), et l'influence des divers paramètres. Enfin la capacité de recherche de cet algorithme est illustrée par son application à l'apprentisssage non-supervisé du comportement d'un robot.

Préalables

Pour ce TP, bootez indifféremment sous Windows ou Linux.

Exercice 1 : recherche du maximum d'une fonction de deux variables

Pour démarrer, exécutez le fichier demo-OEP-maxFonc.jar (double-cliquez dessus, ou bien faire java -jar demo-OEP-maxFonc.jar dans un "terminal").

NOTE : sous Linux, si le double-clic sur le fichier jar ne fonctionne pas, il suffit, dans l'explorateur de fichier, de faire clic-droit à la souris sur un fichier .jar, d'aller dans l'onglet "Ouvrir avec", puis d'appuyer sur le bouton "Ajouter", et enfin de mettre à l'endroit prévu la commande "java -jar %s" (ceci définira pour la suite l'action que l'ordinateur effectuera quand on double-clique sur un fichier de type .jar).
        

Une fois le programme démarré, une fenêtre comme ci-dessus à gauche devrait apparaître. Cette fenêtre permet de choisir :
Après avoir choisi les divers paramètres (laissez ceux par défaut pour commencer), cliquez sur le bouton OK en bas pour initialiser l'essaim : une fenêtre comme celle ci-dessus à droite devrait apparaître. On visualise sur celle-ci : la fonction dont on va rechercher le/les maximum(s), et les positions initiales des particules. En cliquant sur le bouton "Commencer", vous pouvez démarrer l'algorithme OEP et visualiser l'évolution des particules de l'essaim.

  1. Vérifiez tout d'abord que si le nombre de voisins est <2 (pas d'informatrice externe) ou bien si le coefficient de "suivisme" vaut 0, alors l'OEP ne démarre pas !!
    En reprenant les équations de l'algo présentées en cours, expliquez pourquoi (et précisez ce que cela indique sur la façon dont les vitesses ont été initialisées).
  2. Vérifiez ensuite, sur les fonctions "Cardinal" et "Rastrigin", la capacité de l'OEP à trouver le maximum global sur ces fonctions pleines de minimas locaux, et ce même avec un faible nombre de particules (N~10)
  3. Constatez ensuite, avec un grand nombre de particules (N~500) sur les fonctions Cosinus et Schaffer, l'aptitude de l'OEP à trouver plusieurs maxima globaux égaux(voire même toute une zone maximale...).
  4. Que se passe-t-il si vous mettez un coefficient d'inertie trop grand (par exemple 1.1) ?
  5. De même, que se passe-t-il si "nostalgie" ou "suivisme" sont trop grands (par exemple 3) ?

Exercice 2 : apprentissage d'un comportement de robot

Le problème à résoudre est exactement le même que celui de l'exercice 3 du TP sur les algorithmes génétiques : trouver une combinaison de valeurs de poids pour un réseaux de neurones totalement connecté qui permette d'obtenir pour un robot virtuel un comportement consistant à explorer l'espace pour y trouver et "manger" toute la "nourriture" (les F, comme Food, disséminés aléatoirement sur la grille), tout en ne consommant pas le "poison" (les P disposés eux-aussi aléatoirement) s'il vient à passer dessus.
     

Pour démarrer l'apprentissage par OEP, exécutez le fichier demo-OEP-animat.jar (double-cliquez dessus, ou bien faire java -jar demo-OEP-animat.jar dans un "terminal").


  1. Créez un essaim initial.
  2. Faire évoluer l'essaim : à chaque itération (ou bien toutes les I itérations, si une valeur I est mise dans frequAffich) sont affichées diverses évaluation de l'essaim : moyenne, minimum, et maximum de l'évaluation des particules de l'essaim courant, et enfin, en dernier, l'évaluation de la meilleure position mémorisée par l'essaim depuis le début des itérations
  3. Poursuivre les itérations jusqu'à obtenir un histBEST > 0.9 
  4. Arrêtez alors l'évolution, et sauvegardez la meilleure position mémorisée.
  5. Testez le comportement de l'animat obtenu en lançant, dans un terminal la commande suivante :
          java -jar demo-OEP-testAnimat.jar bestHistFound-xxiter-blaBla.dat
       où bestHistFound-xxiter-blaBla.dat doit être remplacé par le nom exact du fichier qui a été créé par la sauvegarde.

Dans cette application, vous pouvez aussi  :