Last Revision - January 11th 1998
MSc Project (Original Project Proposal).
Student: Michael Ratford. Co-supervisor: Dr Henry Thompson
In nature, sexually reproducing organisms do not mate indiscriminately --- the choice of mate has a large impact upon the fitness if the organism's offspring, and there is no reason why such a principle should not be respected in genetic algorithms. By balancing the trade-off between inbreeding and outbreeding, there is the potential for making crossover a more effective search operator. Furthermore, mate choice can lead to speciation effects which may enhance the genetic algorithm's ability to locate multiple distinct solutions.
The project showed that, for a wide range of problems in the literature, sexual selection proved to be a robust method both in enhancing genetic algorithm performance, and in locating multiple distinct solutions. In addition, evidence for deciding which parameters are important for a successful implementation of sexual selection in genetic algorithms was provided.
M. Ratford, A.L. Tuson, and H. Thompson (1997). Applying Sexual Selection as a Mechanism for Obtaining Multiple Distinct Solutions. Presented at Emerging Technologies '97.
M. Ratford, A.L. Tuson, and H. Thompson (1997). The Single Chromosome's Guide To Dating. Presented at the Third International Conference On Artificial Neural Networks And Genetic Algorithms.
Ratford, M. (1996). The Single Chromosome's Guide To Dating. Master's Thesis, Department of Artificial Intelligence, Edinburgh University, U.K.
MSc Project (Original Project Proposal).
Student: Peter Baron (pt). Co-supervisors: Dr Bob Fisher, Mr Frank Mill (Mechanical Engineering), and Mr Andrew Sherlock (Mechanical Engineering).
Previous work has applied genetic algorithms (GAs) to shape optimisation problems with encouraging results. Using engineering software packages to evaluate the suitability of a given design, successful shapes have been evolved. However, previous work on evolutionary shape optimisation has primarily used parametric representations of such problems.
This investigation evaluates a voxel (N-dimensional pixel) based representation which can describe any topology, but it also has its drawbacks: the long length of the chromosomes and the possible formation of small holes in the shape. This project amounts to an investigation into whether these drawbacks are sufficient to prevent this approach being useful, and of how domain knowledge can be added in a principled way.
The final results obtained in this project have been encouraging. For the optimisation of a beam cross-section, the use of a `standard' GA with two-point crossover and bit-flip mutation lead to disappointing results - the final shape was highly irregular and possessed small holes. Three domain specific operators were then designed to overcome perceived problems with schema linkage, irregular shapes and small holes. With these operators, the GA was able to produce shapes that were known to be optimal for this problem.
The system was then tested on an aircraft annulus problem from Rolls Royce previously attempted by a GA with a parametric representation. After some further refinements to the system to effectively integrate the voxel representation with the FEA analysis package used, the GA was able to come up with a novel annulus shape which on further analysis was found to be due to the GA exploiting weaknesses in the problem specification - which provides evidence of the optimisation power of this approach.
P. Baron, A.L. Tuson, A. Sherlock, F. Mill, and R. Fisher (1997). An Investigation of a Voxel-based Representation for Evolutionary Shape Optimisation. In preparation for submission to Artificial Intelligence for Engineering Design, Analysis and Manufacturing (AI-EDAM).
P. Baron (1997). Evolutionary Shape Optimisation Using a Voxel Based Representation. Master's Thesis, Department of Artificial Intelligence, Edinburgh University, U.K.
P. Baron, R. Fisher, F. Mill, A. Sherlock, and A. L. Tuson (1997). A Voxel-based Representation for the Evolutionary Shape Optimisation of a Simplified Beam: A Case-Study of a Problem-Centred Approach to Genetic Operator Design. Presented at the 2nd On-line World Conference on Soft Computing in Engineering Design and Manufacturing (WSC2).
P. Baron, R. Fisher, F. Mill, A. Sherlock, and A.L. Tuson (1997). A Voxel Based Approach To Evolutionary Shape Optimisation. Presented at the 1997 AISB Workshop on Evolutionary Computing.
AI4 Project (Original Project Proposal).
Student: Chi Kit Tsang. Co-supervisor: Dr Henry Thompson
RNA (Ribose Nucleic Acid) consists of a sequence of bases - the primary structure. Certain bases in the RNA sequence pair with each other, thus creating closed loops in the molecule. The problem is to predict how the molecule folds together - the secondary structure - given constraints on what bases can pair up. Earlier work [El-Said 91] formulated the problem as a constraint satisfaction problem (CSP), and used constraint logic programming (CLP) techniques to find possible structures.
Another promising approach to solving CSPs is the genetic algorithm (GA). This has proved successful at solving other CSPs such as timetabling. This project aims to assess the applicability of genetic algorithms for RNA secondary structure prediction.
The results obtained during this project indicated that care must be taken in the design of the representation and operators if an evolutionary approach is to be successful for this problem. Finally a hillcibing heuristic based on the representation and operators for used for the GA was able to solve the CSP significantly faster than the CLP code by [El-Said 91].
El-Said, A .M. (1991) A Constraint Satisfaction Approach to RNA Structure Prediction. Masters Thesis, Department of Artificial Intelligence, Edinburgh University, U.K.
C.K. Tsang (1997). A Genetic Algorithm for RNA Secondary Structure Prediction, AI4 Project Report, Department of Artificial Intelligence, Edinburgh University, U.K.
AI4 Project (Original Project Proposal).
Student: Shigeaki Nakata. Co-supervisor: Dr Chris Mellish.
The Travelling Salesman Problem (TSP) is a classic example of a Combinatorial Optimisation Problem (COP) which has been the subject of active research over many years. Good exact methods do exist, but for large numbers of cities (>2000) the cost is prohibitive. Instead, attention has turned to techniques that, although not guaranteeing an optimal solution, can find good solutions to large instances of COPs in a reasonable time [Reeves 94].
The role that representation plays in the effective use of neighbourhood search (NS) techniques have been identified as being of importance [Tuson 96]. The TSP/NS literature has devised a range of representations, but little comparison has been performed. Also, if the arguments advanced in [Tuson 96] are correct then the choice of representation is more important that the choice of NS optimiser, the TSP domain could be used to see if this is in fact the case.
The results obtained indicated that the representation plays a more important and predicable role in the quality of optimisation than the choice of optimiser, and that the choice of representation is transferrable across optimisers.
C. R., Reeves (1994). Modern Heuristic Approaches To Combinatorial Optimisation. Blackwells (Oxford).
A. L., Tuson (1996). PhD Proposal: A Neighbourhood Search Approach To Scheduling. Discussion Paper, Department of Artificial Intelligence, Edinburgh University, U.K.
S. Nakata (1997). A Study of Modern Combinatorial Approaches To The Travelling Salesman Problem, AI4 Project Report, Department of Artificial Intelligence, Edinburgh University,
MSc Project (Original Project Proposal).
Student: Nicholas Altmann. Co-supervisors: Drs Joel Malard (PNL, USA) and Alan Smaill
One of the major bottlenecks in modern computers is the interface between the CPU and the (much slower) main memory. The usual solution to this is to use a cache - a small amount of very fast memory on the CPU that stores items in the main memory that are used often. It is found that the structure of the code has a large impact on how effective the cache is.
One method of improving cache usage (and hence the speed of the code), is to add padding to the arrays in the program, which aligns the arrays in main memory so that the cache is more effectively used. The project was to evola
Further integration of the Civet library and RPL2 (a GA-orientated) programming language to implement a GA to optimise the array padding. This was found to have obtained some encouraging results, with a quite dramatic increase in cache hit rate (which translates to final code speed) over the same unpadded code, especially when a specially designed directed mutation operator was used. However, more work seems to be required before it can be said when, or if, it should be used over other approaches such as array merging or index interchange.
J.M. Malard (1996). Evolutionary Computing and Performance Optimisation, Slides for CSG Talk.
J.M. Malard (1996). A Genetic Algorithm for Optimising Cache-Usage on the Cray T3D, presented at the SIAM Annual Meeting, July, Kansas City.
C.R. Reeves (1994). Modern Heuristic Approaches To Combinatorial Optimisation. Blackwells (Oxford).
N. Altmann, J.M. Malard, A.L. Tuson, and A. Smaill (1997). An Evolutionary Approach for Improving the Cache Usage of FORTRAN Codes. In preparation for submission to the Fifth International Conference on Parallel Problem Solving From Nature (PPSN V).
N. Altmann (1997). An Investigation into Neighbourhood Search for Improving Cache Use. Master's Thesis, Department of Artificial Intelligence, Edinburgh University, U.K.
MSc Project (Original Project Proposal).
Student: Sergio Ramos Co-supervisors: Dr Julian Miller (CS, Napier Univ), Mr Peter Thompson (CS, Napier Univ), Mr Chris Malcolm
The application of modern neighbourhood search optimisation techniques (including genetic algorithms) to combinatorial problems in electrical engineering is an area of recent activity. An example is the problem of minimising Boolean functions as an exclusive-OR sum-of-products (Reed-Muller). This has an important application in finding good, compact gate designs for FPGAs (Field Programmable Gate Arrays - programmable logic chips).
Julian Miller and Peter Thomson [Thompson and Miller 96] from Napier University have recently devised an optimisation-based approach to this problem that uses a genetic algorithm to determine a good variable ordering for a TDD (ternary decision diagram) representation of a Boolean function in Reed-Muller logic to obtain a multi-level circuit. The results obtained were encouraging: the approach was capable of minimising benchmark Boolean functions with large numbers of inputs and outputs, and gave very good results when compared with previous approaches.
However, the work previously had concentrated on evaluating the general approach, as opposed to improving the optimisation process in a principled way. The main aim of this project will be to take the optimisation approach to FPGA logic minimisation, and apply neighbourhood-search optimisation techniques to the problem in a more principled manner. This work examined a number of issues such as the alternative representation for the variable ordering, and a comparative study of the various neighbourhood search techniques.
The investigation found that hillclimbing and other neighbourhood search techniques were able to generally outperform the orginal GA-based system, especially when a more `natural' representation of the variable ordering was used. It was also found that the choice of neighbourhood operator for a given problem was transferrable across the different optimisers.
S. Nakata (1997). A Study of Modern Combinatorial Approaches To The Travelling Salesman Problem, AI4 Project Report, Department of Artificial Intelligence, Edinburgh University, UK.
C.R. Reeves (1994). Modern Heuristic Approaches To Combinatorial Optimisation. Blackwells (Oxford).
P. Thomson and J.F. Miller (1996) Symbolic method for simplifying AND-EXOR representations of Boolean functions using a binary-decision technique and a genetic algorithm, IEE Proceedings on Computers and Digital Techniques. Vol. 143, No. 2, pp151-155.
A.L. Tuson (1996). PhD Proposal: A Neighbourhood Search Approach To Scheduling. Discussion Paper, Department of Artificial Intelligence, Edinburgh University, UK.
S. Ramos, A.L. Tuson, J.F. Miller, P. Thomson and C. Malcolm (1997). A Comparitive Study of Software Optimisation Methods for Logic Circuit Design. In preparation for submission to the International Journal of Electronics.
S. Ramos (1997). A Neighbourhood Search Approach to FPGA Design. Master's Thesis, Department of Artificial Intelligence, Edinburgh University, U.K.
MSc Project (Original Project Proposal).
Student: Somnuk Phon-Amnuaisuk Co-supervisors: Dr Geraint Wiggins.
This project explored the possibilities of using genetic algorithms to generate music. The goal was to produce a working system for the harmonisation of tunes in a four-part tonal style, like, for example, hymn tunes. Initially, development focussed on the production of a fitness function based on standard rules for tonal harmony, gleaned from a music textbook. Once the fitness function was developed and verifed, it formed the basis of a testbed for experimentation with different forms of representaton of the musical score.
The project showed that, with a suitable choice of representation and operators, it was possible for a GA to produce a short piece of music that conformed to the basic rules of four-voice harmony. The student has now transferred to the PhD course.
H. Lovelock. "First Year harmony".
G. Wiggins, E. Miranda, A. Smaill, and M. Harris (1993). A Framework for the Evaluation of Music Representation Systems., Computer Music Journal, Vol 17, Number 3.
G. Papadopoulos, S. Phon-Amnuaisuk, G. Wiggins, and A.L. Tuson (1997). Evolutionary Methods for Music Composition. Submitted to the International Conference on Computer Music (ICMC 98).
MSc Project (Original Project Proposal).
Student: George Papadopoulos Co-supervisors: Dr Geraint Wiggins.
This project aimed to produce a working improvisation system, where the user would input a chord sequence, and an instrumental solo to top it will be evolved using GA techniques. As in the four-voice harmony project, much effort was expended in the design of a fitness function based on the musical rules of Jazz - a departure from the purely interactive `human-as-fitness-function' approach taken recently. The final system managed to produce simple, short pieces of Jazz. The student has now transferred to the PhD course.
G. Wiggins, E. Miranda, A. Smaill, and M. Harris (1993). A Framework for the Evaluation of Music Representation Systems., Computer Music Journal, Vol 17, Number 3.
G. Papadopoulos, S. Phon-Amnuaisuk, G. Wiggins, and A.L. Tuson (1997). Evolutionary Methods for Music Composition. Submitted to the International Conference on Computer Music (ICMC 98).
I am, as always, open to suggestions for self-proposed or future MSc projects. If you are interested, please email me.