ИИ с Python - генетические алгоритмы

В этой главе подробно рассматриваются генетические алгоритмы ИИ.

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

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

ГА были разработаны Джоном Холландом и его студентами и коллегами из Мичиганского университета, в первую очередь Дэвидом Э. Голдбергом. С тех пор он был успешно опробован на различных задачах оптимизации.

В GA у нас есть набор возможных решений данной проблемы. Затем эти растворы подвергаются рекомбинации и мутации (как в естественной генетике), производят новых детей, и этот процесс повторяется для разных поколений. Каждому индивиду (или возможному решению) присваивается значение приспособленности (на основе значения его целевой функции), а более приспособленные индивидуумы получают более высокий шанс спариться и уступитьfitterлиц. Это соответствует дарвиновской теорииSurvival of the Fittest.

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

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

Как использовать GA для решения задач оптимизации?

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

Этапы механизма GA для процесса оптимизации

Ниже приводится последовательность шагов механизма GA при использовании для оптимизации задач.

• Шаг 1 - Сгенерируйте начальную популяцию случайным образом.

• Шаг 2 - Выберите исходное решение с наилучшими значениями пригодности.

• Шаг 3 - Перекомбинируйте выбранные решения, используя операторы мутации и кроссовера.

• Шаг 4 - Вставьте потомство в популяцию.

• Шаг 5 - Теперь, если условие остановки выполнено, верните решение с наилучшим значением пригодности. В противном случае перейдите к шагу 2.

Установка необходимых пакетов

Для решения проблемы с помощью генетических алгоритмов в Python мы собираемся использовать мощный пакет для GA под названием DEAP. Это библиотека новой эволюционной вычислительной среды для быстрого прототипирования и тестирования идей. Мы можем установить этот пакет с помощью следующей команды в командной строке -

pip install deap

Если вы используете anaconda среда, то для установки deap можно использовать следующую команду -

conda install -c conda-forge deap

Реализация решений с использованием генетических алгоритмов

В этом разделе объясняется реализация решений с использованием генетических алгоритмов.

Создание битовых комбинаций

В следующем примере показано, как сгенерировать битовую строку, содержащую 15 единиц, на основе One Max проблема.

Импортируйте необходимые пакеты, как показано -

import random
from deap import base, creator, tools

Определите функцию оценки. Это первый шаг к созданию генетического алгоритма.

def eval_func(individual):
   target_sum = 15
   return len(individual) - abs(sum(individual) - target_sum),

Теперь создайте набор инструментов с правильными параметрами -

def create_toolbox(num_bits):
   creator.create("FitnessMax", base.Fitness, weights=(1.0,))
   creator.create("Individual", list, fitness=creator.FitnessMax)

Инициализировать набор инструментов

toolbox = base.Toolbox()
toolbox.register("attr_bool", random.randint, 0, 1)
toolbox.register("individual", tools.initRepeat, creator.Individual,
   toolbox.attr_bool, num_bits)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

Зарегистрируйте оператора оценки -

toolbox.register("evaluate", eval_func)

Теперь зарегистрируйте оператор кроссовера -

toolbox.register("mate", tools.cxTwoPoint)

Зарегистрируйте оператор мутации -

toolbox.register("mutate", tools.mutFlipBit, indpb = 0.05)

Определите оператора для разведения -

toolbox.register("select", tools.selTournament, tournsize = 3)
return toolbox
if __name__ == "__main__":
   num_bits = 45
   toolbox = create_toolbox(num_bits)
   random.seed(7)
   population = toolbox.population(n = 500)
   probab_crossing, probab_mutating = 0.5, 0.2
   num_generations = 10
   print('\nEvolution process starts')

Оцените все население -

fitnesses = list(map(toolbox.evaluate, population))
for ind, fit in zip(population, fitnesses):
   ind.fitness.values = fit
print('\nEvaluated', len(population), 'individuals')

Создавайте и повторяйте из поколения в поколение -

for g in range(num_generations):
   print("\n- Generation", g)

Выбор людей следующего поколения -

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

Теперь клонируйте выбранных людей -

offspring = list(map(toolbox.clone, offspring))

Примените кроссовер и мутацию к потомству -

for child1, child2 in zip(offspring[::2], offspring[1::2]):
   if random.random() < probab_crossing:
   toolbox.mate(child1, child2)

Удалить значение пригодности для ребенка

del child1.fitness.values
del child2.fitness.values

Теперь примените мутацию -

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

Оцените людей с инвалидностью -

invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
fitnesses = map(toolbox.evaluate, invalid_ind)
for ind, fit in zip(invalid_ind, fitnesses):
   ind.fitness.values = fit
print('Evaluated', len(invalid_ind), 'individuals')

Теперь замените популяцию особью следующего поколения -

population[:] = offspring

Распечатайте статистику по текущим поколениям -

fits = [ind.fitness.values[0] for ind in population]
length = len(population)
mean = sum(fits) / length
sum2 = sum(x*x for x in fits)
std = abs(sum2 / length - mean**2)**0.5
print('Min =', min(fits), ', Max =', max(fits))
print('Average =', round(mean, 2), ', Standard deviation =',
round(std, 2))
print("\n- Evolution ends")

Распечатайте окончательный результат -

best_ind = tools.selBest(population, 1)[0]
   print('\nBest individual:\n', best_ind)
   print('\nNumber of ones:', sum(best_ind))
Following would be the output:
Evolution process starts
Evaluated 500 individuals
- Generation 0
Evaluated 295 individuals
Min = 32.0 , Max = 45.0
Average = 40.29 , Standard deviation = 2.61
- Generation 1
Evaluated 292 individuals
Min = 34.0 , Max = 45.0
Average = 42.35 , Standard deviation = 1.91
- Generation 2
Evaluated 277 individuals
Min = 37.0 , Max = 45.0
Average = 43.39 , Standard deviation = 1.46
… … … …
- Generation 9
Evaluated 299 individuals
Min = 40.0 , Max = 45.0
Average = 44.12 , Standard deviation = 1.11
- Evolution ends
Best individual:
[0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 
 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0,
 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1]
Number of ones: 15

Проблема регрессии символов

Это одна из самых известных проблем генетического программирования. Все задачи символьной регрессии используют произвольное распределение данных и пытаются подогнать наиболее точные данные с помощью символьной формулы. Обычно такой показатель, как RMSE (среднеквадратическая ошибка), используется для измерения физической подготовки человека. Это классическая задача регрессора, и здесь мы используем уравнение5x³-6x²+8x=1. Нам нужно выполнить все шаги, указанные в приведенном выше примере, но основная часть будет заключаться в создании примитивных наборов, поскольку они являются строительными блоками для отдельных лиц, чтобы можно было начать оценку. Здесь мы будем использовать классический набор примитивов.

Следующий код Python подробно объясняет это -

import operator
import math
import random
import numpy as np
from deap import algorithms, base, creator, tools, gp
def division_operator(numerator, denominator):
   if denominator == 0:
      return 1
   return numerator / denominator
def eval_func(individual, points):
   func = toolbox.compile(expr=individual)
   return math.fsum(mse) / len(points),
def create_toolbox():
   pset = gp.PrimitiveSet("MAIN", 1)
   pset.addPrimitive(operator.add, 2)
   pset.addPrimitive(operator.sub, 2)
   pset.addPrimitive(operator.mul, 2)
   pset.addPrimitive(division_operator, 2)
   pset.addPrimitive(operator.neg, 1)
   pset.addPrimitive(math.cos, 1)
   pset.addPrimitive(math.sin, 1)
   pset.addEphemeralConstant("rand101", lambda: random.randint(-1,1))
   pset.renameArguments(ARG0 = 'x')
   creator.create("FitnessMin", base.Fitness, weights = (-1.0,))
   creator.create("Individual",gp.PrimitiveTree,fitness=creator.FitnessMin)
   toolbox = base.Toolbox()
   toolbox.register("expr", gp.genHalfAndHalf, pset=pset, min_=1, max_=2)
   toolbox.expr)
   toolbox.register("population",tools.initRepeat,list, toolbox.individual)
   toolbox.register("compile", gp.compile, pset = pset)
   toolbox.register("evaluate", eval_func, points = [x/10. for x in range(-10,10)])
   toolbox.register("select", tools.selTournament, tournsize = 3)
   toolbox.register("mate", gp.cxOnePoint)
   toolbox.register("expr_mut", gp.genFull, min_=0, max_=2)
   toolbox.register("mutate", gp.mutUniform, expr = toolbox.expr_mut, pset = pset)
   toolbox.decorate("mate", gp.staticLimit(key = operator.attrgetter("height"), max_value = 17))
   toolbox.decorate("mutate", gp.staticLimit(key = operator.attrgetter("height"), max_value = 17))
   return toolbox
if __name__ == "__main__":
   random.seed(7)
   toolbox = create_toolbox()
   population = toolbox.population(n = 450)
   hall_of_fame = tools.HallOfFame(1)
   stats_fit = tools.Statistics(lambda x: x.fitness.values)
   stats_size = tools.Statistics(len)
   mstats = tools.MultiStatistics(fitness=stats_fit, size = stats_size)
   mstats.register("avg", np.mean)
   mstats.register("std", np.std)
   mstats.register("min", np.min)
   mstats.register("max", np.max)
   probab_crossover = 0.4
   probab_mutate = 0.2
   number_gen = 10
   population, log = algorithms.eaSimple(population, toolbox,
      probab_crossover, probab_mutate, number_gen,
      stats = mstats, halloffame = hall_of_fame, verbose = True)

Обратите внимание, что все основные шаги такие же, как и при генерации битовых комбинаций. Эта программа даст нам результат в виде min, max, std (стандартное отклонение) после 10 поколений.