UEGO, an abstract clustering technique for multimodal global optimization

In this paper, UEGO, a new general technique for accelerating and/or parall elizing existing search methods is suggested. The skeleton of the algorithm is a parallel hill climber. The separate hill climbers work in restricted search regions (or clusters) of the search space. The volume of the cluster s decreases as the search proceeds which results in a cooling effect simila r to simulated annealing. Besides this, UEGO can be effectively parallelize d; the communication between the clusters is minimal. The purpose of this c ommunication is to ensure that one hill is explored only by one hill climbe r. UEGO makes periodic attempts to find new hills to climb. Empirical resul ts are also presented which include an analysis of the effects of the user- given parameters and a comparison with a hill climber and a GA.