On Jul 12, 2005, at 3:32 PM, Steve Butcher (Steve-O) wrote:

> Conceptually, a hill climber is a population of 1 who at each step is
> compared to the performance of a clone of itself that has undergone a
> random mutation.

I think generally a hill-climber has a population of two.  I've had a
spirited debate with Paul Wiegand about the difference between
hill-climbing and the 1+1 ES, and it comes down to the assumption that
a hill-climber's mutator is "local" -- it cannot mutate to every
possible spot in space in a single jump.

Here's a 1+1 mutation-only ES for the ec/app/sum problem.  It's using
VectorMutationPipeline which could in theory mutate to any point in
space, but you could replace it with a true "local" hill-climbing
mutator if you so desire.


parent.0 = ../../simple/simple.params

generations =                           1000
pop.subpop.0.size =                     2
es.mu.0 =                                               1
es.lambda.0 =                                   1
breed =                                         ec.es.MuPlusLambdaBreeder

pop.subpop.0.fitness =                  ec.simple.SimpleFitness
pop.subpop.0.duplicate-retries = 0
pop.subpop.0.species =                  ec.vector.IntegerVectorSpecies
pop.subpop.0.species.ind =
ec.vector.IntegerVectorIndividual
pop.subpop.0.species.min-gene = 0
pop.subpop.0.species.max-gene = 100
pop.subpop.0.species.genome-size = 10
pop.subpop.0.species.mutation-prob = 0.1
pop.subpop.0.species.pipe = ec.vector.breed.VectorMutationPipeline
pop.subpop.0.species.pipe.source.0 = ec.es.ESSelection

eval.problem = ec.app.sum.Sum


As to simulated annealing: SA can be done, I think, using 1+1 as above,
but with a special ESSelection subclass.  In a 1+1 ES,
MuPlusLambdaBreeder puts the "parent" in the top of the population
(state.population.subpops[subpop].inds[1]), and the "child" in the
bottom (state.population.subpops[subpop].inds[0]).  What your SA
version of ESSelection needs to do is compare the two, and if the child
is better, the child is the one that gets returned by the selection
operation.  Else flip a biased coin (using the generation number to
determine the temperature perhaps) and if it comes up heads, you still
return the child.  Else return the parent.

So, to sum up:
        - RMHC actually can already be done nicely in ECJ.
        - SA would require an easily-written ESSelection subclass designed for
it.  If you'd like to try that, it'd be an hour's work tops my guess,
and would be welcome.
        - If you're fishing for packages to write in this vein, I think the
really crunchy items not yet written for ECJ are an Ant Colony
Optimization algorithm and a Particle Swarm Optimization package.

Sean