Генетический алгоритм

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

История

Корни генетических алгоритмов восходят к работам Джона Холланда (John Holland) в 1960-х — 1970-х годах в Мичиганском университете. Он предложил концепцию, названную «генетические алгоритмы», в своей книге «Adaptation in Natural and Artificial Systems» (1975). Холланд показал, что комбинация случайного поиска, элитизма и операторов размножения может эффективно исследовать пространства решений. В 1989 году Дэвид Голдберг (David Goldberg) опубликовал книгу «Genetic Algorithms in Search, Optimization, and Machine Learning», которая стала стандартным учебником и способствовала широкому внедрению метода в инженерии и науке. В СССР и России пионерами в области эволюционного моделирования были В.П. Маслов, К.А. Ковалёв и другие исследователи, работавшие над автоматизированным синтезом алгоритмов, но активное развитие генетических алгоритмов в русскоязычном пространстве началось в 1990-е годы.

Основные компоненты

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

Кодирование решений

Каждое возможное решение кодируется в хромосому. Наиболее распространённые способы:

• Бинарное кодирование — хромосома — строка из 0 и 1. Исторически первое и простое.
• Вещественное кодирование — хромосома — вектор действительных чисел. Часто используется для задач непрерывной оптимизации.
• Символьное кодирование — например, для задач коммивояжёра используется перестановка городов.

Выбор кодирования существенно влияет на эффективность алгоритма.

Функция пригодности (фитнес-функция)

Ключевой компонент, оценивающий качество каждого решения. Чем выше значение фитнеса, тем «лучше» хромосома. Функция пригодности всегда зависит от задачи: для задачи максимизации — целевая функция; для многокритериальных задач — свёртка или метод Парето-доминирования.

Операторы:

• Селекция (отбор) — выбор хромосом для размножения. Вероятность выбора пропорциональна фитнесу. Виды:
• Рулеточный отбор: пропорционально фитнесу.
• Турнирный отбор: случайный выбор группы, из которой берётся лучшая.
• Ранговый отбор: отбор по рангу, а не по абсолютному значению.
• Скрещивание (кроссинговер) — комбинация двух родительских хромосом для создания одного или двух потомков. Примеры:
• Одноточечный кроссинговер: обмен срезами после случайной точки.
• Многоточечный: несколько точек разрыва.
• Арифметический (для вещественных): линейная комбинация.
• Мутация — случайное изменение части хромосомы (например, инверсия бита, прибавление случайной величины). Предотвращает преждевременную сходимость к локальному оптимуму.
• Элитизм — сохранение нескольких лучших хромосом без изменений на следующую итерацию, гарантируя, что наилучшее решение не потеряется.

Параметры

• Размер популяции (обычно от 50 до 1000).
• Вероятность скрещивания (0,6–0,9).
• Вероятность мутации (0,001–0,1).
• Число поколений.

Разновидности и модификации

За десятилетия исследований предложено множество вариантов генетических алгоритмов.

По типу кодирования

• Бинарный ГА (Binary GA) — классика.
• Вещественный ГА (Real-coded GA) — для непрерывных функций без дискретизации.
• Гибридные ГА — комбинация с локальным поиском (например, алгоритмы, встраивающие метод Ньютона или имитацию отжига).

По стратегии эволюции

• Стандартные (простые) ГА (Simple GA) — одна популяция, последовательное поколение.
• Инкрементальные ГА — каждый раз заменяется только одна или несколько хромосом.
• Параллельные ГА — популяция разбивается на острова; миграция особей между ними. Ускоряет поиск на многопроцессорных системах.

Со специальными механизмами

• Популяция с адаптивной вероятностью мутации — меняется в зависимости от разнообразия популяции.
• Мульти-объективные ГА (например, NSGA-II, SPEA2) — для задач с несколькими целевыми функциями, где ищут множество решений по Парето.
• Генетическое программирование — хромосомы — программные деревья, эволюция программ.

Применение

Генетические алгоритмы нашли применение в самых разных областях.

Оптимизация

• Инженерное проектирование: форма самолётного крыла, конструкция мостов, параметры механизмов.
• Экономика — составление оптимальных инвестиционных портфелей; настройка торговых стратегий.
• Логистика — маршрутизация транспорта, задача коммивояжёра большой размерности.

Искусственный интеллект и машинное обучение

• Обучение нейронных сетей (подбор весов, топологии).
• Настройка гиперпараметров моделей (например, SVM, Random Forest).
• Синтез игровых агентов (например, эволюция стратегий в шахматах, настольных играх).

Распознавание образов и обработка сигналов

• Выбор признаков для классификации (Feature Selection).
• Оптимизация фильтров в цифровой обработке сигналов.

Биоинформатика

• Предсказание структуры белков (фолдинг).
• Множественное выравнивание последовательностей ДНК.

Интерактивные приложения

• Эволюция художественных изображений (Рисунки, музыка, дизайн), где фитнес-функция задаётся пользователем.

Преимущества и недостатки

• Преимущества:
• Работают с любыми типами целевых функций (нелинейные, недифференцируемые, шумные, с разрывами).
• Устойчивость к попаданию в локальные оптимумы (благодаря случайной мутации и популяционному поиску).
• Простота распараллеливания.
• Не требуют градиентной информации.
• Недостатки:
• Вычислительная трудоёмкость для больших популяций и многих поколений.
• Отсутствие гарантии нахождения глобального оптимума.
• Чувствительность к настройке параметров (размер популяции, вероятности операторов).
• Медленная сходимость в сложных пространствах без модификаций (например, без элитизма и локального уточнения).

Пример простого алгоритма

Рассмотрим задачу максимизации функции f(x) = x² на отрезке [0, 31] с точностью до целых.

1. Кодирование: 5-битная строка (0–31).
2. Популяция: случайно генерируется 4 особи: 01101 (13), 11000 (24), 01000 (8), 10011 (19).
3. Фитнес: f(13) = 169; f(24) = 576; f(8) = 64; f(19) = 361.
4. Селекция: методом рулетки выбираем, например, особи 24 и 19.
5. Скрещивание: одноточечный на позиции 2: 11000 + 10011 → 11011 (27) и 10000 (16).
6. Мутация: с вероятностью 0,01 бит меняется, например, у 27 → 11111 (31).
7. Новая популяция: включаем элиту (24), а затем потомков. Повторяем до сходимости. За 5–10 поколений часто находят 31 (максимум).

Связь с другими методами

Генетические алгоритмы являются частным случаем эволюционных стратегий (Evolution Strategies) и эволюционного программирования, но отличаются акцентом на скрещивание (вместо мутации). Состоят в родстве с роевым интеллектом (муравьиные и пчелиные алгоритмы) и дифференциальной эволюцией, где также используют популяцию и стохастические операторы. В машинном обучении частично вытеснены методами стохастического градиентного спуска для нейросетей, но остаются востребованными для структурной оптимизации.

Критика и ограничения

Критики отмечают, что ГА часто излишне сложны для простых задач, где классические градиентные методы дают точное решение быстрее. В некоторых публикациях указывалось на «генетический шум» — случайный поиск без реального улучшения популяции при неверном выборе параметров. Также существуют проблемы с интерпретацией результатов: нейросеть, выращенная генетическим алгоритмом, может быть «чёрным ящиком». Тем не менее, в практической оптимизации ГА считаются надёжным инструментом, особенно в задачах комбинаторной и многокритериальной оптимизации.

Источники

1. Goldberg, D.E. Genetic Algorithms in Search, Optimization, and Machine Learning. — Addison-Wesley, 1989.
2. Holland, J.H. Adaptation in Natural and Artificial Systems. — University of Michigan Press, 1975.
3. Михайлов, А.Л. Эволюционные алгоритмы: теория и практика. — М.: Наука, 2002.
4. Рутковская, Д., Пилиньский, М., Рутковский, Л. Нейронные сети, генетические алгоритмы и нечеткие системы. — М.: Горячая линия – Телеком, 2006.
5. Deb, K. Multi-Objective Optimization using Evolutionary Algorithms. — Springer, 2001.
6. Корнилов, В.Е. Генетические алгоритмы в задачах автоматизации проектирования — М.: Энергоатомиздат, 1993.