Algos génétiques, heuristiques...

**Regis.C** · 28/04/2004, 23h51

Je viens pour la première fois sur le forum des algos et j'avoue que je plane à 10 000 !
Qu'est-ce qu'un algo génétique ? Heuristique ?

Pardon d'être largé...

**duffman** · 29/04/2004, 10h05

Bon je vais tenter une explication simple et courte, n'étant pas moi-même un spécialiste.
Heuristique est un terme général désignant une méthode de résolution pour un problème donné. La caractéristique d'une heuristique est qu'elle ne donne pas forcément la meilleure solution possible (tout dépend bien entendu du problème abordé). Ces termes sont surtout employés en théorie de la complexité (= distinction des problèmes "difficiles" et des problèmes "faciles").

petits exemples:
Imaginons que ton problème soit de trier un tableau. Ce problème est dit 'facile' car il existe un (même plusieurs) algorithme permettant de trier un tableau dans un temps de calcul restreint.

Maintenant imaginons que ton problème est un problème d'ordonnancement (affecter des tâches à des machines pour minimiser le nombre de tâche en retard) et bien dans ce cas, le problème est difficile (ou on dit parfois plus justement: NP-Difficile) et il n'existe pas d'algorithme permettant de trouver la meilleure solution possible dans un temps de calcul court. Dans ce cas, on fait souvent appel à une méthode heuristique.

Pour un problème difficile, une approche par heuristique est bien souvent la solution retenue car bien qu'il existe des méthodes permettant la résolution exacte des problèmes, elles sont souvent couteuses en temps de calcul.
Voilà pour les heuristiques, j'espère t'avoir éclairer
En ce qui concerne les algorithmes génétiques, il s'agit d'une sous-famille des méthodes heuristiques (ils sont donc eux-même des heuristiques)

**Regis.C** · 30/04/2004, 00h06

Merci beaucoup pour ces éclaircissements!
La "théorie des graphes" qui permet la résolution de problème complexes (certaines fois) est-elle une méthode heuristique, par exemple ??