Генетические алгоритмы и эволюционная оптимизация

Эволюция как алгоритм оптимизации

Природная эволюция решила «задачу оптимизации» колоссальной сложности: создать существ, способных выживать в меняющейся среде. Механизм: случайные мутации, рекомбинация генов (кроссовер), естественный отбор. Генетические алгоритмы (GA) имитируют этот процесс для оптимизации. Вместо одной «частицы» в пространстве решений — целая «популяция», которая эволюционирует. Это обеспечивает глобальный поиск: разные особи исследуют разные части пространства.

Структура генетического алгоритма

Хромосома (особь): кодировка решения в виде вектора. Для TSP — перестановка городов. Для задачи рюкзака — бинарная строка.

Приспособленность (fitness): значение целевой функции. В GA обычно работаем с максимизацией, поэтому: fitness = −cost для задач минимизации.

Основной цикл GA:

Инициализация: генерируем начальную популяцию P₀ из N случайных решений
Оценка: вычисляем fitness(s) для каждого s ∈ P
Отбор: выбираем «родителей» пропорционально приспособленности
- Рулеточный отбор: P(выбрать s) = fitness(s) / Σ fitness. Аналог «вращения рулетки»
- Турнирный отбор: случайно выбираем k особей, побеждает лучшая. Параметр k — «давление отбора»
Кроссовер (скрещивание): создаём потомков из пары родителей
Мутация: случайно изменяем некоторых потомков
Замена: формируем новую популяцию из потомков (+ часть родителей)
Повторяем до критерия остановки (поколения или время)

Операторы для TSP

Задача: хромосома = перестановка городов π = (π₁, π₂, ..., πₙ). Кроссовер должен давать корректные перестановки (каждый город ровно один раз).

Order Crossover (OX):

Выбрать случайный отрезок [l, r] родителя P1
Скопировать π₁[l..r] в потомка на те же позиции
Оставшиеся позиции заполнить из P2 в порядке появления (пропуская уже включённые)

Пример: P1 = (1,2,3,4,5), P2 = (3,4,1,5,2), отрезок [2,4].

Потомок: ( _, 2, 3, 4, _ ). Из P2 в порядке 3,4,1,5,2, пропуская 2,3,4: берём 1, 5. Потомок = (1, 2, 3, 4, 5). (В данном случае без изменений, реальный пример сложнее.)

Мутация для TSP:

Swap: случайно поменять два города местами
Insertion: вырвать один город и вставить в другое место
Inversion (2-opt): обратить случайный подмаршрут

Вероятность мутации обычно мала: 0.01–0.05.

Теоретические основы: Schema Theorem

Шаблон (schema) H: строка из {0, 1, *}, где * — «дон't care» (любое значение). Например: H = (1, *, 0, *) описывает все строки, начинающиеся с 1 и имеющие 0 на 3-й позиции.

Порядок шаблона o(H) = число фиксированных позиций (не-*). Длина определяющего отрезка l(H) = расстояние между крайними фиксированными позициями.

Schema Theorem (Холланд): шаблон H, имеющий выше среднего приспособленность f̄(H) > f̄_pop (среднее по популяции), растёт экспоненциально в следующем поколении:

E[m(H, t+1)] ≥ m(H,t) · f̄(H)/f̄ · (1 − p_c · l(H)/(n−1)) · (1 − p_m)^{o(H)}

где m(H,t) — число особей шаблона H в момент t, p_c — вероятность кроссовера, p_m — мутации.

Интерпретация: «хорошие, короткие, старательные» шаблоны экспоненциально растут. Это основа теории «строительных блоков» (building blocks).

Memetic Algorithms (MA)

GA ищет «хорошие» области пространства, но «не дожимает» локально. Решение: Memetic Algorithm = GA + Local Search:

Для каждого потомка, полученного кроссовером/мутацией, запускаем локальный поиск (2-opt для TSP).

Результат: MA для TSP значительно лучше чистого GA или чистого LS:

Чистый GA: исследует пространство глобально, но решения не «доведены»
Чистый LS: застревает в локальных оптимумах
MA: глобальный поиск + локальная «полировка»

Пример: LKH (Lin-Kernighan-Helsgott) для TSP использует MA: GA для комбинирования хороших туров + LK для локального поиска. Лучший практический алгоритм для TSP.

NSGA-II: многокритериальная оптимизация

Часто нужно оптимизировать несколько конфликтующих критериев одновременно (стоимость vs. качество, риск vs. доходность). Нет единственного оптимума — есть фронт Парето: решения, в которых нельзя улучшить один критерий, не ухудшив другой.

NSGA-II (Non-dominated Sorting GA, Deb 2002): стандарт для многокритериальной GA-оптимизации.

Операторы отбора:

Non-domination rank: решения ранжируются по «уровню доминирования»: ранг 1 = не доминируется никем, ранг 2 = доминируется только рангом 1, и т.д.
Crowding distance: расстояние до соседей по фронту. Предпочитаем «менее населённые» зоны — разнообразие.

Применения NSGA-II: аэрокосмическая инженерия (оптимизация конструкций), химическая промышленность (оптимизация реакторов), финансы (фронт риск-доходность), электроника (схемотехническая оптимизация). Это индустриальный стандарт многокритериальной оптимизации.