Utilice el algoritmo genético adaptativo basado en la búsqueda de particiones para resolver el problema de TSP
Jiang Jinlong, Xue Yuncan, Feng Jun
Para mejorar el uso de algoritmos genéticos para resolver el problema del viajante (TSP), combinados con ideas de optimización como operadores adaptativos y estrategias de competencia entre padres e hijos, se propone un algoritmo genético adaptativo basado en la búsqueda de particiones. Este algoritmo divide toda el área de búsqueda en varias áreas de búsqueda más pequeñas. Después de obtener la combinación de genes localmente óptima, primero realiza una búsqueda local y luego realiza una búsqueda de región completa no solo mejora la velocidad de convergencia del algoritmo genético, sino que también mejora el rendimiento operativo del operador de mutación. muestra que el algoritmo genético adaptativo basado en la búsqueda de particiones es un algoritmo de optimización estable y eficiente.
Afiliación del autor: Escuela de Ingeniería Informática y de la Información, Universidad de Hohai; de Ingeniería Informática y de la Información, Universidad Hohai, Changzhou, Jiangsu 213022 Escuela de Ingeniería Electrónica de Jiujiang; Jiangxi Jiujiang 332005; Jiangsu Changzhou 213022
Palabras clave: búsqueda de partición; p>
Financiamiento: Proyecto de la Fundación Provincial de Ciencias Naturales de Hubei (2004ABA018); Proyecto del Fondo de Innovación del Campus de Changzhou de la Universidad Hohai (2005B002-01)
Número de categoría: TP18
DOI: cnki :ISSN:1009-1130.0.2005-03 -001
Instantánea de texto:
1 La idea básica del algoritmo genético adaptativo de búsqueda de particiones El problema del viajante (TSP). significa que un viajante parte de una determinada ciudad y viaja a Después de atravesar N ciudades y luego regresar al punto de partida, y solo pasar por cada ciudad una vez, el problema de encontrar el itinerario más corto del viajante es un TSP. N P, y el número de rutas posibles aumenta exponencialmente a medida que aumenta el número de ciudades N. Si es un problema de TSP simétrico, hay ***0,5 (N-1) ¡Si es un problema de TSP asimétrico! , las posibles rutas se duplicarán. Muchos estudiosos utilizan diferentes métodos de control de algoritmos genéticos para resolver el TSP óptimo. La solución óptima [2-3], pero la velocidad de convergencia del algoritmo genético simple (SG A) es lenta. Es fácil caer en la solución óptima local si se pueden encontrar algunas combinaciones de genes excelentes localmente (... p>
Recomendar descargar CAJ en formato PDF
El lector CAJViewer7.0 admite todos los formatos de archivo CNKI y AdobeReader. solo admite formato PDF
Resolución del problema del viajante mediante el algoritmo genético adaptativo basado en la búsqueda regional
JIANG Jin-long1;2;XUE Yun-can1;FENG Jun1(1.College of Computer & Information Engineering;Hohai Univ.;Changzhou 213022;China;2.Facultad de Ingeniería Electrónica ;Jiujiang Univ.;Jiujiang 332005;China)
Para aumentar la velocidad de convergencia del algoritmo genético en la resolución de Problema del viajante (TSP), combinado con operadores adaptativos y estrategia competitiva entre padres e hijos, un algoritmo genético adaptativo.
Se propone un itmo basado en la búsqueda regional. Este algoritmo divide el espacio global en espacio regional y realiza la búsqueda regional primero. La búsqueda espacial global se lleva a cabo en función de las mejores secuencias de genes locales obtenidas de la búsqueda regional, para mejorar la calidad. Además, este algoritmo mejora el rendimiento de la mutación al mismo tiempo. Las simulaciones de TSP muestran que el algoritmo mejorado es un método de búsqueda óptimo constante y eficiente.
Palabra clave: algoritmos genéticos; problema(TSP)