Improving DSMGA-II performance on hierarchical problems by introducing preservative back mixing
Journal
GECCO 2022 Companion - Proceedings of the 2022 Genetic and Evolutionary Computation Conference
ISBN
9781450392686
Date Issued
2022-07-09
Author(s)
Ngai, Chi Meng
Abstract
Inspired from the optimal mixing in the linkage tree gene-pool optimal mixing evolutionary algorithm, the dependent structure matrix genetic algorithm II (DSMGA-II) is one of the state-of-the-art model-building genetic algorithms. It obtains the patterns from successful restricted mixing and uses them during the back mixing (BM) to remove spurious linkage information such that the linkage information in need stands out. However, such techniques can be misled in hierarchical problems where the linkages in latter layers are mistreated as spurious in BM. There has been diversity preservation scheme developed for DSMGA-II by monitoring the entropy, but such technique impairs the exploration ability of DSMGA-II on plateau. To solve this issue, this paper proposes the preservative back mixing (PBM), a modified version of BM. Specifically, PBM features (i) the adaptive back mixing that automatically adjusts the power of BM and (ii) the linkage preservation that preserves the linkages among complementary patterns. This paper conducted several experiments to show that, PBM improves DSMGA-II greatly on hierarchical problems including the hierarchical trap and hierarchical exclusive-or while the NFE performances on other problems are not compromised by much.
Subjects
estimation-of-distribution algorithms | genetic algorithms | linkage learning | model building | optimal mixing
SDGs
Type
conference paper