Как создать мою популяцию генетического алгоритма?

Question

Проблема задана, и я должен найти 5 лучших путей от начала до цели с помощью генетического алгоритма.Изображение игровой площадки показано здесь:

1

Детская площадка имеет одну стартовую точку, один гол и несколько барьеров.Ответы не должны конфликтовать с барьерами.Я собираюсь использовать Python-3.x для своей реализации.

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

grid = np.array([
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])

start = (12,0)
goal = (0,10)

Теперь я не знаю, как создать свое первоначальное население для работы с другими Операторы GA , такие как кроссовер и мутация.

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

Answer 1

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

Например, одно решение (или один кандидат от начальной популяции) может быть таким:

([
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, *, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, *, *, *, *, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, *, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, *, *, *, *, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, *, 0, *, *, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, *, 0, *, *, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, *, 0, *, *, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, *, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, *, 1, 1, 1, 0, 0],
[0, *, *, *, *, *, *, *, *, *, *, 1, 1, 1, 0, 0],
[0, *, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, *, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[*, *, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])

, где след *это путь от (12, 0) до (0, 10).

Так что теперь вам нужно найти способ случайным образом сгенерировать путь *, начинающийся с start в конце в end.Наивный подход заключается в использовании случайного направления влево, вправо, вверх и вниз.Если это направление заблокировано границей или 1, выберите другое направление.Продолжайте, пока не дойдете до конца.

Кроме того, путь может иметь * смежные друг с другом, как показано выше.(3, 11) и (3, 12) содержит *, но не являются частью непрерывного следа.Для этого используйте разные числа для обозначения направления, или я бы предложил использовать юникод для стрелок, например, \u2190 для левой стрелки.

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

Answer 2

Поскольку вы уже знаете размер своего пространства поиска (это размер квадрата на вашем рисунке), вы можете инициализировать свое население из целочисленного равномерного распределения, используя эту информацию.

Я не знаюразмер плитки квадрата, но давайте предположим, что это [15,15].Каждый человек в вашем населении будет 2D, верно?Итак, поскольку вы используете python и считаете, что численность населения равна 10, вы должны сделать что-то вроде:

import numpy as np
pop = np.random.randint(0,15,[10,2])

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

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

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