Efficient credit assignment through evaluation function decomposition
Adrian Agogino, Kagan Tumer, Risto P Miikkulainen · 2005
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 theoreticaal 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.