Генетические алгоритмы (ГА) — это мощный инструмент для решения задач оптимизации, вдохновленный процессами эволюции в природе. Подобные алгоритмы применяются в таких областях, как маршрутизация, машинное обучение, финансовая аналитика, проектирование и многие другие. В этой статье я разберу принцип работы ГА и приведу пример решения, одной из самых популярных задач в алгоритмах на языке Java.
Статья может быть полезна для новичков, изучающих алгоритмы для общего развития, например, в качестве одно из подходов решения задачи коммивояжера, конечно код реализации данной задачи достаточно массивен и не является оптимальным для собеседования, а также работы с малыми объемами данных.
Алгоритм основан на модели эволюции Дарвина. Его ключевые компоненты:
Инициализация: создается начальная популяция случайных решений.
Оценка: вычисляется фитнес-функция для каждого индивида.
Селекция: выбираются лучшие решения для создания новой популяции.
Кроссовер: создаются новые индивиды на основе выбранных родителей.
Мутация: небольшие случайные изменения в новых индивидах.
Обновление популяции: новая популяция заменяет старую.
Повторение: шаги 2–6 повторяются, пока не будут выполнены условия завершения.
Пошаговое применение ГА для задачи коммивояжера
Инициализация
Случайным образом создается набор маршрутов (хромосом). Каждая хромосома — это список городов, представляющий возможный путь.Фитнес-функция
Для каждого маршрута вычисляется его длина. Чем меньше длина, тем лучше фитнес.Селекция
Выбираются лучшие маршруты на основе их фитнеса (например, с помощью рулетки или турнира).Кроссовер
Два маршрута (родители) комбинируются, чтобы создать новый маршрут (ребенок). Например, часть маршрута берется от первого родителя, а оставшиеся города добавляются из второго.Мутация
В маршруте меняются местами два города. Это помогает исследовать новые возможные пути.Обновление
Формируется новая популяция маршрутов.Прекращение
Если количество поколений достигает заданного предела или найден маршрут с минимальной длиной, алгоритм завершает работу.
На основе одной из самых популярных задач — задача «Коммивояжера» разберем применение данного алгоритма для нахождения расстояния между городами.
Допустим у нас есть 4 города (A, B, C, D), представим расстояние между ними в виде матрицы расстояний:
A | B | C | D | |
|---|---|---|---|---|
A | 0 | 10 | 15 | 25 |
B | 10 | 0 | 20 | 35 |
C | 15 | 20 | 0 | 30 |
D | 25 | 35 | 30 | 0 |
Вот схематичное пошаговое описание работы генетического алгоритма на примере задачи с четырьмя городами (A, B, C, D). Используем символы, чтобы изобразить этапы.
1. Инициализация
Случайным образом создаются несколько маршрутов:
2. Фитнес-функция
Для каждого маршрута рассчитывается суммарное расстояние. Чем меньше значение, тем лучше фитнес:
3. Селекция
Выбираются лучшие маршруты. Например, используем турнирный метод:
4. Кроссовер
Комбинируются два маршрута (родители) для создания нового:
Шаги для создания ребёнка
Выбор участка для копирования: Случайным образом выбирается участок из первого родителя, который будет передан ребёнку. Например, из ABCDA выбирается подстрока BCD (с индексами 1–3).
Родитель 1: A | BCD | A
Родитель 2: B | CAD | BКопирование участка в ребёнка: Этот участок сразу помещается на те же позиции в ребёнке.
Ребёнок (на этом этапе): _ | BCD | _
Заполнение оставшихся позиций: Города из второго родителя добавляются в порядке их следования, начиная с первого города после выбранного участка, с пропуском уже добавленных городов.
Из второго родителя: B, C, A, D, B.
Пропускаем B, C, и D (они уже в ребёнке).
Добавим оставшиеся: A (первая пустая позиция слева), затем А (на последнюю позицию-так как мы спланировали всегда возврат в начальный город).
Ребёнок после заполнения: A | BCD | A
5. Мутация
В маршруте случайно меняются местами два города:
6. Обновление популяции
Формируется новая популяция, включающая детей и лучших родителей. Например:
7. Прекращение
Процесс продолжается, пока не будет найден оптимальный маршрут или достигнуто заданное количество поколений. Например, после 10 поколений алгоритм выдает результат:
( Итого: 10 + 20 + 30 + 25 = 85 )
Другие подходы к решению задачи коммивояжера:
Точные алгоритмы (для малых задач, n<=20):
Перебор всех маршрутов (факториальный подход): Наивный способ. Для n городов сложность O(n!), что не подходит для больших задач.
Динамическое программирование (алгоритм Беллмана–Хелда–Карпа): Позволяет уменьшить сложность до O(2^n *n^2). Всё ещё сложно для больших n.
Эвристические алгоритмы (для средних и больших задач, 20<n<=50):
Ближайший сосед (Nearest Neighbor): Выбирается ближайший город на каждом шаге. Быстро, но не гарантирует оптимальность.
Жадный алгоритм: Пытается построить решение, добавляя короткие рёбра, избегая циклов, пока маршрут не будет завершён.
Метаэвристики (для больших задач, близко к оптимальному решению, 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, чтобы усилить разнообразие.
Применяя подходы из эволюционной биологии — отбор, кроссовер и мутации — мы можем находить решения, которые классическими методами требуют огромных вычислительных ресурсов. Хотя результат может быть не всегда идеальным, подход с генетическими алгоритмами часто оказывается достаточно эффективным для практического применения.