Density-Assisted Evolutionary Dynamic Multimodal Optimization
Ying Zhu, Peilan Xu, Jiahao Huang, Xin Bo Lin, Wenjian Luo · ACM Transactions on Evolutionary Learning and Optimization · 2025
Dynamic Multimodal Optimization Problems (DMMOPs) demand algorithms capable of swiftly locating and tracking multiple optimal solutions over time. The primary challenge lies in controlling the population diversity to facilitate effective exploration, all within the limitation of computational resources between consecutive environmental changes. In this article, we study the utilization of density information derived from both current and historical populations to enhance exploration. First, for each active sub-population, we construct a density landscape based on the distribution of concurrently active sub-populations and establish dominance relationships between candidate solutions in the sub-population based on density and fitness values, directing this sub-population toward exploring low-density promising areas. Then, for each converged sub-population, we construct a density landscape based on the distribution of sub-populations that have historically become extinct, guiding the restart of this sub-population in low-density unexploited areas. Finally, we develop a comprehensive framework of Density-Assisted Evolutionary Algorithm (DAEA), which encompasses density-assisted search and restart, also combined with initialization. Moreover, we employ prediction and memory strategies to enhance the performance of DAEA in dynamic environments. Notably, the algorithm relies on an external monitor to detect environmental changes and trigger the dynamic response strategy. DAEA is tested on the CEC’2022 dynamic multimodal optimization benchmark suite and is compared against several state-of-the-art dynamic multimodal optimization algorithms. The experimental results demonstrate the competitiveness of DAEA in handling DMMOPs. Additionally, experimental results from the berth allocation problem further confirm the applicability of DAEA to real-world dynamic multimodal optimization tasks.