Участник:AlexeyP
Основные авторы описания: А.С.Плотников
Содержание
1 Свойства и структура алгоритма
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]\{1,...,K\}[/math] при условии, что на одной площадке в один тур не играют два матча. Остановка:
Алгоритм завершает работу, когда достигается заданное количество итераций или функция приспособленности не меняется в течение нескольких поколений.
