Voici un résumé du cours sur les métaheuristiques, incluant les étapes des algorithmes présentés,
leurs avantages, inconvénients, et cas d'emploi.
1. La recherche locale
Étapes de l'algorithme
1. Initialisation :
o Choisir une solution initiale (aléatoire ou déterministe).
2. Itération :
o Générer les solutions voisines de la solution actuelle.
o Évaluer la fonction objectif pour chaque voisin.
o Sélectionner le voisin qui améliore le plus la fonction objectif.
o Mettre à jour la solution courante avec la meilleure solution voisine.
3. Critère d'arrêt :
o Arrêter lorsque aucune amélioration n'est possible ou lorsqu'un critère (nombre
maximal d'itérations, temps, etc.) est atteint.
Avantages :
Simple à implémenter.
Efficace pour des problèmes de petite taille ou unimodaux.
Fonctionne bien pour des espaces de recherche continus.
Inconvénients :
Risque de convergence vers un optimum local.
Dépend fortement de la définition du voisinage.
Ne garantit pas de trouver la solution globale.
Cas d'emploi :
Problème du voyageur de commerce (TSP) : Réduction de la longueur totale d'un itinéraire.
Coloriage de graphe : Minimiser le nombre de conflits entre sommets reliés.
2. Les algorithmes génétiques
Inspirés de la sélection naturelle, ces algorithmes explorent un espace de solutions en combinant
plusieurs solutions candidates.
Étapes de l'algorithme
1. Codage (Représentation des solutions) :
o Représenter chaque solution (individu) sous forme d'une chaîne (binaire, réelle, ou
autre).
o Ex. TSP : une permutation des villes.
2. Sélection :
o Favoriser les meilleurs individus pour la reproduction.
o Méthodes : roulette, tournoi, élitisme, etc.
3. Croisement :
o Combiner deux parents pour créer de nouveaux individus (enfants).
o Méthodes : croisement à un point, à plusieurs points, ou uniforme.
4. Mutation :
o Introduire des modifications aléatoires pour maintenir la diversité dans la population.
o Ex. TSP : permuter deux villes dans un itinéraire.
5. Évaluation :
o Attribuer une valeur (adaptation) à chaque individu selon une fonction d'objectif.
6. Critère d'arrêt :
o Terminer après un certain nombre de générations ou lorsqu'il n'y a plus
d'amélioration significative.
Avantages :
Capacité à explorer de vastes espaces de recherche.
Adapté aux problèmes complexes et discontinus.
Moins susceptible de rester coincé dans un optimum local grâce à la diversité.
Inconvénients :
Coût computationnel élevé.
Nécessite de nombreux paramètres (taille de la population, taux de mutation, etc.).
Pas de garantie de trouver la solution optimale.
Cas d'emploi :
Problème du voyageur de commerce (TSP) : Optimisation d'itinéraires.
Planification et ordonnancement : Optimisation des séquences d'actions.
Comparaison des deux méthodes
Critères Recherche locale Algorithmes génétiques
Nature du problème Simple, continu, unimodal Complexe, combinatoire
Vitesse Rapide pour des problèmes simples Plus lente (nombreux calculs)
Exploration Localisée autour de la solution actuelle Globale grâce à la diversité
Critères Recherche locale Algorithmes génétiques
Convergence Risque d'optimum local Meilleure exploration (moins de risque)
Paramétrage Relativement simple Complexe (taux de mutation, etc.)
Résumé final
La recherche locale est simple et efficace pour des problèmes bien définis et de petite taille.
Les algorithmes génétiques sont adaptés aux problèmes combinatoires ou discontinus, mais
ils sont plus coûteux en temps de calcul.
Le choix de la méthode dépend de la nature du problème, des ressources disponibles et des
exigences en termes de qualité de la solution.
Flashcards : Métaheuristiques
Flashcard 1
Question : Qu'est-ce qu'une métaheuristique ?
Réponse :
Une métaheuristique est une méthode d'optimisation qui explore un espace de recherche complexe
pour trouver des solutions de bonne qualité en un temps raisonnable, sans garantir l'optimalité.
Flashcard 2
Question : Quelles sont les étapes principales de la recherche locale ?
Réponse :
1. Initialisation : Choisir une solution initiale.
2. Itération :
o Générer des solutions voisines.
o Évaluer les voisins.
o Sélectionner la meilleure solution voisine.
3. Critère d'arrêt : Arrêter lorsque l'amélioration est impossible ou un seuil est atteint.
Flashcard 3
Question : Quels sont les avantages de la recherche locale ?
Réponse :
Simple à implémenter.
Rapide pour des problèmes continus ou unimodaux.
Efficace pour des problèmes de petite taille.
Flashcard 4
Question : Quels sont les inconvénients de la recherche locale ?
Réponse :
Peut se bloquer dans un optimum local.
Dépend de la définition du voisinage.
Non adaptée aux problèmes complexes ou discontinus.
Flashcard 5
Question : Quelles sont les étapes principales des algorithmes génétiques ?
Réponse :
1. Codage : Représenter les solutions sous forme d'individus.
2. Sélection : Choisir les individus les plus adaptés.
3. Croisement : Combiner deux parents pour créer des enfants.
4. Mutation : Introduire des variations aléatoires pour maintenir la diversité.
5. Évaluation : Calculer la qualité (fitness) des individus.
6. Critère d'arrêt : Terminer après un certain nombre de générations ou lorsque la solution
converge.
Flashcard 6
Question : Quels sont les avantages des algorithmes génétiques ?
Réponse :
Bonne exploration globale de l'espace de recherche.
Moins susceptibles de rester coincés dans un optimum local.
Adaptés aux problèmes combinatoires et complexes.
Flashcard 7
Question : Quels sont les inconvénients des algorithmes génétiques ?
Réponse :
Coût computationnel élevé.
Paramètres complexes à régler (taille de la population, taux de mutation, etc.).
Pas de garantie de solution optimale.
Flashcard 8
Question : Quels sont les cas d'emploi typiques de la recherche locale ?
Réponse :
Problème du voyageur de commerce (TSP) : Minimisation de la longueur d'un itinéraire.
Coloriage de graphe : Réduction des conflits entre sommets adjacents.
Flashcard 9
Question : Dans quels cas utilise-t-on les algorithmes génétiques ?
Réponse :
Problèmes combinatoires comme le TSP.
Planification et ordonnancement.
Optimisation dans des espaces discontinus.
Flashcard 10
Question : Quelle est la différence principale entre la recherche locale et les algorithmes génétiques ?
Réponse :
Recherche locale : Exploration locale autour de la solution actuelle (rapide, mais risque
d'optimum local).
Algorithmes génétiques : Exploration globale grâce à la diversité des solutions, mais plus
coûteuse.
Si tu veux approfondir un sujet ou ajouter d'autres concepts, fais-le-moi savoir ! 😊
