Алгоритм обнаружения интронов линейного генетического программирования

что касается удаления интронов, я бы посмотрел эту статью: A Сравнение линейного генетического программирования и нейронных сетей в интеллектуальном анализе медицинских данных.

В то время как фокус документа, вероятно, не представляет интереса, в разделе II-B (страницы 20-21, я думаю). Авторы обсуждают то, что я считаю довольно хорошим простым алгоритмом обнаружения интронов.

Это довольно старая статья, поэтому, вероятно, стоило бы поискать в документах, цитирующих эту статью, другие подходы, которые могли бы вам помочь.

В частности, я бы рекомендовал для более продвинутого подхода алгоритм, описанный в статье:

«Избыточность в линейном GP, каноническом преобразовании и его использовании: демонстрация синтеза признаков изображения» (Evolvable Machines, 2011 г.)

Чтобы получить эту вторую статью, просто введите название в Google, первая ссылка должна быть ссылкой на платную стену Springer, но если вы нажмете «Быстрый просмотр», вы сможете без проблем получить статью из Google Cache. (Дайте мне знать, если вы не можете добраться до него, я помогу)

Я реализовал проект с открытым исходным кодом по генетическому программированию, в котором есть эта функция. Пожалуйста, взгляните на мою реализацию линейного генетического программирования на 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 — выходной регистр }. Начните с последней инструкции программы и двигайтесь назад.
2. Отметьте следующую предыдущую операцию в программе с помощью: регистра назначения r_dest element-of R_eff. Если такая инструкция не найдена, то перейти к 5.
3. Если операция непосредственно следует за ветвью или последовательностью ветвей, отметьте и эти инструкции. В противном случае удалите r_dest из R_eff.
4. Вставьте каждый регистр источника (операнда) r_op вновь помеченных инструкций в R_eff, если он еще не содержится. Перейти к 2.
5. Останавливаться. Все немаркированные инструкции являются интронами.

Ниже приведена процедура Program.markStructuralIntrons(), реализованная на 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());
                }
            }
        }
    }
}