IMPLEMENTATION AND PERFORMANCE EVALUATION OF A PARALLELIZATION OF ESTIMATION OF BAYESIAN NETWORK ALGORITHMS
Abstract
This paper presents, discusses and evaluates parallel implementations of a set of algorithms designed for optimization tasks: Estimation of Bayesian Network Algorithms (EBNAs). These algorithms belong to the family of Evolutionary Computation. Two different APIs have been combined: message passing and threads, with the aim of obtaining good performance levels in a wide range of parallel machines. Our approach has been to analyze the most computationally intensive sections of sequential implementations of EBNAs, and then to parallelize those sections using a master-worker design pattern. This way the resulting program exhibits exactly the same behavior of the sequential one, but runs faster. To evaluate our proposal, we have chosen a complex scenario where EBNAs can be applied: Feature Subset Selection (FSS) for supervised classification problems. For the experiments, three computing systems have been tested: two different clusters built from commodity components, and an 8-way multiprocessor. Programs have been executed on the target machines using different combination of message-passing processes and threads. Achieved performance is excellent, with efficiency around 1. These encouraging results do widen the spectrum of problems (and problem sizes) that can be solved, in reasonable times, with EBNAs.
This work has been done with the support of the Government of the Basque Country (ETORTEK NASH) and the Spain's MEC (TIN 2004-07440-C02-02 and TIN 2005-03824).
References
-
T. Bäck , Evolutionary Algorithms in Theory and Practice ( Oxford University Press , 1996 ) . Crossref, Google Scholar H. Mühlenbein and G. Paaß , Parallel Problem Solving from Nature - PPSN IV,Lecture Notes in Computer Science 1411 (1996) pp. 178–187. Crossref, Google Scholar-
P. Larrañaga and J. A. Lozano , Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation ( Kluwer Academic Publishers , 2002 ) . Crossref, Google Scholar J. A. Lozano , R. Sagarna and P. Larrañaga , Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation (2002) pp. 129–145. Crossref, Google ScholarJ. Ocenasek and J. Schwarz , The Parallel Bayesian Optimization Algorithm, Proceedings of the European Symposium on Computational Intelligence (2000) pp. 61–67. Google ScholarJ. Ocenasek and J. Schwarz , The Distributed Bayesian Optimization Algorithm for combinatorial optimization, EUROGEN - Evolutionary Methods for Design, Optimisation and Control (CIMNE, 2001) pp. 115–120. Google ScholarM. Pelikan , D. E. Goldberg and E. Cantú-Paz , BOA: The Bayesian optimization algorithm, Proceedings of the Genetic and Evolutionary Computation Conference GECCO-99 (1999) pp. 525–532. Google Scholar- The International Journal of Supercomputer Applications and High Performance Computing 8(3/4), 159 (1994). Google Scholar
-
D. R. Butenhof , Programming with POSIX Threads ,Addison-Wesley Professional Computing Series ( 1997 ) . Google Scholar -
A. A. Zhigljavsky , Theory of Global Random Search ( Kluwer Academic Publishers , 1991 ) . Crossref, Google Scholar - Computational Optimization and Applications 21(1), 5 (2002), DOI: 10.1023/A:1013500812258. Crossref, ISI, Google Scholar
- Evolutionary Computation 7(4), 353 (1999). Crossref, ISI, Google Scholar
-
E. Castillo , J. M. Gutiérrez and Ali S. Hadi , Expert Systems and Probabilistic Network Models ( 1997 ) . Crossref, Google Scholar - IEEE Transactions on Evolutionary Computation 9(4), (2005), DOI: 10.1109/TEVC.2005.850299. Google Scholar
-
H. Liu and H. Motoda , Feature Selection for Knowledge Discovery and Data Mining ( 1998 ) . Crossref, Google Scholar - C. L. Blake and C. J. Merz, UC1 Repository of machine learning databases, http://www.ics.uci.edu/~mlearn/MLRepository.html, University of California (1998) . Google Scholar
- Annals of Statistics 7(2), 461 (1978). ISI, Google Scholar
- Uncertainty in Artificial Intelligence 2, 149 (1988). Google Scholar
I. Inza , P. Larrañaga and B. Sierra , Estimation of Distribution Algorithms. A New Tool for Evolutionary Computation (2002) pp. 269–294. Crossref, Google Scholar- Artificial Intelligence 123(1-2), 157 (2000), DOI: 10.1016/S0004-3702(00)00052-7. Crossref, ISI, Google Scholar


