Algorithme mémétique

Les algorithmes mémétiques appartiennent à la famille des algorithmes évolutionnistes. Leur but est d'obtenir une solution approchée à un problème d'optimisation, lorsqu'il n'existe pas de méthode de résolution pour résoudre le problème de manière exacte en un temps raisonnable. Les algorithmes mémétiques sont nés d'une hybridation entre les algorithmes génétiques et les algorithmes de recherche locale. Ils utilisent le même processus de résolution que les algorithmes génétiques mais utilisent un opérateur de recherche locale après celui de mutation. L'intérêt de cette classe d'algorithme est l'apport de la diversification de la partie génétique accompagnée par l'intensification de la recherche locale.

On peut classer les algorithmes mémétiques dans les métaheuristiques.

Principe

Le principe général des algorithmes mémétiques est semblable à celui des algorithmes génétiques à la différence près qu'un opérateur de recherche locale est ajouté après celui de mutation. Ce dernier permet d'ajouter une intensification à la diversification apportée par le principe de l'algorithme génétique. Un algorithme génétique a besoin pour son fonctionnement d'une population initiale. Celle-ci peut-être construite de manière aléatoire ou de façon gloutonne. L'algorithme itère différentes étapes ensuite jusqu'à un critère d'arrêt propre à chaque problème/utilisateur :

• sélection de deux parents (individus) dans la population
• application d'un opérateur de croisement entre les deux parents afin de générer un nouvel enfant (individu)
• application d'un opérateur de recherche locale à l'enfant
• mise à jour de la population avec l'enfant (selon la stratégie garder les meilleures solutions, un échantillon large, etc.)

Schéma récapitulatif

1. Population de base générée aléatoirement ou avec une initialisation de type gloutonne
2. Évaluation de chaque individu
3. Sélection d'un sous groupe parmi la population
4. Croisement de deux parents pour créer un nouveau fils
   • Application d'une recherche locale aux nouveaux enfants
   • Mutation à appliquer sur l'enfant
   • Mis à jour de la population en gardant les meilleurs enfants, et supprimant les plus mauvais individus

Voir aussi

Bibliographie

• Adrien Goëffon. Nouvelles heuristiques de voisinage et mémétiques pour le problème Maximum de Parcimonie. Other. Université d’Angers, 2006. French. <tel-00256670>