Scilab : parallélisation de l’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).

/////////////////////////////////////////////////////////////////////
//_______  ______    _______  _______ 
//|   _   ||    _ |  |       ||       |
//|  |_|  ||   | ||  |    ___||    _  |
//|       ||   |_||_ |   |___ |   |_| |
//|       ||    __  ||    ___||    ___|
//|   _   ||   |  | ||   |___ |   |    
//|__| |__||___|  |_||_______||___|    
// 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