Difference between revisions of "Genetic Programming"

From Chessprogramming wiki
Jump to: navigation, search
Line 62: Line 62:
 
* [[John Maynard Smith]] ('''1982'''). ''[https://en.wikipedia.org/wiki/Evolution_and_the_Theory_of_Games Evolution and the Theory of Games]''. Cambridge; New York, Cambridge University Press.
 
* [[John Maynard Smith]] ('''1982'''). ''[https://en.wikipedia.org/wiki/Evolution_and_the_Theory_of_Games Evolution and the Theory of Games]''. Cambridge; New York, Cambridge University Press.
 
* [[Mathematician#RAxelrod|Robert Axelrod]] ('''1987'''). ''The Evolution of Strategies in the Iterated Prisoner’s Dilemma''. in [http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/LawrenceDavidDavis.html Lawrence D. Davis] (ed.) ''[http://dl.acm.org/citation.cfm?id=535531 Genetic Algorithms and Simulated Annealing]''. [http://www-personal.umich.edu/~axe/research/Evolving.pdf 2001 reprint as pdf] <ref>[https://en.wikipedia.org/wiki/Prisoner%27s_dilemma Prisoner's dilemma from Wikipedia]</ref>
 
* [[Mathematician#RAxelrod|Robert Axelrod]] ('''1987'''). ''The Evolution of Strategies in the Iterated Prisoner’s Dilemma''. in [http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/LawrenceDavidDavis.html Lawrence D. Davis] (ed.) ''[http://dl.acm.org/citation.cfm?id=535531 Genetic Algorithms and Simulated Annealing]''. [http://www-personal.umich.edu/~axe/research/Evolving.pdf 2001 reprint as pdf] <ref>[https://en.wikipedia.org/wiki/Prisoner%27s_dilemma Prisoner's dilemma from Wikipedia]</ref>
* [[David E. Goldberg]], [[Mathematician#Holland|John H. Holland]] ('''1988'''). ''[http://www.springerlink.com/content/rw3572714v41q507/ Genetic Algorithms and Machine Learning]''. [http://www.informatik.uni-trier.de/~ley/db/journals/ml/ml3.html#GoldbergH88 Machine Learning 3], [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Kluwer Academic Publishers]
+
* [[David E. Goldberg]], [[Mathematician#Holland|John H. Holland]] ('''1988'''). ''[https://link.springer.com/article/10.1023/A:1022602019183 Genetic Algorithms and Machine Learning]''. [https://www.springer.com/journal/10994 Machine Learning], Vol. 3
* [[David E. Goldberg]] ('''1989'''). ''Genetic algorithms in search, optimization, and machine learning''. [https://en.wikipedia.org/wiki/Addison-Wesley Addison-Wesley]. [http://www.amazon.com/Genetic-Algorithms-Optimization-Machine-Learning/dp/0201157675 amazon.com]
+
* [[David E. Goldberg]] ('''1989'''). ''Genetic Algorithms in Search, Optimization and Machine Learning''. [https://en.wikipedia.org/wiki/Addison-Wesley Addison-Wesley]
 
* [[John Maynard Smith]] ('''1989'''). ''Evolutionary Genetics''. Oxford; New York, Oxford University Press.
 
* [[John Maynard Smith]] ('''1989'''). ''Evolutionary Genetics''. Oxford; New York, Oxford University Press.
 
* [[Greg M. Gupton]] ('''1989'''). ''Genetic Learning Algorithm Applied to the Game of Othello''. [[1st Computer Olympiad#Workshop|Heuristic Programming in AI 1]]
 
* [[Greg M. Gupton]] ('''1989'''). ''Genetic Learning Algorithm Applied to the Game of Othello''. [[1st Computer Olympiad#Workshop|Heuristic Programming in AI 1]]
 
==1990 ...==  
 
==1990 ...==  
 
* [https://en.wikipedia.org/wiki/John_Koza John Koza] ('''1990'''). ''Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems''. Stanford University Computer Science Department technical report STAN-CS-90-1314, [http://www.genetic-programming.com/jkpdf/tr1314.pdf pdf]
 
* [https://en.wikipedia.org/wiki/John_Koza John Koza] ('''1990'''). ''Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems''. Stanford University Computer Science Department technical report STAN-CS-90-1314, [http://www.genetic-programming.com/jkpdf/tr1314.pdf pdf]
* [[David E. Goldberg]] ('''1991'''). ''Real-coded genetic algorithms. Virtual alphabets, and blocking''. Complex Systems 5, pp. 139–167. [http://www.complex-systems.com/pdf/05-2-2.pdf pdf]
+
* [[David E. Goldberg]] ('''1991'''). ''[https://www.complex-systems.com/abstracts/v05_i02_a02/ Real-coded Genetic Algorithms, Virtual Alphabets, and Blocking]''. [https://en.wikipedia.org/wiki/Complex_Systems_(journal) Complex Systems], Vol. 5, No. 2
 
* [[William Tunstall-Pedoe]] ('''1991'''). ''Genetic Algorithms Optimizing Evaluation Functions''. [[ICGA Journal#14_3|ICCA Journal, Vol. 14, No. 3]]
 
* [[William Tunstall-Pedoe]] ('''1991'''). ''Genetic Algorithms Optimizing Evaluation Functions''. [[ICGA Journal#14_3|ICCA Journal, Vol. 14, No. 3]]
 
* [https://en.wikipedia.org/wiki/John_Koza John Koza] ('''1992'''). ''Genetic Programming: On the Programming of Computers by Means of Natural Selection''. [https://en.wikipedia.org/wiki/MIT_Press MIT Press], [https://en.wikipedia.org/wiki/Special:BookSources/0262111705 ISBN 0-262-11170-5]
 
* [https://en.wikipedia.org/wiki/John_Koza John Koza] ('''1992'''). ''Genetic Programming: On the Programming of Computers by Means of Natural Selection''. [https://en.wikipedia.org/wiki/MIT_Press MIT Press], [https://en.wikipedia.org/wiki/Special:BookSources/0262111705 ISBN 0-262-11170-5]
Line 102: Line 102:
 
'''2002'''
 
'''2002'''
 
* [[Yngvi Björnsson]], [[Tony Marsland]] ('''2002'''). ''Learning Control of Search Extensions''. Proceedings of the 6th Joint Conference on Information Sciences (JCIS 2002), pp. 446-449. [http://www.ru.is/faculty/yngvi/pdf/BjornssonM02.pdf pdf]
 
* [[Yngvi Björnsson]], [[Tony Marsland]] ('''2002'''). ''Learning Control of Search Extensions''. Proceedings of the 6th Joint Conference on Information Sciences (JCIS 2002), pp. 446-449. [http://www.ru.is/faculty/yngvi/pdf/BjornssonM02.pdf pdf]
* [[David E. Goldberg]] ('''2002'''). ''The design of innovation: Lessons from and for competent genetic algorithms''. [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Kluwer Academic Publishers], [http://books.google.com/books/about/The_design_of_innovation.html?id=DGBxj3z5mi4C google books], [http://www.amazon.com/Innovation-Genetic-Algorithms-Evolutionary-Computation/dp/1402070985 amazon.com]
+
* [[David E. Goldberg]] ('''2002'''). ''[https://www.springer.com/gp/book/9781475736458 The Design of Innovation: Lessons from and for Competent Genetic Algorithms]''. [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Kluwer Academic Publishers]
 
* [[Roderich Groß]], [[Keno Albrecht]], [[Wolfgang Kantschik]], [[Wolfgang Banzhaf]] ('''2002'''). ''Evolving Chess Playing Programs''. [http://www.informatik.uni-trier.de/~ley/db/conf/gecco/gecco2002.html#GrossAKB02 GECCO 2002], [http://naturalrobotics.group.shef.ac.uk/publications/gecco02.pdf pdf]
 
* [[Roderich Groß]], [[Keno Albrecht]], [[Wolfgang Kantschik]], [[Wolfgang Banzhaf]] ('''2002'''). ''Evolving Chess Playing Programs''. [http://www.informatik.uni-trier.de/~ley/db/conf/gecco/gecco2002.html#GrossAKB02 GECCO 2002], [http://naturalrobotics.group.shef.ac.uk/publications/gecco02.pdf pdf]
 
* [[Krzysztof Krawiec]] ('''2002'''). ''[http://link.springer.com/article/10.1023/A:1020984725014 Genetic Programming-based Construction of Features for Machine Learning and Knowledge Discovery Tasks]''. [http://www.informatik.uni-trier.de/~ley/db/journals/gpem/gpem3.html#Krawiec02 Genetic Programming and Evolvable Machines, Vol. 3], No. 4
 
* [[Krzysztof Krawiec]] ('''2002'''). ''[http://link.springer.com/article/10.1023/A:1020984725014 Genetic Programming-based Construction of Features for Machine Learning and Knowledge Discovery Tasks]''. [http://www.informatik.uni-trier.de/~ley/db/journals/gpem/gpem3.html#Krawiec02 Genetic Programming and Evolvable Machines, Vol. 3], No. 4
Line 123: Line 123:
 
* [[Ami Hauptman]], [[Moshe Sipper]] ('''2005'''). ''GP-EndChess: Using Genetic Programming to Evolve Chess Endgame Players''. [http://www.informatik.uni-trier.de/~ley/db/conf/eurogp/eurogp2005.html#HauptmanS05 EuroGP 2005], [http://www.cs.bgu.ac.il/~sipper/papabs/eurogpchess-final.pdf pdf]
 
* [[Ami Hauptman]], [[Moshe Sipper]] ('''2005'''). ''GP-EndChess: Using Genetic Programming to Evolve Chess Endgame Players''. [http://www.informatik.uni-trier.de/~ley/db/conf/eurogp/eurogp2005.html#HauptmanS05 EuroGP 2005], [http://www.cs.bgu.ac.il/~sipper/papabs/eurogpchess-final.pdf pdf]
 
* [[David B. Fogel]], [[Timothy J. Hays]], [[Sarah L. Hahn]], [[James Quon]] ('''2005'''). ''Further Evolution of a Self-Learning Chess Program''. [[IEEE#CIG|IEEE Symposium on Computational Intelligence & Games]], [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.5288 CiteSeerX]
 
* [[David B. Fogel]], [[Timothy J. Hays]], [[Sarah L. Hahn]], [[James Quon]] ('''2005'''). ''Further Evolution of a Self-Learning Chess Program''. [[IEEE#CIG|IEEE Symposium on Computational Intelligence & Games]], [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.5288 CiteSeerX]
* [http://www.linkedin.com/in/kumarasastry Kumara Sastry], [[David E. Goldberg]], [[Graham Kendall]] ('''2005'''). ''[http://link.springer.com/chapter/10.1007/0-387-28356-0_4 Genetic algorithms]''. Search Methodologies, [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
+
* [https://dblp.uni-trier.de/pers/hd/s/Sastry:Kumara Kumara Sastry], [[David E. Goldberg]], [[Graham Kendall]] ('''2005'''). ''[https://link.springer.com/chapter/10.1007/0-387-28356-0_4 Genetic Algorithms]''. [https://link.springer.com/book/10.1007/0-387-28356-0 Search Methodologies], [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
 
* [[Kokolo Ikeda]] ('''2005'''). ''Exemplar-based direct policy search with evolutionary optimization''. [http://www.informatik.uni-trier.de/~ley/db/conf/cec/cec2005.html#Ikeda05 CEC 2005]
 
* [[Kokolo Ikeda]] ('''2005'''). ''Exemplar-based direct policy search with evolutionary optimization''. [http://www.informatik.uni-trier.de/~ley/db/conf/cec/cec2005.html#Ikeda05 CEC 2005]
 
* [[Thomas Philip Runarsson]],  [[Mathematician#XYao|Xin Yao]] ('''2005'''). ''Search biases in constrained evolutionary optimization''. [[IEEE#SMC|IEEE Transactions on Systems, Man, and Cybernetics]], Vol. 35, No. 2, [https://www.researchgate.net/profile/Thomas_Runarsson/publication/3421612_Search_Biases_in_Constrained_Evolutionary_Optimization/links/543fa8810cf21227a11a4b5d.pdf pdf]
 
* [[Thomas Philip Runarsson]],  [[Mathematician#XYao|Xin Yao]] ('''2005'''). ''Search biases in constrained evolutionary optimization''. [[IEEE#SMC|IEEE Transactions on Systems, Man, and Cybernetics]], Vol. 35, No. 2, [https://www.researchgate.net/profile/Thomas_Runarsson/publication/3421612_Search_Biases_in_Constrained_Evolutionary_Optimization/links/543fa8810cf21227a11a4b5d.pdf pdf]

Revision as of 22:59, 28 March 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