Multiparticle genetic algorithm

[Klaus Meffert-3]

Following message posted on behalf of Stan ("scopp dort"):
--- snip
Guys,

Suppose I have to find equilibrium configurations of particles placed in a 2
dimensional circle. I am trying to do this with a genetic algorithm.

The fitness function (energy) for the particles is as simple as F =
0.5*(double sum over all particles of 1/(distance between two particles)^3).

F needs to have minimum value.

For example, in a case with 2 particles, they'd place at opposite ends of
circle (so the distance between them was maximal).

The problem I am having is that the more particles I add, the worse the
algorithm behaves.

For example with 10 particles it would hardly converge to the solution
(which is 9 particles on the edge of circle, and one in the middle).

Could it be that genetic algorithm does not work well for multiparticle
systems?

As much as I have read, it always describes finding a value x such that f(x)
is maximum (or minimum).

I have a case where I have f(x1, x2, ..., xN), a multi-valued function,
where each x_i is a particle.


My algorithm works as following:

As the problem is 2 dimensional, it is calculated in polar coordinate
system. A particle is represented by tuple (radius, angle), where both
radius and angle is a binary string.

1) Create some random systems with N particles.

2) From these systems, randomly select fittest proportional to their
fitness.

3) Cross-over the systems to get more children.

The cross over of systems happens like this:
For particle1 in system1:
Take particle2 from system2:
Cross-over radius part between particle1 and particle2
Cross-over angle part between particle1 and particle2

I tried both one-point crossover and two-point crossover.


4) Mutate all the systems (flip bits in both radius and angle proportional
to the length of binary string)


I was thinking that cross-over is not accurate, as I take some particle from
first system and some from the second system, and they might be like on
opposite sides. As I cross over them, I end up with a particle neither near
the first, nor the second.

I made the crossover part so that as I take particle from the first system,
I search for the nearest particle in system2 and perform crossover with only
that particle. But this did not improve the results...

Any hints?


PS. It was very difficult to explain all the details. If you did not
understand some part, I'll be happy to explain it in more details.

Thanks!

Sincerely,
Stan
 
--- snap
Klaus Meffert
www.klaus-meffert.com


-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
jgap-users mailing list
jgap-users@...
https://lists.sourceforge.net/lists/listinfo/jgap-users

[socratesone]

So, when you crossover, you are mutating specific particles? I think that might be the problem.

If you are mutating specific particles in the a separate system for crossover, that new particle would just be placed in the new system rather than have some kind of selection mechanism for the crossover (Though your test to see which is the closest particle in the second system was a good idea). The mutation may work fine if you are mutating a particle inside its own system, but if you are "mutating" (by crossover) a particle of another system into another system, I think that's highly inefficient, and this would be realized the more particles you have in the system.

When you mutate, mutate only the particles themselves, like you are doing.

When you crossover, try this:
Create a crossover function that swaps out the entire particles themselves between the two system rather than crossing over the radius and angle of one or more particles in the other system.
First, sort each system based on radius/angle, and swap out the particles based on the way they are sorted.
Looping through the sorted system, you then populate the new system, with alternating particles from both parents.
The new system would contain half the particles of one system and half of the other.

The sort function could be simple, such as sorting by angles in 5 or 10 degree increments, then sorting by radius, but it might be helpful to come up with a more efficient and useful sorting algorithm based on the way you calculated the closest particle.

Basically, if you have two systems with 10 particles:
r0a0-r10a30-r20a22-r15a30-r12a55-r8a96-r9a130-r20a175-r14a200-r9a350
r5a0-r8a33-r18a33-r13a45-r11a65-r10a101-r9a132-r23a215-r13a256-r6a345

The crossover would be this system:
r0a0-r8a33-r20a22-r13a45-r11a65-r8a96-r9a132-r20a175-r13a256-r9a350

See if that works.

Klaus Meffert-3 wrote:

Following message posted on behalf of Stan ("scopp dort"):
--- snip
Guys,

Suppose I have to find equilibrium configurations of particles placed in a 2
dimensional circle. I am trying to do this with a genetic algorithm.

The fitness function (energy) for the particles is as simple as F =
0.5*(double sum over all particles of 1/(distance between two particles)^3).

F needs to have minimum value.

For example, in a case with 2 particles, they'd place at opposite ends of
circle (so the distance between them was maximal).

The problem I am having is that the more particles I add, the worse the
algorithm behaves.

For example with 10 particles it would hardly converge to the solution
(which is 9 particles on the edge of circle, and one in the middle).

Could it be that genetic algorithm does not work well for multiparticle
systems?

As much as I have read, it always describes finding a value x such that f(x)
is maximum (or minimum).

I have a case where I have f(x1, x2, ..., xN), a multi-valued function,
where each x_i is a particle.


My algorithm works as following:

As the problem is 2 dimensional, it is calculated in polar coordinate
system. A particle is represented by tuple (radius, angle), where both
radius and angle is a binary string.

1) Create some random systems with N particles.

2) From these systems, randomly select fittest proportional to their
fitness.

3) Cross-over the systems to get more children.

The cross over of systems happens like this:
For particle1 in system1:
Take particle2 from system2:
Cross-over radius part between particle1 and particle2
Cross-over angle part between particle1 and particle2

I tried both one-point crossover and two-point crossover.


4) Mutate all the systems (flip bits in both radius and angle proportional
to the length of binary string)


I was thinking that cross-over is not accurate, as I take some particle from
first system and some from the second system, and they might be like on
opposite sides. As I cross over them, I end up with a particle neither near
the first, nor the second.

I made the crossover part so that as I take particle from the first system,
I search for the nearest particle in system2 and perform crossover with only
that particle. But this did not improve the results...

Any hints?


PS. It was very difficult to explain all the details. If you did not
understand some part, I'll be happy to explain it in more details.

Thanks!

Sincerely,
Stan
 
--- snap
Klaus Meffert
www.klaus-meffert.com


-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
jgap-users mailing list
[e-mail]
https://lists.sourceforge.net/lists/listinfo/jgap-users