Une introduction aux algorithmes génétiques

Les algorithmes génétiques sont un programme qui cherche la meilleure solution au problème en simulant des processus évolutifs naturels tels que "la survie des plus aptes", traversant les chromosomes et mutation. Cet article présentera brièvement les méthodes d'écriture des algorithmes génétiques, discutera de certains facteurs importants qui doivent être pris en compte lors de la rédaction de vos propres algorithmes et fournissent quelques exemples d'applications pratiques des algorithmes génétiques.

Points clés

• Les algorithmes génétiques simulent des processus évolutifs tels que "la survie des plus en forme" et utilisent des mécanismes tels que la sélection, le croisement et la mutation pour trouver les solutions optimales à des problèmes complexes.
• Dans les algorithmes génétiques, la solution potentielle est exprimée en chromosomes, et son applicabilité est évaluée par une fonction de fitness qui détermine la probabilité qu'il soit sélectionné pour la reproduction.
• Le processus de croisement combine les fonctionnalités d'une paire de solutions parentales pour créer une nouvelle progéniture, tandis que la variation introduit des changements aléatoires dans la progéniture, maintenant ainsi la diversité génétique et potentiellement découvrir de nouvelles solutions.
• Étant donné que les algorithmes génétiques peuvent explorer efficacement les espaces de solutions importants et complexes, ils sont très efficaces pour les problèmes difficiles à résoudre dans les méthodes de recherche et d'optimisation traditionnelles.
• Les applications pratiques des algorithmes génétiques vont de la conception d'antennes avec des caractéristiques de performance améliorées à l'optimisation de la conception Web, qui illustre leur polyvalence et leur puissance dans la résolution de problèmes pratiques.

Cracking Informations inconnues

Le temps est de 2369 ans, et les humains se sont propagés partout dans la mer des étoiles. Vous êtes un médecin jeune et intelligent stationné dans une base d'étoiles bien animée, animé de voyageurs interstellaires, de marchands et de hors-la-loi occasionnels. Peu de temps après votre arrivée, un commerçant de la base s'est intéressé à vous. Il prétend qu'il n'est qu'un simple tailleur, mais les rumeurs disent qu'il est un agent secret travaillant pour un régime particulièrement mauvais.

Vous commencez à déjeuner ensemble chaque semaine, en discutant des sujets de la politique à la poésie. Même après quelques mois, vous ne savez toujours pas s'il exprime des sentiments romantiques ou prend des secrets (vous n'avez certainement pas de secrets). Peut-être les deux.

Un jour au déjeuner, il vous a mis au défi: "J'ai un message pour vous dire, cher docteur! Je ne peux certainement pas vous dire ce que c'est. Mais je vous le dis, c'est 12 personnages. Ces personnages peuvent être n'importe lequel Lettre, l'espace ou la ponctuation.

Vous êtes retourné au bureau dans la cabine médicale, pensant toujours à ce qu'il vient de dire. Soudain, une expérience de simulation de séquençage de gènes que vous aviez déjà exécutée sur un ordinateur à proximité vous a donné une idée. Vous n'êtes pas un expert en décryptage de mot de passe, mais vous pouvez peut-être utiliser votre expertise en génétique pour déchiffrer ses informations!

Certaines théories

Comme je l'ai mentionné au début, un algorithme génétique est un programme qui utilise des opérations qui entraînent l'évolution pour rechercher des solutions. Après de nombreuses itérations, l'algorithme sélectionne les meilleurs candidats (deviner) à partir d'un ensemble de solutions possibles, les recombines et les vérifications que les combinaisons se rapprochent de la solution. Les pauvres candidats seront rejetés.

Dans la scène ci-dessus, tout personnage du message secret peut être A-Z, l'espace ou la ponctuation de base. Supposons que cela nous donne les 32 caractères suivants "Alphabet": ABCDEFGHIJKLMNOPQRSTUVWXYZ -.,!? eux sont corrects. Il faut trop de temps pour vérifier chaque possibilité. Au lieu de cela, l'algorithme génétique sélectionnera au hasard 12 caractères et demandera au tailleur / espion d'évaluer la proximité du résultat de ses informations. Ceci est plus efficace que les recherches par la force brute, car les scores nous permettent de régler les futurs candidats. La rétroaction nous permet de mesurer la forme physique de chaque supposition et, espérons-le, éviter de perdre du temps dans une impasse. Supposons que nous ayons fait trois suppositions: homlk? Wsrzdj, bgk ka! Qtpxc et xelpocv.xlf!. Le premier candidat a marqué 248,2, le second était de 632,5 et le troisième était de 219,5. La façon dont les scores sont calculées dépend de la situation, dont nous discuterons plus loin, mais supposons maintenant qu'elle est basée sur l'écart entre le candidat et les informations cibles: le score parfait est 0 (c'est-à-dire pas de déviation; le candidat et la cible sont La même chose), un score plus élevé signifie un plus grand écart. Les suppositions avec des scores de 248,2 et 219,5 sont plus proches du contenu des informations secrètes que la supposition avec des scores de 635,5. La future supposition est faite grâce à la combinaison des meilleures tentatives. Il existe de nombreuses façons de combiner les candidats, mais maintenant nous considérons une simple approche de croisement: chaque personnage de la nouvelle supposition a une probabilité de 50-50 copiée du premier ou du deuxième candidat parent. Si nous prenons les deux suppositions de Homlk? Wsrzdj et Xelpocv.xlf!, Alors le premier caractère de notre candidat descendant a une probabilité de 50% de H, une probabilité de 50% de x, et le deuxième caractère sera O ou E, et bientôt. La progéniture peut être bonjour? W.rld!.

générer de nouveaux candidats par croisement

Cependant, si nous n'utilisons que les valeurs du candidat parent, il peut y avoir un problème dans plusieurs itérations: manque de diversité. Si nous avons un candidat se compose de tout ce que A et l'autre se compose de tout B, alors tous les descendants générés par le crossover ne comprendront que A et B. Si la solution comprend C, nous serions malheureux.

Pour atténuer ce risque et maintenir la diversité tout en rétrécissant la portée des solutions, nous pouvons introduire de légers changements. Plutôt que de faire une segmentation 50-50 directement, nous permettons à une petite probabilité de remplacer toute valeur dans l'alphabet. Grâce à cette mutation, la progéniture peut devenir Hello World !.

La mutation

maintient les choses fraîches!

Selon les attentes, les algorithmes génétiques empruntent un grand nombre de vocabulaires en sciences génétiques. Donc, avant de discuter davantage, affinons quelques termes:

• allèles: un membre de l'alphabet génétique. La définition des allèles dépend de l'algorithme. Par exemple, 0 et 1 peuvent être des allèles d'algorithmes génétiques utilisés pour traiter les données binaires, et les algorithmes utilisés pour traiter les codes peuvent utiliser des pointeurs de fonction, etc. Dans notre scénario d'information secret, les allèles sont des lettres, des espaces et diverses marques de ponctuation dans l'alphabet.
• Chromosome: une séquence d'allèles donnée; Dans notre scénario, Homlk? Wsrzdj, xelpocv.xlf!
• gène: allèles à des endroits spécifiques des chromosomes. Pour l'homlk chromosome? Wsrzdj, le premier gène est H, le deuxième gène est O, le troisième gène est M, etc.
• Population: une collection d'un ou plusieurs chromosomes candidats proposés comme solution au problème.
• Générations: Population pendant les itérations spécifiques de l'algorithme. Les candidats d'une génération fournissent des gènes pour produire la prochaine génération de populations.
• Fitness: une mesure de la proximité d'un candidat à la solution souhaitée. Les chromosomes adaptatifs sont plus susceptibles de transmettre leurs gènes aux futurs candidats, tandis que les chromosomes moins adaptatifs sont plus susceptibles d'être jetés.
• SELECT: Le processus de sélection de certains candidats pour la reproduction (utilisé pour créer de nouveaux chromosomes de candidats) et de rejet d'autres candidats. Il existe une variété de stratégies de sélection qui varient dans la tolérance à la sélection des candidats plus faibles.
• Reproduction: Le processus de combinaison des gènes d'un ou plusieurs candidats pour produire de nouveaux candidats. Le chromosome donneur est appelé le père, et le chromosome produit est appelé la progéniture.
• Mutation: a introduit au hasard des gènes anormaux chez la progéniture pour empêcher la perte de diversité génétique dans de nombreuses générations.

Montrez-moi du code!

Je soupçonne que compte tenu de la vue d'ensemble avancée et de la liste des termes, vous pourriez être tenté de voir du code en ce moment. Examinons donc un code JavaScript qui résout notre problème d'information secrète. Pendant le processus de lecture, je vous invite à réfléchir aux méthodes qui peuvent être considérées comme un "code de passe-partout" et quelles implémentations sont plus étroitement liées au problème que nous essayons de résoudre:

// ... (Candidate class and GeneticAlgorithm class code as provided in the original text) ...

Nous définissons d'abord un objet de données candidat, juste pour coupler les chromosomes avec leurs scores de fitness. Pour plus de commodité, une méthode de tri statique est également attachée;

Ensuite, nous avons une classe Geneticalgorithme qui implémente l'algorithme génétique lui-même.

Le constructeur utilise des objets qui résolvent divers paramètres requis pour la simulation. Il fournit un moyen de spécifier l'alphabet génétique, les messages cibles et d'autres paramètres qui définissent les contraintes dans lesquelles la simulation s'exécutera. Dans l'exemple ci-dessus, nous nous attendons à une population de 100 candidats par génération. À partir de cela, seulement 40 chromosomes seront sélectionnés pour la reproduction. Nous avons 3% de chances d'introduire une mutation, et lorsqu'elle se produit, nous changerons jusqu'à deux gènes. La valeur des MAXGERATIONS est utilisée comme mesure de protection;

Il convient de mentionner que la population, la taille de sélection et le nombre maximal d'âges fournis lors de l'exécution de l'algorithme sont assez petits. Des problèmes plus complexes peuvent nécessiter un espace de recherche plus important, ce qui augmente à son tour l'utilisation de la mémoire de l'algorithme et le temps nécessaire pour fonctionner. Cependant, il est fortement recommandé d'utiliser des paramètres variants plus petits. S'ils deviennent trop gros, nous perdons tout avantage des candidats à l'élevage en fonction de la forme physique, et la simulation commence à devenir une recherche aléatoire.

Des méthodes comme RandomInt (), init () et run () peuvent être considérées comme un passe-partout. Mais ce n'est pas parce qu'il y a un passe-partout qu'il n'aura pas un impact pratique sur la simulation. Par exemple, les algorithmes génétiques utilisent fortement le hasard. Bien que la fonction Math.Random () intégrée convient à nos fins, pour d'autres problèmes, vous avez besoin d'un générateur aléatoire plus précis. Crypto.getRandomValues ​​() fournit des valeurs aléatoires cryptographiques plus fortes.

Les performances sont également une considération. Je m'efforce d'être clair et facile à comprendre dans cet article, mais n'oubliez pas que l'opération sera répétée. Vous pouvez vous retrouver à micro-optimiser le code dans une boucle, à utiliser des structures de données de mémoire plus efficaces et à aligner le code au lieu de le séparer en fonctions / méthodes, le tout sans égard à votre langage d'implémentation.

L'implémentation de calcFitness (), select (), reproduire () et même les méthodes stop () est spécifique au problème que nous essayons de résoudre.

CalcFitness () Renvoie une valeur qui mesure la forme physique d'un chromosome basé sur certains critères attendus - dans notre cas, c'est à quel point il correspond bien à un message secret. Le calcul de la forme physique est presque toujours spécifique à la situation; notre implémentation calcule l'erreur quadratique moyenne en utilisant la valeur ASCII de chaque gène, mais d'autres indicateurs peuvent être plus appropriés. Par exemple, je peux calculer la distance de Hamming ou la distance de Levinstein entre deux valeurs et même combiner plusieurs mesures. En fin de compte, il est important que la fonction de fitness renvoie des mesures utiles en fonction du problème à accomplir, pas seulement du booléen "fit" / "non ajusté".

SELECT () Méthode démontre une stratégie de sélection d'élite - seuls les candidats les plus appropriés de la population entière sont sélectionnés pour l'élevage. Comme je l'ai mentionné plus tôt, il existe d'autres stratégies, telles que la sélection du tournoi, qui sélectionne le candidat le plus approprié de l'ensemble des candidats individuels dans la population, et la sélection de Boltzmann, qui impose des candidats de plus en plus de plus en plus grands sur la sélection de la pression des candidats. Le but de ces différentes méthodes est de s'assurer que les chromosomes ont la possibilité de livrer des gènes qui pourraient s'avérer bénéfiques plus tard, même si cela peut ne pas être immédiatement apparent. Des descriptions approfondies de ces stratégies de sélection et d'autres, ainsi que d'exemples implémentations, sont facilement trouvées en ligne.

décrivant diverses stratégies de sélection

Il existe de nombreuses méthodes pour combiner les gènes. Notre code crée une progéniture en utilisant un crossover uniforme où chaque gène a la même probabilité de choisir parmi un parent. D'autres stratégies peuvent tendre vers le gène d'un parent plutôt que sur un autre. Une autre stratégie populaire est la traversée en K, où les chromosomes sont divisés en points k , résultant en 1 des fragments qui se combinent pour produire une progéniture. Les intersections peuvent être fixées ou sélectionnées au hasard.

Description de la stratégie de croisement en K

Nous ne sommes pas limités à deux chromosomes parents; Considérez un algorithme qui évolue des images en dessinant des polygones aléatoires. Dans ce cas, nos chromosomes sont implémentés sous forme de données d'image. Dans chaque génération, l'image la plus appropriée est sélectionnée parmi la population en tant que parent, et tous les enfants candidats sont générés en dessinant leurs propres polygones sur la copie parent. Les chromosomes / images parents sont les variations / dessins uniques du parent.

Application pratique de l'algorithme génétique

Les algorithmes génétiques peuvent être utilisés pour le divertissement et la rentabilité. Peut-être que les deux exemples les plus populaires d'application pratique des algorithmes génétiques sont les antennes en bande X évoluées par Boxcar 2D et NASA.

Boxcar 2D est une simulation qui utilise des algorithmes génétiques pour faire évoluer les meilleures "voitures" qui peuvent voyager à travers un terrain simulé. La voiture se compose de huit vecteurs aléatoires et relie les roues aux points aléatoires. Le site Web du projet se trouve sur boxcar2d.com, qui présente brièvement l'algorithme sur sa page à propos et fournit une liste de classement montrant certains des meilleurs conceptions. Malheureusement, le site utilise Flash et peut désormais être inaccessible à de nombreuses personnes - dans ce cas, divers enregistrements d'écran peuvent être trouvés sur YouTube si vous êtes curieux. Vous pouvez également consulter une simulation similaire (excellente) écrite par Rafael Matsunaga en utilisant la technologie HTML5, qui peut être trouvée sur rednuht.org/genetic_cars_2.

Les voitures ont évolué dans Boxcar 2D, des images du classement 2D BoxCar

En 2006, la Mission Space Technology 5 de la NASA a testé diverses nouvelles technologies dans l'espace. L'une de ces technologies est un nouveau type d'antenne conçu à l'aide d'algorithmes génétiques. La conception de nouvelles antennes peut être un processus très coûteux et long. Il nécessite une expertise spéciale et souvent des revers se produisent lorsque les modifications de la demande ou les prototypes ne fonctionnent pas comme prévu. Le temps de création d'antennes évolué est plus court, avec un gain plus élevé et une consommation d'énergie plus faible. Le texte intégral de l'article discutant du processus de conception est disponible gratuitement en ligne (conception de l'antenne automatisée à l'aide d'algorithmes évolutifs). Des algorithmes génétiques ont également été utilisés pour optimiser les conceptions d'antennes existantes pour des performances plus élevées.

Les meilleures antennes évolutives de leur catégorie, les images proviennent des articles génétiques de conception d'antenne automatisés

ont même été utilisés dans la conception Web! Un projet avancé d'Elijah Mensch (optimisation de la conception du site Web en appliquant des algorithmes génétiques interactifs) les utilise pour optimiser les carrousels de l'article de presse en manipulant les règles CSS et en notant la forme physique à l'aide des tests A / B.

La meilleure mise en page pour les première et neuvième générations, l'image provient du document sur la conception optimisée du site Web

Conclusion

Jusqu'à présent, vous devriez avoir une compréhension de base de ce que sont les algorithmes génétiques et être suffisamment familier avec leur vocabulaire pour interpréter toutes les ressources que vous pourriez rencontrer dans votre propre recherche. Cependant, la compréhension des théories et des termes n'est que la moitié du travail. Si vous prévoyez d'écrire votre propre algorithme génétique, vous devez également comprendre votre problème spécifique. Avant de commencer, voici quelques questions importantes à vous poser:

• Comment représenter mon problème en tant que chromosome? Qu'est-ce que mon allèle valide?
• Est-ce que je sais quel est le but? C'est-à-dire que suis-je à la recherche? Est-ce une valeur spécifique ou une solution avec une forme physique dépassant un certain seuil?
• Comment quantifier la forme physique des candidats?
• Comment combiner et muter les candidats pour générer de nouvelles solutions de candidats?

J'espère que je vous aidera également à comprendre comment les programmes s'inspirent de la nature - non seulement en forme, mais aussi en processus et en fonction. N'hésitez pas à partager vos propres pensées sur le forum.

Des questions fréquemment posées sur les algorithmes génétiques

• Qu'est-ce qu'un algorithme génétique (GA)? Les algorithmes génétiques sont une technique de recherche et d'optimisation heuristique inspirée du processus de sélection naturelle. Il est utilisé pour trouver des solutions approximatives aux problèmes d'optimisation et de recherche grâce aux principes de l'évolution de la simulation.
• Comment fonctionne les algorithmes génétiques? Les algorithmes génétiques fonctionnent en évoluant des populations de solutions candidates au cours des générations successives. Le processus comprend la sélection, le croisement (recombinaison), la mutation et l'évaluation des individus dans la population, visant à améliorer itérativement la qualité de la solution.
• Quels types de problèmes sont-ils adaptés aux algorithmes génétiques? Les algorithmes génétiques sont largement utilisés et peuvent être appliqués à une variété de problèmes d'optimisation et de recherche, y compris, mais sans s'y limiter, la planification, le routage, l'apprentissage automatique et l'optimisation des fonctions.
• Comment sélectionner les paramètres des algorithmes génétiques? Des paramètres tels que la taille de la population, la variabilité et le taux de croisement dépendent des caractéristiques du problème spécifique et de l'espace de solution. L'expérience et le réglage sont des pratiques courantes pour trouver les meilleures valeurs de paramètres pour un problème donné.
• Quel est le rôle de la fonction de fitness dans les algorithmes génétiques? La fonction de fitness quantifie comment les solutions individuelles fonctionnent dans un problème donné. Il guide le processus de sélection et facilite les solutions qui contribuent positivement aux objectifs d'optimisation.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!