Evolutionary methods are powerful tools in discovering solutions for
difficult continuous tasks. When such a solution is encoded over
multiple genes, a genetic algorithm faces the difficult credit assignment
problem of evaluating how a single gene in a chromosome contributes
to the full solution. Typically a single evaluation function is used
for the entire chromosome, implicitly giving each gene in the chromosome
the same evaluation. This method is inefficient because a gene will
get credit for the contribution of all the other genes as well. Accurately
measuring the fitness of individual genes in such a large search
space requires many trials. This paper instead proposes turning this
single complex search problem into a multi-agent search problem,
where each agent has the simpler task of discovering a suitable gene.
Gene-specific evaluation functions can then be created that have
better theoretical properties than a single evaluation function over
all genes. This method is tested in the difficult double-pole balancing
problem, showing that agents using gene-specific evaluation functions
can create a successful control policy in 20% fewer trials than the
best existing genetic algorithms. The method is extended to more
distributed problems, achieving 95% performance gains over tradition
methods in the multi-rover domain.
GECCO'05: Proc. 7th Genetic and Evolutionary Computation Conf.
year
2005
pages
1309--1316
publisher
ACM Press
crossref
gecco:2005
owner
Rick
notes
GECCO-2005 A joint meeting of the fourteenth international conference
on genetic algorithms (ICGA-2005) and the tenth annual genetic programming
conference (GP-2005). ACM Order Number 910052
%0 Conference Paper
%1 Agogino:2005:gecco
%A Agogino, Adrian Kujaneck
%A Tumer, Kagan
%A Miikkulainen, Risto Pekka
%B GECCO'05: Proc. 7th Genetic and Evolutionary Computation Conf.
%C Washington, DC
%D 2005
%E Beyer, Hans-Georg
%E O'Reilly, Una-May
%E Arnold, Dirk V.
%E Banzhaf, Wolfgang
%E Blum, Christian
%E Bonabeau, Eric W.
%E Cantu-Paz, Erick
%E Dasgupta, Dipankar
%E Deb, Kalyanmoy
%E Foster, James A.
%E de Jong, Edwin D.
%E Lipson, Hod
%E Llora, Xavier
%E Mancoridis, Spiros
%E Pelikan, Martin
%E Raidl, Guenther R.
%E Soule, Terence
%E Tyrrell, Andy M.
%E Watson, Jean-Paul
%E Zitzler, Eckart
%I ACM Press
%K A-Life, Adaptive Algorithms, Ant Applications, Artificial Behaviour, Biological Coevolution, Colony Combinatorial Distribution Engineering Estimation Evolutionary Evolvable Hardware, Immune Intelligence, Local Meta-heuristics Multi-objective Optimisation Optimisation, Optimization, Programming, Real Robotics Search, Search-based Software Strategies, Swarm Systems, World algorithms, and genetic of programming, thesis
%P 1309--1316
%R 10.1145/1068009.1068221
%T Efficient credit assignment through evaluation function decomposition
%U http://portal.acm.org/citation.cfm?id=1068009&jmp=cit&coll=GUIDE&dl=GUIDE&CFID=48779769&CFTOKEN=55479664#supp
%X Evolutionary methods are powerful tools in discovering solutions for
difficult continuous tasks. When such a solution is encoded over
multiple genes, a genetic algorithm faces the difficult credit assignment
problem of evaluating how a single gene in a chromosome contributes
to the full solution. Typically a single evaluation function is used
for the entire chromosome, implicitly giving each gene in the chromosome
the same evaluation. This method is inefficient because a gene will
get credit for the contribution of all the other genes as well. Accurately
measuring the fitness of individual genes in such a large search
space requires many trials. This paper instead proposes turning this
single complex search problem into a multi-agent search problem,
where each agent has the simpler task of discovering a suitable gene.
Gene-specific evaluation functions can then be created that have
better theoretical properties than a single evaluation function over
all genes. This method is tested in the difficult double-pole balancing
problem, showing that agents using gene-specific evaluation functions
can create a successful control policy in 20% fewer trials than the
best existing genetic algorithms. The method is extended to more
distributed problems, achieving 95% performance gains over tradition
methods in the multi-rover domain.
%@ 1-59593-010-8
@inproceedings{Agogino:2005:gecco,
abstract = {Evolutionary methods are powerful tools in discovering solutions for
difficult continuous tasks. When such a solution is encoded over
multiple genes, a genetic algorithm faces the difficult credit assignment
problem of evaluating how a single gene in a chromosome contributes
to the full solution. Typically a single evaluation function is used
for the entire chromosome, implicitly giving each gene in the chromosome
the same evaluation. This method is inefficient because a gene will
get credit for the contribution of all the other genes as well. Accurately
measuring the fitness of individual genes in such a large search
space requires many trials. This paper instead proposes turning this
single complex search problem into a multi-agent search problem,
where each agent has the simpler task of discovering a suitable gene.
Gene-specific evaluation functions can then be created that have
better theoretical properties than a single evaluation function over
all genes. This method is tested in the difficult double-pole balancing
problem, showing that agents using gene-specific evaluation functions
can create a successful control policy in 20% fewer trials than the
best existing genetic algorithms. The method is extended to more
distributed problems, achieving 95% performance gains over tradition
methods in the multi-rover domain.},
added-at = {2017-03-16T11:50:55.000+0100},
address = {Washington, DC},
author = {Agogino, Adrian Kujaneck and Tumer, Kagan and Miikkulainen, Risto Pekka},
biburl = {https://www.bibsonomy.org/bibtex/25d94b64a01371b1f1e43b739ec75efa3/krevelen},
booktitle = {GECCO'05: Proc. 7th Genetic and Evolutionary Computation Conf.},
crossref = {gecco:2005},
doi = {10.1145/1068009.1068221},
editor = {Beyer, Hans-Georg and O'Reilly, Una-May and Arnold, Dirk V. and Banzhaf, Wolfgang and Blum, Christian and Bonabeau, Eric W. and Cantu-Paz, Erick and Dasgupta, Dipankar and Deb, Kalyanmoy and Foster, James A. and de Jong, Edwin D. and Lipson, Hod and Llora, Xavier and Mancoridis, Spiros and Pelikan, Martin and Raidl, Guenther R. and Soule, Terence and Tyrrell, Andy M. and Watson, Jean-Paul and Zitzler, Eckart},
interhash = {f60f1de00413939ec15f8dd4031cc9b3},
intrahash = {5d94b64a01371b1f1e43b739ec75efa3},
isbn = {1-59593-010-8},
keywords = {A-Life, Adaptive Algorithms, Ant Applications, Artificial Behaviour, Biological Coevolution, Colony Combinatorial Distribution Engineering Estimation Evolutionary Evolvable Hardware, Immune Intelligence, Local Meta-heuristics Multi-objective Optimisation Optimisation, Optimization, Programming, Real Robotics Search, Search-based Software Strategies, Swarm Systems, World algorithms, and genetic of programming, thesis},
notes = {GECCO-2005 A joint meeting of the fourteenth international conference
on genetic algorithms (ICGA-2005) and the tenth annual genetic programming
conference (GP-2005). ACM Order Number 910052},
organisation = {ACM SIGEVO (formerly ISGEC)},
owner = {Rick},
pages = {1309--1316},
publisher = {ACM Press},
publisher_address = {New York},
timestamp = {2017-03-16T11:54:14.000+0100},
title = {Efficient credit assignment through evaluation function decomposition},
url = {http://portal.acm.org/citation.cfm?id=1068009&jmp=cit&coll=GUIDE&dl=GUIDE&CFID=48779769&CFTOKEN=55479664#supp},
year = 2005
}