Implementing an Intuitive Mutation Operator for Interactive Evolutionary 3D Design
Jonathan Byrne, James McDermott, Galvan-Lopez E., Michael O'Neill; (2010) Implementing an Intuitive Mutation Operator for Interactive Evolutionary 3D Design. IEEE World Congress on Computational Intelligence, Proceedings of the Congress on Evolutionary Computation
Locality - how well neighbouring genotypes corre- spond to neighbouring phenotypes - has been described as a key element in Evolutionary Computation. Grammatical Evolution (GE) is a generative system as it uses grammar rules to derive a program from an integer encoded genome. The genome, upon which the evolutionary process is carried out, goes through several transformations before it produces an output. The aim of this paper is to investigate the impact of locality during the generative process using both qualitative and quantitative techniques. To explore this, we examine the effects of standard GE mutation using distance metrics and conduct a survey of the output designs. There are two different kinds of event that occur during standard GE Mutation. We investigate how each event type affects the locality on different phenotypic stages when applied to the problem of interactive design generation.
W. Banzhaf. Genotype-phenotype-mapping and neutral variation - A case study in genetic programming. In Y. Davidor, H.-P. Schwefel, and R. Männer, editors, Parallel Problem Solving from Nature III, volume 866 of LNCS, pages 322-332, Jerusalem, 9-14 Oct. 1994. Springer- Verlag.
J. Byrne, J. McDermott, M. O'Neill, and A. Brabazon. An analysis of the behaviour of mutation in grammatical evolution. In Genetic Programming, Proceedings of EuroGP'2010. Springer-Verlag, 2010.
J. Byrne, M. O'Neill, and A. Brabazon. Structural and nodal mutation in grammatical evolution. In Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 1881-1882. ACM, 2009. http://dx.doi.org/10.1145/1569901.1570215
R. Cilibrasi and P. M. B. Vitanyi. Clustering by compression. IEEE Transactions on Information theory, 51(4):1523-1545, 2005. http://dx.doi.org/10.1109/TIT.2005.844059
F. J. Gomez. Sustaining diversity using behavioral information distance. In Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 113-120, Montréal, Canada, 2009. ACM. http://dx.doi.org/10.1145/1569901.1569918
D. A. Hart. Toward greater artistic control for interactive evolution of images and animation. In M. Giacobini, editor, Applications of Evolutionary Computing, volume 4448 of LNCS, pages 527-536. Springer, 2007. http://dx.doi.org/10.1145/1179849.1179852
J. Hugosson, E. Hemberg, A. Brabazon, and M. ONeill. Genotype representations in grammatical evolution., 2007.
C. Igel. Causality of hierarchical variable length representations. In Proceedings of the 1998 IEEE World Congress on Computational Intelligence, pages 324-329, Anchorage, Alaska, USA, 5-9 May 1998. IEEE Press. http://dx.doi.org/10.1109/ICEC.1998.699753
R. E. Keller and W. Banzhaf. Genetic programming using genotypephenotype mapping from linear genomes into linear phenotypes. In J. R. Koza, D. E. Goldberg, D. B. Fogel, and R. L. Riolo, editors, Genetic Programming 1996: Proceedings of the First Annual Conference, pages 116-122, Stanford University, CA, USA, 28-31 July 1996. MIT Press.
M. Li and P. Vitanyi. An introduction to Kolmogorov complexity and its applications. Springer Verlag, 1997.
M. O'Neill, E. Hemberg, E. Bartley, A. Brabazon, and C. Gilligan. Geva - grammatical evolution in java. ncra.ucd.ie/GEVA, 2008.
M. O'Neill, E. Hemberg, C. Gilligan, E. Bartley, J. McDermott, and A. Brabazon. GEVA: grammatical evolution in Java. ACM SIGEVOlution, 3(2):17-22, 2008.
M. O'Neill, J. McDermott, J. M. Swafford, and J. Byrne. Evolutionary design using grammatical evolution and shape grammars: Designing a shelter. In International Journal of Design Engineering., volume In Press. 2010.
M. O'Neill and C. Ryan. Crossover in grammatical evolution: A smooth operator? In R. Poli, W. Banzhaf, W. B. Langdon, J. F. Miller, P. Nordin, and T. C. Fogarty, editors, Genetic Programming, Proceedings of EuroGP'2000, volume 1802 of LNCS, pages 149-162, Edinburgh, 15- 16 Apr. 2000. Springer-Verlag.
M. O'Neill and C. Ryan. Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language. Kluwer Academic Publishers, 2003.
U.-M. O'Reilly. Using a distance metric on genetic programs to understand genetic operators. In IEEE International Conference on Systems, Man, and Cybernetics: Computational Cybernetics and Simulation, volume 5, 1997. http://dx.doi.org/10.1109/ICSMC.1997.637337
F. Rothlauf. Representations for Genetic and Evolutionary Algorithms. Physica-Verlag, 2nd edition, 2006.
F. Rothlauf. On the bias and performance of the edge-set encoding. IEEE transactions on evolutionary computation, 13(3):486-499, June 2009. http://dx.doi.org/10.1109/TEVC.2008.2008799
F. Rothlauf and D. Goldberg. Redundant Representations in Evolutionary Algorithms. Evolutionary Computation, 11(4):381-415, 2003. http://dx.doi.org/10.1162/106365603322519288
F. Rothlauf and M. Oetzel. On the locality of grammatical evolution. In P. Collet, M. Tomassini, M. Ebner, S. Gustafson, and A. Ekárt, editors, Proceedings of the 9th European Conference on Genetic Programming, volume 3905 of Lecture Notes in Computer Science, pages 320-330, Budapest, Hungary, 10 - 12 Apr. 2006. Springer.
D. Shasha and K. Zhang. Fast Parallel Algorithms for the Unit Cost Editing Distance Between Trees. In SPAA '89: Proceedings of the First Annual ACM Symposium on Parallel Algorithms and Architectures, pages 117-126, New York, NY, USA, 1989. ACM. http://dx.doi.org/10.1145/72935.72949
M. Tacker, P. F. Stadler, E. G. Bornberg-Bauer, I. L. Hofacker, and P. Schuster. Algorithm Indepedent Properties of RNA Secondary Structure Predictions. European Biophysics Journal, 25(2):115-130, 1996. (Pubitemid 27026515) http://dx.doi.org/10.1007/s002490050023
H. Takagi. Interactive evolutionary computation: Fusion of the capabilities of EC optimization and human evaluation. Proceedings of the IEEE, 89(9):1275-1296, Sept. 2001. Invited Paper. (Pubitemid 33766623)