Sign in to follow this  
sotnet

Multiparticle genetic algorithm

Recommended Posts

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

Share this post


Link to post
Share on other sites

Quote:

Any hints?
Yes: don't use a genetic algorithm. You've a well-behaved system with a differentiable energy function and a differentiable constraint.

Apply classical nonlinear constraint optimization: google for the method of Lagrange multipliers.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous P

Quote:

Any hints?
Yes: don't use a genetic algorithm. You've a well-behaved system with a differentiable energy function and a differentiable constraint.

Apply classical nonlinear constraint optimization: google for the method of Lagrange multipliers.



Oh. I was reading a paper on this problem and it said the no effective algorithm in polynomial time existed! I'll look into this.

For example, there is a well know Thomson problem (http://en.wikipedia.org/wiki/Thomson_problem) which is pretty similar to this one. The fitness function is differentiable (0.5 * double sum over all particles of 1/(distance between particles)) and constraint (sqrt(x^2 + y^2 + z^2) <= 1), and all the papers I have seen about it, is about solving it with heuristic methods (simulated annealing, molecular dynamics, random search with steepest descent relaxation, etc.)

I posted the problem to comp.ai.genetic as well, and someone told me that genetic algorithms are ok for this problem.

http://groups.google.com/group/comp.ai.genetic/topics


Stan

Share this post


Link to post
Share on other sites
Quote:

Oh. I was reading a paper on this problem and it said the no effective algorithm in polynomial time existed!

Well, it needn't exist to solve it exactly (though I suspect it might in this case). You can formulate it as a classical nonlinear optimization problem and use iterative solvers on it (as provided out of the box by math packages).
Quote:


I posted the problem to comp.ai.genetic as well, and someone told me that genetic algorithms are ok for this problem.
Yes, if done correctly.

Your crossover operators fail to take into account the symmetries induced by your fitness function. What if you have two optimal identical configurations with permuted particle positions and cross them over? Mayhem.

How is your mutation a small perturbation under your fitness metric? It isn't.

Edit: Wrote convex instead of nonlinear.

Share this post


Link to post
Share on other sites
Quote:

Quote:

Oh. I was reading a paper on this problem and it said the no effective
algorithm in polynomial time existed!


Well, it needn't exist to solve it exactly (though I suspect it might
in this case). You can formulate it as a classical nonlinear
optimization problem and use iterative solvers on it (as provided out
of the box by math packages).



Ah! I'll definitely try this!

Quote:

Quote:

I posted the problem to comp.ai.genetic as well, and someone told
me that genetic algorithms are ok for this problem.


Yes, if done correctly.

Your crossover operators fail to take into account the symmetries induced
by your fitness function. What if you have two optimal identical
configurations with permuted particle positions and cross them over? Mayhem.

How is your mutation a small perturbation under your fitness metric? It isn't.


Yes! This is exactly the problem I am having. I have hard time creating such a representation that mutation is a small perturbation under fitness metric for this problem...

Do you (or anyone else) have any ideas how to create such a representation?

Share this post


Link to post
Share on other sites
One more thing...

How do all those examples work, then? For example, almost all documents give as the first example maximization of function f(x) = x^2 (or something similar). Then they say that x can be represented as a binary.

For example a 3 bit representation 111 would give a value 7.

Here a small mutation in the first bit can change the value by 4 (011).

It does not hold that small mutations in chromosome result in a small value mutation.


Confused...

Makes me think that all the introduction texts to genetic algorithms are just wrong, if they suggest to use binary representation. Hmm...

Share this post


Link to post
Share on other sites
Binary representation is what they consider as a representation of a chromosome, there is no set in stone requirement for equality of seeked function, and chromozome function.

Imagine a function fa(u) which is a solution of a problem, and a function fb(u) which is a function of a chromozome. Intersection of fa(u) and fb(u) is solution of the problem, however there is no requirement for fa(u) to be equal to fb(u).

Share this post


Link to post
Share on other sites
Try these two papers for a better approach to the generalised problem:

Ekanayake, S. and Pathirana, P. (2007) Geometric Formations in Swarm Aggregation: an Artificial Formation Force Based Approach, in Harry Watson, Thrish Nanayakkara, Daminda Alahkoon, Lanka Udawatta (eds), ICIAfS 2007 the 3rd International Conference on Information and Automation for Sustainability, pp. 82-87, The Institute of Electrical and Electronics Engineers, Inc (IEEE), United States [E1]


Ekanayake, S. and Pathirana, P. (2006) Artificial Formation Forces for Stable Aggregation of Multi-Agent System, in Institute of Electrical and Electronics Engineers (eds), Sustainable Development Through Effective Man-Machine Co-Existence: Proceedings of the International Conference on Information and Automation (ICIA'06), pp. 129-134, Institute of Electrical and Electronics Engineers, USA [E1]

Share this post


Link to post
Share on other sites
Hopefully, I'm reading your problem correctly, but you're basically trying to find positions for a set of particles such that it maximizes the distance between each other particle within a circular region?

If that is so, then the first thing that comes to mind is some of sort of annealing process, rather than a GA. You could simply randomly drop the particles into the circle and have them exert a repelling force on each other. Then over time reduce the step size that you move a particle during a cycle. It should gradually settle on some configuration where the repelling forces pushes the particles no where significant.

Share this post


Link to post
Share on other sites
Quote:
Original post by WeirdoFu
Hopefully, I'm reading your problem correctly, but you're basically trying to find positions for a set of particles such that it maximizes the distance between each other particle within a circular region?


Yes, that is correct!


Quote:

If that is so, then the first thing that comes to mind is some of sort of annealing process, rather than a GA. You could simply randomly drop the particles into the circle and have them exert a repelling force on each other. Then over time reduce the step size that you move a particle during a cycle. It should gradually settle on some configuration where the repelling forces pushes the particles no where significant.


Thanks for your suggestion.

I actually have two papers in front of me which describe it done with Simulated Annealing successfully, and another one with Molecular Dynamics method.

I am now trying to solve the same problem with genetic algorithms.

A few hours ago I tried to represent the variables with binary strings of a length of 1000*(max value of variable). Where a bit '1' in the string would equal to 1/(1000*max value of variable). (For example, if all the bits are '1' then the value is 'max value', if some are 1, and some 0, then I just sum over '1' and multiply by 1/(1000*max value of variable))

It seems promising.

Share this post


Link to post
Share on other sites
Generally I think that using plain binary for the representation of values in genetic algorithms is a poor idea. I think it gained some traction because it bears resemblance to the way biological crossover and mutation works, but for representing numbers it's not great due to the different significance of each bit. Working with the original values usually works well enough once you develop reasonable mutation and crossover operators, or consider using Gray code if you really enjoy bit-twiddling.

Share this post


Link to post
Share on other sites
Quote:
Original post by sotnet
Quote:
Original post by AngleWyrm
Is the entire population undergoing mutation?

Yes, the entire population is undergoing mutation.


It seems to me that in order to have "Survival of the Fittest", the fittest must survive. Maybe only mutate a percentage?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this