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

Is the entire population undergoing mutation?

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.

Quote: Original post by AngleWyrm
Is the entire population undergoing mutation?

Yes, the entire population is undergoing mutation.

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

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.

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?

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...

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).

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]