NSGA - II: A multi-objective optimization algorithm

A function for multi-objective optimization using evolutionary algorithms

Description

NSGA-II is a very famous multi-objective optimization algorithm. I submitted an example previously and wanted to make this submission useful to others by creating it as a function. Even though this function is very specific to benchmark problems, with a little bit more modification this can be adopted for any multi-objective optimization.

The function is nsga_2(pop,gen). The input arguments for the function are population size and number of generations. For customization purposes the user is free to modify the objective function (function of several decision variables) by modifying an m file (evaluate_objective.m). Couple of sample objective functions is already described in the file. The user also has the freedom to define the decision space.

For more information on NSGA-II visit Kanpur Genetic Algorithm Laboratory at http://www.iitk.ac.in/kangal/

One of the main applications of multi-objective optimization that I am currently working on is tuning PID controllers using MOEA. I am hoping to share that work with everyone soon.

Update (January 27, 2009): I am unable to support user's request to modify this program to incorporate constraints in the optimization program since I have no time to delve into this field. Hence effective today (January 27, 2009) I release this program under GPLv3. This means that anyone and everyone can modify this code as and how they wish. Enjoy! But do remember to contribute the code back to the community.

Effective July 17, 2009 this code is re-licensed under BSD license to comply with Mathworks policy on submissions to MATLAB central.

Note: I no longer have the resources to maintain this code.

• Acknowledgements: This submission has inspired the following:; GODLIKE - A robust single-& multi-objective optimizer
• MATLAB release: MATLAB 7.1.0 (R14SP3)
• Other requirements: Evolutionary algorithms are CPU and memory intensive. Recommended CPU clock speed is 1.6GHz with atleast 512MB RAM.
• Published M Files: evaluate_objective, function f = genetic_operator(parent_chromosome, M, V, mu, mum, l_limit, u_limit), function f = replace_chromosome(intermediate_chromosome,pro,pop), function nsga_2(pop,gen), function tournament_selection(chromosome, pool_size, tour_size), initialize_variables, non_domination_sort_mod, NSGA-II/html/objective_description_function.html
• Other Files: license.txt, ; NSGA-II/evaluate_objective.m, ; NSGA-II/genetic_operator.m, ; NSGA-II/initialize_variables.m, ; NSGA-II/non_domination_sort_mod.m, ; NSGA-II/NSGA II.pdf, ; NSGA-II/nsga_2.m, ; NSGA-II/objective_description_function.m, ; NSGA-II/replace_chromosome.m, ; NSGA-II/tournament_selection.m

[xunkai wei]

A good one, yet if you can use a mex interface, it will be more attractive!

[ZC ZC]

 

[hamid ansari]

 

[Mukiwa Zimbani]

This is a very helpful set of files!
It seems like this implementation does not handle constraints though. Deb's NSGA-II paper mentions a scheme for handling constraints (i.e. not just bound constraints on the decision variables, but "constraint functions"). If this is implemented in this version, could you point me towards whereI acn specify the constraints? If not, would you know of a matlab version that implements these contraints?

Thanks!

[moh hemati]

THanks

[Piotr Wozniak]

Generally a pleasure to work with, has been very useful to my work. The one minor thing I'd recommend would be ensure consistency in variable declarations in the m-files.

Great work!

[Varun Aggarwal]

this code is buggy, use at own risk. sbx is wrong, selection is not done the right way and others...

[Mohammad Hemati]

thank you for this report,but these codes don't use for decition variables space,please guide me ,How I get the variables value (x1,x2,.....).Also How use it for constrained problems.
Very thanks

[tong hunter]

this toolbox is very useful to me .thanks
but,I haven't found there is some bugs

[shahab shamshirband]

HI dear friends
i need a source code for tsp based on quadratic problems

[little cat]

thx

[water bruce]

thx, dear friend, you renew my life.

[Istadi Istadi]

 

[Fenggy Chen]

thx.

[nima tavakkoli]

thanx alot,it`s brilliant!

[Seth Soman]

 

[hadj smail]

 

[Joe Leo]

 

[segaf husein]

 

[Luis Felipe Giraldo]

 

[Slim Bechikh]

Hi Arvind, I am Slim Bechikh a tunisian student, i thank you for your efforts to develop such program but there is a small mistake in your code:
function f = replace_chromosome(intermediate_chromosome,
pro,pop)
must be
function f = replace_chromosome(intermediate_chromosome,
M,V,pop)

I tried your program on MATLAB 7.0 and it did not run and after correcting this mistake it has run with succes.

[elty sarvia]

This is a very helpful set of files! It seems like this implementation does not handle constraints though. Deb's NSGA-II paper mentions a scheme for handling constraints (i.e. not just bound constraints on the decision variables, but "constraint functions"). If this is implemented in this version, could you point me towards whereI acn specify the constraints? If not, would you know of a matlab version that implements these contraints? Thanks!

[Ram Natamo]

To me it seems there is some room for improvement. In file genetic_operator.m line
was_cossover = 0;
should probably be
was_crossover = 0;

Even worse, in the same file, child_3 is of different size than V before call:
child_3(:,V + 1: M + V) = evaluate_objective(child_3, M, V);
This must be an error?!

[Ram Natamo]

Further, it seems that performance of this implementation is not even close to that of Deb's original implementation, with regard to generations.
Probably there is something wrong with this code?

[Ram Natamo]

After my previous comments I did some head to head testing with this implementation and original c-implementation by Deb's group (downloadable from http://www.iitk.ac.in/kangal/), and this implementation is converging really slowly (in terms of objective function evaluations)! That's a pity, I could have used Matlab implementation... :(
My recommendation is that you should use this version only if you dont care a bit about performance.

[Mauro Kito]

The code works well with all the test problems. Indeed, C code implementation will have faster performance in computation

[ali mohammadpour]

 

[Javed Dhillon]

 

[Zhang Tieliang]

thank you for the code.Please help me that how use it for constrained problems. If not, would you know other matlab code that can do these contraints?

[Zhang hua yong]

It can not work !

[lin deng]

the code can work well, and it can be used for constrained problems by little modification, thank u for the author!

[Deepak santhanakrishnan]

Thnks for this. Where do i call the input arguments for the function popsize and number of arguments in the main file?

[hailiang shen]

The author seems to be used to c programming language. If implemented with more vector operation, the performance (speed) should be better.

[Tuan Pham]

 

[Tuan Pham]

I had solved my problem with this NSGA-II codes but it does cost computer resources. However as I know latest Matlab versions have "gamultiobj" dealing with multiobjective optimization with genetic algorithm. I haven't worked with gamultiobj so I don't know what will be different between these two.

[liheng liu]

great job! It can work well on my project! just a little modification to suit my constraint problem! thank you!