genetic-programming - 线性遗传规划内含子检测算法

Question

有人可以指出一种用于从 lgp 个体中去除内含子的特定算法吗？

谢谢

Answer 1

至于去除内含子，我会看这篇论文：医学数据挖掘中的线性遗传规划和神经网络的比较。

虽然本文的重点可能不感兴趣，但在第 II-B 部分（我认为是第 20-21 页）。作者讨论了我认为非常好的简单内含子检测算法。

这是一篇相当古老的论文，因此搜索引用该论文的论文以寻找可以帮助您的其他方法可能是值得的。

我特别推荐一种更高级的方法，即本文中描述的算法：

“线性 GP 中的冗余、规范变换及其开发：图像特征合成演示”（Evolvable Machines 2011）

要获得第二篇论文，只需在 Google 中输入标题，第一个链接应该是 Springer 付费墙链接，但是如果您单击 Quick-View，您应该可以从 Google Cache 中获取论文没有问题。（如果你不能做到，请告诉我，我会帮助你）

Answer 2

我已经实现了一个具有此功能的遗传编程开源项目。请看一下我的线性遗传编程的java实现：

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

为了在评估期间提高线性程序的性能，该库包含“线性遗传编程”一书第 3 章中描述的内含子去除过程的实现。该实现可以在它的 Program.markStructuralIntrons() 中找到

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

markStructuralIntrons() 的原理很简单，下面是从书中引用的：

资料来源：Brameier, M 2004 线性遗传规划（论文）

算法 3.1（结构内含子的检测）

1. 让设置 R_eff 始终包含在当前程序位置有效的所有寄存器。R_eff := { r | r 是输出寄存器}。从最后一条程序指令开始并向后移动。
2. 在程序中标记下一个前面的操作：目标寄存器 r_dest element-of R_eff。如果没有找到这样的指令，则转到 5。
3. 如果操作直接跟随一个分支或一系列分支，那么也标记这些指令。否则从 R_eff 中删除 r_dest 。
4. 如果尚未包含，则将新标记指令的每个源（操作数）寄存器 r_op 插入 R_eff 中。转到 2。
5. 停止。所有未标记的指令都是内含子。

下面是用 Java 实现的 Program.markStructuralIntrons() 的过程：

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