Luego de de nuestra prolongada recopilación de datos resolvimos esta dificultad que presentan ciertos los lectores. Te regalamos la solución y esperamos que te resulte de mucha ayuda.
Solución:
Descargo de responsabilidad: no soy un experto en cubos de Rubik, incluso nunca resolví uno
Resolver un cubo de Rubik dado por GA
Tiene una configuración dada y quiere usar GA para producir la secuencia de pasos que resuelven esta configuración particular.
Representación
Para cada uno de los ejes hay tres posibles rotaciones, cada una de ellas en dos direcciones. Esto da los siguientes movimientos:
X1+, X1-, X2+, X2-, X3+, X3-,
Y1+, Y1-, Y2+, Y2-, Y3+, Y3-,
Z1+, Z1-, Z2+, Z2-, Z3+, Z3-
El genotipo es entonces una secuencia de estos movimientos.
Genotipo
Hay dos posibilidades:
- genotipo de longitud variable
- genotipo de longitud fija
Longitud variable El genotipo sigue la idea de que no sabemos, de antemano, cuántos movimientos llevará resolver la configuración particular. Volveré sobre esta variante más tarde.
Longitud fija También se puede utilizar el genotipo. Aunque no sabemos cuántos movimientos tomará resolver la configuración particular, saber que ningún la configuración se puede resolver en 20 movimientos o menos. Dado que 20 significaría que, para algunas posiciones, el algoritmo se vería obligado a encontrar la solución óptima (lo que podría ser bastante difícil), podemos establecer la longitud del genotipo en, digamos, 50 para darle cierta flexibilidad al algoritmo.
Aptitud física
Debe encontrar una buena medida de aptitud para juzgar la calidad de las soluciones. Actualmente no puedo pensar en una buena medida de calidad ya que no soy un experto en cubos de Rubik. Sin embargo, probablemente debería incorporar la cantidad de movimientos en su medida de condición física. Volveré a ello un poco más tarde.
También debe decidir si está buscando ningún solución o para una buena. Si está buscando alguna solución, puede detenerse en la primera solución encontrada. Si está buscando una buena solución, no se detiene en la primera solución encontrada, sino que luego optimiza su longitud. Luego se detiene cuando decide detenerse (es decir, después de una cantidad deseada de tiempo dedicado a la búsqueda).
Operadores
Los dos operadores básicos, cruce y mutación, pueden ser básicamente idénticos al GA clásico. La única diferencia es que no tienes dos estados para un “bit”, sino 18. Incluso cuando usas un genotipo de longitud variable, el cruce puede seguir siendo el mismo: simplemente cortas ambos genotipos en dos partes e intercambias las colas. La única diferencia con el caso de longitud fija es que los cortes no se realizarán en las mismas posiciones, sino que serán independientes entre sí.
Inflar
El uso de genotipos de longitud variable trae un fenómeno desagradable, que es un crecimiento excesivo del tamaño de la solución, sin un gran impacto en la aptitud. En Programación Genética (que es un tema bastante diferente) esto se llama inflar. Esto puede ser controlado por dos mecanismos.
El primer mecanismo que ya mencioné: incorporar la longitud de la solución en la aptitud. Si busca una buena solución (es decir, no se detiene en encontrar la primera), la longitud es, por supuesto, solo la longitud de la parte efectiva (es decir, el número de movimientos desde el inicio hasta el movimiento que finaliza). el cubo), sin contar el resto.
El otro mecanismo lo tomo prestado de Grammatical Evolution (un algoritmo de programación genética que también usa genotipos lineales de longitud variable), que es poda. Un operador de poda toma una solución y elimina la parte no efectiva del genotipo.
Otras posibilidades
También podría desarrollar algo como una “política” o estrategia, una regla general que, dado un cubo, decidiría qué movimiento hacer a continuación. Esa es una tarea mucho más difícil, pero definitivamente evolutiva (lo que significa que puede usar la evolución para tratar de encontrarla, no que eventualmente la encontrará). Puede usar, por ejemplo, redes neuronales como una representación de la política y usar algunos conceptos y marcos de neuroevolución para lograr esta tarea.
O podría desarrollar una heurística (utilizando Programación genética) para un algoritmo de búsqueda dado, por ejemplo, A*. El algoritmo A* necesita una heurística para estimar la distancia de un estado al estado final. Cuanto más precisa sea esta heurística, más rápido encontrará la solución el algoritmo A*.
Observaciones finales
Desde mi experiencia, si sabe algo sobre el problema (que en el caso del cubo de Rubik sí sabe), es mucho mejor usar un algoritmo dedicado o al menos informado para resolver el problema en lugar de usar uno casi ciego como GA . En mi opinión, el cubo de Rubik es no un buen problema para los GA, o mejor dicho, los GA no son buenos algoritmos para resolver el cubo de Rubik.
Si te ha sido de ayuda este post, sería de mucha ayuda si lo compartes con otros juniors de esta manera contrubuyes a dar difusión a nuestro contenido.