Tablix modules HOW-TO, part 1
Prev	Chapter 2. Kernel API	Next

Fitness function, chromosomes, event restriction

Let's extend our basic module so that it will actually do something useful. Following is the source code of a module that will force selected event to use a certain resource from resource type "dummy-type". It defines a new event restriction named "fixed-dummy-type". The contents of this restriction tell which resource from the "dummy-type" resource type should this event use.

#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);
}

We have two new functions here: fitness() is our fitness function and handler() is the restriction handler for the type of event restrictions we defined.

Note: All global variables in modules should be declared as static.

Module initialization

Let's follow the module_init() function: First we try to find the resourcetype structure for the resource type named "dummy-type". If we can't find it, we report an error and exit. Note that this made our module dependend on the definition of a certain resource type in the configuration file.

Also note that all error messages are enclosed in gettext translation macros. You should use translation macro _() around any warning or error message that will be seen by users. Don't put it around resource type names or restriction types. Also don't use it with debug messages.

Next we allocate memory for the fixed_tuples array. This array stores the information about which tuples (events) had defined fixed resources defined by our restriction. Since it doesn't make sense to have more than one restriction of this type per event, we make the length of the array equal to the number of events (stored in the global dat_tuplenum). fixed_num stores the number of used restrictions.

Now comes the important part. First we define a new event restriction type with the handler_tup_new(). Second we define our fitness function with the fitness_new(). We named this partial fitness value "fixed" (this name is used for example by tablix2_plot utility) and passed unchanged weight and mandatory values from the config file to fitness_new().

Note: Your fitness functions should have short, descriptive names that should be easy for the user to connect with your module.

Finally we must tell the kernel in which form do we want the timetable to be passed to our fitness function. Kernel supports three forms of timetables: chromosome form, which is the native form of the genetic algorithm and is used in most cases, chromosome extension form and slist form. In this example we use a chromosome. Other two forms will be explained in later sections.

Figure 2-1. Timetable representation in the Tablix kernel.

A timetable is fully described with N chromosomes, where N is the number of resource types. For the purpose of this example a chromosome is an array of resource IDs. Length of the array is equal to the number of defined events. Mth resource ID in the array is the ID of the resource that is used by event with tuple ID equal to M.

Note: Resource ID is an unique numerical representation of a resource within its resource type (two resources can have the same resource ID if they are from different resource types).
Tuple ID is an unique numerical representation of an event. Two events always have different tuple IDs. Tuples defined with a single <event> tag and repeats greater than 1 have sequential IDs.

Caution

You may have noticed that the tupleinfo structure, passed by the kernel to event restriction handlers, also contains resource IDs for a tuple. You should never use those values in fitness functions. Resource IDs stored in tupleinfo are those defined in the XML file and may have changed in the timetable that must be evaluated by the fitness function.

Note: The length of the chromosome is stored in the gennum field of the chromosome structure. This number is equal to the number of defined events in the dat_tuplenum global variable. However you should use the gennum field when iterating through the whole chromosome in case of any future changes in the kernel.

In this example we request the chromosome for the resource type "dummy-type" to be passed to our fitness function by calling fitness_request_chromo.

Note: It does not matter if a resource type of the chromosome you requested is defined as variable or as constant in the configuration file.

Event restriction

The handler() function shouldn't require much explanation. It is called once for each event that had our restriction in the configuration file.

Note: If an event restriction is used in an <event> tag with repeats property greater than one, then the restriction handler function will be called multiple times, once for each event defined by the <event> tag (with tuple pointer set accordingly).

restriction argument holds the type of the restriction this handler was called for. Since we only used handler() function in one type of restrictions ("fixed-dummy-type") we don't need to check its value. Otherwise this argument would enable us to use a single function as a handler for multiple restriction types.

tuple is a pointer to tupleinfo structure that describes the event for which this restriction was defined. Here we only use it to get the tuple ID of the event and store its value in the fixed_tuples array. content holds the content of the restriction in string form. We interpret this string as a name of a resource and try to find and store its resource ID by using the res_findid function.

Fitness function

fitness() function is more interesting. Kernel passes to it three arrays with the requested forms of the timetable to evaluate. First is an array of pointers to chromosomes c. First pointer points to the chromosome for the first requested resource type, second pointer to the second requested resource type, etc. e and s are similar arrays of pointers to chromosome extensions and slists. Since we only requested one chromosome in this example a pointer to it is stored in the first location in the chromosome array.

The rest of fitness function is a loop that checks each tuple in the fixed_tuples array if it is using the correct resource. If it is not the error count sum is increased by one. When all tuples have been checked the function exits, returning the total number of tuples that are not using the correct resource. Fitness functions must always return a positive integer.

Note: Fitness function should not change any structures or arrays that are passed to it.

Tip: Fitness functions are one of the most often called functions in Tablix. It must be called for each timetable in a generation. One generation includes by default 500 timetables and it takes many thousand generations to find a solution. Because of this they should be as optimized as possible.

Testing the module

We need to construct an XML configuration file that will use the event restriction we defined with our module. We also have to define a few resources of the type "dummy-type" because our module depends on this resource type. To keep things simple, only one event is defined in the following example.

<?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>

Again save this file under a name fixed.xml and run Tablix. You will have to wait a few moments for Tablix to find a solution. You can then examine one of the result files:

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

You can see that Tablix scheduled event "dummy-event" so, that it is using resource with the name "30" as we requested (resource "30" is one of 50 resources with names from "1" to "50" that were defined with the <linear> tag).

Possible improvements

This module can be improved in many ways. First, it does not check if there is more than one restriction per event in the configuration file (in that case the number of errors could never reach zero). It could also cause a segmentation fault in that case because the number of defined restrictions would exceed the number of defined events. Second, it depends on the definition of the "dummy-type" resource type in the configuration file while such dependency isn't strictly necessary (this module is general enough that it would be useful in a number of different situations). The solution to these problems is left as an exercise for the reader.