Cited By
View all- Mitavskiy BTuci ECannings CRowe JHe J(2013)Geiringer theoremsNatural Computing: an international journal10.1007/s11047-013-9395-412:4(473-484)Online publication date: 1-Dec-2013
A further generalization of the finite-population geiringer-like theorem for pomdps to allow recombination overarbitrary set covers
Pages 133 - 146
Abstract
A popular current research trend deals with expanding the Monte-Carlo tree search sampling methodologies to the environments with uncertainty and incomplete information. Recently a finite population version of Geiringer theorem with nonhomologous recombination has been adopted to the setting of Monte-Carlo tree search to cope with randomness and incomplete information by exploiting the entrinsic similarities within the state space of the problem. The only limitation of the new theorem is that the similarity relation was assumed to be an equivalence relation on the set of states. In the current paper we lift this "curtain of limitation" by allowing the similarity relation to be modeled in terms of an arbitrary set cover of the set of state-action pairs.
Supplementary Material
The compressed file that's attached contains the eps images of the diagrams that appear in the paper.
- Download
- 816.19 KB
References
[1]
J. Antonisse. A new interpretation of schema notation that overturns the binary encoding constraint. In Procedings of the Third International Conference on Genetic Algorithms.
[2]
Chaslot, Saito, Bouzy, Uiterwijk, and van den Herik. Monte-carlo strategies for computer go. In Procedings of the 18th Belgian-Dutch Conference on Artificial Intelligence.
[3]
H. Geiringer. On the probability of linkage in mendelian heredity. Annals of Mathematical Statistics, 15.
[4]
Kee-Eung. Exploiting symmetries in pomdps for point-based algorithms. In Proceedings of the 23rd national conference on Artificial intelligence.
[5]
B. Mitavskiy and J. Rowe. An extension of geiringer theorem for a wide class of evolutionary algorithms. Evolutionary Computation, 14(1):87--118.
[6]
B. Mitavskiy and J. Rowe. A schema-based version of geiringer theorem for nonlinear genetic programming with homologous crossover. In Foundations of Genetic Algorithms 8 (FOGA-2005), pages 156--175. Springer, lecture Notes in Computer Science 3469.
[7]
B. Mitavskiy, J. Rowe, and C. Cannings. A version of geiringer-like theorem for decision making in the environments with randomness and incomplete information. International Journal of Intelligent Computing and Cybernetics, 5(1):36--90.
[8]
R. Poli and B. Langdon. Schema theory for genetic programming with one-point crossover and point mutation. Evolutionary Computation, 6(3):231--252.
[9]
S. C. W. A. Poli, R. and J. Rowe. A schema theory based extension of geiringer's theorem for linear gp and variable length gas under homologous crossover. In Foundations of Genetic Algorithms 7 (FOGA-2003).
[10]
L. Schmitt. Theory of genetic algorithms. Theoretical Computer Science, 259.
[11]
L. Schmitt. Theory of genetic algorithms. Theoretical Computer Science, 310.
[12]
G. Simmons. Introduction to Topology and Modern Analysis. R.E. Krieger Pub. Co.
[13]
M. Vose. The simple genetic algorithm: foundations and theory. MIT Press.
Index Terms
- A further generalization of the finite-population geiringer-like theorem for pomdps to allow recombination overarbitrary set covers
Recommendations
Geiringer theorems: from population genetics to computational intelligence, memory evolutive systems and Hebbian learning
The classical Geiringer theorem addresses the limiting frequency of occurrence of various alleles after repeated application of crossover. It has been adopted to the setting of evolutionary algorithms and, a lot more recently, reinforcement learning and ...
Some results about the Markov chains associated to GPs and general EAs
Foundations of genetic algorithmsGeiringer's theorem is a statement which tells us something about the limiting frequency of occurrence of a certain individual when a classical genetic algorithm is executed in the absence of selection and mutation. Recently Poll, Stephens, Wright and ...
On Near Optimality of the Set of Finite-State Controllers for Average Cost POMDP
We consider the average cost problem for partially observable Markov decision processes (POMDP) with finite state, observation, and control spaces. We prove that there exists an ε-optimal finite-state controller (FSC) functionally independent of initial ...
Comments
Information & Contributors
Information
Published In
January 2013
198 pages
Copyright © 2013 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: 16 January 2013
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
FOGA '13
Sponsor:
Acceptance Rates
Overall Acceptance Rate 72 of 131 submissions, 55%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 46Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 03 Mar 2025
Other Metrics
Citations
Cited By
View all- Mitavskiy BTuci ECannings CRowe JHe J(2013)Geiringer theoremsNatural Computing: an international journal10.1007/s11047-013-9395-412:4(473-484)Online publication date: 1-Dec-2013
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in