Research Repository

See what's under the surface

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

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


Lee A. Christie

John A.W. McCall

David P. Lonie


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.

Start Date Jul 12, 2014
Publication Date Dec 31, 2014
Publisher Association for Computing Machinery
Pages 333-340
ISBN 9781450326629
Institution Citation 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:
Keywords Algorithms; Design; Performance; Theory; Estimation of distribution algorithms; Linkage learning; Monotonicity; Ordinal selection; Perturbation methods; Artificial intelligence; Problem solving; Control methods; Search
Related Public URLs


Downloadable Citations