Abstract
Evolutionary Multiobjective Multitasking (EMOMT) aims to solve multiple optimization tasks simultaneously by leveraging knowledge transfer via inter-task crossover. While effective, the spatial relationship between parent solutions from different tasks significantly influences the resulting offspring's location in the decision space. This paper investigates how parent selection strategies—specifically based on spatial distance—impact search efficiency and convergence. Our findings suggest a 'Goldilocks' principle: while selecting migrants close to the target task's population aids convergence, selecting crossover partners that are too close can trap the search in local optima due to a loss of diversity.
Introduction
In EMOMT, the primary mechanism for performance gain is inter-task crossover, where solutions from different tasks are bred to share useful traits. However, if parents are chosen from distant regions of the decision space, their offspring may fall into unproductive 'no-man's land.' Conversely, if they are too close, the search may become overly narrow. This study systematically explores these spatial dynamics to optimize parent selection strategies.
Methodology: The Island Model
To isolate the effects of selection strategies, the researchers employed an Island Model EMOMT. In this framework, each task is assigned a dedicated 'island' or population.
The process follows a specific cycle as shown in the figure above:
- Selection (i): Parents are selected from the current population.
- Migration (ii): Individuals move between islands to facilitate cross-task breeding.
- Crossover (iii): Offspring are generated through inter-task or intra-task crossover.
- Replacement (iv): The next generation is formed.
The study compared Migration Selection (Random vs. Shortest Distance) and Crossover Partner Selection (Random vs. Nearest Neighbor) across nine benchmark problems categorized by task similarity and optimality intersection.
Spatial Dynamics and the 'Goldilocks' Distance
The core of the investigation lies in how the distance between parents defines the 'offspring generation area.'
As illustrated in the figure above, selecting parents that are physically far apart (b) results in a vast search area, which can be inefficient for convergence. However, selecting the 'Nearest Neighbor' (c) restricts the search to a very small region. While this might seem efficient for fine-tuning, it often leads to premature convergence and stagnation in local optima because the population loses the diversity needed to explore the landscape.
Key Results
Performance was evaluated using Inverted Generational Distance (IGD), where lower values indicate better convergence.
- Optimal Strategy: The combination of Shortest Distance Migration and Random Crossover performed best. This approach brings 'compatible' migrants into the island but maintains enough diversity during crossover to explore effectively.
- The Proximity Trap: Nearest Neighbor crossover consistently underperformed. By forcing migrants to breed with their closest local counterparts, the algorithm's search became too narrow, particularly in tasks with high landscape similarity (CI+HS).
- Task Dependency: These effects were most pronounced in the early stages of the search (around 200 generations). In tasks with no intersection (NI), the selection method had less impact as the populations naturally operated in disjoint regions.
Conclusion
This research highlights that spatial awareness in parent selection is a double-edged sword. While bringing similar tasks closer through intelligent migration is beneficial, maintaining a degree of randomness in partner selection is crucial for global search ability. Future work will investigate selection methods that consider both decision space and objective space distances to further refine EMOMT performance.
Summary updated