Guang studied the structure of search spaces induced by various local seach algorithms for satisfiability. He a combination of theoretical and empirical approaches, and considered the frequency and likely hood of various methods reaching traps. He successfully defended in June 2004.
Wenbin looked at a number of graph drawing algorithms, and heuristics for layouts. As part of his investigation he also considered various clustering techniques.
His work was initially motivated by a desire to animate the rapid graph collapse phenomenon associated with the 3-coloring phase transition [Culberson and Gent] ). His final program allows presentation of this complex phenomenon under a variety of drawing methods.
Wenbin completed in March, 2001. An online copy of his thesis can be found here.
Phase transitions in NP-complete prblems have been associated with the frequent occurence of instances that are very hard to solve in practice. However, this association is not universal, as for example Hamiltonian Cycle does not produce hard instances with high probability at the phase transition.
In this thesis Yong explores theoretically and empirically the threshold behavior of NK-landscapes. These were developed by Kauffman and explored in the Genetic Algorithms and Evolutionary Computation community as models to explain certain aspects of genetic evolution and the behavior of various algorithms. They are closely related to SAT instances and as such give us a different natural distribution than random SAT.
It turns out however that the phase transition in the most natural parameterized distributions do not yield hard instances. Yong's work shows theoretically and empirically that the probability of hard instances tends to zero at the satisfiability threshold.
Yong successfully defended in December, 2000. An online copy of his thesis can be found here.
The satisfiability threshold of NP-complete problems is often associated with the sudden appearance of a backbone or frozen set; this is a set of values that are fixed under all solutions of the instance. It is believed that this backbone is associated with the frequent occurence of hard instances near the phase transition.
Adam's thesis explores the theoretical complexity (in the sense of NP-completeness) of backbone-free (unfrozen) instances. This is generalized into parameterized classes of unfrozeness. For some problems as we increase the unfrozeness they move from NP-c to P, while others do not.
In addition he also explores the difficulty of determining maximal satisfiable instances. In most cases these are in P, but not always.
Adam also worked as a summer NSERC student in 1995 (see below). Apparently this experience helped develop his taste for research.
Adam successfully finished in July 2000. An online copy of his thesis can be found here.
A problem in forestry is the allocation of crews to cut-blocks in order to ensure a supply of wood product and minimize costs. The problem is made difficult by variations in crew types, wood types, terrain types, seasonal considerations, weather, environmental considerations, and other effects. Obtaining optimal solutions involves solving several interlocking NP-complete problems. One central problem is a variation of the P-center problem. Current research focuses on this problem, considering approximation algorithms, heuristic searches and identification of difficult classes.
Bob completed his thesis and MSc in 1998.
Basil looked at the difficulty of determining Hamilton cycles in sparse
graphs. Both backtrack with various forward pruning techniques and randomized
algorithms were considered. One goal was to identify properties that make
the problem hard over a wide range of algorithms, at the same time identifying
classes of graphs that distinguish various types of algorithms.
Basil successfully defended his thesis in February 1998. An abstract and postscript version of the thesis can be found here.
The search space induced by an algorithm can be represented by a graph
with vertices representing state and edges representing possible shifts in
state. In GAs using finite strings over finite discrete alphabets, these
graphs can be simplified so that nodes represent strings, or populations
of strings, and edges join strings that can be created one from the other
through some genetic operation.
The structure of the graphs will depend on the types of operations and on the size of the alphabet. This research identifies isomorphisms between mutation and crossover on arbitrary alphabets, higher order crossover operators that follow naturally, and other extensions of the usual notion of crossover in ordinary GAs. It is also shown that any traditional GA using crossover and mutation can be precisely mimiced by an algorithm using two levels of "higher order" crossover. When this is applied to 4 character alphabets, we get a system of two complementary pairs of strings; that is, in each string 'a' is always paired with 'b' and 'c' is always paired with 'd'.
Key characteristics of the "searchscapes" induced by various sizes of alphabets and various ways of "simplifying" the isomorphic structures are being analyzed. Preliminary results show in some respects superior properties under certain benign assumptions.
Jonathan successfully defended his thesis in April, 1997 and is now at Nortel. He may be reached by email jlich@nortel.ca . The thesis may be found at ftp://ftp.cs.ualberta.ca/pub/TechReports/1997/TR97-04 in compressed postscript.
It is observed in various studies that Genetic Algorithms when implemented in parallel give super-linear speed up in solution time. However, elementary theoretical considerations indicate that any parallel algorithm can be simulated by a sequential algorithm with at worst a linear time ratio. Thus, the switch from a single population to multiple populations must yield additional benefits on these problems. This opens questions on the role of recombination and transfer of information between individuals and populations. Initial research is on the correlations one can expect between simple real-valued operators working at the phenotypical level on landscapes with simple features such as ranges of peaks.
A graphics tool was developed to graphically display the action of multiple
population GAs on real valued terrains in order to aid in this research.
An abstract and the thesis can be found locally
here (uncompressed postscript)
or a Greg's current home at Brandeis
here (compressed postscript).
Greg completed his residency in august, 1996 and is now starting his Phd as part of the Dynamical & Evolutionary Machine Organization supervised by Jordan Pollack and Maja Mataric at Brandeis University.
Michael Lewchuk explored a special case of the Gene Invariant Genetic Algorithm (GIGA) in which selection is also restricted so that no bias towards better individuals is ever used. The only way in which improvement can be achieved is via something akin to diffusion. Selection is now restricted to choosing the pair in the population which are closest to each other in value. This thesis (1992) and an abstract can be found here.
