An Evolutionary Algorithm Taking Account of Epistasis among Parameters for Black-Box Discrete Optimization
Sho Shimazu, Isao Ono · 2021
We propose an evolutionary algorithm that takes account of epistasis among parameters for black-box discrete optimization problems. The black-box discrete optimization (BB-DO) is an important problem that appears in various real-world problems such as hyper-parameter optimization of machine learning and is a difficult class of optimization problems to which optimization methods that require derivative of an objective function cannot be applied. In addition, epistasis among parameters, or the dependencies among variables, makes BB-DO problems more difficult. The bayesian optimization algorithm (BOA) has been proposed as a promising method to address epistasis in BB-DO problems. However, BOA suffers from a serious problem. The problem is that the diversity of a population is likely to be lost. Therefore, BOA requires a large population size for optimization. In order to remedy the problem of BOA, we introduce three schemes to maintain the diversity of the population into BOA. In experiments, we use two benchmark problems, a 3-deceptive function and a NK-landscape, and a structural optimization of neural networks to show the effectiveness of the proposed method. The experimental results showed that the proposed method improved the number of evaluations by 31.5% and the population size by 96.9% in a 180-dimensional 3-deceptive function and found comparable or better solutions in all NK-landscape settings compared to BOA. In the structural optimization of neural networks, the proposed method improved the number of evaluations by 21.3% and the population size by 92.3% compared to BOA. In addition, the proposed method was superior to conventional optimization methods used in this field, ASNG-NAS, regularized evolution, reinforcement learning, TPE, and random search, in terms of the evaluation value.