Использование GA в GUI

Question

Извините, если это не ясно, поскольку я пишу это на мобильном устройстве, и я пытаюсь сделать это быстро.

Я написал базовый генетический алгоритм с бинарным кодированием (генами), который строит значение пригодности и развивается через несколько итераций, используя выбор турнира, мутацию и кроссовер. В качестве базового примера командной строки, похоже, работает.

Проблема, с которой я столкнулся, заключается в применении генетического алгоритма в GUI, поскольку я пишу программу для решения лабиринта, которая использует GA для поиска метода через лабиринт. Как превратить мои случайные двоичные кодированные гены и функцию фитнеса (добавить все двоичные значения вместе) в метод управления ботом вокруг лабиринта? Я построил базовый графический интерфейс на Java, состоящий из лабиринта ярлыков (например, сетки) с доступными маршрутами в синем, а стены - черными.

Чтобы повторить, моя GA хорошо работает и содержит то, что любой обычный GA (метод пригодности, получение и установка совокупности, выбор, кроссовер и т. Д.), Но теперь мне нужно подключить его к графическому интерфейсу, чтобы запустить мой лабиринт. Что нужно делать, чтобы получить бота, который может двигаться в разных направлениях в зависимости от того, что говорит ГА? Грубый псевдокод был бы замечательным, если это возможно

В соответствии с запросом индивидуальный пользователь построил отдельный класс (Indiv), причем все основные работы выполнялись в классе Pop. Когда создается новый индивид, массив ints представляет гены упомянутого человека, причем гены выбираются случайным образом из числа от 0 до 1. Функция фитнеса просто добавляет вместе значение этих генов и в классе дескрипторов класса Pop , мутация и кроссовер двух отобранных индивидуумов. Там не так уж и много, программа командной строки просто показывает эволюцию в течение n поколений, при этом общая пригодность улучшается на каждой итерации.

EDIT: Это начинает делать немного больше смысла сейчас, хотя есть несколько вещей, которые давали мне покой ...

Как Адамской предложила я хочу создать «Агент» с опцией показана ниже , Проблема, с которой я столкнулся, заключается в том, что здесь играет случайная бит-строка. Агент знает, где находятся стены и выкладывается ли он в 4-битовой строке (то есть 0111), но как это влияет на случайную 32-битную строку? (Т.е. 10001011011001001010011011010101) Если у меня есть следующий лабиринт (х начало место, 2 цель, 1 стена):

x 1 1 1 1 
0 0 1 0 0 
1 0 0 0 2 

Если я повернуть налево, я неправильно сориентирована и агент будет полностью перемещайтесь от лабиринта, если он движется вперед. Я предполагаю, что первое поколение строки будет полностью случайным, и оно будет развиваться по мере роста фитнеса, но я не понимаю, как строка будет работать в лабиринте.

Таким образом, чтобы получить это прямо ...

фитнес является результатом, когда агент способен двигаться и стеной.

Гены представляют собой строку из 32 бит, разделенную на 16 наборов из 2 битов, чтобы показать доступные действия, и для того, чтобы робот мог перемещать два бита, необходимо передать четыре бита из показания агента, его положение у стен , Если движение должно пройти мимо стены, движение не производится, и оно считается недействительным, и если ход сделан, и если новая стена будет найдена, то фитнес поднимается.

Это правильно?

Answer 1

ответ BadHorse это хорошо, если вы хотите, чтобы решить конкретный лабиринт; вы просто проиндексируете свою битовую строку как последовательность точных инструкций, чтобы направлять агента через лабиринт. В этом случае ваша пригодность не является суммой битовой строки (как вы заявляете в своем вопросе), а скорее некоторой метрикой, измеряющей, насколько успешным был агент при решении проблемы. Например, ваш фитнес может быть определен как «расстояние по прямой линии от конца лабиринта после обработки 20 инструкций».

Следовательно, при оценке каждого человека вы разрешаете ему обрабатывать первые 20 команд из вашей битовой строки, а затем вычислять ее пригодность, выполнять любые кроссоверы/мутации, а затем создавать следующее поколение людей.

Если вы хотите, чтобы ваш агент, чтобы решить , любой лабиринт, вам нужно закодировать правила внутри вашей битовой строки, а не последовательность инструкций. Вы могли бы определить правила, основанные на том, была ли стена сразу позади, спереди, слева или справа от робота; например

FBLR Action 
0000 Move Forward 
0001 Move Forward 
0010 Turn Right 
etc 

Это дает битовую строку, состоящую из 16 действий, каждое действие кодируется как 2 бита (00 = движение вперед, 01 = поворот вправо, 10 = Поворот влево, 11 = Переместить в обратном направлении). При оценке вашего агента он просто определяет свое текущее состояние и использует битовую строку в качестве таблицы поиска, чтобы определить, как она должна реагировать. Затем он повторяет это определенное количество раз, после чего вы оцениваете его пригодность.

Учитывая эту кодировку, агент может оценить правило, которое люди обычно используют, которое «непрерывно следует за стенкой левой руки». Очевидно, что этот подход не сработает, если лабиринт не будет полностью подключен, и в этом случае вам нужно закодировать большее количество состояний в своем подходе, основанном на правилах (например, агент может реагировать по-другому, если перебирает «старую землю»).

Надеюсь, что это поможет.

EDIT

В ответ на вашу последнюю правку:

Того факт, что я закодирован агент «датчики» обнаруживая ли он рядом со стеной или нет не имеет отношения к битной строки (ваш ген), и, возможно, я немного смутил вещи на моем примере. Ген кодирует только действия (перемещение вперед и т. Д.) не состояние датчика.

Вы должны написать код для поиска соответствующей части битовой строки с учетом конкретной комбинации показаний датчика; например

/** 
* Enumeration describing the four available actions to the agent 
* and methods for decoding a given action from the "bit" string 
* (actually represented using booleans). 
*/ 
public enum Action { 
    MOVE_FORWARD, REVERSE, TURN_LEFT, TURN_RIGHT 

    Action decodeAction(boolean b1, boolean b2) { 
    Action ret; 

    if (b1) { 
     ret = b2 ? Action.MOVE_FORWARD : Action.TURN_LEFT; 
    } else { 
     ret = b2 ? Action.TURN_RIGHT : Action.REVERSE; 
    } 

    return ret; 
    } 
} 

/** 
* Class encapsulating the 32-bit "bit string" represented using booleans. 
* Given the state of the four agent inputs the gene will provide a specific 
* action for the agent to perform. 
*/ 
public class Gene { 
    private final boolean[] values = new boolean[32]; 

    public Action getActionForSensorInputs(boolean wallInFront, 
    boolean wallBehind, boolean wallToLeft, boolean wallToRight) { 

    int i=0; 

    // Encode the four sensor inputs as a single integer value by 
    // bitwise-ORing each sensor value with a power of 2. 
    // The encoded value will be in the range [0, 15]. 
    if (wallToRight) { 
     i |= 0x01; 
    } 

    if (wallToLeft) { 
     i |= 0x02; 
    } 

    if (wallBehind) { 
     i |= 0x04; 
    } 

    if (wallInFront) { 
     i |= 0x08; 
    } 

    // The look-up index is i * 2 because each action is encoded as 2 
    // booleans. 
    int index = i * 2; 

    // Retrieve the two action bits from the bit string. 
    boolean b1 = this.values[index]; 
    boolean b2 = this.values[index + 1]; 

    // Finally decode the action to perform. 
    return Action.decodeAction(b1, b2); 
    } 

    // TODO: Add method to support crossover and mutation with other Genes. 
} 

Учитывая это простое определение Gene можно встроить этот класс в пределах Agent реализации и записи, как агент выполняет с текущим геном «установленным»; например

private enum Direction { NORTH, SOUTH, EAST, WEST }; 

public class Agent { 
    private final Geneva gene; 
    private final int x; // x position in maze; 
    private final int y; // y position in maze; 
    private Direction currentDirection; 

    public double evaluate() { 
    double fitness; 

    // Perform up to 20 actions and then evaluate fitness. 
    for (int i=0; i<20; ++i) { 
     // TODO Determine sensor inputs. 

     Action action = gene.getActionForSensorInputs(...); 

     // TODO: Now apply action to update agent's state. 
     // If agent has reached goal exit loop and return fitness 1.0 (max fitness). 
     // If agent has exited the maze then exit loop and return 0.0 (min fitness). 
    } 

    // Calculate fitness after 100 steps taken. For example could be 
    // calculated as sqrt((goal.x - x)^2 + (goal.y - y)^2). 

    return fitness; 
    } 
} 

Answer 2

Если я правильно понял, вам нужно определить, как действия вашего бота в графическом интерфейсе представлены результатом вашего генетического алгоритма? Я считаю, что определение представления, которое вы хотите использовать, должно быть вашей отправной точкой.Поэтому вам нужно создать сопоставление для каждой (группы) «генов» в вашем индивидууме для определенного действия или определенного изменения в алгоритме движения вашего бота.

Как только вы выбрали жизнеспособное представление, реализация будет несколько более логичной.

Очень простое представление о движении - это дать генам жесткого кода определенный маршрут. Вы можете использовать блоки из четырех генов для представления разных направлений, а затем 0 означает «не двигаться в этом направлении», а 1 означает перемещение.

Тогда представление 01001101 можно перевести как следующую схема движения:

stand still 
go one step east 
stand still 
stand still 
go one step north 
go one step east 
stand still 
go one step west