Implement 'Revisiting the NSGA-II Crowding Distance Computation'?

[Marcus]

I'm running NSGA-II from DEAP, but in a fixed-precision (i.e. Python Decimal) parameter space as an interface to a simulation tool for my PhD research.

I'm benchmarking my implementation against zdt1. Because of the fixed precision, I'm getting many duplicate finesses. My optimal front converges, until it collapses down into 100% copies of one of the boundary values. So I was happy to have discovered the paper Revisiting the NSGA-II Crowding Distance Computation from GECCO'13. Is this implemented in DEAP? Can I have the Python code for this? It's fairly urgent but I just wanted to ask before implementing it myself.

Thanks and best regards,
Marcus





 

[Félix-Antoine Fortin]

Hi Marcus,

It was implemented with DEAP, but it is not as we speak a part of any DEAP release.

I can provide you the code. Can you quantify 'fairly urgent'?

Félix-Antoine Fortin

--
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.
For more options, visit https://groups.google.com/d/optout.

[Marcus]

I can't really proceed with the main work, so sooner is better!

I hacked some progress with the UFTournSelection;
https://github.com/MarcusJones/deap/blob/mj_master/deap/tools/emo.py#L231-318

Using a test bench which overrides the initial population with k copies of first ind;
https://github.com/MarcusJones/deap/blob/mj_master/examples/ga/nsga2_R.py

Is the intent with UFTournSelection that returned population |S| == |N|, but S can still have identical copies of the same individual (same chromosome and same fitness)? I overwrote __hash__ in my individual so I wasn't able to use set() for S because of this. And SAMPLE() is just random.sample(), where the underlying list is not modified?

Anyways, it would be great to compare with your implementation and also to get snippets of LastFrontSelection (all the rest remains same right?).

Cheers,
Marcus

[Marcus]

I hacked together a solution including LastFront.

However I had a problem where boundary solutions become over represented in the population. They always have the best crowding distance (infinite), even if there are multiple copies of the same boundary point. Here is one run; https://www.youtube.com/watch?v=QYlJa_Bv1TI

It's still a big improvement over pure NSGAII. But I still need to improve the algorithm to maintain diversity in the final pareto population.

Marcus

[Jeannie Fitzgerald]

Hi,

I was just wondering if the updated algorithm described in "Revisiting the NSGA-II Crowding Distance Computation" has been made available? I too would like to try it if possible.

many thanks,

Jeannie

[Jaime RG]

Yeah, I would like to try it too! I've read the paper and looks interesting. However, I'm even more intrigued by Deb's 2012 improvement, the MO-NSGAII. Will this one be implemented too?

Thanks in advance!

[dna...@eng.ucsd.edu]

I was wondering if this improvement had been made public or if you have plans to release it soon. I have a 3 objective optimization problem with a lot of non-unique fitnesses and the resulting Pareto front is mostly concentrated at the boundaries. So I think this improvement will help.

Thanks!

[Félix-Antoine Fortin]

Hi everyone,

I have finally put the code on github in deap experimental repository.

Here is the link:

https://github.com/DEAP/experimental/tree/master/fortin2013

The algorithms presented in the article are implemented in the module 'fortin2013'.

The module nsga2.py provides an example of how to use to code in fortin2013.

I will try to bonify the readme and the function docstrings eventually.

Sorry for the delay, and thanks for taking interest in the article!

Regards,

Félix-Antoine

[Jeannie Fitzgerald]

Hi again Felix-Antoine,

Thank you very much for posting your code.
Previously with the original nsga2 I had been using eaMuPlusLambda, passing in (among others) the hof (hof = tools.ParetoFront()).
What is the easiest way to incorporate a paretoFront Hof with your modified code?

thanks,

Jeannie

[Manuel Belmadani]

You could modify this file:

https://github.com/DEAP/experimental/blob/master/fortin2013/nsga2.py

Before the loop for NGEN generations, create your Hallf of Fame or Pareto Front

hof = tools.ParetoFront() # CREATE HOF

# Begin the generational process

for gen in range(1, NGEN):

... Then, inside the loop, near the end, when the new population is updated after selection, add a call to update() on your HOF with the new population.

 # Select the next generation population

 pop = toolbox.select(pop + offspring, MU)

 hof.update(pop) # UPDATE HOF

[henry joe]

Hi Felix,

Please, on this link: https://github.com/DEAP/deap/blob/master/deap/tools/crossover.py

I found the sbx cross over implementation 

def cxSimulatedBinaryBounded(ind1, ind2, eta, low, up):

My problem is are ind1 individuals in the population? It seems in your code implementation, you have them as list e.g ind1[i]. I have a generation of individuals as real numbers.e.g 14.2, 13,3, 15.4..e.t.c these are just floating numbers. so, I tried to modify your code to fit my idea but the ind1[i] and ind2[i] line is abit confusing to me. Could you tell me how you represented the two parents involved in the crossover?

Thanks

[François-Michel De Rainville]

SBX works with individuals that are a list of parameters. From what I understand, you are trying to optimize a single parameter. Can't you just put that single parameter in a list? This way you won't have to reimplement sbx since the size on line 300 will be 1.

The only difference will be in your evaluation function, where instead of working with indvidual, you will have to work with individual[0], which IMHO is much simpler than recoding all the operators.

Cheers,

François-Michel

[henry joe]

Hello Francois, 

I did tested the codes and saw you are using them in this line : 

ind1 = [3.2, 2.1, 5.4,5.1]

ind 2 = [4.3, 2.1, 6.7,8.2]

but I also have a list e.g ind = [5.6,7.3, 4.5, 8.1].. well, if I really have to use your implementation, I will have to divide my single list into two sub lists ind1 and ind2.  I don't know if there is a way I could just pass a single list instead of two into the method. I thought you pass in two parents and these two parents don't necessarily have to be lists. I could just loop through the entire list and get two parameters. e.g 

pass in ind into the method and then cross over 5.6 and 7.3. I just don't know how to tweak the code to do this.

Regards

Henry

[henry joe]

Please Francois,

what is the nature of the individuals in the sortNondominated(individuals, k, first_front_only=False) method?

It seems it some list containing dictionaries. Am I correct?

Regards

Henry

[François-Michel De Rainville]

Consider that I really don't understand what you are trying to do here.

There is several way to split your individual in 2 ... I would use a decorator that does

ind1, ind2 = individual[::2], individual[1::2]

and then the decorator calls the original function ...

or you can simply add this to the begining of the function and replace the signature with one with a single individual.

Regards,

François-Michel

[François-Michel De Rainville]

No.

The individuals are objects with a fitness attribute.