Heuristiques et métaheuristiques
Chercher une bonne solution quand la meilleure est hors d'atteinte : glouton, recherche locale et optimum local, puis recuit simulé, recherche tabou et algorithme génétique, et le compromis entre qualité et temps de calcul.
- 26 cartes
- 4 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
Quelques cartes du deck
Heuristique : de quoi s'agit-il ?
Voir la réponse
Méthode conçue pour un problème précis, qui trouve vite une bonne solution sans garantir qu'elle soit la meilleure.
On l'accepte quand l'optimum coûte trop cher à calculer : le plus proche voisin pour une tournée en est un exemple.
Solution courante de coût 14 (on minimise). Ses quatre voisins coûtent 15, 16, 13 et 17, et celui de coût 13 est tabou (sans critère d'aspiration). Quel voisin la recherche tabou retient-elle ?
- Celui de coût 15, même s'il dégrade la solution
- Celui de coût 13, car il améliore la solution même s'il est tabou
- Aucun : la solution courante est un optimum local, la recherche s'arrête
- Celui de coût 17, pour s'éloigner le plus possible de la solution courante
Voir la réponse
Celui de coût 15, même s'il dégrade la solution
La recherche tabou prend le meilleur voisin non interdit, quitte à dégrader : 15. Cette dégradation permet de sortir d'un optimum local. Le mouvement inverse est ensuite inscrit dans la liste tabou, pour ne pas revenir en arrière.
Dans un recuit simulé, le voisin plus mauvais de Δ est accepté avec la probabilité …, où T est la ….
Voir la réponse
Dans un recuit simulé, le voisin plus mauvais de Δ est accepté avec la probabilité e^(−Δ/T), où T est la température.
Plus Δ est grand, plus la probabilité est petite ; plus T est grand, plus elle est proche de 1. Un voisin meilleur est toujours accepté.
Métaheuristique : de quoi s'agit-il ?
Voir la réponse
Stratégie générale de recherche, applicable à des problèmes variés, qui guide une heuristique pour échapper aux solutions médiocres.
Elle ne dépend pas d'un problème : seules la représentation d'une solution et la définition d'un voisin changent. Recuit simulé, recherche tabou et algorithme génétique en sont trois exemples.