[Plan du site] Vous êtes ici --- > Accueil > Projets > En Cours > Thèse Paris 12

Thèse à l'Université de Paris 12

Présentation

Cette thèse a été débutée en Septembre 2008 en parallèle de mon poste d'enseignant à l'EISTI. Mon maître de thèse : Patrick SIARRY, est enseignant-chercheur à l'université de Paris 12 (Val de Marne) et je suis encadré par Rachid CHELOUAH, responsable du département informatique de l'EISTI. Le sujet actuel de la thèse est: "Développement de Métaheuristiques pour le traitement de l'image".
Dans un premier temps, nous allons développer un algorithme hybride entre l'OEP et un algorithme à mémoire adaptative type algorithme Tabou.

Bibliographie

Fichier BibTeX

Première Partie : Recalage d'images et Méthodes d'optimisation

Cette partie visait à faire une recherche introductive sur les différentes méthodes d'optimisation existantes. Dans un second temps, les applications de la thèse étant dans le domaine de l'image et notamment du recalage d'images issues de données médicales, une recherche bibliographique sur le recalage d'images était très importante.
De plus, une application possible en génomique est envisageable. En effet, un laboratoire travaillant sur ce sujet recherche un algorithme performant pour leurs recherches. Ainsi, une bibliographie rapide sur les publications du laboratoire a été faite.
Voici un papier récapitulatif de cette première recherche bibliographique: Bibliographie n°1.

Liste des papiers de références (téléchargement possible) :

Papiers à approfondir :

Commentaire de Maurice Clerc sur l'article Yin08 de Cyber Swarm Algorithms

Liste des papiers de références sur le domaine de la Génomique (téléchargement possible) :

Seconde Partie : Optimisation par Essaim Particulaire, Mémoire Adaptative, Recherche Tabou.

Cette partie entre dans le cadre d'une première publication. Le but étant de mettre au point une hybridation entre la méthode OEP très efficace dans le domaine continu avec un algorithme à mémoire adaptative telle que la recherche tabou, très efficace dans le domaine discret. En voici un papier récapitulatif : Bibliographie n°2.

Liste des papiers de références :

Hybridation PSO - Tabu :

Hybridation PSO - Memory Adaptive Algorithms

PSO Dynamic

Parallélisation :

Systèmes Multi-Agents :

"Simulation Optimization" et "Dynamic Data Mining" :

Fonctions de Tests :

Autres Papiers :

Troisième Partie : Réalisation d'une application de Test d'Heuristiques : HeurisTest.

Cette partie est dans le prolongement de la précédente. En effet, le but ici est de réaliser une application en Java permettant tout d'abord de tester les Heuristiques existantes sur des problèmes connus (tels que ceux présentés lors de la conférence CEC 2005). Dans un second temps, cette application nous permettra de tester nos nouvelles heuristiques et de les comparer aux heuristiques existantes;

Pour Télécharger le .jar exécutable cliquez ici.

Test de la méthode Standard PSO :

Pour tester cette méthode, j'ai récupérer le code source développé par M. Clerc et intitulé Standard PSO 2007. Je l'ai adapté en langage Java sur ma plateforme de simulation et j'ai effectué tous les tests décrit dans CEC05.
J'obtiens les tableaux de résultats suivant: Tableaux Format Excel ou Tableaux Format OpenOffice L'ensemble des courbes de convergence et des fichiers contenant les coordonnées des points de ces courbes est disponible ici : Courbes de Convergence.
Voici un résumé de ce test ainsi que des résultats obtenus et une discussion.

Autres Heuristiques :

Vous pouvez également télécharger les codes Sources des différentes heuristiques de la plateforme (en Java) :

Testez Vos Propres Heuristiques :

Si vous voulez tester votre Heuristique sur la plateforme c'est très simple.
En effet, celle-ci est très modulaire, j'ai ainsi réalisé un "loader" permettant d'ajouter dynamiquement vos heuristiques à la plateforme pour pouvoir les tester (File > Load Heuristic). Il est possible de charger des fichiers .class déjà compilés ou bien directement le fichier source .java qui sera automatiquement compilé par la plateforme (si le jdk de Java est installé sur la machine). Pour que le chargement fonctionne, le .class ou le .java doit être placé dans l'arborescence suivante : MetaHeuristic/MyHeuristic/

Il suffit donc de créer un fichier source, qu'il faudra nommer comme votre classe et comme le package la contenant : MyHeuristic.java héritant de la classe MetaHeuristic.Heuristic déjà écrite.
Il faut également créer un fichier .htp contenant les paramètres de votre application (que vous pourrez ensuite modifier via l'interface graphique). Ce fichier doit également porter le nom de votre Heuristique : MyHeuristic.htp et doit être stocké dans le même dossier que le fichier .java.

Voilà! Il ne vous reste plus qu'à écrire votre algorithme dans le fichier MyHeuristic.java Vous pouvez éventuellement utiliser les objets suivants :

De plus, la fonction :

double calculateFitness(double[] solution);

permet de récupérer la valeur de la fonction objectif pour une solution donnée. Le vecteur solution devant être de taille n = Problem.dimension

La classe MyHeuristic donnée en exemple est fournit ici. Elle est très commentée afin de comprendre parfaitement son fonctionnement. Vous pouvez également vous inspirer des Heuristiques NelderMead, StandardPSO, TabuSearch, CUS et EUS déjà écrites dont le code est fournit plus haut.
Si vous trouvez des algorithmes performants, ou bien implémentez d'autres algorithmes déjà existants, n'hésitez pas à me les soumettre par mail. Après test, je pourrais les ajouter à la plateforme de base, ce qui permettra d'avoir encore un plus grand benchmark d'heuristiques !

Quatrième Partie : Algorithme d'hybridation d'heuristiques.

J'ai ensuite travailler sur différentes heuristiques existantes : PSO, Nelder-Mead, GA, ... Et j'ai implémenté une heuristique très simple : CUS. Je travaillais en Dimension 10 sur le benchmark de CEC'05, et j'ai constaté que ces 4 heuristiques obtenais de bons résultats en moyenne sur une grande partie des fonctions de test. J'ai donc tenter de les hybrider, sachant que la plupart de leurs paramètres pouvaient être fixés. J'ai donc créer un algorithme d'hybridation d'heuristiques : Hybridizem. Cet algorithme peut en théorie hybrider n'importe quelles heuristiques ensembles. Il crée un jeu de paramètre de probabilité sur chaque algorithme. On a une seule solution sur laquelle travaillent chaque heuristiques. A chaque itération, une heuristique est choisie avec une probabilité définie par son paramètre compris entre [0..1]. A chaque itération, en fonction de la réussite de l'heuristique, on met à jour cette probabilité. Cette algorithme fonctionnait en partie, la mise à jour des probabilités ne fonctionnant pas pour une partie des fonctions.

Quatrième Partie : Présentation d'un poster pour la conférence ITT'09 à Paris (France).

Ce poster a été présenté à l'occasion de la conférence sur les transports qui s'est tenue à l'ENSTA ParisTech du 26 au 29 Octobre 2009. Ce poster présentait ma plateforme de tests d'heuristique : HeurisTest.

Cinquième Partie : Publication dans les proceedings de la conférence ISDA'09 à Pise (Italie).

Cette conférence porte sur les méthodes d'optimisation appliquées aux problèmes à grande dimensionnalité. Le benchmark proposé contient 11 fonctions de tests. Le protocole expérimental proposait de tester notre méthode sur ces 11 fonctions pour les dimensions 50, 100, 200 et 500. J'ai remarqué que l'algorithme CUS que j'avais développé fonctionnait très bien en hautes dimensions, car basé sur des algorithmes de Line Search. J'ai ainsi proposé 2 nouveaux algorithmes : CUS et EUS (version améliorée de CUS) issus de la Line Search. Les résultats obtenus sont très satisfaisant, les algorithmes étant très robustes vis à vis de la dimensionnalité et convergeant très rapidement. Je remercie d'ailleurs Fred Glover pour son implication dans ce papier, lui-même travaillant sur différents algorithmes de Line Search et étant de passage en France.

Sixième Partie : Préparation d'un papier pour une revue dans Springer.

Je suis en train de travailler en collaboration avec Fred Glover sur une version étendue de mon papier présenté lors de la conférence ISDA'09. L'algorithme actuel est une hybridation de EUS et d'un algorithme proposé par Fred : 3-2-3. J'ai également modifié l'algorithme de recherche global afin d'augmenter la vitesse de convergence de l'algorithme. Les résultats actuels sont excellents sur la plupart des fonctions du benchmark.

Collaboration : Fred Glover.

Le créateur de la recherche Tabou, lors d'un passage à l'université de Créteil, m'a parlé de ses travaux et a été interessé par mon papier sur les algorithmes de Line Search. Il a collaboré activement à l'écriture d'un papier de proceedings ainsi qu'un papier de revue. Je lui en suis très reconnaissant.

Collaboration : Julien Lepagnot.

Thésard de Patrick Siarry, avec qui j'ai pu sympathiser lors de la conférence ISDA'09. A intégré avec succès mon algorithme EUS dans son algorithme MADO d'optimisation dynamique.

Collaboration : Mohammed G. Omran.

Thésard Koweitien, il a repris mon travail sur l'algorithme EUS et a trouvé un moyen astucieux de l'améliorer.