New Hybrid Methods applying to Thomson problem and Sensor Network Localization problem

Abstract

Placer N points "uniformément" sur la surface de la sphère connu sous le nom de problème de Thomson, localiser un réseau de capteurs sans fils, sont deux grands problème de l’optimisation globale. Dans cette thèse, on donne une description de ces deux problèmes, et on présente différents algorithmes hybrides pour les résoudre. Ces algorithmes sont basés sur un couplage entre une méthode de gradient "Nonmonotone spectral gradient (NSG) method" et l’une des deux métaheuristiques les plus populaires: l’Optimisation par Essaim de Particules (OEP, ou PSO en anglais) et l’Algorithme évolutionniste (AE, ou EA en anglais). La méthode NSG est une méthode de gradient basée sur les deux récents outils de l’optimisation globale suivants: une recherche linéaire non-monotone qui garantit la convergence globale, et un nouveau choix de la longueur du pas dans la direction opposée du gradient. L’utilisation de ce pas permet d’accélérer le processus de convergence et semble être moins sensible au mauvais conditionnement. Dans cette thèse, nous introduisons trois types d’hybridations : i) La méthode hybride traditionnelle, qui consiste à optimiser d’abord la fonction objectif au moyen d’un algorithme évolutionniste pendant un certain nombre de générations, ensuite, la méthode NSG est appliquée à partir de la solution fournie par l’algorithme évolutionniste. L’intérêt de cette méthode est illustré au moyen du problème de Thomson. ii) Au contraire de l’hybridation précédente, dans la deuxième approche on exécute la méthode NSG avec une estimation initiale aléatoire, et on fait tourner la méthode PSO avec une population initiale construite par des particules voisines de la solution donnée par NSG. L’efficacité de cet algorithme est établie sur le problème de la localisation des réseaux de capteurs sans fils. iii) La dernière approche hybride est appelée PSO-NSG. Dans cette dernière on combine les atouts des méthodes PSO et NSG. On teste l’efficacité de PSO en chaque l itérations en initialisant la méthode NSG par la meilleure particule de PSO. La robustesse de la méthode PSO-NSG est illustrée sur dix fonctions test et également sur le problème de la localisation des réseaux de capteurs sans fils.