Участник:AlexeyP

Генетический алгоритм для решения задачи о составлении расписания

Основные авторы описания: А.С.Плотников

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

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

Задача о составлении расписания турнира с N участниками, R турами и K площадками формулируется следующим образом: требуется создать расписание матчей, при котором участники играют с максимальным количеством различных соперников, посещают как можно больше площадок, а на каждой площадке в каждом туре проводится только один матч.

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

1.1.1 Представление решений

Каждое решение представляется матрицей, где строки — это участники, столбцы — туры, а значения элементов — номера площадок. Таким образом, элемент матрицы [math]M_{i,j}[/math] обозначает номер площадки, на которой участник i проводит матч в туре j. Такая матрица дает полное описание расписания для данного решения.

1.1.2 Функция приспособленности (оценка качества расписания)

Цель алгоритма — максимизировать функцию приспособленности для каждого расписания. Приспособленность определяется следующими критериями:

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

1.1.3 Генетические операции

Для оптимизации расписания применяются следующие генетические операции:

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

2. Отбор: выбираются решения с наибольшей функцией приспособленности, так как они более вероятно содержат оптимальные признаки.

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

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

1.2 Математическое описание алгоритма

Исходные данные:

• N — количество участников,
• R — количество туров,
• K — количество площадок.

Целевая функция: максимизация минимального числа уникальных соперников для каждого участника. Если минимальное количество соперников одинаковое, то учитывается минимальное количество посещенных площадок.

Формирование начальной популяции: Случайно создается множество расписаний, каждое из которых соответствует матрице [math]M[/math] размером [math]N\times R[/math], где [math]M_{i,j}\in\{1,...,K\}[/math]

Вычисление приспособленности: Для каждого участника [math]i[/math] подсчитывается количество уникальных соперников и количество уникальных площадок, которые он посещает. Приспособленность решения равна минимальному числу уникальных соперников среди всех участников. Если оно одинаковое для нескольких решений, используется минимальное количество уникальных площадок как дополнительный критерий.

Операции скрещивания: Пусть [math]M_A[/math] и [math]M_B[/math] — две матрицы-родителя. При одноточечном скрещивании выбирается случайный столбец [math]j[/math] и матрица потомка формируется путем объединения столбцов от [math]M_A[/math] и [math]M_B[/math]​ до и после столбца [math]j[/math] соответственно.

Операции мутации: В каждом дне турнира может произойти перемена мест двух номеров площадок [math]M_{i,k} = M_{j,k}[/math]; [math]M_{j,k} = M_{i,k}[/math]

Остановка: Алгоритм завершает работу, когда достигается заданное количество итераций.

1.3 Вычислительное ядро алгоритма

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

Для вычисление приспособленности существ мы проходим по всех существа в популяции и считаем приспособленность каждого из них

1.3.1 Вычисление минимума по числу уникальных оппонентов среди всех игроков

Мы проходим по всем игрокам, для каждого игрока по всем турам, для каждого тура по всем противникам данного игрока и считаем число уникальных. Итого получаем, что сложность - [math]O(T * P^2)[/math], где T - число туров, P - число игроков

1.3.2 Вычисление минимума по числу уникальных площадок среди всех игроков

Мы проходим по всем игрокам, для каждого игрока по всем турам и считаем число уникальных. Итого получаем, что сложность - [math]O(T * P)[/math], где T - число туров, P - число игроков

Итого для получения приспособленности всех существ нам нужно [math]O(S * T * P^2)[/math], где S - размер популяции, T - число туров, P - число игроков

1.4 Макроструктура алгоритма

Алгоритм состоит из алгоритмов:

• Подсчёта приспособленности
• Отбора лучших существ
• Скрещивания существ
• Мутации существ

Эти алгоритмы описаны в описании ядра алгоритма.

1.5 Схема реализации последовательного алгоритма

1. Начальная инициализация популяции

2. Циклически рассчитываем заданное число поколений

2.1 Подсчёт приспособленности существ

2.2 Отбор существ

2.3 Скрещивание существ

2.4. Мутации получившихся существ

1.6 Последовательная сложность алгоритма

1. Начальная инициализация популяции - [math]O(S * T * P)[/math], где [math]S[/math] — размер популяции, [math]T[/math] — число туров, [math]P[/math] — число игроков

2. Циклически рассчитываем заданное число поколений - [math]O(G * S * (T * P^2 + N))[/math], где G - число поколений, S - размер популяции, T - число туров, P - число игроков, где N - число существ участвующих в турнире отбора

2.1 Подсчёт приспособленности существ - [math]O(S * T * P^2)[/math], где S - размер популяции, T - число туров, P - число игроков

2.2 Отбор существ - [math]O(S * N)[/math], где S - размер популяции, N - число существ участвующих в турнире отбора

2.3 Скрещивание существ - [math]O(S * T * P)[/math], где S - размер популяции, T - число туров, P - число игроков

2.4. Мутации получившихся существ - [math]O(S * T * P)[/math], где S - размер популяции, T - число туров, P - число игроков

1.7 Информационный граф

Опишем информационный граф для начальной инициализации и каждого вычислительного ядра

1.7.1 Инициализации популяции

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

1.7.2 Вычисление приспособленности существ (fitness)

Используя текущую популяцию создаётся таблица приспособленности для каждого вида

1.7.3 Отбор лучших существ (selection)

Существа отбираются в турнир случайным образом из текущей популяции. Используя таблицу приспособленности существа отбираются в следующую популяцию

1.7.4 Скрещивание существ (crossover)

Из текущей популяции отбираются существа, у них обмениваются гены, новые существа заменяют предыдущие в популяции

1.7.5 Мутации существ (mutation)

В каждом существе текущей популяции происходит обмен генов. Новое существо заменяет предыдущее в популяции

1.8 Ресурс параллелизма алгоритма

В алгоритме необходимо последовательное выполнение инициализации и ключевых этапов алгоритма

Опишем ресурс параллелизма для начальной инициализации и каждого вычислительного ядра

1.8.1 Инициализации популяции

• Каждое из существ может инициализироваться независимо от других
• Каждый тур может инициализироваться независимо от других
• Каждый тур необходимо заполнять парами номеров площадок, которые необходимо предварительно сгенерировать

1.8.2 Вычисление приспособленности существ (fitness)

• Приспособленности каждого из существ можно считать независимо от других
• Метрики каждого игрока можно считать независимо от других игроков

Необходимо найти минимальное значение из полученных метрик игроков

1.8.3 Отбор лучших существ (selection)

• Отбирать существ можно независимо

В рамках турнира необходимы последовательные сравнения

После отбора необходимо обновить популяцию с учётом отобранных существ

1.8.4 Скрещивание существ (crossover)

• Можно независимо скрещивать каждую пару существ
• В самом скрещивании можно независимо обмениваться генетической информацией

1.8.5 Мутации существ (mutation)

• Каждое существо может мутировать независимо,
• В каждом туре мутации могут проходить независимо

1.9 Входные и выходные данные алгоритма

1.9.1 Входные данные

Все значения - обычные числа

• Размер популяции (S)
• Максимальное число поколений (G)

• Число существ в турнире отбора (N)
• Вероятность скрещивания существ (C)
• Вероятность мутации гена существа (M)

• Число туров (T)
• Число игроков (P)
• Число площадок (Pg)

1.9.2 Выходные данные

• Популяция существ — трёхмерный массив размерами [math]S * T * P[/math], где [math]S[/math] — размер популяции, [math]T[/math] — число туров, [math]P[/math] — число игроков

• Метрики существ — двумерный массив размерами [math]S * 2[/math], где [math]S[/math] — размер популяции, 2, т.к. приспособленность вычисляется из пары значений минимального числа оппонетов и минимального числа площадок для любого участника турнира
• Лучшее существо в популяции (Лучшая получившаяся таблица турнира) — двумерный массив размерами [math]T * P[/math], где [math]T[/math] — число туров, [math]P[/math] — число игроков

2 Программная реализация алгоритма

2.1 Выводы для классов архитектур

В данном алгоритме можно менять реализации его ключевых этапов (подсчёт приспособленности, отбор, скрещивание, мутации), что позволяет оптимизировать выполнение для конкретных архитектур компьютеров

2.2 Существующие реализации генетического алгоритма для решения задач расписаний

Составление расписания спортивных тренировок с помощью генетических алгоритмов

Использование генетических алгоритмов для генерации конечных автоматов

Генетический алгоритм составления расписания выполнения параллельных заданий в распределённой вычислительной системе