Resumen de Un acercamiento natural al problema de las N-Reinas

Enrique Alba Torres , J.C. Durán

• español

  En este trabajo evaluamos el comportamiento de varias técnicas basadas en procesos naturales tales como la evolución, la neurofisiología del cerebro o el enfriamiento de materiales. En particular, nos interesa comparar el comportamiento relativo de los Algoritmos Genéticos, Redes Neuronales Artificiales, Enfriamiento Simulado y una propuesta llamada Algoritmo Potencial sobre los mismos problemas. Hemos seleccionado las N-Reinas por tratarse de un problema conocido y porque de él se pueden extraer instancias-problema tan grandes como se desee. Hemos adoptado como base comparativa las técnicas de retropropagación (Backtracking) y los algoritmos de Las Vegas. Nuestros resultados muestran que las técnicas naturales son altamente competitivas para solucionar instancias del problema de hasta N=1024 o más reinas de forma eficiente. De hecho los algoritmos genéticos son especialmente buenos reduciendo el número de puntos del espacio de búsqueda visitados antes de alcanzar una solución (aunque a veces es subóptima). El enfriamiento simulado y las redes neuronales son muy eficientes en tiempo real. El resto de técnicas tienen un comportamiento bastante menos eficiente y eficaz.

• English

  In this work we evaluate the behavior of some methods inspired in natural processes like the evolution, the neurophysiology of the human brain or the annealing of materials. In particular, we are interested in comparing popular methods, namely: Genetic Algorithms, Artificial Neural Networks, Simulated Annealing and new ones like the Potential Algorithm. We have selected the N-Queen problem as the testbed since it is a well known problem from which we can derive instances of increasing difficulty. Backtracking and Las Vegas Algorithms represent the base line of our comparisons. Our results show that the natural methods are highly competitive in solving instances of the problem of up to N=1024 queens in an efficient way. In fact Genetic Algorithms are specially good in reducing the number of search points which are visited before reaching a (possibly sub-optimal) solution. The methods of Simulated Annealing and Artificial Neural Networks are very efficient in real time. The other methods present a much less efficient and effective behavior.