Генетические алгоритмы: моделирование дарвиновской системы

В этом уроке я расскажу о шагах по созданию генетического алгоритма с использованием Python. Генетический алгоритм — это алгоритм, имитирующий методологию «выживания наиболее приспособленных». У нас будет популяция, состоящая из группы особей. В каждом поколении мы убиваем наименее приспособленных и создаем детей, используя наиболее приспособленных из населения. Цель этого состоит в том, чтобы наша «цивилизация» вывела максимально приспособленный образец.

Для нашего эксперимента мы попытаемся создать список из 100 чисел в порядке возрастания (т. е. 1, 2, 3, 4… 99 100). Мы начнем со случайных списков длиной ‹ 100 и случайных чисел (0–100) в качестве значений в массиве. Будем надеяться, что наше население будет все ближе и ближе приближаться к желаемому упорядоченному списку по мере того, как мы будем переходить из поколения в поколение.

Генетический алгоритм состоит из четырех частей:

Оцените ФИТНЕС каждого человека
ВЫБЕРИТЕ наиболее подходящих людей, чтобы выжить в следующем поколении
КРОССОВЕР (или размножение) выживших особей, пока мы не вернемся к желаемому размеру популяции.
МУТАЦИЯ потомства в этом новом поколении слегка

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

Сначала давайте настроим некоторые константы для нашего эксперимента.

import math
import random

import numpy as np

MAX_SIZE = 100
MUTATION_PERCENTAGE = 0.3
POP_SIZE = 200
SURVIVE_PERCENT = 0.1
GENERATIONS = 1000

MAX_SIZE, который может быть в нашем списке, равен 100.
Вероятность того, что ребенок подвергнется мутации, составляет 30%.
Численность нашего населения составляет 200 человек.
В каждом поколении выживают только лучшие 10%
Наконец, мы проведем этот эксперимент для 1000 поколений.

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

Теперь давайте посмотрим на наш агент SequentialNumbersAgent.

class SequentialNumbersAgent:
    def __init__(self, nums_arr):
        self.nums_arr = nums_arr

    def get_fitness(self):
        score = 0
        for i in range(0, len(self.nums_arr) - 1):
            if int(self.nums_arr[i]) + 1 == int(self.nums_arr[i + 1]):
                score += 1
        return score

    def mutate(self):
        # grow mutation
        if np.random.random() < MUTATION_PERCENTAGE:
            additions = np.random.randint(MAX_SIZE)
            for _ in range(additions):
                 self.nums_arr = np.append(self.nums_arr, np.random.randint(MAX_SIZE))
            self.nums_arr = self.nums_arr[-MAX_SIZE:]

        # switch values mutation
        if np.random.random() < MUTATION_PERCENTAGE:
            replacements = np.random.randint(MAX_SIZE)
            for _ in range(replacements):
                index = np.random.randint(len(self.nums_arr))
                self.nums_arr[index] = np.random.randint(MAX_SIZE)

    def crossover(self, otherAgent):
        baby_arr = np.concatenate((self.nums_arr[0:math.floor(len(self.nums_arr)/2)], otherAgent.nums_arr[math.floor(len(otherAgent.nums_arr)/2):]))
        return SequentialNumbersAgent(baby_arr)

В нашем конструкторе __init__ мы берем массив чисел в качестве начального состояния нашего агента.
В get_fitness мы рассчитываем индивидуальный балл, наблюдая, сколько последовательных пар у него есть (т. е. если arr[i] + 1 = arr[i+1], то даем ему балл).
В mutate у нас есть две формы мутации. Во-первых, мы случайным образом добавим числа в конец списка (а затем обрежем начало, чтобы убедиться, что мы остаемся в пределах 100 MAX_SIZE). Затем мы случайным образом заменяем значения в нашем массиве другими значениями случайное количество раз. мутация происходит только в MUTATION_PERCENTAGE времени (поэтому не каждый ребенок получает мутацию).
Наконец, в нашем кроссовере мы берем первую половину родителя один и объединяем его со второй половиной родителя два.

Теперь, когда у нас есть функциональность для подготовки наших генетических процессов, мы можем запустить наш алгоритм!

if __name__ == "__main__":

    # create our population
    agents = []
    for _ in range(POP_SIZE):
        arr_size = np.random.randint(MAX_SIZE)
        arr = []
        for _ in range(arr_size):
            arr.append(np.random.randint(MAX_SIZE))
        agents.append(SequentialNumbersAgent(arr))

    for i in range(GENERATIONS):
        # sort by fitness
        fitness_scores = []
        for _ in agents:
            fitness_scores.append(_.get_fitness())
        inds = np.array(fitness_scores).argsort()
        agents = np.flip(np.array(agents)[inds])

        print("MAX_FITNESS")
        print(agents[0].get_fitness())

        # select surviving percent
        agents = agents[:math.floor(POP_SIZE * SURVIVE_PERCENT)]

        # preform crossover until we have our pop back
        babies = []
        while (len(agents) + len(babies)) < POP_SIZE:
            parents = random.sample(agents.tolist(), 2)
            baby = parents[0].crossover(parents[1])
            baby.mutate()
            babies.append(baby)
        agents = np.append(agents, babies)

    # sort by fitness one last time so we can see the best
    fitness_scores = []
    for _ in agents:
        fitness_scores.append(_.get_fitness())
    inds = np.array(fitness_scores).argsort()
    agents = np.flip(np.array(agents)[inds])

    print("Winner")
    print(agents[0].nums_arr)
    print("Min Size")
    print(np.min([len(x.nums_arr) for x in agents]))
    print("Average fitness")
    print(np.mean(fitness_scores))

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

Теперь, когда вы настроили эту структуру, вы можете исследовать множество других интересных идей: возможно, попробовать какие-то другие мутации (или вообще не мутировать), посмотреть, что произойдет со средним уровнем приспособленности, если вы добавите для начала чрезвычайно приспособленного индивидуума (подходит ли он/она). значительно поднять средний показатель?). Вы также можете применить генетические алгоритмы к некоторым более сложным проблемам, которые нельзя решить, выполнив вызов numpy.arange (например, решение задачи коммивояжера).

Генетические алгоритмы: моделирование дарвиновской системы

Похожие вопросы