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

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

Компоненты генетического алгоритма

Генотип

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

[1,0,1,0,0,0,1,1,]

Популяция

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

[[1,0,1,0,0,0,1,1,], [1,1,1,0,0,0,1,1,], [1,0,0,0,0,1,1,1,]]

Функция приспособленности

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

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

def oneMaxFitness(individual):
  return sum(individual),

Таким образом, самый пригодный индивидуум из всей популяции для данной задачи с данной функцией пригодности - это список, состоящий только из единиц ([1,1,1,1,1] с длиной списка = 5).

Отбор

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

Скрещивание

Для создания пары новых индивидуумов родители обычно выбираются из текущего поколения, а части их хромосом меняются местами (скрещиваются), в результате чего создаются две новые хромосомы, представляющие потомков. Эта операция называется скрещиванием, или рекомбинацией. На Python это выглядит вот так:

chromosoma_1 = [1,0,0,1,1,1,0,1,1,0,0,0]
chromosoma_2 = [1,0,0,1,1,1,0,1,1,1,1,1]
# скрещивание - это забирается, например, 
# последние 3 элемента из chromosoma_2 и 
# конкатенируются в chromosoma_1
crossover_1 = chromosoma_1[:-3] + chromosoma_2[-3:]
# crossover_1 = [1,0,0,1,1,1,0,1,1,1,1,1]
crossover_2 = chromosoma_2[:-3] + chromosoma_1[-3:]
# crossover_2 = [1,0,0,1,1,1,0,1,1,0,0,0]

Мутация

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

import random
mutation_probability = 0.1
random_number = random.random()
chromosoma_1 = [1,0,0,1,1,1,0,1,1,0,0,0]
if mutation_probability < random:
  # возьмем для мутации последний элемент
  if chromosoma_1[-1] == 1:
    chromosoma_1[-1] = 0
  else: chromosoma_1[-1] = 1

Сама библиотека DEAP (сокращение от Distributed Evolutionary Algorithms in Python – распределенные эволюционные алгоритмы на Python) поддерживает быструю разработку решений с применением генетических алгоритмов и других методов эволюционных вычислений.

Давайте рассмотрим задачу "Hello world" из мира генетических алгоритмов - OneMax задачу (состоит в том, чтобы найти двоичную строку заданной длины, для которой сумма составляющих ее цифр максимальна)

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

# константы задачи
ONE_MAX_LENGTH = 100 # длина подлежащей оптимизации битовой строки
# константы генетического алгоритма
POPULATION_SIZE = 100 # количество индивидуумов в популяции
P_CROSSOVER = 0.9 # вероятность скрещивания
P_MUTATION = 0.1 # вероятность мутации индивидуума
MAX_GENERATIONS = 50 # максимальное количество поколений

RANDOM_SEED = 42
random.seed(RANDOM_SEED)

# Toolbox() используется как контейнер для функций (или операторов) и позволяет 
# создавать новые операторы путем назначения псевдонимов или настройки существующих функций
toolbox = base.Toolbox()
# создали оператор (или псевдоним) zeroOrOne, который вызывает random.radint()
# с фиксированными параметрами 0 и 1
toolbox.register("zeroOrOne", random.randint, 0, 1)
# Получаем класс creator.FitnessMax, расширяющий класс base.Fitness,
# в котором атрибут класса weights инициализирован значением (1.0,).
# Можно также определить класс для оптимизации сразу нескольких целей
# различной важности - creator.create("FitnessCompound", base.Fitness, weights=(1.0, 0.2, -0.5))
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
# класс Individual создается путем расширения базового класса, 
# представляющего хромосому. класс Individual должен содержать функцию
# приспособленности в качестве атрибута
creator.create("Individual", list, fitness=creator.FitnessMax)
# Поскольку оператор zeroOrOne создает объекты, принимающие случайное
# значение 0 или 1, то получающийся в результате оператор 
# individualCreator заполняет экземпляр Individual 100 
# случайными значениями 0 или 1
toolbox.register("individualCreator", tools.initRepeat, creator.Individual, toolbox.zeroOrOne, ONE_MAX_LENGTH)
# регистрируем оператор populationCreator, создающий список индивидуумов
toolbox.register("populationCreator", tools.initRepeat, list, toolbox.individualCreator)

def oneMaxFitness(individual):
  return sum(individual),
# Определим оператор evaluate – псевдоним только что опреде-
ленной функции oneMaxfitness()
toolbox.register("evaluate", oneMaxFitness)
# Имя select зарегистрировано как псевдоним существующей в модуле
# tools функции selTournament() с аргументом tournsize = 3.
toolbox.register("select", tools.selTournament, tournsize=3)
# Имя mate зарегистрировано как псевдоним существующей в модуле
# tools функции cxTwoPoint().В результате создается оператор toolbox.
# mate, который выполняет двухточечное скрещивание
toolbox.register("mate", tools.cxOnePoint)
# Имя mutate зарегистрировано как псевдоним существующей в модуле
# tools функции mutFlipBit с аргументом indpb = 0.02. В результате создается оператор 
# toolbox.mutate, который выполняет мутацию инвертированием бита с вероятностью 0.02
toolbox.register("mutate", tools.mutFlipBit, indpb=1.0/ONE_MAX_LENGTH)

Основная часть генетического алгоритма:

def main():
  # Создаем начальную популяцию оператором populationCreator, задавая
  # размер популяции POPULATION_SIZE.
  population = toolbox.populationCreator(n=POPULATION_SIZE)
  generationCounter = 0

  # Для вычисления приспособленности каждого индивидуума в начальной популяции
  fitnessValues = list(map(toolbox.evaluate, population))

  # Поскольку элементы списка fitnessValues взаимно однозначно со-
  # ответствуют элементам популяции (представляющей собой список
  # индивидуумов), мы можем воспользоваться функцией zip(), чтобы
  # объединить их попарно, сопоставив каждому индивидууму его при-
  # способленность
  for individual, fitnessValue in zip(population, fitnessValues):
    individual.fitness.values = fitnessValue

  # в нашем случае имеет место приспособляемость всего
  # с одной целью, то извлекаем первое значение из каждого кортежа при-
  # способленности для сбора статистики
  fitnessValues = [individual.fitness.values[0] for individual in population]

  # собираем максимальное и среднее значение приспособленности в каждом поколении
  maxFitnessValues = []
  meanFitnessValues = []

  while max(fitnessValues) < ONE_MAX_LENGTH and generationCounter < MAX_GENERATIONS:
    generationCounter = generationCounter + 1

    offspring = toolbox.select(population, len(population))

    # отобранные индивидуумы, которые находятся в списке offspring, клонируются,
    # чтобы можно было применить к ним следующие
    # генетические операторы, не затрагивая исходную популяцию
    offspring = np.array(map(toolbox.clone, offspring))

    # объединить в пары каждый элемент списка offspring с четным индексом со следующим за ним элементом с нечетным индексом.
    # удалим значения приспособленности потомков, потому что они были модифицированы и старые значения уже не актуальны
    for child1, child2 in zip(offspring[::2], offspring[1::2]):
      if random.random() < P_CROSSOVER:
        toolbox.mate(child1, child2)
        del child1.fitness.values
        del child2.fitness.values

    for mutant in offspring:
      if random.random() < P_MUTATION:
        toolbox.mutate(mutant)
        del mutant.fitness.values

    # Те индивидуумы, к которым не применялось ни скрещивание, ни му-
    # тация, остались неизменными, поэтому их приспособленности, вы-
    # численные в предыдущем поколении, не нужно заново пересчитывать
    freshIndividuals = [ind for ind in offspring if not ind.fitness.valid]

    freshFitnessValues = list(map(toolbox.evaluate, freshIndividuals))
    for individual, fitnessValue in zip(freshIndividuals, freshFitnessValues):
      individual.fitness.values = fitnessValue

    # После того как все генетические операторы применены, нужно заме-
    # нить старую популяцию новой:
    population[:] = offspring

    # учтем в статистике текущие значения приспособленности
    fitnessValues = [ind.fitness.values[0] for ind in population]

    maxFitness = max(fitnessValues)
    meanFitness = sum(fitnessValues) / len(population)
    maxFitnessValues.append(maxFitness)
    meanFitnessValues.append(meanFitness)
    print("- Поколение {}: Макс приспособ. = {}, Средняя приспособ. = {}"
    .format(generationCounter, maxFitness, meanFitness))

    best_index = fitnessValues.index(max(fitnessValues))
    print("Лучший индивидуум = ", *population[best_index], "\n")

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

• GitHub с кодом тут

• Статьи на исследования нейронных сетей с генетическим алгоритмом: один, два, три

• Книга: Генетические алгоритмы на Python Эйял Вирсански