Генетический алгоритм / W Neural Network играет змею не улучшается

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

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

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

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's 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 это список змей, где каждая змея - это список, содержащий NeuralNet, управляющий ею, и пригодность сети.

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

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-16, что означает, что змея делает повороты, чтобы избежать смерти, однако оттуда она почти всегда идет вниз. Первая змея на самом деле достигла тактики поворота, когда она близка к восточному и северному / южному краям, но никогда не к западному краю. После первого поколения физическая форма имеет тенденцию только ухудшаться, в конечном итоге возвращаясь к самой низкой возможной физической форме. Я в недоумении от того, что идет не так, но я чувствую, что это может быть что-то большое, что я упустил из виду.

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

Думаю, я мог бы также упомянуть некоторые вещи, которые я пробовал, но они не работали

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

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

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

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

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

2 ответа

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


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

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

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

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

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

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

У меня была эта проблема в течение недели, и я только понял, в чем проблема. При назначении мозгов от одной змеи к другой обязательно используйте array.copy. Например, сделайте это:

a = np.array([1, 2, 3, 4])
b = a.copy()

а не это:

a = np.array([1, 2, 3, 4])
b = a

Это связано с тем, что во втором случае python иногда заставляет b и a совместно использовать одну и ту же память, и поэтому всякий раз, когда вы переназначаете b, a также будет переназначен.

Другие вопросы по тегам