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

Мутация, кроссовер, популяция, гены, оптимизация, селекция

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

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

Население

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

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

хромосома

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

Гены

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

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

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

Фитнес-функция

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

Функция пригодности также используется для оценки критериев завершения алгоритма, таких как достижение определенного уровня пригодности или достижение определенного количества поколений. Хорошо спроектированная фитнес-функция должна отражать важные аспекты проблемы и желаемые свойства решений. Функция пригодности также должна быть масштабируемой и эффективной для оценки, особенно для задач с большими пространствами решений. Его также можно представить в виде функции оптимизации. Если вы хотите узнать больше об алгоритмах оптимизации, вы можете сделать это по этой ссылке.

Чтобы получить хороший результат, нам нужно узнать несколько шагов о том, как правильно запустить генетический алгоритм. Вот шаги типичного генетического алгоритма:

1. Инициализация: создается совокупность случайных решений, каждое из которых представлено в виде набора параметров или функций. Эти решения оцениваются на основе функции пригодности, которая измеряет, насколько хорошо они решают проблему.
2. Отбор: наиболее подходящие решения отбираются, чтобы стать родителями следующего поколения. Это делается путем присвоения вероятности выбора каждому решению на основе его пригодности.
3. Кроссовер. Два родительских решения выбираются случайным образом, и оператор кроссовера применяется для создания одного или нескольких дочерних решений. Оператор кроссовера объединяет функции двух родительских решений для создания новых решений, которые наследуют некоторые из их лучших функций.
4. Мутация: в некоторые функции дочерних решений вносятся случайные изменения. Это вносит в популяцию новое разнообразие и помогает не застревать в локальных оптимумах.
5. Оценка: оценивается пригодность дочерних решений, после чего они добавляются в популяцию.
6. Повторить. Шаги 2–5 повторяются для многих поколений в надежде, что популяция сойдется к оптимальному или близкому к оптимальному решению.

Методы выбора

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

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

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

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

Методы кроссовера

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

• Одноточечный кроссовер. При одноточечном кроссовере выбирается случайная точка кроссовера в родительских решениях, и связанные сегменты обмениваются для получения двух дочерних решений. Остальные признаки не отличаются от родителей. Точка пересечения выбирается случайным образом из диапазона [1, длина-1], где длина — это длина решения. Эта процедура проста и эффективна, и она может дать широкий спектр решений потомства. Однако он может быть не в состоянии зафиксировать сложные взаимодействия между объектами, которые не находятся близко к точке пересечения.

• Двухточечное пересечение. Двухточечное пересечение включает в себя выбор двух случайных точек пересечения в родительских решениях и обмен сегментами между двумя точками для получения двух дочерних решений. Остальные признаки не отличаются от родителей. Две точки пересечения выбираются случайным образом из диапазона [1, длина-1], причем первая точка меньше второй. Этот метод может фиксировать более сложные взаимодействия между функциями, разбросанными по всем решениям, что приводит к более разнообразным дочерним решениям. Однако он требует более высоких вычислительных затрат, чем одноточечный кроссовер.

• Равномерный кроссовер —Каждая функция решений-потомков выбирается случайным образом из одного из родительских решений с равной вероятностью при равномерном кроссовере. Поскольку каждая функция выбирается независимо, последующие дочерние решения могут содержать сочетание функций обоих родителей. Эта стратегия может внести дополнительное разнообразие в популяцию, а также зафиксировать сложные взаимодействия между признаками. Однако он может давать дочерние решения, которые менее подходят, чем родительские, и требуют больших вычислительных затрат, чем одноточечный кроссовер.

Методы мутации

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

• Bit-Flip Mutation — с небольшой вероятностью случайный бит в двоичном представлении результата переворачивается с 0 на 1 или с 1 на 0. Этот оператор, который может вносить незначительные колебания в решение пространство, широко используется в двоичных представлениях или представлениях с кодировкой Грея. Мутация с переворотом бита проста и быстра в построении, но она может не фиксировать сложные отношения между функциями.

• Мутация перестановки — с небольшой вероятностью две случайные характеристики решения переключаются в мутации перестановки. Этот оператор часто используется в представлениях на основе перестановок, таких как задача коммивояжера или задачи планирования работы магазина. Изменяя последовательность признаков, мутация подкачки может внести в пространство решений более значительные изменения, чем мутация с переворотом битов, и помочь избежать локальных оптимумов. Однако это может привести к невозможным решениям или нарушить ограничения проблемы.

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

Условие прекращения

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

Преимущества генетических алгоритмов

1. Глобальная оптимизация: генетические алгоритмы хорошо находят глобальные оптимумы даже в многомерных и невыпуклых пространствах поиска.
2. Надежность: генетические алгоритмы устойчивы к шуму и неопределенности целевой функции и могут работать с ограничениями и множественными целями.
3. Разнообразие: генетические алгоритмы поддерживают разнообразную популяцию решений, что может помочь избежать застревания в локальных оптимумах.
4. Исследование и эксплуатация: генетические алгоритмы уравновешивают исследование и эксплуатацию, объединяя лучшие черты родительских решений и внося новое разнообразие посредством мутаций.

Недостатки генетических алгоритмов

1. Вычислительная стоимость: генетические алгоритмы могут быть дорогостоящими в вычислительном отношении, особенно для крупномасштабных и сложных задач.
2. Скорость сходимости: генетические алгоритмы могут сходиться медленно, особенно если ландшафт фитнеса суров или размер популяции слишком мал.
3. Настройка параметров. Генетические алгоритмы требуют тщательной настройки параметров, а производительность может зависеть от выбора параметров и операторов.

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

import random

POPULATION_SIZE = 10
GENE_LENGTH = 25
NUM_GENERATIONS = 100
MUTATION_RATE = 0.1

def create_chromosome():
    return [random.randint(0, 1) for _ in range(GENE_LENGTH)]

def create_population():
    return [create_chromosome() for _ in range(POPULATION_SIZE)]

def fitness_function(chromosome):
    return sum(chromosome)

def roulette_wheel_selection(population, fitness_scores):
    total_fitness = sum(fitness_scores)
    selection_probabilities = [fitness / total_fitness for fitness in fitness_scores]
    return random.choices(population, weights=selection_probabilities)[0]

def one_point_crossover(chromosome1, chromosome2):
    crossover_point = random.randint(1, GENE_LENGTH - 1)
    child1 = chromosome1[:crossover_point] + chromosome2[crossover_point:]
    child2 = chromosome2[:crossover_point] + chromosome1[crossover_point:]
    return child1, child2

def bit_flip_mutation(chromosome):
    mutated_chromosome = chromosome.copy()
    for i in range(GENE_LENGTH):
        if random.random() < MUTATION_RATE:
            mutated_chromosome[i] = 1 - mutated_chromosome[i]
    return mutated_chromosome

population = create_population()

for i in range(NUM_GENERATIONS):
    fitness_scores = [fitness_function(chromosome) for chromosome in population]
    fittest_chromosome = max(population, key=fitness_function)
    print(f"Generation {i + 1}: Fittest chromosome has fitness score {fitness_function(fittest_chromosome)}")
    new_population = [fittest_chromosome]
    while len(new_population) < POPULATION_SIZE:
        parent1 = roulette_wheel_selection(population, fitness_scores)
        parent2 = roulette_wheel_selection(population, fitness_scores)
        child1, child2 = one_point_crossover(parent1, parent2)
        child1 = bit_flip_mutation(child1)
        child2 = bit_flip_mutation(child2)
        new_population.extend([child1, child2])
    population = new_population

Подводя итог

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

Если вам понравилась статья, не забудьте подписаться на мои новые статьи.

Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Присоединяйтесь к нашему сообществу Discord и следите за нами в Twitter, LinkedIn и YouTube.

Узнайте, как привлечь внимание к своему стартапу с помощью Circuit.