Title :
Parallel cross-entropy optimization
Author :
Evans, Gareth E. ; Keith, Jonathan M. ; Kroese, Dirk P.
Author_Institution :
Univ. of Queensland, Brisbane
Abstract :
The cross-entropy (CE) method is a modern and effective optimization method well suited to parallel implementations. There is a vast array of problems today, some of which are highly complex and can take weeks or even longer to solve using current optimization techniques. This paper presents a general method for designing parallel CE algorithms for multiple instruction multiple data (MIVID) distributed memory machines using the message passing interface (MPI) library routines. We provide examples of its performance for two well-known test-cases: the (discrete) Max-Cut problem and (continuous) Rosenbrock problem. Speedup factors and a comparison to sequential CE methods are reported.
Keywords :
application program interfaces; distributed memory systems; entropy; message passing; optimisation; parallel algorithms; parallel machines; parallel memories; MIMD distributed memory machine; message passing interface library routine; multiple instruction multiple data; parallel cross-entropy optimization algorithm; Algorithm design and analysis; Design methodology; Entropy; Iterative methods; Libraries; Mathematics; Message passing; Optimization methods; Sampling methods; Testing;
Conference_Titel :
Simulation Conference, 2007 Winter
Conference_Location :
Washington, DC
Print_ISBN :
978-1-4244-1306-5
Electronic_ISBN :
978-1-4244-1306-5
DOI :
10.1109/WSC.2007.4419854
