Principio del algoritmo tSp Concorder
El algoritmo genético del problema tsp convierte múltiples objetivos en un solo objetivo de manera ponderada linealmente y luego utiliza el algoritmo genético tradicional para resolverlo
donde w_i representa el peso de i -ésimo objetivo, y f_k representa la regresión. El i-ésimo valor objetivo después de la normalización. Podemos saber fácilmente que la clave de este tipo de método es cómo diseñar las pesas. Por ejemplo, el algoritmo genético de peso aleatorio (RWGA) utiliza pesos aleatorios. Cada vez que se calcula la aptitud, se generan aleatoriamente diferentes pesos objetivo para todos los individuos y luego se realiza una operación de selección. El algoritmo genético evaluado por vectores (VEGA) es también un algoritmo genético multiobjetivo basado en ponderación lineal. Si hay K objetivos, VEGA dividirá aleatoriamente la población en K subpoblaciones de igual tamaño, establecerá valores objetivo en diferentes subpoblaciones de acuerdo con diferentes funciones objetivo y luego realizará la operación de selección. VEGA es esencialmente un algoritmo genético multiobjetivo basado en ponderación lineal. VEGA es el primer algoritmo genético multiobjetivo, que inició una tendencia de investigación durante más de diez años.
1. El problema del TSP se refiere a suponer que un empresario viajero quiere visitar n ciudades debe elegir el camino a tomar, la restricción del camino es que cada ciudad solo se puede visitar una vez, y en. Al final tiene que regresar a la ciudad de salida original. El objetivo de la selección de ruta es exigir que la distancia de la ruta sea el valor mínimo entre todas las rutas. Este artículo utiliza un algoritmo genético para resolver el problema att30, que es el problema del viajante de comercio en 30 ciudades. El problema del viajante es un problema clásico de optimización combinatoria. Un problema clásico del vendedor ambulante puede describirse como: un vendedor va a varias ciudades para vender productos. El vendedor parte de una ciudad y necesita pasar por todas las ciudades antes de regresar al punto de partida. ¿Cómo se debe elegir la ruta de viaje para que el viaje total sea el más corto? Desde la perspectiva de la teoría de grafos, la esencia de este problema es encontrar un ciclo de Hamilton con el peso más pequeño en un gráfico ponderado completamente no dirigido. Dado que la solución factible a este problema es la disposición total de todos los vértices, a medida que aumenta el número de vértices se producirá una explosión combinatoria y es un problema NP-completo. Los problemas de TSP se pueden dividir en simétricos y asimétricos. En el problema de TSP simétrico, la distancia de ida y vuelta entre las dos ciudades es igual, formando un gráfico no dirigido, mientras que el TSP asimétrico forma un gráfico dirigido. Los problemas de TSP simétricos pueden reducir el número de soluciones a la mitad. Por lo tanto, el problema de TSP en este experimento utiliza datos att48 y el paquete de datos se puede descargar en tsplib. El algoritmo evolutivo es un tipo de algoritmo biónico que simula las leyes de evolución genética de la naturaleza. No es un algoritmo específico, sino un conjunto de algoritmos. El algoritmo genético es una rama del algoritmo evolutivo. Dado que la estrategia de búsqueda general y el cálculo de optimización del algoritmo genético no dependen de la información de gradiente, se utiliza ampliamente. También utilizamos un algoritmo genético (escrito en MATLAB) para resolver el problema de TSP en este experimento.