Adaptive Control of Parameter-less Population Pyramid on the Local Distribution of Inferior Individuals
Kazuyuki Inoue, Taku Hasegawa, Yuta Araki, Naoki Mori, Keinosuke Matsumoto · 2015
Many evolutionary techniques such as genetic algorithms (GAs) employ parameters that facilitate user control of search dynamics. However, these parameters require time-consuming tuning processes to avoid problems such as premature convergence. Unlike many GAs, the Parameter-less Population Pyramid (P3) is an optimization model that avoids premature convergence due to the pyramid-like structure of populations, and thus P3 can be applied to a wide range of problems without parameter tuning. P3 approaches to search would be useful for constructing a novel theory for optimal search using GAs. In this study, we propose a novel technique "analysis based on the Distribution of Inferior Individuals in the local neighborhood" (DII analysis). DII analysis can be applied to local search techniques, including P3. The computational complexity of applied problems can be estimated based on a number of local optima according to the results obtained using DII. We also propose combining P3 with DII analysis (P3-DII), which controls the maximum number of fitness evaluations performed by genetic operators. The computational experiments were carried out taking several combinational problems as examples. According to our experimental results, we demonstrated that P3-DII found several optimal solutions that P3 failed to find.