Cuando se utilizan algoritmos genéticos para resolver problemas de optimización de rutas de distribución, ¿cómo establecer la tasa de cruce y la tasa de mutación?
La siguiente es una respuesta detallada a la pregunta. El texto es un poco largo. Tenga paciencia y léalo.
El algoritmo puede resolver el problema de la optimización de la ruta de distribución logística. Sin embargo, dado que la operación del operador de apareamiento del algoritmo genético puede hacer que se pierda la mejor solución, el algoritmo genético y el algoritmo de recocido simulado se combinan para resolver este problema. Los resultados experimentales muestran que el uso de este algoritmo de recocido genético simulado con función de memoria para resolver el problema de optimización de la ruta de distribución logística puede resolver los problemas anteriores hasta cierto punto y obtener soluciones de mayor calidad.
Introducción al sistema logístico
El sistema logístico tiene como objetivo la satisfacción del cliente según los requerimientos del cliente, desde el sitio de producción hasta el sitio de venta, incluye almacenamiento, embalaje, distribución,. transporte, carga y descarga. Es un sistema complejo compuesto por el proceso de circulación de bienes físicos, servicios e información formado por la integración orgánica de otros eslabones.
La distribución logística es un eslabón importante en la gestión logística moderna. Se refiere a la actividad de clasificar y asignar mercancías en el centro de distribución de acuerdo con los requisitos de pedido del usuario y entregar las mercancías preparadas al destinatario de manera oportuna. Este artículo analiza el problema de optimización de rutas en la distribución logística y combina el algoritmo de recocido simulado para resolver las deficiencias de los algoritmos genéticos en la resolución de dichos problemas.
Diseño del modelo de sistema II
El problema de optimización de la ruta de distribución logística se puede describir de la siguiente manera: se utilizan múltiples vehículos de distribución para entregar mercancías a múltiples clientes desde un centro de distribución logística. La ubicación de cada cliente y la demanda de mercancías son determinadas, la capacidad de carga de cada vehículo es determinada, su tiempo de entrega es determinado y la distancia máxima de conducción para una entrega es determinada. Se requiere organizar razonablemente rutas de entrega de vehículos para optimizar la función objetivo. Y cumplir con las siguientes condiciones: (1) La suma de la demanda de cada cliente en cada ruta de entrega no excede la capacidad de carga del vehículo de entrega (2) La longitud de cada ruta de entrega no excede la distancia máxima de conducción del vehículo; vehículo de entrega para una entrega; (3) Los bienes entregados cada vez no pueden exceder el tiempo requerido por el cliente (4) Se deben satisfacer las necesidades de cada cliente y solo un vehículo de entrega puede entregar los bienes. Suponga que el centro de distribución necesita entregar bienes a k clientes, la demanda de bienes de cada cliente es g (i = 1, 2, ... k), la capacidad de carga de cada vehículo de entrega es q y g. establecimiento de este problema Modelo matemático: c representa el costo de transporte desde el punto i al punto j, y t representa el tiempo máximo permitido de i a s. El número del centro de distribución es 0 y cada número de cliente es i (i=1, 2,...,k). Las variables se definen de la siguiente manera:
x = 1 o 0 (donde, cuándo). x es igual a 1, significa que el vehículo s viaja de i a j; 0 significa que no existe tal camino).
y = 1 o 0 (donde, cuando y es igual a 1, significa que la tarea de carga en el punto i la completa el vehículo s; 0 significa que no).
El modelo matemático que se puede obtener en base a la definición de variable anterior es el siguiente:
min Z = (1)
= ; 1 o m ( Entre ellos, es 1 cuando i = 1, 2,..., k, de lo contrario es 0. ); (3)
= y, j = 1, 2,. .., k; s = 1 , 2,...,m; (4)
= y, i = 0, 1,...,k; .,m; (5)
t > 0; y t t , j = 1, 2..., s-1; (2) es la restricción de capacidad del vehículo; la ecuación (3) garantiza que la tarea de transporte de cada cliente se complete con un solo vehículo y que todas las tareas de transporte se completen con m vehículos en colaboración. Las ecuaciones (4) y (5) limitan la cantidad de automóviles que llegan; y dejar que un determinado cliente sea uno y solo uno. La ecuación (6) restringe el tiempo de entrega, es decir, el tiempo para que el artículo llegue al lugar designado no puede ser mayor que el tiempo máximo permitido.
El modelo anterior también debe considerar la cuestión del tiempo, es decir, cada cliente tiene diferentes requisitos de tiempo para los artículos entregados, por lo que es necesario agregar un parámetro de tiempo t. Se agrega un parámetro de tiempo t a cada ruta de transporte (el valor de t puede conocerse a partir de las necesidades del cliente y registrarse en la base de datos), y dentro de cada tiempo especificado (por ejemplo, un mes), se da prioridad a la entrega de artículos con un Valor t pequeño. Cada vez que se utiliza el algoritmo genético para resolver el problema, se recorren todas las t dentro del tiempo especificado, los cromosomas se organizan de pequeño a grande según el valor t, y luego se encuentra la solución óptima y la distribución. El plan se formula en base a la solución óptima.
En tercer lugar, se introduce el algoritmo de recocido para mejorar el proceso de solución.
En vista de algunas deficiencias del algoritmo genético, el algoritmo de recocido simulado se combina con él y se agrega un dispositivo de memoria. construir una solución para el problema de optimización de la ruta de distribución logística. Un algoritmo de recocido genético simulado con función de memoria. La característica de este algoritmo es que expande la vecindad de búsqueda del algoritmo genético original y acepta temporalmente algunas soluciones deterioradas bajo cierto control de probabilidad. Al mismo tiempo, el dispositivo de memoria se utiliza para garantizar que la solución final obtenida bajo ciertas condiciones de terminación sea al menos la solución óptima entre todas las soluciones obtenidas durante el proceso de búsqueda. Este algoritmo se obtiene añadiendo un operador de recocido simulado y un dispositivo de memoria al algoritmo genético convencional. Los pasos de este algoritmo de simulación genética con función de memoria se presentan primero a continuación. Según la referencia [3], se dan los siguientes pasos de implementación del algoritmo:
PASO 1 Dado el tamaño de la población maxpop, divida la población inicial en bloques de acuerdo con el valor especificado por t, k=0; = t, genere la población inicial pop (k), y cada bloque de la población inicial tiene un valor característico t que satisface un determinado atributo, calcule el valor objetivo f (i) para la población inicial y encuentre la función mínima f (; t) El cromosoma i y el valor de esta función f se registran como i =i, f =f donde f (t) es el valor objetivo del estado i cuando la temperatura es t; i∈ pop(k), es decir, un cromosoma en la población contemporánea;
PASO2 Si se cumple la condición final, detenga el cálculo y genere el cromosoma óptimo i y la solución óptima f; la población pop(k) Seleccione aleatoriamente un estado j∈N(i) de la vecindad de cada cromosoma i∈ pop(k), y t cumpla con los requisitos de la condición, acepte o rechace j según la probabilidad de aceptación en el recocido simulado. p>
, Entre ellos, f (t) y f (t) son los valores objetivo de los estados i y j respectivamente. En esta etapa, se requieren iteraciones de maxpop para seleccionar el nuevo grupo newpop1
PASO3 Calcular la función de aptitud en newpop1(k+1)
Donde, f es newpop1( El valor mínimo enk+1). La distribución de probabilidad determinada por la función de aptitud selecciona aleatoriamente los cromosomas maxpop de newpop1 para formar la población newpop2;
STEP4 utiliza el método convencional de algoritmo genético para cruzar newpop2 para obtener crosspop y luego mutar para obtener mutpop <; /p>
PASO 5 Si cada elemento del cromosoma satisface t y el elemento con un valor t mayor se completa sin destruir las condiciones requeridas para el cálculo con un valor t menor, no es necesario ordenarlo de pequeño a grande. Organice en orden,
PASO6 Sea pop(k+1)=mutpop, calcule f (t) para pop(k+1) y encuentre el cromosoma i que minimiza la función f (t) y este Función Valor f, si f < f, entonces sea i = i, f =f, t = d(t), k = k+1, regrese al PASO2.
Con el fin de lograr una expresión sencilla y un procesamiento informático conveniente, la codificación de números naturales se suele utilizar para la codificación de algoritmos genéticos de problemas de VRP. El vector solución del modelo matemático anterior se puede compilar en un cromosoma con una longitud de k+m+1 (0,i,i,…,i,0,i,…i,0,…0,i,…, i,0). En todo el cromosoma, el número natural i representa el j-ésimo cliente. El número de 0 es m + 1, que representa el centro de distribución, y el código de número natural se divide en m segmentos para formar m subrutas, lo que indica que m vehículos completan todas las tareas de transporte. Dicha codificación cromosómica se puede interpretar como: el primer vehículo parte del centro de distribución, pasa por i, i,...,i clientes y regresa al centro de distribución, formando el segundo vehículo que también parte de la distribución; center vía i ,...i los clientes luego regresan al centro de distribución, formando la subruta 2. m vehículos partieron en secuencia para completar todas las tareas de transporte, formando m subrutas.
Por ejemplo, el cromosoma 0123045067890 representa la disposición de la ruta de tres vehículos que completan las tareas de transporte de 9 clientes:
Subruta 1: Centro de distribución → Cliente 1 → Cliente 2 → Cliente 3 → Centro de entrega
Subruta 2: Centro de distribución→Cliente 4→Cliente 5→Centro de distribución
Subruta 3: Centro de distribución→Cliente 6→Cliente 7→Cliente 8→ Cliente 9→Centro de distribución.
Para que el algoritmo converja al óptimo global, la población genética debe tener una determinada escala. Sin embargo, para garantizar la eficiencia del cálculo, el tamaño del grupo no puede ser demasiado grande. Generalmente, el valor del tamaño del grupo está entre 10 y 100.
Al inicializar el cromosoma, primero genere una matriz completa de k clientes y luego inserte aleatoriamente m + 1 0 en la matriz. Los tiempos solicitados por los k clientes seleccionados deben estar en un momento específico. período, y completar la tarea de entrega para cualquier cliente no puede destruir las condiciones para completar la tarea de entrega para otros clientes. Cabe señalar que debe haber dos 0 dispuestos al principio y al final del arreglo, y no puede haber dos 0 consecutivos en el arreglo. Esto forma un cromosoma que satisface las necesidades del problema. Para este cromosoma, se seleccionan aleatoriamente elementos en dos posiciones para su intercambio y se utiliza un algoritmo para ajustarlos y convertirlo en un nuevo cromosoma que cumpla con los requisitos. Intercambie varias veces hasta que se generen cromosomas que cumplan con el tamaño de la población.
Aquí, la restricción de capacidad (2) se convierte en una parte del costo de transporte, y el costo de transporte se convierte en:
Donde M es un número positivo grande, lo que significa que cuando un vehículo Coeficiente de penalización cuando la capacidad de carga del vehículo supera su capacidad máxima de carga. M debería tender al infinito. Considerando el problema del procesamiento por computadora, consulte [6], es apropiado establecer M en 1000000. Sea esta función de costo de transporte nuestra función objetivo. La función de fitness utiliza una función de fitness acelerada:
Esta función de fitness tiene un mejor rendimiento de aceleración y puede mejorar rápidamente el valor de fitness y acortar el tiempo de ejecución del algoritmo.
Los cromosomas con mayor aptitud entre los cromosomas de cada generación se copian directamente y se introducen en la siguiente generación. Otros cromosomas de la población utilizan el método de la ruleta para producir descendencia según la distribución de probabilidad de su aptitud. Esto no sólo garantiza que los mejores puedan sobrevivir hasta la siguiente generación, sino que también garantiza que los cromosomas restantes puedan generar descendencia de acuerdo con el método de competencia de supervivencia, de modo que el algoritmo pueda converger al óptimo global. Los cromosomas seleccionados producen descendencia según una cierta probabilidad: tasa de cruce. La tasa de cruce está entre 0,6 y 0,8 y el efecto de evolución del algoritmo es mejor.
IV Datos experimentales y comparación
Los datos experimentales están tomados de la referencia [6].
Experimento 1, genera aleatoriamente un problema de VRP con 8 tiendas, los datos iniciales son los siguientes:
Figura 1 Demanda y ubicación de ocho tiendas
Basado en la demanda de cada almacén, calcule el número de coches necesarios: m=[17,82/(0,85*8)]+1=3. Se utilizó cada operador del algoritmo genético tradicional y se modificó el operador de cruce. El tamaño del grupo se estableció en 20 y el álgebra evolutiva en 50. Al aplicar este procedimiento, le tomó 3 segundos obtener el resultado: <. /p>
Nuestro algoritmo agrega un operador de recocido simulado al algoritmo anterior, toma la temperatura de recocido inicial como 10 y el coeficiente de atenuación como 0,85. Utilizando los pasos del algoritmo descritos en la Sección 3, se calcula en una computadora Pentium 4. , lo cual toma 2 segundos, y obtenemos Los resultados son los siguientes:
Experimento 2, generamos aleatoriamente un problema VRP con 20 tiendas, los datos iniciales son los siguientes:
Figura 2 Demanda y ubicación de 20 tiendas
Calculada: Se necesitan 6 vehículos. Utilice el algoritmo de la referencia [6] para establecer el tamaño de la población en 100 y establecer las generaciones evolutivas en 20, 50 y 100 respectivamente. Los resultados obtenidos son diferentes:
Figura 3 Resultados experimentales de genética ordinaria. algoritmos
Con el algoritmo de este artículo, la temperatura de recocido inicial es 10 y el coeficiente de atenuación es 0,85. Cuando se calcula en una computadora Pentium 4, los resultados son los siguientes:
Figura. 4 Resultados experimentales del nuevo algoritmo
Se puede ver en los dos experimentos anteriores que el uso del algoritmo descrito en este artículo puede acortar el álgebra evolutiva para obtener los mismos resultados, ahorrando así tiempo de cálculo. Aumentar el número de generaciones evolutivas conducirá inevitablemente a mejores resultados.
Cinco conclusiones
El uso del algoritmo de recocido simulado combinado con el algoritmo genético tradicional para resolver el problema de enrutamiento de vehículos en el sistema logístico puede reducir significativamente la cantidad de álgebra evolutiva requerida por el algoritmo. y el problema se podrá solucionar Encuéntralo en el menor tiempo. Por lo tanto, las características de tiempo mejoran mejor, el consumo de tiempo es más corto y se obtienen mejores resultados. Según los datos registrados en los materiales de referencia, este algoritmo es realmente factible y tiene un buen rendimiento en la resolución de problemas como los problemas de rutas de vehículos. Y a medida que aumenta el tamaño del problema, esta mejora en el rendimiento del tiempo se hará más evidente. Esto es muy útil para que las empresas de logística tomen decisiones logísticas científicas y efectivas basadas en sus propias condiciones reales, reduzcan riesgos, reduzcan costos y mejoren los beneficios económicos y su propia competitividad.
Referencias
[1] Guo Yaohuang y Li Jun, Programación de optimización de vehículos, Chengdu: Universidad de Ciencia y Tecnología de Chengdu, 1994
[2] Xing Wenxun y Xie Jinxing, ed. Modern Optimization Computational Methods, Beijing: Tsinghua University Press, 1999
[3] Lang Maoxiang, Investigación sobre modelos y algoritmos de problemas de programación de vehículos de distribución logística, Beijing: Northern Jiaotong University, 2002
[4] Lang Maoxiang y Hu Siji, Investigación sobre el uso de algoritmos genéticos híbridos para resolver el problema de optimización de rutas de distribución logística, Chinese Management Science, 2002
[5] Li Jun, Xie Binglei y Guo Yaohuang, Algoritmo genético para problemas de programación de vehículos no completos, Teoría y práctica de la ingeniería de sistemas, 2000
[6] Tang Kun, Diseño de algoritmos genéticos en problemas de rutas de vehículos, Journal of Northeastern University (Edición de Ciencias Naturales) ), 2002
[7] Jiang Dali, Yang Xilongdu Wen et al., Investigación sobre algoritmos genéticos para problemas de rutas de vehículos, Teoría y práctica de la ingeniería de sistemas, 1999
[8] Yan Qing y Bao Yuanlu, Nuevo algoritmo de recocido genético simulado para resolver problemas de enrutamiento de distribución logística, Ciencias de la Computación y Desarrollo, 2002