user_mobilelogo

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 sciencecomputer 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 detectedone 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