Show simple item record

dc.contributor.authorChristie, Lee A.
dc.contributor.authorMcCall, John
dc.contributor.authorLonie, David P.
dc.date.accessioned2016-02-16T15:36:46Z
dc.date.available2016-02-16T15:36:46Z
dc.date.issued2014
dc.identifier.citationCHRISTIE, 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: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO '14). 12-16 July 2014. New York: ACM. pp. 333-340.en
dc.identifier.isbn978-1-4503-2662-9en
dc.identifier.urihttp://hdl.handle.net/10059/1384
dc.description.abstractProblem 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.en
dc.language.isoenen
dc.publisherACMen
dc.relation.ispartofProceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO '14). 12-16 July 2014. New York: ACM.en
dc.relation.urihttp://hdl.handle.net/10059/1585
dc.rights© ACM, 2014. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO '14). 12-16 July 2014. New York: ACM. pp. 333-340. http://doi.acm.org/10.1145/ 2576768.2598240en
dc.subjectAlgorithmsen
dc.subjectDesignen
dc.subjectPerformanceen
dc.subjectTheoryen
dc.subjectEstimation of distribution algorithmsen
dc.subjectLinkage learningen
dc.subjectMonotonicityen
dc.subjectOrdinal selectionen
dc.subjectPerturbation methodsen
dc.subjectArtificial intelligenceen
dc.subjectProblem solvingen
dc.subjectControl methodsen
dc.subjectSearchen
dc.titleMinimal walsh structure and ordinal linkage of monotonicity-invariant function classes on bit strings.en
dc.typeConference publicationsen
dc.relation.referencesCHRISTIE, L.A. 2016. Walsh families of all rank-invariant classes of 3-bit pseudo-Boolean functions. [Dataset]. Held on OpenAIR [online]. Available from: http://hdl.handle.net/10059/1585
dc.publisher.urihttp://dx.doi.org/10.1145/2576768.2598240en


Files in this item

This item appears in the following Collection(s)

Show simple item record