Effects of Parent Selection in Inter-Task Crossover on the Search Ability of Evolutionary Multiobjective Multitasking

Ryuichi Hashimoto, Naoki Masuyama, Yusuke Nojima, Hisao IshibuchiJournal of Japan Society for Fuzzy Theory and Intelligent Informatics 2020 · DOI

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 Island Model EMOMT framework illustrates the cycle of local evolution and inter-task migration.

The process follows a specific cycle as shown in the figure above:

  1. Selection (i): Parents are selected from the current population.
  2. Migration (ii): Individuals move between islands to facilitate cross-task breeding.
  3. Crossover (iii): Offspring are generated through inter-task or intra-task crossover.
  4. 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.'

Comparison of offspring generation areas (purple dashed boxes) based on parent distance. (a) Standard selection, (b) Distant parents creating a large search area, (c) Nearby parents creating a restricted search 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

Abstract

複数の多目的最適化問題(タスク)を同時に解く進化型多目的マルチタスク最適化手法(Evolutionary Multiobjective Multitasking: EMOMT)に関する研究が近年盛んに行われている.EMOMTの特徴として,タスク毎に個体群を生成して探索を行い,探索途中で異なるタスクを解く個体間で交叉を行う点が挙げられる.タスク間の交叉により生成された子個体を各タスクの個体群に追加することでEMOMTの探索性能の向上が報告されている.タスク間の交叉において,決定変数空間における親個体の位置が極端に離れると子個体の生成領域が非常に大きくなるなど,決定変数空間における親個体の位置は生成する子個体,さらに次世代の個体群に大きな影響を及ぼすと考えられるが,十分に調査されていない.そこで本研究では決定変数空間内の親個体の位置に着目し,親個体の選択方法が探索性能へ与える影響を調査する.
BibTeX
@article{hashimoto2020effects,
  author = {Ryuichi Hashimoto and Naoki Masuyama and Yusuke Nojima and Hisao Ishibuchi},
  title = {{Effects of Parent Selection in Inter-Task Crossover on the Search Ability of Evolutionary Multiobjective Multitasking}},
  journal = {Journal of Japan Society for Fuzzy Theory and Intelligent Informatics},
  year = {2020},
  doi = {10.3156/jsoft.32.1\_501},
}
Figure