Генетический алгоритм: природа в действии для оптимизации сложных задач (c примером на java)

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

Статья может быть полезна для новичков, изучающих алгоритмы для общего развития, например, в качестве одно из подходов решения задачи коммивояжера, конечно код реализации данной задачи достаточно массивен и не является оптимальным для собеседования, а так же работы с малыми объемами данных.

Алгоритм основан на модели эволюции Дарвина. Его ключевые компоненты:

• Инициализация: создается начальная популяция случайных решений.

• Оценка: вычисляется фитнес-функция для каждого индивида.

• Селекция: выбираются лучшие решения для создания новой популяции.

• Кроссовер: создаются новые индивиды на основе выбранных родителей.

• Мутация: небольшие случайные изменения в новых индивидах.

• Обновление популяции: новая популяция заменяет старую.

• Повторение: шаги 2–6 повторяются, пока не будут выполнены условия завершения.

Пошаговое применение ГА для задачи коммивояжера

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

2. Фитнес-функция
   Для каждого маршрута вычисляется его длина. Чем меньше длина, тем лучше фитнес.

3. Селекция
   Выбираются лучшие маршруты на основе их фитнеса (например, с помощью рулетки или турнира).

4. Кроссовер
   Два маршрута (родители) комбинируются, чтобы создать новый маршрут (ребенок). Например, часть маршрута берется от первого родителя, а оставшиеся города добавляются из второго.

5. Мутация
   В маршруте меняются местами два города. Это помогает исследовать новые возможные пути.

6. Обновление
   Формируется новая популяция маршрутов.

7. Прекращение
   Если количество поколений достигает заданного предела или найден маршрут с минимальной длиной, алгоритм завершает работу.

На основе одной из самых популярных задач — задача «Коммивояжера» разберем применение данного алгоритма для нахождения расстояния между городами.

Допустим у нас есть 4 города (A, B, C, D), представим расстояние между ними в виде матрицы расстояний:

Вот схематичное пошаговое описание работы генетического алгоритма на примере задачи с четырьмя городами (A, B, C, D). Используем символы, чтобы изобразить этапы.

1. Инициализация

Случайным образом создаются несколько маршрутов:

2. Фитнес-функция

Для каждого маршрута рассчитывается суммарное расстояние. Чем меньше значение, тем лучше фитнес:

3. Селекция

Выбираются лучшие маршруты. Например, используем турнирный метод:

4. Кроссовер

Комбинируются два маршрута (родители) для создания нового:

Шаги для создания ребёнка

1. Выбор участка для копирования: Случайным образом выбирается участок из первого родителя, который будет передан ребёнку. Например, из ABCDA выбирается подстрока BCD (с индексами 1–3).

   Родитель 1: A | BCD | A
   Родитель 2: B | CAD | B

2. Копирование участка в ребёнка: Этот участок сразу помещается на те же позиции в ребёнке.

   Ребёнок (на этом этапе): _ | BCD | _

3. Заполнение оставшихся позиций: Города из второго родителя добавляются в порядке их следования, начиная с первого города после выбранного участка, с пропуском уже добавленных городов.

   • Из второго родителя: B, C, A, D, B.

   • Пропускаем B, C, и D (они уже в ребёнке).

   • Добавим оставшиеся: A (первая пустая позиция слева), затем А (на последнюю позицию-так как мы спланировали всегда возврат в начальный маршрут).

   Ребёнок после заполнения: A | BCD | A

5. Мутация

В маршруте случайно меняются местами два города:

6. Обновление популяции

Формируется новая популяция, включающая детей и лучших родителей. Например:

7. Прекращение

Процесс продолжается, пока не будет найден оптимальный маршрут или достигнуто заданное количество поколений. Например, после 10 поколений алгоритм выдает результат:

Другие подходы к решению задачи коммивояжера:

1. Точные алгоритмы (для малых задач, n<=20):

   • Перебор всех маршрутов (факториальный подход): Наивный способ. Для n городов сложность O(n!), что не подходит для больших задач.

   • Динамическое программирование (алгоритм Беллмана–Хелда–Карпа): Позволяет уменьшить сложность до O(2^n *n^2). Всё ещё сложно для больших n.

2. Эвристические алгоритмы (для средних и больших задач, 20<n<=50):

   • Ближайший сосед (Nearest Neighbor): Выбирается ближайший город на каждом шаге. Быстро, но не гарантирует оптимальность.

   • Жадный алгоритм: Пытается построить решение, добавляя короткие рёбра, избегая циклов, пока маршрут не будет завершён.

3. Метаэвристики (для больших задач, близко к оптимальному решению, 50<n):

   • Генетические алгоритмы: Имитация эволюции для поиска оптимального маршрута.

   • Муравьиные алгоритмы: Моделируют поведение муравьёв, находящих оптимальные пути.

   • Алгоритмы на основе имитации отжига: Постепенное улучшение решений, допуская временное ухудшение для выхода из локального минимума.

import java.util.*;  public class GeneticAlgorithmTSP {      // Константы для настройки алгоритма     private static final int NUM_CITIES = 4; // Число городов     private static final int POPULATION_SIZE = 100; // Размер популяции     private static final int GENERATIONS = 500; // Количество поколений     private static final double MUTATION_RATE = 0.1; // Вероятность мутации      // Матрица расстояний между городами     private static final int[][] DISTANCES = {             {0, 10, 15, 25},             {10, 0, 20, 35},             {15, 20, 0, 30},             {25, 35, 30, 0}     };      public static void main(String[] args) {         // Инициализация начальной популяции         List<List<Integer>> population = initializePopulation();         for (int generation = 0; generation < GENERATIONS; generation++) {             // Создание нового поколения             List<List<Integer>> newPopulation = new ArrayList<>();             while (newPopulation.size() < POPULATION_SIZE) {                 // Выбор родителей                 List<Integer> parent1 = selectParent(population);                 List<Integer> parent2 = selectParent(population);                 // Скрещивание родителей                 List<Integer> child = crossover(parent1, parent2);                 // Применение мутации                 if (Math.random() < MUTATION_RATE) {                     mutate(child);                 }                 newPopulation.add(child);             }             // Замена старой популяции новой             population = newPopulation;             // Выбор лучшего маршрута             List<Integer> bestRoute = getBestRoute(population);             int bestDistance = calculateDistance(bestRoute);             System.out.println("Поколение " + generation + ": Лучший маршрут = " + bestRoute + ", Расстояние = " + bestDistance);         }     }      // Инициализация начальной популяции случайными маршрутами     private static List<List<Integer>> initializePopulation() {         List<List<Integer>> population = new ArrayList<>();         for (int i = 0; i < POPULATION_SIZE; i++) {             List<Integer> route = new ArrayList<>();             for (int j = 0; j < NUM_CITIES; j++) {                 route.add(j);             }             Collections.shuffle(route); // Перемешивание городов             population.add(route);         }         return population;     }      // Выбор родителя из популяции     private static List<Integer> selectParent(List<List<Integer>> population) {         Random rand = new Random();         return population.get(rand.nextInt(POPULATION_SIZE));     }      // Скрещивание двух родителей для создания потомка     private static List<Integer> crossover(List<Integer> parent1, List<Integer> parent2) {         List<Integer> child = new ArrayList<>(Collections.nCopies(parent1.size(), -1));         Random rand = new Random();         int start = rand.nextInt(parent1.size());         int end = rand.nextInt(parent1.size());         if (start > end) {             int temp = start;             start = end;             end = temp;         }          // Копирование части маршрута из первого родителя         for (int i = start; i <= end; i++) {             child.set(i, parent1.get(i));         }          // Заполнение оставшихся городов из второго родителя         int childIndex = 0;         for (int i = 0; i < parent2.size(); i++) {             int currentCity = parent2.get(i);             if (!child.contains(currentCity)) {                 while (child.get(childIndex) != -1) {                     childIndex++;                 }                 child.set(childIndex, currentCity);             }         }         return child;     }      // Мутация маршрута     private static void mutate(List<Integer> route) {         Random rand = new Random();         int index1 = rand.nextInt(route.size());         int index2 = rand.nextInt(route.size());         Collections.swap(route, index1, index2);     }      // Поиск лучшего маршрута в популяции     private static List<Integer> getBestRoute(List<List<Integer>> population) {         List<Integer> bestRoute = population.get(0);         int bestDistance = calculateDistance(bestRoute);         for (List<Integer> route : population) {             int distance = calculateDistance(route);             if (distance < bestDistance) {                 bestRoute = route;                 bestDistance = distance;             }         }         return bestRoute;     }      // Расчет расстояния для маршрута     private static int calculateDistance(List<Integer> route) {         int distance = 0;         for (int i = 0; i < route.size() - 1; i++) {             distance += DISTANCES[route.get(i)][route.get(i + 1)];         }         distance += DISTANCES[route.get(route.size() - 1)][route.get(0)]; // Возврат в начальный город         return distance;     } }

Значения переменных:

    private static final int NUM_CITIES = 4; // Число городов     private static final int POPULATION_SIZE = 100; // Размер популяции     private static final int GENERATIONS = 500; // Количество поколений     private static final double MUTATION_RATE = 0.1; // Вероятность мутации

в генетическом алгоритме выбираются с учетом характера задачи, требований к производительности, размера данных и экспериментов.

1. Число городов (NUM_CITIES)

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

• Например, если матрица расстояний задана для 4 городов, то NUM_CITIES = 4.

• В реальных задачах число городов может быть большим (десятки, сотни), что увеличивает сложность задачи и время вычислений.

2. Размер популяции (POPULATION_SIZE)

• Определяет, сколько решений (маршрутов) рассматривается в каждом поколении.

• Чем больше популяция, тем выше вероятность найти хорошее решение за счет большего разнообразия, но возрастает вычислительная сложность.

• Обычно выбирают значение в диапазоне 50–500. Для малых задач достаточно 100.

Рекомендации:

• Для небольших задач: 50–100.

• Для больших задач: 200–500.

3. Количество поколений (GENERATIONS)

• Число итераций алгоритма для улучшения решений.

• Выбор зависит от требуемого качества решения и допустимого времени работы алгоритма.

• Обычно выбирается 100–1000 поколений. Для задач с малым числом городов (до 10), 500 поколений обычно достаточно.

Рекомендации:

• Наблюдайте за изменением лучшего маршрута. Если улучшения прекращаются задолго до достижения лимита поколений, можно уменьшить значение.

4. Вероятность мутации (MUTATION_RATE)

• Определяет вероятность случайной перестановки городов в маршруте.

• Мутация предотвращает преждевременную стагнацию в локальном минимуме.

• Обычно выбирают в диапазоне 0.01–0.2.

Рекомендации:

• Для задач с малым количеством городов подходит 0.1 (10%).

• Для больших задач можно увеличить вероятность мутации до 0.2, чтобы усилить разнообразие.

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