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

Генетический алгоритм (ГА) — это эвристический (поисковый) алгоритм оптимизации и машинного обучения, основанный на принципах естественного отбора и генетики, описанных Чарльзом Дарвином.

Если просто, то это метод “искусственной эволюции” для поиска хороших решений сложных задач, где традиционные методы (например, перебор всех вариантов) не работают из-за огромного количества возможностей.

Ключевая аналогия с биологией:

1. Популяция — это набор возможных решений задачи.
2. Особь (хромосома) — одно конкретное решение, закодированное в виде строки (часто бинарной или числовой).
3. Ген — элемент (бит, число, символ) внутри строки, кодирующий часть решения.
4. Функция приспособленности (fitness function) — главный “естественный отбор”. Это функция, которая оценивает, насколько хорошо конкретное решение. Чем лучше решение, тем выше его “приспособленность” и тем больше у него шансов на “размножение”.

Как работает генетический алгоритм (основной цикл):

1. Инициализация: Создаётся начальная популяция случайных особей (решений).

2. Оценка приспособленности: Для каждой особи вычисляется значение функции приспособленности. Это ответ на вопрос: “Насколько это решение хорошее?”

3. Отбор (селекция): Выбираются наиболее “приспособленные” особи для “размножения”. Чем выше приспособленность, тем выше шанс быть выбранным. Популярные методы: рулетка (вероятность пропорциональна приспособленности) или турнирный отбор (соревнуются несколько случайных особей).

4. Скрещивание (кроссовер): Пары выбранных особей-”родителей” обмениваются частями своих “хромосом”, порождая новых особей-”детей”. Это позволяет комбинировать полезные черты родителей.

   • Пример (одноточечный кроссовер):
     • Родитель 1: 1010 | 1010
     • Родитель 2: 1100 | 1100
     • Ребёнок: 1010 1100 (первая часть от родителя 1, вторая — от родителя 2).

5. Мутация: Случайным образом изменяются некоторые гены в новых хромосомах (например, 0 меняется на 1 или немного меняется число). Это вносит в популяцию новое разнообразие и позволяет исследовать новые области поиска, избегая застревания в локальных оптимумах.

   • Пример: 10101100 → 101**0**1100 (изменён один бит).

6. Формирование новой популяции: Новое поколение, состоящее из детей (и иногда лучших родителей — стратегия элитизма), заменяет старое.

7. Проверка критерия останова: Алгоритм повторяет шаги 2-6, пока не будет выполнен критерий останова. Это может быть:

   • Найдено решение с достаточной приспособленностью.
   • Исчерпано заданное число поколений.
   • Приспособленность популяции перестала улучшаться.

Простой пример: задача коммивояжёра

Задача: Найти самый короткий маршрут, проходящий через все заданные города по одному разу.

• Особь: Последовательность номеров городов (например, [3, 1, 4, 2]).
• Функция приспособленности: Обратная пропорциональность длине маршрута (чем короче маршрут, тем выше приспособленность).
• Кроссовер: Комбинирование частей маршрутов двух родителей.
• Мутация: Случайная перестановка двух городов в маршруте местами.

Алгоритм будет эволюционировать популяцию маршрутов, постепенно “выводя” более короткие пути.

Где применяются генетические алгоритмы?

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

Плюсы и минусы:

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