P. Vitanyi. Theoretical Computer Science, 241 (1--2):
3--23(28 June 2000)
Аннотация
Genetic fitness optimization using small populations
or small population updates across generations
generally suffers from randomly diverging evolutions.
We propose a notion of highly probable fitness
optimization through feasible evolutionary computing
runs on small size populations. Based on rapidly mixing
Markov chains, the approach pertains to most types of
evolutionary genetic algorithms, genetic programming
and the like. We establish that for systems having
associated rapidly mixing Markov chains and appropriate
stationary distributions the new method finds optimal
programs (individuals) with probability almost 1. To
make the method useful would require a structured
design methodology where the development of the program
and the guarantee of the rapidly mixing property go
hand in hand. We analyze a simple example to show that
the method is implementable. More significant examples
require theoretical advances, for example with respect
to the Metropolis filter.
%0 Journal Article
%1 Vitanyi:2000:DEP
%A Vitanyi, Paul
%D 2000
%J Theoretical Computer Science
%K Algorithms, Artificial Complexity, Computational Computing, Data Evolutionary Intelligence, Learning, Multiagent Neural Structures Systems algorithms, and genetic programming,
%N 1--2
%P 3--23
%T A discipline of evolutionary programming
%U http://www.elsevier.nl/gej-ng/10/41/16/175/21/22/article.pdf
%V 241
%X Genetic fitness optimization using small populations
or small population updates across generations
generally suffers from randomly diverging evolutions.
We propose a notion of highly probable fitness
optimization through feasible evolutionary computing
runs on small size populations. Based on rapidly mixing
Markov chains, the approach pertains to most types of
evolutionary genetic algorithms, genetic programming
and the like. We establish that for systems having
associated rapidly mixing Markov chains and appropriate
stationary distributions the new method finds optimal
programs (individuals) with probability almost 1. To
make the method useful would require a structured
design methodology where the development of the program
and the guarantee of the rapidly mixing property go
hand in hand. We analyze a simple example to show that
the method is implementable. More significant examples
require theoretical advances, for example with respect
to the Metropolis filter.
@article{Vitanyi:2000:DEP,
abstract = {Genetic fitness optimization using small populations
or small population updates across generations
generally suffers from randomly diverging evolutions.
We propose a notion of highly probable fitness
optimization through feasible evolutionary computing
runs on small size populations. Based on rapidly mixing
Markov chains, the approach pertains to most types of
evolutionary genetic algorithms, genetic programming
and the like. We establish that for systems having
associated rapidly mixing Markov chains and appropriate
stationary distributions the new method finds optimal
programs (individuals) with probability almost 1. To
make the method useful would require a structured
design methodology where the development of the program
and the guarantee of the rapidly mixing property go
hand in hand. We analyze a simple example to show that
the method is implementable. More significant examples
require theoretical advances, for example with respect
to the Metropolis filter.},
added-at = {2008-06-19T17:46:40.000+0200},
author = {Vitanyi, Paul},
bibdate = {Tue Oct 31 11:38:29 MST 2000},
biburl = {https://www.bibsonomy.org/bibtex/23c6e75e2c0433cd977a2a9c60c559af4/brazovayeye},
coden = {TCSCDI},
interhash = {1741a5b71165a30600f9cbcb38e4ee6a},
intrahash = {3c6e75e2c0433cd977a2a9c60c559af4},
issn = {0304-3975},
journal = {Theoretical Computer Science},
keywords = {Algorithms, Artificial Complexity, Computational Computing, Data Evolutionary Intelligence, Learning, Multiagent Neural Structures Systems algorithms, and genetic programming,},
month = {28 June},
notes = {Update of \cite{alt96*67} Presented at Dagstuhl Feb
2004. Generic to evolutionary computation, rather than
specifically on GP.},
number = {1--2},
pages = {3--23},
size = {21 pages},
timestamp = {2008-06-19T17:53:41.000+0200},
title = {A discipline of evolutionary programming},
url = {http://www.elsevier.nl/gej-ng/10/41/16/175/21/22/article.pdf},
volume = 241,
year = 2000
}