GA-viz - Visualisation d’algorithme génétique Programme Datavisualisation #3, 2017


Le travail consiste à donner forme visuelle à la méthode de calcul massif qui fait appel à l’algorithme génétique. Cette méthode de calcul permet de chercher les meilleurs solutions approximatives à un problème trop complexe pour être solutionné avec les ressources dont on dispose. On cherche donc la ou les meilleur(e)s approximation(s) en fonction d’un résultat attendu.

Inspiré par le processus de sélection naturelle décrit par Charles Darwin, l'algorithme génère aléatoirement une première génération solutions potentielles et effectue un filtrage pour sélectionner les solutions les plus proches de l'objectif (la fonction de fitness). Puis, les individus sélectionnés seront croisés les uns avec les autres pour produire une nouvelle génération de solutions, en principe plus adaptées encore à l'objectif. En répétant l'opération N fois, on obtient progressivement de meilleurs approximations de l'objectif attendu. Pour éviter l'assèchement génétique lors du calcul, une portions des individus de chaque génération est dotée de caractères génétiques mutants.

En collaboration avec le chercheur iranien Habib Daneshpajouh, le groupe tente plusieurs approches visuelles pour représenter un cas d'étude typique de l'algorithmie génétique appelé Vehicule Routing Problem. Une tournée de livraison peut être organisée de multiple façon. Laquelle sera la plus efficace au regard de tel ou tel critère (distance totale parcourue, durée de la tournée, …) ? L'enjeu de design graphique : donner forme aux individus, aux générations, aux hiérarchies de la sélection. L'enjeu de design numérique : élaborer une interface pour naviguer dans le processus du calcul.

Recherches visuelles

Vidéo de présentation du design d’interface

Principes de l'interface finale du projet, après évaluation des différentes pistes explorées.

Vidéo de présentation du prototype fonctionnel

Réalisé par les étudiants ingénieurs de TSP, ce prototype intègre partiellement l'interface graphique et se concentre sur la chaine technique en situation réelle (chargement de vrais calculs, passage à l'échelle des quantités d'individus et de générations, structure software, etc.).

Un projet du programme Datavisualisation
Esad de Reims
Télécom SudParis / IMT

Designers graphiques
Alice Dubreuil
Jeanne Delorme
Pia Gaussot
Odyssée Khorsandian
Seul Kim
Sindy Serapicos

Ingénieurs
Victor Person
Benjamin Cloquet
Thomas Jacquemin
Olivier Freyssinet
Pierre Touchard

Chercheur
Habib Daneshpajouh, département d’informatique de L'Université de Technologie de Petronas / Malaisie

Supercalculateur ROMÉO
Jean-Mathieu Etancelin, département d’informatique de L'Université Reims Champagne-Ardenne

Organisation & supervision
Olaf Avenati - Esad de Reims
Michel Simatic - Télécom SudParis / IMT