Este Trabajo Fin de Grado presenta el estudio y desarrollo de un sistema de inteligencia artificial orientado a la resolución del cubo de Rubik 3x3x3 mediante técnicas de optimización combinatoria. El proyecto se centra en el diseño e implementación de un solver basado en un modelo evolutivo mixto, cuyo núcleo es un Algoritmo de Estimación de Distribuciones (EDA), complementado con distintos mecanismos heurísticos y un simulador propio que permite evaluar de forma controlada el comportamiento del sistema.
El documento comienza con una introducción al problema, en la que se define el cubo de Rubik como un reto combinatorio de gran complejidad y se presentan los EDAs como una alternativa a otros enfoques clásicos de búsqueda y optimización. A partir de esta base, se establecen las hipótesis de trabajo, el ámbito y alcance del proyecto, así como los objetivos perseguidos, centrados en analizar la viabilidad de este tipo de algoritmos para la resolución automática del cubo y en estudiar el impacto de distintas mejoras prácticas sobre su rendimiento.
A continuación, se desarrolla un marco teórico que recoge los fundamentos necesarios para el proyecto y un análisis del estado del arte. En este apartado se abordan tanto los aspectos teóricos del cubo de Rubik —incluyendo su estructura, notación, simetrías y estrategias de resolución— como los principales conceptos de la optimización combinatoria y los algoritmos evolutivos, con especial énfasis en los EDAs, sus variantes basadas en modelos gráficos y las estrategias híbridas empleadas en la literatura.
El núcleo del trabajo lo constituye el diseño e implementación del modelo del cubo y del solver. Se presenta una representación formal del cubo que permite simular sus estados y movimientos, así como mecanismos de simplificación, canonización, eliminación de ciclos y explotación de simetrías. Sobre esta base se construye el solver evolutivo, definiendo la representación de los individuos, las funciones de fitness basadas en medidas de similitud y otros criterios alternativos, y el proceso de evolución. El algoritmo se enriquece progresivamente mediante técnicas como elitismo, mutación, búsqueda local y poda, dando lugar a un modelo evolutivo mixto que combina exploración probabilística y explotación heurística.
Finalmente, se presentan y analizan los resultados obtenidos a partir de distintas pruebas experimentales, evaluando el grado de cumplimiento de los objetivos planteados y comparando el comportamiento de las distintas configuraciones del algoritmo. El trabajo concluye con una discusión sobre las principales conclusiones extraídas, las limitaciones del enfoque propuesto y las posibles líneas de mejora futuras, incluyendo la exploración de modelos probabilísticos alternativos y el uso más profundo de herramientas matemáticas, como la teoría de grupos.
En conjunto, este TFG aporta un estudio detallado y experimental sobre la aplicación de algoritmos de estimación de distribuciones y estrategias evolutivas híbridas a un problema combinatorio complejo, ofreciendo una base sólida para futuras extensiones en el ámbito de la inteligencia artificial y la optimización.
ABSTRACT
This Bachelor’s Thesis presents the study and development of an artificial intelligence system aimed at solving the 3x3x3 Rubik’s Cube using combinatorial optimization techniques. The project focuses on the design and implementation of a solver based on a mixed evolutionary model, whose core is an Estimation of Distribution Algorithm (EDA), complemented by several heuristic mechanisms and a custom simulator that allows the system’s behavior to be evaluated in a controlled manner.
The document begins with an introduction to the problem, defining the Rubik’s Cube as a highly complex combinatorial challenge and presenting EDAs as an alternative to classical search and optimization approaches. Based on this foundation, the working hypotheses, the scope of the project, and the main objectives are established, with a particular emphasis on analyzing the feasibility of these algorithms for the automatic resolution of the cube and on studying the impact of different practical enhancements on their performance.
Subsequently, a theoretical framework and a review of the state of the art are developed. This section addresses both the theoretical aspects of the Rubik’s Cube—including its structure, notation, symmetries, and resolution strategies—and the main concepts of combinatorial optimization and evolutionary algorithms, with special emphasis on EDAs, their variants based on graphical models, and hybrid strategies reported in the literature.
The core of the thesis consists of the design and implementation of the cube model and the solver. A formal representation of the cube is presented, enabling the simulation of its states and movements, along with mechanisms for simplification, canonization, cycle elimination, and exploitation of symmetries. On this basis, the evolutionary solver is constructed by defining the representation of individuals, fitness functions based on similarity measures and alternative criteria, and the evolutionary process itself. The algorithm is progressively enhanced through techniques such as elitism, mutation, local search, and pruning, resulting in a mixed evolutionary model that combines probabilistic exploration with heuristic exploitation.
Finally, the results obtained from different experimental tests are presented and analyzed, evaluating the degree to which the proposed objectives are achieved and comparing the behavior of the different algorithm configurations. The thesis concludes with a discussion of the main findings, the limitations of the proposed approach, and possible future lines of improvement, including the exploration of alternative probabilistic models and a deeper use of mathematical tools such as group theory.
Overall, this project provides a detailed experimental study on the application of estimation of distribution algorithms and hybrid evolutionary strategies to a complex combinatorial problem, offering a solid foundation for future extensions in the field of artificial intelligence and optimization.
Este Trabajo Fin de Grado presenta el estudio y desarrollo de un sistema de inteligencia artificial orientado a la resolución del cubo de Rubik 3x3x3 mediante técnicas de optimización combinatoria. El proyecto se centra en el diseño e implementación de un solver basado en un modelo evolutivo mixto, cuyo núcleo es un Algoritmo de Estimación de Distribuciones (EDA), complementado con distintos mecanismos heurísticos y un simulador propio que permite evaluar de forma controlada el comportamiento del sistema.
El documento comienza con una introducción al problema, en la que se define el cubo de Rubik como un reto combinatorio de gran complejidad y se presentan los EDAs como una alternativa a otros enfoques clásicos de búsqueda y optimización. A partir de esta base, se establecen las hipótesis de trabajo, el ámbito y alcance del proyecto, así como los objetivos perseguidos, centrados en analizar la viabilidad de este tipo de algoritmos para la resolución automática del cubo y en estudiar el impacto de distintas mejoras prácticas sobre su rendimiento.
A continuación, se desarrolla un marco teórico que recoge los fundamentos necesarios para el proyecto y un análisis del estado del arte. En este apartado se abordan tanto los aspectos teóricos del cubo de Rubik —incluyendo su estructura, notación, simetrías y estrategias de resolución— como los principales conceptos de la optimización combinatoria y los algoritmos evolutivos, con especial énfasis en los EDAs, sus variantes basadas en modelos gráficos y las estrategias híbridas empleadas en la literatura.
El núcleo del trabajo lo constituye el diseño e implementación del modelo del cubo y del solver. Se presenta una representación formal del cubo que permite simular sus estados y movimientos, así como mecanismos de simplificación, canonización, eliminación de ciclos y explotación de simetrías. Sobre esta base se construye el solver evolutivo, definiendo la representación de los individuos, las funciones de fitness basadas en medidas de similitud y otros criterios alternativos, y el proceso de evolución. El algoritmo se enriquece progresivamente mediante técnicas como elitismo, mutación, búsqueda local y poda, dando lugar a un modelo evolutivo mixto que combina exploración probabilística y explotación heurística.
Finalmente, se presentan y analizan los resultados obtenidos a partir de distintas pruebas experimentales, evaluando el grado de cumplimiento de los objetivos planteados y comparando el comportamiento de las distintas configuraciones del algoritmo. El trabajo concluye con una discusión sobre las principales conclusiones extraídas, las limitaciones del enfoque propuesto y las posibles líneas de mejora futuras, incluyendo la exploración de modelos probabilísticos alternativos y el uso más profundo de herramientas matemáticas, como la teoría de grupos.
En conjunto, este TFG aporta un estudio detallado y experimental sobre la aplicación de algoritmos de estimación de distribuciones y estrategias evolutivas híbridas a un problema combinatorio complejo, ofreciendo una base sólida para futuras extensiones en el ámbito de la inteligencia artificial y la optimización.
ABSTRACT
This Bachelor’s Thesis presents the study and development of an artificial intelligence system aimed at solving the 3x3x3 Rubik’s Cube using combinatorial optimization techniques. The project focuses on the design and implementation of a solver based on a mixed evolutionary model, whose core is an Estimation of Distribution Algorithm (EDA), complemented by several heuristic mechanisms and a custom simulator that allows the system’s behavior to be evaluated in a controlled manner.
The document begins with an introduction to the problem, defining the Rubik’s Cube as a highly complex combinatorial challenge and presenting EDAs as an alternative to classical search and optimization approaches. Based on this foundation, the working hypotheses, the scope of the project, and the main objectives are established, with a particular emphasis on analyzing the feasibility of these algorithms for the automatic resolution of the cube and on studying the impact of different practical enhancements on their performance.
Subsequently, a theoretical framework and a review of the state of the art are developed. This section addresses both the theoretical aspects of the Rubik’s Cube—including its structure, notation, symmetries, and resolution strategies—and the main concepts of combinatorial optimization and evolutionary algorithms, with special emphasis on EDAs, their variants based on graphical models, and hybrid strategies reported in the literature.
The core of the thesis consists of the design and implementation of the cube model and the solver. A formal representation of the cube is presented, enabling the simulation of its states and movements, along with mechanisms for simplification, canonization, cycle elimination, and exploitation of symmetries. On this basis, the evolutionary solver is constructed by defining the representation of individuals, fitness functions based on similarity measures and alternative criteria, and the evolutionary process itself. The algorithm is progressively enhanced through techniques such as elitism, mutation, local search, and pruning, resulting in a mixed evolutionary model that combines probabilistic exploration with heuristic exploitation.
Finally, the results obtained from different experimental tests are presented and analyzed, evaluating the degree to which the proposed objectives are achieved and comparing the behavior of the different algorithm configurations. The thesis concludes with a discussion of the main findings, the limitations of the proposed approach, and possible future lines of improvement, including the exploration of alternative probabilistic models and a deeper use of mathematical tools such as group theory.
Overall, this project provides a detailed experimental study on the application of estimation of distribution algorithms and hybrid evolutionary strategies to a complex combinatorial problem, offering a solid foundation for future extensions in the field of artificial intelligence and optimization. Read More
Related posts:
Desarrollo de una aplicación didáctica sobre el cubo de Rubik y su aplicación en la enseñanza de estructuras algebraicas
Diseño y desarrollo de un resolvedor para cubos de Rubik con bloqueos
Managing combinatorial optimization problems by means of evolutionary computation and multi-agent system
Aplicación de la inteligencia artificial para la gestión de la innovación: análisis del modelo ChatGPT
Take $65 off this Logitech MX keyboard and mouse bundle today
Interview: Simon Goodyear, chief information and technology officer, Redwood Bank