Skip to main content

Research Repository

Advanced Search

Minimal walsh structure and ordinal linkage of monotonicity-invariant function classes on bit strings.

Christie, Lee A.; McCall, John A.W.; Lonie, David P.



Christian Igel


Problem structure, or linkage, refers to the interaction between variables in a black-box fitness function. Discovering structure is a feature of a range of algorithms, including estimation of distribution algorithms (EDAs) and perturbation methods (PMs). The complexity of structure has traditionally been used as a broad measure of problem difficulty, as the computational complexity relates directly to the complexity of structure. The EDA literature describes necessary and unnecessary interactions in terms of the relationship between problem structure and the structure of probabilistic graphical models discovered by the EDA. In this paper we introduce a classification of problems based on monotonicity invariance. We observe that the minimal problem structures for these classes often reveal that significant proportions of detected structures are unnecessary. We perform a complete classification of all functions on 3 bits. We consider nonmonotonicity linkage discovery using perturbation methods and derive a concept of directed ordinal linkage associated to optimization schedules. The resulting refined classification factored out by relabeling, shows a hierarchy of nine directed ordinal linkage classes for all 3-bit functions. We show that this classification allows precise analysis of computational complexity and parallelizability and conclude with a number of suggestions for future work.


CHRISTIE, L.A., MCCALL, J.A.W. and LONIE, D.P. 2014. Minimal walsh structure and ordinal linkage of monotonicity-invariant function classes on bit strings. In Igel, C. (ed.) Proceedings of the 2014 Genetic and evolutionary computation conference (GECCO 2014): a recombination of the 23rd International conference on genetic algorithms (ICGA-2014), and the 19th Annual genetic programming conference (GP-2014), 12-16 July 2014, Vancouver, Canada. New York: ACM [online], pages 333-340. Available from:

Conference Name 2014 Genetic and evolutionary computation conference (GECCO 2014)
Conference Location Vancouver, Canada
Start Date Jul 12, 2014
End Date Jul 16, 2014
Acceptance Date Mar 12, 2014
Online Publication Date Jul 12, 2014
Publication Date Dec 31, 2014
Deposit Date Feb 16, 2016
Publicly Available Date Feb 16, 2016
Publisher Association for Computing Machinery (ACM)
Pages 333-340
ISBN 9781450326629
Keywords Algorithms; Design; Performance; Theory; Estimation of distribution algorithms; Linkage learning; Monotonicity; Ordinal selection; Perturbation methods; Artificial intelligence; Problem solving; Control methods; Search
Public URL
Related Public URLs ; ; ;


Related Outputs

You might also like

Downloadable Citations