Papers and Programming

by J.D. Marble on February 24, 2010

Overview

Papers!

  • Efficient Allele Fitness Assignment with Self-organizing Multi-agent System [1]

  • Application of a Compact Genetic Algorithm to Pipe Network Optimization Problems [2]

Programming!

  • Progress on Extended Compact Genetic Algorithm

  • Problems

  • Results

  • An Idea

Allele Fitness Assignment

“The problem of discovering complex control policies for continuous tasks is often best addressed by decomposing the policy into several simpler parts.”[1]

  • Credit assignment problem

  • Multi-agent search problem

  • 2-D pole balancing

CGA for Pipe Networks

New York tunnel network.[2]

Progress

Done:

  • Basic ECGA

  • Parametrized over genome type (bit string / real string / etc..)

To do:

  • Tournament selection (vs. truncation)

  • Partial replacement (vs. complete)

  • Limit building block size so 2^l \leq N (l = b.b. size, N = pop. size)

Flowchart

Extended Genetic Algorithm flowchart.[3]

Problems

  • Enumeration of all 2^n bit combinations in a building block (out of memory)

  • Execution speed

  • Early convergence

Results So Far

  • Solves segmented deceptive problem (number of bits \leq 32)

  • (sometimes)

Idea!

Modeling the population is an optimization problem.

  • Try other search algorithms besides greedy, best-only

  • Try different heuristics for the tree search

Bibliography

[1] A. Agogino and R. Miikkulainen, “Efficient Allele Fitness Assignment with Self-organizing Multi-agent System,” Proc. Genetic and Evolutionary Computation Conference, GECCO–2004, New York, NY: Springer-Verlag, 2004.

[2] M.H. Afshar, “Application of a Compact Genetic Algorithm to Pipe Network Optimization Problems,” Civil Engineering, vol. 16, 2009, pp. 264–271.

[3] K. Sastry and D. Goldberg, “On extended compact genetic algorithm,” Genetic and Evolutionary Computation Conference, Urbana, IL, USA: 2000, p. 352–359.