Dissertation: On Evolutionary Algorithms for Evolving Code in a Closed Context
Evolutionary algorithms are used in many situations where complex, abstract and or hard to achieve solutions have to be found. Some applications are: cancer diagnosis; artificial creativity; and spacecraft antennae design. Genetic algorithms are a subset of evolutionary algorithms that use Darwinian Evolution Theory principles such as splicing; mutation; and cross-over functions, to evolve genomic sequences that represent solutions to a given problem.
Core War is a programming game, in which two or more programs are executed in a sandboxed memory battle, where the aim of each program is to terminating the other’s process.
An application was built to evolve Core War programs using genetic algorithms for the purpose of searching for improvements on the original programs. By making use of an Elo Rating system, the fitness of each generated program is evaluated, one generation after the other. To calculate a program’s rating, the program is battled against other programs to measure their wins, ties and losses versus. The updated Elo Rating is then used to determine which programs are discarded or saved and carried over to future generations where they can continue to evolve. The Elo Rating is reset after every generation, to prevent programs carried over from previous generations from having high Elo Ratings that dominate the new generation and do not give new programs the opportunity to be carried over. The particular genetic algorithm approach taken is based on simulated annealing, but also makes use of elitism and the taboo search metaheuristic, all of which are designed to improve searching, speed, and the quality of the evolved Core War programs.
Results have shown, that generated programs are able to be evolved properly and can be more effective than some standard programs when tested in the actual nMars IDE. Improved results can be obtained by improving the speed of execution of the algorithm through practices such as parallelism; different parsing techniques; and adjust the genetic algorithm searching process.