Jornal de Ciência da Computação e Biologia de Sistemas

Swarm Based Population Seeding of Grammatical Evolution

Abstract

Chris Headleand and William J Teahan

Evolutionary Algorithms, although powerful, are known to be wasteful and time consuming, requiring the evaluation of a large number of candidates. However the strength of the methodology is their ability to continually optimise the population hopefully ensuring a near optimal final solution. When applied to automatic programming tasks, the same limitations are observed, notably the time taken to develop a solution. An alternate, swarm-based method ‘Grammatical Herding’ suffers from the opposite concerns. Whilst it generates moderate fitness solutions quickly, these candidates often lack the optimisation of solutions generated via an evolutionary approach. This study details a hybrid technique ‘Seeded Grammatical Evolution’ where Grammatical Herding (GH) is used to seed the initial population of a Grammatical Evolution (GE) algorithm, with the result that the final solution is produced faster than one produced by GE alone and more effective (fitter) than one produced by GH. In this paper, we explore the background to the study including the initial work that inspired the approach. We also discuss the design of the algorithm and finally the results. We conclude that the hybrid approach is not only capable of producing a fast solution but also achieves state of the art results on a standard benchmark problem, the Santa Fe Trail.