Fonction d'ajustage, chromosomes, restriction d'évènement

#include <stdlib.h>
#include "module.h"

#define        RESTYPE                "dummy-type"

struct fixed {
        int tupleid;
        int resid;
};

static int fixed_num;
static struct fixed *fixed_tuples;

static resourcetype *dummy;

int handler(char *restriction, char *content, tupleinfo *tuple)
{
        int resid;

        resid=res_findid(dummy, content);
        if(resid==INT_MIN) {
                error(_("Resource '%s' not found"), content);
                return -1;
        }

        fixed_tuples[fixed_num].resid=resid;
        fixed_tuples[fixed_num].tupleid=tuple->tupleid;

        fixed_num++;

        return 0;
}

int fitness(chromo **c, ext **e, slist **s)
{
        chromo *dummy_c;
        int n, sum;
        int tupleid, resid;

        dummy_c=c[0];

        sum=0;

        for(n=0;n<fixed_num;n++) {
                tupleid=fixed_tuples[n].tupleid;
                resid=fixed_tuples[n].resid;

                if(dummy_c->gen[tupleid]!=resid) sum++;
        }

        return sum;
}

int module_init(moduleoption *opt)
{
        fitnessfunc *f;

        dummy=restype_find(RESTYPE);
        if(dummy==NULL) {
                error(_("Resource type '%s' not found"), RESTYPE);
                return -1;
        }

        fixed_tuples=malloc(sizeof(*fixed_tuples)*dat_tuplenum);
        fixed_num=0;

        if(fixed_tuples==NULL) {
                error(_("Can't allocate memory"));
                return -1;
        }

        if(handler_tup_new("fixed-" RESTYPE, handler)==NULL) return -1;

        f=fitness_new("fixed",
                option_int(opt, "weight"),
                option_int(opt, "mandatory"),
                fitness);

        if(f==NULL) return -1;

        fitness_request_chromo(f, RESTYPE);

        return(0);
}

Initialisation du module

Examinons le code de la fonction module_init() : En premier, nous essayons de trouver la structure resourcetype pour le type de ressource nommé "dummy-type". Si nous ne pouvons pas la trouver, nous reportons une erreur et quittons le programme. Notez que cela rend notre module dépendant de la définition d'un certain type de ressources dans le fichier de configuration.

Notez également que tous les messages d'erreurs sont inclus dans des macros de traduction gettext. Vous devez utiliser la macro de traduction _() pour tous les messages d'avertissement ou d'erreur qui seront affichés à l'utilisateur. N'utilisez surtout pas cette fonction pour les noms de type de ressources ou de restrictions, ni pour les messages de debugage.

Nous allouons ensuite de la mémoire pour le tableau fixed_tuples.
Ce tableau contient l'information définissant quels tuples (évènements) ont des ressources fixes définies, qui l'ont été par notre restriction. Comme cela n'a pas de sens d'avoir plus d'une restriction de ce type par évènement, nous fixons la taille du tableau au nombre d'évènements (enregistré dans la variable globale dat_tuplenum). La variable fixed_num contient le nombre de restrictions utilisées.

Vient ensuite la partie importante. Nous définissons d'abord un nouveau type de restriction d'évènement, en utilisant la fonction handler_tup_new(). Ensuite, nous définissons notre fonction d'ajustage avec fitness_new(). Nous nommons cette valeur d'ajustage partiel "fixed" (ce nom est utilisé par exemple par l'utilitaire tablix2_plot) et passons les paramètres (inchangés) de poids et d'obligation, tirés du fichier de configuration, à la fonction fitness_new().

Enfin, nous devons dire au noyau sous quelle forme nous souhaitons que l'emploi du temps soit passé à notre fonction d'ajustage.
Le noyau gère trois formes d'emploi du temps :

• La forme chromosomique, qui est la forme native de l'algorithme génétique et qui est utilisée dans la plupart des cas,
• La forme chromosomique étendue,
• La forme "slist"

Dans cet exemple, nous utilisons un chromosome. Les deux autres formes seront expliquées plus loin.

Un emploi du temps est complètement décrit avec N chromosomes, où N est le nombre de types de ressources.
Pour cet exemple un chromosome est un tableau d'identifiants de ressources. La taille de ce tableau est égale au nombre d'évènements définis. Le Mième identifiant de ressource dans le tableau est l'identifiant de la ressource utilisée par l'évènement dont l'identifiant de tuple égal à M.

Dans l'exemple, nous demandons à ce que le chromosome pour le type de ressource "dummy-type" soit passé à la fonction d'ajustage en invoquant la fonction fitness_request_chromo.

Restriction d'évènement

La fonction handler() ne devrait pas nécessité beaucoup d'explications. Elle est appelée une fois pour chaque évènement qui a notre restriction dans le fichier de configuration.

L'argument restriction contient le type de restriction pour lequel le gestionnaire (handler) a été appelé. Puisque nous n'utilisons la fonction handler() pour un type de restriction ("fixed-dummy-type"), nous n'avons pas besoin de vérifier cette valeur. Sinon, cet argument nous permet d'utiliser une unique fonction pour plusieurs types de restrictions.

tuple est un pointeur vers la structure tupleinfo qui décrit l'évènement pour lequel la restriction a été définie. Ici, nous ne l'utilisons que pour récupérer l'identifiant du tuple de l'évènement et enregistrer sa valeur dans le tableau fixed_tuples . content stocke le contenu de la restriction, sous forme de chaîne de caractères. Cette chaîne est interprétée comme le nom d'une ressource et nous essayons de trouver et enregistrer son identifiant en utilisant la fonction res_findid .

Fonction d'ajustage

La fonction fitness() est plus intéressante.
Le noyau lui passe trois tableaux, avec les formes d'emplois du temps à évaluer.
Le premier est un tableau de pointeurs vers les chromosomes c. Le premier pointeur pointe sur le chromosome du premier type de ressource demandé, le second vers le second type de ressource demandé, etc...
e et s sont des tableaux de pointeurs similaires pour les extensions de chromosomes et les "slists".
Puisque nous n'avons demandé qu'un chromosome dans cet exemple, un pointeur vers celui-ci est enregistré en première place dans le tableau des chromosomes.

Le reste de la fonction d'ajustage est une boucle qui vérifie que chaque tuple du tableau fixed_tuples utilise la bonne ressource. Si ce n'est pas le cas, le compteur d'erreur sum est augmenté de 1. Lorsque tous les tuples ont été vérifiés, la fonction retourne le nombre total de tuples qui n'utilisent pas la ressource correcte. Les fonctions d'ajustage doivent toujours retourner un entier positif.

Tester le module

Nous devons créer un fichier de configuration XML qui utilise la restriction d'évènement que nous venons de définir. Nous devons également définir quelques ressources du type "dummy-type" car notre module dépend de ce type de ressources. Pour rester simple, un seul évènement est défini dans l'exemple suivant :

<?xml version="1.0" encoding="iso-8859-1"?>
<ttm version="0.2.0">
        <modules>
                <module name="fixed.so" weight="10" mandatory="yes"/>
        </modules>

        <resources>
                <variable>
                        <resourcetype type="dummy-type">
                                <linear name="#" from="1" to="50"/>
                        </resourcetype>
                </variable>
        </resources>

        <events>
                <event name="dummy-event" repeats="1">
                        <restriction type="fixed-dummy-type">30</restriction>
                </event>
        </events>
</ttm>

Sauvegardez ce fichier sous le nom de fixed.xml et lancez Tablix. Vous devrez attendre un moment, le temps que Tablix trouve une solution. Vous pourrez ensuite consulter un des fichiers de résultat :

<event name="dummy-event" repeats="1" tupleid="0">
        <restriction type="fixed-dummy-type">30</restriction>
        <resource type="dummy-type" name="30"/>
</event>

Vous pouvez voir que Tablix a programmé l'évènement "dummy-event", en utilisant la ressource avec le nom "30", comme nous l'avions demandé (la ressource "30" est une des 50 ressources avec les noms allant de "1" à "50", qui ont été définies avec la balise <linear> ).

Améliorations possibles

Ce module peut être amélioré de plusieurs façons. D'abord, il ne vérifie pas si il y a plus d'une restriction par évènement dans le fichier de configuration (dans ce cas, le nombre d'erreur ne pourra jamais être nul). Il peut également engendrer une erreur de segmentation dans ce cas, puisque le nombre de restrictions définies dépasserait le nombre d'évènements définis. Ensuite, il dépend de la définition du type de ressources "dummy-type" dans le fichier de configuration alors qu'une telle dépendance n'est pas strictement nécessaire (ce module est suffisamment général pour qu'il puisse être utile dans d'autres situations). Les solutions à ces problèmes sont laissées comme excercice pour le lecteur.