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