Si j'ai bien compris, ce sont des algorithmes qui génèrent plein de solutions, ne gardent que les meilleures, et regénèrent d'autres solutions à partir de celles la.
Ton approche est ce qu'on appel un algo Maximiseur ou MiniMax, on effectue une coupe franche en fonction de la performance mesuré pour un ensemble de solution partiel, ça marche très bien pour certains problèmes mais pas pour d'autre. Pour prendre un exemple, si tes algo jouent aux échecs, Minimax écartera systématiquement les solution qui implique la perte d'une pièce, alors que cela peut ouvrir des solutions plus intéressante par la suite ( on appel ça un minimum local ).
Un algo génétique n'écarte une branche ou un élément de solution un "géne" qu'au bout de plusieurs générations infructueuses quand il est poussé a l'extinction par d'autre "géne", c'est beaucoup plus efficace mais aussi beaucoup plus lourd le nombre de solution a traité est toujours assez grand, mais l'on limite tous de même le nombre de test a la population tous en s'approchant d'une solution optimale.
Ils se comportent comme la sélection naturelle, en gros. Ca ne permet pas forcément de trouver la solution idéale et il faut beaucoup de génération pour que cela vaille le coup.
Ce type d'algorithme est principalement utiliser sur les probléme dit NP complexe, Non Polynomiale Complexe, c'est une notion mathématique que je ne maîtrise pas pour en gros dire que pour telle problème le temps de traitement est incroyablement long avec un algo simple du type je teste toutes les solutions et que n'est pas efficace MiniMax ( je n'ai pas de critère efficace qui me permet des tronçonner mon arbre de test ) , concrètement l'exemple type c'est le problème du voyageur de commerce ( un voyageur doit passer par tout un ensemble de ville, une seul fois et en parcourant le chemin le plus court ).
Hors on ne trouve que très rarement la meilleur solution a un problème NP complet, on est déjà bien contant d'avoir une bonne solution.
C'est surtout cela qui m'impressionne ici, il arrive à compenser le coût de son algorithme et à gagner de la performance en plus.
Il ne faut pas s'enflammer non plus les algo génétique ne sont pas la panacée universelle. Ce n'est pas le seul algo auto-adaptatif, ( y a les réseaux de neurones, les fourmis, le recuit ) en général c'est assez/trés dur a maîtriser et utiliser, de plus c'est non déterministe ( son temps d'exécution n'est pas connue ) ce qui est leurs principaux défauts.
[^] # Re: Algorithme génétique ?
Posté par Beretta_Vexee . En réponse à la dépêche Améliorer les performances du noyau avec un algorithme génétique. Évalué à 10.
Ton approche est ce qu'on appel un algo Maximiseur ou MiniMax, on effectue une coupe franche en fonction de la performance mesuré pour un ensemble de solution partiel, ça marche très bien pour certains problèmes mais pas pour d'autre. Pour prendre un exemple, si tes algo jouent aux échecs, Minimax écartera systématiquement les solution qui implique la perte d'une pièce, alors que cela peut ouvrir des solutions plus intéressante par la suite ( on appel ça un minimum local ).
Un algo génétique n'écarte une branche ou un élément de solution un "géne" qu'au bout de plusieurs générations infructueuses quand il est poussé a l'extinction par d'autre "géne", c'est beaucoup plus efficace mais aussi beaucoup plus lourd le nombre de solution a traité est toujours assez grand, mais l'on limite tous de même le nombre de test a la population tous en s'approchant d'une solution optimale.
Ce type d'algorithme est principalement utiliser sur les probléme dit NP complexe, Non Polynomiale Complexe, c'est une notion mathématique que je ne maîtrise pas pour en gros dire que pour telle problème le temps de traitement est incroyablement long avec un algo simple du type je teste toutes les solutions et que n'est pas efficace MiniMax ( je n'ai pas de critère efficace qui me permet des tronçonner mon arbre de test ) , concrètement l'exemple type c'est le problème du voyageur de commerce ( un voyageur doit passer par tout un ensemble de ville, une seul fois et en parcourant le chemin le plus court ).
Hors on ne trouve que très rarement la meilleur solution a un problème NP complet, on est déjà bien contant d'avoir une bonne solution.
Il ne faut pas s'enflammer non plus les algo génétique ne sont pas la panacée universelle. Ce n'est pas le seul algo auto-adaptatif, ( y a les réseaux de neurones, les fourmis, le recuit ) en général c'est assez/trés dur a maîtriser et utiliser, de plus c'est non déterministe ( son temps d'exécution n'est pas connue ) ce qui est leurs principaux défauts.