  Estimation of Distribution Algorithms have been proposed as a new paradigm
for evolutionary optimization. This paper focuses on the parallelization of
Estimation of Distribution Algorithms. More specifically, the paper discusses
how to predict performance of parallel Mixed Bayesian Optimization Algorithm
(MBOA) that is based on parallel construction of Bayesian networks with
decision trees. We determine the time complexity of parallel Mixed Bayesian
Optimization Algorithm and compare this complexity with experimental results
obtained by solving the spin glass optimization problem. The empirical results
fit well the theoretical time complexity, so the scalability and efficiency of
parallel Mixed Bayesian Optimization Algorithm for unknown instances of spin
glass benchmarks can be predicted. Furthermore, we derive the guidelines that
can be used to design effective parallel Estimation of Distribution Algorithms
with the speedup proportional to the number of variables in the problem.
