Enhanced Gold Mining Optimization with Dual-Layer Information Sharing and Dynamic Control for Multi-Objective Scheduling of Heterogeneous UAV Swarms

Résumé technique : Optimisation améliorée de l'extraction d'or pour les essaims de drones hétérogènes

Énoncé du problème
L'article traite du défi complexe de l'ordonnancement collaboratif multi-objectif pour les essaims de véhicules aériens sans pilote (UAV) hétérogènes. Ce problème implique l'optimisation étroitement couplée de l'allocation des tâches et de la planification des trajectoires pour des flottes comprenant divers types d'UAV (par exemple, à voilure fixe, à voilure tournante et hybride). L'objectif est d'optimiser simultanément trois buts conflictuels sous des contraintes opérationnelles strictes :

1. Minimiser le temps d'achèvement de la mission (makespan).
2. Minimiser la consommation totale d'énergie.
3. Maximiser l'équilibre de la charge de travail (minimiser l'écart-type des temps d'achèvement individuels des UAV).

Le problème est contraint par l'unicité des tâches, la faisabilité énergétique, les fenêtres temporelles et la faisabilité dynamique (limites cinématiques comme le rayon de virage et les angles de montée). Les auteurs soutiennent que les métaheuristiques existantes souffrent souvent d'un découplage structurel entre la planification des tâches et des trajectoires, de conceptions algorithmiques statiques manquant d'adaptabilité aux changements en temps réel, et d'une uniformité sous-optimale du front de Pareto (lacunes ou regroupements). De plus, l'algorithme original Gold Mining Optimization (GMO), bien qu'efficace dans l'exploration globale, manque de diversité de population suffisante, de contrôle adaptatif de la taille du pas et de mécanismes dédiés à la gestion multi-objectif, ce qui conduit à une convergence prématurée et à une mauvaise approximation du front de Pareto dans ce domaine spécifique.

Méthodologie : IGMO-DP
Pour surmonter ces limitations, les auteurs proposent l'Improved Gold Mining Optimization with Dual-layer Information Sharing and Dynamic Pareto Dominance (IGMO-DP). La méthodologie intègre trois améliorations fondamentales au cadre standard du GMO :

1. Mécanisme de partage d'informations à double couche :

   • Amélioration du voisinage local : Utilise une structure de voisinage topologique où les individus échangent des informations avec leurs $K_{neigh}$ plus proches voisins. Une stratégie de fusion par moyenne pondérée attribue des poids plus élevés aux voisins ayant de meilleurs rangs non dominés, préservant ainsi la diversité locale et empêchant la convergence prématurée.
   • Guidage par l'élite globale : Dirige la population vers le front de Pareto optimal à l'aide d'une archive externe de solutions élites.
   • Fusion adaptative : Un coefficient variant dans le temps $\alpha(t)$ équilibre dynamiquement l'influence des vecteurs locaux et globaux, privilégiant l'exploration globale lors des premières itérations et le raffinement local lors des phases ultérieures.

2. Mécanisme de mise à jour de position dynamique :

   • Taille de pas adaptative : La taille du pas $\eta_i(t)$ est ajustée en fonction de l'amélioration de l'aptitude (fitness) de l'individu et du nombre d'itérations. Cela permet de grands pas lors de l'exploration globale et des pas plus petits et précis lors de l'exploitation locale.
   • Ajustement directionnel : Un facteur basé sur le gradient est introduit pour ajuster la direction de recherche en fonction du terrain local de la fonction objectif, équilibrant le guidage par l'information et la descente de gradient.

3. Dominance de Pareto dynamique et maintenance de l'archive :

   • Seuil de dominance dynamique : Un seuil $\tau(t)$ diminue au fil des itérations. Aux premiers stades, il relâche les critères de dominance pour conserver des solutions diverses légèrement inférieures ; aux stades ultérieurs, il se resserre pour appliquer la dominance de Pareto standard afin d'accélérer la convergence.
   • Archive d'élite : Maintient un ensemble de solutions non dominées, utilisant la distance de crowding pour élaguer l'archive lorsque sa capacité est dépassée, assurant ainsi une couverture uniforme du front de Pareto.

L'algorithme encode les solutions sous forme de matrices d'allocation de tâches et de séquences d'exécution, utilisant des modèles de trajectoires de Dubins pour garantir la faisabilité cinématique lors de l'évaluation de l'aptitude. La prise de décision finale parmi l'ensemble de Pareto est effectuée à l'aide de la méthode TOPSIS.

Contributions clés

• Innovation algorithmique : Le développement de l'IGMO-DP, qui adapte spécifiquement l'algorithme Gold Mining Optimization pour l'ordonnancement multi-objectif d'UAV hétérogènes grâce au partage d'informations à double couche et aux mécanismes de contrôle dynamique.
• Formulation du problème : Un modèle mathématique rigoureux qui optimise conjointement le temps, l'énergie et l'équilibre de la charge tout en imposant des contraintes physiques et temporelles strictes via les trajectoires de Dubins.
• Analyse des mécanismes : L'introduction d'une stratégie de dominance de Pareto dynamique qui ajuste automatiquement la pression de sélection sans réglage manuel des paramètres, équilibrant efficacement la vitesse de convergence et la diversité des solutions.

Résultats expérimentaux
L'algorithme IGMO-DP a été évalué par rapport à quatre bases de référence (GMO original, NSGA-II, MOPSO et HMOEA) à travers trois scénarios de complexité croissante (S1 : 5 UAV/10 tâches ; S2 : 10 UAV/20 tâches ; S3 : 20 UAV/40 tâches).

• Convergence et qualité : L'IGMO-DP a systématiquement surpassé toutes les bases de référence. Dans le scénario le plus complexe (S3), il a obtenu une amélioration de la Distance de Génération Inversée (IGD) de 12,7 % à 18,3 % et une amélioration de l'Hypervolume (HV) de 8,2 % à 14,6 % par rapport au second meilleur algorithme (HMOEA).
• Uniformité : L'algorithme a produit des fronts de Pareto avec un espacement (SP) nettement meilleur, montrant une amélioration de 15,1 % à 22,4 % de l'uniformité de la distribution des solutions.
• Stabilité : L'IGMO-DP a démontré une stabilité supérieure sur 30 essais indépendants, avec des écarts types plus faibles et moins de valeurs aberrantes par rapport aux autres algorithmes.
• Études d'ablation : Les expériences ont confirmé que le retrait de n'importe quel composant (partage local, partage global, taille de pas adaptative ou dominance dynamique) entraînait une dégradation mesurable des performances. Par exemple, le retrait du partage local a dégradé la métrique SP de 21,3 %.
• Efficacité de calcul : Bien que l'IGMO-DP induise une légère augmentation du temps d'exécution (environ 15 % de plus que NSGA-II dans S2), les auteurs notent que cela est acceptable pour les applications d'ordonnancement hors ligne où la qualité de la solution est primordiale.

Signification et revendications
L'article affirme que l'IGMO-DP fournit une solution robuste et évolutive pour l'ordonnancement multi-objectif d'essaims d'UAV hétérogènes. Sa principale importance réside dans sa capacité à :

1. Optimiser simultanément des objectifs conflictuels (temps, énergie, charge) tout en respectant des contraintes physiques complexes.
2. Maintenir une grande diversité dans l'ensemble de solutions, offrant aux décideurs un large éventail d'options de compromis bien distribuées (par exemple, prioriser la vitesse par rapport à l'énergie dans des scénarios de réponse aux catastrophes).
3. Opérer de manière autonome sans nécessiter de calibrage manuel des paramètres pour équilibrer la convergence et la diversité, grâce à sa dominance dynamique et ses mécanismes adaptatifs.

Les auteurs concluent que l'algorithme est viable pour les applications d'ingénierie, citant une étude de cas spécifique où il a réduit le temps d'achèvement des tâches de 23 % et la consommation d'énergie de 18 % par rapport aux méthodes gourmandes traditionnelles dans un scénario de réponse aux catastrophes. Des travaux futurs sont suggérés pour se concentrer sur l'ordonnancement en ligne via l'apprentissage par renforcement, les architectures distribuées et les tests de type "hardware-in-the-loop".