Difference between revisions of "Genetic Programming"

From Chessprogramming wiki
Jump to: navigation, search
 
(6 intermediate revisions by the same user not shown)
Line 45: Line 45:
 
* [[Dynamic Programming]]
 
* [[Dynamic Programming]]
 
* [[Falcon#GA|GA in Falcon]]
 
* [[Falcon#GA|GA in Falcon]]
 +
* [[David E. Moriarty#SANE|SANE]]
 
* [[Simulated Annealing]]
 
* [[Simulated Annealing]]
 
* [[Trial and Error]]
 
* [[Trial and Error]]
Line 76: Line 77:
 
* [[Deniz Yuret]] ('''1994'''). ''[http://home.ku.edu.tr/%7Edyuret/pub/aitr1569/index.html From Genetic Algorithms To Efficient Optimization]''. Ms.C. Thesis, Supervisor: [[Patrick Winston|Patrick Henry Winston]]
 
* [[Deniz Yuret]] ('''1994'''). ''[http://home.ku.edu.tr/%7Edyuret/pub/aitr1569/index.html From Genetic Algorithms To Efficient Optimization]''. Ms.C. Thesis, Supervisor: [[Patrick Winston|Patrick Henry Winston]]
 
* [[Kurt Thearling]], [https://en.wikipedia.org/wiki/Thomas_S._Ray Thomas S. Ray] ('''1994'''). ''[http://www.thearling.com/text/alife4/alife4.htm Evolving Multi-cellular Artificial Life]''. [http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=8335 Artificial Life IV], [https://en.wikipedia.org/wiki/Rodney_Brooks R. Brooks] and [http://web.media.mit.edu/%7Epattie/ P. Maes] (eds.), [https://en.wikipedia.org/wiki/MIT_Press MIT Press]
 
* [[Kurt Thearling]], [https://en.wikipedia.org/wiki/Thomas_S._Ray Thomas S. Ray] ('''1994'''). ''[http://www.thearling.com/text/alife4/alife4.htm Evolving Multi-cellular Artificial Life]''. [http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=8335 Artificial Life IV], [https://en.wikipedia.org/wiki/Rodney_Brooks R. Brooks] and [http://web.media.mit.edu/%7Epattie/ P. Maes] (eds.), [https://en.wikipedia.org/wiki/MIT_Press MIT Press]
* [[David E. Moriarty]], [[Risto Miikkulainen]] ('''1994'''). ''Evolving Neural Networks to focus Minimax Search''. [[AAAI|AAAI-94]], [http://www.cs.utexas.edu/~ai-lab/pubs/moriarty.focus.pdf pdf]
+
* [[David E. Moriarty]], [[Risto Miikkulainen]] ('''1994'''). ''[http://nn.cs.utexas.edu/?moriarty:aaai94 Evolving Neural Networks to focus Minimax Search]''. [[Conferences#AAAI-94|AAAI-94]] » [[Othello]]
 
==1995 ...==
 
==1995 ...==
 +
* [[David E. Moriarty]], [[Risto Miikkulainen]] ('''1995'''). ''[http://nn.cs.utexas.edu/?moriarty:connsci95 Discovering Complex Othello Strategies Through Evolutionary Neural Networks]''. [https://www.scimagojr.com/journalsearch.php?q=24173&tip=sid Connection Science], Vol. 7
 
* [[Omar Syed]] ('''1995'''). ''[http://arimaa.com/arimaa/about/Thesis/ Applying Genetic Algorithms to Recurrent Neural Networks for Learning Network Parameters and Architecture]'', Masters Thesis, [https://en.wikipedia.org/wiki/Case_Western_Reserve_University Case Western Reserve University]
 
* [[Omar Syed]] ('''1995'''). ''[http://arimaa.com/arimaa/about/Thesis/ Applying Genetic Algorithms to Recurrent Neural Networks for Learning Network Parameters and Architecture]'', Masters Thesis, [https://en.wikipedia.org/wiki/Case_Western_Reserve_University Case Western Reserve University]
 
* [[Eric B. Baum]], [https://en.wikipedia.org/wiki/Dan_Boneh Dan Boneh], [[Charles Garrett]] ('''1995'''). ''[http://dl.acm.org/citation.cfm?id=225326 On Genetic Algorithms]''. [http://dblp.uni-trier.de/db/conf/colt/colt1995.html#BaumBG95 COLT 1995]
 
* [[Eric B. Baum]], [https://en.wikipedia.org/wiki/Dan_Boneh Dan Boneh], [[Charles Garrett]] ('''1995'''). ''[http://dl.acm.org/citation.cfm?id=225326 On Genetic Algorithms]''. [http://dblp.uni-trier.de/db/conf/colt/colt1995.html#BaumBG95 COLT 1995]
Line 181: Line 183:
 
* [[Krzysztof Krawiec]], [[Wojciech Jaśkowski]], [[Marcin Szubert]] ('''2011'''). ''[http://www.degruyter.com/view/j/amcs.2011.21.issue-4/v10006-011-0057-3/v10006-011-0057-3.xml Evolving small-board Go players using Coevolutionary Temporal Difference Learning with Archives]''. [http://www.degruyter.com/view/j/amcs Applied Mathematics and Computer Science], Vol. 21, No. 4
 
* [[Krzysztof Krawiec]], [[Wojciech Jaśkowski]], [[Marcin Szubert]] ('''2011'''). ''[http://www.degruyter.com/view/j/amcs.2011.21.issue-4/v10006-011-0057-3/v10006-011-0057-3.xml Evolving small-board Go players using Coevolutionary Temporal Difference Learning with Archives]''. [http://www.degruyter.com/view/j/amcs Applied Mathematics and Computer Science], Vol. 21, No. 4
 
* [[Moshe Sipper]] ('''2011'''). ''[http://www.moshesipper.com/etw/ Evolved to Win]''. [https://en.wikipedia.org/wiki/Lulu_%28company%29 Lulu]
 
* [[Moshe Sipper]] ('''2011'''). ''[http://www.moshesipper.com/etw/ Evolved to Win]''. [https://en.wikipedia.org/wiki/Lulu_%28company%29 Lulu]
 +
* [[Alan J. Lockett]], [[Risto Miikkulainen]] ('''2011'''). ''[http://www.cs.utexas.edu/users/ai-lab/?lockett:gecco11 Real-Space Evolutionary Annealing]''. [https://dblp.uni-trier.de/db/conf/gecco/gecco2011.html GECCO 2011]
 
'''2012'''
 
'''2012'''
 
* [http://www.informatik.uni-trier.de/~ley/pers/hd/o/Orlov:Michael.html Michael Orlov], [[Moshe Sipper]], [[Ami Hauptman]] ('''2012'''). ''[http://link.springer.com/content/pdf/10.1007/978-1-4614-1800-9_81.pdf Genetic and evolutionary algorithms and programming: General introduction and application to game playing]''. [http://www.springer.com/birkhauser/computer+science/journal/37 Computational Complexity], [https://en.wikipedia.org/wiki/Springer_Publishing Springer New York]
 
* [http://www.informatik.uni-trier.de/~ley/pers/hd/o/Orlov:Michael.html Michael Orlov], [[Moshe Sipper]], [[Ami Hauptman]] ('''2012'''). ''[http://link.springer.com/content/pdf/10.1007/978-1-4614-1800-9_81.pdf Genetic and evolutionary algorithms and programming: General introduction and application to game playing]''. [http://www.springer.com/birkhauser/computer+science/journal/37 Computational Complexity], [https://en.wikipedia.org/wiki/Springer_Publishing Springer New York]
Line 188: Line 191:
 
* [[Ilya Loshchilov]], [[Marc Schoenauer]], [[Michèle Sebag]] ('''2012'''). ''Self-Adaptive Surrogate-Assisted Covariance Matrix Adaptation Evolution Strategy''. [https://arxiv.org/abs/1204.2356 arXiv:1204.2356]
 
* [[Ilya Loshchilov]], [[Marc Schoenauer]], [[Michèle Sebag]] ('''2012'''). ''Self-Adaptive Surrogate-Assisted Covariance Matrix Adaptation Evolution Strategy''. [https://arxiv.org/abs/1204.2356 arXiv:1204.2356]
 
* [[Ilya Loshchilov]], [[Marc Schoenauer]], [[Michèle Sebag]] ('''2012'''). ''Alternative Restart Strategies for CMA-ES''. [https://arxiv.org/abs/1207.0206 arXiv:1207.0206]  
 
* [[Ilya Loshchilov]], [[Marc Schoenauer]], [[Michèle Sebag]] ('''2012'''). ''Alternative Restart Strategies for CMA-ES''. [https://arxiv.org/abs/1207.0206 arXiv:1207.0206]  
 +
* [[Alan J. Lockett]] ('''2012'''). ''General-Purpose Optimization Through Information Maximization''. Ph.D. thesis, [https://en.wikipedia.org/wiki/University_of_Texas_at_Austin University of Texas at Austin], advisor [[Risto Miikkulainen]], [http://www.alockett.com/static/pdf/lockett-thesis.pdf pdf]
 
'''2013'''
 
'''2013'''
 
* [[Marcin Szubert]], [[Wojciech Jaśkowski]], [[Krzysztof Krawiec]] ('''2013'''). ''[http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6504736 On Scalability, Generalization, and Hybridization of Coevolutionary Learning: a Case Study for Othello]''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 5, No. 3 » [[Othello]]
 
* [[Marcin Szubert]], [[Wojciech Jaśkowski]], [[Krzysztof Krawiec]] ('''2013'''). ''[http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6504736 On Scalability, Generalization, and Hybridization of Coevolutionary Learning: a Case Study for Othello]''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 5, No. 3 » [[Othello]]
Line 202: Line 206:
 
* [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]
 
* [[Rahul Aralikatte]] ('''2014'''). ''Phoenix : A Self Learning Chess Engine''. for the Award of M. Tech in Information Technology, [https://en.wikipedia.org/wiki/International_Institute_of_Information_Technology,_Bangalore International Institute of Information Technology, Bangalore], [https://en.wikipedia.org/wiki/Bangalore Bangalore], advisor [[Gopalakrishnan Srinivasaraghavan|G. Srinivasaraghavan]], [https://github.com/rahular/phoenix/blob/master/docs/ThesisReport.pdf pdf] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55476&start=4 Re: PHOENIX=CuckooChess with learning function in Falcon style] by [[Peter Österlund]], [[CCC]], March 20, 2016</ref>
 
* [[Rahul Aralikatte]] ('''2014'''). ''Phoenix : A Self Learning Chess Engine''. for the Award of M. Tech in Information Technology, [https://en.wikipedia.org/wiki/International_Institute_of_Information_Technology,_Bangalore International Institute of Information Technology, Bangalore], [https://en.wikipedia.org/wiki/Bangalore Bangalore], advisor [[Gopalakrishnan Srinivasaraghavan|G. Srinivasaraghavan]], [https://github.com/rahular/phoenix/blob/master/docs/ThesisReport.pdf pdf] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55476&start=4 Re: PHOENIX=CuckooChess with learning function in Falcon style] by [[Peter Österlund]], [[CCC]], March 20, 2016</ref>
 +
* [[Alan J. Lockett]], [[Risto Miikkulainen]] ('''2014'''). ''[http://nn.cs.utexas.edu/?lockett:jogo13 Evolutionary Annealing: Global Optimization in Arbitrary Measure Spaces]''. [https://www.springer.com/journal/10898 Journal of Global Optimization], Vol. 58
 +
* [[Simon Lucas]], [[Spyridon Samothrakis]], [[Diego Perez]] ('''2014'''). ''[https://link.springer.com/chapter/10.1007/978-3-662-45523-4_29 Fast Evolutionary Adaptation for Monte Carlo Tree Search]''. [https://dblp.uni-trier.de/db/conf/evoW/evoappl2014.html EvoApplications 2014], [http://www.diego-perez.net/papers/FastEvoMCTS.pdf pdf]
 
==2015 ...==
 
==2015 ...==
 
* [[Rahul Aralikatte]], [[Gopalakrishnan Srinivasaraghavan|G. Srinivasaraghavan]] ('''2016'''). ''Phoenix: A Self-Optimizing Chess Engine''. [http://arxiv.org/abs/1603.09051 arXiv:1603.09051]
 
* [[Rahul Aralikatte]], [[Gopalakrishnan Srinivasaraghavan|G. Srinivasaraghavan]] ('''2016'''). ''Phoenix: A Self-Optimizing Chess Engine''. [http://arxiv.org/abs/1603.09051 arXiv:1603.09051]
Line 226: Line 232:
 
* [http://www.talkchess.com/forum/viewtopic.php?t=59738 Genetical learning (again)] by [[Stefano Gemma]], [[CCC]], April 03, 2016
 
* [http://www.talkchess.com/forum/viewtopic.php?t=59738 Genetical learning (again)] by [[Stefano Gemma]], [[CCC]], April 03, 2016
 
* [http://www.talkchess.com/forum/viewtopic.php?t=66105 Genetic optimization re-started] by [[Stefano Gemma]], December 23, 2017
 
* [http://www.talkchess.com/forum/viewtopic.php?t=66105 Genetic optimization re-started] by [[Stefano Gemma]], December 23, 2017
 +
==2020 ...==
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=75342 Determining evaluation by a genetic algorithm] by [[Marcel Vanthoor]], [[CCC]], October 09, 2020
  
 
=External Links=  
 
=External Links=  
Line 234: Line 242:
 
* [https://en.wikipedia.org/wiki/Gene Gene from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Gene Gene from Wikipedia]
 
* [http://www.geneticprogramming.com/Tutorial/ The GP Tutorial]
 
* [http://www.geneticprogramming.com/Tutorial/ The GP Tutorial]
 +
* [https://en.wikipedia.org/wiki/Cartesian_genetic_programming Cartesian genetic programming from Wikipedia]
 +
* [https://github.com/connormcmonigle/cartesian-gp-chess-engine GitHub - connormcmonigle/cartesian-gp-chess-engine: Experiment involving evolving cartesian genetic programs to evaluate chess positions] by [[Connor McMonigle]]
 
==Evolutionary Programming==
 
==Evolutionary Programming==
 
* [https://en.wikipedia.org/wiki/Evolutionary_programming Evolutionary programming from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Evolutionary_programming Evolutionary programming from Wikipedia]

Latest revision as of 00:06, 8 December 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

2020 ...

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