Как мне классифицировать проблему оптимизации ввода в моем эмуляторе и с каким алгоритмом мне к ней подойти?

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

Какие существуют методы поиска локальных оптимумов в чрезвычайно больших комбинаторных пространствах поиска?

Фон

В сообществе суперпользователей с помощью инструментов мы стремимся предоставить специально созданный (не сгенерированный в реальном времени) ввод для игровой консоли или эмулятора, чтобы минимизировать некоторые затраты (обычно время до завершения). В настоящее время это делается путем покадрового воспроизведения игры и указания входных данных для каждого кадра, часто многократно повторяя фрагменты прогона (например, недавно опубликованный прогон «Легенда о Зельде: окарина времени» имеет в общей сложности 198 590 попыток).

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

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

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

Теперь моя цель - попытаться автоматизировать процесс обхода в целом для системы Nintendo 64 . Пространство поиска для этой проблемы пока слишком велико , чтобы атаковать с перебором подходом. Сегмент n-кадра серии N64 имеет 2 ³⁰ⁿ возможных входов, что означает, что всего 30 кадров ввода (секунда при 30FPS) имеет 2 ⁹⁰⁰ возможных входов; было бы невозможно проверить эти потенциальные решения, не говоря уже о тех, которые рассчитаны на два часа работы.

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

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

Текущее состояние

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

Обратите внимание, что самой медленной частью этой программы будет, безусловно, оценка входного потока . Это потому, что это связано с эмуляцией игры для n кадров. (Если бы у меня было время, я бы написал свой собственный эмулятор, который предоставлял хуки для такого рода вещей, но сейчас я остаюсь синтезировать сообщения и изменять память для существующего эмулятора из другого процесса.) На моем главном компьютере, который является довольно современным, оценка 200 кадров занимает примерно 14 секунд. Поэтому я бы предпочел алгоритм (с учетом выбора), который минимизирует количество оценок функций.

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

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

После добавления параллелизма я включил мутацию нажатий кнопки «А» и выполнил ту же функцию оценки в области, которая требовала прыжков. С 24 запущенными эмуляторами потребовалось приблизительно 1 час, чтобы достичь цели из изначально пустого потока ввода, но, вероятно, потребуется несколько дней, чтобы достичь чего-то близкого к оптимальному.

проблема

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

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

Вопрос

Итак, мой вопрос: как мне это смоделировать? Какую проблему оптимизации я пытаюсь решить? Какой алгоритм я должен использовать? Я не боюсь читать научные статьи, поэтому дайте мне знать, что я должен читать!

Интуитивно понятно, что генетический алгоритм не может быть лучшим, потому что он, похоже, не учит. Например, если нажатие кнопки «Пуск», кажется, всегда ухудшает оценку (потому что это приостанавливает игру), должен быть какой-то дизайнер или мозг, который учится: «нажимать« Старт »в любой момент бесполезно». Но даже эта цель не так тривиальна, как кажется, потому что иногда нажимающий старт является оптимальным, например, в так называемых «паузах назад-длинные прыжки» в Super Mario 64 ! Здесь мозг должен был бы выучить гораздо более сложный паттерн: «нажимать« Старт »бесполезно, за исключением случаев, когда игрок находится в этом очень специфическом состоянии и продолжит некоторое сочетание нажатий кнопок ».

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

В настоящее время я читаю о (Реактивном) Поиске Табу, Очень широкомасштабном Поиске Соседства, Оптимизации на основе преподавания и обучения и Оптимизации колоний муравьев.

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

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

• пространство объекта,
• целевая функция и
• параметры вашего генетического алгоритма,

так позвольте мне уточнить.

Каковы ваши объекты?

Вы уже ответили: вы смотрите на последовательность действий, каждое из которых занимает один кадр. Я думаю, что это может быть слишком мелкозернистым; возможно попробуйте последовательность действий, каждое с продолжительностью (в количестве кадров). Это позволило бы иметь такие мутации, как «ходить немного дольше», чтобы иметь разные вероятности, чем «вставить нажатие А» естественным образом. Попробуйте, что работает лучше всего; Возможно, вам придется вернуться к этому пункту, подумав о других ингредиентах.

Какова ваша целевая функция?

Это действительно важно. Что вы хотите оптимизировать? Время к цели? Количество разных действий? Количество собранных звезд? Сочетание нескольких факторов? Как только вы получаете несколько целей, все становится волосатым - там (обычно) больше нет оптимы!

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

^{[ источник ]}

$0$$0$

$\qquad \displaystyle \frac{1}{1 + \text{final distance to goal}} + \frac{1}{1 + \text{time to goal}}$

$0$$1$$1$

Так как вы измеряете расстояние? Линейное расстояние может выглядеть заманчиво, но имеет свои проблемы; опять же, могут быть отправлены неправильные сигналы. Рассмотрим этот простой сценарий:

^{[ источник ]}

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

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

Как работает ваша GA?

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

Население

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

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

выбор

$k$

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

Размножение и мутация

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

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

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

прекращение

$N$$k$$1$$n$

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

Примечание: посмотрите на BoxCar 2D в свете вышесказанного. Они делают некоторые вещи довольно хорошо (другие, не так), и вы можете понять, как параметры GA могут влиять на его производительность.

1. На самом деле, построение последовательности, жадно использующей это приспособление, то есть выбор действия, минимизирующего расстояние до цели из всех возможных следующих действий, может работать довольно хорошо. Попробуйте это перед использованием GA!
2. Конечно, вы, как наблюдатель, всегда помните лучшее решение, которое когда-либо встречалось.

Для получения более подробной информации о методе обучения на основе обучения (TLBO) и его коде, обратитесь к следующей статье:

Элитарный алгоритм оптимизации, основанный на обучении и обучении, для решения сложных задач оптимизации с ограничениями Р. Венката Рао и В. Патель; Международный журнал промышленных инженерных вычислений 3 (4): 535–560 (2012)

Для дополнительного чтения:

• Алгоритм оптимизации, основанный на обучении и обучении, для задач оптимизации реальных параметров без ограничений Р. Венката Рао, В. Дж. Савсани и Дж. Балик; Инженерная оптимизация (2012)
• Оптимизация механического проектирования с использованием передовых методов оптимизации Р. Венката Рао, JV Savsani; Springer-Verlag London (2012); ISBN 978-1-4471-2747-5
• Многоцелевая оптимизация теплообменников с использованием модифицированного алгоритма оптимизации, основанного на обучении и обучении , Р. Венката Рао и В. Патель; Прикладное математическое моделирование (2012)
• Многоцелевая оптимизация двухступенчатых термоэлектрических охладителей с использованием модифицированного алгоритма оптимизации, основанного на обучении и обучении , Р. Венката Рао и В. Пателя; Инженерные приложения искусственного интеллекта (2012)