World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

IMPLEMENTATION AND PERFORMANCE EVALUATION OF A PARALLELIZATION OF ESTIMATION OF BAYESIAN NETWORK ALGORITHMS

    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 ) . CrossrefGoogle Scholar
    • H. Mühlenbein and G. Paaß, Parallel Problem Solving from Nature - PPSN IV, Lecture Notes in Computer Science 1411 (1996) pp. 178–187. CrossrefGoogle Scholar
    • P.   Larrañaga and J. A.   Lozano , Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation ( Kluwer Academic Publishers , 2002 ) . CrossrefGoogle Scholar
    • J. A. Lozano, R. Sagarna and P. Larrañaga, Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation (2002) pp. 129–145. CrossrefGoogle Scholar
    • J. Ocenasek and J. Schwarz, The Parallel Bayesian Optimization Algorithm, Proceedings of the European Symposium on Computational Intelligence (2000) pp. 61–67. Google Scholar
    • J. 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 Scholar
    • M. 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
    • Message Passing Interface ForumThe 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 ) . CrossrefGoogle Scholar
    • M. Pelikan, D. E. Goldberg and F. Lobo, Computational Optimization and Applications 21(1), 5 (2002), DOI: 10.1023/A:1013500812258. Crossref, ISIGoogle Scholar
    • H. Mühlenbein and T. Mahning, Evolutionary Computation 7(4), 353 (1999). Crossref, ISIGoogle Scholar
    • E.   Castillo , J. M.   Gutiérrez and Ali S.   Hadi , Expert Systems and Probabilistic Network Models ( 1997 ) . CrossrefGoogle Scholar
    • A. Mendiburu, J. A. Lozano and J. Miguel-Alonso, 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 ) . CrossrefGoogle 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
    • G. Schwarz, Annals of Statistics 7(2), 461 (1978). ISIGoogle Scholar
    • M. Henrion, 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. CrossrefGoogle Scholar
    • I. Inzaet al., Artificial Intelligence 123(1-2), 157 (2000), DOI: 10.1016/S0004-3702(00)00052-7. Crossref, ISIGoogle Scholar