On Searching A-ary Hypercubes and Related Graphs
Joseph Culberson and Jonathan Lichtner
Abstract
This paper develops two themes on landscapes
in search algorithms. First it focuses on
the notion of landscapes as being induced by operators
and fitness functions together with a frequently overlooked
influence, the way in which the operator is used within the algorithm.
This latter influence is sometimes confused by the tendency
to consider a landscape
as representative of a search even when a different operator is introduced
into the search. We make a finer distinction and show that even when the
graph is strictly adhered to by the operators,
functions can be found that exponentially
differentiate between algorithms that use the neighbor generation in elitist,
non-elitist, full neighbor search and neighborhood sampling techniques.
These results can be seen as a form of ``no free lunch'' in that
in order to fully analyze an algorithm, no detail can be excluded from the
analysis.
The second theme tries to abstract out salient properties of landscapes
that are dependent on properties of graphs such as degree, diameter and
independent set structure. These properties limit the effects of adversaries
in various ways. For this to
make sense, we must give up the notion of universal problem
solvers, and consider more restricted adversaries that better reflect our
expectations of search on specific problem classes.
This analysis is mostly restricted to graphs induced by simple operations on
sets of strings over fixed alphabets.
Full paper
joe@cs.ualberta.ca