%0 Conference Paper %1 1277283 %A Looks, Moshe %B GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation %C London %D 2007 %E Thierens, Dirk %E Beyer, Hans-Georg %E Bongard, Josh %E Branke, Jurgen %E Clark, John Andrew %E Cliff, Dave %E Congdon, Clare Bates %E Deb, Kalyanmoy %E Doerr, Benjamin %E Kovacs, Tim %E Kumar, Sanjeev %E Miller, Julian F. %E Moore, Jason %E Neumann, Frank %E Pelikan, Martin %E Poli, Riccardo %E Sastry, Kumara %E Stanley, Kenneth Owen %E Stutzle, Thomas %E Watson, Richard A %E Wegener, Ingo %I ACM Press %K Study, algorithms, empirical genetic heuristics, optimisation, programming, representation %P 1636--1642 %T On the behavioral diversity of random programs %U http://doi.acm.org/10.1145/1276958.1277283 %V 2 %X Generating a random sampling of program trees with specified function and terminal sets is the initial step of many program evolution systems. I present a theoretical and experimental analysis of the expected distribution of uniformly sampled programs, guided by algorithmic information theory. This analysis demonstrates that increasing the sample size is often an inefficient means of increasing the overall diversity of program behaviours (outputs). A novel sampling scheme (semantic sampling) is proposed that exploits semantics to heuristically increase behavioral diversity. An important property of the scheme is that no calls of the problem-specific fitness function are required. Its effectiveness at increasing behavioural diversity is demonstrated empirically for Boolean formulae. Furthermore, it is found to lead to statistically significant improvements in performance for genetic programming on parity and multiplexer problems.

@inproceedings{1277283, abstract = {Generating a random sampling of program trees with specified function and terminal sets is the initial step of many program evolution systems. I present a theoretical and experimental analysis of the expected distribution of uniformly sampled programs, guided by algorithmic information theory. This analysis demonstrates that increasing the sample size is often an inefficient means of increasing the overall diversity of program behaviours (outputs). A novel sampling scheme (semantic sampling) is proposed that exploits semantics to heuristically increase behavioral diversity. An important property of the scheme is that no calls of the problem-specific fitness function are required. Its effectiveness at increasing behavioural diversity is demonstrated empirically for Boolean formulae. Furthermore, it is found to lead to statistically significant improvements in performance for genetic programming on parity and multiplexer problems.}, added-at = {2008-06-19T17:35:00.000+0200}, address = {London}, author = {Looks, Moshe}, biburl = {https://www.bibsonomy.org/bibtex/2805e08991b67294c84b410cd1d51f57a/brazovayeye}, booktitle = {GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation}, editor = {Thierens, Dirk and Beyer, Hans-Georg and Bongard, Josh and Branke, Jurgen and Clark, John Andrew and Cliff, Dave and Congdon, Clare Bates and Deb, Kalyanmoy and Doerr, Benjamin and Kovacs, Tim and Kumar, Sanjeev and Miller, Julian F. and Moore, Jason and Neumann, Frank and Pelikan, Martin and Poli, Riccardo and Sastry, Kumara and Stanley, Kenneth Owen and Stutzle, Thomas and Watson, Richard A and Wegener, Ingo}, interhash = {650455d4704ef472ba0adbcaa43b896f}, intrahash = {805e08991b67294c84b410cd1d51f57a}, isbn13 = {978-1-59593-697-4}, keywords = {Study, algorithms, empirical genetic heuristics, optimisation, programming, representation}, month = {7-11 July}, notes = {GECCO-2007 A joint meeting of the sixteenth international conference on genetic algorithms (ICGA-2007) and the twelfth annual genetic programming conference (GP-2007). ACM Order Number 910071}, organisation = {ACM SIGEVO (formerly ISGEC)}, pages = {1636--1642}, publisher = {ACM Press}, publisher_address = {New York, NY, USA}, timestamp = {2008-06-19T17:45:48.000+0200}, title = {On the behavioral diversity of random programs}, url = {http://doi.acm.org/10.1145/1276958.1277283}, volume = 2, year = 2007 }