Execution

Evaluation

In LGP — as in other forms of Genetic Programming — the cost of computation is dominated by the evaluation of the programs evolved on the fitness cases defined by the problem.

A program must be executed for each fitness case, and if evaluating the fitness of a problem is quite computationally demanding this can cause the majority of the time to spent evaluating fitness.

One method LGP uses to speed up the execution of programs is related to the linear representation of programs. This representation leads to instructions in a program that are not effective, that is, they don’t effect the programs output.

These instructions can be found efficiently and removed from the program so that when evaluating the program, only those instructions which directly effect the output of the program are executed.

This unique aspect of LGP can lead to a drastic performance improvement as on average, it decreases the number of instructions that are executed for each program, which is advantageous when there are a large number of fitness cases or evaluating a programs fitness is a computationally demanding task.

To test a program on a set of fitness cases, the basic steps are:

  1. Load a set of inputs from a fitness case into the programs input registers.
  2. Execute the program with the inputs given by executing each effective instruction.
  3. Store the output of the program for later fitness evaluation.
  4. Go to step 1. while there are still fitness cases left, otherwise go to step 5.
  5. Compare each fitness cases desired output with the output predicted by the program for that fitness case using some fitness function.

Translation

Because the primary objective of GP is to find the best program that generalises a solution to the problem, it is important that the program found by LGP can actually be used in a context outside of the LGP system.

Internally, an LGP program is interpreted using a simple virtual machine that can execute a programs instructions. It is not advantageous to only programs generated by LGP to be used within this context, so programs need to be translated to another format.

In typical LGP, all instructions are able to be translated to equivalent instructions in the C programming language, but our system allows for custom representations to be defined so that a program can be translated to any format required (e.g. assembly, other imperative languages, etc).