Migrant Resettlement by Evolutionary Multi-objective Optimization

Dan-Xuan Liu, Yu-Ran Gu, Chao Qian, Xin Mu, Ke Tang

Abstract

Efficiently resettling migrants to maximize employment is a critical challenge for host nations. This paper presents MR-EMO, a framework that treats migrant resettlement as a bi-objective optimization problem. By maximizing expected employment while minimizing the total number of migrants dispatched, the framework leverages a specialized evolutionary algorithm, GSEMO-SR, to navigate complex constraints. Experimental results on synthetic models demonstrate that MR-EMO consistently outperforms traditional greedy approaches, offering superior theoretical guarantees and empirical performance.

Introduction

Global migration necessitates sophisticated strategies for integrating newcomers into the workforce. The migrant resettlement problem involves assigning individuals to localities to maximize total expected employment. This task is mathematically defined as a submodular maximization problem subject to matroid constraints: each migrant is assigned to at most one location, and each location has a finite capacity.

Figure 1: Conceptual diagram of the migrant resettlement problem, illustrating the matching of migrants to localities based on diverse professional profiles.

Traditional solutions often rely on greedy algorithms. While computationally efficient, these methods are prone to local optima and lack robust theoretical guarantees when the objective function exhibits noise or approximate submodularity (where the benefit of adding one more migrant diminishes as more are added).

The MR-EMO Framework

The proposed MR-EMO (Migrant Resettlement by Evolutionary Multi-objective Optimization) framework reformulates the problem into two conflicting objectives:

  1. Maximizing the expected number of employed migrants.
  2. Minimizing the total number of migrants dispatched.

This multi-objectivization strategy introduces diversity into the search process, allowing the algorithm to discover "stepping stone" solutions that help bypass the local optima that often trap greedy heuristics.

The core of the framework is the GSEMO-SR algorithm. Unlike standard evolutionary algorithms that use bit-wise mutation, GSEMO-SR employs a Matrix-Swap Mutation mechanism. By representing solutions as a Migrant-by-Locality matrix, the algorithm swaps rows or columns to maintain feasibility. A dedicated Repair Mechanism further ensures that any constraint violations—such as a migrant being assigned to multiple locations—are corrected by randomly removing redundant assignments.

Experimental Evaluation

The framework was evaluated using two synthetic migration models: the Interview Model, where competition is restricted to specific professions (e.g., chefs only compete with chefs), and the Coordination Model, a flexible bipartite matching scenario where migrants can potentially take jobs outside their primary profession based on compatibility probabilities.

Figure 2: Visualization of the objective function landscape during optimization. The clusters represent solution candidates, with the color scale indicating the expected employment value.

Results indicate that MR-EMO variants, particularly GSEMO-SR, consistently achieve higher objective values than standard greedy and additive algorithms. The specialized mutation and repair operators allow for a more effective exploration of the solution space, as visualized in the objective function landscape (Figure 2). The authors also mathematically proved that MR-EMO provides a tighter approximation guarantee than the best-known greedy algorithms, ensuring high performance even in worst-case scenarios.

Conclusion

MR-EMO provides a robust alternative to greedy heuristics for migrant resettlement. By leveraging multi-objective optimization and problem-specific evolutionary operators, the framework achieves superior employment outcomes. While evolutionary algorithms require more evaluations than simple greedy passes, the performance gains are significant. Future work will focus on reducing computational overhead for large-scale real-time applications and extending theoretical proofs to more complex algorithms like NSGA-II.

Summary updated

BibTeX
@article{liu2025migrant,
  author = {Dan-Xuan Liu and Yu-Ran Gu and Chao Qian and Xin Mu and Ke Tang},
  title = {{Migrant Resettlement by Evolutionary Multi-objective Optimization}},
  journal = {IEEE Trans. Artif. Intell.},
  year = {2025},
  doi = {10.1109/tai.2024.3443790},
}
Figure