Футбольные алгоритмы глобальной оптимизации (часть 2)

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

Алгоритм футбольной оптимизации (Football Optimization Algorithm, FOA)

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

v — скорость игроков, d — расстояние между лучшим игроком и другими игроками, а y — параметр, регулирующий отклонение от исходного направления. Влияние зрителей моделируется случайным изменением параметров игроков.

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

Оптимизация чемпионата мира (World Cup Optimization, WCO)

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

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

где f — функция приспособленности, g — коммутирует значение функции приспособленности в неотрицательное число, а F — относительная пригодность решений. Это необходимо в тех случаях, когда функция приспособленности должна быть минимизирована, поскольку более низкие значения функции соответствуют лучшим решениям.

Алгоритм самого ценного игрока (Most Valuable Player Algorithm, MVPA)

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

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

Алгоритм концептуально очень прост, эффективен, быстр, надёжен и лёгок в реализации. Однако на текущий момент разработка MVPA находится в зачаточном состоянии, предполагающем дальнейшие исследования и улучшения для его применения к самым различным проблемам. Более того, в некоторых предварительных вычислительных исследованиях обнаружено, что оптимизация на основе обучения (Teaching-Learning-based Optimization, TLBO) немного лучше на более высоких размерностях. Этот момент является одной из проблем будущих версий MVPA.

Алгоритм Тики-Така (Tiki-Taka Algorithm, ТТА)

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

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

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

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

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

Второй шаблон алгоритмов (FGA, FOA, SGO, TTA) концептуализирует пространство поиска как само футбольное поле. Процесс поиска в этих алгоритмах является корректировкой «игроками» своих позиций в соответствии с конкретными операторами до тех пор, пока они в конечном итоге не сойдутся к наиболее выгодным. Эти алгоритмы во многом схожи с роевыми.

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

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

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

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

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

Самые возрастные алгоритмы LCA и GBA имеют возможности глобального и локального поиска, которые уравновешивают исследование и эксплуатацию. Они кажутся частично более эффективными в унимодальных и многомодальных функциях или задачах. Более современные WCO, SLO и FOA требуют дополнительных исследований в области повышения производительности с точки зрения надёжности, сходимости и точности. SLO и FOA описаны крайне скудно и экспериментальных исследований совершенно недостаточно, чтобы сделать однозначный вывод об общей оценке их производительности. Кроме того, после обзора спортивных алгоритмов можно увидеть, что некоторые из них являются просто похожими версиями существующих подходов с другим названием и метафорой, на которой они базируются. Некоторые алгоритмы схожи в терминах и параметрах. Например, FOA напоминает FGA, хотя у них похоже используются разные подходы к исследованию и эксплуатации. В общем и целом, работы по изучению и доработке этих спортивных алгоритмов очень много, так что когда-нибудь я ещё вернусь к этой теме и обязательно напишу об этом.

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