Research Title: The Role of Walsh Structure and Ordinal Linkage in the Optimisation of Pseudo-Boolean Functions under Monotonicity Invariance
Start Date: October 2011
Optimisation heuristics rely on implicit or explicit assumptions about the structure of the black-box fitness function they optimise. A review of the literature shows that understanding of structure and linkage is helpful to develop and analyse heuristics. The aim of this thesis is to investigate the role that problem structure plays in heuristic optimisation.
Many heuristics use ordinal operators; those that are invariant under monotone transformation of the fitness function. In this thesis we develop a classification of pseudo-Boolean functions based on rank-invariance. This classifies functions which are monotone transformations of one another as equivalent, and so partitions an infinite set of functions into a finite set of classes. Reasoning about heuristics composed of ordinal operators is, by construction, invariant over these classes.
We perform a complete analysis of 2-bit and 3-bit psuedo-Boolean functions. We use Walsh analysis to define concepts of necessary, unnecessary, and conditionally necessary interactions, and of Walsh families. This helps to make precise some existing ideas in the literature such as spurious correlations.
Many algorithms are invariant under the classes we define, which allows us to examine the difficulty of psuedo-Boolean functions in terms of function classes. We analyse a choice of ordinal selection operators for an EDA. Using a concept of directed ordinal linkage, we define precedence networks and precedence profiles to represent key algorithmic steps and their interdependency in terms of problem structure. The precedence profiles provide a measure of problem difficulty. This correspond to problem difficulty and algorithmic steps to optimisation.
The work develops insight into the relationship between function structure and problem difficulty for optimisation, which may be used to direct the development of novel algorithms. Concepts of structure are also used to construct easy and hard problems for a hill-climber.
- John McCall
- David Lonie
- Christie, Lee A., McCall, John A. W., Lonie and David P. Minimal walsh structure and ordinal linkage of monotonicity-invariant function classes on bit strings. Proceedings of the 2014 conference on Genetic and evolutionary computation. pp. 333-340, 2014
- Brownlee, Alexander E. I., McCall, John A. W. and Christie, Lee A. Structural Coherence of Problem and Algorithm: An Analysis for EDAs on all 2-bit and 3-bit Problems. 2015
- McCall, John A. W., Christie, Lee A. and Brownlee, Alexander E. I. Generating Easy and Hard Problems using the Proximate Optimality Principle. Proceedings of the Companion Publication of the 2015 on Genetic and Evolutionary Computation Conference. pp. 767-768. 2015
- Christie, Lee A., Lonie, David P. and McCall, John, A. W.Partial structure learning by subset walsh transform. 13th UK Workshop on Computational Intelligence (UKCI), 2013. pp. 128-135. 2013