Logo of Science Foundation Ireland  Logo of the Higher Education Authority, Ireland7 CapacitiesGPGPU Research Projects
Ireland's High-Performance Computing Centre | ICHEC
Home | News | Infrastructure | Outreach | Services | Research | Support | Education & Training | Consultancy | About Us | Login

Publication

Title:Explorations on template-directed genetic repair using ancient ancestors and other templates
Authors:Donagh Hatton, Diarmuid P. O'Donoghue, 2011
Abstract: Handling constraints for combinatorial optimization problems is a classic challenge faced by genetic and evolutionary algorithms. This paper explores a naturally inspired genetic repair process to enforce constraints on evolutionary search. Lolle et al. (2005) controversially claim that the model plant Arabidopsis thaliana appears to repair genetic errors using information inherited from ancestors other than the immediate parents [10] (i.e. non-Mendelian inheritance). We adapt this natural template-driven genetic repair process (GeneRepair) to help solve constraint problems. Building upon previous results [6][7][8] this paper explores repair templates that originate across a range of ancestors, between one and many thousands of generations old. The fitness of resulting populations are presented and compared to a benchmark technique using a random repair template [9]. The results show that very ancient (ancestral) repair templates perform best for larger problems, significantly outperforming the benchmark. The impact of background mutation rates on solution quality is also explored. Results suggest that ancestral repair is a good general-purpose constraint handling technique - helping to explain why this strategy might have evolved in nature.
ICHEC Project:Genetic Repair in Genetic Algorithms
Publication:Proceedings of the 13th annual conference companion on Genetic and evolutionary computation (GECCO '11), pp. 325-332, 2011
URL: http://dx.doi.org/10.1145/2001858.2002014
Keywords: constraint search, evolutionary optimization, genetic algorithms, genetic repair
Status: Submitted

return to publications list