powered by

MULTIOBJECTIVE OPTIMIZATION AND GENETIC
ALGORITHMS
In this Scilab tutorial we discuss about the importance of multiobjective
optimization and we give an overview of all possible Pareto frontiers. Moreover
we show how to use the NSGA-II algorithm available in Scilab.
Level

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

www.openeering.com

Step 1: Purpose of this tutorial
It is very uncommon to have problems composed by only a single
objective when dealing with real-world industrial applications. Generallymultiple, often conflicting, objectives arise naturally in most practicaloptimization problems.
Optimizing a problem means finding a set of decision variables which
satisfies constraints and optimizes simultaneously a vector function. The
elements of the vector represent the objective functions of all decision
makers. This vector optimization leads to a non-unique solution of theproblem.
For example, when selecting a vehicle that maximizes the comfort andminimizes the cost, not a single car, but a segment of cars may represent
the final optimal selections (see figure).

After a general introduction on multiobjective optimization, the final aim of
this tutorial is to introduce the reader to multiobjective optimization inScilab and particularly to the use of the NSGA II algorithm.

(Example of car classification)

Step 2: Roadmap
In the first part of the tutorial we review some concepts on multiobjectiveoptimization, then we show how to use NSGA-II algorithm in Scilab.
Steps 14 to 16 present some examples and exercises.
Step 17 shows how to call external (black-box) functions in Scilab.

Descriptions
Multiobjective optimization
NSGA 2
Examples and exercises
Calling external functions
Conclusion and remarks

Steps
3-5
6-13
14-16
1718-19

Multiobjective optimization with NSGA-II
www.openeering.com

page 2/16

Step 3: Multiobjective scenario
Here we consider, without loss of generality, the minimization of two
objectives all equally important, where no additional information about
the problem is available.
A solution of the problem can be described by a “decision vector” of
the formlying in the design space . The evaluation of thetwo objective functions on
produces a solution
in theobjective space , i.e. is a vector map of the form:.
Comparing two solutions
andrequires to define a dominancecriteria. In modern multiobjective optimization the Pareto criteria is themost used. This criteria states:
An objective vector
is said to dominate another objectivevector(i.e.,) if no component ofis greater than thecorresponding components ofand at least one component isgreater;accordingly, the solution;

dominates, ifdominates

all non-dominated solutions are the optimal solutions of theproblem, solutions not dominated by any others. The set of thesesolutions is named Pareto set while its image in objective spaceis named Pareto front.
A generic multiobjective optimization solver searches for non-dominatedsolutions that correspond to trade-offs between all the objectives.
The utopia (or ideal) point corresponds to the minimal of all the objectives
and typically is not a real and feasible point.

Multiobjective optimization with NSGA-II
www.openeering.com

page 3/16

Step 4: Type of Pareto fronts
The computation of the Pareto front can be a very difficult task. Many
obstacles can make the problem complex: non-continuous design space,high-dimensionality and clustered solutions. Moreover, in a similarmanner as local optimal points can trap algorithms in single objectiveproblems, local Pareto frontiers can cause bad convergence of themultiobjective optimization approaches.
Two very typical Pareto fronts can arise when solving multiobjective
optimization problems:Convex front
This is the most interest case for decision makers. When the Pareto
front has this shape, the decision makers can negotiate, fighting fortheir own objective and they can more easily agree for a trade-off
point. In this situation, the trade-off is much better than the linear
combination of the original objectives. This means, practically, that if adecision maker gives up a percentage of its target, say 20%, anotherdecision maker may have an improvement of more than 20% on hispersonal target.

(Convex front)

Non-convex front:
This is the opposite of the previous situation, negotiation between
decision markers is harder. Here, a decision maker should give up
more than 20% of his goal to give at least 20% advantage to anotherdecision maker. The final solution depends more on the influence ofthe decision maker rather than on a “democratic” negotiation.
Discontinuous fronts are common and more complex to analyze, any
piece of a discontinuous front may be reduced to the two previous cases.
(Non-convex front)

Multiobjective optimization with NSGA-II
www.openeering.com

page 4/16

-

Step 5: Evolution algorithms
Many algorithms are based on a stochastic search approach such as
evolution algorithm, simulating annealing, genetic algorithm.

The idea of these kind of algorithms is the following:
1. Define a memory that contains current solutions;
2. Define a selection module that determines which of thepreviously solutions should be kept in memory. Two types ofselection are available:-

Mating selection which consists of a fitness selection
phase where promising solutions are picked for variation;-

Environmental selection that determines which of storedsolutions are kept into the memory.

3. Define a variation module that takes a set of solutions andsystematically, or randomly, modifies these solutions to generatepotentially better solutions using specific operators such as:-

Crossover which produces new individuals combining
the information of two or more parents;-Mutation which alters individuals with low probability ofsurvival.

When we consider an evolution algorithm, by analogy to natural evolution,
we call solutions as candidates and the set of candidates as population.
The fitness function is a particular objective function that characterizes
the problem measuring how close a given solution is to achieve thetarget, considering also all problem constraints.

Multiobjective optimization with NSGA-II
www.openeering.com

page 5/16

Scilab syntax:

Step 6: NGSA-II
NSGA-II is the second version of the famous “Non-dominated Sorting
Genetic Algorithm” based on the work of Prof. Kalyanmoy Deb forsolving non-convex and non-smooth single and multiobjective
optimization problems.

[pop_opt,fobj_pop_opt,pop_init,fobj_pop_init] =optim_nsga2(ga_f,pop_size,nb_generation,p_mut,p_cross,Log,param)

Input arguments:
ga_f: the function to be optimized;
pop_size: the size of the population of individuals;
nb_generation: the number of generations to be computed;
p_mut: the mutation probability;
p_cross: the crossover probability;
Log: if %T, we will display to information message during the run of
the genetic algorithm;
param: a list of parameters:'codage_func': the function which will perform the coding
and decoding of individuals;'init_func': the function which will perform the initialization of
the population;'crossover_func': the function which will perform thecrossover between two individuals;'mutation_func': the function which will perform themutation of one individual;'selection_func': the function which will perform theselection of individuals at the end of a generation;'nb_couples': the number of couples which will be selectedso as to perform the crossover and mutation;'pressure': the value the efficiency of the worst individual.

Its main features are:A sorting non-dominated procedure where all the individual aresorted according to the level of non-domination;
It implements elitism which stores all non-dominated solutions,and hence enhancing convergence properties;
It adapts a suitable automatic mechanics based on the crowding
distance in order to guarantee diversity and spread of solutions;
Constraints are implemented using a modified definition ofdominance without the use of penalty functions.

The Scilab function that implements the NSGA-II algorithm is:

optim_nsga2

which is directly available with Scilab installation.

Output Parameters:
pop_opt: the population of optimal individuals;
fobj_pop_opt: the set of objective function values associated topop_opt;
pop_init: the initial population of individuals;
fobj_pop_init: the set of objective function values associated topop_init (optional).

Multiobjective optimization with NSGA-II
www.openeering.com

page 6/16

Step 7: Problem ZDT1The ZDT1 problem consists of solving the following multiobjective
optimization problem:where the object functions areand(Optimal Pareto front for n=2)

On the left we report the optimal Pareto front defined byThis function has a continuous optimal Pareto front. Moving along thefrontier, from left to right, we improve the value ofmaking the objectivefunction worse.

(Pareto Set Points for n=2)

Multiobjective optimization with NSGA-II
www.openeering.com

page 7/16

Step 8: Creating the ZDT1 function
In this first step, we create the "zdt1" function and its boundaries.

Please note that the function ZDT1 returns a horizontal vector ofmultiobjective functions evaluations.

In the boundary functions we even define the problem dimension.

// ZDT1 multiobjective function
function f=zdt1(x)f1 = x(1);g = 1 + 9 * sum(x(2:$)) / (length(x)-1);
h = 1 - sqrt(f1 ./ g);
f = [f1, g.*h];endfunction// Min boundary function
function Res=min_bd_zdt1(n)Res = zeros(n,1);
endfunction// Max boundary function
function Res=max_bd_zdt1(n)Res = ones(n,1);
endfunction

Step 9: Set NSGA-II parameters
In this step, we set algorithm parameters and problem dimension.

// Problem dimension
dim = 2;// Example of use of the genetic algorithm
funcname= 'zdt1';
PopSize= 500;
Proba_cross = 0.7;
Proba_mut= 0.1;
NbGen= 10;
NbCouples= 110;
Log= %T;
pressure= 0.1;

Multiobjective optimization with NSGA-II
www.openeering.com

page 8/16

Step 10: Set NSGA-II main functions
Here, we set the NSGA-II main functions. In our case, since the problem
is continuous we use the default NSGA functions.
In case of more complex mathematical optimization problem, the user caneasily change the NSGA-II operators. For example, the user may define
his own "mutation_func" function describing a mutation operation that
perfectly fits with the problem at hand. The same can be done for"crossover_func" function or for the internal coding "codage_func".

// Setting parameters of optim_nsga2 function
ga_params = init_param();// Parameters to adapt to the shape of the optimization
problem
ga_params =add_param(ga_params,'minbound',min_bd_zdt1(dim));ga_params =add_param(ga_params,'maxbound',max_bd_zdt1(dim));ga_params = add_param(ga_params,'dimension',dim);
ga_params = add_param(ga_params,'beta',0);ga_params = add_param(ga_params,'delta',0.1);// Parameters to fine tune the Genetic algorithm.
// All these parameters are optional for continuousoptimization.
// If you need to adapt the GA to a special problem.
ga_params =add_param(ga_params,'init_func',init_ga_default);
ga_params =add_param(ga_params,'crossover_func',crossover_ga_default);
ga_params =add_param(ga_params,'mutation_func',mutation_ga_default);
ga_params =add_param(ga_params,'codage_func',coding_ga_identity);
ga_params = add_param(ga_params,'nb_couples',NbCouples);ga_params = add_param(ga_params,'pressure',pressure);// Define s function shortcut
deff('y=fobjs(x)','y = zdt1(x);');

Step 11: Performing optimization
The multiobjective optimization is performed using the command"optim_nsga2". Other methods are available, see for example:
optim_moga: multiobjective genetic algorithm;// Performing optimization
printf("Performing optimization:");[pop_opt, fobj_pop_opt, pop_init, fobj_pop_init] =optim_nsga2(fobjs, PopSize, NbGen, Proba_mut,Proba_cross, Log, ga_params);

optim_ga: A flexible genetic algorithm;
optim_nsga: A multiobjective Niched Sharing Genetic Algorithm.

Multiobjective optimization with NSGA-II
www.openeering.com

page 9/16

Step 12: Plot the Pareto front
The Pareto front is obtained using the "pareto_filter" Scilab
command, which automatically extracts non dominated solutions from a
set of multiobjective and multidimensional solutions.

In order to plot the “population” it is necessary to convert the list
"pop_pareto" to a vector using the command “list2vec“.

// Compute Pareto front and filter[f_pareto,pop_pareto] =pareto_filter(fobj_pop_opt,pop_opt);// Optimal front function definition
f1_opt = linspace(0,1);
f2_opt = 1 - sqrt(f1_opt);// Plot solution: Pareto front
scf(1);// Plotting final population
plot(fobj_pop_opt(:,1),fobj_pop_opt(:,2),'g.');// Plotting Pareto population
plot(f_pareto(:,1),f_pareto(:,2),'k.');plot(f1_opt, f2_opt, 'k-');title("Pareto front","fontsize",3);xlabel("$f_1$","fontsize",4);ylabel("$f_2$","fontsize",4);legend(['Final pop.','Pareto pop.','Pareto front.']);// Transform list to vector for plotting Pareto set
npop = length(pop_opt);
pop_opt = matrix(list2vec(pop_opt),dim,npop)';nfpop = length(pop_pareto);
pop_pareto = matrix(list2vec(pop_pareto),dim,nfpop)';// Plot the Pareto set
scf(2);// Plotting final population
plot(pop_opt(:,1),pop_opt(:,2),'g.');// Plotting Pareto population
plot(pop_pareto(:,1),pop_pareto(:,2),'k.');title("Pareto Set","fontsize",3);xlabel("$x_1$","fontsize",4);ylabel("$x_2$","fontsize",4);legend(['Final pop.','Pareto pop.']);

Multiobjective optimization with NSGA-II
www.openeering.com

page 10/16

Step 13: Some results
Here, we report some results obtained running NSGA-II with the ZDT1
and changing the number of generations (parameter “NbGen“).
NbGen takes values from the set (5,10,15,20).

(NbGen = 5)

(NbGen = 10)(NbGen = 15)(NbGen = 20)

Multiobjective optimization with NSGA-II
www.openeering.com

page 11/16

Step 14: Exercise #1: ZDT2 problem
Solve for the ZDT2 problem consists of solving the following
multiobjective optimization problem:

where the two object functions areand(Optimal Pareto front for n=2)

In the left we have reported the optimal Pareto front defined byThis function presents a continuous non-convex optimal Pareto front.

(Pareto Set Points for n=2)

Multiobjective optimization with NSGA-II
www.openeering.com

page 12/16

Step 15: Exercise #2: ZDT3 problem
Solve for the ZDT3 problem consists of solving the following
multiobjective optimization problem:

where the two object functions areand(Optimal Pareto front)

In the left we have reported the optimal Pareto front defined bywithdefined as

This function has a discontinuous optimal Pareto front.
(Pareto Set Points for n=2)

Multiobjective optimization with NSGA-II
www.openeering.com

page 13/16

Step 16: Exercise #3
Modify the ZDT1 program in order to plot the population at each step.
Hints:Create a global variable named “currPop“ where to save thepopulation at each time step;
Create an initial function for the optim_nsga2 named“init_ga_previous“ that loads the computed population ateach step except the initial step where the original init function
must be called.
Add plot at each time step
If you want to produce a video or animate png save each plotusing the command “xs2png“ (for example an animated png
image can be created using the program JapngEditor).
// Create a global variableglobal currPop;// Create a function for initialize the global variable
function Pop_init=init_ga_previous(popsize, param)
global currPop;
Pop_init = currPop;
endfunction// Performing optimization
for i=1:NbGen// Call optim_nsga2 with a local number of generation equals
to 1
if i>1// Change init generation function
end// Save population
currPop = pop_opt;// filtering and Plotting data
end

Multiobjective optimization with NSGA-II
www.openeering.com

page 14/16

Step 17: Calling external functions

The most useful commands to integrate Scilab with your external code are:dos — shell (cmd) command execution (Windows only);
unix — shell (sh) command execution;
unix_g — shell (sh) command execution, output redirected to avariable;
unix_s — shell (sh) command execution, no output ;unix_w — shell (sh) command execution, output redirected to scilab
window;
unix_x — shell (sh) command execution, output redirected to awindow;
host — Unix or DOS command execution.

Scilab, with its Input/Output functions, enables coupling to any externalfunctions and tools (even CAD, CAE, CFD) that can be called fromexternal commands.
This can be done in a very easy way as shown in several examples in“Made with Scilab”:

http://www.openeering.com/made_with_scilab

Scilab can even deal with parallel computing. This represents anenormous advantage when combining optimization together withengineering simulations. This approach can speed-up time-consuming
optimization problems that are very typical in industrial applications.

Moreover, if simulation time is still too demanding, Scilab can takeadvantage of several meta-modeling techniques such as Kriging, DACE,
neural networks, etc.

// Windows only example[s,w] = dos('dir');// general syntax to run my simulation code with options
in Windows systems//[s, w] = dos('mysimulation.exe /option')//Run list or dir according to operating systems
if getos() == 'Windows' thenunix_w("dir "+'""'+WSCI+"\modules"+'""');
else
unix_w("ls $SCI/modules");end

If you are interested in integrating your simulation code into Scilab forsolving specific optimization problem, please do not hesitate to contact
the Openeering team.

Multiobjective optimization with NSGA-II
www.openeering.com

page 15/16

Step 18: Concluding remarks and References
1. Scilab Web Page: Available: www.scilab.org.
In this Scilab tutorial we have shown how to use the NSGA-II within
Scilab.

2. Openeering: www.openeering.com.
3. ZDT1, ZDT2 and ZDT3 documentation:

On the right-hand column you may find a list of interesting references forfurther studies.

http://www.tik.ee.ethz.ch/sop/download/supplementary/testproblems/
4. JapngEditor : https://www.reto-hoehener.ch/japng/

Step 19: Software content
To report bugs or suggest improvements please contact the Openeering
team.
---------------NSGA 2 IN SCILAB----------------

www.openeering.com.

-------------Main directory-------------example_steps.sce
example_ZDT1.sce
example_ZDT2.sce
example_ZDT3.sce
front_plots.sce
license.txt: Exercise 1: Example for the ZDT1 function: Example for the ZDT2 function: Example for the ZDT3 function: Plots Pareto fronts and sets
: The license fileThank you for your attention,
Manolo Venturin and Silvia Poles

Multiobjective optimization with NSGA-II
www.openeering.com

page 16/16