Optimization::NSGAII - non dominant sorting genetic algorithm for multi-objective optimization (also known as NSGA2)
Version 0.03
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);
f_Optim_NSGAII
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
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.
NSGAII.pm
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)
f_to_optimize
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:
nProc
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.
nPop
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:
filesDir
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.
startPop
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.
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:
percentMut
-> Small perturbation of the each gene by adding a number chosen randomly from the given distrib (scaled with both scaleDistrib and the difference between the two bounds).
distrib
scaleDistrib
-> Random change (inside the permitted bounds)
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.
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], } );
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]
Following the instruction in perlmodinstall:
download the Optimization-NSGAII-X.XX.tar.gz
decompress and unpack
gzip -d Optimization-NSGAII-X.XX.tar.gz
tar -xof Optimization-NSGAII-X.XX.tar
cd Optimization-NSGAII-X.XX
perl Makefile.PL
make
make test
make install
to install it locally use this instead of perl Makefile.PL:
perl Makefile.PL PREFIX=/my/folder if 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 using use Optimization::NSGAII qw/ f_Optim_NSGAII /;
perl Makefile.PL PREFIX=/my/folder
use lib "path/before(Optimization/NSGAII.pm);"
use Optimization::NSGAII qw/ f_Optim_NSGAII /;
Dario Rubino, <drubino at cpan.org>
<drubino at cpan.org>
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.
bug-optimization-nsgaii at rt.cpan.org
You can find documentation for this module with the perldoc command.
perldoc Optimization::NSGAII
You 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
https://cpanratings.perl.org/d/Optimization-NSGAII
Search CPAN
https://metacpan.org/release/Optimization-NSGAII
This software is Copyright (c) 2022 by Dario Rubino.
This is free software, licensed under:
The Artistic License 2.0 (GPL Compatible)
To install Optimization::NSGAII, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Optimization::NSGAII
CPAN shell
perl -MCPAN -e shell install Optimization::NSGAII
For more information on module installation, please visit the detailed CPAN module installation guide.