EEBIC group

2001 Meetings

AINC Seminars

2001

The performance of several mutation-based evolutionary algorithms and the local search heuristic is going to be considered from the point of view of discrete optimisation. In particular this presentation will discuss the upper and lower bounds on probability to generate the solutions of certain quality in the (1+1)-ES, the (1,lambda)-ES evolutionary strategies and in a simplified version of genetic algorithm with tournament selection. Some recent results on comparison of the (1+1)-ES to other evolutionary algorithms and to the local search will be discussed. The ways of statistical estimation of the landscape properties will be considered in conclusion.

Many problems in planning and reinforcement learning involve states and actions described in terms of some set of features or state variables, rather than using an explicit enumeration of all possible states. In decision-theoretic planning, the structured policy iteration algorithm [Boutilier et al. 1995] has been used to construct optimal policies for these problems by exploiting any structure present in the representation to keep the policy compact. This allows problems to be solved more efficiently, and allows solutions to problems that can't be solved by other methods due to space constraints. In this talk, I will review the structured policy iteration algorithm and show how it can be applied locally to produce a structured version of the prioritised sweeping algorithm. In structured prioritized sweeping, we maintain a structured estimate of the value function and update the values of aggregate states when learning occurs. This increased the scope of local value function changes and allows more efficient learning because learned information is more quickly propogated between states.

Artificial Genomes are models of biological DNA and its template-matching properties. As has been previously shown, they can be used to study the dynamics of gene regulatory networks in a similar manner as Random Boolean Networks, but with the advantage a biologically plausible structural underpinning. Among other things, this opens the possibility of experiments on structural genome evolution. For instance, questions as to the importance of regulatory vs. coding sequences, crossover events, or genome length can be readily addressed.

The Walsh/Fourier Transform and the Walsh Basis are powerful tools that can be used with dynamical system models of the genetic algorithm. The Walsh transform represents a population in a basis that is closely related to the schema averages of the population. The representation of mixing (crossover and mutation) is essentially the same as the representation of crossover. This enables a model of the gene pool genetic algorithm that incorporates both mutation and crossover whereas previous models only included crossover.

When trying to optimise a real-valued function of a real variable, one approach is to discretise the search space, encode this set of points using a binary representation, and then apply a local search algorithm (e.g. steepest descent). There are many ways of encoding a set of points in binary. The conditions under which different encodings lead to identical behaviour of a local search algorithm are investigated and some implications drawn. Gray code representations have some nice properties in such applications - for example, a steepest descent algorithm using the reflective Gray code will optimise a unimodal function in a linear number of steps. Rotating a Gray code produces a different Gray code. This technique can be used to help a local search algorithm escape from a local optimum, by a change of representation. The probability that a random shift will allow such an escape can be estimated. Finally, the class of "long-path" problems are known to be unimodal in Hamming-space, but require an exponential amount of time to be optimised by local search. We ask what class of real functions they correspond to, under a reflective Gray encoding. The answer is that they are fractals with an exponential number of local optima.

Even before the completion of the first working draft of the human genome, it was known that most of our DNA was so-called 'junk', serving no apparent biological function. However, this junk, rather than being the random garbage that the name might suggest, actually contains a considerable amount of structure. One example of this structure can be found with the Alu repeat, a DNA sequence able to have copies of itself inserted back into its host genome, acting as a sort of molecular level parasite. Analyses of the distribution of Alus throughout the human genome have revealed a number of interesting and counter-intuitive results. The work to be presented here has involved using a genetic algorithm based simulation of transposable elements (of which the Alu is just one example) to model these patterns. Parameter sweeps and analysis of this simulation suggest revisions to the ways in which the evolutionary dynamics of Alus are conceptualised, and highlight inadequacies in the current theories that attempt to describe the particular observed genomic distribution of Alus. The development and use of the simulation also raises methodological questions as to the proper application of such modelling enterprises within biology.

An ant system algorithm designed for the solution of the Vehicle Routing Problem with Backhauls (VRPB) is put forward. The mixed VRPB where linehaul and backhaul customers can be visited in any order along routes is considered together with a `restricted' VRPB. The restricted VRPB allows the user to determine the mix of linehaul and backhaul customers on a route by using the percentage of linehaul load delivered along the route to restrict the position where the first backhaul may be served. Such a flexibility enhances the results of the classical VRPB, where the backhauls are included on a route only when all linehauls are served, while reducing the risk of implementing an impractical solution produced by the fully mixed VRPB. Some ideas with respect to the size of the candidate list, initial placement of ants and updating of the trail will be proposed to enhance the basic ant system. Results based on test problems will be presented.

Most real-world optimisation problems are better posed as multi-objective optimisation problems involving conflicting objectives, but due to the lack of suitable solution techniques they have been solved as single-objective optimisation problems. Optimising a product for minimum cost as well as for maximum reliability, for example, is often desired but is difficult to achieve with classical approaches. In reality, such conflicting objectives give rise to a set of optimal solutions, known as Pareto-optimal solutions. In tackling such problems, a less-subjective and useful technique is to first find a set of trade-off solutions and then to choose one from the set. In this talk, a number of state-of-the-art multi-objective evolutionary methods, capable of finding multiple trade-off solutions, will be presented. A few case studies from different areas of science and engineering will be shown. Finally, some salient research issues will be discussed.