Алгоритм MAP-Elites: поиск оптимальности через разнообразие
MAP-Elites - это метод обучения с подкреплением, позволяющий избежать локального оптимума пространства поиска путем хранения нескольких возможных решений, элит, с различными характеристиками. Для каждой характеристики сохраняется наиболее эффективное решение с этой характеристикой. Этот метод оказался успешным при перемещении роботов, цель которого состоит в том, чтобы робот переместился как можно дальше от исходного местоположения. В этой области одной характеристикой может быть то, что робот имеет определенный рост, другой характеристикой может быть то, что робот имеет определенный вес. Таким образом, для каждой партии возможных решений сохраняется наиболее эффективный робот определенной высоты и наиболее эффективный робот определенного веса. Эти элиты могут быть заменены на любой итерации другим роботом, который соответствует определенным критериям и выполняет их. Этот процесс повторяется до тех пор, пока не будет найдено подходящее решение или набор решений. Таким образом поддерживается разнообразный набор возможных решений, и попадание в локальный оптимум менее вероятно. Кроме того, исследователи обнаружили, что поддержание разнообразного набора решений таким образом может облегчить открытие, которое без них было бы невероятным. Они обнаружили, что часто решения не всегда привязаны к одной категории. Таким образом, MAP-Elites подходит не только для задач, требующих не только разнообразного набора решений, но и для тех, для которых требуется одно лучшее решение. Часто лучшие решения попадают в разные категории, возможно, никогда не являясь абсолютным лучшим исполнителем, но будучи достаточно разнообразными и достаточно хорошими, чтобы оставаться среди элитных решений. В определенный момент разнообразие и производительность этого решения могут окупиться, поскольку оно обнаруживает функцию, которая была бы недоступна для решения в не разнообразном наборе решений. Это открытие может привести к тому, что это решение станет лучшим решением. Псевдокод и полное описание этого алгоритма можно найти здесь: https://arxiv.org/pdf/1504.04909.pdf.
