Que sont les algorithmes génétiques?
Ces dernières années, il y a eu un tollé concernant l'intelligence artificielle (IA). De grandes entreprises comme Google, Apple et Microsoft travaillent activement sur ce problème. En fait, l'IA n'est qu'un parapluie qui couvre de nombreux objectifs, approches, outils et applications. Les algorithmes génétiques (GA) ne sont que l'un des outils intelligents à la recherche de nombreuses solutions possibles.
différence entre c corp et s corp
AG est une recherche méta-heuristique ainsi qu'une technique d'optimisation basée sur des principes présents dans l'évolution naturelle. Il appartient à une classe plus longue d'algorithmes évolutifs.
L'AG maintient un population chromosomique —Un ensemble de solutions possibles au problème. L'idée est que «l'évolution» trouve une solution optimale au problème après un certain nombre de générations successives - similaire à la sélection naturelle.
AG imite trois processus évolutifs: la sélection, le croisement chromosomique et la mutation.
Tout comme la sélection naturelle, le concept central de la sélection AG est l'adaptation. Les chromosomes qui s'adaptent mieux ont de meilleures chances de survie. L'adaptation est une fonction qui mesure la qualité de la solution représentée par le chromosome. Essentiellement, chaque chromosome au sein de la population représente les paramètres d'entrée, tels que le volume et le taux d'échange, chaque chromosome, logiquement, sera composé de deux éléments. La manière dont les éléments sont codés dans le chromosome est une autre question.
Lors de la sélection, les chromosomes forment des paires de Parents pour la la reproduction . Chaque enfant prend les caractéristiques de ses parents. Fondamentalement, l'enfant représente une recombinaison des caractéristiques de ses parents: certaines caractéristiques sont tirées d'un parent et d'autres de l'autre parent. En plus de la recombinaison, certaines des caractéristiques peuvent subir une mutation .
Puisque les chromosomes les plus appropriés produisent plus d'enfants, chaque génération suivante sera plus appropriée. À un moment donné, une génération contiendra un chromosome qui représente une assez bonne solution à notre problème.
AG est puissant et largement applicable à des problèmes complexes. Il existe une classe étendue de problèmes d'optimisation qui sont quelque peu difficiles à résoudre en utilisant des techniques d'optimisation conventionnelles. Les algorithmes génétiques sont des algorithmes efficaces qui ont des solutions approximativement optimales. Les applications bien connues incluent la planification, le transport, la planification d'itinéraire, les technologies de groupe, la conception de plans, la formation de réseaux neuronaux et bien d'autres.
Mettre les choses en pratique
L'exemple que nous allons voir peut être considéré comme «Hello World» d'AG. Cet exemple a été initialement présenté par J. Freeman dans Simulation de réseaux de neurones avec Mathematica . Je l'ai pris de Algorithmes génétiques et conception technique par Mitsuo Gen et Runwei Cheng.
Le problème de la simulation mondiale tente de faire évoluer une expression avec un algorithme génétique. Au départ, l'algorithme doit «deviner» la phrase «être ou ne pas être» à partir de listes de lettres générées aléatoirement.
Puisqu'il y a 26 lettres possibles pour chacun des 13 emplacements [à l'exclusion des blancs] dans la liste, la chance que nous obtenions la phrase correcte purement au hasard est (1/26) ^ 13 = 4,03038 × 10-19, donc ce qui est environ deux chances sur un [trillion] (Gen & Chong, 1997).
Nous allons définir un peu plus le problème ici en rendant la solution encore plus difficile. Supposons que nous ne soyons pas limités à la langue anglaise ou à une phrase spécifique. Nous pouvons finir par avoir affaire à n'importe quel alphabet, ou même à n'importe quel ensemble de symboles. Nous n'avons aucune connaissance de la langue. Nous ne savons même pas s'il existe une langue.
Disons que notre adversaire a pensé à une phrase arbitraire, y compris des blancs. Nous connaissons la longueur de la phrase et le nombre de symboles dans l'alphabet. C'est la seule connaissance que nous ayons. Après chaque supposition, notre adversaire nous dit combien de lettres sont à sa place.
Chaque chromosome est une séquence d'indices des symboles de l'alphabet. Si nous parlons de l'alphabet anglais, alors «a» sera représenté par 0, «b» par 1, «c» par 2, et ainsi de suite. Ainsi, par exemple, le mot «être» sera représenté par [4, 1].
Nous démontrerons toutes les étapes à travers des morceaux de code Java, mais les connaissances en Java il n'est pas nécessaire de comprendre chaque étape.
comment obtenir la certification aws
Le centre de l'algorithme génétique
Nous pouvons commencer par l'implémentation générale de l'algorithme génétique:
public void find() { // Initialization List population = Stream.generate(supplier) .limit(populationSize) .collect(toList()); // Iteration while (!termination.test(population)) { // Selection population = selection(population); // Crossover crossover(population); // Mutation mutation(population); } } Il s'agit d'un ensemble d'étapes simples que chaque AG devrait suivre. Dans la première étape, nous générons une population initiale de phrases. La taille de la population est déterminée par populationSize. Et la façon dont cette phrase est générée dépend de l'implémentation de supplier.
Au cours de l'étape d'itération, nous faisons évoluer la population jusqu'à ce que les conditions du terme soient remplies, dans le nœud test while. Les conditions de terme peuvent inclure le nombre de générations et la correspondance parfaite de l'une des phrases de la population. Le termination encapsule une implémentation exacte.
Dans chaque itération, nous effectuons les étapes typiques de l'AG:
- Il effectue une sélection sur la population en adéquation chromosomique.
- Produit une nouvelle 'génération' via l'opération de croisement.
- Il effectue une recombinaison de certaines lettres dans certaines phrases.
Le cœur de l'algorithme est très simple et indépendant du domaine. Ce serait la même chose pour tous les problèmes. Ce que vous devez ajuster, c'est la mise en œuvre d'opérateurs génétiques. Ensuite, nous examinerons de plus près chacun des opérateurs AG susmentionnés.
comment faire votre propre verre google
Sélection
Comme nous le savons déjà, la sélection est un processus fait pour trouver des successeurs pour les chromosomes actuels - les chromosomes les mieux adaptés à notre problème. Lors de la sélection, nous devons nous assurer que les meilleurs chromosomes correspondants ont de meilleures chances de survie.
private List selection(List population) { final double[] fitnesses = population.stream() .mapToDouble(fitness) .toArray(); final double totalFitness = DoubleStream.of(fitnesses).sum(); double sum = 0; final double[] probabilities = new double[fitnesses.length]; for (int i = 0; i { int index = binarySearch(probabilities, random()); if (index <0) { index = -(index + 1); } return population.get(index); }).collect(toList()); } L'idée de cette implémentation est la suivante: La population est représentée comme des traits conséquents sur l'axe numérique. La population entière est comprise entre 0 et 1.
Le morceau de la série qu'un chromosome prend est proportionnel à son adéquation. Il en résulte un chromosome beaucoup plus approprié qui prend une plus grande partie. Ensuite, nous choisissons un nombre au hasard entre 0 et 1 et trouvons une série qui comprend ce nombre. De toute évidence, les plus grandes séries ont de meilleures chances d'être sélectionnées, par conséquent, les chromosomes les plus appropriés ont de meilleures chances de survie.
Comme nous ne connaissons pas les détails de la fonction de fitness, nous devons normaliser les valeurs de fitness. La fonction de fitness est représentée par fitness, qui transforme un chromosome en un double arbitraire qui représente la fitness du chromosome.
Dans le code, nous trouvons un taux de correspondance pour tous les chromosomes de la population et nous trouvons également la correspondance totale. À l'intérieur du nœud for, nous exécutons une somme cumulative sur les probabilités diminuées par l'ajustement total. Mathématiquement, cela devrait avoir pour résultat que la variable finale a une valeur de 1. En raison de l'imprécision de la virgule flottante, nous ne pouvons pas garantir cela, donc nous la définissons sur 1 pour être sûr.
Enfin, pendant une durée égale au nombre de chromosomes entrants, nous générons un nombre aléatoire, trouvons une série qui comprend le nombre, puis sélectionnons le chromosome correspondant. Comme vous l'avez peut-être remarqué, le même chromosome peut être sélectionné plusieurs fois.
Crossover
Maintenant, nous avons besoin des chromosomes pour «se reproduire».
private void crossover(List population) { final int[] indexes = range(0, population.size()) .filter(i-> random() Avec la probabilité prédéfinie comme crossoverProbability, nous sélectionnons les parents pour la reproduction. Les parents sélectionnés sont mixtes, ce qui permet de faire n'importe quelle combinaison. Nous prenons des paires de parents et appliquons l'opérateur crossover. Nous appliquons l'opérateur deux fois pour chaque paire car nous devons conserver la même taille de population. Les enfants remplacent les parents dans la population.
code python pour extraire des données de twitter
Mutation
Enfin, nous procédons à la recombinaison des caractéristiques.
private void mutation(List population) { for (int i = 0; i Avec la probabilité mutationProbability prédéfini, nous réalisons la 'mutation' dans les chromosomes. La mutation en tant que telle est définie par mutation.
Configuration de l'algorithme spécifique au problème
Voyons maintenant quel type de paramètres de problème spécifiques nous devons fournir pour notre implémentation générique.
private BiFunction crossover; private double crossoverProbability; private ToDoubleFunction fitness; private Function mutation; private double mutationProbability; private int populationSize = 100; private Supplier supplier; private Predicate termination; Les paramètres sont respectivement: 1. Opérateur de croisement 2. Probabilité de croisement 3. Fonction d'aptitude 4. Opérateur de mutation 5. Probabilité de mutation 6. Taille de la population 7. Fournisseur de chromosomes pour la population initiale 8. Terme de fonction
Voici la configuration de notre problème:
new GeneticAlgorithm() .setCrossover(this::crossover) .setCrossoverProbability(0.25) .setFitness(this::fitness) .setMutation(this::mutation) .setMutationProbability(0.05) .setPopulationSize(100) .setSupplier(() -> supplier(expected.length)) .setTermination(this::termination) .find() Opérateur et probabilité de croisement
private char[] crossover(char[] value1, char[] value2) { final int i = (int) round(random() * value1.length); final char[] result = new char(value1.length); System.arraycopy(value1, 0, result, 0, i); System.arraycopy(value2, i, result, i, value2.length - i); return result; } La probabilité de croisement est de 0,25, nous prévoyons donc qu'en moyenne 25% des chromosomes seront sélectionnés pour le croisement. Nous effectuons une procédure simple, pour le croisement d'une paire de chromosomes. Nous générons un nombre aléatoire n pour la sélection [0..length], où length est la longueur du chromosome. Maintenant, nous rejoignons la paire sélectionnée en prenant le premier symbole n de l'un des chromosomes et le reste des symboles après le second.
Fonction adéquate
private double fitness(char[] value) { return range(0, value.length) .filter(i -> value[i] == expected[i]) .count(); } La fonction appropriée compte simplement le nombre de combinaisons entre la phrase clé et le chromosome donné.
Opérateur de mutation et de probabilité
private char[] mutation(char[] value) { final char[] result = Arrays.copyOf(value, value.length); for (int i = 0; i <2; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); int location = (int) round(random() * (value.length - 1)); result[location] = ALPHABET[letter]; } return result; } L'opération de mutation se déroule indépendamment sur chaque chromosome. La probabilité de mutation est de 0,05, nous prévoyons donc qu'en moyenne cinq pour cent de la population sera mutée. Nous mutons en choisissant une position de lettre aléatoire et en remplaçant sa valeur par une lettre aléatoire de l'alphabet. Nous le faisons deux fois pour chaque chromosome muté.
Fournisseur
private char[] supplier(int length) { final char[] result = new char(length); for (int i = 0; i Le fournisseur génère des phrases au hasard en prenant les lettres de l'alphabet de manière égale au hasard. Chaque phrase a une longueur constante prédéfinie.
Fonction de terme
private boolean termination(Collection chars) { count++; final Optional result = chars.stream() .filter(value -> round(fitness(value)) == expected.length) .findAny(); if (result.isPresent()) { System.out.println('Count: ' + count); System.out.println(result.get()); return true; } final boolean terminated = count == 3000; if (terminated) { chars.forEach(System.out::println); } return terminated; } La fonction term compte le nombre d'appels et renvoie true, s'il existe déjà une correspondance exacte ou si le nombre de générations atteint 3000.
Exécution
Nous sommes maintenant prêts à tester notre algorithme. Si vous l'exécutez plusieurs fois, vous remarquerez que toutes les exécutions ne réussissent pas. A chaque fois, le nombre d'itérations sera différent. Cela est dû à une nature probabiliste de l'algorithme. L'algorithme a plusieurs points où il peut être amélioré. Vous pouvez jouer avec les probabilités de croisement et de mutation.
didacticiel de l'api web asp net
Réduisez le nombre à une solution stable mais lente. Un plus petit nombre de chromosomes sera affecté par les opérateurs génétiques, donc plus d'itérations seront nécessaires pour la solution.
L'augmentation des nombres accélérera l'algorithme, mais cela rendra également la solution instable. Les chromosomes appropriés seront non seulement préservés, mais seront également affectés par les opérateurs génétiques. Pour cette raison, ils perdront leurs «bons» gènes.
Il est important de trouver un bon équilibre. L'augmentation du nombre d'itérations donnera à l'algorithme plus de possibilités de trouver une solution mais, d'un autre côté, cela prendra plus de temps. Appliquez également différentes méthodes de croisement et de mutation. Une bonne sélection de ces opérateurs améliorera considérablement la qualité de la solution.
Suivant?
Nous n'avons couvert que la pointe de l'iceberg. Nous prenons un exemple qui n'a qu'une seule entrée et cela peut être facilement présenté comme un chromosome. Les opérateurs génétiques sont simples.
Il est très intéressant de prendre un problème de la vie réelle et d'y appliquer l'algorithme génétique. Vous découvrirez différentes approches pour encoder les entrées de données réelles, ainsi que différentes implémentations de croisement et de mutation.
Si un problème peut être exprimé à travers un ensemble de paramètres que nous devons deviner pour optimiser une métrique, nous pouvons rapidement établir un AG que nous pouvons utiliser pour le résoudre.
L'un des problèmes les plus intéressants est l'enseignement des réseaux de neurones artificiels. Nous pouvons définir les paramètres optimisés pour être des forces de synapse et pour que la métrique appropriée soit le pourcentage d'entrées pour lesquelles nos réseaux de neurones ont donné la bonne réponse. Après cela, nous pouvons nous détendre et laisser nos réseaux de neurones évoluer vers la solution idéale que nous souhaitons. Ou du moins jusqu'à ce que nous ayons quelque chose d'assez bon, car l'évolution prend du temps.
