Code covered by the BSD License  

Highlights from
NGPM -- A NSGA-II Program in Matlab v1.4

4.5

4.5 | 13 ratings Rate this file 197 Downloads (last 30 days) File Size: 387 KB File ID: #31166
image thumbnail

NGPM -- A NSGA-II Program in Matlab v1.4

by

 

23 Apr 2011 (Updated )

NSGA-II and R-NSGA-II in Matlab

| Watch this File

File Information
Description

This program is an implementation of nondominated sorting genetic algorithm II (NSGA-II) proposed by K. Deb. Capabilities:
1. R-NSGA-II: Reference-point-based NSGA-II.
2. Coding: real, integer.
3. GA operator: Intermediate crossover, Gaussian mutation.
4. Constraint handling.
5. Parallel computation of objective function evaluation.
6. Population plot in window.
I write this program because Aravind Seshadri’ program (File ID#10429) could not satisfy my request. I need constraint handling, integer coding to solve a finite element optimization problem. The finite element solution is very time-expensive, thus the parallel computation of objective evaluation is implemented in the code.

Acknowledgements

Nsga Ii: A Multi Objective Optimization Algorithm inspired this file.

MATLAB release MATLAB 7.11 (R2010b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (61)
11 Sep 2014 Hsinting

I tried. Maximize one of the objective by adding a minus sign onto the objective function. Also need to change the plot instruction. Is there any better way to deal with it?

09 Sep 2014 Melissa

Has anyone tried the maximize?

03 Sep 2014 Hsinting

Sorry, I found my mistake already. The summation is operated in the following lines of the program.

03 Sep 2014 Hsinting

Thank you very much for your sharing.
Cinna think
In function f = non_domination_sort_mod(x, M, V) line 182
y(index_of_objectives(j),M + V + 1 + i) = ...
+ (next_obj - previous_obj)/(f_max - f_min);
Should be
y(index_of_objectives(j),M + V + 1 + i) = ...
y(index_of_objectives(j),M + V + 1 + i) ...
+ (next_obj - previous_obj)/(f_max - f_min);
Please correct me if I am wrong.
Thank you

08 Jul 2014 Mahesh

Thanks for the great work!!!

You have explained about constraints (Your manual Page 1)
g1(x)=x2+9x1>=6

But if constraints are like say,
g1(x)=x2+9x1<=6
Then how to modify the code in objective function (Page 3)

Thanks and regards,
Mahesh.

27 May 2014 Nitinvarman

nils, Even after making the change I get values for constraints only in the first generation, For the rest I get only zeroes. Is there any probable solution for it?

23 Apr 2014 nils

Sorry, last post was wrong. I meant:

% Save the objective values and constraint violations
indi.obj = y;
if( ~isempty(indi.cons) )
indi.cons = cons; % <<<< ADDED LINE >>>
idx = find( cons );

23 Apr 2014 nils

Great work, thanks a lot for sharing!
In the first few generations, some individuals of the population have violated constraints. I was expecting to find the actual contraints variables in results.pops.cons, but there were all zero. I only found the *number* of violations in results.pops.nViol.

I was able to improve this by adding one line in evaluate.m:

% Save the objective values and constraint violations
indi.obj = y; % <<<< ADDED LINE >>>
if( ~isempty(indi.cons) )
indi.cons = cons;
idx = find( cons );

04 Mar 2014 Damjan

Another question which is related to the previous one: how can I write equality constraints? For example:

x(1)*x(4)=x(2)+x(3)

04 Mar 2014 Damjan

Can someone help how to write a binary constraint, in particular a variable to take 1 or 0 value. I am working on a facility location problem and I need YES/NO decision constraints. One idea that I got (not working) was putting the boundaries of the variables 0 and 1, and plus writing a constraint like this:

if (x(1)==0)
cons(22) = x(2) - 1;
else
cons(23) = x(1) - 1;
end

I want the function to choose between the variable x(1) or x(2)

21 Feb 2014 Melissa

Iman or Ivan, thanks for your response. In the code I have tried the following but still cant get a maximum optimization (still negative values).

options.objfun = @(-NSGA2_Objfun);
*doesn't work still looking up @ function properties in matlab.

Or within the NSGA2_Objfun I multiple the final result by negative one.

21 Feb 2014 Abdulkadir Celik

Dear Song Lin,

Thanks for your great work. I am researching on cognitive radios and use NPGM with integer coding. I have an binary assignment matrix and a cost matrix. Each population member represents an assignment matrix and the objective evaluated based on cost.

Setting:
options.numVar=90
options.vartype=2

Each solution is a vector of size 90 with integer values in it. Even though, I set the 'options.vartype=2' for integer optimization, at the output result, I have seen real values in population member. How can I fix this issue? Thanks for your great effort and help.

07 Feb 2014 Carlos Oliveira

Hello to all,
I want to maximize an objective and minimize other? How can I make this code? I'm having some difficulties.

16 Jan 2014 Iman

Dear Pedram,
Dear All,
I have a similar problem.Although my problem is multi-objective, I need to reach a definite result in the end not an array of compromised results as Pareto suggests.I have used fuzzy decision making to satisfy this need but I don't know how I can justify the solution is the best compromised one.For this reason I thought about aggregating objectives or using e-constraints methods which considers one main objective and the rest are applied as constraints.Since my programming skill is limited I have been unable to implement it in this code.Do you have any idea how can I do it?
Thanks

16 Jan 2014 Iman

Dear Melissa
Another way of getting maximized objectives is by inversing them.If F(x)=x is an increasing function then F(x)=1/x is a decreasing one

13 Jan 2014 Ivan

... ? Just multiply the final objective function value by -1.

07 Jan 2014 Melissa

Hi all,
Can anyone give me an example on how to maximize an objective function? I understand multiplying by negative one but its only producing negative results.
Thanks!!

05 Jan 2014 pedram

Hi everyone
I have a NSGA-II Matlab code and I have 3 objective function and 3 Variable I'm going to use Level Diagram Method to convert 3 objective function to one objective function in addition This objective functions are in conflict with each other but for this method I need to have Pareto point first could anyone help me to add this part to my NSGA code and find Pareto points and draw Pareto frontier too.
Best Regards

05 Dec 2013 Francesco

I confirm, there is a small (but potentially dangerous) bug. The value of the constraint violation is not inserted into the individual info, thus it is zero both in the txt file and in the result Matlab variable.
Just add a line:
indi.cons= cons;
at the end of the evaluate.m file

25 Aug 2013 Tiago

To those having the problems in file ndsort.m, line 259: Expression or statement is incorrect--possibly unbalanced (, {, or [.,

change the line to:

[temp,ix] = sort(normDistance(:, ipt));

It seems to work fine then.

09 Apr 2013 Remsus

Hi, thanks for the code i like it a lot. I had to take a deeper look at the code, because in the populations.txt file the constraints are always zero. even for the TP_CONSTR example when the c in the function evaluation is not zero.

i think there should be another line on the bottom in the evaluation.m file.

% Save the objective values and constraint violations
indi.obj = y;
if( ~isempty(indi.cons) )
idx = find( cons );
if( ~isempty(idx) )
indi.nViol = length(idx);
indi.violSum = sum( abs(cons) );
indi.cons =cons; %added line!
else
indi.nViol = 0;
indi.violSum = 0;
end
end

Could you or some body else please also check if that is right? and that i am not messing up something else by doing this?
Cheers

06 Apr 2013 Li Liu  
11 Mar 2013 Iman

Dear all,
anyone has used this optimization in power system?

20 Nov 2012 imfactory

it can work if change "1-sum(x)=0" into " 1-sum(x)>0 and sum(x)-1>0 " , and it can't get your result if just express one of the variables as one minus the sum of the rest. I have varified the two above methods. in addition, I have tried to turn the constraints to one of the objection, such as y=1/(abs(1-sum(x))+eps), also failed.

20 Nov 2012 Ivan

imfactory, would you mind sharing how did you achieve it? I guess it is not just by expressing one of the variables as one minus the sum of the rest?

20 Nov 2012 imfactory

done.

19 Nov 2012 imfactory

Dear all,How to add contraints such as "sum(x)=1"? thanks in advance.

03 Oct 2012 Zebin

Hello,

To apply the convergence criterion to your code, is it possible?

27 Sep 2012 mimi lili

Dear SONG LIN

I wanted to run the main function (TP_CONSTR.m)of (NGPM -- A NSGA-II Program in Matlab v1.4) but it doesn't working I get the following error message:
??? Error: File: ndsort.m Line: 259 Column: 11
Expression or statement is incorrect--possibly unbalanced (, {, or [.
Error in ==> nsga2 at 82
[opt, pop] = ndsort(opt, pop);
Error in ==> TP_CONSTR at 24
result = nsga2(options); % begin the optimization!

27 Sep 2012 mimi lili

I wanted to run the main function (TP_CONSTR.m)of (NGPM -- A NSGA-II Program in Matlab v1.4) but it doesn't working I get the following error message:

??? Error: File: ndsort.m Line: 259 Column: 11
Expression or statement is incorrect--possibly unbalanced (, {, or [.

Error in ==> nsga2 at 82
[opt, pop] = ndsort(opt, pop);

Error in ==> TP_CONSTR at 24
result = nsga2(options); % begin the optimization!

24 Jul 2012 Iman

Dear Song Lin,
Dear all
Is there anyway t hat I can apply constraints on variables that are not part of design variables?
For example one of my Objective Functions is Pl and this is a function of x which is my design variable.The thing is that Pl also depends on another variable(here named as V) which is not in design variable .
Is it possible to do so?
Thanks

11 Jul 2012 mimi lili

hello
please, how can I handle the constraintes in nsga2 code in matlab

11 Jun 2012 Iman

Dear Kalyani Mahanthesh,
From where you can change mutation and cross over fraction?
Thanks
Iman

04 May 2012 escato carreira

verification of lb and ub: have lb twice intead of lb and ub.

if( length(opt.lb)~=opt.numVar || length(opt.lb)~=opt.numVar )

03 May 2012 Kalyani Mahanthesh

In addition to the above furnished fact,please note that the no. of generation and population size are both set to 500

03 May 2012 Kalyani Mahanthesh

Hi Song,

I am using your NGPM code to solve a 2 objective optimization problem.
There are around 3 constraints.It is a min-max problem.So I am appending the second objective with a minus sign.

There are 30 decision variables(all real).

The mutation and xover fractions are set to 0.002 and 0.9 respectively.I am using parallel processing,with two worker threads.

The problem that I'm facing is that the algorithm fails to discover the pareto-front,could you please let me know what could be the possible reason behind this?

Please note that the objectives are not strictly conflicting.

08 Mar 2012 Andreas

Hello Iman!

With limiting by constraints the algorithm worked very slowly, so I did the following:
First of all, let me explain my problem to you: I have to develop an electric machine but I can only use some diameters for the winding.
To solve the problem I round the design variable for the diameter to the next possible value at the beginning of the file TP_CONSTR_objfun. That means the algorithm works with the "admissible" diameters. In the populations.txt-file still stands the "not-admissible" value for the diameter, but since the algorithm doesn't work with this value but because of my rounding with the admissible one, this doesn't matter.
All you have to do is to round the result in populations.txt by your own.
Hope you can understand me.

Regards
Andreas

06 Mar 2012 Iman

Dear Andreas , I limit my design variables only by the means of constraints . I don't know any other way;however, your idea seems intesrting.Please let me know if you found the answer.

05 Mar 2012 Andreas

Hello!
I've got another question and it would be nice if you could help me one more time.
I have 3 design variables but the third one can only reach certain values. Now my question is:
Can I specify a matrix or something similar for this variable which contains the reachable values so that the algorithm does not have to search the whole "solution space"?
I know that I could do it with constraints but does also a "smarter" solution exist?
Thanks in advance for your answer.
Andreas

29 Feb 2012 Andreas

Thanks for your answer, Iman.

29 Feb 2012 Iman

Dear Andreas,
NGPM uses integer coding to handle discrete design variables. You can use options.vartype to define integer coding. More info could be found in the manual document .

29 Feb 2012 Andreas

Hello to all!
How can I specify the format type of the solution parameters? For example, I would like to have only integer values for x1, but x2 should be of type double.
Hope you can help me.
Best wishes!
Andreas

26 Jan 2012 Jonathan Roy

I get this error (Undefined function or method 'ndsort' for input arguments of type 'struct') when function nsga2 call "fct ndsort".
Some one seen this error before and can help me?

10 Jan 2012 Iman

Dear All,
1-What are the default values for crossover and mutation?
From the document we know that crossover could be changed to 1 by “options.crossover={'intermediate', 1};”
and mutation could be changed by options.mutation = {'gaussian', scale, shrink} .If we don't add those line what are the default values?where it is written?
2-Do we need a constant number for scale and shrink ? for example is
options.mutation = {'gaussian', 0.5, 0.6} correct?
Thanks for your time and patience

23 Dec 2011 Song Lin

Hello, Iman. If x(1)=1, the x(3), x(4), x(6), x(7) values do not affect the objective values. These design variables can be ignored when you process the optimzation results. The optimization progress is not affected except for the efficiency. You may need more optimzation generations to get a good result.

21 Dec 2011 Iman

Dear Song Lin,
Do u have any idea regarding my question asked on 09 Dec?

21 Dec 2011 Song Lin

I forgot to save the constraint variables to the individual structure in the function 'evalIndividual' in file 'evaluate.m'.

Modify the code as below:

...
indi.obj = y;
indi.cons = cons; // Add this line
if( ~isempty(indi.cons) )
idx = find( cons );
...

19 Dec 2011 Andreas

Is it possible that the constraints in the output file "populations.txt" are not displayed? They are calculated correctly in the Matlab-workspace, but in "populations.txt" there stands only zero at the constraints' place.
Does anybody have any idea?

09 Dec 2011 Iman

Dear All
I have a question about defining objective function.
As far as the number of design variables are fixed, there is no problem in defining the objective functions. For example my objective function works very well even if it calls another function in it:
function [y, cons] = TP_Test_objfun(x)
y = [0,0];
cons = [];
[Vm, Pl] = MyFunction (x(1),x(2));
SUM=0;
for k=1:14
SUM=(((1.060-Vm(k))/1.060).^2)+SUM;
end
y(1)=SUM;
y(2) = Pl;

But the problems begin when other design variables depends on the first design variable.
For example if x(1)=1 the MyFunction1 should be called with other two design variables x (2), x(5)
If x(1)=2, the MyFunction2 should be called with other design variables x(2),x(3),x(5),x(6)
Is it correct to write the code as follows for my problem?
function [y, cons] = TP_Test_objfun(x)
y = [0,0];
cons = [];
switch x(1)
case 1
[Vm, Pl] = MyFunction1 (x(1),x(2),x(5));

case 2
[Vm, Pl] = MyFunction2 (x(1),x(2),x(3),x(5),x(6));
case 3
[Vm, Pl] = MyFunction3 (x(1),x(2),x(3),x(4),x(5),x(6),x(7));
end
SUM=0;
for k=1:14
SUM=(((1.060-Vm(k))/1.060).^2)+SUM;
end
y(1)=SUM;
y(2) = Pl;
Is it correct? It is a bit confusing since in population .txt I see all other six design variables (x(2),x(3),x(4),x(5),x(6),x(7)) even for case 1
Thank you for your time and concern

01 Dec 2011 Iman

Dear all ,Ignore my two comments on 30 Nov.It is resolved.Thank you

30 Nov 2011 Iman

Regarding my question on 30 Nov 2011 , I should also mention that I changed options.vartype =[2] to options.vartype =[2 1];as my second design variable is real but still have the error as :
??? Subscript indices must either be real positive integers or logicals.

30 Nov 2011 Iman

Dear Lin,
Thanks for your answer regarding population. There is another question and I hope that you or any other people in here would help me out.
Right now I am using one design variable which uses Newton Raphson calculations by a function name as Raphson(x), thus in the objfun m file we have:
function [y, cons] = TP_Test_objfun(x)
y = [0,0];
cons = [];
[Vm, Pl] = Raphson(x);
y(1)=Vm;
y(2) = Pl;
Now I want to have two design variable so I change [Vm, Pl] = Raphson (x(1),x(2));
I added a new bounds for the second design variable as :
options.lb = [2 5]; % lower bound of x
options.ub = [14 25]; % upper bound of x
and also options.numVar = 2;
Consequently I changed the Raphson function as :
function [Vm, Pl] = Raphson(n,m) and changed a constant value with m.
But I unfortunately my program gives me this error:
??? Subscript indices must either be real positive integers or logicals.
Error in ==> Raphson at 34
mpc.gen (n,PG) = m; %add 10 MW to the bus located at row n (if row 7 so it is
added to bus 7)
Error in ==> TP_Test_objfun at 4
[Vm, Pl] = Raphson (x(1),x(2));
Error in ==> evaluate>evalIndividual at 67
[y, cons] = objfun( indi.var, varargin{:} );
Error in ==> evaluate at 45
[pop(i), allTime(i)] = evalIndividual(pop(i), opt.objfun, varargin{:});
Error in ==> nsga2 at 81
[pop, state] = evaluate(opt, pop, state, varargin{:});
Error in ==> TP_Test at 28
result = nsga2(options); % begin the optimization!

It looks like that the program have a problem in Raphson finction but this seems unlikely since Raphson works quite well with one variable and the only change that I have made in Raphhson is exchanging one constant with a value .
Do you think that I need to define it differently?
Thank you in advance

25 Nov 2011 Ivan  
25 Nov 2011 Song Lin

Hi Iman,
You can check the result file(the default file name is "populations.txt"), or you can use command "vertcat(result.pops(end,:).var)" to combine all of the design variables together.

24 Nov 2011 Ivan

Yes, very well written too! Congratulations on the good work !

24 Nov 2011 Iman

Dear all,
I defined my two objective functions and got only three points as a solutions (in a Pareto front),thanks to Song. One of them looks like a better soultion .How can I extract the value of x which gives me this soultion?
Best regards

15 Jul 2011 Song Lin

The original code could not get the correct Pareto-front because the crossover and mutation strategies I used do not fit for the ZDT problem. In original code, all variables of an individual would mutate if it was selected to be mutated. In the version 1.3 code, I change the strategies to mutate several variables instead, and the correct solution could be get now.

16 May 2011 ANU  
15 May 2011 ANU

Please try running problem ZDT4 described in paper "A Fast and Elitst Multi-Objective Genetic Algorithm: NSGA-II" before using this software for your research.

It doesn't give the correct solution or even close to Deb's original implementation in c language. It seems there are bugs in this software. I did this for ZDT4 problem:

cons = zeros(1,10);
y(1) = x(1);

V = 10;
t = 0;
for i = 2:V
t = t + x(i)^2 - 10*cos(4*pi*x(i));
end

g_x = 1+10*(V-1) + t;
y(2) = g_x*(1-sqrt(x(1)/g_x));

13 May 2011 ANU

Please ignore my previous comment. It works fine with MATLAB 7.11 (2010b).

13 May 2011 ANU

Sorry, I think, your code is full of bugs... please upload the clean code again.

Updates
01 Jul 2011

(2011-07-01)v1.1
Load optimization result from file and restart a optimization from previous optimization result.

15 Jul 2011

v1.3 [2011-07-15]
1. Add: Implement reference-point-based NSGA-II procedure -- R-NSGA-II.
2. Improve: Improve efficiency.
3. Modify: Modify the crossover and mutation strategy.

26 Jul 2011

v1.4 [2011-07-26]
1. Add: Support three or more objectives visualization display in "plotnsga".
2. Add: R-NSGA-II problem: DTLZ2.
3. Improve efficiency for large generation.

Contact us