Algorithmes génétiques

Un aspect inattendu du magasin le Retour à la Terre créé par ma femme Catherine est qu’il me donne l’opportunité de travailler dans des domaines connexes à ceux que je connais sur des projets intéressants parce que directement valorisables et à taille humaine.

C’est le cas du système de gestion des emplois du temps dont je viens de terminer une première version.

La gestion des emplois du temps dans une entreprise gérant une dizaine de personnes avec des rôles et des contraintes d’emploi du temps très variées est un véritable casse-tête et Catherine passait chaque semaine plus d’une demi-journée à constituer l’emploi du temps de la semaine suivante.

Les recherches que j’ai fait sur Internet pour essayer de dénicher un logiciel pouvant gérer cela sans modifier les habitudes déjà prises au magasin (j’estime que c’est aux logiciels de s’adapter aux organisations et non l’inverse) et de préférence disponible en Open Source se sont soldées par un échec et après l’avoir vu une nouvelle fois gâcher son week-end à travailler sur l’emploi du temps je me suis résolu à écrire mon propre système pour gérer cela.

Ce type de problème me rappelait pourtant de mauvais souvenirs, l’optimisation sous contraintes restant pour de nombreux centraliens de ma promotion synonyme de “Simplexe“, un des points les plus obscurs du cours d’analyse numérique…

Pour éviter cela, j’ai décidé de mettre en pratique les rudiments d’algorithmes génétiques que j’avais récemment acquis grâce au livre fascinant de Toby Segaran : “Programming Collective Intelligence“.

Et ça marche!

C’est sans doute un des problèmes les plus complexes que j’ai dû résoudre et l’efficacité de cette méthode est simplement ahurissante.

En deux mots, les algorithmes génétiques appliquent à la recherche de solutions des techniques empruntées à l’évolution naturelles des espèces : on part d’une population de solutions générées aléatoirement que l’on note et on les améliore, génération après génération par des sélections et des mutations et croisements aléatoires.

Les deux principales difficultés sont la modélisation et la notation des solutions, le reste étant de la programmation classique sans grande difficulté.

C’est une manière de programmer – et de raisonner! – totalement nouvelle pour moi. Elle est fascinante par le parallèle entre ces populations de solutions et la biodiversité du monde qui nous entourent et l’observation de la manière dont convergent ces solutions alimente toutes sortes de réflexions…

J’aime beaucoup ce type de projets courts dont la richesse repose sur quelques idées simples.

Share and Enjoy:
  • Identi.ca
  • StumbleUpon
  • del.icio.us
  • Facebook
  • Twitter
  • Add to favorites

4 thoughts on “Algorithmes génétiques”

  1. Effectivement la création d’emploi du temps est un problème très complexes… Cela ne m’étonne pas de savoir que tu n’as rien trouvé sur le net à ce sujet. Pourtant il y a un marché énorme dans l’éducation nationale : les directeurs d’établissement se casse la tête tous les ans sur ces problèmes !

  2. @gl3am:

    J’ai effectivement trouvé beaucoup de logiciels “orientés éducation” mais le problème est sensiblement différent : il faut gérer des cours dispensés par des professeurs dans des salles dont la capacité doit permettre d’accueillir les élèves inscrits à ces cours…

    Dans le cas d’un magasin, il s’agit d’assurer un nombre minimum de personnes susceptibles d’assurer plusieurs rôles pour faire face à une charge de travail dépendant de l’affluence et du planning des livraisons et ce en tenant compte dans la mesure du possible des contraintes personnelles de chacun.

    Eric

  3. effictivement, le problème des emplois du temps est un veritable casse tête! je travail à present sur ce problème. je développe un logiciel qui pourra générer un emploi du temps automatiquement sous réseau pour une université. mais le problème est le nombre énorme de contrainte qu’il faut respecter.
    mais les AG restent une methode assez riche qui permet la réalisation, sans hormis d’autre méthode métaheuristique comme : la satisfaction de contraintes, la recherche tabou…. qui peuvent être utile.

  4. j’ai le même problème , je veut faire une génération d’emploi du temps si quelqu’un peut m’aider car je suis débutant dans ces type d’algorithme qui ce basent sur la recherche opérationnelle , et les algorithme simplexe , je serais reconnaissant

Leave a Reply

Your email address will not be published. Required fields are marked *

Enter your OpenID as your website to log and skip name and email validation and moderation!