Algorithme génétique

Sommaire :

  1. Introduction
  2. Algorithme génétique (NSGA-II)
  3. Application Démo
  4. Simulateur
  5. Projet et évolutions
  6. Téléchargement

Introduction

Ce projet a été réalisé lors de mon stage de fin DUT (Avril 2014 à Juin 2014) à l’université d’Aberystwyth au Pays de Galles, dans le département Computer Sciences.

Le projet a été proposé par Elio Tuci, enseignant chercheur à l’université d’Aberystwyth. Il travaille sur un projet plus global de « Swarm » Robotique, c’est-à-dire une robotique inspirée des insectes.

 

L’objectif a été de développer les outils nécessaires pour pouvoir, d’abord sur simulateur, puis éventuellement avec des tests réels, faire en sorte que des robots se contrôlent de manière autonome et soient capables d’évoluer par eux même pour répondre à certains objectifs.
Pour obtenir ce genre de résultats, il était important de réaliser des traitements évolutifs. Ceux-ci étant assez génériques pour pouvoir être utilisés dans ce contexte. Les algorithmes que mon superviseur voulait utiliser sont des algorithmes génétiques.
Les algorithmes génétiques nécessaires ont été développés grâce à la norme 2011 du C++, ce qui permet l’utilisation de fonctionnalités standards avancées.
Des vidéos disponibles sur YouTube montrent quelques résultats obtenus à terme du projet. Les liens étant disponibles plus bas dans l’article.

 

Pour structurer et faciliter le travail, le début du projet a été réalisé en utilisant le gestionnaire de version Git. Le projet du développement de l’architecture des algorithmes génétiques ainsi qu’une application d’exemple sont disponibles sur GitHub.

Le dépôt du projet est accessible à l’adresse suivante :
https://github.com/KeRNeLith/Single-Multi-Objective-Genetic-Algorithm.

 

flèche haut

Algorithme génétique (NSGA-II)

Au début du projet, j’ai dû développer un algorithme génétique simple objectif, c’est à dire qu’il devait répondre à une question et en trouver la solution optimale. Toutefois dans le cas du contrôle de robots, celui-ci ne doit pas répondre à un seule critère de manière optimale.
C’est là qu’interviennent les algorithmes génétique multi objectifs, lors de mon stage l’algorithme choisi a été NSGA-II (Non-Dominated Sorting Genetic Algorithm II), qui est le plus performant d’entre eux.

 

La procédure de cet algorithme est la suivante :

Procédure NSGA-II

 

L’algorithme a d’abord été développé en mono thread. Puis, lorsqu’il était au point, j’ai implémenté son exécution en multi-threading. Ceci qui a eu pour effet de grandement accélérer son exécution.

 

Pour obtenir plus de détails sur cet algorithme je vous invite à lire le rapport de stage disponible dans la partie téléchargement.

flèche haut

Application Démo

La mise au point de tels algorithmes nécessite des tests, et dans le but de fournir des résultats visibles et explicable à mon maitre de stage, j’ai donc conçu une application graphique (GUI) qui permet d’exécuter ces algorithmes sur des problèmes fixes et d’en visualiser les résultats. Ce qui a été grandement utile pour le commentaire du bon fonctionnement des algorithmes. L’application a été réalisé avec le framework Qt (version 5.2).

Screenshot de l'application GUI

 

Dans le cas de l’algorithme NSGA-II, le problème à résoudre était mathématiques, il suffisait de minimiser les fonctions x² et (x-2)².
Ci-dessous le résultat d’une exécution de l’algorithme et l’ensemble des résultats obtenus.

Screenshot des résultats de l'exécution de l'algorithme NSGA-II

 

La vidéo suivante montre l’utilisation de l’application de démonstration :

flèche haut

Simulateur

Une fois que l’algorithme multi objectifs était au point, il a donc été utilisé dans une simulation de robots pour initialiser les poids des connexions d’un réseau neuronal.

Voici une image du simulateur, l’expérience utilisée lors du projet était simpliste, il suffisait de faire le tour des 2 cylindres et ceci en un temps minimum.

Screenshot du simulateur

 

La vidéo suivante montre le fonctionnement du simulateur basé sur les résultats fourni par l’algorithme NSGA-II.

flèche haut

Projet et évolutions

Le projet est actuellement terminé, toutefois il n’est pas écarté la possibilité de le continuer pour optimiser l’algorithme NSGA-II implémenté. Ou encore l’étendre sur un projet plus vaste. Sans plus de détails pour le moment.

 

Permettre de réaliser divers autres types d’expériences.

 

Il est possible de consulter une publication faite dans un journal se basant sur ce projet.
Voici les références de celui-ci :
Article : On the design of generalist strategies for swarms of simulated robots engaged in a task-allocation scenario
Journal : Swarm Intelligence
Date : 1 Octobre 2015
Auteurs : Elio Tuci, Alexandre Rabérin

flèche haut

Téléchargement

Dû a des contraintes liées au format du rapport, celui-ci contient des parties écrites en anglais.
Vous pouvez télécharger mon rapport de stage via les liens ci-dessous :

Mémoire de stage (Majoritairement français)

Mémoire de stage anglais (sauf partie technique)

flèche haut

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Le temps imparti est dépassé. Merci de recharger le CAPTCHA.

Vous pouvez utiliser ces balises et attributs HTML : <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>