Реализация генетического алгоритма на Python: от основ до продвинутых примеров
Введение в генетические алгоритмы
Генетический алгоритм (ГА) – это эвристический метод оптимизации, вдохновлённый естественным отбором. На Python его реализация позволяет решать задачи поиска экстремумов, подбора параметров и комбинаторной оптимизации. В статье рассмотрены различные подходы к реализации: от библиотечных решений до написания кода с нуля, с указанием типичных проблем и способов их устранения.
Как реализовать генетический алгоритм с использованием библиотеки DEAP?
Библиотека DEAP (Distributed Evolutionary Algorithms in Python) предоставляет готовые компоненты для построения ГА. Это самый эффективный способ для быстрого прототипирования и задач средней сложности.
Установка: pip install deap
Пример: максимизация функции f(x) = x^2 для целочисленных x от 0 до 31. Особи – 5-битные двоичные строки.
import random
from deap import base, creator, tools, algorithms
# Определяем тип особи (максимизация приспособленности)
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)
# Особь из 5 бит
toolbox.register("individual", tools.initRepeat, creator.Individual,
toolbox.attr_bool, n=5)
# Популяция из 10 особей
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
def evalOneMax(individual):
# Преобразуем биты в целое число и возвращаем квадрат
x = int(''.join(str(b) for b in individual), 2)
return (x * x,)
toolbox.register("evaluate", evalOneMax)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)
# Запуск алгоритма
pop = toolbox.population(n=10)
result = algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=20,
verbose=False)
# Лучшая особь
best = tools.selBest(pop, k=1)[0]
print("Лучшая особь:", best, "-> x =", int(''.join(str(b) for b in best), 2),
"f(x)=", evalOneMax(best)[0])генетический алгоритм python (генетический алгоритм на python)
Типичная ошибка: неправильное определение функции приспособленности – она должна возвращать кортеж, даже для одного значения. Проблема: при использовании `weights=(1.0,)` для минимизации нужно указать (-1.0,). Если забыть преобразовать биты в число, алгоритм будет работать с битовой строкой, а не с реальным значением.
Как написать генетический алгоритм с нуля на Python?
Этот вариант полезен для глубокого понимания механики и для случаев, когда требуется тонкая настройка или нестандартные операторы.
import random
POP_SIZE = 10
GENES = 5
MUT_RATE = 0.1
CX_RATE = 0.5
NGEN = 20
def create_individual():
return [random.randint(0, 1) for _ in range(GENES)]
def fitness(ind):
x = int(''.join(map(str, ind)), 2)
return x * x
def selection(pop, fit_vals):
# Турнирный отбор
selected = []
for _ in range(len(pop)):
i, j = random.sample(range(len(pop)), 2)
selected.append(pop[i] if fit_vals[i] > fit_vals[j] else pop[j])
return selected
def crossover(p1, p2):
if random.random() < CX_RATE:
point = random.randint(1, GENES-1)
return p1[:point] + p2[point:], p2[:point] + p1[point:]
return p1[:], p2[:]
def mutate(ind):
return [1-b if random.random() < MUT_RATE else b for b in ind]
pop = [create_individual() for _ in range(POP_SIZE)]
for gen in range(NGEN):
fit_vals = [fitness(ind) for ind in pop]
parents = selection(pop, fit_vals)
next_pop = []
for i in range(0, POP_SIZE, 2):
off1, off2 = crossover(parents[i], parents[i+1])
next_pop.append(mutate(off1))
next_pop.append(mutate(off2))
pop = next_pop
best = max(pop, key=fitness)
print("Лучший индивид:", best, "fitness =", fitness(best))Распространённая ошибка: забыть изменить размер популяции после скрещивания (количество потомков должно совпадать). Или использовать неверный тип данных – списки изменяемы, и при копировании ссылок возникают побочные эффекты. Рекомендуется всегда создавать новые списки.
Как использовать PyGAD для генетического алгоритма?
PyGAD – библиотека, ориентированная на простоту и задачи машинного обучения. Позволяет задавать свою функцию приспособленности, типы генов и многое другое.
import pygad
def fitness_func(ga_instance, solution, idx):
x = int(''.join(map(str, solution.astype(int))), 2)
return x * x
num_genes = 5
ga_instance = pygad.GA(num_generations=20,
num_parents_mating=5,
fitness_func=fitness_func,
sol_per_pop=10,
num_genes=num_genes,
gene_type=int,
init_range_low=0,
init_range_high=2,
parent_selection_type="tournament",
crossover_type="two_points",
mutation_type="random",
mutation_percent_genes=10)
ga_instance.run()
solution, fit, idx = ga_instance.best_solution()
print("Лучшее решение:", solution, "fit =", fit)Ошибка: если не указать `gene_type=int`, библиотека создаст вещественные числа, что не подходит для двоичного кодирования. Также стоит проверить, что `init_range_low` и `init_range_high` заданы правильно (0 и 2, где 2 – эксклюзив).
Как ускорить генетический алгоритм с помощью NumPy?
Для решения задач с большими популяциями или высокой размерностью векторизация вычислений с использованием NumPy даёт значительный прирост производительности.
import numpy as np
POP_SIZE = 50
GENES = 20
pop = np.random.randint(0, 2, (POP_SIZE, GENES))
# Функция приспособленности для осей: сумма квадратов десятичных значений
def fitness_np(pop):
# Преобразуем биты в десятичные числа
powers = 2 ** np.arange(GENES-1, -1, -1)
x = np.dot(pop, powers)
return x ** 2
for gen in range(100):
fits = fitness_np(pop)
# Турнирный отбор (векторизованный)
idx = np.random.randint(0, POP_SIZE, (POP_SIZE, 2))
i1, i2 = idx[:,0], idx[:,1]
winners = np.where(fits[i1] > fits[i2], i1, i2)
parents = pop[winners]
# Двухточечное скрещивание (векторизованное)
points = np.random.randint(1, GENES-1, size=POP_SIZE)
mask = np.arange(GENES) < points[:, None]
offspring = np.where(mask, parents[0::2], parents[1::2])
# Мутация
mutation_mask = np.random.rand(POP_SIZE, GENES) < 0.1
offspring = np.where(mutation_mask, 1 - offspring, offspring)
pop = offspring
best_idx = np.argmax(fitness_np(pop))
print("Лучший:", pop[best_idx], "fit =", fitness_np(pop[best_idx])[best_idx])Частая проблема: неправильное формирование масок при скрещивании – нужно следить, чтобы количество потомков совпадало с POP_SIZE (равным численностью родителей). Ошибки при broadcasting могут привести к неверным размерам. Рекомендуется проверять shape промежуточных массивов.
Расширенные примеры применения генетического алгоритма
Пример: задача коммивояжера с использованием DEAP
Генетический алгоритм способен находить субоптимальные маршруты для задачи коммивояжера (TSP). Кодирование – порядок городов (перестановка).
import random, math
from deap import base, creator, tools, algorithms
# Координаты городов
cities = [(0, 0), (1, 2), (3, 1), (5, 2), (4, 5), (2, 4)]
n = len(cities)
# Матрица расстояний
dist = [[math.hypot(cities[i][0]-cities[j][0], cities[i][1]-cities[j][1])
for j in range(n)] for i in range(n)]
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)
toolbox = base.Toolbox()
toolbox.register("indices", random.sample, range(n), n)
toolbox.register("individual", tools.initIterate, creator.Individual,
toolbox.indices)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
def evalTSP(individual):
distance = sum(dist[individual[i]][individual[i+1]] for i in range(n-1))
distance += dist[individual[-1]][individual[0]] # возврат в начало
return (distance,)
toolbox.register("evaluate", evalTSP)
toolbox.register("mate", tools.cxOrdered) # для перестановок
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)
pop = toolbox.population(n=50)
algorithms.eaSimple(pop, toolbox, cxpb=0.7, mutpb=0.2, ngen=100, verbose=False)
best = tools.selBest(pop, k=1)[0]
print("Лучший маршрут:", best, "длина =", evalTSP(best)[0])Лучший маршрут: [2, 0, 1, 4, 3, 5] длина = 17.688
Ошибка: использование обычного двухточечного кроссовера для перестановок приведёт к повторяющимся городам. Обязательно использовать `cxOrdered` или `cxPartialyMatched`. При мутации `mutShuffleIndexes` перемешивает гены, что не нарушает уникальность.
Пример: оптимизация гиперпараметров нейронной сети Keras с помощью PyGAD
Генетический алгоритм может подбирать количество нейронов, скорость обучения и т.д. В этом примере оптимизируется простая сеть для задачи классификации.
import pygad.kerasga
from tensorflow.keras.models import Sequential
from tensorflow.keras.layers import Dense
from tensorflow.keras.optimizers import Adam
import numpy as np
# Генерируем синтетические данные
np.random.seed(0)
X = np.random.rand(200, 4)
y = (X[:,0] + X[:,1] > 1).astype(int)
def build_model(hyperparams):
# hyperparams: [neurons1, neurons2, lr]
model = Sequential()
model.add(Dense(int(hyperparams[0]), activation='relu', input_shape=(4,)))
model.add(Dense(int(hyperparams[1]), activation='relu'))
model.add(Dense(1, activation='sigmoid'))
model.compile(optimizer=Adam(learning_rate=hyperparams[2]),
loss='binary_crossentropy', metrics=['accuracy'])
return model
def fitness_func(ga, solution, idx):
model = build_model(solution)
history = model.fit(X, y, epochs=5, verbose=0)
loss, acc = model.evaluate(X, y, verbose=0)
return acc
ga_instance = pygad.GA(num_generations=10,
num_parents_mating=5,
fitness_func=fitness_func,
sol_per_pop=8,
num_genes=3,
gene_type=[int, int, float],
init_range_low=[4, 2, 0.001],
init_range_high=[64, 32, 0.1],
parent_selection_type="tournament",
crossover_type="uniform",
mutation_type="random",
mutation_percent_genes=20)
ga_instance.run()
solution, fit, _ = ga_instance.best_solution()
print("Лучшие гиперпараметры: нейроны1 =", int(solution[0]),
"нейроны2 =", int(solution[1]), "lr =", solution[2],
"точность =", fit)Лучшие гиперпараметры: нейроны1 = 48 нейроны2 = 12 lr = 0.023 точность = 0.995
Проблема: переобучение из-за малого количества данных. Также при каждом запуске строится и обучается новая модель, что может быть медленным. Рекомендуется ограничить количество эпох или использовать кросс-валидацию.
Пример: подбор коэффициентов полинома для аппроксимации функции
Генетический алгоритм находит коэффициенты полинома степени k, минимизирующие среднеквадратичную ошибку.
import numpy as np
from deap import base, creator, tools, algorithms
# Целевая функция
x_real = np.linspace(0, 2*np.pi, 30)
y_real = np.sin(x_real) + 0.1*np.random.randn(30)
degree = 4 # степень полинома
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)
toolbox = base.Toolbox()
toolbox.register("attr_float", random.uniform, -10, 10)
toolbox.register("individual", tools.initRepeat, creator.Individual,
toolbox.attr_float, n=degree+1)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
def evalPoly(individual):
p = np.poly1d(individual)
error = np.mean((p(x_real) - y_real)**2)
return (error,)
toolbox.register("evaluate", evalPoly)
toolbox.register("mate", tools.cxBlend, alpha=0.5)
toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=1, indpb=0.1)
toolbox.register("select", tools.selTournament, tournsize=3)
pop = toolbox.population(n=50)
algorithms.eaSimple(pop, toolbox, cxpb=0.7, mutpb=0.2, ngen=40, verbose=False)
best = tools.selBest(pop, k=1)[0]
print("Коэффициенты:", best)
print("MSE:", evalPoly(best)[0])Коэффициенты: [-0.042, 0.251, -0.988, 0.999, -0.003] (пример) MSE: 0.0128
Типичная ошибка: коэффициенты выходят за разумные пределы из-за отсутствия ограничений. Можно добавить репараметризацию или сузить диапазон `attr_float`. Также при большом числе генов скорость сходимости падает.