Воссоздание команды мечты с помощью генетического алгоритма

Авторы — Pratik P S, Николас Браун (AI Skunks)

Постановка задачи

Соединенные Штаты являются домом для ведущей в мире мужской профессиональной баскетбольной лиги — Национальной баскетбольной ассоциации (НБА), одной из крупнейших профессиональных спортивных лиг Северной Америки. Одной из таких популярных команд является «Лос-Анджелес Лейкерс». «Лейкерс» планируют создать команду, которая превзойдет «команду 1971–72», купив некоторых из лучших игроков лиги в этом сезоне, чтобы выиграть чемпионат. Они хотят сделать это, получая игроков, которых они рассматривают, на основе рейтинга игрока и бюджета. Команда аналитиков «Лейкерс» пытается найти способ получить наилучшее сочетание соотношения игроков и бюджета, чтобы заключать сделки «подписать и обменивать», чтобы максимизировать общий рейтинг выбора при текущем бюджете в 105 тысяч.

Мы будем использовать генетический алгоритм для решения этой проблемы.

Что, если я скажу вам, что вы можете смоделировать эволюцию?

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

Что такое генетический алгоритм?

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

Есть 4 шага до ГА

Посвящение
Выбор фитнеса
кроссовер
Мутация

Эта блок-схема описывает шаги алгоритма:

Алгоритм

«x» — это доля населения, которая будет заменена кроссовером на каждой итерации. «n» — количество выборок в популяции, а «e» — количество эволюций.

Реализация

Основные используемые функции:

1. Генератор команд: генерирует команды случайным образом из заданного варианта игроков.

2. Генератор комбинаций команд. Создает список команд определенного размера, в данном случае количество команд, созданных для каждой группы населения, равно 10.

3.Фитнес-функция: вычисляется функция проверки общей цены и стоимости команды, и команда отбрасывается, если значение превышает предельный вес, т.е. 105

4. Функция пересечения: перекрестие объединяет пару родительских команд для создания пары потомков на основе точки пересечения.

5.Функция мутации: инвертирует один бит из 1->0 или 0->1 в зависимости от значения вероятности.

Примечание. Игроки в списке команд представлены цифрами 1 и 0. Включение конкретного игрока обозначается 1 и 0 в противном случае.

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

Полученные результаты

Получившаяся команда состоит из Стефа Карри, Кевина Дюранта, Энтони Дэвиса и Зака ЛаВина с общим рейтингом выбора 29.

Затрачено время

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

ссылка на код- https://github.com/Pratik-Prakash-Sannakki/NBA_LakersDramTeam_SuperPicks

Заключение

Алгоритм не детерминирован, он не дает один и тот же результат каждый раз, когда мы запускаем алгоритм. Но с большим количеством сгенерированных решений на поколение мы в конечном итоге достигнем результата, который будет «достаточно близким», если не «лучшим решением».

Более широкий выбор

С большими значениями для выбора грубая сила занимает непомерно много времени, и GA будет оставаться эффективным с низкой временной сложностью, как цитируют — Svogor, Ivan & Crnkovic, Ivica & Vrcek, Neven. (2013). Многокритериальное размещение программных компонентов на гетерогенной платформе. Материалы Международной конференции по интерфейсам информационных технологий, ITI. 341–346. 10.2498/iti.2013.0558.- https://www.researchgate.net/publication/261306247_Multi-criteria_software_component_allocation_on_a_heterogeneous_platform

Локальная максимальная проблема

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