|
Делаем генетический алгоритм для задачи OneMaxАрхив проекта: ga_2.py На предыдущем занятии мы с вами в целом познакомились со структурой ГА, и чтобы все лучше понять, реализуем его для простой, но наглядной задачи OneMax.
Как мы уже отмечали, в этой задаче популяция состоит из списков, содержащих нули и единицы:
Наша цель – найти решение, которое бы давало максимальную сумму цифр этого списка:
Здесь N – длина списка. Очевидно, лучший, наиболее приспособленный индивид, должен состоять из всех единиц:
Это и есть решение данной задачи. В рамках задачи OneMax мы воспользуемся идеей турнирного отбора с выборкой из трех претендентов на каждой итерации:
Будем использовать одноточечное скрещивание (одноточечный кроссинговер):
А при мутации будем выполнять инвертирование бита с некоторой очень небольшой вероятностью:
Реализация задачи OneMax на PythonВначале подключим необходимые библиотеки и зададим глобальные константы для работы нашего варианта ГА: import random import matplotlib.pyplot as plt # константы задачи ONE_MAX_LENGTH = 100 # длина подлежащей оптимизации битовой строки # константы генетического алгоритма POPULATION_SIZE = 200 # количество индивидуумов в популяции P_CROSSOVER = 0.9 # вероятность скрещивания P_MUTATION = 0.1 # вероятность мутации индивидуума MAX_GENERATIONS = 50 # максимальное количество поколений Далее, я зафиксирую счетчик псевдослучайных чисел, так, чтобы и у меня и у вас он выдавал одну и ту же реализацию случайных значений: RANDOM_SEED = 42 random.seed(RANDOM_SEED) Таким образом, будет обеспечена воспроизводимость эксперимента в разное время и на разных устройствах. Для представления каждого индивидуума в популяции, мы объявим класс с именем Individual, который будет наследоваться от базового класса list (это класс для представления списков в Python). То есть, хромосома особи будет представлена обычным списком и содержать целые числа 0 или 1: class FitnessMax(): def __init__(self): self.values = [0] class Individual(list): def __init__(self, *args): super().__init__(*args) self.fitness = FitnessMax() В конструкторе этого класса мы вызовем конструктор базового класса и дополнительно определим локальное свойство fitness, через которое мы будем получать значение приспособленности данного индивидуума. Для этого дополнительно объявлен вспомогательный класс FitnessMax и при создании экземпляра этого класса в нем появляется свойство values, которое и определяет степень приспособленности особи. В самом начале мы инициализируем эту величину равной нулю. Далее, определим функцию принадлежности, которая будет вычислять приспособленность отдельной особи: def oneMaxFitness(individual): return sum(individual), # кортеж И еще две функции для создания отдельного индивидуума и всей популяции: def individualCreator(): return Individual([random.randint(0, 1) for i in range(ONE_MAX_LENGTH)]) def populationCreator(n = 0): return list([individualCreator() for i in range(n)]) После этого создаем начальную популяцию и определяем счетчик поколений: population = populationCreator(n=POPULATION_SIZE) generationCounter = 0 Вычисляем текущие значения приспособленности для каждой особи в начальной популяции и сохраняем эти значения в свойстве values каждого индивидуума: fitnessValues = list(map(oneMaxFitness, population)) for individual, fitnessValue in zip(population, fitnessValues): individual.fitness.values = fitnessValue Затем, определяем вспомогательные списки для хранения лучшей и средней приспособленности в каждом текущем поколении: maxFitnessValues = [] meanFitnessValues = [] Далее, нам понадобятся функции для клонирования индивида, выполнения турнирного отбора, одноточечного скрещивания и мутации: def clone(value): ind = Individual(value[:]) ind.fitness.values[0] = value.fitness.values[0] return ind def selTournament(population, p_len): offspring = [] for n in range(p_len): i1 = i2 = i3 = 0 while i1 == i2 or i1 == i3 or i2 == i3: i1, i2, i3 = random.randint(0, p_len-1), random.randint(0, p_len-1), random.randint(0, p_len-1) offspring.append(max([population[i1], population[i2], population[i3]], key=lambda ind: ind.fitness.values[0])) return offspring def cxOnePoint(child1, child2): s = random.randint(2, len(child1)-3) child1[s:], child2[s:] = child2[s:], child1[s:] def mutFlipBit(mutant, indpb=0.01): for indx in range(len(mutant)): if random.random() < indpb: mutant[indx] = 0 if mutant[indx] == 1 else 1 Перед главным циклом ГА мы вычислим список значений приспособленностей для всех хромосом в популяции: fitnessValues = [individual.fitness.values[0] for individual in population] И, затем, в условиях цикла пропишем либо достижение максимальной приспособленности, либо достижение максимального числа поколений: while max(fitnessValues) < ONE_MAX_LENGTH and generationCounter < MAX_GENERATIONS: generationCounter += 1 offspring = selTournament(population, len(population)) offspring = list(map(clone, offspring)) for child1, child2 in zip(offspring[::2], offspring[1::2]): if random.random() < P_CROSSOVER: cxOnePoint(child1, child2) for mutant in offspring: if random.random() < P_MUTATION: mutFlipBit(mutant, indpb=1.0/ONE_MAX_LENGTH) freshFitnessValues = list(map(oneMaxFitness, offspring)) for individual, fitnessValue in zip(offspring, 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(f"Поколение {generationCounter}: Макс приспособ. = {maxFitness}, Средняя приспособ.= {meanFitness}") best_index = fitnessValues.index(max(fitnessValues)) print("Лучший индивидуум = ", *population[best_index], "\n") Непосредственно в цикле мы увеличиваем счетчик популяции, выполняем турнирный отбор для выбора родителей. После того, как оператор отбора выполнен, необходимо создать копии выбранных особей, так как некоторые могут быть отобраны дважды и, фактически, получим две разные ссылки на один и тот же список. Это нарушит логику работы ГА. Поэтому, необходимо выполнить клонирование данных. Далее, последовательно выбираем четные и нечетные особи в качестве родителей и с вероятностью P_CROSSOVER выполняем операцию одноточечного скрещивания. То же самое и для мутации. Перебираем особей в формируемой популяции и с вероятностью P_MUTATION подвергаем хромосому случайному изменению. При этом, дополнительно определяем вероятность indpb для инвертирования конкретного бита (гена) в хромосоме. После этого пересчитываем приспособленности особей, обновляем свойство values, список популяции population и список fitnessValues. В конце цикла выбираем максимальное и среднее значения приспособленности в текущей популяции, добавляем их в списки maxFitnessValues и meanFitnessValues и выводим текущую информацию в консоль. После цикла отображаем графики изменения максимальной и средней приспособленностей для каждого поколения: plt.plot(maxFitnessValues, color='red') plt.plot(meanFitnessValues, color='green') plt.xlabel('Поколение') plt.ylabel('Макс/средняя приспособленность') plt.title('Зависимость максимальной и средней приспособленности от поколения') plt.show() Все, мы создали простой ГА для решения задачи OneMax. После запуска программы увидим следующий результат:
А также строчки в консоли: Поколение
50: Макс приспособ. = 100, Средняя приспособ.= 98.525
То есть, наша простейшая реализация ГА по имитации процесса эволюции позволила получить наиболее приспособленную особь, состоящую из всех единиц. Другими словами, ГА нашел решение поставленной задачи. Как видите, у нас получилась довольно внушительная программа даже для такого простого алгоритма. Разумеется, существуют способы ее сокращения и на следующем занятии мы рассмотрим один из них – использование пакета DEAP для реализаций самых разных ГА. Видео по теме |
