Session:

SOE - Self-Organization on Representations for Genetic and Evolutionary Algorithms

Title:

Efficient Allele Fitness Assignment with Self-organizing Multi-agent System

Authors:

Adrian Agogino
Risto Miikkulainen

Abstract:

The problem of discovering complex control policies for continuous tasks is often best addressed by decomposing the policy into several simpler parts. While a genetic algorithm usually decomposes the task by encoding a chromosome over multiple genes, it faces the difficult credit assignment problem of evaluating how a single allele in a chromosome contributes to the full solution. Typically a single evaluation function is used for the entire chromosome, implicitly giving each allele in the chromosome the same evaluation. This method is inefficient because an allele will get credit for the contribution of all the other alleles as well. Accurately measuring the fitness of an individual allele in such a large search space requires many trials and may result in stagnation. 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 allele. Gene-specific evaluation functions can then be created that have better theoretical properties than a single evaluation function over all genes. Even though each gene has its own evaluation function, through the process of self-organization a set of compatible alleles can be found to form a high performing chromosome. The method is tested on the double-pole balancing problem, showing that agents that self-organize using gene-specific evaluation functions can create a successful control policy in 20% fewer trials than the best existing genetic algorithms.