optim_GA Genetic algorithm parallelization
Scilab includes a genetic algorithm in the function optim_GA
.
To save time when evaluating each individual in a generation, it is possible to parallelize the evaluations: they are independent.
Here we propose a modification to the Scilab routine optim_ga which allows a number of individuals equal to the number of computer cores to be evaluated in parallel (the reduction in calculation time is therefore proportional to the number of cores in your machine).
This is only valid under Linux, as the Windows version of Scilab 6 does not support parallelism: *In this current version of Scilab, parallel_run uses only one core on Windows platforms" (
source
).
See code
////////////////////////////////////////////////////////////////////
//_______ ______ _______ _______
//| _ || _ | | || |
//| |_| || | || | ___|| _ |
//| || |_||_ | |___ | |_| |
//| || __ || ___|| ___|
//| _ || | | || |___ | |
//|__| |__||___| |_||_______||___|
// AREP - 16, av. d'Ivry, 7501/3 Paris, FRANCE
////////////////////////////////////////////////////////////////////
// Scilab (www.scilab.org) - This file is part of Scilab
// Copyright (C) 2008 - Yann COLLETTE <yann[dot]collette[at]renault[dot]com>
// Copyright (C) 2014 - Michael Baudin <michael[dot]baudin[at]contrib[dot]scilab[dot]org>
//
// 26/6/2017 : added the "parallel_run" capability for
// the evaluation of individuals (Edouard Walther)
//
// This file must be used under the terms of the CeCILL.
// This source file is licensed as described in the file COPYING, which
// you should have received as part of this distribution. The terms
// are also available at
// http://www.cecill.info/licences/Licence_CeCILL_V2.1-en.txt //
////////////////////////////////////////////////////////////////////
// Last modification : 26/06/2017 //
////////////////////////////////////////////////////////////////////
// Contact : edouard[dot]walther[at]arep[dot]com
////////////////////////////////////////////////////////////////////
function [pop_opt, fobj_pop_opt, pop_init, fobj_pop_init] = optim_GA_parallel(ga_f, pop_size, nb_generation, p_mut, p_cross, Log, param)
[nargout, nargin] = argn();
if ~isdef("param", "local") then
param = [];
end
[codage_func, err] = get_param(param, "codage_func", coding_ga_identity);
[init_func, err] = get_param(param, "init_func", init_ga_default);
[crossover_func, err] = get_param(param, "crossover_func", crossover_ga_default);
[mutation_func, err] = get_param(param, "mutation_func", mutation_ga_default);
[selection_func, err] = get_param(param, "selection_func", selection_ga_elitist);
[nb_couples, err] = get_param(param, "nb_couples", 100);
[pressure, err] = get_param(param, "pressure", 0.05);
[output_func, err] = get_param(param, "output_func", output_ga_default);
if ~isdef("ga_f", "local") then
error(sprintf(gettext("%s: ga_f is mandatory"), "optim_ga"));
else
if typeof(ga_f) == "list" then
deff("y = _ga_f(x)", "y = ga_f(1)(x, ga_f(2:$))");
else
deff("y = _ga_f(x)", "y = ga_f(x)");
end
end
if ~isdef("pop_size", "local") then
pop_size = 100;
end
if ~isdef("nb_generation", "local") then
nb_generation = 10;
end
if ~isdef("p_mut", "local") then
p_mut = 0.1;
end
if ~isdef("p_cross", "local") then
p_cross = 0.7;
end
if ~isdef("Log", "local") then
Log = %F;
end
// Initialization of the population
Pop = list();
Pop = init_func(pop_size, param);
if (nargout >= 3) then
pop_init = Pop;
end
// Code the individuals
Pop = codage_func(Pop, "code", param);
// Getting the objective function for each individual
//disp("Extraction list...");
[vec_param_pop]=Pop(1);
vec_param_total=vec_param_pop;
for i = 2:length(Pop)
[vec_param_pop]=Pop(i);
vec_param_total=cat(2,vec_param_total,vec_param_pop);
end
// First launch
//disp("Execution for the first population...");
[FObj_Pop]=parallel_run(vec_param_total,_ga_f);
FObj_Pop=FObj_Pop';
if (nargout == 4) then
fobj_pop_init = FObj_Pop;
end
FObj_Pop_Max = max(FObj_Pop);
FObj_Pop_Min = min(FObj_Pop);
// Normalization of the efficiency
Efficiency = (1 - pressure) * (FObj_Pop_Max - FObj_Pop) / max([FObj_Pop_Max - FObj_Pop_Min %eps]) + pressure;
//disp("Starting optimisation with GA...");
// The genetic algorithm
for i = 1:nb_generation
//
// Selection
//
Indiv1 = list();
Indiv2 = list();
Wheel = cumsum(Efficiency);
for j = 1:nb_couples
// Selection of the first individual in the couple
Shoot = grand(1, 1, "unf", 0, Wheel($));
Index = find(Shoot <= Wheel, 1);
Indiv1(j) = Pop(Index);
FObj_Indiv1(j) = FObj_Pop(Index);
// Selection of the second individual in the couple
Shoot = grand(1, 1, "unf", 0, Wheel($));
Index = 1;
Index = find(Shoot <= Wheel, 1);
Indiv2(j) = Pop(Index);
FObj_Indiv2(j) = FObj_Pop(Index);
end
//
// Crossover
//
for j = 1:nb_couples
if (p_cross>grand(1, 1, "def")) then
[x1, x2] = crossover_func(Indiv1(j), Indiv2(j), param);
Indiv1(j) = x1;
Indiv2(j) = x2;
ToCompute_I1(j) = %T;
ToCompute_I2(j) = %T;
else
ToCompute_I1(j) = %F;
ToCompute_I2(j) = %F;
end
end
//
// Mutation
//
for j = 1:nb_couples
if (p_mut>grand(1, 1, "def")) then
x1 = mutation_func(Indiv1(j), param);
Indiv1(j) = x1;
ToCompute_I1(j) = %T;
end
if (p_mut>grand(1, 1, "def")) then
x2 = mutation_func(Indiv2(j), param);
Indiv2(j) = x2;
ToCompute_I2(j) = %T;
end
end
//
// Computation of the objective functions
k=0;kk=0; // counters to iterate
for j = 1:nb_couples // for all couples in the population
if ToCompute_I1(j) then// if to be computed
k=k+1;
if k==1 then // create the first vector of parameters
[vec_param_pop1]=Indiv1(j);
else // concatenate for parallel_run
[vec_param_indiv1]=Indiv1(j);
indices_indiv1(k)=j;
vec_param_pop1=cat(2,vec_param_pop1,vec_param_indiv1);
end
end
if ToCompute_I2(j) then// if to be computed
kk=kk+1;
if kk==1 then
[vec_param_pop2]=Indiv2(j);
else
[vec_param_indiv2]=Indiv2(j);
indices_indiv2(kk)=j;
vec_param_pop2=cat(2,vec_param_pop2,vec_param_indiv2);
end
end
end
// Parallel_run
//disp("Parallel launch for Indiv1...");
[objectifs_Indiv1]=parallel_run(vec_param_pop1,_ga_f);
objectifs_Indiv1=objectifs_Indiv1';
//disp("Parallel launch for Indiv2...");
[objectifs_Indiv2]=parallel_run(vec_param_pop2,_ga_f);
objectifs_Indiv2=objectifs_Indiv2';
// Updating indexes
//disp("Updating FObj1 ...");
for k=1:length(objectifs_Indiv1)
if indices_indiv1(k)<> 0 then
FObj_Indiv1(indices_indiv1(k))= objectifs_Indiv1(k);
end;
end
for k=1:length(objectifs_Indiv2)
if indices_indiv2(k)<> 0 then
FObj_Indiv2(indices_indiv2(k))= objectifs_Indiv2(k);
end;
end
// Reinit ToCompute lists
ToCompute_I1 = ToCompute_I1 & %F;
ToCompute_I2 = ToCompute_I2 & %F;
// Recombination
[Pop, FObj_Pop] = selection_func(Pop, Indiv1, Indiv2, FObj_Pop, FObj_Indiv1, FObj_Indiv2, [], [], [], param);
// Callback for plotting / printing intermediate results or stopping the algorithm
if (Log) then
stop = output_func(i, nb_generation, Pop, FObj_Pop, param);
if (stop) then
break
end
end
end
pop_opt = Pop;
pop_opt = codage_func(pop_opt, "decode", param);
fobj_pop_opt = FObj_Pop;
endfunction