OneMax in Assembly

Generating real assembly programs: a different kind of OneMax

The goal, here, is to evolve an assembly program that, when executed, solves the one-max function by filling with 1's the AX register. It may be as useless as the canonical one-max, but at least it will show how µGP is able to create effective assembly code with a given goal.

The example may be found under Samples/OneMax/Assembly/. Due to small differences in the assembly language, two versions of the constraints exist: constraints.xml.i686 and constraints.xml.86_64. In order to run the experiment you need to copy (or link) the correct constraint file to constraints.xml. E.g.,

$ ln -s constraints.xml.`uname --machine` constraints.xml

µGP creates the code for an assembly function named evolved_function. The external evaluator fitness.sh assembles such function and links it with a fixed main to form a working program. Then runs the resulting executable. Indeed, this is a pretty standard procedure to evolve code.

fitness.sh

The fitness value here is the number of bits at 1 in ax (i.e., returned by the function). As a comment it is used the hexadecimal representation of the value, just to ease the task of checking.

Since the final goal is to solve the one-max problem with the shortest possible program, the actual fitness is composed of two elements: the number of 1 bit in AX produced by the execution, and a measure of the shortness of the function. µGP always tries to maximize the fitness and does not handle negative values, thus the so-called shortness is calculated as 1000-lines of code of the program by the script.

# Compile & execute
gcc -o tprog main.c $1 -lm 2>error.log
tprog=( $(./tprog) )
# Build output
len=$(wc -l $1 | awk '{ print $1 }')
a=${tprog[0]}
(( b = 10000 - $len )); [[ $b < 0 ]] && b=0 # (paranoia)
note="0x${tprog[1]}/$len"
echo "$a $b $note" >$UGP3_FITNESS_FILE

For the sake of efficiency, it can be wise to compile main.c only once at the beginning of the experiment, and generate the object file main.o.

[[ -f main.o ]] || gcc -O99 -c main.c
gcc -o tprog main.o $1 -lm 2>error.log

Please note that the actual fitness.sh provided includes a few additional checks.

main.c

The file main.c contains the wrapper for executing the program. It simply calls the evolved fragment of code and create the output.

The only code of some interest may be the watchdog. Since it is possible that µGP generates an endless loop (if backward jumps are enabled in the constraints), the main function sets a timer of 1000µs. If the evolved function does not return in a given time, the watchdog stops the execution and forces 0 XX as fitness.

int main(int argc, char *argv[])
{
    unsigned long int val;
    unsigned long int m;
    int fitness;

    /* Set up watchdog */
    signal(SIGVTALRM, timeout);
    new.it_interval.tv_sec = 0;
    new.it_interval.tv_usec = 0;
    new.it_value.tv_sec = 0;
    new.it_value.tv_usec = 1000;

    setitimer(ITIMER_VIRTUAL, &new, NULL);
    if(setjmp(wakeup_place)) {
        /* if the evolved_function hung, the longjmp will bring back us here */
        printf("0 XX\n");
    } else {
        /* "normal" flow */
        val = evolved_function();   
        fitness = 0;
        for(m = 0x1; m; m <<= 1) {
            if(val & m) 
                ++fitness;
        }
        printf("%d %lx\n", fitness, val);
    }
    return 0;
}

static void timeout(int foo)
{
    longjmp(wakeup_place, 1);
} 

The watchdog uses a non-local jump to break the standard subroutine call-sequence from an interrupt handler. See setjmp/longjmp on wikipedia, if you are not familiar with it.

Evolved function

µGP should learn how to write 32 ones into AX (the final goal). The evolved function is a fragment of assembly instructions chosen and optimized by the toolkit, wrapped into some code to interface with the main function in C.

The process followed to write the constraints is described here.