Содержание
Памятка: ключевые шаги при реализации генетического алгоритма
- Определите задачу и способ кодирования решений (хромосомы).
- Напишите функцию приспособленности (fitness).
- Создайте начальную популяцию случайных особей.
- Реализуйте селекцию (например, турнирную или рулеточную).
- Реализуйте оператор скрещивания (одноточечный или двухточечный кроссинговер).
- Реализуйте оператор мутации с заданной вероятностью.
- Сформируйте новое поколение из потомков.
- Проверьте условие остановки (поколения или точность).
- Верните лучшее найденное решение.
- Протестируйте алгоритм на простой задаче (например, OneMax).
Реализация задачи OneMax на Python
Вначале подключим необходимые библиотеки и зададим глобальные константы для работы нашего варианта ГА:
import random import as plt # константы задачи ONE_MAX_LENGTH = 100 # длина подлежащей оптимизации битовой строки # константы генетического алгоритма POPULATION_SIZE = 200 # количество индивидуумов в популяции P_CROSSOVER = 0.9 # вероятность скрещивания P_MUTATION = 0.1 # вероятность мутации индивидуума MAX_GENERATIONS = 50 # максимальное количество поколений
Далее, я зафиксирую счетчик псевдослучайных чисел, так, чтобы и у меня и у вас он выдавал одну и ту же реализацию случайных значений:
В конструкторе этого класса мы вызовем конструктор базового класса и дополнительно определим локальное свойство fitness, через которое мы будем получать значение приспособленности данного индивидуума. Для этого дополнительно объявлен вспомогательный класс FitnessMax и при создании экземпляра этого класса в нем появляется свойство values, которое и определяет степень приспособленности особи. В самом начале мы инициализируем эту величину равной нулю.
Далее, определим функцию принадлежности, которая будет вычислять приспособленность отдельной особи:
Вычисляем текущие значения приспособленности для каждой особи в начальной популяции и сохраняем эти значения в свойстве values каждого индивидуума:
Затем, определяем вспомогательные списки для хранения лучшей и средней приспособленности в каждом текущем поколении:
Далее, нам понадобятся функции для клонирования индивида, выполнения турнирного отбора, одноточечного скрещивания и мутации:
def clone(value): ind = Individual(value[:]) = 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 = (0, p_len-1), (0, p_len-1), (0, p_len-1) (max([population[i1], population[i2], population[i3]], key=lambda ind:)) return offspring def cxOnePoint(child1, child2): s = (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 () < indpb: mutant[indx] = 0 if mutant[indx] == 1 else 1
Перед главным циклом ГА мы вычислим список значений приспособленностей для всех хромосом в популяции:
И, затем, в условиях цикла пропишем либо достижение максимальной приспособленности, либо достижение максимального числа поколений:
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 () < P_CROSSOVER: cxOnePoint(child1, child2) for mutant in offspring: if () < P_MUTATION: mutFlipBit(mutant, indpb=1.0/ONE_MAX_LENGTH) freshFitnessValues = list(map(oneMaxFitness, offspring)) for individual, fitnessValue in zip(offspring, freshFitnessValues): = fitnessValue population[:] = offspring fitnessValues = [for ind in population] maxFitness = max(fitnessValues) meanFitness = sum(fitnessValues) / len(population) (maxFitness) (meanFitness) print(f»Поколение {generationCounter}: Макс приспособ. = {maxFitness}, Средняя приспособ.= {meanFitness}») best_index = (max(fitnessValues)) print(«Лучший индивидуум = «, *population[best_index], «\n»)
Непосредственно в цикле мы увеличиваем счетчик популяции, выполняем турнирный отбор для выбора родителей. После того, как оператор отбора выполнен, необходимо создать копии выбранных особей, так как некоторые могут быть отобраны дважды и, фактически, получим две разные ссылки на один и тот же список. Это нарушит логику работы ГА. Поэтому, необходимо выполнить клонирование данных.
Далее, последовательно выбираем четные и нечетные особи в качестве родителей и с вероятностью P_CROSSOVER выполняем операцию одноточечного скрещивания.
То же самое и для мутации. Перебираем особей в формируемой популяции и с вероятностью P_MUTATION подвергаем хромосому случайному изменению. При этом, дополнительно определяем вероятность indpb для инвертирования конкретного бита (гена) в хромосоме.
После этого пересчитываем приспособленности особей, обновляем свойство values, список популяции population и список fitnessValues.
В конце цикла выбираем максимальное и среднее значения приспособленности в текущей популяции, добавляем их в списки maxFitnessValues и meanFitnessValues и выводим текущую информацию в консоль.
После цикла отображаем графики изменения максимальной и средней приспособленностей для каждого поколения:
(maxFitnessValues, color=’red’) (meanFitnessValues, color=’green’) (‘Поколение’) (‘Макс/средняя приспособленность’) (‘Зависимость максимальной и средней приспособленности от поколения’) ()
Все, мы создали простой ГА для решения задачи OneMax. После запуска программы увидим следующий результат:
То есть, наша простейшая реализация ГА по имитации процесса эволюции позволила получить наиболее приспособленную особь, состоящую из всех единиц. Другими словами, ГА нашел решение поставленной задачи.
Как видите, у нас получилась довольно внушительная программа даже для такого простого алгоритма. Разумеется, существуют способы ее сокращения и на следующем занятии мы рассмотрим один из них – использование пакета DEAP для реализаций самых разных ГА.
В следующих сериях…
- Реализация других функций селекции, скрещивания и мутации. Например, интересно посмотреть, как в поставленной задаче будет работать турнирный метод селекции aka естественный отбор
- Сравнение по времени и эффективности подобных алгоритмов со стандартными методами оптимизации, например, градиентным спуском
- Новые функции пакета (вероятно)
- python
- питон
- генетический алгоритм
- оптимизация
- визуализация
- matplotlib
- матемактика
- математическое моделирование
- Python
- Алгоритмы
- Биотехнологии
- Математика
- Программирование
Оставляя почту, я принимаю Политику конфиденциальности и даю согласие на получение рассылок
Часто задаваемые вопросы о создании генетического алгоритма на Python
Вопрос: С чего начать написание генетического алгоритма на Python?
Ответ: Начните с импорта библиотеки random и определения фитнес-функции для вашей задачи.
Вопрос: Какие библиотеки Python нужны для генетического алгоритма?
Ответ: Для базовой реализации достаточно random, для продвинутой — DEAP или PyGAD.
Вопрос: Как выбрать размер популяции в генетическом алгоритме?
Ответ: Обычно от 50 до 500 особей, в зависимости от сложности задачи.
Вопрос: Что такое функция приспособленности (fitness function)?
Ответ: Это функция, которая оценивает, насколько хорошо каждое решение соответствует цели.
Вопрос: Как реализовать оператор скрещивания (crossover) в Python?
Ответ: Выберите две родительские особи и случайным образом обменяйте их части генов.
Вопрос: Как работает мутация в генетическом алгоритме?
Ответ: С небольшой вероятностью случайно изменяются отдельные гены в хромосоме.
Вопрос: Когда останавливать выполнение генетического алгоритма?
Ответ: При достижении максимального числа поколений или при нахождении решения с заданной точностью.
Вопрос: Как избежать преждевременной сходимости алгоритма?
Ответ: Используйте высокую вероятность мутации и турнирную селекцию.
Вопрос: Можно ли использовать генетический алгоритм для оптимизации нейросетей?
Ответ: Да, для подбора весов или архитектуры нейронной сети.
Вопрос: Как визуализировать работу генетического алгоритма на Python?
Ответ: Используйте matplotlib для построения графика изменения лучшей приспособленности по поколениям.
