Dynamic Island Model based on Spectral Clustering in Genetic Algorithm
This addresses diversity loss in island models for optimization, but it is incremental as it builds on existing island model approaches.
The authors tackled the problem of premature convergence in population-based optimization by proposing a dynamic island model (DIM-SP) that maintains diversity and controls island numbers dynamically, which outperformed three state-of-the-art models on optimization problems like job shop scheduling, traveling salesman, and quadratic multiple knapsack.
How to maintain relative high diversity is important to avoid premature convergence in population-based optimization methods. Island model is widely considered as a major approach to achieve this because of its flexibility and high efficiency. The model maintains a group of sub-populations on different islands and allows sub-populations to interact with each other via predefined migration policies. However, current island model has some drawbacks. One is that after a certain number of generations, different islands may retain quite similar, converged sub-populations thereby losing diversity and decreasing efficiency. Another drawback is that determining the number of islands to maintain is also very challenging. Meanwhile initializing many sub-populations increases the randomness of island model. To address these issues, we proposed a dynamic island model~(DIM-SP) which can force each island to maintain different sub-populations, control the number of islands dynamically and starts with one sub-population. The proposed island model outperforms the other three state-of-the-art island models in three baseline optimization problems including job shop scheduler problem, travelling salesmen problem and quadratic multiple knapsack problem.