«уникальный» кроссовер для генетического алгоритма - TSP - PullRequest
Новая
       71

«уникальный» кроссовер для генетического алгоритма - TSP

1 голос
/ 29 марта 2019

Я создаю Генетический алгоритм для решения Задачи коммивояжера .

В настоящее время два 2D списка представляют двух родителей, которых нужно пересечь: 

path_1 = np.shuffle(np.arange(12).reshape(6, 2))
path_2 = np.arange(12).reshape(6,2)

Предположим, что каждый элемент в списке представляет координату (x, y) на декартовой плоскости, а 2D-список представляет путь, по которому должен идти «коммивояжер» (от индекса 0 до индекса -1).

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

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

Ответы [ 2 ]

1 голос
/ 05 июня 2019

Вам необходимо использовать заказанный оператор кроссовера, например OX1 .

OX1 - довольно простой кроссовер перестановок. В основном, ряд последовательных аллелей от родительского 1 падает вниз, а остальные значения помещаются в дочерний элемент в том порядке, в котором они появляются в родительском 2.

Я использовал для запуска TSP с этими операторами:

0 голосов
/ 29 марта 2019

Вы можете сделать что-то вроде этого,

Выберите половину (или любое случайное число между 0 to (length - 1)) координатами одного из родителей, используя любой подход, скажем, где i % 2 == 0.

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

Теперь оставшиеся координаты должны исходить от 2-го родителя, по которому вы можете перейти во 2-м родителе, и, если координата не выбрана, добавить ее в пустые места.

Например,

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

def crossover(p1, p2, number_of_cities):
    chk = {}
    for i in range(number_of_cities):
        chk[i] = 0
    child = [-1] * number_of_cities
    for x in range(len(p1)):
        if x % 2 == 0:
            child[x] = p1[x]
            chk[p1[x]] = 1
    y = 1
    for x in range(len(p2)):
        if chk[p2[x]] == 0:
            child[y] = p2[x]
            y += 2
    return child

Этот подход сохраняет порядок городов, посещаемых обоими родителями.

Также, поскольку он не является симметричным, p1 и p2 можно переключить, чтобы дать 2 детям, и можно выбрать лучшего (или обоих).

...