Генетический алгоритм /w Нейронная сеть, играющая змею, не улучшается

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

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

Настройка нейронной сети

24 входных узла

2 Скрытые слои

8 узлов на слой

4 выходных узла (по одному для каждого направления, которое может принимать змея)

Вход представляет собой массив каждого направления, которое может видеть змея. Для каждого направления он проверяет, насколько далеко расстояние до стены, плода или самого себя. Конечным результатом является массив длиной 3*8 = 24.

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

Настройка генетического алгоритма

Размер населения: 50000

Родители, выбранные за поколение: 1000

Сохраняйте верхний уровень для каждого поколения: 25000 (новая переменная, видя лучшие результаты)

Вероятность мутации на ребенка: 5%

(Я пробовал много разных соотношений размеров, хотя я все еще не уверен, что такое типичное соотношение.)

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

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

Пригодность змеи рассчитывается с: age * 2**score (не больше, больше информации в обновлении), где возраст - это количество поворотов, которые выжила змея, и оценка - количество собранных фруктов.

подробности

Вот какой-то псевдокод, чтобы попытаться обобщить, как мой генетический алгоритм (должен) работать:

pop = Population(size=1000)

while True:  # Have yet to implement a 'converged' check
    pop.calc_fitness()

    new_pop = []

    for i in range(n_parents):

        parent1 = pop.fitness_based_selection()
        parent2 = pop.fitness_based_selection()

        child_snake1, child_snake2 = parent1.crossover(parent2)

        if rand() <= mutate_chance:
            child_snake.mutate()

        new_pop.append(child_snake1, child_snake2)

    pop.population = new_pop

    print(generation_statistics)
    gen += 1

Вот метод, который я использую для выбора родителя:

def fitness_based_selection(self):
    """
    A slection process that chooses a snake, where a snake with a higher fitness has a higher chance of being
    selected
    :return: The chosen snake brain
    """
    sum_fitnesses = sum(list([snake[1] for snake in self.population]))

    # A random cutoff digit.
    r = randint(0, sum_fitnesses)

    current_sum = 0

    for snake in self.population:
        current_sum += snake[1]
        if current_sum > r:
            # Return brain of chosen snake
            return snake[0]

Стоит отметить, что self.population - это список змей, где каждая змея - это список, содержащий контроль над нейронной сетью, и фитнес-сеть.

И вот метод получения вывода из сети из выхода игры, поскольку я подозреваю, что может быть что-то, что я делаю неправильно здесь:

def get_output(self, input_array: np.ndarray):
    """
    Get output from input by feed forwarding it through the network

    :param input_array: The input to get an output from, should be an array of the inputs
    :return: an output array with 4 values of the shape 1x4
    """

    # Add biases then multiply by weights, input => h_layer_1, this is done opposite because the input can be zero
    h_layer_1_b = input_array  + self.biases_input_hidden1
    h_layer_1_w = np.dot(h_layer_1_b, self.weights_input_hidden1)
    h_layer_1 = self.sigmoid(h_layer_1_w)  # Run the output through a sigmoid function

    # Multiply by weights then add biases, h_layer_1 => h_layer_2
    h_layer_2_w = np.dot(h_layer_1, self.weights_hidden1_hidden2)
    h_layer_2_b = h_layer_2_w + self.biases_hidden1_hidden2
    h_layer_2 = self.sigmoid(h_layer_2_b)

    # Multiply by weights then add biases, h_layer_2 => output
    output_w = np.dot(h_layer_2, self.weights_hidden2_output)
    output_b = output_w + self.biases_hidden2_output

    output = self.sigmoid(output_b)
    return output

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

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

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

Обновить:

Я изменил пару вещей:

  • Исправлена генерация веса/смещения, ранее они составляли только от 0 до 1.
  • Отредактировал мой метод кроссовера, чтобы вернуть двух детей на один набор родителей вместо одного.
  • Измененная функция фитнеса была равна только возрасту змеи (для целей тестирования)
  • Изменены переменные

Теперь алгоритм работает лучше, первое поколение обычно находит змею с фитнесом 14 -1 6, а это означает, что змея делает поворот, чтобы избежать смерти, однако она почти всегда идет вниз по склону оттуда. Первая змея фактически достигла тактики поворота, когда приближалась к востоку и к северу/югу, но не к западному краю. После первого поколения фитнес, как правило, только ухудшается, в конечном итоге возвращается к минимально возможной пригодности. Я в недоумении, что происходит не так, но у меня есть ощущение, что это может быть что-то большое, что я забыл.

Обновление № 2:

Возможно, я мог бы упомянуть некоторые вещи, которые я пробовал, которые не срабатывали:

  • Изменены узлы на один скрытый слой от 8 до 16, это сделало змей намного хуже.
  • Позволял змее вернуться в себя, это также сделало змей хуже.
  • Большие (я думаю, они большие, не уверены, что такое стандартный размер поп-музыки.) Численность населения ~ 1 000 000, с ~ 1000 родителями, никаких положительных изменений.
  • 16 или 32 узла на скрытый слой, казалось бы, практически не повлияли.
  • Исправлена функция мутации для правильного назначения значений между -1 и 1, без заметного воздействия.

Обновление № 3:

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

Однако проблема все еще существует в том, что после первых двух поколений фитнес будет падать, первые 1-5 поколений могут иметь пригодность 300 (иногда они этого не делают и имеют низкую пригодность вместо этого, но я предполагаю, что это не так к численности населения.), но после этого пригодность поколений упадет до ~ 20-30 и останется там.

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

Ответы

Ответ 1

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

Если вы решите сосредоточиться на генераторе-потомстве, один из способов (в некоторой степени) гарантировать улучшенное потомство - реализовать бесполое воспроизведение, просто добавив небольшое количество шума к каждому весовому вектору. Если уровень шума достаточно мал, вы можете создать улучшенное потомство с вероятностью успеха до 50%. Более высокие уровни шума, тем не менее, позволяют ускорить улучшение, и они помогают выпрыгнуть из локальных оптимумов, даже если они имеют показатели успеха ниже 50%.

Ответ 2

Вы только мутируете 5% населения, а не 5% от "генома". Это означает, что ваше население будет зафиксировано невероятно быстро - https://en.wikipedia.org/wiki/Fixation_(population_genetics).

Это имеет смысл, почему население не очень хорошо себя чувствует, потому что вы изучаете только небольшую область фитнес-ландшафта (https://en.wikipedia.org/wiki/Fitness_landscape).

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

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

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