Efficiency enhancement techniques such as
parallelisation and hybridisation are among the most
important ingredients of practical applications of
genetic and evolutionary algorithms and that is why
this research area represents an important niche of
evolutionary computation. This paper describes and
analyses sporadic model building, which can be used to
enhance the efficiency of the hierarchical Bayesian
optimisation algorithm (hBOA) and other estimation of
distribution algorithms (EDAs) that use complex
multivariate probabilistic models. With sporadic model
building, the structure of the probabilistic model is
updated once in every few iterations (generations),
whereas in the remaining iterations, only model
parameters (conditional and marginal probabilities) are
updated. Since the time complexity of updating model
parameters is much lower than the time complexity of
learning the model structure, sporadic model building
decreases the overall time complexity of model
building. The paper shows that for boundedly difficult
nearly decomposable and hierarchical optimization
problems, sporadic model building leads to a
significant model-building speedup, which decreases the
asymptotic time complexity of model building in hBOA by
a factor of $$\Uptheta(n^0.26)$$ to
$$\Uptheta(n^0.5),$$ where n is the problem size. On
the other hand, sporadic model building also increases
the number of evaluations until convergence;
nonetheless, if model building is the bottleneck, the
evaluation slowdown is insignificant compared to the
gains in the asymptotic complexity of model building.
The paper also presents a dimensional model to provide
a heuristic for scaling the structure-building period,
which is the only parameter of the proposed sporadic
model-building approach. The paper then tests the
proposed method and the rule for setting the
structure-building period on the problem of finding
ground states of 2D and 3D Ising spin glasses.
%0 Journal Article
%1 Pelikan:2008:GPEM
%A Pelikan, Martin
%A Sastry, Kumara
%A Goldberg, David E.
%D 2008
%J Genetic Programming and Evolvable Machines
%K BOA, Bayesian Efficiency Estimation HBOA, Hierarchical Sporadic algorithm, algorithms, building distribution enhancement, genetic model of optimisation
%N 1
%P 53--84
%R doi:10.1007/s10710-007-9052-8
%T Sporadic model building for efficiency enhancement of
the hierarchical BOA
%V 9
%X Efficiency enhancement techniques such as
parallelisation and hybridisation are among the most
important ingredients of practical applications of
genetic and evolutionary algorithms and that is why
this research area represents an important niche of
evolutionary computation. This paper describes and
analyses sporadic model building, which can be used to
enhance the efficiency of the hierarchical Bayesian
optimisation algorithm (hBOA) and other estimation of
distribution algorithms (EDAs) that use complex
multivariate probabilistic models. With sporadic model
building, the structure of the probabilistic model is
updated once in every few iterations (generations),
whereas in the remaining iterations, only model
parameters (conditional and marginal probabilities) are
updated. Since the time complexity of updating model
parameters is much lower than the time complexity of
learning the model structure, sporadic model building
decreases the overall time complexity of model
building. The paper shows that for boundedly difficult
nearly decomposable and hierarchical optimization
problems, sporadic model building leads to a
significant model-building speedup, which decreases the
asymptotic time complexity of model building in hBOA by
a factor of $$\Uptheta(n^0.26)$$ to
$$\Uptheta(n^0.5),$$ where n is the problem size. On
the other hand, sporadic model building also increases
the number of evaluations until convergence;
nonetheless, if model building is the bottleneck, the
evaluation slowdown is insignificant compared to the
gains in the asymptotic complexity of model building.
The paper also presents a dimensional model to provide
a heuristic for scaling the structure-building period,
which is the only parameter of the proposed sporadic
model-building approach. The paper then tests the
proposed method and the rule for setting the
structure-building period on the problem of finding
ground states of 2D and 3D Ising spin glasses.
@article{Pelikan:2008:GPEM,
abstract = {Efficiency enhancement techniques such as
parallelisation and hybridisation are among the most
important ingredients of practical applications of
genetic and evolutionary algorithms and that is why
this research area represents an important niche of
evolutionary computation. This paper describes and
analyses sporadic model building, which can be used to
enhance the efficiency of the hierarchical Bayesian
optimisation algorithm (hBOA) and other estimation of
distribution algorithms (EDAs) that use complex
multivariate probabilistic models. With sporadic model
building, the structure of the probabilistic model is
updated once in every few iterations (generations),
whereas in the remaining iterations, only model
parameters (conditional and marginal probabilities) are
updated. Since the time complexity of updating model
parameters is much lower than the time complexity of
learning the model structure, sporadic model building
decreases the overall time complexity of model
building. The paper shows that for boundedly difficult
nearly decomposable and hierarchical optimization
problems, sporadic model building leads to a
significant model-building speedup, which decreases the
asymptotic time complexity of model building in hBOA by
a factor of $$\Uptheta(n^{0.26})$$ to
$$\Uptheta(n^{0.5}),$$ where n is the problem size. On
the other hand, sporadic model building also increases
the number of evaluations until convergence;
nonetheless, if model building is the bottleneck, the
evaluation slowdown is insignificant compared to the
gains in the asymptotic complexity of model building.
The paper also presents a dimensional model to provide
a heuristic for scaling the structure-building period,
which is the only parameter of the proposed sporadic
model-building approach. The paper then tests the
proposed method and the rule for setting the
structure-building period on the problem of finding
ground states of 2D and 3D Ising spin glasses.},
added-at = {2008-06-19T17:46:40.000+0200},
author = {Pelikan, Martin and Sastry, Kumara and Goldberg, David E.},
biburl = {https://www.bibsonomy.org/bibtex/2387e39e186dfdd975392f6d88eefd69f/brazovayeye},
doi = {doi:10.1007/s10710-007-9052-8},
interhash = {9b36c8db5180285829e699a2ddedee74},
intrahash = {387e39e186dfdd975392f6d88eefd69f},
issn = {1389-2576},
journal = {Genetic Programming and Evolvable Machines},
keywords = {BOA, Bayesian Efficiency Estimation HBOA, Hierarchical Sporadic algorithm, algorithms, building distribution enhancement, genetic model of optimisation},
month = {March},
number = 1,
pages = {53--84},
size = {32 pages},
timestamp = {2008-06-19T17:49:22.000+0200},
title = {Sporadic model building for efficiency enhancement of
the hierarchical {BOA}},
volume = 9,
year = 2008
}