NAME
Optimization::NSGAII - non dominant sorting genetic algorithm for multi-objective optimization (also known as NSGA2)
VERSION
Version 0.03
SYNOPSIS
use Optimization::NSGAII qw/ f_Optim_NSGAII /;
use Data::Dumper;
# D E F I N E O B J E C T I V E S T O O P T I M I Z E
###########################################################
sub f_to_optimize {
my $x = shift; # load input parameters (genes constituting a single individual)
my $id = shift # load id of this particular individual of the population
# ... # do your things using these inputs $x->[0], $x->[1] ...
# and produce the outputs to be minimized $f1, $f2 ...
# examples of things you can do include:
# - mathematical formulas in perl to define $f1, $f2, ...
# - computations with commercial software and so:
# - create a directory using $id in the name
# - write input file using $x->[0] ...
# - run the computation, for example with perl system() function
# - locally or
# - on a server for example with 'qsub... '
# - wait simulation to end
# - postprocess its output and define $f1, $f2 ...
# - delete directory and contents
# - ...
my $out = [$f1,$f2,$f3]; # and finally return the set of these outputs for
return $out; # this single individual of the population
}
# D E F I N E B O U N D S [ A N D I N E Q U A L I T I E S ]
###################################################################
# define min and max bounds for $x->[0], $x->[1], ...
my $bounds = [[0,1],[0,1],[0,1]]; # example with 3 input parameters (genes) with min = 0 and max = 1:
sub f_inequality { # optional inequality constraints set
my $x =shift;
my @ineq =
(
$x->[1] + 1 , # equations >= 0
$x->[0] + $x->[1] - 9,
...
...
);
return \@ineq;
}
# R U N O P T I M I Z A T I O N
#################################
# execute NSGA-II algorithm
my $ref_input_output = f_Optim_NSGAII(
{
'nPop' => 50, # population size
'nGen' => 250, # final generation number
'bounds' => $bounds, # loads the previously defined bounds
'function' => \&f_to_optimize, # loads the subroutine to optimize (minimize)
'nProc' => 8, # how many individuals to evaluate in parallel as separate processes
'filesDir' => '/tmp', # work directory
# optional parameters:
'verboseFinal' => 1, # 0|1: input and output values print at final generation, for each individual of the population
# default: print is made ( = 1)
'f_ineq' => \&f_inequality, # subroutine describing the constraining inequality set
# default: no constraint function
# parameters for mutation
'distrib' => [-1,0,1], # distribution of values (for example a Gaussian distribution), used to perturb individuals
# default: [-1,-0.5,0,0.5,1]
'scaleDistrib' => 0.05, # scaling of the distribution array
# default: 0 (no perturbation will be done)
'percentMut' => 5, # percentage of individual that are randomly perturbated (in all their genes)
# and also percentage of input parameters (genes) that are randomly mutated in each individual
# default: 5%
'startPop' => [[0.3,0.18,-0.1],# initial population
[-0.38,0.5,0.1], # default: random population satisfying the bounds
...,
]
},
# the following is the optional set of parameters for 'Pareto front' 2D live plot
# if the part below is not present, no plot will be made
{
'dx' => 200, # characters width and height of the plot
'dy' => 40,
'xlabel' => 'stiffness [N/mm]', # horizontal and vertical axis labels
'ylabel' => 'mass [kg]',
'xlim' => [0,1], # horizontal and vertical axis limits
'ylim' => [0,1],
'nfun' => [0,2], # which function to plot from return value by f_to_optimize ($out) ; 0=f1, 1=f2 ...
}
);
# U S E S O L U T I O N S
############################
# for example print of the input parameters and
# corresponding output functions' values of the final found Pareto front
my @ref_input = @{$ref_input_output->[0]};
my @ref_output = @{$ref_input_output->[1]};
print Dumper(\@ref_input);
print Dumper(\@ref_output);EXPORT
f_Optim_NSGAII
DESCRIPTION
Reference
NSGAII.pm apply (with some variations) the NSGA-II algorithm described in the paper:
A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-II
Kalyanmoy Deb, Associate Member, IEEE, Amrit Pratap, Sameer Agarwal, and T. Meyarivan
Objective
NSGAII.pm performs multi-objective optimization using a genetic algorithm approach: it searches the input parameters (genes) which minimize a set of output functions and with some luck a Pareto front is produced. In the Pareto front no solution is better than the others because each solution is a trade-off.
Function to optimize
This module requires to define a perl subroutine (f_to_optimize in the code above) which can take the input parameters and gives the corresponding outputs (in other words, it requires a subroutine to evaluate an individual of this population)
Features
The optimization is done:
considering allowed boundary for each input parameter (min e max)
considering optional set of inequality equations containing input parameters (x1^2 + sqrt(x2) -x3 >= 0 , ...)
with a parallel evaluation of the subroutine to optimize (and so of individuals) in each generation, by using perl fork() function
The inequalities must be given by a subroutine which calculate the error, look below in the example: basically all the LHS of the inequalities in the form "... >=0" are put in an array.
The number of parallel evaluation of f_to_optimize, and so the value of nProc, can be for example the max number of parallel f_to_optimize computation that you want and can:
run on your pc if you run the computation locally (e.g. 4)
run on a remote server if you run (inside the
f_to_optimize) the computation there (e.g. 32)
nPop should be multiple of nProc, to optimize resources use, but it is not necessary.
Problems with this modules are expected on systems not supporting fork() perl function.
A 2D plot can be activated to control in real time the convergence of the algorithm on two chosen output functions (to assist at the formation of the Pareto front, generation after generation).
Each time a new generation finish, all information of the population are written in the filesDir directory:
VPt_genXXXXX.txt: input (parameters values)
Pt_genXXXXX.txt: output (corresponding functions values)
The algorithm can start by default with a random initial population (satisfying the bounds) or the start population can be assigned by assigning it to the startPop option.
Assigning the population at the start can be useful for example if:
there was an unexpected termination of the program during the optimization, so that one can restart by using the content of one of the last saved VPt_genXXXXX.txt
there is the interest in continuing the optimization with different parameters
there is already an idea of some input parameters which could give a good output
For an example of use see NSGAII_startPop_example.pl.
Mutation
The implementation of the mutation algorithm part has been done in a different way if compared to that described in the paper.
In particular two mutation are applied in sequence:
- 1) mutation of all the input parameters (the genes), but only on a certain percentage
percentMutof the population: -
-> Small perturbation of the each gene by adding a number chosen randomly from the given
distrib(scaled with bothscaleDistriband the difference between the two bounds). - 2) mutation of all the individuals of the population, but only on a certain percentage
percentMutof the input parameters (the genes) -
-> Random change (inside the permitted bounds)
Verification
This module has been tested, successfully, on many of the test problems defined in the paper described in the Reference section (see EXAMPLE section)
The performance (convergence for same population number and max generation number) seems to be comparable to that described in that paper.
EXAMPLE
More examples (the same test problems contained in the paper described in the Reference section) are available in the test folder (NSGAII_all_examples.pl containing ZDT1, ZDT2, TNK, ...).
Here you see the CONSTR problem with:
two input parameters $x->[0] and $x->[1]
two output functions to optimize f1 and f2
two constraining equations between the input parameters
8 process in parallel (8 subroutine f_CONTRS are evaluated in parallel as indipendent processes)
use Optimization::NSGAII qw/ f_Optim_NSGAII /;
# function to minimize
sub f_CONSTR {
my $x = shift;
my $n = scalar(@$x);
my $f1 = $x->[0];
my $f2 = (1 + $x->[1])/$x->[0];
my $out = [$f1,$f2];
return $out;
}
# inequality constraints set
sub f_inequality {
my $x =shift;
# equation >= 0
my @ineq =
(
$x->[1] + 9*$x->[0] - 6 ,
-$x->[1] + 9*$x->[0] -1
);
return \@ineq;
}
my $bounds = [[0.1,1],[0,5]];
my $ref_input_output = f_Optim_NSGAII(
{
'nPop' => 50,
'nGen' => 100,
'bounds' => $bounds,
'function' => \&f_CONSTR,
'f_ineq' => \&f_inequality,
'nProc' => 8,
'filesDir' => '/tmp',
'verboseFinal' => 1,
'distrib' => [-1,-0.9,-0.8,-0.7,-0.6,-0.5,-0.4,-0.3,-0.2,-0.1,0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9],
'scaleDistrib' => 0.05,
'percentMut' => 5,
},
{
'dx' => 100,
'dy' => 40,
'xlabel' => 'stiffness [N/mm]',
'ylabel' => 'mass [kg]',
'xlim' => [0.1,1],
'ylim' => [0,10],
'nfun' => [0,1],
}
);OUTPUT PREVIEW
This below is a typical output of the final Pareto front (problem TNK).
The numbers represent the rank of the points: in the initial generations you can see points of rank 1,2,3... where points with rank 1 dominate points of rank 2 and so on.
Generation after generation all the points go on the Pareto front, so all the points become rank 1 (not dominated, nothing best is present in this population)
The points will also expand to occupy the entire front.
GENERATION 250
m|
a|
s|
s|
|
[|
k|
g| 1
]| 11
| 11
| 1 1
| 11
| 1
| 11 1 1 1 1
| 1
| 1
|
| 1
| 1 1
| 1111
| 1
|
|
|
|
| 1
| 11
| 1
| 1
|
|______________________________________________________________________
stiffness [N/mm]INSTALLATION
Following the instruction in perlmodinstall:
download the Optimization-NSGAII-X.XX.tar.gz
decompress and unpack
gzip -d Optimization-NSGAII-X.XX.tar.gztar -xof Optimization-NSGAII-X.XX.tar
cd Optimization-NSGAII-X.XXperl Makefile.PLmakemake testmake installto install it locally use this instead of
perl Makefile.PL:perl Makefile.PL PREFIX=/my/folderif you want to install it in /my/folder then you will have to use in your script:use lib "path/before(Optimization/NSGAII.pm);"before usinguse Optimization::NSGAII qw/ f_Optim_NSGAII /;
AUTHOR
Dario Rubino, <drubino at cpan.org>
BUGS
Solutions (input-output pairs) often contain duplicates, this would require some investigation.
Please report any bugs to bug-optimization-nsgaii at rt.cpan.org, or through the web interface at https://rt.cpan.org/NoAuth/ReportBug.html?Queue=Optimization-NSGAII. I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.
SUPPORT
You can find documentation for this module with the perldoc command.
perldoc Optimization::NSGAIIYou can also look for information at:
RT: CPAN's request tracker (report bugs here)
https://rt.cpan.org/NoAuth/Bugs.html?Dist=Optimization-NSGAII
CPAN Ratings
Search CPAN
LICENSE AND COPYRIGHT
This software is Copyright (c) 2022 by Dario Rubino.
This is free software, licensed under:
The Artistic License 2.0 (GPL Compatible)