Parallélisation le d’algorithme génétique optim_GA
Scilab intègre un algorithme génétique dans la fonction optim_GA
.
Pour gagner du temps lors de l’évaluation de chaque individu d’une génération, il est possible de paralléliser les évaluations : celles-ci sont indépendantes.
Nous vous proposons ici une modification de la routine Scilab optim_ga permettant d’évaluer en parallèle un nombre d’individus égal au nombre de cœurs de l’ordinateur (la réduction du temps de calcul est ainsi proportionnelle au nombre de cœurs de votre machine).
Ce fonctionnement est valide sous Linux uniquement, la version Windows de Scilab 6 ne supportant pas le parallélisme : “In this current version of Scilab, parallel_run uses only one core on Windows platforms.” (
source
).
Voir 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