Une étude sur un nouveau cadre pour résoudre le problème de réinstallation des migrants via l’optimisation multiobjectif évolutive

Dans le contexte de la mondialisation accélérée et des dynamiques socio-économiques en constante évolution, le phénomène migratoire est devenu une tendance mondiale incontournable. Que ce soit sous l’angle de l’aide humanitaire ou pour le développement économique durable à l’échelle mondiale, gérer et réinstaller efficacement les migrants est devenu un défi complexe et crucial. Selon les statistiques, en 2019, le nombre total de migrants internationaux a atteint 272 millions, dépassant largement les prévisions antérieures, une tendance qui devrait se poursuivre à l’avenir. Cependant, la réinstallation des migrants pose également de nombreux défis, notamment : comment augmenter leur taux d’emploi et comment répartir les migrants dans des lieux d’accueil appropriés ? Les réponses à ces questions ont un impact considérable non seulement sur les migrants eux-mêmes, mais aussi sur les pays d’accueil ainsi que sur le bien-être économique et culturel de l’ensemble de la société.

Face à cette problématique mondiale, cette étude a été réalisée en collaboration par plusieurs chercheurs d’institutions telles que l’Université de Nanjing, le laboratoire Peng Cheng et l’Université des Sciences et Technologies du Sud (Southern University of Science and Technology). L’équipe de recherche inclut Dan-Xuan Liu, Yu-Ran Gu, Chao Qian (Membre Senior de l’IEEE), Xin Mu et Ke Tang (Membre Fellow de l’IEEE). L’article, intitulé “Migrant Resettlement by Evolutionary Multiobjective Optimization”, a été publié dans le numéro de janvier 2025 de la revue IEEE Transactions on Artificial Intelligence (TAI). Il propose un nouveau cadre pour résoudre la problématique de la réinstallation des migrants et démontre, tant sur le plan théorique qu’empirique, sa supériorité.

Contexte et objectifs de la recherche

Les méthodes traditionnelles de réinstallation des migrants reposent principalement sur des algorithmes gloutons (greedy algorithms), qui, grâce à leurs performances élevées et leur implémentation relativement simple, sont largement utilisés. Cependant, la nature inhérente de ces méthodes les limite à des optimisations locales, ce qui les rend vulnérables aux contraintes de leur stratégie myope. Dans les scénarios réels de réinstallation des migrants, les effets de compétition entre individus migrants et les contraintes imposées par les localités d’accueil (telles que les limites de capacité et la distribution des ressources) augmentent encore la complexité de ce problème. Pour y répondre, cette recherche propose un cadre basé sur l’optimisation multiobjectif évolutive (Evolutionary Multiobjective Optimization, EMO) appelé MR-EMO (Migrant Resettlement by EMO). L’objectif de cette étude est d’explorer des solutions surpassant, tant théoriquement que pratiquement, les algorithmes gloutons traditionnels grâce à une nouvelle modélisation et conception algorithmique.

Processus de recherche

L’article reformule le problème de réinstallation des migrants, passant d’une approche d’optimisation sous-modulaire classique à un problème d’optimisation à deux objectifs (biobjective optimization), introduisant des cadres méthodologiques et algorithmiques remarquablement innovants. Le processus de recherche comprend principalement les étapes suivantes :

1. Modélisation du problème et formulation mathématique

Les auteurs transforment la modélisation traditionnelle à un objectif en un problème à deux objectifs : - Le premier objectif consiste à maximiser le nombre attendu de migrants employés (expected number of employed migrants), une mesure directe de l’efficacité du placement des migrants. - Le deuxième objectif vise à minimiser le nombre de migrants dispatchés (number of dispatched migrants), pour optimiser la rentabilité économique et l’utilisation des ressources.

Ce processus de modélisation formule explicitement les contraintes complexes du problème de réinstallation, telles que les limites de capacité de chaque localité d’accueil (locality capacity) et l’unicité d’allocation pour chaque migrant (chaque migrant ne pouvant être assigné qu’à une seule localité). Ces contraintes sont représentées au moyen de contraintes d’intersection de matroïdes (matroid constraints).

2. Conception algorithmique basée sur le cadre EMO

L’article propose le cadre MR-EMO et implémente trois instances algorithmiques typiques d’optimisation multiobjectif : - NSGA-II (Nondominated Sorting Genetic Algorithm II) : Cet algorithme se base sur le tri de Pareto (Pareto sorting) et la distance d’encombrement (crowding distance) pour l’évolution. - MOEA/D (Multiobjective Evolutionary Algorithm based on Decomposition) : Cet algorithme réduit la complexité de l’optimisation multiobjectif en décomposant le problème. - GSEMO (Global Simple Evolutionary Multiobjective Optimizer) : Une approche théorique combinant des opérations génétiques simples.

En outre, les chercheurs ont développé un nouvel algorithme, spécifiquement conçu pour le problème de réinstallation des migrants : GSEMO-SR. Cet algorithme intègre les mécanismes suivants pour surmonter les limitations des opérateurs évolutifs traditionnels : 1. L’opérateur de mutation Matrix-Swap : Cet opérateur génère des solutions descendantes en échangeant les lignes ou colonnes de la matrice représentant les solutions, assurant ainsi leur faisabilité. 2. Mécanisme de réparation (Repair Mechanism) : Ce mécanisme ajuste aléatoirement les bits non conformes dans les solutions infaisables pour les rendre conformes aux contraintes de matroïdes, évitant ainsi leur élimination directe.

3. Analyse théorique et garantie

L’étude démontre que les algorithmes basés sur GSEMO ou GSEMO-SR dans le cadre MR-EMO peuvent fournir des garanties théoriques supérieures à celles des algorithmes gloutons traditionnels. En construisant des solutions quasi-optimales, l’analyse théorique des algorithmes montre que GSEMO-SR atteint un niveau de performance de 1/(k + 1/p + 2εr / (1−ε)), surpassant celui de 1/(k + 1 + 4εr / (1−ε)) obtenu avec l’algorithme glouton.

4. Validation expérimentale

Les chercheurs ont testé leur approche sur deux modèles de migration (le modèle d’interview et le modèle de coordination). Leurs expérimentations ont généré des configurations diversifiées de migrants et localités (par exemple, en variant le nombre de migrants, de localités, les types de professions et les contraintes de capacité). Les performances des algorithmes sont comparées avec celles des méthodes gloutonnes et additives à l’aide d’analyses statistiques.

Résultats principaux de l’étude

1. Améliorations théoriques garanties
   Les nouveaux algorithmes proposés dans le cadre MR-EMO augmentent considérablement les garanties théoriques en optimisation multiobjectif, surpassant significativement les algorithmes gloutons classiques, notamment dans des environnements hautement contraints.

2. Validation des performances algorithmiques
   Pour divers scénarios (nombre de migrants, localités, professions, etc.), GSEMO-SR s’est démarqué comme la meilleure solution parmi toutes les approches testées. En particulier, dans les conditions les plus complexes, l’algorithme maintient des performances supérieures avec un coût de calcul relativement faible.

3. Efficacité et innovations de GSEMO-SR
   Les innovations introduites, à savoir l’opérateur Matrix-Swap et le mécanisme de réparation, permettent de résoudre efficacement les problèmes liés à la génération de solutions infaisables. Les résultats montrent que GSEMO-SR atteint les meilleures performances en termes de nombre attendu de migrants employés, tout en augmentant l’efficacité d’exploration de l’espace des solutions.

Signification et applications potentielles

Le cadre MR-EMO et ses algorithmes dérivés apportent une contribution significative au problème de réinstallation des migrants en offrant un outil quantitatif pour les décideurs politiques et les organisations humanitaires. Cet outil pourrait non seulement améliorer la qualité de vie de millions d’individus déplacés, mais également favoriser une harmonisation sociale et un développement économique à travers des stratégies de réinstallation plus efficaces. Les algorithmes et méthodologies proposés pourraient également trouver des applications précieuses dans d’autres domaines d’optimisation multiobjectif, tels que l’allocation de ressources ou la planification des tâches.

En combinant méthodologie innovante et conception algorithmique, cette étude améliore de manière significative le niveau d’optimisation pour le problème de réinstallation des migrants, étendant à la fois la théorie des algorithmes d’optimisation et leur utilité pratique à des fins de bénéfices sociaux et économiques.