research-article

Evolving neural networks for fractured domains

Authors:

Risto MiikkulainenAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 1405 - 1412

https://doi.org/10.1145/1389095.1389366

Published: 12 July 2008 Publication History

Abstract

Evolution of neural networks, or neuroevolution, bas been successful on many low-level control problems such as pole balancing, vehicle control, and collision warning. However, high-level strategy problems that require the integration of multiple sub-behaviors have remained difficult for neuroevolution to solve. This paper proposes the hypothesis that such problems are difficult because they are fractured: the correct action varies discontinuously as the agent moves from state to state. This hypothesis is evaluated on several examples of fractured high-level reinforcement learning domains. Standard neuroevolution methods such as NEAT indeed have difficulty solving them. However, a modification of NEAT that uses radial basis function (RBF) nodes to make precise local mutations to network output is able to do much better. These results provide a better understanding of the different types of reinforcement learning problems and the limitations of current neuroevolution methods. Thus, they lay the groundwork for creating the next generation of neuroevolution algorithms that can learn strategic high-level behavior in fractured domains.

References

[1]

P. J. Angeline. Evolving basis functions with dynamic receptive fields. In IEEE International Conference on Systems, Man, and Cybernetics, volume 5, pages 4109--4114, 1997.

[2]

A. Barron, J. Rissanen, and B. Yu. The minimum description length principle in coding and modeling. IEEE Trans. Information Theory, 44(6):2743--2760, 1998.

Digital Library

[3]

S. A. Billings and G. L. Zheng. Radial basis function network configuration using genetic algorithms. Neural Networks, 8:877--890, 1995.

Digital Library

[4]

L. Bull and T. O'Hara. Accuracy-based neuro and neuro-fuzzy classifier systems. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 905--911, 2002.

Digital Library

[5]

M. V. Butz. Kernel-based, ellipsoidal conditions in the real-valued xcs classifier system. In Proceedings of the 2005 conference on Genetic and Evolutionary Computation, pages 1835--1842, 2005.

Digital Library

[6]

N. Chaiyaratana and A. M. S. Zalzala. Evolving hybrid rbf-mlp networks using combinedgenetic/unsupervised/supervised learning. In UKACC International Conference on Control, volume 1, pages 330--335, 1998.

[7]

D. E. Goldberg and J. Richardson. Genetic algorithms with sharing for multimodal function optimization. In Proceedings of the Second International Conference on Genetic Algorithms, pages 148--154, 1987.

Digital Library

[8]

F. Gomez, J. Schmidhuber, and R. Miikkulainen. Efficient non-linear control through neuroevolution. In Proceedings of the European Conference on Machine Learning (ECML-06, Berlin), 2006.

Digital Library

[9]

J. Gonzalez, I. Rojas, J. Ortega, H. Pomares, F. Fernandez, and A. Diaz. Multiobjective evolutionary optimization of the size, shape, and position parameters of radial basis function networks for function approximation. IEEE Transactions on Neural Networks, 14:1478--1495, 2003.

Digital Library

[10]

F. Gruau, D. Whitley, and L. Pyeatt. A comparison between cellular encoding and direct encoding for genetic neural networks. 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 81--89. MIT Press, 1996.

Digital Library

[11]

A. Guillen, H. Pomares, J. Gonzalez, I. Rojas, L. J. Herrera, and A. Prieto. Parallel Multi-objective Memetic RBFNNs Design and Feature Selection for Function Approximation Problems, volume 4507/2007. 2007.

Digital Library

[12]

A. Guillen, I. Rojas, J. Gonzalez, H. Pomares, L. J. Herrera, and B. Paechter. Improving the Performance of Multi-objective Genetic Algorithm for Function Approximation Through Parallel Islands Specialisation, volume 4304/2006. 2006.

Digital Library

[13]

L. Guo, D.-S. Huang, and W. Zhao. Combining genetic optimisation with hybrid learning algorithm for radial basis function neural networks. Electronics Letters, 39:1600--1601, 2003.

[14]

H. Gutmann. A radial basis function method for global optimization. Journal of Global Optimization, 19:201--227, 2001.

Digital Library

[15]

N. Kohl, K. Stanley, R. Miikkulainen, M. Samples, and R. Sherony. Evolving a real-world vehicle warning system. In Proceedings of the Genetic and Evolutionary Computation Conference 2006, pages 1681--1688, July 2006.

Digital Library

[16]

R. Kretchmar and C. Anderson. Comparison of cmacs and radial basis functions for local function approximators in reinforcement learning. In Proceedings of the International Conference on Neural Networks, 1997.

[17]

P. Lanzi, D. Loiacono, S. Wilson, and D. Goldberg. Classifier prediction based on tile coding. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1497--1504, 2006.

Digital Library

[18]

P. L. Lanzi, D. Loiacono, S. W. Wilson, and D. E. Goldberg. Xcs with computed prediction for the learning of boolean functions. In Proceedings of the IEEE Congress on Evolutionary Computation Conference, 2005.

[19]

J. Li and T. Duckett. Q-learning with a growing rbf network for behavior learning in mobile robotics. In Proceedings of the Sixth IASTED International Conference on Robotics and Applications, 2005.

[20]

J. Li, T. Martinez-Maron, A. Lilienthal, and T. Duckett. Q-ran: A constructive reinforcement learning approach for robot behavior learning. In Proceedings of IEEE/RSJ International Conference on Intelligent Robot and System, 2006.

[21]

S. Lucas and J. Togelius. Point-to-point car racing: an initial study of evolution versus temporal difference learning. In IEEE Symposium on Computational Intelligence and Games, pages 260--267, 2007.

Digital Library

[22]

E. Maillard and D. Gueriot. Rbf neural network, basis functions and genetic algorithm. In International Conference on Neural Networks, volume 4, 1997.

[23]

J. Moody and C. J. Darken. Fast learning in networks of locally tuned processing units. Neural Computation, 1:281--294, 1989.

Digital Library

[24]

J. Park and I. W. Sandberg. Universal approximation using radial-basis-function networks. Neural Computation, 3:246--257, 1991.

[25]

N. J. Radcliffe. Genetic set recombination and its application to neural network topology optimization. Neural Computing and Applications, 1(1):67--90, 1993.

[26]

J. Reisinger, E. Bahceci, I. Karpov, and R. Miikkulainen. Coevolving strategies for general game playing. In Proceedings of the IEEE Symposium on Computational Intelligence and Games, 2007.

Digital Library

[27]

H. Sarimveis, A. Alexandridis, S. Mazarakis, and G. Bafas. A new algorithm for developing dynamic radial basis function neural network models based on genetic algorithms. Computers and Chemical Engineering, 28:209--217, 2004.

[28]

K. Stanley, N. Kohl, R. Sherony, and R. Miikkulainen. Neuroevolution of an automobile crash warning system. In Proceedings of the Genetic and Evolutionary Computation Conference 2005, pages 1977--1984, 2005.

Digital Library

[29]

K. O. Stanley, B. D. Bryant, and R. Miikkulainen. Real-time neuroevolution in the NERO video game. IEEE Transactions on Evolutionary Computation, 9(6):653--668, 2005.

Digital Library

[30]

K. O. Stanley and R. Miikkulainen. Evolving neural networks through augmenting topologies. Evolutionary Computation, 10(2), 2002.

Digital Library

[31]

K. O. Stanley and R. Miikkulainen. Competitive coevolution through evolutionary complexification. Journal of Artificial Intelligence Research, 21:63--100, 2004.

Digital Library

[32]

K. O. Stanley and R. Miikkulainen. Evolving a roving eye for go. In Proceedings of the Genetic and Evolutionary Computation Conference, 2004.

[33]

P. Stone, G. Kuhlmann, M. E. Taylor, and Y. Liu. Keepaway soccer: From machine learning testbed to benchmark. In I. Noda et al., editors, RoboCup-2005: Robot Soccer World Cup IX, volume 4020, pages 93--105. Springer Verlag, Berlin, 2006.

Digital Library

[34]

M. Taylor, S. Whiteson, and P. Stone. Comparing evolutionary and temporal difference methods for reinforcement learning. In Genetic and Evolutionary Computation Conference, pages 1321--28, July 2006.

Digital Library

[35]

J. Togelius, S. Lucas, H. D. Thang, J. Garibaldi, T. Nakashima, C. H. Tan, I. Elhanany, S. Berant, P. Hingston, R. M. MacCallum, A. Gowrisankar, P. Burrow, and T. Haferlach. The 2007 IEEE CEC simulated car racing competition. Unpublished manuscript.

[36]

V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16:264--280, 1971.

[37]

B. Whitehead and T. Choate. Cooperative-competitive genetic evolution of radial basis functioncenters and widths for time series prediction. IEEE Transactions on Neural Networks, 7:869--880, 1996.

Digital Library

[38]

S. W. Wilson. Classifiers that approximate functions. Natural Computing, 1:211--234, 2002.

Digital Library

[39]

S. W. Wilson. Classifier conditions using gene expression programming. Technical Report 2008001, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, 2008.

[40]

X. Yao. Evolving artificial neural networks. Proceedings of the IEEE, 87(9):1423--1447, 1999.

Cited By

Zaniolo MGiuliani MCastelletti A(2022)Neuro-Evolutionary Direct Policy Search for Multiobjective Optimal ControlIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2021.307196033:10(5926-5938)Online publication date: Oct-2022
https://doi.org/10.1109/TNNLS.2021.3071960
John NGow J(2021)Adversarial Behaviour Debugging in a Two Button Fighting Game2021 IEEE Conference on Games (CoG)10.1109/CoG52621.2021.9618893(01-08)Online publication date: 17-Aug-2021
https://doi.org/10.1109/CoG52621.2021.9618893
Vargas DMurata J(2017)Spectrum-Diverse Neuroevolution With Unified Neural ModelsIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2016.255174828:8(1759-1773)Online publication date: Aug-2017
https://doi.org/10.1109/TNNLS.2016.2551748
Show More Cited By

Index Terms

Evolving neural networks for fractured domains
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Neural networks

Recommendations

Evolving neural networks
GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation

Neuroevolution, i.e. evolution of artificial neural networks, has recently emerged as a powerful technique for solving challenging reinforcement learning problems. Compared to traditional (e.g. value-function based) methods, neuroevolution is especially ...
Investigating whether hyperNEAT produces modular neural networks
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

HyperNEAT represents a class of neuroevolutionary algorithms that captures some of the power of natural development with a computationally efficient high-level abstraction of development. This class of algorithms is intended to provide many of the ...
Evolving the placement and density of neurons in the hyperneat substrate
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

The Hypercube-based NeuroEvolution of Augmenting Topologies (HyperNEAT) approach demonstrated that the pattern of weights across the connectivity of an artificial neural network (ANN) can be generated as a function of its geometry, thereby allowing ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
382
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zaniolo MGiuliani MCastelletti A(2022)Neuro-Evolutionary Direct Policy Search for Multiobjective Optimal ControlIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2021.307196033:10(5926-5938)Online publication date: Oct-2022
https://doi.org/10.1109/TNNLS.2021.3071960
John NGow J(2021)Adversarial Behaviour Debugging in a Two Button Fighting Game2021 IEEE Conference on Games (CoG)10.1109/CoG52621.2021.9618893(01-08)Online publication date: 17-Aug-2021
https://doi.org/10.1109/CoG52621.2021.9618893
Vargas DMurata J(2017)Spectrum-Diverse Neuroevolution With Unified Neural ModelsIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2016.255174828:8(1759-1773)Online publication date: Aug-2017
https://doi.org/10.1109/TNNLS.2016.2551748
Vargas DTakano HMurata JEsparcia-Alcázar A(2015)The Relationship Between (Un)Fractured Problems and Division of Input SpaceProceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739482.2768447(981-987)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739482.2768447
Kohl NMiikkulainen R(2012)An Integrated Neuroevolutionary Approach to Reactive Control and High-Level StrategyIEEE Transactions on Evolutionary Computation10.1109/TEVC.2011.215075516:4(472-488)Online publication date: 1-Aug-2012
https://dl.acm.org/doi/10.1109/TEVC.2011.2150755
Svec PGupta S(2012)Automated synthesis of action selection policies for unmanned vehicles operating in adverse environmentsAutonomous Robots10.1007/s10514-011-9268-632:2(149-164)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1007/s10514-011-9268-6
Whiteson S(2012)Evolutionary Computation for Reinforcement LearningReinforcement Learning10.1007/978-3-642-27645-3_10(325-355)Online publication date: 2012
https://doi.org/10.1007/978-3-642-27645-3_10
Lowell JGrabkovsky SBirger K(2011)Comparison of NEAT and HyperNEAT Performance on a Strategic Decision-Making ProblemProceedings of the 2011 Fifth International Conference on Genetic and Evolutionary Computing10.1109/ICGEC.2011.33(102-105)Online publication date: 29-Aug-2011
https://dl.acm.org/doi/10.1109/ICGEC.2011.33
Whiteson STaylor MStone P(2010)Critical factors in the empirical performance of temporal difference and evolutionary methods for reinforcement learningAutonomous Agents and Multi-Agent Systems10.1007/s10458-009-9100-221:1(1-35)Online publication date: 1-Jul-2010
https://dl.acm.org/doi/10.1007/s10458-009-9100-2
Schrum JMiikkulainen R(2009)Evolving multi-modal behavior in NPCsProceedings of the 5th international conference on Computational Intelligence and Games10.5555/1719293.1719348(325-332)Online publication date: 7-Sep-2009
https://dl.acm.org/doi/10.5555/1719293.1719348
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten