Conference publications (Computing)
http://hdl.handle.net/10059/62
2016-04-30T09:02:31ZGenerating easy and hard problems using the Proximate Optimality Principle.
http://hdl.handle.net/10059/1406
Generating easy and hard problems using the Proximate Optimality Principle.
McCall, John; Christie, Lee A.; Brownlee, Alexander Edward Ian
We present an approach to generating problems of variable difficulty based on the well-known Proximate Optimality Principle (POP), often paraphrased as "similar solutions have similar fitness". We explore definitions of this concept in terms of metrics in objective space and in representation space and define POP in terms of coherence of these metrics. We hypothesise that algorithms will perform well when the neighbourhoods they explore in representation space are coherent with the natural metric induced by fitness on objective space. We develop an explicit method of problem generation which creates bit string problems where the natural fitness metric is coherent or anti-coherent with Hamming neighbourhoods. We conduct experiments to show that coherent problems are easy whereas anti-coherent problems are hard for local hill climbers using the Hamming neighbourhoods.
2015-01-01T00:00:00ZPartial structure learning by subset Walsh transform.
http://hdl.handle.net/10059/1387
Partial structure learning by subset Walsh transform.
Christie, Lee A.; Lonie, David P.; McCall, John
Estimation of distribution algorithms (EDAs) use structure learning to build a statistical model of good solutions
discovered so far, in an effort to discover better solutions. The non-zero coefficients of the Walsh transform produce a
hypergraph representation of structure of a binary fitness function; however, computation of all Walsh coefficients requires
exhaustive evaluation of the search space. In this paper, we propose a stochastic method of determining Walsh coefficients for hyperedges contained within the selected subset of the variables (complete local structure). This method also detects parts of hyperedges which cut the boundary of the selected variable set (partial structure), which may be used to incrementally build an approximation of the problem hypergraph.
2013-01-01T00:00:00ZMinimal walsh structure and ordinal linkage of monotonicity-invariant function classes on bit strings.
http://hdl.handle.net/10059/1384
Minimal walsh structure and ordinal linkage of monotonicity-invariant function classes on bit strings.
Christie, Lee A.; McCall, John; Lonie, David P.
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.
2014-01-01T00:00:00ZStructural coherence of problem and algorithm: an analysis for EDAs on all 2-bit and 3-bit problems.
http://hdl.handle.net/10059/1362
Structural coherence of problem and algorithm: an analysis for EDAs on all 2-bit and 3-bit problems.
Browlnee, Alexander Edward Ian; McCall, John; Christie, Lee A.
Metaheuristics assume some kind of coherence
between decision and objective spaces. Estimation of Distribution
algorithms approach this by constructing an explicit probabilistic
model of high fitness solutions, the structure of which is intended
to reflect the structure of the problem. In this context,
“structure” means the dependencies or interactions between
problem variables in a probabilistic graphical model. There are
many approaches to discovering these dependencies, and existing
work has already shown that often these approaches discover
“unnecessary” elements of structure - that is, elements which
are not needed to correctly rank solutions. This work performs
an exhaustive analysis of all 2 and 3 bit problems, grouped into
classes based on mononotic invariance. It is shown in [1] that each
class has a minimal Walsh structure that can be used to solve
the problem. We compare the structure discovered by different
structure learning approaches to the minimal Walsh structure for
each class, with summaries of which interactions are (in)correctly
identified. Our analysis reveals a large number of symmetries that
may be used to simplify problem solving. We show that negative
selection can result in improved coherence between discovered
and necessary structure, and conclude with some directions for
a general programme of study building on this work. CONFERENCE HELD IN SENDAI, JAPAN, 25-28 MAY 2015.
2015-05-01T00:00:00Z