Home Research About me CV Publications Contact Me Links

Back-tracking mutations A mutation-based strategy is described here which is used in preference to genetic algorithms. The strategy is suitable for online evolution, whereby a single agent uses a controller generated from the current best genotype that it has yet mutated for use within its environment. Generally this strategy is used to optimise the parameter sets of neural networks when multiple evaluations are required to determine an average fitness level. As with a genetic algorithm, a fitness function and mutation genetic operator is used, but there is no sexual reproduction or cross-over. A queue is used to store genotypes that encode neural networks. and is ordered according to average fitness. A neural network is generated from the fittest genotype and used to control the behaviour of an agent for a period of time. The average fitness of the genotype that the network was generated from is then updated accordingly. If the average fitness decreases to below that of another solution then the queue is re-ordered. This backtracking is required to prevent a genotype that would normally lead to a high average fitness being replaced by another genotype, that by chance, happens to be mapped to a fitter phenotype. When it is discovered that the search has moved downhill, backtracking allows the search to revert back to a previous position. If the genotype of the current neural network still has the highest average fitness then the agent copies and mutates a new version of it. The new version is then tested. It deletes the least fit network in order to save memory. A genetic algorithm can be seen as a process of convergence to a single, hopefully optimal solution, whereby the run is finished and the best solution is picked. A temperature rating is used here much to the same purpose. It determines how great a percentage of the new solution is mutated. The search starts off with a temperature rating of 100% so that each new solution is completely random. Unlike the temperature rating for simulated annealing, the temperature rating for this mutation-based strategy can revert back to a previous level. Each new solution uses the temperature rating of the previous solution that it is copied and mutated from, but decreases it by a random amount. This allows the search to backtrack to higher temperature ratings when the queue needs re-ordering. At the end of the search, the queue is iterated over so that each solution has been evaluated the same number of times. The fittest solution can then be picked by the designer. It is easy to record how often an entire genotype has been evaluated and its average fitness. This is of particular importance for stochastic genotype-phenotype mappings. The temperature rating indicates the progress of the evolutionary run. It is known exactly which genotype in the final population has the highest average fitness. Memory requirements are reduced. Only the current best genotype, and at times a mutated version of it, need to be present in the physical RAM of a computer. It is more practical to swap the rest of the queue to non-transient memory. A parallel-processing version of this algorithm is currently being developed. A server farms out new and existing genotypes to clients for evaluation. Results are returned asynchronously and the queue is re-ordered as necessary.