Juegos Combinatorios

Objetivo del proyecto:

Generar algoritmos que resuelvan problemas de optimización a partir de la experiencia de juegos computacionales. Los juegos de interés representan problemas clásicos de optimización combinatoria.

Optimización Web

Objetivo del proyecto

Generar algoritmos que resuelvan problemas de optimización a partir de la experiencia de juegos computacionales. Los juegos de interés representan problemas clásicos de optimización combinatoria.

Enfoque:

A partir de los estudios de extraordinariedad producidos en el área de psicología en los últimos años, es posible estudiar las técnicas que desarrollan los jugadores expertos en juegos computacionales. Por lo mismo, nuestra idea es crear juegos computacionales que implícitamente estén resolviendo un problema de optimización combinatoria difícil. Por ejemplo, el problema del vendedor viajero. El propósito es analizar las jugadas realizadas por estos expertos, tanto visualmente como con algoritmos de reconocimiento de patrones obteniendo como resultado un algoritmos que resuelve el problema original.

Automatic generation of algorithms

There is a variety of combinatorial optimization problems for which any efficient algorithm capable of ccurately resolve any input data of the problem, has been found so far. Such problems are associated with the decision making in large part of the production and services processes and are studied in the field of management science, computer science and operations research. Typical cases arise in the optimal use of raw material, the optimal use of time; the optimal scheduling of human resources, etc. Situations like these have been extensively studied in the literature, giving rise to a particular class of problems known as NP-complete, which in turn, is the origin of the famous conjecture of NP-completeness. Despite a relentless search for the last 40 years, an efficient algorithm for any of the problems of the family has not been found yet, in fact, one algorithm would be sufficient to activate a complex network of knowledge that interconnects all problems, triggering a specific and efficient algorithm for each problem belonging to the class. Knowing that the computational power ofprocessors has increased enormously since the NP-completeness was detected, one wonders if the task of finding efficient algorithms could be performed by machines. We argue that the creation of an algorithm for solving an optimization problem can also be seen as an optimization problem. In this case, the feasible solutions of the optimization problem are the different algorithms that solve the problem, while the objective function corresponds to the characteristics of the algorithms that we are looking for. In this project, using a suitable search method, several algorithms are automatically produced for various combinatorial optimization problems.

Contributions

• Automatically generated algorithms for the Vertex Coloring Problem. PLoS ONE, 2013.(Contreras, C., Gatica, G., Parada, V. ).
• Effective instruction trees for the graph coloring problem. International Conference on Metaheuristics and Nature Inspired Computing. Tunisia, 2012. (Contreras C., Gatica G., Parada, V. ).
• Una plataforma para la generación de  árboles de instrucciones para problemas de optimización combinatoria. Actas del XVI Congreso Latino Ibero - Americano de Investigación Operativa. Río de Janeiro, 2012.(Contreras, C., Gatica, G., Parada, V. ).
• Nuevos algoritmos para la asignación de tripulaciones con múltiples buses y depósitos. Cyted-Harosa Workshop & Meeting On Applied Optimization & Distributed Computing. Jornadas Chilenas De Computación. Valparaíso, 2012.(Parada, S., Parada, V. ).
• Automatic Generation of Algorithms for the Non Guillotine Cutting Problem. Workshop on Applied Combinatorial Optimization. Porto, 2011.(Zepeda, J.  Parada, V., Gatica, G.,, Sepúlveda, M. ).
• Algoritmos híper--heurísticos en optimización combinatoria. Congreso del Instituto Chileno de Investigación de Operaciones. Pucón. 2011.(Acuña, K., Gatica, G., Parada, V. ).
• Evolución de algoritmos para el problema del vendedor viajero simétrico. Congreso del Instituto Chileno de Investigación de Operaciones. Pucón, 2011.(Sepúlveda, M., Álvarez, J., Parada, V. ).
• Evolucionando programas para el problema de la mochila mediante programación genética. VIII Congreso Chileno de Investigación Operativa - OPTIMA 2009, Chillán, 2009.(Barra, L., Gatica, G., Parada, V. ).