Genetic Fitness Optimization Using Rapidly Mixing
Markov Chains
P. Vitanyi. technical report, NC-TR-005. NeuroCOLT, Computer Science, Royal Holloway, Egham, Surrey,
England, (February 1997)
Abstract
A notion of highly probable fitness optimization
through evolutionary computing runs on small size
populations in a very general setting is proposed. This
has applications to evolutionary learning. Based on
rapidly mixing Markov chains, the approach pertains to
most types of evolutionary genetic algorithms, genetic
programming and the like. For systems having associated
rapidly mixing Markov chains and appropriate stationary
distributions the new method finds optimal programs
(individuals) with probability almost 1.
Algorithmically, the novel approach prescribes a
strategy of executing many short computation runs,
rather than one long computation run. Given an
arbitrary evolutionary program it may be infeasible to
determine whether its associated matrix is rapidly
mixing. In our proposed structured evolutionary program
discipline, the development of the program and the
guaranty of the rapidly mixing property go hand in
hand. We conclude with a tentative toy example.
%0 Report
%1 vitanyi:1997:gfourmmc
%A Vitanyi, Paul
%C Computer Science, Royal Holloway, Egham, Surrey,
England
%D 1997
%K computation evolutionary
%N NC-TR-005
%T Genetic Fitness Optimization Using Rapidly Mixing
Markov Chains
%U http://www.neurocolt.com/abs/1997/abs97005.html
%X A notion of highly probable fitness optimization
through evolutionary computing runs on small size
populations in a very general setting is proposed. This
has applications to evolutionary learning. Based on
rapidly mixing Markov chains, the approach pertains to
most types of evolutionary genetic algorithms, genetic
programming and the like. For systems having associated
rapidly mixing Markov chains and appropriate stationary
distributions the new method finds optimal programs
(individuals) with probability almost 1.
Algorithmically, the novel approach prescribes a
strategy of executing many short computation runs,
rather than one long computation run. Given an
arbitrary evolutionary program it may be infeasible to
determine whether its associated matrix is rapidly
mixing. In our proposed structured evolutionary program
discipline, the development of the program and the
guaranty of the rapidly mixing property go hand in
hand. We conclude with a tentative toy example.
@techreport{vitanyi:1997:gfourmmc,
abstract = {A notion of highly probable fitness optimization
through evolutionary computing runs on small size
populations in a very general setting is proposed. This
has applications to evolutionary learning. Based on
rapidly mixing Markov chains, the approach pertains to
most types of evolutionary genetic algorithms, genetic
programming and the like. For systems having associated
rapidly mixing Markov chains and appropriate stationary
distributions the new method finds optimal programs
(individuals) with probability almost 1.
Algorithmically, the novel approach prescribes a
strategy of executing many short computation runs,
rather than one long computation run. Given an
arbitrary evolutionary program it may be infeasible to
determine whether its associated matrix is rapidly
mixing. In our proposed structured evolutionary program
discipline, the development of the program and the
guaranty of the rapidly mixing property go hand in
hand. We conclude with a tentative toy example.},
added-at = {2008-06-19T17:46:40.000+0200},
address = {Computer Science, Royal Holloway, Egham, Surrey,
England},
author = {Vitanyi, Paul},
biburl = {https://www.bibsonomy.org/bibtex/22eaf8620b682c12d878e74029d6bcefd/brazovayeye},
email = {neurocolt@dcs.rhbnc.ac.uk},
institution = {NeuroCOLT},
interhash = {6a0f7bf7c50838051cf85db2cd5d3975},
intrahash = {2eaf8620b682c12d878e74029d6bcefd},
keywords = {computation evolutionary},
month = {February},
notes = {See also \cite{alt96*67} and \cite{Vitanyi:2000:DEP}
Although refers several time to GP, approach is
evolutionary as a whole, ie not just GP},
number = {NC-TR-005},
size = {17 pages},
timestamp = {2008-06-19T17:53:40.000+0200},
title = {Genetic Fitness Optimization Using Rapidly Mixing
Markov Chains},
type = {technical report},
url = {http://www.neurocolt.com/abs/1997/abs97005.html},
year = 1997
}