A Research Report on a New Framework for Solving Migrant Resettlement Using Multiobjective Evolutionary Optimization

Against the backdrop of accelerated globalization and evolving socio-economic conditions, migration has become an undeniable global trend. From the perspective of humanitarian relief or the sustainable development of a globalized economy, effectively managing and resettling migrants has emerged as a complex and critical issue. Statistics reveal that as of 2019, the total number of international migrants surpassed 272 million—significantly exceeding previous forecasts—and this trend is expected to continue in the future. However, alongside this surge in migration, several challenges arise during the resettlement process: How can we enhance the employment rate of migrants? How can we allocate them to suitable localities effectively? Answers to these questions have significant implications not only for migrants themselves but also for host countries and economic and cultural welfare at large.

This global issue forms the focus of a study co-conducted by a collaborative team of researchers from Nanjing University, Peng Cheng Laboratory, and the Southern University of Science and Technology. The authors, including Dan-Xuan Liu, Yu-Ran Gu, Chao Qian (Senior Member, IEEE), Xin Mu, and Ke Tang (Fellow, IEEE), published their findings in the January 2025 issue of IEEE Transactions on Artificial Intelligence (TAI) under the title Migrant Resettlement by Evolutionary Multiobjective Optimization. The study proposes a novel framework to address the migrant resettlement problem and demonstrates its superiority through theoretical and experimental evidence.

Research Background and Objectives

Traditional migrant resettlement methods have frequently relied on the greedy algorithm, widely used for its relatively high efficiency and theoretical simplicity. However, the very nature of the greedy approach limits it to local optimization, making it prone to the restrictions of myopic strategies. In real-world scenarios, the competitive effects among migrants and constraints associated with host localities (e.g., capacity limitations, resource allocation) further amplify the complexity of this problem. Addressing these challenges, the study introduces a new framework for migrant resettlement based on evolutionary multiobjective optimization (EMO), referred to as MR-EMO (Migrant Resettlement by EMO). The research aims to explore solutions that surpass traditional greedy algorithms in both theoretical rigor and practical performance by incorporating innovative modeling techniques and algorithmic designs.

Research Workflow

The paper redefines the migrant resettlement problem by transitioning from traditional submodular optimization modeling to a biobjective optimization framework. The structured research workflow includes the following key steps:

1. Problem Modeling and Mathematical Representation

The study expands the traditional single-objective optimization framework into a biobjective formulation: - Objective 1: Maximize the expected number of employed migrants, which serves as a direct measure of the effectiveness of resettlement. - Objective 2: Minimize the number of dispatched migrants, optimizing the economic efficiency and resource utilization of the resettlement strategy.

This formalized modeling approach incorporates complex constraints embedded in the real-world problem, including locality capacity limitations and the exclusivity of migrant assignments (i.e., each migrant can only be assigned to one locality). These constraints are mathematically expressed through intersecting matroid constraints.

2. Algorithm Design Based on the EMO Framework

The paper proposes the MR-EMO framework and demonstrates specific implementations of it using the following three representative multiobjective optimization algorithms: - NSGA-II (Nondominated Sorting Genetic Algorithm II): This algorithm evolves solutions based on Pareto sorting and crowding distance. - MOEA/D (Multiobjective Evolutionary Algorithm based on Decomposition): It decomposes multiobjective optimization problems to reduce complexity. - GSEMO (Global Simple Evolutionary Multiobjective Optimizer): A theoretically grounded approach that combines simple genetic operators.

Additionally, the researchers developed a novel algorithm, “GSEMO-SR,” specifically tailored for the migrant resettlement problem. This algorithm incorporates two enhancements to address limitations of traditional genetic operations: 1. Matrix-Swap Mutation Operator: A mutation operation that generates offspring solutions by swapping rows or columns of matrices, ensuring feasibility. 2. Repair Mechanism: For infeasible solutions, this mechanism randomly adjusts over-allocated entries to meet matroid constraints, avoiding the need to discard infeasible solutions outright.

3. Theoretical Analysis and Guarantees

The study demonstrates that MR-EMO using either GSEMO or GSEMO-SR achieves stronger theoretical guarantees than traditional greedy algorithms. By constructing approximately optimal solutions, the theoretical analysis shows that GSEMO-SR achieves an optimization performance level of (1/(k + 1/p + 2\epsilon r / (1-\epsilon))), which significantly outperforms the greedy algorithm’s guarantee of (1/(k + 1 + 4\epsilon r / (1-\epsilon))).

4. Experimental Validation

The study validates its findings experimentally using two migration models (the interview model and the coordination model). Simulated data included diverse configurations of migrants and localities (e.g., different numbers of migrants, localities, job types, and capacity limitations). Performance was assessed by comparing MR-EMO variants with traditional algorithms, including the greedy method and the additive algorithm, using statistical analyses.

Key Findings and Results

1. Theoretical Guarantees

The new algorithms based on the MR-EMO framework demonstrably improve theoretical guarantees for multiobjective optimization, notably offering superior solution exploration capabilities under complex constraints compared to classic greedy methods. Experimental results indicate that this approach consistently outperforms others in maximizing the expected number of employed migrants.

2. Algorithm Performance

Under varying conditions—including changes in the number of migrants, localities, and professions—GSEMO-SR demonstrates the best performance across both migration models. Even under high-complexity conditions, the new algorithm maintains its superior performance with relatively lower computational costs.

3. Innovation and Efficiency of GSEMO-SR

The introduction of the Matrix-Swap Operator and Repair Mechanism effectively addresses the challenge of generating infeasible offspring solutions in traditional frameworks. In experimental tests, GSEMO-SR not only achieves the highest expected employment outcomes but also significantly enhances exploratory efficiency in the solution space.

Significance and Practical Applications

The MR-EMO framework and its derivative algorithms present a significant breakthrough in addressing the migrant resettlement optimization problem, offering a novel quantitative tool for policymakers and humanitarian organizations. This tool not only improves the quality of life for millions of displaced individuals but also fosters harmonious social and economic development through more effective resettlement strategies. Furthermore, the proposed algorithms and theoretical methodologies have potential applications in other multiobjective optimization problems, such as resource allocation and task scheduling.

Through innovative modeling and algorithmic design, this paper elevates the optimization capability for the migrant resettlement problem, enhancing both the theoretical foundations of optimization algorithms and their impactful, real-world applications.