GSOC 2008 - Improved MOSES

Basic Details

Abstract

To make MOSES more efficently, some algorithm will take the place of hBOA or incorporate into it. The Building Block Hill Climbing algorithm is currently in the plan

Contributors

• Chen Shuo

Mentors

• Moshe Looks

Work Log

Theory Learning Period

Week of May 19 (2008, May 19 - May 25)

• Reading PMBGA

Week of May 26 (2008, May 26 - Jun 1)

• reading BOA
• reading escaping-hierarchical-traps-with

Week of Jun 2 (2008, Jun 2 - Jun 8)

• reading Levels of Abstraction in Modeling and Sampling
  • reading more material about model building

week of Jun 9 (2008, Jun 9 - Jun 15)

• building concept of MOSES's framework

week of Jun 16 (2008, Jun 16 - Jun 22)

• reading BBHC
• reading "Exploiting Random Walk Strategies"

Coding Period

Week of July 14 (2008, July 14 - July 20)

• reading code of MOSES

Week of July 21 (2008, July 21 - July 27)

• write testing code of BBHC

Week of July 28 (2008, July 21 - August 3)

• Improveing BBHC and try to repeat Iclanzan's result
• nearly completed

Coding & Experiment Period

Week of August 4 (2008, August 4 - August 10)

• improve current coding
• try noisy fitness function
• try new ways of linkage learning on BBs

Week of August 11 (2008, August 11 - August 17)

• try to incorporate hBOA into BBHC

Week of August 18 (2008, August 18 - August 24)

• experiment on the new algorithm

Week of August 25 (2008, August 25 - August 29)

• debugging
• writing documents

result

The project meets its original purpose on improving performance of everlutionary algorithm.

experiment result

repeat Iclanzan's results or BBHC

My program gives similar results on testing evaluation functions, it does a little better on HIFF function & HXOR function and a little worse on HTRAP function. Here is some test data:

experiment result on function HIFF:
sting length   pop size   evals(BBHC)      evals(Iclanzan)
    128         12            6200              10000
    256         15            15500             20000
    512         16            33000             47000
    1024        18            74000             100000

(about a new idea) incorporate hBOA into BBHC

• I tryed to incorporate hBOA into BBHC in a simple mannar that consider each Building Block as a single variable in hBOA, then do a hBOA optimization on the current promising solutions, then use the result to update BB model. Experiment gived negative results, hBOA takes a few part of evaluations in the whole procedure and makes the algorithm easier to fall into traps.
• Experiment results indicates that hBOA and BBHC needs different settings to work well. hBOA need a large population size and runs many turns, in each turn it take only a little evaluations. BBHC use only a little population size and runs for a little turns, but it takes many evaluations in each loop. This idea doesn't work.

source code

download it form here: http://code.google.com/p/moses/downloads/list