Linear Genetic Programming Intron Detection Algorithm

Question

Can someone point me to a specific algorithm that is used to remove introns from lgp individuals ?

Thank you

Answer 1

as far as removing introns are concerned, I would look at this paper: A Comparison of Linear Genetic Programming and Neural Networks in Medical Data Mining.

While the focus of the paper is probably not of interest, in Section II-B (Pages 20-21 I think). The authors discuss what I believe to be a pretty good simple intron detection algorithm.

This is a rather old paper, so it would be probably worth it to search the papers that cite this paper for other approaches that could help you.

I would in particular recommend for a more advanced approach the algorithm described in the paper:

"Redundancies in linear GP, canonical transformation, and its exploitation: a demonstration on image feature synthesis" (Evolvable Machines 2011)

To obtain this second paper, just type the title into Google, the first link should be the Springer pay wall link, but if you click Quick-View you should be able to get the paper no problem from Google Cache. (Let me know if you can't get to it I will help)

Answer 2

I have implemented a open source project on genetic programming which has this feature. Please take a look at my java implementation of linear genetic programming:

https://github.com/chen0040/java-genetic-programming

To improve the performance of the linear programs during evaluation, the library contains the implementation of intron removal procedure as described in the "Linear Genetic Programming" book chapter 3. The implementation can be found in the Program.markStructuralIntrons() in its

https://github.com/chen0040/java-genetic-programming/blob/master/src/main/java/com/github/chen0040/gp/lgp/program/Program.java

The principle of the markStructuralIntrons() is quite simple, below is cited from the book:

Source: Brameier, M 2004 On Linear Genetic Programming (thesis)

Algorithm 3.1 (detection of structural introns)

1. Let set R_eff always contain all registers that are effective at the current program position. R_eff := { r | r is output register }. Start at the last program instruction and move backwards.
2. Mark the next preceding operation in program with: destination register r_dest element-of R_eff. If such an instruction is not found then go to 5.
3. If the operation directly follows a branch or a sequence of branches then mark these instructions too. Otherwise remove r_dest from R_eff .
4. Insert each source (operand) register r_op of newly marked instructions in R_eff if not already contained. Go to 2.
5. Stop. All unmarked instructions are introns.

Below is the procedure of the Program.markStructuralIntrons() implemented in Java:

public void markStructuralIntrons(LGP manager) {

    int instruction_count=instructions.size();
    for (int i = instruction_count - 1; i >= 0; i--) {
        instructions.get(i).setStructuralIntron(true);
    }

    Set<Integer> Reff = new HashSet<>();
    int io_register_count = manager.getRegisterCount();
    for (int i = 0; i < io_register_count; ++i) {
        Reff.add(i);
    }

    Instruction current_instruction = null;
    Instruction prev_instruction = null;  // prev_instruction is the last visited instruction from bottom up of the program 

    for (int i = instruction_count - 1; i >= 0; i--) {
        prev_instruction = current_instruction;
        current_instruction = instructions.get(i);
        // prev_instruction is not an structural intron and the current_instruction
        // is a conditional construct then, the current_instruction is not structural intron either
        // this directly follows from Step 3 of Algorithm 3.1
        if (current_instruction.getOperator().isConditionalConstruct() && prev_instruction != null) {
            if (!prev_instruction.isStructuralIntron()) {
                current_instruction.setStructuralIntron(false);
            }
        } else {
            if (Reff.contains(current_instruction.getTargetOperand().getIndex())) {
                current_instruction.setStructuralIntron(false);
               Reff.remove(current_instruction.getTargetOperand().getIndex());
                if (!current_instruction.getOperand1().isConstant()) {
                    Reff.add(current_instruction.getOperand1().getIndex());
                }
                if (!current_instruction.getOperand2().isConstant()) {
                   Reff.add(current_instruction.getOperand2().getIndex());
                }
            }
        }
    }
}