The Evolution of Size in Variable Length
Representations
W. Langdon. 1998 IEEE International Conference on Evolutionary
Computation, стр. 633--638. Anchorage, Alaska, USA, IEEE Press, (5-9 May 1998)
DOI: doi:10.1109/ICEC.1998.700102
Аннотация
In many cases programs length's increase (known as
"bloat", "fluff" and increasing "structural
complexity") during artificial evolution. We show
bloat is not specific to genetic programming and
suggest it is inherent in search techniques with
discrete variable length representations using simple
static evaluation functions. We investigate the
bloating characteristics of three non-population and
one population based search techniques using a novel
mutation operator.
An artificial ant following the Santa Fe trail problem
is solved by simulated annealing, hill climbing, strict
hill climbing and population based search using two
variants of the the new subtree based mutation
operator. As predicted bloat is observed when using
unbiased mutation and is absent in simulated annealing
and both hill climbers when using the length neutral
mutation however bloat occurs with both mutations when
using a population.
We conclude that there are two causes of bloat 1)
search operators with no length bias tend to sample
bigger trees and 2) competition within populations
favours longer programs as they can usually reproduce
more accurately.
%0 Conference Paper
%1 langdon:1997:pgSAHCP
%A Langdon, W. B.
%B 1998 IEEE International Conference on Evolutionary
Computation
%C Anchorage, Alaska, USA
%D 1998
%I IEEE Press
%K Price's Theorem algorithms, complexity, genetic introns, programming, structural
%P 633--638
%R doi:10.1109/ICEC.1998.700102
%T The Evolution of Size in Variable Length
Representations
%U http://www.cs.bham.ac.uk/~wbl/ftp/papers/WBL.wcci98_bloat.ps.gz
%X In many cases programs length's increase (known as
"bloat", "fluff" and increasing "structural
complexity") during artificial evolution. We show
bloat is not specific to genetic programming and
suggest it is inherent in search techniques with
discrete variable length representations using simple
static evaluation functions. We investigate the
bloating characteristics of three non-population and
one population based search techniques using a novel
mutation operator.
An artificial ant following the Santa Fe trail problem
is solved by simulated annealing, hill climbing, strict
hill climbing and population based search using two
variants of the the new subtree based mutation
operator. As predicted bloat is observed when using
unbiased mutation and is absent in simulated annealing
and both hill climbers when using the length neutral
mutation however bloat occurs with both mutations when
using a population.
We conclude that there are two causes of bloat 1)
search operators with no length bias tend to sample
bigger trees and 2) competition within populations
favours longer programs as they can usually reproduce
more accurately.
@inproceedings{langdon:1997:pgSAHCP,
abstract = {In many cases programs length's increase (known as
{"}bloat{"}, {"}fluff{"} and increasing {"}structural
complexity{"}) during artificial evolution. We show
bloat is not specific to genetic programming and
suggest it is inherent in search techniques with
discrete variable length representations using simple
static evaluation functions. We investigate the
bloating characteristics of three non-population and
one population based search techniques using a novel
mutation operator.
An artificial ant following the Santa Fe trail problem
is solved by simulated annealing, hill climbing, strict
hill climbing and population based search using two
variants of the the new subtree based mutation
operator. As predicted bloat is observed when using
unbiased mutation and is absent in simulated annealing
and both hill climbers when using the length neutral
mutation however bloat occurs with both mutations when
using a population.
We conclude that there are two causes of bloat 1)
search operators with no length bias tend to sample
bigger trees and 2) competition within populations
favours longer programs as they can usually reproduce
more accurately.},
added-at = {2008-06-19T17:35:00.000+0200},
address = {Anchorage, Alaska, USA},
author = {Langdon, W. B.},
biburl = {https://www.bibsonomy.org/bibtex/234386ed73de5a54ed125af5e13f9c0e3/brazovayeye},
booktitle = {1998 IEEE International Conference on Evolutionary
Computation},
doi = {doi:10.1109/ICEC.1998.700102},
file = {c109.pdf},
interhash = {48d0e0a86ce46d3a0afe08250c6b764b},
intrahash = {34386ed73de5a54ed125af5e13f9c0e3},
keywords = {Price's Theorem algorithms, complexity, genetic introns, programming, structural},
month = {5-9 May},
notes = {ICEC-98 Held In Conjunction With WCCI-98 --- 1998 IEEE
World Congress on Computational Intelligence
based on \cite{langdon:1997:bloatSAHCP}},
organisation = {IEEE},
pages = {633--638},
publisher = {IEEE Press},
size = {6 pages},
timestamp = {2008-06-19T17:44:48.000+0200},
title = {The Evolution of Size in Variable Length
Representations},
url = {http://www.cs.bham.ac.uk/~wbl/ftp/papers/WBL.wcci98_bloat.ps.gz},
year = 1998
}