Какой алгоритм машинного обучения позволяет оценить лучшие комбинации групп?

Question

Вот упрощенная версия проблемы:

У вас есть группа из пяти воинов. Каждый воин имеет от 1 до 10 предметов, и каждый может принести 1 из своих предметов в бой. Учитывая информацию о битве (тип местности, время суток и т. Д.), Какое оружие должен выбрать каждый воин для создания самой сильной группы?

Предметы могут быть луком, щитом, мечом, катапультой, аптечкой, лошадью и т. Д. Тип местности может быть горным, равниной, болотом, снегом и т. Д.

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

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

Есть ли лучший алгоритм для высказывания "учитывая все эти возможности, выберите лучшую комбинацию"? Бонусные баллы, если его можно использовать в стеке машинного обучения Amazon.

Answer 1

Это не проблема машинного обучения. Это проблема поиска / оптимизации, и поэтому для нее не существует лучшего алгоритма "машинного обучения". Смотрите: https://en.wikipedia.org/wiki/Mathematical_optimization

Учитывая, что у вас уже есть дешевый способ симуляции битвы с учетом местности и комбинации, проблема, которую вы упоминаете в своем наивном подходе, заключается в том, что тестирование всех комбинаций слишком дорого, просто не делайте этого! Существует множество алгоритмов поиска, которые попытаются сократить ваше пространство поиска (см. https://en.wikipedia.org/wiki/Beam_search). Простая в использовании техника, которая очень хорошо подходит для вашего случая (это один из типичных примеров), - это использование генетических алгоритмов, в которых ваш генотип является составом воинов. Уверен, есть много библиотек для GA, которые вы можете импортировать в AWS.