Объясненные генетические алгоритмы: реализация Python

Генетические алгоритмы, также называемые просто «GA», являются алгоритмами, вдохновленными Чарльзом Дарвином. Теория естественного отбора Это направлено на поиск оптимальных решений проблем, о которых мы мало знаем. Например: Как найти данную функцию максимальной или минимальной, если вы не можете ее получить? Он основан на трех концепциях: выбор, воспроизведение, и мутация, Мы генерируем случайный набор людей, Выбрать самые лучшие, пересекать их над и, наконец, немного мутировать результат — снова и снова, пока мы не найдем приемлемое решение. Вы можете проверить некоторые сравнения других методов поиска на Книга Гольдберга,

Давайте проверим, как написать простую реализацию генетического алгоритма с использованием Python!

Проблема, которую мы попытаемся решить, состоит в том, чтобы найти максимум 3D-функции, похожей на шляпу. Определяется как f (x, y) = грех (sqrt (x ^ 2 + y ^ 2)), Мы ограничим нашу проблему границами 4 ≥ x ≥ -4 и 4 ≥ y ≥ -4,

(График функции между нашими определенными границами, созданный с CalcPlot3D)

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

import random

def generate_population(size, x_boundaries, y_boundaries):
    lower_x_boundary, upper_x_boundary = x_boundaries
    lower_y_boundary, upper_y_boundary = y_boundaries

    population = ()
    for i in range(size):
        individual = {
            "x": random.uniform(lower_x_boundary, upper_x_boundary),
            "y": random.uniform(lower_y_boundary, upper_y_boundary),
        }
        population.append(individual)

    return population

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

Двигаясь дальше, давайте определим нашу фитнес-функцию. Это будет наш оценщик, который скажет, насколько лучше или хуже человек друг от друга. Люди с наилучшей подготовкой должны сохраняться и размножаться, а худшие — падать, как в природе. В нашем случае, как мы хотим найти максимум нашей функции, мы можем просто применить наш целевая функция для человека, и самые большие числа будут самой большой пригодностью. Если мы хотим найти минимум, пригодность может быть выражена как результат функции -1, поэтому меньшие значения становятся более подходящими.

import math

def apply_function(individual):
    x = individual("x")
    y = individual("y")
    return math.sin(math.sqrt(x ** 2 + y ** 2))

Так как у нас есть генератор населения и фитнес-оценщик, мы можем начать воспроизводить наших людей для достижения следующего поколения. Мы будем делать это, пока не найдем приемлемое решение. Существует несколько критериев остановки, в основном используется критерий «n поколений со устаревшей пригодностью», но мы будем использовать более простой критерий — просто n поколений — мы будем использовать 100. До сих пор наша функция входа выглядит следующим образом:

generations = 100

population = generate_population(size=10, x_boundaries=(-4, 4), y_boundaries=(-4, 4))

i = 1
while True:
    print(f"🧬 GENERATION {i}")

    for individual in population:
        print(individual)

    if i == generations:
        break

    i += 1

    # Make next generation...

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

def choice_by_roulette(sorted_population, fitness_sum):
    offset = 0
    normalized_fitness_sum = fitness_sum

    lowest_fitness = apply_function(sorted_population(0))
    if lowest_fitness < 0:
        offset = -lowest_fitness
        normalized_fitness_sum += offset * len(sorted_population)

    draw = random.uniform(0, 1)

    accumulated = 0
    for individual in sorted_population:
        fitness = apply_function(individual) + offset
        probability = fitness / normalized_fitness_sum
        accumulated += probability

        if draw <= accumulated:
            return individual

Чтобы проиллюстрировать наш метод, скажем, у нас есть четыре человека: A, B, C и D с пригодностью 0, 50, 200 и 250 соответственно. Сумма общей пригодности составляет 500, поэтому каждый из них будет иметь фитнесс / total_fitness вероятность выбора: 0%, 10%, 40%, 50%. Мы выбираем случайное число от 0 до 1, а затем проверяем, какой человек находится в выбранной части: A (0, 0), B (0, 0,1), C (0,1, 0,5), D (0,5, 1).

Поскольку наш сценарий может иметь отрицательную пригодность, сначала мы должны нормализовать наших индивидуумов, выбрав самую низкую пригодность, умножив ее на -1, а затем добавив ее ко всем из них (например, если у нас есть два человека с пригодностью -10 и 5 соответственно, мы добавьте 10, чтобы оба стали 0 и 15). Мы также ожидаем, что аргумент населения будет отсортирован по возрастанию, чтобы легче было найти худших и лучших людей.

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

Есть несколько методов кроссовера для действительных чисел: например, мы могли бы взять Икс индивидуума А и Y для отдельного B мы могли бы взять среднее геометрическое каждого или, самое простое, взять среднее арифметическое каждого. Если мы имеем дело с двоичными данными, наиболее распространенным методом является выбор части строки битов A и части строки битов B. Для простоты, давайте используем среднее арифметическое.

Для мутации также есть множество вариантов — мы просто сложим небольшое случайное число между фиксированным интервалом. Этот интервал является частотой мутаций и может быть соответственно настроен, давайте использовать (-0,05, 0,05). Для больших пространств поиска вы можете выбрать большие интервалы и уменьшать их из поколения в поколение. При работе с двоичными данными вы можете просто перевернуть случайно выбранные биты отдельной строки.

def sort_population_by_fitness(population):
    return sorted(population, key=apply_function)


def crossover(individual_a, individual_b):
    xa = individual_a("x")
    ya = individual_a("y")

    xb = individual_b("x")
    yb = individual_b("y")

    return {"x": (xa + xb) / 2, "y": (ya + yb) / 2}


def mutate(individual):
    next_x = individual("x") + random.uniform(-0.05, 0.05)
    next_y = individual("y") + random.uniform(-0.05, 0.05)

    lower_boundary, upper_boundary = (-4, 4)

    # Guarantee we keep inside boundaries
    next_x = min(max(next_x, lower_boundary), upper_boundary)
    next_y = min(max(next_y, lower_boundary), upper_boundary)

    return {"x": next_x, "y": next_y}


def make_next_generation(previous_population):
    next_generation = ()
    sorted_by_fitness_population = sort_population_by_fitness(previous_population)
    population_size = len(previous_population)
    fitness_sum = sum(apply_function(individual) for individual in population)

    for i in range(population_size):
        first_choice = choice_by_roulette(sorted_by_fitness_population, fitness_sum)
        second_choice = choice_by_roulette(sorted_by_fitness_population, fitness_sum)

        individual = crossover(first_choice, second_choice)
        individual = mutate(individual)
        next_generation.append(individual)

    return next_generation

Вот и все! Теперь у нас есть все три шага ГА: отбор, кроссовер и мутация. Наш основной метод тогда просто так:

generations = 100

population = generate_population(size=10, x_boundaries=(-4, 4), y_boundaries=(-4, 4))

i = 1
while True:
    print(f"🧬 GENERATION {i}")

    for individual in population:
        print(individual, apply_function(individual))

    if i == generations:
        break

    i += 1

    population = make_next_generation(population)

best_individual = sort_population_by_fitness(population)(-1)
print("n🔬 FINAL RESULT")
print(best_individual, apply_function(best_individual))
best_individual

Переменная будет держать нашего человека с самой высокой подготовкой после этих 100 поколений. Это может быть точным оптимальным решением или нет, вам придется настраивать параметры (частоту мутаций, поколения и т. Д.) И методы (методы отбора, кроссовера и мутации) до тех пор, пока вы не сможете больше совершенствоваться. Давайте посмотрим последние выходные строки для экспериментального прогона (обратите внимание, что из-за случайных параметров вы, скорее всего, получите разные, но схожие результаты):


🧬 GENERATION 100
{'x': -1.0665224807251312, 'y': -1.445963268888755} 0.9745828000809058
{'x': -1.0753606354537244, 'y': -1.4293367491155182} 0.976355423070003
{'x': -1.0580786664161246, 'y': -1.3693549033564183} 0.9872729309456848
{'x': -1.093601208942564, 'y': -1.383292089777704} 0.9815156357267611
{'x': -1.0464963866796362, 'y': -1.3461172606906064} 0.9910018621648693
{'x': -0.987226479369966, 'y': -1.4569537217049857} 0.9821687265560713
{'x': -1.0501568673329658, 'y': -1.430577408679398} 0.9792937786319258
{'x': -1.0291192465186982, 'y': -1.4289167102720242} 0.9819781801342095
{'x': -1.098502968808768, 'y': -1.3738230550364259} 0.9823409690311633
{'x': -1.091317403073779, 'y': -1.4256574643591997} 0.9748817266026281

🔬 FINAL RESULT
{'x': -1.0464963866796362, 'y': -1.3461172606906064} 0.9910018621648693

Наш конечный результат был очень близок к одному из возможных решений (эта функция имеет несколько максимумов внутри наших границ, что составляет 1,0, как вы можете видеть на графике в начале). Обратите внимание, что мы использовали менее сложные возможные методы, поэтому этот результат каким-то образом ожидается — это отправная точка для точной настройки, пока мы не сможем найти лучшие решения с меньшим количеством поколений.

Это была очень вводная статья о генетических алгоритмах, использующих Python. Если вам понравилось, вы наверняка захотите узнать больше обо всех возможных улучшениях, которые вы можете сделать в нем, и в приложениях, которые вы можете использовать. Я настоятельно рекомендую прочитать "Генетические алгоритмы в поиске, оптимизации и машинном обученииКнига, упомянутая в начале.



Источник: Объясненные генетические алгоритмы: реализация Python


Похожие материалы по теме: Объясненные генетические алгоритмы: реализация Python

Leave a comment