Applying entire search history for parameter control of evolutionary algorithms

Abstract

Evolutionary Algorithms (EAs) are reliable, powerful and robust tools for solving optimization problems. It has been successfully applied in many different fields related to our daily lives. The performance of EA is affected by its properties in different problems. In turn, the properties of EA depend on the parameter settings. Here, parameters refer in a general sense to both the operators and the numerical parameters. Thus users need to tune the parameters to optimize the performance on different problems. When the user does not have any prior knowledge of the problem, parameter tuning is very difficult and time consuming. One needs to try different combinations of parameter values to find the best settings. One method to solve this problem is to control the parameters during the EA run. This thesis proposes a new adaptive parameter control system, called Parameter Control system using entire Search History (PCSH). It is a general add-on system which is not restricted to a specific class of EA. Users are only required to know the range of the parameters. It records the entire search history to build a surrogate model of the problem and uses the model to predict the performance of different parameter combinations. By using this idea, PCSH automatically adjusts the parameters of an EA according to the entire search history. To illustrate the performance of PCSH, it is applied to control the parameters of three common classes of EAs: 1) canonical Genetic Algorithm (GA); 2) Particle Swarm Optimization (PSO); 3) Differential Evolution (DE), and one advanced EA: 4) History-driven Evolutionary Algorithm. The test results show that, in most of the benchmark functions, the performance of the test EAs have improved or remained similar after adopting PCSH. It shows that PCSH retains or improves the performance of the test EAs while relieving the heavy burden of the algorithm designer on the setting of parameters. Inspired by self-adaptive DE algorithms, a variant version of PCSH is designed especially for DE, called History Adaptive Differential Evolution (HADE). In other self-adaptive DE algorithms such as Self-adaptive Differential Evolution (SDE), Self adaptive Differential Evolution (SaDE) and Adaptive Differential Evolution with Optional External Archive (JADE), parameter settings are individual based, assigning a parameter setting to each solution in the population. Following this general observation, HADE applies the same idea as PCSH but is modified to an individual based approach. Moreover, to control the population size parameters of HADE, a population reduction scheme is applied. The performance of HADE is compared with the original DE and three state-of-the-art self-adaptive algorithms, namely, SDE, SaDE and JADE. The result shows that HADE outperforms all these algorithms. Moreover, PCSH is applied to control the parameters of GA to solve a Heat, Ventilating, and Air Conditioning (HVAC) duct system design problem. It is found that PCSH significantly improves the performance of GA in solving the HVAC duct system design problem. The above experimental results show that the idea of PCSH can help to find the appropriate setup for the test algorithms and maintain or even improve the performance. The use of entire search history brings positive effects to parameter control in EA, through which the burden of users in setting parameters can be released.

Date of Award	15 Jul 2013
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Shiu Yin Kelvin YUEN (Supervisor)