Research output

Conference Paper (in Formal Publication) ()

Minimal Walsh Structure and Ordinal Linkage of Monotonicity-Invariant Function Classes on Bit Strings

Citation
Christie LA, McCall J & Lonie D (2014) Minimal Walsh Structure and Ordinal Linkage of Monotonicity-Invariant Function Classes on Bit Strings In: Igel C (ed.) Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, New York: ACM. 2014 Annual Conference on Genetic and Evolutionary Computation, 12.7.2014 - 16.7.2016, Vancouver, Canada, pp. 333-340.

Abstract
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.

Keywords
Estimation of Distribution Algorithms; Linkage Learning; Monotonicity;Ordinal Selection; Perturbation Methods

Related dataset
https://openair.rgu.ac.uk/handle/10059/1585

StatusPublished
EditorIgel C
AuthorsChristie Lee A, McCall John, Lonie David
Publication date2014
Date of public distribution07/2014
URLhttp://dl.acm.org/citation.cfm?id=2598240
PublisherACM
Place of publicationNew York
ISBN 978-1-4503-2662-9
LanguageEnglish
© University of Stirling FK9 4LA Scotland UK • Telephone +44 1786 473171 • Scottish Charity No SC011159
My Portal