Qu’est-ce que les algorithmes génétiques ?

Au cours des dernières années, il y a eu un formidable buzz autour de l’intelligence artificielle (IA). De grandes entreprises comme Google, Apple et Microsoft travaillent activement sur le sujet. En fait, l’IA est un terme générique qui recouvre de nombreux objectifs, approches, outils et applications. Les algorithmes génétiques (AG) ne sont qu’un des outils de recherche intelligente à travers de nombreuses solutions possibles.

L’AG est une technique métaheuristique de recherche et d’optimisation basée sur les principes présents dans l’évolution naturelle. Elle appartient à une classe plus large d’algorithmes évolutionnaires.

GA maintient une population de chromosomes-un ensemble de solutions potentielles pour le problème. L’idée est que “l’évolution” trouvera une solution optimale pour le problème après un certain nombre de générations successives – semblable à la sélection naturelle.

GA imite trois processus évolutifs : la sélection, le croisement de gènes et la mutation.

Similaire à la sélection naturelle, le concept central de la sélection de GA est la fitness. Les chromosomes qui sont plus aptes ont une meilleure chance de survie. La fitness est une fonction qui mesure la qualité de la solution représentée par le chromosome. En substance, chaque chromosome de la population représente les paramètres d’entrée. Par exemple, si votre problème contient deux paramètres d’entrée, tels que le prix et le volume des transactions, chaque chromosome sera logiquement composé de deux éléments. La façon dont les éléments sont codés dans le chromosome est un autre sujet.

Lors de la sélection, les chromosomes forment des paires de parents pour la reproduction. Chaque enfant prend des caractéristiques de ses parents. Fondamentalement, l’enfant représente une recombinaison des caractéristiques de ses parents : Certaines caractéristiques proviennent d’un parent et d’autres d’un autre. En plus de la recombinaison, certaines des caractéristiques peuvent muter.

Parce que les chromosomes plus aptes produisent plus d’enfants, chaque génération suivante aura une meilleure aptitude. A un moment donné, une génération contiendra un chromosome qui représentera une solution suffisamment bonne pour notre problème.

L’AG est puissante et largement applicable pour les problèmes complexes. Il existe une grande classe de problèmes d’optimisation qui sont assez difficiles à résoudre par les techniques d’optimisation conventionnelles. Les algorithmes génétiques sont des algorithmes efficaces dont la solution est approximativement optimale. Les applications bien connues comprennent l’ordonnancement, le transport, le routage, les technologies de groupe, la conception d’agencement, la formation de réseaux neuronaux, et bien d’autres.

Mise en pratique

L’exemple que nous allons examiner peut être considéré comme le “Hello World” des AG. Cet exemple a été initialement donné par J. Freeman dans Simulating Neural Networks with Mathematica. Je l’ai repris de Genetic Algorithms and Engineering Design de Mitsuo Gen et Runwei Cheng.

Le Word-Matching Problem tente de faire évoluer une expression avec un algorithme génétique. Initialement, l’algorithme est censé “deviner” la phrase “être ou ne pas être” à partir de listes de lettres générées de manière aléatoire.

Puisqu’il y a 26 lettres possibles pour chacun des 13 emplacements de la liste, la probabilité que nous obtenions la phrase correcte de manière purement aléatoire est (1/26)^13=4.03038×10-19, ce qui représente environ deux chances sur un (Gen & Chong, 1997).

Nous allons définir le problème un peu plus largement ici, ce qui rendra la solution encore plus difficile. Supposons que nous ne soyons pas limités à la langue anglaise ou à une phrase spécifique. Nous pouvons nous retrouver à traiter 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 un langage tout court.

Disons que notre adversaire a pensé à une phrase arbitraire, incluant les espaces blancs. Nous connaissons la longueur de la phrase et le nombre de symboles dans l’alphabet. C’est la seule connaissance que nous avons. Après chaque supposition, notre adversaire nous dit combien de lettres sont en 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 ” be ” sera représenté par .

Nous démontrerons toutes les étapes par des extraits de code Java, mais la connaissance de Java n’est pas nécessaire pour comprendre chaque étape.

Noyau de l’algorithme génétique

Nous pouvons commencer par une mise en œuvre générale de l’algorithme génétique :

public void find() { // Initialization List<T> population = Stream.generate(supplier) .limit(populationSize) .collect(toList()); // Iteration while (!termination.test(population)) { // Selection population = selection(population); // Crossover crossover(population); // Mutation mutation(population); }}

C’est l’ensemble simple d’étapes dont chaque AG se compose plus ou moins. À l’étape d’initialisation, nous générons une population initiale de phrases. La taille de la population est déterminée par populationSize. La façon dont la phrase est générée dépend de la mise en œuvre de la supplier.

Au cours de l’étape d’itération, nous faisons évoluer la population jusqu’à ce que les conditions de terminaison soient remplies dans le test de la boucle while. Les conditions de terminaison peuvent inclure à la fois le nombre de générations et la correspondance exacte d’une des phrases de la population. Le termination encapsule une implémentation exacte.

Au cours de chaque itération, nous effectuons les étapes typiques du GA :

1. Préparer une sélection sur la population basée sur la fitness des chromosomes.
2. Produire une nouvelle “génération” via l’opération de crossover.
3. Préparer une recombinaison de certaines lettres dans certaines phrases.

Le cœur de l’algorithme est très simple et agnostique au domaine. Il sera le même pour tous les problèmes. Ce que vous devrez régler, c’est l’implémentation des opérateurs génétiques. Ensuite, nous allons examiner de près chacun des opérateurs de l’AG précédemment mentionnés.

Sélection

Comme nous le savons déjà, la sélection est un processus qui consiste à trouver des successeurs aux chromosomes actuels – les chromosomes qui sont plus adaptés à notre problème. Pendant la sélection, nous devons nous assurer que les chromosomes avec une meilleure fitness ont une meilleure chance de survie.

private List<T> selection(List<T> population) { final double fitnesses = population.stream() .mapToDouble(fitness) .toArray(); final double totalFitness = DoubleStream.of(fitnesses).sum(); double sum = 0; final double probabilities = new double; for (int i = 0; i < fitnesses.length; i++) { sum += fitnesses / totalFitness; probabilities = sum; } probabilities = 1; return range(0, probabilities.length).mapToObj(i -> { int index = binarySearch(probabilities, random()); if (index < 0) { index = -(index + 1); } return population.get(index); }).collect(toList());}

L’idée derrière cette implémentation est la suivante : La population est représentée sous forme de plages conséquentes sur l’axe numérique. L’ensemble de la population est comprise entre 0 et 1.

Le morceau de la plage que prend un chromosome est proportionnel à sa fitness. Il en résulte qu’un chromosome plus apte obtient un plus grand morceau. Ensuite, nous jetons un coup d’œil aléatoire à un nombre entre 0 et 1 et trouvons une plage qui inclut ce nombre. De toute évidence, les plages plus grandes ont plus de chances d’être sélectionnées, et donc les chromosomes plus aptes ont une meilleure chance de survie.

Parce que 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 convertit un chromosome en un double arbitraire qui représente le fitness du chromosome.

Dans le code, nous trouvons les taux de fitness pour tous les chromosomes de la population, et nous trouvons également le fitness total. Dans la boucle for, nous effectuons une somme cumulative sur les probabilités mises à l’échelle par la fitness totale. Mathématiquement, cela devrait aboutir à ce que la variable finale ait la valeur 1. En raison de l’imprécision de la virgule flottante, nous ne pouvons pas le garantir, donc nous la fixons à 1 juste pour être sûrs.

Enfin, pour un nombre de fois égal au nombre de chromosomes d’entrée, nous générons un nombre aléatoire, trouvons une plage qui inclut le nombre, puis sélectionnons le chromosome correspondant. Comme vous pouvez le remarquer, le même chromosome peut être sélectionné plusieurs fois.

Croisement

Maintenant, nous devons aux chromosomes de se “reproduire”.

private void crossover(List<T> population) { final int indexes = range(0, population.size()) .filter(i-> random() < crossoverProbability) .toArray(); shuffle(Arrays.asList(indexes)); for (int i = 0; i < indexes.length / 2; i++) { final int index1 = indexes; final int index2 = indexes; final T value1 = population.get(index1); final T value2 = population.get(index2); population.set(index1, crossover.apply(value1, value2)); population.set(index2, crossover.apply(value2, value1)); }}

Avec la probabilité prédéfinie crossoverProbability, nous sélectionnons les parents pour la reproduction. Les parents sélectionnés sont mélangés, permettant à toutes les combinaisons de se produire. 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 garder la taille de la population identique. Les enfants remplacent leurs parents dans la population.

Mutation

Enfin, nous effectuons une recombinaison des caractéristiques.

private void mutation(List<T> population) { for (int i = 0; i < population.size(); i++) { if (random() < mutationProbability) { population.set(i, mutation.apply(population.get(i))); } }}

Avec une probabilité prédéfinie mutationProbability, nous effectuons une “mutation” sur les chromosomes. La mutation elle-même est définie par mutation.

Configuration de l’algorithme spécifique au problème

Maintenant, regardons quel type de paramètres spécifiques au problème nous devons fournir à notre implémentation générique.

private BiFunction<T, T, T> crossover;private double crossoverProbability;private ToDoubleFunction<T> fitness;private Function<T, T> mutation;private double mutationProbability;private int populationSize = 100;private Supplier<T> supplier;private Predicate<Collection<T>> termination;

Les paramètres, respectivement, sont :

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. Fonction de terminaison

Voici la configuration pour notre problème :

new GeneticAlgorithm<char>() .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 de crossover et probabilité

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 crossover est de 0.25, nous nous attendons donc à ce qu’en moyenne 25 % des chromosomes soient sélectionnés pour le crossover. Nous effectuons une procédure simple pour le crossover d’une paire de chromosomes. Nous générons un nombre aléatoire n à partir de la plage , où length est la longueur d’un chromosome. Maintenant, nous accouplons la paire sélectionnée en prenant les premiers caractères n d’un chromosome et les caractères restants après du second.

Fonction de fitness

private double fitness(char value) { return range(0, value.length) .filter(i -> value == expected) .count();}

La fonction de fitness compte simplement le nombre de correspondances entre la phrase cible et le chromosome donné.

Opérateur de mutation et 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 = ALPHABET; } return result;}

L’opération de mutation est effectuée indépendamment sur chaque chromosome. La probabilité de mutation est de 0,05, on s’attend donc à ce que, en moyenne, 5 % de la population soit 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 < length; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); result = ALPHABET; } return result;}

Le fournisseur génère des phrases aléatoires en prenant des lettres aléatoires de l’alphabet. Chaque phrase a une longueur constante prédéfinie.

Fonction de terminaison

private boolean termination(Collection<char> chars) { count++; final Optional<char> 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 de terminaison compte le nombre d’appels et renvoie true s’il y a soit une correspondance exacte, soit si le nombre de générations atteint 3 000.

Exécution

Maintenant nous sommes prêts à tester notre algorithme. Si vous l’exécutez plusieurs fois, vous remarquerez que toutes les exécutions ne sont pas réussies. À chaque fois, le nombre d’itérations sera différent. Cela est dû à la nature probabiliste de l’algorithme. L’algorithme peut être amélioré sur plusieurs points. Vous pouvez jouer avec les probabilités de croisement et de mutation.

La diminution du nombre conduira à une solution stable mais lente. Un plus petit nombre de chromosomes sera affecté par les opérateurs génétiques et, par conséquent, plus d’itérations seront nécessaires pour la solution.

L’augmentation des nombres accélérera l’algorithme, mais rendra également la solution instable. Les chromosomes aptes ne seront pas seulement conservés, mais ils seront aussi affectés par les opérateurs génétiques. Par conséquent, ils perdront leurs “bons” gènes.

Il est important de trouver un bon équilibre. Augmenter le nombre d’itérations donnera à l’algorithme plus d’opportunités de trouver une solution mais, en contrepartie, cela prendra plus de temps. Vous pouvez également appliquer différentes méthodes de croisement et de mutation. Une bonne sélection de ces opérateurs améliorera drastiquement la qualité de la solution.

Nous n’avons couvert que la pointe de l’iceberg ici. Nous avons pris un exemple qui n’a qu’une seule entrée, et l’entrée peut être facilement présentée comme un chromosome. Les opérateurs génétiques sont clairs et simples.

Il est très intéressant de prendre un problème du monde réel et d’y appliquer l’algorithme génétique. Vous découvrirez différentes approches dans l’encodage des données d’entrée réelles ainsi que différentes implémentations de crossover et de mutation.

Si un problème peut être exprimé par un ensemble de paramètres que nous devons deviner pour optimiser une métrique, nous pouvons rapidement mettre en place un AG que nous pouvons utiliser pour le résoudre.

Un des problèmes les plus intéressants est l’enseignement des réseaux de neurones artificiels. Nous pouvons définir les paramètres optimisables comme étant les forces des synapses, et la métrique de fitness comme étant le pourcentage d’entrées pour lesquelles notre réseau neuronal a donné la bonne réponse. Après cela, nous pouvons nous asseoir et laisser notre réseau neuronal évoluer vers la solution idéale que nous souhaitons. Ou du moins jusqu’à ce que nous obtenions quelque chose d’assez bon, car l’évolution prend du temps.