Использование GA в GUI
Извините, если это не ясно, когда я пишу это на мобильном устройстве, и я пытаюсь сделать это быстро.
Я написал базовый Генетический Алгоритм с двоичным кодированием (генами), который строит значение пригодности и развивается через несколько итераций с использованием выбора турнира, мутации и кроссовера. В качестве основного примера командной строки, кажется, работает.
Проблема, с которой я столкнулся, заключается в применении генетического алгоритма в графическом интерфейсе, когда я пишу программу решения лабиринтов, которая использует GA, чтобы найти метод через лабиринт. Как превратить мои случайные двоичные закодированные гены и фитнес-функцию (сложить все двоичные значения вместе) в метод управления ботом вокруг лабиринта? Я построил базовый графический интерфейс на Java, состоящий из лабиринта меток (например, сетки) с доступными маршрутами, выделенными синим, а стены - черными.
Чтобы повторить, моя GA работает хорошо и содержит то, что мог бы сделать любой типичный GA (метод пригодности, получить и установить популяцию, выбор, кроссовер и т. Д.), Но теперь мне нужно подключить его к GUI, чтобы запустить мой лабиринт. Что нужно сделать, чтобы получить бота, который может двигаться в разных направлениях, в зависимости от того, что говорит ГА? Грубый псевдокод был бы хорош, если это возможно
По запросу, Individual создается с использованием отдельного класса (Individual), а вся основная работа выполняется в классе Pop. Когда создается новый индивид, массив целых чисел представляет гены указанного индивида, причем гены выбираются случайным образом из числа от 0 до 1. Функция пригодности просто складывает вместе значение этих генов и в классе Pop обрабатывает выборку., мутация и кроссовер двух выбранных особей. В этом нет ничего особенного, программа командной строки просто показывает эволюцию за n поколений, а общая пригодность улучшается за каждую итерацию.
РЕДАКТИРОВАТЬ: Это начинает иметь немного больше смысла сейчас, хотя есть несколько вещей, которые меня беспокоят...
Как предложил Адамски, я хочу создать "агента" с параметрами, показанными ниже. Проблема, с которой я столкнулся, заключается в том, что здесь появляется случайная битовая строка. Агент знает, где находятся стены, и выложил ли он 4-битную строку (т. Е. 0111), но как это влияет на случайную 32-битную строку? (т.е. 10001011011001001010011011010101) Если у меня есть следующий лабиринт (х - начальное место, 2 - цель, 1 - стена):
x 1 1 1 1
0 0 1 0 0
1 0 0 0 2
Если я поверну налево, то поверну не в ту сторону, и агент полностью уйдет из лабиринта, если будет двигаться вперед. Я предполагаю, что первое поколение струн будет совершенно случайным и будет развиваться по мере роста физической формы, но я не понимаю, как струна будет работать в лабиринте.
Итак, чтобы получить это прямо...
Пригодность - это результат того, что агент может двигаться и находится у стены.
Гены представляют собой строку из 32 битов, разделенных на 16 наборов по 2 бита, чтобы показать доступные действия и для перемещения робота два бита должны быть переданы с четырьмя битами от агента, показывающего его положение около стен. Если движение должно проходить мимо стены, то движение не выполняется, и оно считается недействительным, и если движение сделано, и если найдена новая стена, то пригодность возрастает.
Это правильно?
2 ответа
Ответ BadHorse хорош, если вы хотите решить конкретный лабиринт; Вы просто интерпретируете свою битовую строку как последовательность точных инструкций, чтобы вести агента через лабиринт. В этом случае ваша пригодность - это не сумма строки битов (как вы указали в своем вопросе), а скорее некоторая метрика, измеряющая, насколько успешно агент был в решении проблемы. Например, ваша физическая форма может быть определена как "расстояние по прямой от конца лабиринта после обработки 20 инструкций".
Следовательно, оценивая каждого человека, вы позволяете ему обрабатывать первые 20 инструкций из вашей цепочки битов, а затем вычислять его пригодность, выполнять любые пересечения / мутации и затем создавать следующее поколение индивидуумов.
Если вы хотите разработать свой агент для решения любого лабиринта, вам нужно кодировать правила в вашей битовой строке, а не в последовательности инструкций. Вы можете определить правила, основываясь на том, была ли стена позади, спереди, слева или справа от робота; например
FBLR Action
0000 Move Forward
0001 Move Forward
0010 Turn Right
etc
Это дает вам битовую строку, состоящую из 16 действий, каждое из которых закодировано как 2 бита (00 = движение вперед, 01 = поворот вправо, 10 = поворот влево, 11 = движение назад). При оценке вашего агента он просто определяет его текущее состояние и использует битовую строку в качестве таблицы поиска, чтобы определить, как он должен реагировать. Затем он повторяет это определенное количество раз, после чего вы оцениваете его пригодность.
Учитывая это кодирование, агент может оценить правило, которое люди обычно используют, которое гласит: "Следуйте за левой стенкой непрерывно". Очевидно, что этот подход потерпит неудачу, если лабиринт не полностью подключен, и в этом случае вам нужно закодировать больше состояний в подходе, основанном на правилах (например, агент может реагировать по-другому, если переходит "старый путь").
Надеюсь, это поможет.
РЕДАКТИРОВАТЬ
В ответ на ваше последнее изменение:
Тот факт, что я кодировал агентские "датчики", определяющие, находится ли он рядом со стеной или нет, не имеет отношения к битовой цепочке (вашему гену), и, возможно, я немного спутал вещи с моим примером. Ген только кодирует действия (движение вперед и т. Д.), А не состояния датчика.
Поэтому вы должны написать код для поиска соответствующей части строки битов, учитывая конкретную комбинацию показаний датчика; например
/**
* 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;
}
}
Если я правильно понимаю, вам нужно определить, как действия вашего бота в GUI представлены результатами вашего генетического алгоритма? Я думаю, что определение репрезентации, которую вы хотите использовать, должно быть вашей отправной точкой. Таким образом, вам нужно создать сопоставление для каждого (группы) "генов" вашего индивидуума с определенным действием или определенным изменением алгоритма движения вашего бота.
Как только вы выбрали жизнеспособное представление, реализация будет несколько более логичной.
Очень простым представлением движения было бы позволить генам жестко закодировать определенный маршрут. Вы можете использовать блоки из четырех генов для представления различных направлений, а затем 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