Two Approaches for Parallelizing the UEGO Algorithm

TitleTwo Approaches for Parallelizing the UEGO Algorithm
Publication TypeBook Chapter
Year of Publication2001
AuthorsOrtigosa P.M, García I., Jelásity M.
EditorGiannessi F, Pardalos P, Rapcsák T
Book TitleOptimization Theory: Recent Developments from Mátraháza
PublisherSpringer US
Place PublishedBoston, MA
ISBN Number978-1-4613-0295-7

In this work UEGO, a new stochastic optimization technique for accelerating and/or parallelizing existing search methods is described and parallelized. The skeleton of the algorithm is a parallel hillclimber. The separate hillclimbers work in restricted search regions (or clusters) of the search space. The volume of the clusters decreases as the search proceeds which results in a cooling effect similar to simulated annealing. Вesides this, UEGO can be effectively parallelized because the amount of information exchanged among clusters (communication) is minimal. The purpose of this communication is to ensure that a hill is explored only by one hillclimber. UEGO makes periodic attempts to find new hills to climb. Two parallel algorithms of UEGO have been implemented and empirical results are also presented including an analysis of speedup.