Совсем недавно закончился Евро-2024 и, если честно, оставил после себя смешанные чувства. Я, конечно, больше по хоккею, однако такое событие, как чемпионат Европы по футболу, не могло остаться совсем за бортом. Скажу сразу, по зрелищности турнир совсем не порадовал. Много разочарований, организационных проблем и других форс-мажоров, да и всё-таки в турнирах такого уровня ждёшь большего накала страстей, больше голов, больше хайлайтов. Но это так, чисто субъективно. По итогам турнира много обсуждали разные технологические новшества, которые с каждым годом всё глубже проникают в игру, хотя их применение тоже носит спорный характер. Однако и спорт (в данном случае футбол) влияет на технологии, и в этой статье я хочу написать об одном из неочевидных влияний. Речь пойдёт об алгоритмах, инспирированных динамикой футбола и стратегическими элементами футбольного матча.

За последние несколько десятилетий различные природные алгоритмы широко использовались для решения большого спектра задач оптимизации. В прикладной математике эти задачи носят фундаментальный характер. Одним из популярных методов оптимизации являются метаэвристики. Эти методы представляют набор рекомендаций или стратегий, которые можно адаптировать для создания алгоритмов эвристической оптимизации. Метаэвристические алгоритмы используют комбинацию общих правил для поиска удовлетворительных или почти оптимальных решений задач оптимизации. Так как классические детерминированные методы не всегда могут обеспечить оптимальное решение или достичь гарантированной границы в течение эффективного периода времени. Однако общим слабым местом метаэвристик является требовательность к вычислительным ресурсам. Точнее к балансу между надёжностью и вычислительной эффективностью.

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

Баланс между локальным и глобальным

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

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

Метаэвристики используются в самых различных областях, например, в интеллектуальном анализе данных, медицинских приложениях, для балансировки нагрузки в облачных вычислениях, идентификация разговорной речи, логистике и многих других. На страницах Хабра можно найти много статей, так или иначе затрагивающих метаэвристики. Очень условно их можно разделить на четыре основные категории: эволюционные, физические, роевые и алгоритмы, основанные на поведении человека (о которых и пойдёт речь). 

Футбольные команды можно рассматривать как саморегулирующиеся системы, практикующие сотрудничество, обмен информацией и конкуренцию. Более того, футбол сочетает в себе жёстко установленные правила с интуитивным и гибким принятием решений. В совокупности эти характеристики делают футбол интересным и богатым источником для конструирования алгоритмов.

Алгоритм Лиги чемпионов (League Championship Algorithm, LCA)

LCA представляет собой стохастический популяционный алгоритм для непрерывной глобальной оптимизации, имитирующий самый престижный клубный турнир Европы, в котором искусственные команды играют в искусственной лиге в течение нескольких недель (итераций). В этом алгоритме индивидуальные решения связаны с командами. Каждое решение интерпретируется как текущий состав команды. По итогам игры двух команд, запланированной по расписанию лиги, оценивается пригодность каждого решения и проводится SWOT-анализ, в результате которого происходит изменение составов. Новые составы формируются жадным алгоритмом и сохраняются только в том случае, если их уровень пригодности не хуже текущего. Для ускорения глобальной конвергенции алгоритма существует дополнительный модуль трансферов игроков в конце сезона.

LCA моделирует искусственное первенство в процессе оптимизации алгоритма на основе некоторых идеализированных правил:

— команда с большей игровой силой (способностью команды побеждать конкурентов) имеет больше шансов на победу в игре,

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

— сумма вероятностей победы обеих команд, участвующих в матче, равна единице,

— в базовой версии LCA результатом игры может быть только победа или поражение (ничья не допускается в качестве исхода игры),

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

На рисунке ниже показана блок-схема LCA, которая иллюстрирует процесс оптимизации базового LCA.

Алгоритм Золотого мяча (Golden Ball Algorithm, GBA)

GBA представляет собой многопопуляционный алгоритм комбинаторной оптимизации. В GBA именно игроки являются решениями. Они распределяются по различным командам, входящим в лигу. Команды соревнуются друг с другом в матчах, результаты которых определяют процесс обмена игроками и тренерами. В начале работы алгоритма создаётся начальная популяция и между подгруппами системы (командами) случайно распределяются решения (игроки). После завершения начального этапа начинается первый сезон. Сезон делится на недели, в течение которых команды тренируются и встречаются друг с другом, соревнуясь в лиге. Когда сезон заканчивается, начинается фаза трансферов, во время которой игроки и тренеры могут меняться командами. Этот процесс повторяется до тех пор, пока не будет выполнен критерий завершения.

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

На рисунке ниже показана блок-схема этого алгоритма.

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

В предлагаемой методике у каждой команды есть свой метод обучения, выраженный некоторой функцией следования (successor function), которая работает с определённой структурой в пространстве решений. Например, для некоторых задач маршрутизации функцией этого типа могут быть хорошо известные 2-opt или 3-opt.

Метод обучения назначается случайным образом в процессе инициализации. Для каждой тренировки эта функция применяется некоторое количество раз (до тех пор, пока не будет достигнут критерий завершения). Разные тренировочные функции влияют на каждую команду по-разному. Из-за чего игроки команд также развиваются уникальным образом, в зависимости от команды, в которой они находятся. Этот факт помогает исследовать и более эффективно использовать пространство решений, что также усиливается тем, что игроки могут переходить из команды в команду.

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

Период трансферов — это процесс, в ходе которого команды обмениваются игроками. Тем самым все команды стараются усилиться за счет приобретения новых игроков. В футбольном мире этот процесс происходит каждый год. Обычно лучшие команды стараются набрать лучших игроков из возможных, в то время как другим командам приходится довольствоваться игроками более низкого качества. В алгоритме трансферы зависят от положения команды в лиге. Команды, находящиеся в верхней половине турнирной таблицы, усиливаются лучшими игроками команд нижней половины. В то время как команды нижней части таблицы довольствуются приобретением менее лучших игроков слабейших команд. Следует учитывать, что чем лучше позиция команды, тем лучшего игрока она получает. То есть лучшая команда получает лучшего игрока из предыдущей по рейтингу команды. Трансферы помогают процессу поиска, поскольку позволяют по-разному обрабатывать решения во время выполнения, избегая попадания игроков в локальные оптимумы и увеличивая возможности поиска метаэвристики. Другими словами, этот процесс изменения составов улучшает исследовательскую способность метода и, в частности, способствует более широкому использованию перспективных областей пространства решений.

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

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

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

Оптимизация футбольной игры с запасными игроками (Soccer game optimization with substitute players, SGO)

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

Метод основан на двигательном поведении футболистов, то есть преобразует базовое поведение игроков в метод оптимизации за счёт упрощения среды и правил. В футбольном матче игрок занимает удобную позицию, чтобы вести мяч и забить гол. Важным является сотрудничество между игроками в команде. Мяч перемещается между игроками, и положение мяча является основным фактором, учитывающим движение игрока. Игрок, который не ведёт мяч, будет стараться занять лучшую позицию, чтобы стать ведущим. Некоторые игроки будут приближаться к мячу, а другие будут двигаться дальше, чтобы исследовать футбольное поле. Помимо положения мяча, на движение игрока также влияют находящиеся рядом игроки, а также его собственный опыт. Команда представляет собой одновременный набор векторных решений. Каждый игрок кодирует набор переменных решения. Качество игрока оценивается с помощью его целевой функции. Игрок с мячом представляет собой лучшее текущее решение, полученное в процессе поиска. Позиция игрока, ведущего мяч, прозрачна для всей системы, поэтому всем игрокам доступна эта информация (текущее лучшее решение). Это похоже на настоящую футбольную игру, где все игроки в своих движениях учитывают положение игрока, ведущего мяч. В ходе игры футболист, ведущий мяч, может как передать мяч другому игроку, так и продолжать удерживать мяч.

Алгоритм соревнований Футбольной лиги (Soccer League Competition, SLCA)

SLCA — это популяционная метаэвристика, которая моделирует конкуренцию между командами внутри лиги за достижение высшей позиции и внутреннюю конкуренцию между игроками за личный рейтинг. В SLCA игроки представляют возможные решения, а сила игрока представляет объективную ценность. Игроки соревнуются за звание лучшего игрока команды (локальный оптимум). Лучшие игроки каждой команды лиги соревнуются за позицию лучшего игрока лиги (глобальный оптимум).

Каждая команда состоит из 11 игроков основы (определяемых основными векторами решений в алгоритме) и нескольких запасных игроков (описываемых зарезервированными векторами решений). Для каждого игрока рассчитывается целевая функция, характеризующая силу соответствующего игрока. В задаче минимизации меньшие значения целевых функций (функции стоимости) иллюстрируют сильных игроков. Общая сила команды определяется как среднее значение силы её игроков, включая как основу, так и запасных. После каждого матча выявляются победитель и проигравший, а некоторые игроки (векторы решений) меняются. Эти изменения, направленные на улучшение производительности игроков и команд, моделируются с помощью операторов имитации, провокации, мутации и замены. Имитация подразумевает, что игроки основы подражают как лучшему игроку своей команды, так и лучшему игроку лиги. Оператор провокации выполняет процесс, при котором запасные игроки команды стремятся к среднему значению результативности основных игроков, чтобы выйти в основу. Оператор мутации выполняет функцию коррекции, при которой основные игроки проигравшей в матче команды пересматривают свою игру, чтобы не допустить неудач в будущих играх. Для выполнения этой операции позиции некоторых игроков случайным образом меняются. Операторы замены и подстановки реализуют процесс поиска лучших решений между основой и запасными игроками.

В целом, описанные операторы имеют в алгоритме следующие эффекты:

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

После каждой игры на игроков действуют описанные операторы (векторы решений), и характеристики команд обновляются в соответствии с новыми решениями. Очевидно, что сильные команды с большей вероятностью добиваются успеха в своих будущих матчах. Этот процесс продолжается до конца сезона, и лучший игрок лиги показывает глобальный оптимум (лучшее решение) задачи оптимизации. После каждого сезона игроки расставляются с учётом их обновленной игровой силы. Перед началом нового сезона лучшие игроки переходят в лучшие команды, средние игроки распределяются в команды со средними показателям, а слабые — в команды из нижней части турнирной таблицы.

Чтобы найти решение задачи, алгоритм SLCA быстро достигает локальных оптимумов и рассматривает лучший из них как глобальное оптимальное решение, используя оператор имитации. Далее локальное оптимальное решение точно аппроксимируется оператором провокации. Во время вышеупомянутых операций операторы мутации и замены проверяют точки перекоса, чтобы предотвратить игнорирование любых других возможных точек локального или глобального оптимума в домене. Сочетание четырёх операторов вместе с процедурами ранжирования команд в лиге делает этот алгоритм отличным оптимизатором среди многих других и обладает очень низкой чувствительностью к размерам проблемы.

Оптимизация футбольной лиги (Soccer League Optimization, SLO)

SLO — популяционный алгоритм, основанный на результатах ведущих европейских футбольных лиг. Инициализация алгоритма начинается с распределения команд в зависимости от их финансового положения: богатые (самые сильные), обычные и бедные (самые слабые). Процесс оптимизации основан на имитации конкуренции между командами трёх уровней за приобретение лучших игроков. Беднейшие команды находят, обучают и продают молодых талантливых игроков обычным командам, если они показывают хорошие результаты. Обычные команды либо покупают игроков у беднейших команд, либо сами находят и тренируют игроков. Игроки с лучшими показателями продаются в сильнейшие команды.

Алгоритм футбольного матча (Football Game Algorithm, FGA)

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

— время работы алгоритма считается общим временем матча, а пространство поиска решений рассматривается как футбольное поле;

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

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

Начальный состав определяет первоначальное расположение игроков на поле. После начала работы алгоритма каждый игрок с течением времени перемещается вокруг своей последней позиции (случайное блуждание) по направлению к мячу. Мяч передаётся между игроками, и игроки, находящиеся в лучшей позиции, имеют больше шансов получить мяч.

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

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

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

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

В этой статье мы кратко рассмотрели несколько алгоритмов, инспирированных самой популярной спортивной игрой в мире, но их количество несколько больше, чем можно было описать в рамках одного материала. Поэтому в следующей статье я расскажу о других «футбольных» алгоритмах и разберём какой-нибудь из них подробнее.

НЛО прилетело и оставило здесь промокод для читателей нашего блога:
-15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS