Análisis comparativo de los Operadores Genéticos de Cruce Puntual SPX y Uniforme UX aplicados a la resolución del problema de optimización PathFinder

Cristian Gabriel Zambrano Vega

Abstract


En el presente trabajo se emplea un estudio experimental de dos variantes de un algoritmo evolutivo estándar para la exploración de un laberinto (PathFinder) que le permita a un robot encontrar el mejor camino de salida a partir de su ubicación dentro del mismo. La primera variante del algoritmo emplea el Operador Genético de Cruce Puntual SPX (“point crossover”) y la segunda el Operador Uniforme UX (“uniform crossover”). Los laberintos de prueba están formados por un tamaño de NxM posiciones con un 20% de ellas representadas como obstáculos para el robot,  la representación de un camino, básicamente está compuesta de cuatro coordenadas internas absolutas (Norte, Sur, Este y Oeste), pero se agregan coordenadas relativas como: Avanzar, Girar-Derecha y Girar-Izquierda, para realizar un análisis adicional al caso de estudio. Para confirmar los resultados se identifican si existen o no diferencias estadísticamente significativas entre los resultados brindados por estos dos operadores. Los resultados obtenidos indican que la mejor variante a implementarse del algoritmo es la que usa el operador UX con coordenadas relativas, ya que siempre genera una solución factible para la salida del laberinto o una solución más cercana a la salida en comparación a las otras variantes.


Keywords


Algoritmos Evolutivos, Operadores Genéticos, Cruce SPX, Cruce UX PathFinder.

Full Text:

Ver PDF (Español)

References


Alba, E., & Dorronsoro, B. (2008). Introduction to Cellular Genetic Algorithms. In Cellular Genetic Algorithms (pp. 3–20). Boston, MA: Springer US. http://doi.org/10.1007/978-0-387-77610-1_1

Back, T., 1996. Evolutionary Algorithms in Theory and Practice, Oxford Press,.

Davis, L., 1991. Handbook of Genetic Algorithms, Van Nostrand Reinhold.

Fogel, D. B. (1994). An introduction to simulated evolutionary

optimization. IEEE Transactions on Neural Networks, 5(1), 3–14. http://doi.org/10.1109/72.265956

Larrañaga, P., Kuijpers, C. M. H., Murga, R. H., Inza, I., & Dizdarevic, S. (1999). Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators.

Artificial Intelligence Review, 13(2), 129–170. http://doi.org/10.1023/A:1006529012972

M. Belén, M. José A., & M., J. M. (2003). Inteligencia Artificial. Revista Iberoamericana de Inteligencia Artificial. Inteligencia Artificial. Revista Iberoamericana de Inteligencia Artificial, 7, 0.

Sumathi, S., & Paneerselvam, S. (2010). Computational intelligence paradigms: theory & applications using MATLAB. CRC Press.

Goldberg, D.E., 1989. Genetic Algorithms in Search, Optimization and Machine Learning, Addison- Wesley.

Holland, J.H., 1992. Adaptation in Natural and Artificial Systems, MIT Press, Second Edition.


Refbacks

  • There are currently no refbacks.




Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Revista Publicando.

Licencia de Creative Commons

 

This Content is available under licencia de Creative Commons Reconocimiento-NoComercial-CompartirIgual 4.0 Internacional.