Working under the premise that most optimisable
functions are of bounded epistasis, this paper
addresses the problem of discovering the linkage
structure of a black-box function with a domain of
arbitrary-cardinality under the assumption of bounded
epistasis. To model functions of bounded epistasis, we
develop a generalisation of the mathematical model of
embedded landscapes over domains of cardinality M. We
then generalise the Walsh transform as a discrete
Fourier transform, and develop algorithms for linkage
learning of epistatically bounded GELs. We propose
Generalised Embedding Theorem that models the
relationship between the underlying decomposable
structure of GEL and its Fourier coefficients. We give
a deterministic algorithm to exactly calculate the
Fourier coefficients of GEL with bounded epistasis.
Complexity analysis shows that the epistatic structure
of epistatically bounded GEL can be obtained after a
polynomial number of function evaluations. Finally, an
example experiment of the algorithm is presented.
%0 Journal Article
%1 Zhou:2008:GPEM
%A Zhou, Shude
%A Heckendorn, Robert B.
%A Sun, Zengqi
%D 2008
%J Genetic Programming and Evolvable Machines
%K Epistasis, Fourier Generalised Linkage Problem algorithms, detection, embedded genetic landscape, structure transform,
%N 2
%P 125--155
%R doi:10.1007/s10710-007-9045-7
%T Detecting the epistatic structure of generalized
embedded landscape
%V 9
%X Working under the premise that most optimisable
functions are of bounded epistasis, this paper
addresses the problem of discovering the linkage
structure of a black-box function with a domain of
arbitrary-cardinality under the assumption of bounded
epistasis. To model functions of bounded epistasis, we
develop a generalisation of the mathematical model of
embedded landscapes over domains of cardinality M. We
then generalise the Walsh transform as a discrete
Fourier transform, and develop algorithms for linkage
learning of epistatically bounded GELs. We propose
Generalised Embedding Theorem that models the
relationship between the underlying decomposable
structure of GEL and its Fourier coefficients. We give
a deterministic algorithm to exactly calculate the
Fourier coefficients of GEL with bounded epistasis.
Complexity analysis shows that the epistatic structure
of epistatically bounded GEL can be obtained after a
polynomial number of function evaluations. Finally, an
example experiment of the algorithm is presented.
@article{Zhou:2008:GPEM,
abstract = {Working under the premise that most optimisable
functions are of bounded epistasis, this paper
addresses the problem of discovering the linkage
structure of a black-box function with a domain of
arbitrary-cardinality under the assumption of bounded
epistasis. To model functions of bounded epistasis, we
develop a generalisation of the mathematical model of
embedded landscapes over domains of cardinality M. We
then generalise the Walsh transform as a discrete
Fourier transform, and develop algorithms for linkage
learning of epistatically bounded GELs. We propose
Generalised Embedding Theorem that models the
relationship between the underlying decomposable
structure of GEL and its Fourier coefficients. We give
a deterministic algorithm to exactly calculate the
Fourier coefficients of GEL with bounded epistasis.
Complexity analysis shows that the epistatic structure
of epistatically bounded GEL can be obtained after a
polynomial number of function evaluations. Finally, an
example experiment of the algorithm is presented.},
added-at = {2008-06-19T17:46:40.000+0200},
author = {Zhou, Shude and Heckendorn, Robert B. and Sun, Zengqi},
biburl = {https://www.bibsonomy.org/bibtex/2f1a8d5fd7ebbed44ad2a370c7aa443b3/brazovayeye},
doi = {doi:10.1007/s10710-007-9045-7},
interhash = {cf74e6dfe07e7d98486473ffacf93b12},
intrahash = {f1a8d5fd7ebbed44ad2a370c7aa443b3},
issn = {1389-2576},
journal = {Genetic Programming and Evolvable Machines},
keywords = {Epistasis, Fourier Generalised Linkage Problem algorithms, detection, embedded genetic landscape, structure transform,},
month = {June},
note = {Special Issue on Theoretical foundations of
evolutionary computation},
number = 2,
pages = {125--155},
size = {31 pages},
timestamp = {2008-06-19T17:55:52.000+0200},
title = {Detecting the epistatic structure of generalized
embedded landscape},
volume = 9,
year = 2008
}