Algorithme génétique compact

L’objectif de traitement de l’information de l’algorithme est de simuler le comportement d’un algorithme génétique avec une empreinte mémoire beaucoup plus petite (sans nécessiter le maintien d’une population). Ceci est réalisé en maintenant un vecteur qui spécifie la probabilité d’inclure chaque composant dans une solution dans de nouvelles solutions candidates. Les solutions candidates sont générées de manière probabiliste à partir du vecteur et les composants de la meilleure solution sont utilisés pour apporter de petites modifications aux probabilités dans le vecteur.

L’algorithme génétique compact maintient un vecteur prototype à valeur réelle qui représente la probabilité que chaque composant soit exprimé dans une solution candidate. L’algorithme suivant fournit un pseudocode de l’algorithme génétique compact pour maximiser une fonction de coût. Le paramètre n indique le nombre de probabilités de mise à jour des bits en conflit à chaque itération.

Le paramètre de mise à jour vectorielle (n) influence la quantité de mises à jour des probabilités à chaque itération de l’algorithme. Le paramètre de mise à jour du vecteur (n) peut être considéré comme comparable au paramètre de taille de la population dans l’algorithme génétique. Les premiers résultats démontrent que le cGA peut être comparable à un algorithme génétique standard sur les problèmes classiques d’optimisation de chaînes binaires (tels que OneMax). L’algorithme peut être considéré comme ayant convergé si les probabilités vectorielles sont toutes égales à 0 ou 1.