Labeling in CLP(FD) with evolutionary programming

Introduction

  • Les problèmes d’optimisation combinatoire sur des nombres entiers sont définis comme suit :
    • un groupe de variable.
    • un groupe de contraintes associées à celles-ci.
    • un fonction objective

    Le problème est de trouver une solution qui satisfait les contraintes et optimise (minimise ou maximise) la fonction objective.

  • L’idée de base de la Programmation Logique par Contrainte (Constraint Logic Programming(FD)¹)
    est de remplacer le mécanisme d’unification de la Programmation Logique par la résolution de contraintes sur des domaines particuliers, en considérant le résolveur de contraintes comme une boîte noire qui se charge de tester la satisfiabilité des contraintes.
  • La compréhension et l’imitation des phénomènes naturels d’évolution et d’adaptation des individus et des populations a donné lieu à de nombreux algorithmes d’intelligence artificielle regroupés sous le terme générique d’algorithmes évolutionnaires. Les plus connus sont les algorithmes génétiques (GA), les Evolution Strategies (ES) et les Evolutionary Programming (EP).
  • Ces algorithmes se révèlent robustes et efficaces dans la résolution de nombreux problèmes et en particulier des problèmes d’optimisation et de satisfaction de contraintes (p. ex. la planification, l’ordonancement et l’affectation de ressources). Ils sont largement utilisés dans les industries, le transport, les télécommunications, la défence, les soins de santé , etc. De nombreuses recherches sont aujourd’hui réalisées dans ce domaine très actif de l’intelligence artificielle.
  • Le principe de base de ces algorithmes est la mise en oeuvre de processus de sélection, mutation et recombinaison au sein d’une population d’individus; chaque individu représentant un point particulier dans l’espace de recherche.
  • La littérature scientifique propose une large game d’algorithmes évolutionnaires, de stratégies de sélection, d’opérateurs de mutation et de recombinaison. Néanmoins, la mise en oeuvre de ces algorithmes pour la résolution de problèmes spécifiques d’optimisation reste encore, aujourd’hui, un art et laisse une grande part à la créativité.

Base du problème

  • Problème d’optimisation combinatoire
  • Programmation Logique par Contrainte sur des Domaines Finis (CLP-FD)
  • Paradigme utilisé : « Constraint & Generate », 3 phases
    1) Phase de contrainte : réduction de l’espace de recherche
    2) Phase d’énumération ou Labeling : invoque la résolution complète des contraintes
    3) Phase de recherche de la solution optimale : heuristique spécifique ou méthode générale ( Branch & Bound )
  • Mais les limites existent…

L’alternative

  • Les algorithmes d’approximation
  • Pas de garantie pour trouver la solution optimale
  • Haute probabilité de trouver une bonne solution en explorant seulement une partie de l’espace des solutions.
  • Intégration d’une technique d’approximation appelée « Evolutionary Programming into CLP(FD) »

Labeling with evolutionary programming

  • But : Améliorer CLP(FD)
  • Par une technique d’optimisation qui : suivant une liste de variables de domaines et une expression de coût qui retourne une solution (la plus optimale) en respectant l’expression de coût.

Algorithmes évolutionnaires

  • La compréhension et l’imitation des phénomènes naturels d’évolution et d’adaptation des individus et des populations a donné lieu à de nombreux algorithmes d’intelligence artificielle regroupés sous le terme générique d’algorithmes évolutionnaires.
  • Ils permettent une recherche effective dans un espace de recherche très large.
  • Le principe de base de ces algorithmes est la mise en oeuvre de processus de sélection, mutation et recombinaison au sein d’une population d’individus; chaque individu représentant un point particulier dans l’espace de recherche.
  • « Genetic Algorithms + Data structures = evolution programs »

Evolutionary program (1)

Procedure evolutionary program
Begin
 t:=0;
 initialize P(t); 
 evaluate P(t);
 while not termination-condition do begin
   t := t + 1;
   select P(t) from P(t-1);
   alter P(t);
   evaluate P(t);
 end;
End.

Evolutionary program (2)

  • Population de « chromosomes », P(t) = {Xt1 …,Xtn } pour l’itération t.
  • Chaque chromosome représente une solution potentiele du problème et est représenté par une structure de donnée : S
  • La première étape dans tous les programmes évolutionnaires est la génération de la population initiale : P(0), qui est généré de façon aléatoire (INITIALIZE)
  • La population est ensuite évaluée. A chaque génération, une valeur «fitness » (adaptation) est calculée pour chaque chromosome Xti
  • Fitness indiquant le degré de « justesse » du chromosome comme étant solution du problème d’optimisation. (EVALUATE)
  • La fonction objective du problème qui doit être optimisée est à la base du calcul de la valeur « fitness »

Evolutionary program (3)

  • Une nouvelle population P(t+1) est formée par sélection d’un certain nombre de chromosomes de la population P(t) (SELECT)
  • Les chromosomes, ayant la meilleure valeur d’ «adaptation», ont plus de chance d’être retenu par la procédure de sélection.
  • Quelques chromosomes de la population P(t) seront présent dans la population P(t+1)
  • Tous les « mauvais » chromosomes ne sont pas tous jetés car ils pourraient éventuellement conduire à la génération d’une bonne solution.

Evolutionary program (4)

  • Quelques membres de la nouvelle population subiront des transformations (opérateurs génétiques) afin de former de nouvelles solutions. (ALTER)
  • Ces opérateurs génétiques vont générer de nouveaux chromosomes qui seront additionnés à la population P(t)
  • La mutation : la mutation crée des nouvelles solutions par de petit changement dans un simple chromosomes. S S, elle permet de « sauter » vers des zones encore inexplorée de l’espace de recherche.

Condition de terminaison

  • Soit on atteint un nombre d’itération maximum
  • Soit on arrête après un temps déterminé par l’utilisateur
  • Soit on obtient un chromosome ayant le coût spécifié par l’utilisateur
  • Soit on atteint une population invariante et sans espoir

Paramétrisation

  • Taille de la population
  • Pourcentage de survivant à chaque génération, …
  • Affecte dramatiquement les performances du système

Exemple

Recherche d’un plan de transport de coût minimum pour un produit unique

  • Soit n sources et k destination
  • Nombre de provision à la source i : sour(i)
  • Nombre de demande à la destination : dest(j)
  • Coût de transport entre la source i et la destination j : cost(i,j)
  • Volume transporté entre la source i et la destination j : X i,j

Exemple (2)

  • La forme de la courbe est caractéristique des programmes évolutionnaires
  • Les chromosomes de départ ont une valeur adaptative pauvre, mais après quelques itérations les bonnes solutions sont générées
  • Tous les chromosomes de la population tendent à converger lentement vers une même solution proche de l’optimale

Conclusion

  • L’intégration d’un algorithme évolutionnaire dans la programmation logique par contrainte sur les domaines finis a permis de réaliser la phase d’énumération (de façon optimale) du problème de recherche d’optimisation combinatoire
  • La version finale du système devrait être compétitive par rapport aux stratégies classiques tel que « branch & bound » et promet un bel avenir.

¹CLP(FD) : Constraint Logic Programming over Finite Domains