������������������������������������������������������������������������������

 

Control en la Calidad de Optimizaci�n con Resoluci�n del Problema de Ajedrez de las Ocho Reinas con el Algoritmo de B�squeda Temple Simulado

 

Control in the Optimization Quality with Resolution of the Eight Queens Chess Problem with the Simulated Temple Search Algorithm

 

Controle na Qualidade de Otimiza��o com Resolu��o do Problema de Xadrez das Oito Rainhas com o Algoritmo de Busca de Templos Simulados

 

 

 

 

 

 

 

 

 

 

 

 

 

����������������������������������������

 

Correspondencia: mario.moreno01@epn.edu.ec �

 

 

Ciencias T�cnicas y Aplicadas

Art�culo de Revisi�n

 

 

* Recibido: 20 de marzo de 2022 *Aceptado: 18 de abril de 2022 * Publicado: 24 de mayo de 2022

 

 

        I.            Magister en Computaci�n Menci�n en Sistemas Inteligentes, Escuela Polit�cnica Nacional, Quito, Ecuador.

     II.            Magister en Ingenier�a Industrial y Productividad Msc, Escuela Polit�cnica Nacional, Quito, Ecuador.

   III.            Magister en Inform�tica Aplicada, Escuela Superior Polit�cnica de Chimborazo (ESPOCH), Riobamba, Ecuador.

 

 

Resumen

El algoritmo de Temple Simulado se utiliza para resolver problemas de optimizaci�n, ya sea para minimizar los gastos o aumentar las ganancias. La resoluci�n del problema de ajedrez de las ocho reinas con el algoritmo mencionado anteriormente, en este trabajo se us� datos de tiempo de 1700000 y de temperatura de 100000. Eso dio un tiempo de ejecuci�n promedio de 0.0681 segundos.

Palabras Clave: Algoritmo de B�squeda; Temple Simulado; Problemas de Optimizaci�n; Ocho Reinas.

 

Abstract

The Simulated Annealing algorithm is used to solve optimization problems, either to minimize expenses or increase profits. The resolution of the chess problem of the eight queens with the algorithm mentioned above, in this work was used time data of 1700000 and temperature of 100000. That gave an average execution time of 0.0681 seconds.

Keywords: Search Algorithm; Simulated Temple; Optimization Problems; Eight Queens.

 

Resumo

O algoritmo Simulated Quenching � utilizado para resolver problemas de otimiza��o, seja para minimizar custos ou aumentar lucros. Resolvendo o problema do xadrez das oito rainhas com o algoritmo mencionado acima, neste trabalho foram utilizados dados de tempo de trabalho de 1700000 e dados de temperatura de 100000, o que deu um tempo m�dio de execu��o de 0,0681 segundos.

Palavras-chave: Algoritmo de Busca; T�mpera simulada; Problemas de Otimiza��o; Oito Rainhas.

 

Introducci�n

El algoritmo de temple es conocido tambi�n como: recorrido simulado, cristalizaci�n simulada o enfriamiento simulado. Es un algoritmo de b�squeda para la optimizaci�n global de problemas, el objetivo es el de encontrar una buena aproximaci�n al valor �ptimo de la funci�n en un espacio de b�squeda que es amplio, al valor optimo se lo conoce como optimo global [1].

El nombre del proceso del algoritmo est� inspirado en el recocido del acero y cer�micas, t�cnica en la que consiste en calentar y luego enfriar lentamente el material para que sus propiedades f�sicas var�en. El Temple Simulado es la uni�n de la ascensi�n de colinas con un camino aleatorio de un conjunto de sucesores que produce eficacia como completitud [1], [2].

El temple simulado es similar a colocar una pelota de ping-pong en la grieta las profunda de una superficie desigual, si esta pelota rodara sola se estancar�a en un m�nimo local, pero si se sacude la superficie esta puede llegar al m�nimo global; es decir; la soluci�n del temple simulado inicia sacudiendo con fuerza y luego gradualmente seguir reduciendo la intensidad de la sacudida [2].

El algoritmo del Temple Simulado es muy similar al ascenso de colinas, su bucle interno en vez de escoger el mejor movimiento escoge un movimiento aleatorio. Si el movimiento mejora la situaci�n es siempre aceptado, el algoritmo acepta el movimiento con una probabilidad menor que 1, la probabilidad tambi�n baja cuando la temperatura baja, si el esquema disminuye la temperatura bastante despacio, el algoritmo encontrara un �ptimo global con probabilidad cerca de 1 [2].

Para este caso en particular se implement� el algoritmo del Temple Simulado para resolver el problema de ajedrez de las ocho reinas, que consiste en poner ocho reinas en un tablero de ajedrez sin que se amenacen. Una reina amenaza aquellas piezas que se encuentren en su misma fila, columna o diagonal. El problema de las ocho reinas consiste en poner en un tablero de ajedrez ocho reinas sin que estas se amenacen, este caso fue propuesto por el ajedrecista alem�n Max Bezzel en 1848.

Existen varias respuestas al problema anteriormente mencionado por ejemplo existen algoritmos que implementados con backtracking, b�squedas en profundidad, algoritmos gen�ticos, etc. El presente trabajo realiza una soluci�n al problema de las ocho reinas mediante el algoritmo del Temple Simulado para �comprobar si el algoritmo emite una respuesta �ptima, el desarrollo del algoritmo se lo realizo en el lenguaje de programaci�n c++ [3]�[6].

Este trabajo en la Secci�n II denominada Metodolog�a y Materiales se encuentra la metodolog�a usada para resolver el problema planteado , la Secci�n III Resultados muestra los datos que se obtuvo al realizar el algoritmo del Temple Simulado, la Secci�n IV �Discusi�n de los resultados obtenidos y Secci�n V Conclusiones la cual muestra las conclusiones en base a los resultados obtenidos.

 

 

 

Metodolog�a y materiales

El algoritmo de Temple Simulado en este caso en particular de las ocho reinas es necesario minimizar el costo computacional, que ocasiona el resolver estos tipos de problemas de optimizaci�n combinatoria ya que tiene un conjunto de piezas y hay posiciones en las que se deben colocar cada pieza de forma que no se amenacen [7].

El seudoc�digo del algoritmo de Temple Simulado es el siguiente[2]:

 

Funci�n TEMPLE-SIMULADO(problema, esquema) devuelve un estado soluci�n

Entradas: problema, un problema

esquema, una aplicaci�n desde el tiempo a �temperatura� variables locales: actual, un nodo

����� siguiente, un nodo

����� T, una �temperatura� controla la�������� probabilidad de un paso hacia abajo

actual ← HACER-NODO(ESTADO-INICIAL[problema])

para t ← 1 a ∞ hacer

T ← esquema[t]

si T = 0 entonces devolver actual

siguiente ← un sucesor seleccionado aleatoriamente de actual

∆E ← VALOR[siguiente] - VALOR[actual]

si ∆E > 0 entonces actual ← siguiente

en caso contrario actual ← siguiente s�lo con probabilidad

 

En el presente trabajo el seudoc�digo fue implementado en lenguaje de programaci�n c++, en este algoritmo se deben definir valores a la temperatura que es 100000 y el tiempo m�ximo para realizar las iteraciones es 1700000. El tiempo es el que decide si se sobrepasa su valor este devolver�a la mejor respuesta que ha obtenido.

Los principales problemas al momento de la implementaci�n del algoritmo de Temple Simulado para el problema de las ocho reinas fue: el decidir cu�l es la mejor cantidad para el tiempo y la temperatura ya que si el tiempo es muy bajo este no llegar�a a alcanzar la respuesta deseada, al igual que la temperatura si no empieza de forma adecuada.

Con las cantidades de la temperatura y el tiempo mencionados anteriormente se obtuvo un tiempo bajo para hallar la respuesta correcta al problema de las ocho reinas, cabe mencionar que el programa implementado para este caso se ejecut� diez veces as� obteniendo un promedio de tiempo de ejecuci�n.��

 

Resultados

A continuaci�n en la Tabla 1 se presenta los tiempos correspondientes a cada ejecuci�n realizada, con el algoritmo del Temple Simulado.

 

 

���������������������������������

Como medida de dispersi�n de los datos de la Tabla 1, con respecto a la media o promedio se obtuvo el valor de 0.034 segundos. Para un mejor entendimiento de presenta la Figura 1.

 

Discusi�n

En el presente trabajo en el que se realiz� la implementaci�n del algoritmo de Temple Simulado para la resoluci�n del problema de las ocho reinas, al realizar las ejecuciones correspondientes para hallar sus tiempos de ejecuci�n, se puede observar que al ocupar los datos de: temperatura con 100000 y el tiempo con 1700000 se obtiene un tiempo promedio de ejecuci�n de 0.068 segundos.�

 

Conclusiones

El problema de las ocho reinas utilizando el algoritmo de Temple Simulado con tiempo de 1700000 da una respuesta �ptima con un tiempo de ejecuci�n bajo.

 

Referencias

[1]����� �revista enLinea.� [Online]. Available: https://www.azc.uam.mx/publicaciones/enlinea2/3-2rec.htm. [Accessed: 03-Feb-2019].

[2]����� S. Norvig, P., & Russell, Inteligencia artificial, vol. 1, no. 3. 2014.

[3]����� E. W. Weisstein, �Queens Problem.�

[4]����� �Computer Science and Software Engineering.�

[5]����� V. M. Saffarzadeh, P. Jafarzadeh, and M. Mazloom, �A Hybrid Approach Using Particle Swarm Optimization and Simulated Annealing for N-queen Problem.�

[6]����� P. B. Gibbons and J. A. Webb, �Some New Results for the Queens Domination Problem.�

[7]����� J. del C. P. Abarca, J. Y. J. Ch�vez, and B. M. Bahena, �Aplicaciones de recocido simulado en problemas de optimizaci�n combinatoria,� Inven. la g�nesis la Cult. Univ. en Morelos, vol. 11, no. 23, pp. 23�28, 2015.

 

 

 

� 2022 por los autores. Este art�culo es de acceso abierto y distribuido seg�n los t�rminos y condiciones de la licencia Creative Commons Atribuci�n-NoComercial-CompartirIgual 4.0 Internacional (CC BY-NC-SA 4.0)

(https://creativecommons.org/licenses/by-nc-sa/4.0/).