Surrogate-Assisted Genetic Programming with Rank-Based Phenotypic Characterisation for Dynamic Multi-Mode Project Scheduling

Cet article propose une méthode de programmation génétique assistée par modèle de substitution utilisant une caractérisation phénotypique basée sur le rang pour résoudre efficacement le problème d'ordonnancement de projets dynamique à modes multiples, permettant d'identifier des règles heuristiques de haute qualité plus rapidement que les approches existantes avec un surcoût computationnel négligeable.

L'essentiel

🏗️ Le Défi : Construire un gratte-ciel dans le brouillard

Imaginez que vous êtes le chef d'un chantier de construction géant (un projet). Votre but est de finir le plus vite possible. Mais il y a un problème : le brouillard.

• Vous ne savez pas exactement combien de temps prendra chaque tâche (parfois un camion arrive en retard, parfois le béton sèche plus vite).
• Vous avez des ressources limitées (peu de grues, peu de maçons).
• Chaque tâche peut être faite de plusieurs façons (modes) : rapide mais cher, ou lent mais économique.

C'est ce qu'on appelle le DMRCPSP (un nom compliqué pour dire : "Planifier un projet dynamique avec des ressources limitées et des incertitudes").

🤖 La Solution habituelle : L'entraîneur de génie (GP)

Pour gérer ce chaos, les chercheurs utilisent une intelligence artificielle appelée Programmation Génétique (GP).
Imaginez que le GP est un entraîneur de football. Il ne joue pas lui-même, mais il crée des milliers de "stratégies" (des règles de décision) pour ses joueurs.

• Il teste une stratégie : "Si le ciment est humide, utilisez la petite pelle."
• Il la fait jouer sur un simulateur (une répétition générale du chantier).
• Si ça marche bien, il la garde. Si ça rate, il la jette et en crée une nouvelle en mélangeant les meilleures idées.

Le problème ? Tester une stratégie prend du temps. Pour trouver la meilleure stratégie, l'entraîneur doit faire des milliers de répétitions générales. C'est très lent et très coûteux en temps de calcul.

🚀 La Nouvelle Idée : Le "Cristal de Prédiction" (Surrogate Model)

Pour aller plus vite, les auteurs de ce papier ont ajouté un assistant à l'entraîneur : un modèle de substitution (ou "surrogate").

Imaginez que cet assistant est un vétéran du chantier qui a vu des milliers de projets. Il ne fait pas la répétition complète. Il regarde juste la "physionomie" (l'apparence) de la nouvelle stratégie et dit : "Hé, cette stratégie ressemble beaucoup à celle qu'on a testée hier qui a bien marché. Je parie qu'elle va bien marcher aussi."

C'est ce qu'on appelle un modèle de substitution. Il permet de prédire le résultat sans avoir à faire la simulation complète.

🎨 Le Secret : La "Carte d'Identité" (Phenotypic Characterisation)

Mais comment l'assistant peut-il reconnaître les stratégies ? C'est là que réside l'innovation majeure du papier.

Avant, on essayait de comparer les stratégies de manière floue. Ici, les chercheurs ont créé une carte d'identité numérique (appelée Phenotypic Characterisation ou PC) pour chaque stratégie.

Voici comment ça marche, avec une analogie simple :
Imaginez que vous avez une liste de courses (les tâches à faire).

1. La règle de classement : Votre stratégie dit : "Achetez d'abord le pain, puis le lait, puis les œufs."
2. La règle de groupe : "Si vous avez le pain et le lait, mettez-les dans le même panier."

L'assistant ne regarde pas le code complexe de la stratégie. Il regarde l'ordre dans lequel elle classe les tâches.

• Il prend une situation typique (ex: "Il reste 5 tâches à faire").
• Il demande à la stratégie : "Dans quel ordre tu les traites ?"
• Il note les rangs : "Le pain est 1er, le lait 2ème, les œufs 3ème..."
• Il crée une liste de chiffres (un vecteur) qui résume le comportement de la stratégie.

C'est comme si on ne regardait pas le moteur d'une voiture, mais juste la façon dont le conducteur tourne le volant. Si deux stratégies tournent le volant de la même façon dans les mêmes situations, elles sont "pareilles" aux yeux de l'assistant.

🏆 Les Résultats : Plus rapide, tout aussi fort

Les chercheurs ont testé cette méthode (appelée SKGGP) contre la méthode classique (KGGP).

• Le résultat : L'assistant a permis de trouver d'excellentes stratégies beaucoup plus tôt.
• L'économie : Au lieu de faire 100 répétitions complètes pour trouver une bonne solution, ils n'en ont fait que 60 ou 70. Ils ont économisé 20 à 40 % du temps de calcul.
• La précision : L'assistant est très bon pour repérer les "bonnes graines" parmi les nouvelles idées. Parfois, il se trompe un peu si on lui présente trop d'idées d'un coup, mais globalement, il guide l'entraîneur vers les meilleurs joueurs.

🧠 En résumé

Ce papier dit essentiellement :

"Au lieu de faire courir tous les candidats sur le terrain pour voir qui est le meilleur (ce qui prend du temps), regardons d'abord leur façon de s'échauffer (leur comportement). Si leur échauffement ressemble à celui des champions passés, on les sélectionne directement. Cela nous fait gagner un temps précieux sans sacrifier la qualité."

C'est une méthode intelligente pour gérer des projets complexes dans un monde incertain, en utilisant un peu de "devinette éclairée" pour éviter de gaspiller du temps.

Résumé technique

1. Problématique : DMRCPSP et Coût Computationnel

L'article aborde le problème de planification de projet dynamique à modes multiples avec contraintes de ressources (DMRCPSP).

• Contexte : Il s'agit d'une version dynamique du problème classique MRCPSP où les durées réelles des activités sont incertaines et ne sont révélées qu'au cours de l'exécution. Les décisions (quelle activité exécuter et dans quel mode) doivent être prises en temps réel à mesure que l'état du projet évolue.
• Approche actuelle : La programmation génétique (PG) est utilisée comme hyper-heuristique pour évoluer des règles heuristiques capables de prendre ces décisions. Une approche représentative (KGGP) utilise deux arbres de décision : un pour le classement des paires activité-mode et un autre pour la sélection de groupes d'activités.
• Défi majeur : L'évaluation de la qualité (fitness) de chaque individu PG nécessite de nombreuses simulations coûteuses pour estimer la durée totale du projet (makespan). Ce coût computationnel élevé limite l'évolutivité et l'applicabilité pratique de la PG dans des environnements dynamiques.

2. Méthodologie Proposée

Les auteurs proposent un algorithme PG assisté par modèle de substitution (Surrogate-Assisted GP), nommé SKGGP, intégrant une nouvelle méthode de caractérisation phénotypique.

A. Caractérisation Phénotypique (PC) Basée sur le Rang

Le défi principal pour l'application des modèles de substitution à la PG est l'absence de schéma de caractérisation phénotypique (PC) adapté au DMRCPSP. Les schémas existants (conçus pour des choix uniques) ne fonctionnent pas ici car les règles heuristiques gèrent à la fois :

1. Le classement (ranking) de paires activité-mode.
2. La sélection de sous-ensembles (groupes d'activités).

Solution proposée :

• L'échantillonnage de situations de décision représentatives durant la simulation.
• Pour chaque situation, les règles heuristiques attribuent des valeurs de priorité aux candidats.
• Au lieu de stocker les valeurs brutes, le schéma extrait les rangs (positions dans l'ordre de priorité) de tous les candidats éligibles.
• Ces rangs forment un vecteur de décision. La concaténation des vecteurs de toutes les situations de décision (classement et sélection de groupes) crée le vecteur PC complet de l'individu.
• Ce vecteur capture le comportement de classement de l'heuristique, permettant de mesurer la similarité comportementale entre individus.

B. Estimation de Fitness par Modèle de Substitution

• Modèle : Un modèle de régression par plus proche voisin (Nearest-Neighbour) utilisant la distance de Manhattan sur les vecteurs PC.
• Fonctionnement :
  1. Une population initiale est évaluée complètement pour construire une base de données (vecteurs PC + fitness réelle).
  2. Des descendants intermédiaires ($k \times |P|$) sont générés.
  3. Leurs vecteurs PC sont calculés.
  4. Le modèle de substitution estime leur fitness en trouvant l'individu le plus proche dans la base de données de la génération courante.
  5. Seuls les meilleurs descendants (selon l'estimation) sont soumis à l'évaluation complète (simulation réelle).
• Note importante : La base de données n'est pas cumulée sur les générations car les simulations sont stochastiques (différentes graines aléatoires), rendant les fitness absolues non comparables entre générations. Seuls les individus de la génération courante sont utilisés pour l'entraînement.

3. Contributions Clés

1. Nouveau schéma de PC : Développement d'une méthode de caractérisation phénotypique basée sur le rang, capable de gérer simultanément les décisions de classement et de sélection de sous-ensembles, comblant ainsi un vide dans la littérature pour le DMRCPSP.
2. Algorithme SKGGP : Intégration de ce schéma dans un cadre PG assisté par modèle de substitution, permettant de réduire drastiquement le nombre d'évaluations complètes nécessaires.
3. Analyse de l'impact du multiplicateur de descendants ($k$) : Étude systématique de l'effet du nombre de descendants intermédiaires générés ($k=1, 1.5, 2, 4$) sur la qualité de la sélection et la précision du modèle.

4. Résultats Expérimentaux

Les expériences ont été menées sur des instances de projets avec 200 activités, 3 modes d'exécution et 12 types de ressources, avec différents niveaux de complexité de précédence.

• Performance de Convergence : Les variantes SKGGP-2 et SKGGP-4 convergent significativement plus vite que l'algorithme de base (KGGP). Elles identifient des règles heuristiques de haute qualité plus tôt dans le processus évolutif.
• Économie de Budget : L'approche assistée permet d'atteindre la même qualité de solution que KGGP en économisant 20 % à 40 % des évaluations complètes.
• Précision du Modèle :
  • La précision du modèle (capacité à distinguer les bons individus) diminue lorsque $k$ augmente (de ~80-90 % pour $k=1.5$ à ~50-60 % pour $k=4$).
  • Cependant, même avec une précision modérée, la génération de descendants supplémentaires ($k=2$) permet d'ajouter environ 35 % d'individus "correctement" sélectionnés (qui améliorent la population) par rapport à la sélection standard.
• Surcharge Computationnelle : Le temps consacré à l'estimation par modèle de substitution est négligeable (environ 1/20 à 1/40 du temps d'évaluation complète), confirmant que l'approche est très efficace en termes de coût global.

5. Signification et Conclusion

Cet article démontre que l'intégration d'un modèle de substitution dans la programmation génétique pour la planification de projet dynamique est non seulement viable, mais supérieure aux approches traditionnelles.

• Impact Pratique : La méthode permet de trouver des solutions de meilleure qualité plus rapidement, ce qui est crucial pour les environnements de prise de décision en temps réel où le temps de calcul est limité.
• Innovation Théorique : La proposition d'une caractérisation phénotypique basée sur le rang ouvre la voie à l'application de techniques d'optimisation par modèles de substitution à des problèmes complexes impliquant des structures de décision mixtes (classement et sélection de groupes).
• Perspectives : Les auteurs notent que la précision du modèle pourrait être améliorée en élargissant la base de données de substitution ou en explorant des modèles d'apprentissage automatique plus expressifs, mais concluent que l'approche actuelle offre déjà un compromis optimal entre coût et performance.