Analysing the Genotype-Phenotype Map in Grammatical Evolution
David S. Fagan · 2013
The Genotype-Phenotype Map (GPM) is an important aspect of the representation in Evolutionary Computing (EC). The GPM decouples the search space of the EC algorithm into a many-to-one mapping, allowing an abstraction of the search and solution spaces, which can bring a number of benefits to search. Grammatical Evolution (GE) is a grammar based form of Genetic Programming (GP) that incorporates a GPM at its core, which is loosely inspired by nature. This thesis investigates whether di↵erent approaches to the GPM can have a positive e↵ect on GE’s performance. By examining a range of GPMs that use di↵ering expansion order principles it was found the one approach, Position Independent Grammatical Evolution (⇡GE) presented a viable alternative to the canonical GE GPM. ⇡GE, while showing good performance, uses a variable expansion order controlled by evolution. This variable ordering increases the size of the search space that must be navigated by ⇡GE during evolution. It is found that ⇡GE gains a significant increase in connectivity by using an evolvable order, while also providing ⇡GE with additional neutrality. Knowing what orders ⇡GE uses during evolution may provide insight into new GPM approaches. With this in mind a set of measures are devised, that allow for the monitoring of ⇡GE’s population during an evolutionary run. What is found is that ⇡GE doesn’t converge to a single order but rather a distribution of GPM orders. The addition of the evolvable order in ⇡GE provides an added degree of freedom in the mapping that is not exploited by standard genetic operations. A mutation operation is presented that will allow the algorithm to focus mutation on certain aspects of the ⇡GE chromosome. It is found that with this ability the performance of ⇡GE is increased. For Mam and Dad In Memory Vincent Fagan 1954 2013 Acknowledgements Firstly I would like to thank my supervisors, Prof. Michael O’Neil and Dr. Sean McGarraghy. Michael saw something in me, and decided I was worth investing time and money in. I am forever indebted to you for all the support, encouragement, and supervision you have given me. I couldn’t have asked for a better supervisor, you knew when to push me and when to just let me figure things out by myself. Sean you were always there to bounce ideas o↵, and get hands on as I tried to muddle my way through certain mathematical challenges. I must also thank Prof. Anthony Brabazon, while not my supervisor you always showed interest in my work, providing invaluable advice and encouragement. I want to thank all the members, past and present, of the Natural Computing Research and Applications group for the support, guidance, and welcoming environment they provided. Dr. James McDermott, Dr. Miguel Nicolau, Dr. Erik Hemberg, and Dr. Alexandros Agapitos, as post-docs you all provided me with a sounding board for my ideas and I am grateful for the feedback and friendship that has come of it. Special thanks must also be given to Dr. Jonathan Byrne and Dr. John Mark Swa↵ord. We were in the trenches together doing our PhDs. You welcomed me into the group with open arms and I am very grateful for the friends you have become. I honestly don’t think I would have enjoyed my time in research as much if it was not for Dr. Eoin Murphy. We have been through a lot together, BSc and PhD, and remained good friends throughout. I could not be happier knowing that we will graduate together. I do not like for my work life to interfere with my private life, mainly so I don’t have to explain to friends what I do, but also so that I can escape and unwind when not in work. So I wish to thanks all my friends (you know who you are) for doing nothing. I know your help and support was always o↵ered but I like to not burden you guys with having to fain interest in my research. The time we spent just sitting around having a laugh was exactly what I needed. My family plays an important part in my life. Kevin, Laura, Fiona, Rachel, Sarah, Keith, and Emma; thank you, I could not have done this without your love and support. I would not change a thing about the cloud of madness we exist in as a family. Most importantly I must thank my parents. Everything I do and achieve in life is to try an make you guys proud. The love and support you have shown me throughout my life has made me into the man I am today. Without your presence I am certain I would not be here today with this PhD thesis. Mam you pestered me about not wasting my intelligence after my first unsuccessful attempt at this college lark. My returning to education to do my undergraduate degree was a direct result of this. Without that I would never have achieved what has followed that decision. I can’t express in words how much I love you Mam, and how grateful I am to have you as a mother. Tragically my father passed away the week after my viva. Dad I love you and miss you immensely. I know it brought you so much happiness the day I passed my viva. Dad, I am forever grateful for everything you did for me. You provided me with whatever you possibly could, and tried to nurture any interest I had. I am deeply saddened that you won’t be around for my graduation, but I know you will be there with me in spirit. Finally, I would like to thank Science Foundation Ireland (SFI). This research is based upon works supported by the SFI under Grant No. 08/IN.1/I1868. Table of