1
$\begingroup$

I have a problem with three objective functions to be minimized, F1(interval value is [0,100]); F2(interval value is [0,100]); and F3(interval value is [0,20]). To solve my problem, I use Particle Swarm Optimization (PSO) algorithm and Genetic algorithm (GA) with the weighted sum method. When I run the algorithm with different weight values, always the PSO find the better solution in term of F1 and F2, whereas GA always finds the better solution for F3.

I tested also to optimize only F3 without F1 and F2, the GA is always the best one.

Is that logic? How we can explain that?

$\endgroup$
1
  • $\begingroup$ GA performance is tied to how you define the chromosome and how you implement crossover (among other things). It's difficult for me to articulate this, but in a loose sense it matters that what makes a solution good involves "chunks" of a chromosome (so that crossover tends to preserve what's good in a good solution). Is it possible our implementation does that better for F3 than for F1 and F2? $\endgroup$
    – prubin
    Nov 9 '21 at 16:25
3
$\begingroup$

First, let me state that it is difficult to write an answer to this question as it is very vague and lacks necessary detail. The real question here is not that GA and PSO perform differently (that's something that can be expected), but that you want to know whether there is a bias in the variation/selection operators that results in a bias towards different fitness functions.

The PSO algorithm uses a variation operator that interpolates solutions. Each particle is attracted by its personal best and by the best in its "neighborhood". The particles may however move beyond the direct path between these two attractors.

The GA may use variation operators that either interpolate (for instance an arithmetic crossover, such as a uniform arithmetic crossover or a blended crossover) or combine (an N-point or discrete crossover) different solutions. It is not clear from the description which crossover is used. The N-point/discrete crossover is much more different to the particle update in the PSO. It is much less "local". That could explain a certain bias. Potentially there is a stronger gradient with respect to F1 and F2, but a much weaker one with respect to F3, while a local minimum with respect to F3 is still quite good overall.

So you could compare the performances of these algorithms if you vary their parameters or if you introduce some specific bias in the way initial solutions are generated. For instance perform experiments where the particles are produced not uniformly in the whole solution space, but rather where you select a certain point and generate them in a certain radius around that point. That way you can explore whether different starting regions bias a search trajectory that uses a more local update mechanism.

In any case, it is important to really explore the parameter space of the algorithms before drawing conclusions. Some suggestions on how you can proceed:

A) Automated parameter tuning. GA and PSO have many different parameters that affect the performance of the algorithm for a given problem. I assume you're comparing just two instances of these algorithms with default parameterizations. You want to tune those parameters to the actual problem. This can be done by hand through design of experiments, but automated methods exist. irace for instance is an easily accessible tool that simply requires that you provide an executable that takes parameters as input and which starts your algorithm. It needs to output a single number (the fitness) to stdout at the end. It will perform several experiments and provide the best performing parameterization as output. Of course it can take a lot of time to run (but it's automated).

B) Examine the obtained solutions. In what way do the solutions of PSO differ from those of the GA? Are there large differences in the parameters, can it be attributed to a small number of parameters or is the solution entirely different? Do you have any bias in the way you generate the starting solution that differs between those algorithms. If you start PSO with solutions biased in a region where the GA found the best solution, does it perform similarily?

C) Use multi-objective optimization algorithms to explore the Pareto front. MOPSO and NSGA-II are multi-objective variants of these algorithms, but any algorithm suffices. You just want to approximate the Pareto front as best as possible, so any algorithm's output can be combined. Then explore the solutions on the Pareto front. Is the Pareto front convex? Aim to identify those solutions that the single-objective algorithms would be drawn to given the weight vector (you can e.g. rank all of them by the weighted sum and highlight them on a visual representation of the Pareto front). If your Pareto Front is not convex, then the weighted sum approach cannot be used to identify any point on the front. The shape of the Pareto front can also potentially provide some explanations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.