Maurice Clerc

2003-04-27

Some PSO versions have been specifically designed to cope with Multiobjective Optimization [1,2,3]. As TRIBES is a non-specialized tool, it can't compete with these algorithms, but, as we will see, it is not that bad at all.

Let p_{1} and p_{2} be two
positions in the search space. Usually, we have just one objective function,
and we say that p_{1} is "better than" p_{2} iif f(p_{1})<f(p_{2}).
The trick is to define the operator "better than" so that it also works when
there are several objective function f_{i}. Of course I used the Pareto's
definition: p_{1} is said to be "better than" p_{2}iif f_{i}(p_{1})<f_{i}(p_{2})
for all i, and f_{i}(p_{1})<f_{i}(p_{2}),
for at least one i.

It easy to see that this second definition
is consistent with the previous one when there is only one objective function.
So, I have rewritten the module better_than(p_{1},p_{2}) according
to the second definition. Similarly, I have modified the way the error is
calculated. As usually, you give the wanted target S, but the error for a
position p is now

Again, it is consistent with the classical , so there was nothing else to change in the program.

In practice, anyway, we don't know S, so the simplest way is to just set it to zero, and then the stop criterion is the maximum number of position evaluations you allow.

Now, if you want to find several solutions (hopefully near of the Pareto front), you just have to launch several times the program, for the initialization is made at random (with just one particle). As TRIBES converges quite quickly, the best strategy is to run it a lot of times (say 1000), but to allow only a small number of position evaluations for each run (say 20). The strategy set used here is (0,0,0,0), the simplest one, which doesn't try to take into account the "quality" of a particle to choose its own strategy (see the source code for details).

I also added a "cleaning" module that runs
*after* TRIBES itself, which keeps only non dominated solutions. So,
if you visualize the result, you more clearly see the front(s). Note that
for specific PSO versions, this cleanup is done *during* the process.

The best specific version I am aware of is
MOPSO, by Coello Coello [1]. So I ran TRIBES (version 4.2) on the examples than
the author has published [1].

Min f_{1}(x_{1}, x_{2})
= x_{1 }

Min f_{2}(x_{1}; x_{2})
= g.(1-(x_{1}/g)^{2}-(x_{1}/g).sin(2.pi.x_{1})),
with g=1+10x_{2, }where 0 ≤x_{1},x_{2 }≤1

MOPSO generates 200 non dominated points after
4000 evaluations. Figure 1 shows the result with TRIBES after the same number
of evaluations, and Figure 2 an attempt to obtain the same number of non
dominated points.

*Fig. 1- Problem F1. 4000 evaluations with TRIBES (200 runs with 20 evaluations). Only 22 non dominated points are kept
*

*
*

*
Fig. 2- Problem F1. 34000 evaluations (1700 runs of 20 evaluations) with
TRIBES, in order to have about 200 non dominated points (202)*

As we can see TRIBES needs 8.5 more evaluations than MOPSO to obtain the same result. Note that, though, the processor time between two evaluations is very short, for almost nothing is done, except sometimes adaptations, as in MOPSO more computations are done (selecting hypercubes, updating the repository, etc.). However, processor times are very difficult to compare, first for different machines are used, and second for TRIBES compute some extra things just for information, and display them or write them on files (for further analysis and visualization).

where -5 ≤x≤10.

MOPSO generates 200 non dominated points after 4000 evaluations.

*Fig. 3- Problem F2. TRIBES, 200 runs of 20
evaluations*

*
*

*Fig. 4- Problem F2. TRIBES, 900 runs of 10 evaluations. 204 non dominated points*

Here TRIBES needs about 2.2 more evaluations
to find a result similar to the one found by MOPSO (see Fig. 4). However,
if you give it exactly the same stop criterion (4000 evaluations), you already
have a pretty good idea of the front (see Fig. 3).

where

MOPSO generates 200 non dominated points after 3200 evaluations.

*Fig. 5- Problem F3. TRIBES, 160 runs of 20 evaluations
*

*Fig. 6- Problem F3. TRIBES, 1200 runs of 10 evaluations. 194 non dominated points*

The good news is that TRIBES can perfectly solve multiobjective problems that are well known to be quite difficult. The bad new is that, not surprisingly, and for a given result quality, it sometimes needs far more position evaluations than the best specific PSO version MOPSO, which seems more or less equivalent to NSGA or PAES. Note that, though, all these specialized algorithms need to be carefully tuned, as TRIBES is completely adaptive and parameter free.

The processor time is still quite reasonable,
say a few seconds for the above problems on a 333 MHz personal computer. Note
that most of specific algorithms divide the search space into small parts
(typically hypercubes, and that is why they are better (Of course, you *could*
do the same with TRIBES, but it means you would have to arbitrary define
the number of "cells"). It's OK in 2D, but for such algorithms the processor
time will increase like 2^{D}, where D is the number of dimensions. This won't be the
case with TRIBES.

So, finally, it was certainly worthwhile to add the multiobjective option to TRIBES, for now any user can solve this kind of problem just by describing it, without the tedious process of finding the "good" parameters. The "price" of this easiness is not very high: just a bit more processor time.

________________________________________________________________________________

[1] Coello
Coello C. A., Lechuga M. S., "MOPSO: A Proposal for Multiple Objective Particle
Swarm Optimization", *Congress on Evolutionary Computation (CEC'2002)*,
Piscataway, New Jersey, 2002, p. 1051-1056.

[2] Hu X., Eberhart R. C., "Multiobjective Optimization
Using Dynamic Neighborhood Particle Swarm Optimization",*Congress on Evolutionary
Computation (CEC'2002)*, Piscataway, New Jersey, 2002, p. 1677-1681.

[3] Parsopoulos K. E., Vrahatis M. N., "Particle Swarm
Optimization Method in Multiobjective Problems", *ACM Symposium on Applied
Computing (SAC 2002)*, 2002, p. 603-607.