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 search algorithms that use structural models at each iteration to determine the trajectory of the search. Examples include Information Geometry Optimisation (IGO), Covariance Matrix Adaptation Evolution Strategy (CMA-ES), Bayesian Evolutionary Learning (BEL) and Estimation of Distribution Algorithms (EDA).

In particular, EDAs use probabilistic graphical models to represent structure learned from evaluated solutions. Various EDA approaches using trees, directed acyclic graphs and undirected graphs have been developed and evaluated on a range of benchmarks with a variety of representations.

Benchmarks typically have “known structure” determined a priori from full knowledge of the relationship between fitness and variable interactions. In practice, the relationship between the problem structure, structures found by by the EDA and algorithm success is a complex one. The EDA literature discusses “necessary” and “unnecessary” interactions in order to explore this but the usage of the terms is not precise.

In this talk I will explore these ideas using a classification of problems based on monotonicity invariance. We completely classify of all functions on 3 bits and show that conventional concepts of the relationship between structure and problem difficulty are too brittle to capture the subtlety even of this low dimensional function space.

The talk concludes with a discussion of some closely related work on using geometric structure to generate problems of controllable difficulty and some ideas for a category theoretic approach to problem classification.

Biography

John McCall is a Professor of Computing Science at Robert Gordon University. He works in the Computational Intelligence research group, which he founded in 2003. He has over twenty years research experience in naturally-inspired computing.

His research focuses on the study and analysis of a range of naturally-inspired optimization algorithms (genetic algorithms, particle swarm optimisation, ant colony optimisation, estimation of distribution algorithms etc.) and their application to difficult learning and optimisation problems, particularly real-world problems arising in complex engineering and medical / biological systems. Application areas of this research include medical decision support, data modeling of drilling operations, analysis of biological sequences, staff rostering and scheduling, industrial process optimization and bio-control. He has over 90 publications in books, journals and conferences. He has successfully supervised 13 PhD students and has examined over 15 PhD theses.