Участник: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 Вычисление приспособленности существ (fitness)

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

Вычисление приспособленности существа состоит из 2 этапов:

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

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

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

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

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

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

Существуют несколько вариантов отбора существ

Например рассмотрим Турнирный отбор (Tournament selection)

Для турнирного отбора мы проходимся по всей популяции, берём случайные N существ и среди них выбираем наиболее приспособленного, который перейдёт в следующую популяцию. Итого нам нужно [math]O(S * N)[/math], S - размер популяции, где N - число существ турнира

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

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

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

Мы проходим по всей популяции, и для каждого существа в каждом туре меняем оппонентов. Итого получаем [math]O(S * T * P)[/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 Входные данные

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

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

• Число туров
• Число игроков
• Число площадок

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

• Популяции существ
• Метрики существ
• Лучшая получившаяся таблица турнира

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

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

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

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

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

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