SunnySpell

Maurice.Clerc@WriteMe.com
2005-08-26

In an adaptive Particle Swarm Optimiser like Tribes, some particles are added from time to time. Doing that just purely at random may be not the best way. It could be better to add a particle that is as "isolated" as possible in order to explore some "no man's lands" in the search space.

However, we are not looking for a very precise result, but just a "good enough" one.

Note that in Tribes, some particles are sometimes generated on purpose just on the frontier of the search space. I just try here to replace the generation of the others, which is for the moment purely at random.

The idea is simply to define an "isolation" function, that take into account not only the already known points, but also the whole border of the search space, and to maximise it.

I have written a small algorithm that does the job. Actually, it is itself a basic (non adaptive PSO). Note that it is not at all the same problem that putting simultaneously N particles in the search space. In such a case, a Voronoï/Delaunay  tessellation would be OK. But not here, as N-1 positions are already known: a Delaunay tessellation could easily give the biggest "empty domain",  but the result would sometimes be to near of the frontier of the search space.

In order to easily plot some figures, the code is for MuPAD (+JavaView), and I have added an "exhaustive" search to compare results.

Here are some examples.

2D, 5 positions already known


             Fig. 1.  Position of the "best" new point

The green point is the result of the exhaustive search (step size =0.01 => 10000 evaluations). The red one is the result after 108 evaluations of the basic PSO.
You could think a point around (0.5, 0.75) would be better, but it would be in fact to near of the upper frontier of the search space.


          Fig. 2.  Fitness landscape. We are trying to maximize the "isolation".

By definition, "isolation" is null on the frontier of the search space and on each already known point. Note that there may be some local maximums.

2D, 30 points



          Fig. 3. The result after 108 evaluations (red) is not perfect (green), but good enough


          Fig. 4. Change your mind! These are just 30 bowls, not breasts ...


3D, 30 positions


          Fig. 5. After 405 evaluations, the basic PSO finds a quite good position