Proposition d'un nouvel algorithme d'optimisation basé sur la théorie de la gravitation.

Abstract

Ce travail est un mémoire de Master en Automatique et système effectué à l’université de Bejaia. Il est consacré à la proposition d’un nouvel algorithme intelligent basé sur la théorie de la gravitation et la représentation compacte. Il nous a permis, entre autres, de nous confronter à plusieurs problèmes interdisciplinaires toujours en relation avec les métaheuristiques et l’automatique d’une manière générale. Au cours des dernières années, diverses méthodes d'optimisation heuristique ont été développées. Certains de ces algorithmes sont inspirés par les comportements des essaims et d’autres sur la génétique. Dans ce mémoire, l’algorithme étudié est appelé algorithme de recherche gravitationnelle (GSA). GSA est construit sur la base de la loi de Gravité et de la notion d'interactions entre des masses ponctuelles. L'algorithme GSA utilise la théorie de la physique newtonienne et ses agents de recherche sont une collection de masses. La force gravitationnelle est un moyen de transférer des informations entre différentes masses. Comme tout autre algorithme basé sur une population, le GSA présente l’inconvénient de ses capacités de calcul élevées. Dans ce mémoire, néanmoins, un nouvel algorithme dédié à l’optimisation et la recherche est proposé. Nous l’avons nommé compact Gravitational Search Algorithm (cGSA). L’idée principale consiste à compacter l’information relative à la population de masses et de la représenter statistiquement afin de réduire les capacités de calcul et de mémoire requise par GSA. Pour ce faire nous avons conduit notre travail en quatre étapes. La première consiste à étudier le vaste domaine des métaheuristiques et de fournir un bref état de l’art des techniques utilisées. Nous avons présenté étude dans le chapitre 1 et cela nous permis d’approfondir le domaine des métaheuristiques. Dans la deuxième étape, nous avons étudié l’algorithme GSA qui est basé sur la théorie de la gravitation. Son principe de fonctionnement et les détails qui lui sont liés sont présentés dans le chapitre 2. Dans la troisième étape, nous avons étudié la réduction des capacités de calculs par la représentation compacte. Les algorithmes étudiés, comme le bCGA, pe- cFA et ne-cFA, sont présentés au chapitre 3. La quatrième étape consiste à appliquer la représentation compacte sur GSA. L’algorithme obtenu a été baptisé cGSA : compact gravitational search algorithm. L’algorithme et la validation par des fonctions de tests sont présentés au chapitre 4. Nous avons fourni aussi une application de notre algorithme pour la planification de trajectoire d’un robot mobile dans un environnement contenant des obstacles.