Evolution grammaticale pour l'algorithme génétique

L’algorithme d’évolution grammaticale s’inspire du processus biologique utilisé pour générer une protéine à partir de matériel génétique ainsi que du processus évolutif génétique plus large. Le génome est composé d’ADN comme une chaîne de blocs de construction qui sont transcrits en ARN. Les codons d’ARN sont à leur tour traduits en séquences d’acides aminés et utilisés dans la protéine. La protéine résultante dans son environnement est le phénotype.

Le phénotype est un programme informatique créé à partir d’un génome à base de chaînes binaires. Le génome est décodé en une séquence d’entiers qui sont à leur tour mappés sur des règles pré-définies qui constituent le programme. La cartographie du génotype au phénotype est un processus un-à-plusieurs qui utilise une fonction d’emballage. C’est comme le processus biologique observé dans de nombreuses bactéries, virus et mitochondries, où le même matériel génétique est utilisé dans l’expression de différents gènes. La cartographie ajoute de la robustesse au processus à la fois dans la capacité à adopter des opérateurs génétiques utilisés pendant le processus évolutif sur la représentation sous-symbolique et la transcription de programmes exécutables bien formés à partir de la représentation.

L’objectif de Grammatical Evolution est d’adapter un programme exécutable à une fonction objective spécifique au problème. Ceci est réalisé grâce à un processus itératif avec des substituts de mécanismes évolutifs tels que la descente avec variation, la mutation génétique et la recombinaison, la transcription génétique et l’expression des gènes. Une population de programmes est développée sous une forme sous-symbolique en tant que chaînes binaires de longueur variable et mappée à une forme symbolique et bien structurée en tant que grammaire sans contexte pour l’exécution.

Une grammaire est définie sous forme normale Backus (BNF), qui est une grammaire sans contexte exprimée comme une série de règles de production comprenant des terminaux et des non-terminaux. Une représentation de chaîne binaire de longueur variable est utilisée pour le processus d’optimisation. Les bits sont lus à partir du génome des solutions candidates en blocs de 8 appelés codon et décodés en un entier (compris entre 0 et 2 ^ 8 – 1). Si la fin de la chaîne binaire est atteinte lors de la lecture d’entiers, le processus de lecture revient en boucle au début de la chaîne, créant ainsi un génome circulaire. Les entiers sont mappés aux expressions de la BNF jusqu’à ce qu’une expression syntaxiquement correcte complète soit formée. Cela peut ne pas utiliser un génome entier de solutions, ou utiliser le génome décodé plus d’une fois étant donné sa nature circulaire.

L’évolution grammaticale a été conçue pour optimiser les programmes (tels que les équations mathématiques) pour des fonctions de coût spécifiques. Les opérateurs génétiques classiques utilisés par l’algorithme génétique peuvent être utilisés dans l’algorithme d’évolution grammaticale, tels que les mutations ponctuelles et le croisement en un point. Des opérateurs génétiques supplémentaires peuvent être utilisés avec des représentations de longueur variable telles que des segments de codon, la duplication (ajouter à la fin), le nombre de codons sélectionnés au hasard et la suppression.