Un design évolutif pour des solutions révolutionnaires

Les algorithmes génétiques représentent une catégorie des algorithmes évolutionnaires, inspirés par l’évolution biologique des organismes vivants. Ils traduisent les mécanismes de l’évolution en un processus computationnel capable de résoudre des problèmes complexes et d’identifier des solutions adaptées.

Pour concevoir de tels algorithmes, nous devons commencer par modéliser ou formuler précisément ce problème. Cela consiste en la définition des paramètres, des contraintes et des objectifs à optimiser. Cette phase est décisive, car elle permet de transformer un problème complexe en une structure organisée et logique, facilitant ainsi l’analyse et mettant en lumière les paramètres critiques ainsi que les limitations du problème à résoudre.

Ensuite, une fois les solutions potentielles modélisées, nous générons un certain nombre de ces solutions, soit de manière aléatoire, soit en intégrant des connaissances préexistantes, pour former la population initiale. Cet ensemble de solutions constitue la base à partir de laquelle les solutions vont évoluer afin d’atteindre un optimum ou de s’en rapprocher. Pour cela, chaque solution est évaluée à l’aide d’une "fonction fitness", qui mesure son aptitude à répondre aux objectifs définis. Les critères de fitness peuvent inclure la robustesse, l’efficacité, le coût ou encore la performance.

Les solutions les plus performantes, c’est-à-dire celles ayant les meilleurs scores de fitness, sont sélectionnées pour contribuer à la génération suivante. Cette étape, appelée sélection, vise à favoriser les solutions qui se rapprochent le plus de l’optimum. L’approche où les solutions ayant les meilleurs scores sont systématiquement choisies est appelée élitisme. Cependant, d’autres types de sélection existent, comme la roulette (Roulette Wheel Selection), le tournoi (Tournament Selection), la sélection par rang (Rank Selection), et la sélection stochastique universelle (Stochastic Universal Sampling).

Une fois les solutions sélectionnées, le croisement combine des éléments de deux solutions parentales pour générer de nouvelles solutions, appelées enfants.

Ce processus permet d’explorer de nouveaux points dans l’espace de recherche en mélangeant les caractéristiques des solutions existantes, augmentant ainsi les chances de découvrir des configurations innovantes ou plus performantes.

Finalement, la mutation consiste à introduire des modifications aléatoires à certains éléments de solutions sélectionnées aléatoirement.

Ce mécanisme a pour objectif de créer de nouvelles variantes, augmentant ainsi la diversité de la population et permettant d’explorer des régions de l’espace de recherche qui pourraient autrement rester inaccessibles.

Ce cycle de sélection, croisement, et mutation se répète sur plusieurs générations, et la population évolue vers des solutions de plus en plus optimales.

La stratégie d’évolution a été introduite dans les années 1960 par Ingo Rechenberg et Hans-Paul Schwefel pour résoudre des problèmes d’optimisation complexes, principalement dans le cadre de l’ingénierie et de la conception de systèmes. La stratégie d’évolution se distingue des algorithmes génétiques par sa focalisation sur la mutation et l’adaptation des paramètres, avec une moindre importance accordée au croisement. Alors que les algorithmes génétiques utilisent une combinaison de croisement, mutation et sélection pour générer de nouvelles solutions, la stratégie d’évolution repose essentiellement sur des mutations appliquées aux individus pour explorer l’espace de recherche.

La programmation génétique est utilisée pour générer des programmes informatiques capables de résoudre des problèmes complexes. Contrairement aux algorithmes génétiques qui manipulent des vecteurs de réels ou des chaînes binaires, la programmation génétique utilise des arbres de syntaxe où les nœuds représentent des opérateurs et les feuilles des constantes ou des variables.

Le processus commence par une population initiale d’arbres générés aléatoirement, suivie de l’évaluation de leur performance à résoudre le problème via une fonction de fitness. Ensuite, les meilleurs individus sont sélectionnés pour la reproduction, où le croisement et la mutation sont utilisés pour générer de nouvelles solutions.

La programmation génétique est appliquée dans des domaines variés, tels que la création automatique de logiciels, l’optimisation de modèles d’apprentissage automatique, la conception de circuits électroniques, la génération de stratégies de jeu et la création d’algorithmes d’optimisation.

Les MOEA sont une classe d’algorithmes évolutionnaires conçus pour résoudre des problèmes d’optimisation multi-objectifs. Contrairement aux problèmes d’optimisation mono-objectifs où un seul objectif est maximisé ou minimisé, les problèmes multi-objectifs comportent plusieurs critères contradictoires ou complémentaires à prendre en compte. Leur but est de trouver un ensemble de solutions optimales, appelées Front de Pareto, plutôt qu’une seule solution optimale.

Le front de Pareto représente un ensemble de solutions où aucune ne peut être améliorée dans un objectif sans détériorer un autre objectif.

L’évolution différentielle (Differential Evolution) est un algorithme évolutionnaire utilisé principalement pour résoudre des problèmes d’optimisation continue dans des espaces de recherche de grande dimension. Il a été proposé pour la première fois par Rainer Storn et Kenneth Price en 1995. L’évolution différentielle est similaire aux autres algorithmes évolutionnaires, mais elle se distingue par ses opérateurs de mutation et de croisement spécifiques.

L’idée principale de l’évolution différentielle est d’utiliser des différences vectorielles entre des individus (solutions candidates) pour générer de nouvelles solutions. L’algorithme repose sur trois opérateurs principaux : mutation, croisement et sélection.

La mutation dans ED repose sur une approche novatrice qui exploite les différences entre individus pour produire des solutions prometteuses.

Cette méthode permet un compromis efficace entre exploration (recherche dans de nouvelles zones) et exploitation (raffinement des solutions actuelles).

Les paramètres comme le facteur \(F\) et la stratégie de mutation choisie jouent un rôle crucial dans la performance de l’algorithme.

Applications concrètes : Optimisation des hyperparamètres dans les réseaux de neurones ou dans des systèmes où la solution est un vecteur continu, comme l’optimisation de la trajectoire d’un robot autonome en utilisant des données sensorielles.

Les algorithmes mémétiques (ou algorithmes de la mémoire), parfois appelés métaheuristiques hybrides, sont une classe d’algorithmes d’optimisation qui combinent les algorithmes évolutionnaires avec des techniques locales de recherche (souvent appelées descentes locales ou méthodes de voisinage). L’objectif principal des algorithmes mémétiques est d’améliorer l’efficacité de la recherche en combinant la capacité d’exploration globale des algorithmes évolutionnaires avec la capacité d’exploitation locale des méthodes de recherche locale.

Ils s’inspirent du concept de coévolution biologique, où deux ou plusieurs populations évoluent simultanément en réponse aux pressions que chacune subit de l’autre.

Ainsi, les individus d’une population sont souvent évalués non seulement en fonction de leur performance par rapport à des critères internes, mais aussi en tenant compte de leur interaction avec les individus d’autres populations.

Ces algorithmes sont souvent utilisés dans des contextes où les solutions optimales sont dépendantes des interactions entre différents agents ou éléments.

Cela peut être appliqué dans divers domaines, comme l’optimisation multi-objectifs, la résolution de problèmes combinatoires complexes, ou même dans les jeux et la robotique.

Chaque type d’algorithme évolutionnaire est adapté à des types spécifiques de problèmes.

Les AG et les MOEA sont parmi les plus polyvalents, tandis que des approches comme la programmation génétique ou l’évolution différentielle répondent à des besoins plus spécialisés.

En fonction des contraintes et des objectifs, ces algorithmes peuvent être combinés ou modifiés pour maximiser leur efficacité dans le design ou l’optimisation.

jMetal est une bibliothèque Java open source dédiée à l’optimisation multi-objectifs. Elle fournit une collection d’algorithmes évolutionnaires et des structures de données pour les utiliser de manière flexible et extensible.

Plusieurs types d’algorithmes évolutionnaires et techniques d’optimisation multi-objectifs sont pris en charge.

En plus des classiques algorithmes génétiques, stratégies d’évolution, programmation génétique, elle propose des algorithmes évolutionnaires multi-objectifs (MOEA) comme NSGA-II (Non-dominated Sorting Genetic Algorithm II) est un algorithme génétique multi-objectifs largement utilisé en recherche opérationnelle et en informatique.

Il classe les solutions en différents “fronts de Pareto” en fonction de leur non-dominance et utilise une distance de regroupement pour maintenir la diversité des solutions.] , SPEA2^[1] , IBEA^[2] et autres.

MOEA Framework est une bibliothèque Java open-source conçue pour l’optimisation multi-objectifs utilisant des algorithmes évolutionnaires. Elle est très populaire dans la communauté de la recherche et de l’industrie. Le framework offre une large gamme d’algorithmes d’optimisation multi-objectifs et des outils pour l’évaluation, la gestion et la visualisation des résultats.

MOEA offre plusieurs algorithmes, y compris des versions avancées de NSGA-II, SPEA2, NSGA-III, et d’autres techniques populaires d’optimisation.

Le framework est conçu pour être extensible et personnalisable, permettant aux utilisateurs de définir leurs propres problèmes, algorithmes et opérateurs d’évolution.

Opt4J est une bibliothèque Java pour l’optimisation basée sur les métaheuristiques, particulièrement adaptée pour la recherche. Elle offre une intégration modulaire, ce qui permet de combiner différents algorithmes pour résoudre des problèmes d’optimisation.

ECJ (Evolutionary Computation in Java) est un système de calcul évolutionnaire écrit en Java.

Il a été conçu pour être extrêmement flexible, permettant aux utilisateurs de configurer presque toutes les classes et leurs paramètres dynamiquement à l’exécution à l’aide d’un fichier de paramètres fourni par l’utilisateur. Les structures du système sont organisées de manière à être facilement modifiables tout en maintenant une grande efficacité.

ECJ est développé par l’ECLab (Evolutionary Computation Laboratory) de l’Université George Mason. ECJ possède un projet "frère" appelé MASON, un système de simulation multi-agents conçu pour bien s’intégrer avec ECJ.

Dans un ou plusieurs clusters Kafka composés de plusieurs brokers par cluster, avec une infrastructure de communication cellulaire 5G, des milliers de capteurs IoT, une diversité d’API utilisant différents protocoles, ainsi que des milliers de microservices et d’applications, nous sommes confrontés à un problème d’optimisation particulièrement complexe

La question est la suivante :

L’objectif est de permettre à nos microservices d’échanger des données en temps réel tout en respectant des contraintes telles que la scalabilité, le temps de réponse et les coûts.

Une approche classique consisterait à tester manuellement toutes les architectures et leurs configurations possibles. Ce qui doit être extrêmement coûteux en temps et en ressources. Une approche intuitive serait de : prendre une architecture arbitraire A1 avec une configuration des composants et service C1, effectuer un test réel et attendre les résultats après un certain délai. Ensuite, réaliser un benchmarking pour passer à une configuration C2, ce qui pourrait impliquer des modifications telles que la taille des machines, le nombre de brokers, le nombre de partitions, etc. Ce processus serait ensuite répété pour d’autres architectures, comme A2, A3, et ainsi de suite.

Cependant, avec 10 brokers pouvant avoir 10 configurations possibles, cela donne un total de \(10^{10}\) configurations. Tester un tel volume est impraticable, même avec des outils d’automatisation, en raison du temps requis et de la complexité des paramètres à considérer (latence réseaux, partitions, charge, mémoire, CPU, disponibilité, etc.)

Pour résoudre ce problème efficacement, nous pouvons utiliser un des algorithmes communément utilisés dans ce contexte qui est NSGA-II (Non-dominated Sorting Genetic Algorithm II), une méthode bien adaptée aux problèmes d’optimisation multi-objectifs.

Cet algorithme est conçu pour trouver des solutions optimales en équilibrant plusieurs objectifs contradictoires, tels que :

Tout en simulant les différentes configurations possibles, NSGA-II explore l’espace des solutions pour trouver un ensemble de solutions optimales.