Resumen

Para el problema de trazado de la red de carreteras rurales, que a menudo se caracteriza por un conglomerado de nodos geográficamente dispersos, no pueden aplicarse fácilmente ni el algoritmo de Prim ni el algoritmo de Kruskal, porque la velocidad de cálculo y la precisión no son en absoluto satisfactorias. En lugar de estos dos algoritmos polinómicos y del algoritmo genético tradicional, este artículo propone un algoritmo genético mejorado. Codifica los árboles de expansión mínima del trazado de redes de carreteras rurales a gran escala con la matriz de Prufer, un método que puede reducir la longitud del cromosoma; descodifica la matriz de Prufer utilizando un algoritmo eficiente con una complejidad temporal o(n) y adoptando el método de transposición simple y el método de intercambio de ortoposiciones, que sustituyen a las operaciones tradicionales de cruce y mutación, lo que puede superar eficazmente la prematuridad del algoritmo genético. Las pruebas de simulación por ordenador y el estudio de casos confirman que el algoritmo genético mejorado es mejor que el tradicional.

• Materias:Matemáticas Análisis Matemático Álgebra Ingeniería Lógica matemática
• Subjects:mathematics Mathematical Analysis Algebra Engineering Mathematical logic
• Palabras claves:prufer array, algoritmo genético, trazado de red de carreteras rurales, pruebas de simulación por ordenador, algoritmo genético mejorado, método de intercambio de ortoposiciones, red de carreteras rurales, método de transposición única, complejidad temporal o(n, algoritmo genético tradicional
• Keywords:prufer array, genetic algorithm, rural highway network layout, computer simulation tests, improved genetic algorithm, orthoposition exchange method, rural highway network, single transposition method, time complexity o(n, traditional genetic algorithm