Difference between revisions of "Genetic Programming"

From Chessprogramming wiki
Jump to: navigation, search
Line 132: Line 132:
 
* [[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
* [[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''. ACM Genetic and Evolutionary Computation Conference ([http://www.sigevo.org/gecco-2008/ GECCO '08]), pp. 1469-1475, Atlanta, GA, July 2008.
 
* [[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'''
* [[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''. [[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
* [[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]
 
* [[Nur Merve Amil]], [[Nicolas Bredèche]], [[Christian Gagné]], [[Sylvain Gelly]], [[Marc Schoenauer]], [[Olivier Teytaud]] ('''2009'''). ''A Statistical Learning Perspective of Genetic Programming''. EuroGP 2009, [http://hal.inria.fr/docs/00/36/97/82/PDF/eurogp.pdf pdf]
 
* [[Nur Merve Amil]], [[Nicolas Bredèche]], [[Christian Gagné]], [[Sylvain Gelly]], [[Marc Schoenauer]], [[Olivier Teytaud]] ('''2009'''). ''A Statistical Learning Perspective of Genetic Programming''. EuroGP 2009, [http://hal.inria.fr/docs/00/36/97/82/PDF/eurogp.pdf pdf]
Line 144: Line 144:
 
==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
* [[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]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2010'''). ''[http://www.springerlink.com/content/3346t8432n718821 Expert-Driven Genetic Algorithms for Simulating Evaluation Functions]''.  
* [[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]], [[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]
* [[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]]
 
* [[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 158: Line 158:
 
* [[Borko Bošković]], [[Janez Brest]] ('''2011'''). ''Tuning Chess Evaluation Function Parameters using Differential Evolution''. Algorithm. Informatica, 35, No. 2, [http://www.informatica.si/PDF/35-2/14_Boskovic%20-%20Tuning%20chess%20evaluation.pdf pdf]
 
* [[Borko Bošković]], [[Janez Brest]] ('''2011'''). ''Tuning Chess Evaluation Function Parameters using Differential Evolution''. Algorithm. Informatica, 35, No. 2, [http://www.informatica.si/PDF/35-2/14_Boskovic%20-%20Tuning%20chess%20evaluation.pdf pdf]
 
* [[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
* [[Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2011'''). ''Expert-Driven Genetic Algorithms for Simulating Evaluation Functions''. Genetic Programming and Evolvable Machines 12(1), pp. 5-20, [http://u.cs.biu.ac.il/~koppel/papers/expertga-oct21.pdf pdf]
+
* [[Eli David|Omid David]], [[Moshe Koppel]], [[Nathan S. Netanyahu]] ('''2011'''). ''Expert-Driven Genetic Algorithms for Simulating Evaluation Functions''. Genetic Programming and Evolvable Machines 12(1), pp. 5-20, [http://u.cs.biu.ac.il/~koppel/papers/expertga-oct21.pdf 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'''). ''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 176: Line 176:
 
* [[S. Ali Mirsoleimani]], [http://dblp.uni-trier.de/pers/hd/k/Karami:Ali Ali Karami], [http://dblp.uni-trier.de/pers/hd/k/Khunjush:Farshad Farshad Khunjush] ('''2013'''). ''[https://scholar.google.de/citations?view_op=view_citation&hl=en&user=VvkRESgAAAAJ&citation_for_view=VvkRESgAAAAJ:ufrVoPGSRksC A parallel memetic algorithm on GPU to solve the task scheduling problem in heterogeneous environments]''. [http://www.sigevo.org/gecco-2013/program.html GECCO '13], [https://www.lri.fr/~hansen/proceedings/2013/GECCO/proceedings/p1181.pdf pdf]
 
* [[S. Ali Mirsoleimani]], [http://dblp.uni-trier.de/pers/hd/k/Karami:Ali Ali Karami], [http://dblp.uni-trier.de/pers/hd/k/Khunjush:Farshad Farshad Khunjush] ('''2013'''). ''[https://scholar.google.de/citations?view_op=view_citation&hl=en&user=VvkRESgAAAAJ&citation_for_view=VvkRESgAAAAJ:ufrVoPGSRksC A parallel memetic algorithm on GPU to solve the task scheduling problem in heterogeneous environments]''. [http://www.sigevo.org/gecco-2013/program.html GECCO '13], [https://www.lri.fr/~hansen/proceedings/2013/GECCO/proceedings/p1181.pdf pdf]
 
'''2014'''
 
'''2014'''
* [[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]], [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 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>
 
* [[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 14:43, 27 August 2018

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.

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 ....

  • Ryszard Michalski (2000). LEARNABLE EVOLUTION MODEL: Evolutionary Processes Guided by Machine Learning. Machine Learning 38 [5]

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

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