La définition du point d'arrêt d'un algorithme génétique va-t-elle à l'encontre de l'objectif de l'algorithme?

Wikipedia définit le point de terminaison d'une AG à ceci:

Généralement, l'algorithme se termine lorsqu'un nombre maximal de générations a été produit ou qu'un niveau de forme physique satisfaisant a été atteint pour la population. Si l'algorithme s'est arrêté en raison d'un nombre maximum de générations, une solution satisfaisante peut ou non avoir été trouvée.

Maintenant, s'il se termine lorsqu'un niveau de forme physique satisfaisant a été atteint, et que vous êtes celui qui définit ce niveau de forme physique, pourquoi ne pourriez-vous pas simplement créer vous-même le génome "parfait" depuis le début, puisque vous connaissez déjà les caractéristiques de ce génome parfait?

Je suppose que je suis juste un peu confus ici. Je pensais que le but d'une AG était d'évoluer constamment et de nous montrer peut-être une solution encore meilleure que ce à quoi nous pensions, et notre fonction de fitness était juste quelque chose qui l'a aidée en cours de route, pas quelque chose que nous avons mis sur le piédestal comme terminaison " parfait "état. Cela ne détruit-il pas le point?

La fonction fitness évalue la sortie de votre algorithme. Il est tout à fait possible de reconnaître une sortie idéale lorsque vous la voyez, mais ne connaissez pas les étapes pour produire cette sortie à partir d'une entrée donnée. C'est là que les algorithmes génétiques sont les plus utiles.

Par exemple, une application amusante courante de GA consiste à produire une animation qui peut déplacer une créature virtuelle de manière efficace. Il est facile de dire si la créature se déplace à une certaine vitesse en ligne relativement droite. C'est votre fonction de fitness. Il est beaucoup plus difficile de déterminer la séquence exacte des mouvements «musculaires» pour y parvenir.

Il arrive souvent que vous puissiez déterminer l'aptitude d'une solution mais ne pouvez pas déterminer directement la solution elle-même. Supposons que vous essayez de faire évoluer des lapins rapides, et qu'il existe une poignée de gènes qui influent sur la vitesse du lapin. Vous pouvez tester la vitesse du lapin, mais énumérer toutes les combinaisons de gènes liés à la vitesse serait peu pratique. Dans un tel cas, vous pourriez avoir une AG qui élève des lapins et élève les plus rapides. Vous pourriez le faire pour toujours, mais vous préféreriez probablement arrêter quand:

• vous avez trouvé un lapin plus rapide que X, ou
• l'amélioration progressive sur n générations est tombée en dessous d'un certain seuil, ou
• vous avez élevé des lapins à travers m générations

Le but de l'AG est de vous donner la solution au problème qui a ce niveau de forme physique. Cette solution serait très difficile à trouver en utilisant d'autres algorithmes de recherche plus conventionnels, c'est pourquoi vous utilisez d'abord un GA en premier lieu.

Ou au lieu d'une limite de valeur de fitness, vous pouvez décider du nombre de générations que vous souhaitez exécuter (plus vous générez de générations, plus vous avez de chances de trouver des valeurs de fitness toujours plus élevées). Par exemple, dans le problème du voyageur de commerce, obtenir un chemin qui a le coût le plus bas entre les villes que vous devez traverser.

Le fait que votre condition d'arrêt soit un certain niveau de condition physique acceptable ou une certaine contrainte de temps (exécution de l'AG pendant une période de temps maximale ou un nombre limité de générations pour les applications critiques comme le pathfinding ou les applications AI) est généralement déterminé par votre problème. domaine.

Intuitivement, le but d'un algorithme génétique est de formuler une solution algorithmique à un problème qui ne se prête pas à une analyse logique simple. Une fois cet objectif atteint, l'AG n'a plus besoin de poursuivre.

Bien sûr, si une meilleure "forme physique" est souhaitée, l'algorithme génétique peut être laissé en marche pour voir s'il peut trouver une solution plus hautement optimisée, ou l'algorithme génétique peut lui-même être modifié pour voir s'il convergera vers une meilleure solution.

Un algorithme génétique nécessite un moyen de récompenser les bons gènes avec une plus grande propagation. Si vous n'aviez aucun moyen de distinguer les bons gènes des mauvais gènes, vous ne pourriez pas du tout utiliser un algorithme génétique.

Pour qu'un algorithme génétique fonctionne, vous devez permettre aux solutions les plus adaptées de se reproduire de préférence aux solutions les moins adaptées. Sinon, vous essayez simplement des solutions aléatoires.

Voici un exemple typique de ma propre expérience: en développant l'un des premiers systèmes de numérotation vocale, nous avons eu du mal à trouver un algorithme pour faire correspondre un nom prononcé à une copie stockée de ce même nom. On nous a dit qu'une précision de 95% pour choisir un nom sur 25 était suffisante. Nous avions un corpus stocké de personnes disant 25 noms 10 fois chacun.

Tout d'abord, nous avons développé un système d'entrée qui mesurait la longueur du mot parlé et l'énergie de fréquence en plusieurs morceaux normalisés. Ensuite, nous avons développé un algorithme qui a attribué des poids aux correspondances sur ces paramètres et comparé deux ensembles de paramètres à travers ces poids.

Maintenant, nous avons eu une dernière étape - quelle devrait être la valeur de ces poids?

Nous avons créé 1 000 ensembles aléatoires de poids et les avons testés par rapport au corpus. Nous avons jeté les 500 qui ont fait le pire. Pour les 500 restants, nous avons dupliqué chacun et dans l'un d'eux, augmenté ou abaissé au hasard l'un des poids.

Nous avons répété ce processus sur un ordinateur pendant environ deux semaines jusqu'à ce qu'il ait finalement un ensemble de poids répondant au critère de précision de 95%. Nous l'avons ensuite testé sur des données ne figurant pas dans le corpus. Il était précis à environ 92%. Nous avons donc couru plus longtemps pour atteindre une précision de 98% sur le corpus et cet ensemble de poids a produit une précision de 95% sur les données ne figurant pas dans le corpus.

Donc, le fait est que vous devez avoir une fonction de fitness pour exécuter un algorithme génétique. Si vous n'avez aucun moyen de distinguer les bons gènes des mauvais gènes, comment pouvez-vous vous assurer que les bons gènes se reproduisent et que les mauvais gènes ne le font pas?

Itérer jusqu'à ce qu'une solution ne diffère pas beaucoup de l'itération précédente. Pour beaucoup, veuillez comprendre une tolérance fixe.

Solution in iteration n-6: 600
Solution in iteration n-5: 800
Solution in iteration n-4: 768
Solution in iteration n-3: 780 
Solution in iteration n-2: 778
Solution in iteration n-1: 778.23
Solution in iteration n: 780.18
Solution in iteration n+1: 780.1815

Dans cet exemple, si votre tolérance fixe était de 0,01, alors (n + 1) vous indique d'arrêter car abs (solution (n + 1) -solution (n)) <0,01.

En reprenant, c'est quand votre algorithme peut dire: cela ne s'améliorera pas!

Pour une réponse rapide à votre question principale: Il y a une grande différence entre savoir ce que vous voulez atteindre et savoir comment y arriver.

Plus en détail, par exemple, avec l'un des problèmes les plus populaires résolus en utilisant des algorithmes génétiques / évolutionnaires, généralement une étude de cas en classe, trouvant la route optimale dans un graphique. Cela est souvent utilisé dans les réseaux pour trouver l'itinéraire le moins cher d'un bout à l'autre. Lorsque vous définissez les coûts (nombre de sauts, coût de chaque saut, etc ...), vous définissez également votre coût cible (niveau de forme physique) auquel vous êtes satisfait du résultat. Votre algorithme peut ne pas trouver le meilleur, mais il trouvera un optimum algorithmiquement acceptable. J'entends par là que la relation coût / bénéfice de trouver une meilleure réponse est prohibitive.

Avec GA / EA, vous constaterez que c'est un comportement normal que vous trouviez très rapidement une réponse optimale à 95% +, mais réduire les 5% précédents est exponentiellement plus coûteux. Ainsi, la théorie est que vous définissez un optimum acceptable pour obtenir le meilleur résultat en un minimum de temps. Étant donné que le coût de la recherche, par exemple le 1% supérieur, pourrait l'emporter sur ses avantages par rapport aux 5% supérieurs, vous définissez votre optimum acceptable.

Pour résumer, vous n'avez pas maintenant la réponse à un problème particulier, vous définissez simplement, par problème, votre optimum acceptable, le point où trouver une meilleure réponse n'est pas pratique.

Il y a des recherches sur la correction des bogues en C avec des algorithmes génétiques en fournissant des cas de test négatifs et positifs en tant que fonctions de fitness, ainsi qu'un code cassé en entrée. Ceci est un exemple d'un problème qui pourrait être résolu par un humain, mais il est plus facile à faire pour un algorithme génétique. Il est important de noter:

Bien que les méthodes décrites dans cet article n'évoluent pas de nouveaux programmes à partir de zéro, elles montrent comment faire évoluer les logiciels hérités pour réparer les défauts existants.

Cependant, de nouveaux programmes ont été élaborés à partir de zéro, mais pas en C. Les quelques programmes non triviaux écrits dans le langage de programmation ésotérique Malbolge ont tous (à ma connaissance) évolué, pas écrits. Le langage est trop complexe pour être utilisé par un programmeur et trop compliqué pour déduire efficacement des programmes de la logique seule, de sorte que la majorité des programmes qui y sont écrits ont été produits par des algorithmes génétiques. La fonction fitness est généralement la distance de montage à la sortie attendue.

C'est en quelque sorte bien circulaire. En observant que le code génétique complexe est écrit par des processus évolutifs, nous pouvons simuler des processus évolutifs pour produire du code dans un langage complexe différent, sans même savoir comment fonctionne le code!