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

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

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.

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: https://doi.org/10.1145/2576768.2598240

• 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
• DOI: https://doi.org/10.1145/2576768.2598240
• 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: http://hdl.handle.net/10059/1384
• Related Public URLs: http://hdl.handle.net/10059/1406 ; http://hdl.handle.net/10059/1407 ; http://hdl.handle.net/10059/1567 ; http://hdl.handle.net/10059/1585