Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme mémétique
Résumé
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.
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.)
Population de base générée aléatoirement ou avec une initialisation de type gloutonne
Évaluation de chaque individu
Sélection d'un sous groupe parmi la population
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
Adrien Goëffon.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.