Как работает Geneti c Algorithm Crossover, когда мой вывод содержит только 2 состояния?

Question

В настоящее время я работаю над проектом, в котором я использую базовый c сотовый автомат и алгоритм Geneti c для создания карт, похожих на подземелья. В настоящее время мне невероятно трудно понять, как именно работает кроссовер, когда мои выходные данные могут быть только в двух состояниях: DEAD или ALIVE (1 или 0).

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

Однако, даже если я кодирую свои мертвые / живые ячейки в биты и пересекаю их ... Что мне в итоге? Ячейка может быть ТОЛЬКО Мертвой или Живой. Кроссовер даст мне случайное значение, которое находится за пределами этого диапазона, верно? И даже если бы мне пришлось работать с числами с плавающей запятой, разве я бы в итоге не получил 1 или 0? В этом случае кажется, что было бы лучше просто случайным образом мутировать мертвые клетки в живые клетки, или наоборот.

Я читал несколько статей на топи c, но, похоже, ни одна из них не объясняет этот конкретный случай. вопрос (во всяком случае, на понятном мне языке). Интуитивно я подумал, что, может быть, я смогу выполнить кроссовер на соседних ячейках - так что я нахожу 2 подходящих окрестности, а затем они обмениваются членами (например, соседство A отдает 4 своих соседей соседству B). Однако я нигде не видел эту идею, что наводит меня на мысль, что это должно быть в корне неверно.

Любая помощь будет принята с благодарностью, я действительно застрял на этой.

Answer 1

Любитель подземелий и программирования Geneti c здесь:)

Я думаю, вы неправильно поняли концепцию кроссовера. На ваших клеточных автоматах вы должны иметь генетическую c информацию (хромосомы), чтобы ваша система решала, является ли соответствующая клетка мертвой или живой. Состояние ячейки - это вывод вашей системы.

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

Кроссовер дает вам новую хромосому для картирования вашего подземелья, но не дает новых состояний для клеток. Чтобы получить новые состояния, просто запустите новую хромосому.

Состояние ваших клеток будет фенотипом, способом, которым проявляется ваша хромосома. Ваша хромосома - это модель, которая решает, жива ли ваша клетка. Меня не волнует модель, которую вы используете. Например, вы используете нейронную сеть с двумя входными узлами. Один входной узел получает координату X ячейки в сетке, а другой узел получает координату Y. Выходной узел представляет собой двоичное значение: DEAD или ALIVE. Эта нейронная сеть имеет определенное количество скрытых слоев и весов, которые закодированы в вашей хромосоме. Выполнив оператор кроссовера, вы создадите новый способ соединения нейронов, который находится между обоими родителями. Но чтобы узнать новое состояние каждой ячейки, вам нужно снова передать координаты в нейронную сеть. Возможно, проверка алгоритма NEAT Стенли проясняет процесс кроссовера: http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf

Если у вас нет модели, которая кодирует состояние каждой ячейки на карте, ваш генет c информация непосредственно о состоянии каждой ячейки. В этой ситуации вы можете разбить родительские сетки на более мелкие, например, 10x10. Затем бегите по карте в тайлах размером 10x10 и выбирайте случайным образом, выбираете ли вы подходящую плитку из parent1 или parent2.

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

Альберто