Spring/Mass means that you specify, "I'd like x masses and y springs"
and the GA will try to maximise the objective.
The objective at the moment is just to keep the first two masses (marked
in red) as far apart as possible. Hopefully this is nice and simple for
the GA.
Get it at
http://www.websamba.com/charlieb/Sdl-forces.tar.gz
http://www.websamba.com/charlieb/Sdl-forces.zip
The archive contents are the same but the tar.gz seems to be mangled by
the webspace provider (which is very odd), YMMV.
There are no docs at the moment nor any packaging. Load the lisp files
in the following order to avoid errors vectors, force-clos, force-sdl,
genetic.
The good stuff is at the bottom of genetic.lisp (and indeed throughout
all the files!).
To start just do (evolve 100 :pop-size 300)
Also note that the mutation rate control is in (breed ...) and may be
too high for may people's taste.
I've been trying some long runs with many masses and springs but as of
yet I haven't managed to get the masses farther than about 80-85 units
apart. Let me know if you have an evolutionary breakthrough.
I am having trouble controlling the convergence of the GA but I'm just a
beginner in evolutionary problem solving so any suggestions would be
welcome.
My suspicions point in many different directions but here are my top 2:
* The search space may have too many local maxima. I actually throttle
the mutation rate so that if the pop looks stagnant I increase it for a
bit. This seems to help a bit.
* The selection/recombination function is a simple take the best 20% and
breed randomly with uniform distribution. This may not be sufficiently
discriminatory against weakness or rewarding of fitness.
Enjoy!
Charlieb
(concatenate 'string "charburr" ·@"
(if (spammer-p you) "nowhere" "uk2")
".net")
Could you tell us a bit more about the problem? Looking briefly
through your code, it seems you're in two dimensions, with gravity
acting. Are you hanging a two-dimensional sheet of springs and masses
in the air, and looking for where gravity pulls it into equilibrium?
(If it's the problem I've stated) I would approach this with a physical
model, not a genetic algorithm. I would write down the potential
function, and try to minimize it with a routine that took the gradient
into account.
If I'm missing something, I'd be happy to learn about it.
···············@yahoo.com wrote:
> Could you tell us a bit more about the problem? Looking briefly
> through your code, it seems you're in two dimensions, with gravity
> acting. Are you hanging a two-dimensional sheet of springs and masses
> in the air, and looking for where gravity pulls it into equilibrium?
Exactly only no gravity (this time) but damping (strength proportional
to speed) to drain the initial energy in the system away and reach
equilibrium.
>
> (If it's the problem I've stated) I would approach this with a physical
> model, not a genetic algorithm. I would write down the potential
> function, and try to minimize it with a routine that took the gradient
> into account.
My maths is not that strong and besides the system will eventually fall
into equilibrium (with the addition of a little damping). The point of
the GA was to ensure the equilibrium state optimised the challenge I
gave it (see below). It would be nice to have a faster way of finding
the equilibrium than a naive simulation but as I say my maths isn't so
good. Anyway, if your still interested read on.
>
> If I'm missing something, I'd be happy to learn about it.
>
The only problem is my understanding of genetic algorithms. The idea was
that the GA should find ways of connecting up the springs to the masses
such that two specified masses (the ones highlighted in red) are as far
apart as possible. All the masses start off very close together so there
is a lot of energy in the system initially.
The problem was that the results didn't seem to actually keep the masses
appart at all, so I thought the GA must be at fault since it's the first
one I've written. What I've realised since then is that the GAs are much
more resilient and intelligent than I gave them credit for.
I had read that, if there were any bugs in the problem implementation,
the GA would find them. I didn't think there were any such bugs as I had
tested the spring/mass code quite thoroughly for conservation of energy
and such. The GA had taken advantage of the fact that I only run the
simulation part of the testing process for a couple of hundred
timesteps. It was using all that initial spring energy getting the
masses as far apart as possible and holding them there until the clock
ran out. If I re-simulated them with say double the number of timesteps
the masses would almost always end up in the same place. So the GA was
optimising on my exact requirements which were more specific than I
realised.
My next challenge will be to come up with GA that makes the mass/spring
network
1. Start will little energy in the springs
2. Is encouraged to have a stable arrangement under noisy conditions and
3. Keeps the masses apart.
Hopefully I'll get some interesting solutions.
Thanks for your interest.
Charlie.
> The idea was
> that the GA should find ways of connecting up the springs to the
masses
> such that two specified masses (the ones highlighted in red) are as
far
> apart as possible.
This was the main place I misunderstood--sorry. I thought the springs
were already connected to the masses in a fixed configuration, and you
just wanted to see how that configuration would stretch. If you're
looking for where to put the springs, that's a discrete problem that
could benefit from simulated annealing or GA.