Parallelize selNSGA2

[Martial Madoumier]

Dear deap developpers and users,

We have an optimization problem based on the DEAP library. As our optimization is slow (one week-long), we used scoop to parallelize our computations [1].

We use selNSGA2 from the deap library [2], and in our settings this function takes up to 90% of the total computation time. Is there any documentation about how to parallelize selNSGA2, for example by using the scoop library ?

We have read the suggestion to use the sortLogNonDominated function by passing nd='log' to the selNSGA2 function [3], but we would like to know if there is a way to parallelize selNSGA2.

Thank you in advance,

[1] https://deap.readthedocs.io/en/master/tutorials/basic/part4.html
[2] deap version 1.3.1-py.3.8 and 1.3.3-py3.11, tested on Mac M1 and linux https://deap.readthedocs.io/en/master/api/tools.html?highlight=nsga2#deap.tools.selNSGA2
[3] https://groups.google.com/g/deap-users/c/OllBATfn7oQ/m/bnkV5aOTAwAJ

[François-Michel De Rainville]

The complexity of the NSGA algorithm is high in the order of O(mn^2), for many individuals (n) it can be overwhelming. Parallelization won't help much to scale. I see a couple of papers proposing other simpler dominance algorithms. However, none are implemented in DEAP.

--
You received this message because you are subscribed to the Google Groups "deap-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to deap-users+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/deap-users/7fab9ede-b2f8-44eb-96da-bf82907ac201n%40googlegroups.com.

[Russell Jarvis]

It was actually a similar sort of problem that inspired me to try other GA optimization tools

https://facebookresearch.github.io/nevergrad/optimization.html#multiobjective-minimization-with-nevergrad

Never grad has a simpler API (there are less things that only optionally should be defined), it has parallel support with modern non DEAP libraries.

If you want genuine performance I would use Julia instead if there is no getting around calling Python code, you can do this with PyCall and you can use Numba JIT as much as possible inside Python.

https://github.com/wildart/Evolutionary.jl/blob/master/docs/src/index.md

To view this discussion on the web visit https://groups.google.com/d/msgid/deap-users/CAJjWHnaFKkReMi1r5kx-0E7xvh4ebP_%2B1oQ9YGmRdW-Cz08afQ%40mail.gmail.com.

--

Russell Jarvis (he/him)

PhD Personal Website I respectfully acknowledge the Traditional Owners of the land on which we work and learn, and pay respect to the First Nations Peoples and their elders, past, present and future.

phone: 61444576301

email: russel...@protonmail.com

[Russell Jarvis]

Sorry no SCOOP dependencies.

[Russell Jarvis]

Sorry I probably shouldn't have recommended a different tool on the DEAP forum. but I think its okay to mention tools in a different language. 


I strongly agree with this quote:"The complexity of the NSGA algorithm is high in the order of O(mn^2), for many individuals (n) it can be overwhelming. Parallelization won't help much to scale. I see a couple of papers proposing other simpler dominance algorithms. However, none are implemented in DEAP."

The complexity of the algorithm matters more the language implementation, but practically the speed of the language can matter too. It's not impossible to do GA optimizations on neuronal models in Julia (despite it being true that there is not much ecosystem yet).

Is the model multicompartment or a point neural network?

[Bogdan Burlacu]

NSGA is limited by the complexity of the non-dominated sorting algorithm. The original algo proposed by Deb is O(n^2) and very inefficient, but surprisingly enough, it's still the default in many evolutionary frameworks.

Non-dominated sorting can be O(n log n). I've done some work on the topic: https://arxiv.org/abs/2203.13654

Even a simple algorithm can do better than the original algorithm: https://gist.github.com/foolnotion/d693861d8b7f6a20e4f48f1c209ebed8

This should be straightforward to include in DEAP

Bogdan