¿Cómo clasifico mi problema de optimización de entrada del emulador y con qué algoritmo debería abordarlo?

Debido a la naturaleza de la pregunta, tengo que incluir mucha información de fondo (porque mi pregunta es: ¿cómo puedo reducir esto?) Dicho esto, se puede resumir (según mi leal saber y entender) como:

¿Qué métodos existen para encontrar óptimos locales en espacios de búsqueda combinatoria extremadamente grandes?

Antecedentes

En la comunidad de superjuego asistido por herramientas, buscamos proporcionar una entrada especialmente diseñada (no generada en tiempo real) a una consola o emulador de videojuegos para minimizar algunos costos (generalmente el tiempo de finalización). La forma en que esto se hace actualmente es jugando el juego cuadro por cuadro y especificando la entrada para cada cuadro, a menudo rehaciendo partes de la carrera muchas veces (por ejemplo, la carrera recientemente publicada para The Legend of Zelda: Ocarina of Time ha un total de 198,590 reintentos).

Hacer que estas carreras obtengan su objetivo generalmente se reduce a dos factores principales: planificación de rutas y recorrido. El primero es mucho más "creativo" que el segundo.

La planificación de rutas determina la forma en que el jugador debe navegar en general para completar el juego, y es a menudo la parte más importante de la carrera. Esto es análogo a elegir qué método de clasificación usar, por ejemplo. La mejor clasificación de burbujas en el mundo simplemente no va a superar a una clasificación rápida en 1 millón de elementos.

Sin embargo, en el deseo de perfección, el recorrido (cómo se realiza la ruta) también es un factor importante. Continuando con la analogía, así es como se implementa el algoritmo de clasificación. Algunas rutas ni siquiera pueden realizarse sin marcos de entrada muy específicos. Este es el proceso más tedioso de asistencia de herramientas y es lo que hace que la producción de una ejecución completa lleve meses o incluso años. No es un proceso difícil (para un humano) porque se trata de probar diferentes variaciones de la misma idea hasta que se considere mejor, pero los humanos solo pueden probar tantas variaciones en su capacidad de atención. La aplicación de máquinas a esta tarea parece adecuada aquí.

Mi objetivo ahora es intentar automatizar el proceso transversal en general para la consola Nintendo 64 . El espacio de búsqueda para este problema es ahora demasiado grande para atacar con un enfoque de fuerza bruta. Un segmento de n cuadros de una ejecución N64 tiene 2 ³⁰ⁿ entradas posibles, lo que significa que solo 30 cuadros de entrada (un segundo a 30FPS) tiene 2 ⁹⁰⁰ entradas posibles; Sería imposible probar estas posibles soluciones, y mucho menos aquellas para una carrera completa de dos horas.

Sin embargo, no estoy interesado en intentar (o más bien, ni siquiera intentaré) la optimización global total de una ejecución completa. Más bien, me gustaría, dada una entrada inicial, aproximar el óptimo local para un segmento particular de una ejecución (o los n óptimos locales más cercanos, para una especie de optimización semi-global) . Es decir, dada una ruta y un recorrido inicial de esa ruta: busque en los vecinos de ese recorrido para minimizar el costo, pero no degenere en probar todos los casos que podrían resolver el problema.

Por lo tanto, mi programa debe tomar un estado inicial, una secuencia de entrada, una función de evaluación y generar el óptimo local al minimizar el resultado de la evaluación.

Estado actual

Actualmente tengo todo el marco cuidado. Esto incluye evaluar un flujo de entrada a través de la manipulación del emulador, instalación y desmontaje, configuración, etc. Y como marcador de posición, el optimizador es un algoritmo genético muy básico. Simplemente evalúa una población de flujos de entrada, almacena / reemplaza al ganador y genera una nueva población al mutar el flujo ganador. Este proceso continúa hasta que se cumplan algunos criterios arbitrarios, como el tiempo o el número de generación.

Tenga en cuenta que la parte más lenta de este programa será, con mucho, la evaluación de una secuencia de entrada . Esto se debe a que esto implica emular el juego para n cuadros. (Si tuviera tiempo, escribiría mi propio emulador que proporcionara ganchos en este tipo de cosas, pero por ahora me queda sintetizar mensajes y modificar la memoria para un emulador existente de otro proceso). En mi computadora principal, que es bastante moderno, evaluar 200 cuadros lleva aproximadamente 14 segundos. Como tal, preferiría un algoritmo (dada la opción) que minimiza el número de evaluaciones de funciones.

Creé un sistema en el marco que administra los emuladores al mismo tiempo. Como tal , puedo evaluar una serie de transmisiones a la vez con una escala de rendimiento lineal, pero prácticamente hablando, la cantidad de emuladores en ejecución solo puede ser de 8 a 32 (y 32 realmente lo empuja) antes de que el rendimiento del sistema se deteriore. Esto significa (dada la opción), un algoritmo que puede procesar mientras se realiza una evaluación sería muy beneficioso, porque el optimizador puede hacer un poco de trabajo pesado mientras espera una evaluación.

Como prueba, mi función de evaluación (para el juego Banjo Kazooie ) era sumar, por cuadro, la distancia desde el jugador hasta un punto de gol. Esto significaba que la solución óptima era acercarse lo más rápido posible a ese punto. Limitando la mutación solo al stick analógico, tardó un día en obtener una solución correcta . (Esto fue antes de implementar la concurrencia).

Después de agregar concurrencia, habilité la mutación de presionar un botón e hice la misma función de evaluación en un área que requería saltar. Con 24 emuladores en ejecución, tardó aproximadamente 1 hora en alcanzar el objetivo desde una secuencia de entrada inicialmente en blanco, pero probablemente necesitaría ejecutarse durante días para llegar a algo cercano a lo óptimo.

Problema

¡El problema que enfrento es que no sé lo suficiente sobre el campo de optimización matemática para saber cómo modelar adecuadamente mi problema de optimización ! Puedo seguir aproximadamente la idea conceptual de muchos algoritmos como se describe en Wikipedia, por ejemplo, pero no sé cómo clasificar mi problema o seleccionar el algoritmo más avanzado para esa categoría.

Por lo que puedo decir, tengo un problema combinatorio con un vecindario extremadamente grande . Además de eso, la función de evaluación es extremadamente discontinua, no tiene gradiente y tiene muchas mesetas . Además, no hay muchas restricciones, aunque con mucho gusto agregaré la capacidad de expresarlas si esto ayuda a resolver el problema; Me gustaría permitir especificar que el botón Inicio no se debe utilizar, por ejemplo, pero este no es el caso general.

Pregunta

Entonces mi pregunta es: ¿cómo modelo esto? ¿Qué tipo de problema de optimización estoy tratando de resolver? ¿Qué algoritmo se supone que debo usar? No tengo miedo de leer trabajos de investigación, ¡así que hágame saber lo que debería leer!

Intuitivamente, un algoritmo genético no podría ser el mejor, porque realmente no parece aprender. Por ejemplo, si presionar Inicio parece empeorar siempre la evaluación (porque detiene el juego), debería haber algún tipo de diseñador o cerebro que aprenda: "presionar Inicio en cualquier momento es inútil". ¡Pero incluso este objetivo no es tan trivial como parece, porque a veces presionar inicio es óptimo, como en la llamada "pausa hacia atrás-saltos largos" en Super Mario 64 ! Aquí el cerebro tendría que aprender un patrón mucho más complejo: "presionar Start es inútil excepto cuando el jugador está en este estado muy específico y continuará con alguna combinación de presionar botones ".

Parece que debería (o la máquina podría aprender a) representar la entrada de alguna otra manera más adecuada para la modificación. La entrada por cuadro parece demasiado granular, porque lo que realmente se necesitan son "acciones", que pueden abarcar varios cuadros ... sin embargo, muchos descubrimientos se hacen cuadro por cuadro, por lo que no puedo descartarlo por completo (el la pausa antes mencionada, salto hacia atrás-largo requiere precisión a nivel de cuadro). También parece que el hecho de que la entrada se procesa en serie debería ser algo que se pueda capitalizar, pero no estoy seguro de cómo.

Actualmente estoy leyendo sobre la búsqueda de tabú (reactiva), la búsqueda de vecindario a muy gran escala, la optimización basada en la enseñanza y el aprendizaje y la optimización de colonias de hormigas.

¿Es este problema simplemente demasiado difícil de abordar con algo más que algoritmos genéticos aleatorios? ¿O es realmente un problema trivial que se resolvió hace mucho tiempo? Gracias por leer y gracias de antemano por cualquier respuesta.

De la información que proporciona en su pregunta, no puedo ver cómo aplicar métodos de optimización estándar (que yo sepa). Sus objetos no son tan complicados (más sobre eso más adelante), pero su función de destino es desagradable: sus valores están definidos por un sistema externo fuera de su control, es poco probable que tenga buenas propiedades, y así sucesivamente. Por lo tanto, creo que usar algoritmos genéticos no es inviable y quizás incluso un buen enfoque aquí; a menudo funcionan mejor que otros métodos si no tienes idea de la estructura de tu problema. Hay mucho que considerar sobre

• espacio objeto
• función objetivo y
• parámetros de su algoritmo genético,

así que permítanme explicarlo.

¿Cuáles son tus objetos?

Ya has respondido eso: estás viendo una secuencia de acciones, cada una de las cuales ocupa un cuadro. Creo que esto puede ser demasiado fino; tal vez intente una secuencia de acciones, cada una con una duración (en número de cuadros). Esto permitiría tener mutaciones como "caminar un poco más" para tener diferentes probabilidades que "insertar una presión de A" de forma natural. Pruebe lo que funciona mejor; Puede que tenga que volver a visitar este artículo después de pensar en los otros ingredientes.

¿Cuál es su función objetivo?

Este es realmente crucial. ¿Qué quieres optimizar? ¿Hora de gol? ¿Número de acciones diferentes? ¿El número de estrellas recogidas? ¿Una combinación de varios factores? Tan pronto como obtienes múltiples objetivos, las cosas se ponen difíciles : ¡por lo general, ya no hay óptimos!

Mencionaste tiempo para el gol. Es probable que esta no sea una buena función objetivo. ¿Por qué? Debido a que la mayoría de las secuencias ni siquiera alcanzarán el objetivo, por lo tanto, llegarán a la línea de fondo a una constante, creando un paisaje de fitness como este (bosquejo conceptual en una dimensión):

^{[ fuente ]}

Hay grandes áreas donde la función objetivo es . Los algoritmos genéticos tienen que ver con las señales : los pequeños cambios en la solución tienen que indicar una mejora (o disminución) en la calidad si y solo si el cambio se "dirige" hacia una solución óptima (idealmente). Si ese no es el caso (drásticamente), tiene poco más que una búsqueda aleatoria, encontrando una buena solución con probabilidad cercana a . ¿Qué significa eso para nuestra función objetivo? Tiene que ser algo que mejore cada vez que una solución mejore ligeramente, incluso si la calidad general sigue siendo baja . ¿Y qué hay de$0$$0$

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

usando "infinito" como tiempo para alcanzar el objetivo si no se alcanza el objetivo, se establece el segundo sumando a . Mientras no se alcance el objetivo, acercarse mueve la aptitud hasta . Todas las secuencias que alcanzan la meta tienen una línea base de y mejoran aún más cuanto más rápido sean.1 $0$$1$$1$

Entonces, ¿cómo se mide la distancia? La distancia lineal puede parecer tentadora pero tiene sus problemas; nuevamente, se pueden enviar señales incorrectas. Considere este escenario simple:

^{[ fuente ]}

Cada secuencia que comienza con un salto al corredor superior mejora hasta que alcanza un punto justo por encima de la meta, ¡pero en realidad nunca puede llegar a la meta! Peor aún, entre todas las secuencias que no alcanzan la meta, las que suben son tan buenas como las que bajan, por lo que el GA no puede rechazar secuencias que están claramente condenadas. En otras palabras, la distancia lineal crea óptimos locales particularmente malos que pueden atrapar el GA si hay callejones sin salida en el nivel.

Por lo tanto, le sugiero que superponga una cuadrícula sobre su nivel y conecte los puntos vecinos si el personaje del juego puede pasar de uno a otro. Luego calcula la distancia desde el objetivo por la longitud del camino más corto desde el punto más cercano al lugar donde la secuencia aterriza el personaje hasta el punto más cercano al objetivo. Esto es fácil de calcular y caminar hacia los muertos (óptimos locales) se castiga de inmediato¹. Por supuesto, necesita acceso a los datos de nivel, pero supongo que los tiene.

¿Cómo funciona tu GA?

Ahora podemos llegar al algoritmo genético real. Las consideraciones clave son población, selección, reproducción / mutación y criterio de detención.

Población

¿Qué tan grande será su población? Si es demasiado pequeño, puede no proporcionar la diversidad necesaria para alcanzar una buena solución. Si es demasiado grande, es más probable que lleve basura inútil, lo que ralentizará el proceso.

¿Cómo inicializas a tu población? ¿Eliges secuencias de acción al azar? Si es así, ¿de qué longitud? ¿Tiene una cantidad (pequeña) de soluciones razonables generadas manualmente para sembrar, tal vez tales que alcancen el objetivo?

Selección

¿Qué individuos son seleccionados para supervivencia / reproducción? El mejor? ¿Celebras torneos ? ¿Decide la supervivencia de un individuo al azar con respecto a su estado físico ? ¿Desea lo mejor para sobrevivir en cualquier caso o pueden morir (puede ser útil para dejar óptimos locales) ²?$k$

El concepto central aquí es la presión de selección : ¿qué tan difícil es sobrevivir? Hazlo demasiado pequeño y no eliminarás las soluciones de basura. Hágalo demasiado alto y realice cambios (en particular, moverse entre los óptimos locales) con fuerza.

Reproducción y Mutación

Una vez que haya seleccionado a sus sobrevivientes de una ronda, debe crear la próxima generación a partir de ellos (¿sobreviven los padres y son parte de la próxima generación?). Hay dos estrategias principales: mutación y recombinación.

La mutación es bastante clara, aunque los detalles pueden diferir. Para cada posición en la secuencia de un individuo, mute con cierta probabilidad. Puede hacer esto independientemente para cada posición, o elegir el número de mutaciones al azar, o puede realizar diferentes mutaciones con diferentes probabilidades (como insertar un nuevo elemento, eliminar uno, cambiar uno, ...). La mutación generalmente se trata de pequeños cambios.

La recombinación, que combina aspectos de dos o más soluciones para una nueva, es más complicada pero puede permitir grandes pasos, es decir, dejar una "montaña de ejercicios" y moverse directamente a la pendiente de otra (que puede ser más alta). Una idea clásica es el crossover ; No sé si eso tiene sentido aquí (me parece que intercambiar el prefijo de una secuencia dada por otra cosa probablemente devaluará el sufijo). Tal vez pueda usar el conocimiento sobre el nivel y las posiciones del personaje del juego en diferentes puntos de la secuencia para guiar esto, es decir, crear puntos de cruce solo cuando el personaje esté en la misma posición en ambas secuencias.

Terminación

¿Cuándo te detienes? ¿Después de generaciones? ¿Cuándo la condición física máxima no ha mejorado desde rondas? ¿Se detiene temprano si no se ha alcanzado algún estado físico (con la función anterior, ) después de rondas para eliminar las poblaciones iniciales inútiles temprano?k 1 $N$$k$$1$$n$

Como puede ver, todas estas cosas se entrelazan para influir en el rendimiento real. Si ejecuta varias poblaciones en paralelo, incluso puede pensar en implementar la deriva genética debido a la migración y / o catástrofes. Hay poca teoría para guiar su camino, por lo que debe probar diferentes configuraciones y ver dónde lo lleva. Con suerte, lo que funciona para un nivel también funcionará para otros. ¡Feliz retoques!

Nota bene: Eche un vistazo a BoxCar 2D a la luz de lo anterior. Hacen algunas cosas bastante bien (otras, no tanto) y puede hacerse una idea de cómo los parámetros de una AG pueden influir en su rendimiento.

1. En realidad, construir una secuencia con avidez usando esta aptitud, es decir, elegir la acción que minimiza la distancia a la meta de todas las acciones posibles, puede funcionar bastante bien. Prueba eso antes de usar GA!
2. Por supuesto, usted como observador siempre recuerda la mejor solución jamás encontrada.

Para obtener más detalles sobre el método de optimización basada en la enseñanza-aprendizaje (TLBO) y su código, consulte el siguiente documento:

Un algoritmo de optimización basado en la enseñanza-aprendizaje elitista para resolver problemas complejos de optimización restringida por R. Venkata Rao y V. Patel; International Journal of Industrial Engineering Computations 3 (4): 535–560 (2012)

Para lectura adicional:

• Algoritmo de optimización basado en enseñanza-aprendizaje para problemas de optimización de parámetros reales sin restricciones y restringidos por R. Venkata Rao, VJ Savsani y J. Balic; Optimización de ingeniería (2012)
• Optimización del diseño mecánico utilizando técnicas avanzadas de optimización por R. Venkata Rao, JV Savsani; Springer-Verlag Londres (2012); ISBN 978-1-4471-2747-5
• Optimización de objetivos múltiples de intercambiadores de calor utilizando un algoritmo de optimización basado en enseñanza-aprendizaje modificado por R. Venkata Rao y V. Patel; Modelado matemático aplicado (2012)
• Optimización de objetivos múltiples de enfriadores termoeléctricos de dos etapas utilizando un algoritmo de optimización basado en la enseñanza y el aprendizaje modificado por R. Venkata Rao y V. Patel; Aplicaciones de Ingeniería de Inteligencia Artificial (2012)