Difference between revisions of "Genetic Programming"

From Chessprogramming wiki
Jump to: navigation, search
Line 141: Line 141:
 
* [[Wojciech Jaśkowski]], [[Krzysztof Krawiec]], [[Bartosz Wieloch]] ('''2008'''). ''Evolving Strategy for a Probabilistic Game of Imperfect Information using Genetic Programming''.  Genetic Programming and Evolvable Machines, Vol. 9, No. 4, [http://www.cs.put.poznan.pl/wjaskowski/pub/papers/jaskowski08evolving.pdf pdf]
 
* [[Wojciech Jaśkowski]], [[Krzysztof Krawiec]], [[Bartosz Wieloch]] ('''2008'''). ''Evolving Strategy for a Probabilistic Game of Imperfect Information using Genetic Programming''.  Genetic Programming and Evolvable Machines, Vol. 9, No. 4, [http://www.cs.put.poznan.pl/wjaskowski/pub/papers/jaskowski08evolving.pdf pdf]
 
* [[Borko Bošković]], [[Sašo Greiner]], [[Janez Brest]], [[Aleš Zamuda]], [[Viljem Žumer]] ('''2008'''). ''An Adaptive Differential Evolution Algorithm with Opposition-Based Mechanisms, Applied to the Tuning of a Chess Program''. [http://www.springer.com/engineering/computational+intelligence+and+complexity/book/978-3-540-68827-3 Advances in Differential Evolution], Studies in Computational Intelligence, ISBN: 978-3-540-68827-3
 
* [[Borko Bošković]], [[Sašo Greiner]], [[Janez Brest]], [[Aleš Zamuda]], [[Viljem Žumer]] ('''2008'''). ''An Adaptive Differential Evolution Algorithm with Opposition-Based Mechanisms, Applied to the Tuning of a Chess Program''. [http://www.springer.com/engineering/computational+intelligence+and+complexity/book/978-3-540-68827-3 Advances in Differential Evolution], Studies in Computational Intelligence, ISBN: 978-3-540-68827-3
* [[Eli David|Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2008'''). ''Genetic Algorithms for Mentor-Assisted Evaluation Function Optimization''. ACM Genetic and Evolutionary Computation Conference ([http://www.sigevo.org/gecco-2008/ GECCO '08]), pp. 1469-1475, Atlanta, GA, July 2008.
+
* [[Eli David|Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2008'''). ''Genetic Algorithms for Mentor-Assisted Evaluation Function Optimization''. [http://www.sigevo.org/gecco-2008/ GECCO '08], [https://arxiv.org/abs/1711.06839 arXiv:1711.06839]
 
* [[Pieter Spronck]], [[Ida Sprinkhuizen-Kuyper]], [[Eric Postma]] ('''2008'''). ''Deca: the doping-Driven Evolutionary Control Algorithm''. [http://www.informatik.uni-trier.de/~ley/db/journals/aai/aai22.html#SpronckSP08 Applied Artificial Intelligence, Vol. 22]
 
* [[Pieter Spronck]], [[Ida Sprinkhuizen-Kuyper]], [[Eric Postma]] ('''2008'''). ''Deca: the doping-Driven Evolutionary Control Algorithm''. [http://www.informatik.uni-trier.de/~ley/db/journals/aai/aai22.html#SpronckSP08 Applied Artificial Intelligence, Vol. 22]
 
'''2009'''
 
'''2009'''
* [[Eli David|Omid David]], [[Jaap van den Herik]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2009'''). ''Simulating Human Grandmasters: Evolution and Coevolution of Evaluation Functions''. [[ACM]] Genetic and Evolutionary Computation Conference ([http://www.sigevo.org/gecco-2009/ GECCO '09]), pp. 1483 - 1489, [https://en.wikipedia.org/wiki/Montreal Montreal], Canada
+
* [[Eli David|Omid David]], [[Jaap van den Herik]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2009'''). ''Simulating Human Grandmasters: Evolution and Coevolution of Evaluation Functions''. [http://www.sigevo.org/gecco-2009/ GECCO '09], [https://arxiv.org/abs/1711.06840 arXiv:1711.06840]
 
* [[Eli David|Omid David]] ('''2009'''). ''Genetic Algorithms Based Learning for Evolving Intelligent Organisms''. Ph.D. Thesis <ref>[[Dap Hartmann]] ('''2010'''). ''Mimicking the Black Box - Genetically evolving evaluation functions and search algorithms''. Review on Omid David's Ph.D. Thesis, [[ICGA Journal#33_1|ICGA Journal, Vol. 33, No. 1]]</ref>  
 
* [[Eli David|Omid David]] ('''2009'''). ''Genetic Algorithms Based Learning for Evolving Intelligent Organisms''. Ph.D. Thesis <ref>[[Dap Hartmann]] ('''2010'''). ''Mimicking the Black Box - Genetically evolving evaluation functions and search algorithms''. Review on Omid David's Ph.D. Thesis, [[ICGA Journal#33_1|ICGA Journal, Vol. 33, No. 1]]</ref>  
 
* [[Ami Hauptman]] ('''2009'''). ''Evolving Search Heuristics for Combinatorial Games with Genetic Programming''. [https://en.wikipedia.org/wiki/Ben-Gurion_University_of_the_Negev Ben-Gurion University of the Negev]
 
* [[Ami Hauptman]] ('''2009'''). ''Evolving Search Heuristics for Combinatorial Games with Genetic Programming''. [https://en.wikipedia.org/wiki/Ben-Gurion_University_of_the_Negev Ben-Gurion University of the Negev]
Line 153: Line 153:
 
==2010 ...==  
 
==2010 ...==  
 
* [[Dmitry Batenkov]] ('''2010'''). ''[http://xrds.acm.org/article.cfm?aid=1836558 Hands-on introduction to genetic programming]''. [[ACM#XRDS|ACM Crossroads]], Vol. 17, No. 1
 
* [[Dmitry Batenkov]] ('''2010'''). ''[http://xrds.acm.org/article.cfm?aid=1836558 Hands-on introduction to genetic programming]''. [[ACM#XRDS|ACM Crossroads]], Vol. 17, No. 1
* [[Eli David|Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''[http://www.springerlink.com/content/3346t8432n718821 Expert-Driven Genetic Algorithms for Simulating Evaluation Functions]''.
+
* [[Eli David|Omid David]], [[Nathan S. Netanyahu]], Yoav Rosenberg, Moshe Shimoni ('''2010'''). ''Genetic Algorithms for Automatic Classification of Moving Objects''. [[ACM]] Genetic and Evolutionary Computation Conference ([http://www.sigevo.org/gecco-2010/ GECCO '10]), [https://en.wikipedia.org/wiki/Portland,_Oregon Portland, OR]
* [[Eli David|Omid David]], [[Nathan S. Netanyahu]], Yoav Rosenberg and Moshe Shimoni ('''2010'''). ''Genetic Algorithms for Automatic Classification of Moving Objects''. [[ACM]] Genetic and Evolutionary Computation Conference ([http://www.sigevo.org/gecco-2010/ GECCO '10]), [https://en.wikipedia.org/wiki/Portland,_Oregon Portland, OR]
 
 
* [[Eli David|Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''Genetic Algorithms for Automatic Search Tuning''. [[ICGA Journal#33_2|ICGA Journal, Vol. 33, No. 2]]
 
* [[Eli David|Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''Genetic Algorithms for Automatic Search Tuning''. [[ICGA Journal#33_2|ICGA Journal, Vol. 33, No. 2]]
 +
* [[Eli David|Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''Optimizing Selective Search in Chess''. [https://icml.cc/Conferences/2010/program.html ICML Workshop on Machine Learning and Games], [https://arxiv.org/abs/1009.0550 arXiv:1009.0550]
 
* [[Jean-Baptiste Hoock]], [[Olivier Teytaud]] ('''2010'''). ''[http://hal.inria.fr/inria-00452887/en/ Bandit-Based Genetic Programming]''. 13th European Conference on Genetic Programming (2010), [http://hal.inria.fr/docs/00/45/28/87/PDF/pattern.pdf pdf]
 
* [[Jean-Baptiste Hoock]], [[Olivier Teytaud]] ('''2010'''). ''[http://hal.inria.fr/inria-00452887/en/ Bandit-Based Genetic Programming]''. 13th European Conference on Genetic Programming (2010), [http://hal.inria.fr/docs/00/45/28/87/PDF/pattern.pdf pdf]
 
* [[Borko Bošković]] ('''2010'''). ''[http://labraj.uni-mb.si/en/PhD_Thesis_Defence_%28Borko_Bo%C5%A1kovi%C4%87%29 Differential evolution for the Tuning of a Chess Evaluation Function]''. Ph.D. thesis, [[University of Maribor]]
 
* [[Borko Bošković]] ('''2010'''). ''[http://labraj.uni-mb.si/en/PhD_Thesis_Defence_%28Borko_Bo%C5%A1kovi%C4%87%29 Differential evolution for the Tuning of a Chess Evaluation Function]''. Ph.D. thesis, [[University of Maribor]]
Line 169: Line 169:
 
* [[Borko Bošković]], [[Janez Brest]] ('''2011'''). ''[http://www.informatica.si/index.php/informatica/article/view/353 Tuning Chess Evaluation Function Parameters using Differential Evolution]''. Algorithm. Informatica, 35, No. 2
 
* [[Borko Bošković]], [[Janez Brest]] ('''2011'''). ''[http://www.informatica.si/index.php/informatica/article/view/353 Tuning Chess Evaluation Function Parameters using Differential Evolution]''. Algorithm. Informatica, 35, No. 2
 
* [[Borko Bošković]], [[Janez Brest]], [[Aleš Zamuda]], [[Sašo Greiner]], [[Viljem Žumer]] ('''2011'''). ''[http://www.springerlink.com/content/y62h14743364x2l7/ History mechanism supported differential evolution for chess evaluation function tuning]''. [http://www.springer.com/engineering/computational+intelligence+and+complexity/journal/500 Soft Computing], Vol. 15, No. 4
 
* [[Borko Bošković]], [[Janez Brest]], [[Aleš Zamuda]], [[Sašo Greiner]], [[Viljem Žumer]] ('''2011'''). ''[http://www.springerlink.com/content/y62h14743364x2l7/ History mechanism supported differential evolution for chess evaluation function tuning]''. [http://www.springer.com/engineering/computational+intelligence+and+complexity/journal/500 Soft Computing], Vol. 15, No. 4
* [[Eli David|Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2011'''). ''Expert-Driven Genetic Algorithms for Simulating Evaluation Functions''. Genetic Programming and Evolvable Machines, Vol. 12, No. 1, [http://u.cs.biu.ac.il/~koppel/papers/expertga-oct21.pdf pdf]
+
* [[Eli David|Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2011'''). ''[https://link.springer.com/article/10.1007/s10710-010-9103-4 Expert-Driven Genetic Algorithms for Simulating Evaluation Functions]''. [https://www.springer.com/journal/10710 Genetic Programming and Evolvable Machines], Vol. 12, No. 1, [https://arxiv.org/abs/1711.06841 arXiv:1711.06841]
 
* [[Eduardo Vázquez-Fernández]], [[Carlos Artemio Coello Coello]], [[Feliú Davino Sagols Troncoso]] ('''2011'''). ''An Evolutionary Algorithm for Tuning a Chess Evaluation Function''. [http://www.informatik.uni-trier.de/~ley/db/conf/cec/cec2011.html#Vazquez-FernandezCT11 CEC 2011], [http://delta.cs.cinvestav.mx/~ccoello/conferences/eduardo-cec2011-final.pdf.gz pdf]
 
* [[Eduardo Vázquez-Fernández]], [[Carlos Artemio Coello Coello]], [[Feliú Davino Sagols Troncoso]] ('''2011'''). ''An Evolutionary Algorithm for Tuning a Chess Evaluation Function''. [http://www.informatik.uni-trier.de/~ley/db/conf/cec/cec2011.html#Vazquez-FernandezCT11 CEC 2011], [http://delta.cs.cinvestav.mx/~ccoello/conferences/eduardo-cec2011-final.pdf.gz pdf]
 
* [[Eduardo Vázquez-Fernández]], [[Carlos Artemio Coello Coello]], [[Feliú Davino Sagols Troncoso]] ('''2011'''). ''[http://dl.acm.org/citation.cfm?id=2001882 An Adaptive Evolutionary Algorithm Based on Typical Chess Problems for Tuning a Chess Evaluation Function]''. [http://www.informatik.uni-trier.de/~ley/db/conf/gecco/gecco2011c.html#Vazquez-FernandezCT11 GECCO 2011], [http://delta.cs.cinvestav.mx/~ccoello/conferences/vazquez-gecco2011.pdf.gz pdf]
 
* [[Eduardo Vázquez-Fernández]], [[Carlos Artemio Coello Coello]], [[Feliú Davino Sagols Troncoso]] ('''2011'''). ''[http://dl.acm.org/citation.cfm?id=2001882 An Adaptive Evolutionary Algorithm Based on Typical Chess Problems for Tuning a Chess Evaluation Function]''. [http://www.informatik.uni-trier.de/~ley/db/conf/gecco/gecco2011c.html#Vazquez-FernandezCT11 GECCO 2011], [http://delta.cs.cinvestav.mx/~ccoello/conferences/vazquez-gecco2011.pdf.gz pdf]
Line 190: Line 190:
 
* [[Ilya Loshchilov]]  ('''2013'''). ''[http://loshchilov.com/phd.html Surrogate-Assisted Evolutionary Algorithms]''. Ph.D. thesis, [[University of Paris#11|Paris-Sud 11 University]], advisors [[Marc Schoenauer]] and [[Michèle Sebag]]
 
* [[Ilya Loshchilov]]  ('''2013'''). ''[http://loshchilov.com/phd.html Surrogate-Assisted Evolutionary Algorithms]''. Ph.D. thesis, [[University of Paris#11|Paris-Sud 11 University]], advisors [[Marc Schoenauer]] and [[Michèle Sebag]]
 
'''2014'''
 
'''2014'''
* [[Eli David|Omid E. David]], [[Jaap van den Herik]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2014'''). ''Genetic Algorithms for Evolving Computer Chess Programs''. [[IEEE#EC|IEEE Transactions on Evolutionary Computation]], [http://www.genetic-programming.org/hc2014/David-Paper.pdf pdf] <ref>[http://www.liacs.nl/nieuws/jaap-van-den-herik-wint-humies-award-2014/ Jaap van den Herik wint Humies Award 2014 - LIACS - Leiden Institute of Advanced Computer Science]</ref> <ref>[http://www.sigevo.org/gecco-2014/humies.html GECCO 2014]</ref>
+
* [[Eli David|Omid David]], [[Jaap van den Herik]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2014'''). ''Genetic Algorithms for Evolving Computer Chess Programs''. [[IEEE#EC|IEEE Transactions on Evolutionary Computation]], [https://arxiv.org/abs/1711.08337 arXiv:1711.08337]
 
* [[Wojciech Jaśkowski]], [[Marcin Szubert]], [[Paweł Liskowski]] ('''2014'''). ''Multi-Criteria Comparison of Coevolution and Temporal Difference Learning on Othello''. [http://www.evostar.org/2014/ EvoApplications 2014], [http://www.springer.com/computer/theoretical+computer+science/book/978-3-662-45522-7 Springer, volume 8602] » [[Othello]]
 
* [[Wojciech Jaśkowski]], [[Marcin Szubert]], [[Paweł Liskowski]] ('''2014'''). ''Multi-Criteria Comparison of Coevolution and Temporal Difference Learning on Othello''. [http://www.evostar.org/2014/ EvoApplications 2014], [http://www.springer.com/computer/theoretical+computer+science/book/978-3-662-45522-7 Springer, volume 8602] » [[Othello]]
 
* [http://people.csail.mit.edu/ignacioarnaldo/ Ignacio Arnaldo], [[Krzysztof Krawiec]], [http://people.csail.mit.edu/unamay/ Una-May O'Reilly] ('''2014'''). ''Multiple Regression Genetic Programming''. [http://www.informatik.uni-trier.de/~ley/db/conf/gecco/gecco2014.html#ArnaldoKO14 GECCO 2014], [http://www.cs.put.poznan.pl/kkrawiec/wiki/uploads/Site/2015GeccoMRGP.pdf pdf]
 
* [http://people.csail.mit.edu/ignacioarnaldo/ Ignacio Arnaldo], [[Krzysztof Krawiec]], [http://people.csail.mit.edu/unamay/ Una-May O'Reilly] ('''2014'''). ''Multiple Regression Genetic Programming''. [http://www.informatik.uni-trier.de/~ley/db/conf/gecco/gecco2014.html#ArnaldoKO14 GECCO 2014], [http://www.cs.put.poznan.pl/kkrawiec/wiki/uploads/Site/2015GeccoMRGP.pdf pdf]

Revision as of 21:58, 4 February 2020

Home * Learning * Genetic Programming

Genetic Programming [1]

Genetic Programming (GP),
an evolutionary based methodology inspired by biological evolution to optimize computer programs, in particular game playing programs. It is a machine learning technique used to optimize a population of programs, for instance to maximize the winning rate versus a set of opponents, after modifying evaluation weights or search parameter.

Evolutionary Programming

Evolutionary programming is similar to genetic programming, but the structure of the program to be optimized is fixed, while its numerical parameters are allowed to evolve. The term was coined by Lawrence J. Fogel in 1960.

Supersets

Genetic Programming is subset of a chain of subsequent fields in Artificial Intelligence.

Genetic Algorithms

Genetic Programming is a specialization of genetic algorithms (GA) where individuals are computer programs. This heuristic is routinely used to generate useful solutions to optimization and search problems. A genetic algorithm requires:

  1. Genetic representation
  2. Fitness function

performing the Genetic operations of

  1. Selection (genetic algorithm)
    1. Fitness proportionate selection
    2. Reward-based selection
    3. Stochastic universal sampling
    4. Tournament selection
    5. Truncation selection
  2. Crossover (genetic algorithm)

PBIL

Population-based incremental learning (PBIL) is a type of of genetic algorithm where the genotype of an entire population (probability vector) is evolved rather than individual members. The algorithm was proposed by Shumeet Baluja in 1994 [2]. The algorithm is simpler than a standard genetic algorithm, and in many cases leads to better results than a standard genetic algorithm [3].

Evolutionary Algorithms

Genetic algorithms belong to the larger class of evolutionary algorithms (EA). An EA uses some mechanisms inspired by biological evolution: reproduction, mutation, recombination, and selection. EAs are individual components that participate in an artificial evolution (AE).

Evolutionary Computation

An evolutionary algorithm (EA) is subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. Evolutionary computation, introduced by John Henry Holland in the 1970s and more popular since 1990s mimics the population-based sexual evolution through reproduction of generations.

Computational Intelligence

Computational Intelligence (CI) is a set of Nature-inspired computational methodologies and approaches and field of Artificial Intelligence. It primarily includes many-valued logic or Fuzzy logic, Neural Networks, Evolutionary Computation, swarm intelligence and Artificial immune system.

See also

Publications

1950 ...

  • Nils Barricelli (1954). Esempi numerici di processi di evoluzione, Methodos, pp. 45-68, 1954
  • Nils Barricelli (1957). Symbiogenetic evolution processes realized by artificial methods. Methodos: 143–182.

1960 ...

1970 ...

  • John Henry Holland (1975). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. amazon.com

1980 ...

1990 ...

1995 ...

2000 ....

2001

2002

2003

2004

2005 ...

2006

2007

2008

2009

2010 ...

2011

2012

2013

2014

2015 ...

Forum Posts

1996 ...

Re: Genetic Algorithms for Chess Evaluation Functions by Jay Scott, rgcc, July 01, 1996

2010 ...

2015 ...

Re: Genetical tuning by Ferdinand Mosca, CCC, August 20, 2015

External Links

Genetic Programming

Evolutionary Programming

Genetic Algorithms

Fitness proportionate selection from Wikipedia
Reward-based selection from Wikipedia
Stochastic universal sampling from Wikipedia
Tournament selection from Wikipedia
Truncation selection from Wikipedia

Evolutionary Algorithms

Evolutionary Computation

Misc

feat.: Bennie Maupin, Bill Summers, Paul Jackson, Mike Clark and Blackbird McKnight

References

Up one Level