Performance Evaluation of the Parallel Polytree Approximation Distribution Algorithm on Three Network Technologies

This paper proposes two parallel versions of an Estimation of Distribution Algorithm (EDA) that represents the probability distribution by means of a single connected graphical model based on a polytree structure (PADA). The main goal is to design a new and more efficient EDA. Our algorithm (pPADA) is based on the master/slave model which allows to perform the estimation of the probability distribution (the most time-consuming phase in EDAs) in a parallel way. The aim of our experimental studies is manifold. Firstly, we show that our parallel versions achieve a notable reduction of the total execution time with respect to existing algorithms. Secondly, we study the behavior of the algorithm from the numerical point of view, analyzing the different versions. Finally, our methods are evaluated over three interconnection networks (Fast Ethernet, Gigabit Ethernet, and Myrinet) and a study on the influence of the parallel platform in the communication is performed