9.1 Введение в генетические алгоритмы
Генетические алгоритмы (GA) — это метод оптимизации и поиска, вдохновлённый процессом естественного отбора, который имитирует биологические эволюционные процессы.
Генетические алгоритмы применяются для решения сложных задач, где традиционные методы могут быть неэффективными. Эти алгоритмы используют механизмы селекции, скрещивания (кроссовер) и мутаций для эволюции решений.
Принципы работы:
1. Инициализация:
Создаётся начальная популяция возможных решений (хромосом). Каждое решение кодируется в виде строки (битовой строки, строки символов или других структур).
2. Функция приспособленности (fitness function):
Оценивает качество каждого решения в популяции.
3. Оценка:
Каждое решение (индивид) оценивается с помощью функции приспособленности (fitness function), которая определяет, насколько хорошо решение решает задачу.
4. Селекция:
Решения с лучшей приспособленностью имеют больше шансов быть выбранными для воспроизводства. Часто используются методы, такие как рулеточный отбор (roulette wheel selection), турнирный отбор (tournament selection) и отбор по ранжированию (rank selection).
5. Скрещивание (кроссовер):
Избранные решения (родители) комбинируются для создания новых решений (потомков). Кроссовер может быть одноточечным, двуточечным или многоточечным.
6. Мутация:
Случайные изменения в новых решениях (мутации) применяются для введения разнообразия. Это помогает алгоритму избежать локальных минимумов.
7. Замена:
Новая популяция заменяет старую, и процесс повторяется до тех пор, пока не будет выполнено условие остановки (например, достижение определённого количества поколений или достижение определённой приспособленности).
Преимущества и недостатки
Преимущества:
- Широкий спектр применения: Могут применяться для решения различных задач, включая те, где аналитические методы не работают.
- Глобальная оптимизация: Способны находить глобальные оптимумы в многомерных и сложных пространствах.
- Гибкость: Могут использоваться с любой функцией приспособленности.
Недостатки:
- Высокие вычислительные затраты: Требуют значительных вычислительных ресурсов, особенно для больших популяций и сложных задач.
- Трудности с настройкой параметров: Подбор параметров (размер популяции, вероятность мутации и кроссовера) может быть сложным и сильно влиять на производительность.
- Отсутствие гарантии оптимального решения: Нет гарантии, что найденное решение будет глобально оптимальным.
Фактически генетический алгоритм является высокоэффективной эвристикой. Он не гарантирует нахождение наилучшего решения, даже если имеет доступ ко всем данным. Но для сложных ситуаций и громадных объемов данных он очень быстро выдает решение приближенное к идеальному.
9.2 Пример применения
Рассмотрим пример применения генетического алгоритма для оптимизации функции.
import random
# Параметры генетического алгоритма
POPULATION_SIZE = 100
GENERATIONS = 1000
MUTATION_RATE = 0.01
TOURNAMENT_SIZE = 5
# Определение функции приспособленности
def fitness_function(x):
return -x**2 + 10*x
# Инициализация популяции
def initialize_population(size):
return [random.uniform(-10, 10) for _ in range(size)]
# Селекция (турнирный отбор)
def tournament_selection(population):
tournament = random.sample(population, TOURNAMENT_SIZE)
return max(tournament, key=fitness_function)
# Кроссовер (одноточечный)
def crossover(parent1, parent2):
alpha = random.random()
return alpha * parent1 + (1 - alpha) * parent2
# Мутация
def mutate(individual):
if random.random() < MUTATION_RATE:
return individual + random.gauss(0, 1)
return individual
# Основной цикл генетического алгоритма
population = initialize_population(POPULATION_SIZE)
for generation in range(GENERATIONS):
new_population = []
for _ in range(POPULATION_SIZE):
parent1 = tournament_selection(population)
parent2 = tournament_selection(population)
offspring = crossover(parent1, parent2)
offspring = mutate(offspring)
new_population.append(offspring)
population = new_population
# Вывод лучшего решения
best_individual = max(population, key=fitness_function)
print("Лучшее решение:", best_individual)
print("Значение функции:", fitness_function(best_individual))
Преимущества и недостатки
9.3 Оптимизация многомерной функции
Задача:
Найти минимальное значение многомерной функции.
Решение:
Берем предыдущий шаблон
import numpy as np
def fitness_function(x):
return np.sum(x ** 2)
def create_individual(dim):
return np.random.uniform(-10, 10, dim)
def create_population(pop_size, dim):
return np.array([create_individual(dim) for _ in range(pop_size)])
def select_individuals(population, fitness, num_parents):
parents = np.empty((num_parents, population.shape[1]))
for parent_num in range(num_parents):
min_fitness_idx = np.where(fitness == np.min(fitness))
min_fitness_idx = min_fitness_idx[0][0]
parents[parent_num, :] = population[min_fitness_idx, :]
fitness[min_fitness_idx] = float('inf')
return parents
def crossover(parents, offspring_size):
offspring = np.empty(offspring_size)
crossover_point = np.uint8(offspring_size[1] / 2)
for k in range(offspring_size[0]):
parent1_idx = k % parents.shape[0]
parent2_idx = (k + 1) % parents.shape[0]
offspring[k, 0:crossover_point] = parents[parent1_idx, 0:crossover_point]
offspring[k, crossover_point:] = parents[parent2_idx, crossover_point:]
return offspring
def mutate(offspring, mutation_rate):
for idx in range(offspring.shape[0]):
if np.random.rand() < mutation_rate:
random_value = np.random.uniform(-1.0, 1.0, 1)
offspring[idx, 4] = offspring[idx, 4] + random_value
return offspring
def genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations):
population = create_population(pop_size, dim)
for generation in range(num_generations):
fitness = np.array([fitness_function(ind) for ind in population])
parents = select_individuals(population, fitness, num_parents)
offspring_crossover = crossover(parents, (pop_size - parents.shape[0], dim))
offspring_mutation = mutate(offspring_crossover, mutation_rate)
population[0:parents.shape[0], :] = parents
population[parents.shape[0]:, :] = offspring_mutation
best_solution = population[np.argmin(fitness)]
return best_solution
# Пример использования:
dim = 10
pop_size = 100
num_parents = 20
mutation_rate = 0.01
num_generations = 1000
best_solution = genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations)
print(f"Лучшее решение: {best_solution}")
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ