| Nodo | Vecinos |
|---|---|
| 1 | 2,8 |
| 2 | 1,3 |
| 3 | 2,4 |
| 4 | 3,5 |
| 5 | 4,6 |
| 6 | 5,7 |
| 7 | 6,8 |
| 8 | 7,1 |
Genetic algorithm
Introducción.
Los algoritmos genéticos son metaheurísticas de optimización inspiradas en los principios de la evolución biológica formalizados por John Holland en los años 70.
Se basan en tres mecanismos fundamentales:
- Selección natural
- Recombinación genética
- Mutación
El objetivo es aproximar soluciones óptimas en espacios de búsqueda grandes, discretos y no convexos.
1. Formalización del problema
Sea un problema de optimización:
\[ \underset{x \in S}{min}~~f(x) \]
Donde:
- \(S\): espacio de soluciones (posiblemente combinatorio)
- \(f(x)\): función objetivo
Un Algoritmo genético transforma este problema en:
- Búsqueda sobre una población \(P_t \subset S\)
- Evolución iterativa \(P_t \rightarrow P_{t+1}\)
2. Representación (Codificación)
La codificación define cómo representas una solución candidata (individuo/cromosoma). Elegir bien la representación no es un detalle menor: condiciona directamente qué operadores genéticos se pueden usar y qué tan eficiente será la búsqueda.
La codificación define cómo se representa una solución:
Binaria:
El cromosoma es un vector de bits:
Ejemplo:
\[ x= (0,1,1,0,1) \]
En general:
\[ x= (b_1, b_2,..., b_n);~ b_i \in \{0,1 \} \]
Cada gen representa una característica codificada en binario. Hay dos casos típicos:
- Variables discretas
Ejemplo:
- Problema de selección:
\[ x= (1,0,1,0,1) \]
Se seleccionan elementos \(1,3\) y \(5\)
- Variables continuas:
Un bloque de bits representa un número real.
Ejemplo:
- \(8\) bits: número entre \([a, b]\)
- Conversión:
\[ x= a + \frac{Valor~binario}{2^{k}-1} (b-a) \]
Operadores típicos
- Cruce (crossover):
- \(1\) punto.
- \(2\) puntos.
- Uniforme
- Mutación:
- Flip de bit \((0 \rightarrow 1, 1 \rightarrow 0)\)
Ventajas y desventajas
- Simple y universal
- Fácil implemetación
- Baja precisión para variables realies -No resulta natural para muchos problemas.
Se suele usar en problemas combinatorios simples o en problemas de selección como el problema de la mochila o selección de características
Real (o contínua)
El cromosoma es un vector de números reales:
Ejemplo:
\[ x = (2.3, 5.1, -12) \]
En general:
\[ x = (x_1,x_2,...,x_n);~ x_i \in \mathbb{R} \]
Cada gen es directamente una variable del problema.
Operadores típicos
- Cruce
- Aritmétic: \[hijo= \alpha x^{(1)} + (1-\alpha) x^{2}\]
- BLX-\(\alpha\) (Blend crossover)
- SBX (simulated binary crossover)
- Mutación
- Gaussiana: \[x^{'}_i = x_i + N(0, \sigma^2)\]
- Uniforme dentro de un rango
Ventajas y desventajas
- Representación natural para optimización continua
- Mayor precisión
- Convergencia más suave
- Requiere operadores especializados
- Puede perder diversidad rápidamente
- Menos soporte teórico clásico que la binaria
Se suele usar en optimización continua, ajuste de parámetros y Machine learning (hiperparámetros, modelos)
Permutacional (usada en VRP):
El cromosoma es una permutación de elementos:
\[ x = (5,2,8,1,3) \]
Cada elemento aparece una sola vez, en general:
\[ x = (p_1, p_2, ... , p_n) \]
Representa un orden o secuencia (típico en problemas de rutas).
No se pueden usar operadores estándar o clásicos (rompen la permutación), por ejemplo, cruzar dos padres puede generar duplicados o perder elementos (vertices).
Operadores especializados
- Cruce
- PMX (partially mapped crossover)
- OX (order crossover)
- CX (cycle crossover)
- Mutación
- Swap
- Insertion
- Inversión
Ventajas y desventajas
- Representación natural para problemas de orden
- Mantiene factibilidad (si se usa bien)
- Operadores más complejos
- Espacio de búsqueda muy grande
Se suele usar para:
- TSP
- VRP
- Scheduling
3. Población
En la iteración \(t\):
\[ P_t = \{x_1,x_2,...,x_N \} \]
Donde:
- \(N\): tamaño poblacional
- Cada individuo es una solución candidata
La Diversidad Poblacional alta facilita la exploración, la Diversidad Poblacional baja facilita la explotación.
4. Función fitness
La función fitness una función que asigna a cada individuo (solución candidata) un valor numérico que mide su calidad:
\[ f: X \rightarrow \mathbb{R} \]
Donde:
- \(X\): espacio de soluciones.
- \(f(x)\): calidad de la solución \(x\)
La función fitness le dice al algoritmo qué tan buena es una solución. Guia el proceso evoluctivo:
- Evalúa cada individuo.
- Determina quién se reproduce (selección)
- Presiona la solución hacia mejores soluciones.
Sin función fitness, un algoritmo genético funciona como una búsqueda aleatoria. Existen muchos tipos de función fitness.
Para problemas de maximización:
Para problemasde maximización la función fitness se puede expresar como:
\[ fitness(x) = f(x) \]
Problemas de minimización
Se transforma la función fitness:
- Inversa:
\[ fitness(x) = \frac{1}{1+f(x)} \]
- Negativa:
\[ fitness(x) = -f(x) \]
5. Selección
La selección en un algoritmo genético es el mecanismo que decide quién se reproduce y, por tanto, qué información genética pasa a la siguiente generación. La selección implementa el principio de “supervivencia del más apto”, aunque, no siempre gana el mejo, solo tiene mayor probabilidad de ser elegido.
En cada generación:
- Se evalúa el fitness.
- Seleccionar individuos.
- Aplican cruce y mutación
La selección conecta fitness con reproducción. Existen varios métodos de selección:
Selección por ruleta
La probabilidad de selección \(P(x_i)\) es proporcional al fitness
\[P(x_i) = \frac{f(x_i)}{\sum_j f(x_j)}\]
En un proceso simple que usa directamente la función \(fitness\), sin embargo, si existe un individuo muy dominante monopoliza la población y si los individuos son muy parecidos, la selección será casi aleatoria.
Selección por torneo
Se toman \(k\) individuos al azar, se selecciona (gana) el mejor. Es una forma de selección bastante robusta, fácil de implementar y no depende de la escala del fitness.
Selección elitista.
Los mejores individuos pasan directamente a la siguiente generación. Este método garantiza que no se pierda la mejor solución, pero, puede reduccir la diversidad.
6. Cruce (crossover).
Dados dos padres \(x^{(1)}\) y \(x^{(2)}\) el cruce produce uno o más hijos:
\[ h= Crossover(x^{(1)}, x^{(2)}) \]
El cruce se fundamenta en el principio Building Blocks:
- Buenas soluciones están formadas por subestructuras útiles.
- El cruce intenta preservar esas subestructuras y combinarlas.
El cruce introduce variación dirigida, explota información existente y trabaja junto con la muitación apra introducir rudio/innovación. Sin cruce el algoritmo genético se comporta como una búsqueda aleatoria con mutuación.
Existen muchos tipos de cruce, a continuación se muestran algunos según la codificación.
Cruce en codificación binaria.
Cruce de un punto.
Se elige una posición \(k\):
\[\begin{align} x^{(1)} = (1,0,1 | 1,0)\\ x^{(2)} = (0,1,0 | 0,1) \end{align}\]
El cruce produce los siguientes hijos:
\[ (1,0,1,0,1);~(0,1,0,1,0) \]
Cruce de dos puntos
Se intercambia un segmento intermedio. Se elegin dos posiciones \(k_1\) y \(k_2\):
\[\begin{align} x^{(1)} = (1,1,0 |1,0,1,0|1,1)\\ x^{(2)} = (0,0,1 |0,1,1,1|0,0) \end{align}\]
El cruce produce los siguientes hijos:
\[ (1,1,0,0,1,1,1,1,1);~~(0,0,1,1,0,1,0,0,0) \]
Se busca:
- Combinar características útiles de ambos padres
- Preservar bloques de información genética
- Explorar nuevas regiones del espacio de búsqueda.
Cruce uniforme
Cada gen se elige aleatoriamente de uno de los padres, no se intercambian bloques completos sino genes individuales, usando la siguiente función:
\[ h_i = \left\{ \begin{array}{lcc} x_i^{(1)} &\text{con prob.}~~0.5\\ \\x_i^{(2)} &\text{con prob.}~~0.5 \\ \end{array} \right. \]
En este cruce:
- Cada gen compite individualmente.
- No se preservan bloques consecutivos.
- La mezcla genética es mucho más agresiva.
- Produce alta diversidad.
- Existe menos conservación estructural.
Cruce en codificación real
En los algoritmos genéticos con codificación real, los cromosomas no están formados por bits, sino por números reales. Por ejemplo:
\[ x = (2.5,7.1,-1.3,4.8) \]
Cada gen representa un valor numérico de una variable de decisión. En este sentido el operador de cruce ya no intercambia bits, sino que combina valores numéricos de los padres para generar los hijos.
Cruce aritmético
Dados dos padres \(x^{(1)}\) y \(x^{(2)}\), los hijos se generan mediante combnación lineal:
\[\begin{align} H_1 &= \alpha x^{(1)} + (1-\alpha)x^{(2)}\\ H_2 &= (1-\alpha) x^{(1)} + \alpha x^{(2)} \end{align}\]
Donde \(0 \le \alpha \le 1\)
En codificación real:
- Cada solución es un punto en el espacio.
- El cruce genera puntos entre los padres.
Por lo anterior, suele verse como:
- Interpolación
- Mezcla continua
- Exploración del espacio numérico.
BLX - (Blend Crossover)
En lugar de generar hijos solo entre los padres, permite explorar fuera de los intervalos determinados por los padres usando las siguientes ecuaciones.
Para cada gen:
\[ x_i \sim U[L_i, U_i] \]
Dónde:
\[\begin{align} L_i &= min(x_{1i}, x_{2i}) - \alpha d_i\\ \\ U_i &= max(x_{1i}, x_{2i}) + \alpha d_i \end{align}\]
y
\[ d_i = |x_{1i} - x_{2i}| \]
\[ 0 \le \alpha \le 1 \]
Este método ofrece una exploración más amplica, permite escapar de óptimos locales y genera soluciones fuera del rango parental.
Cruce en codificación permutacional
En los algoritmos genéticos con codificación permutacional, cada cromosoma representa un ordenamiento válido de elementos. Este tipo de representación aparece en problemas donde el orden es fundamental. Lo anterior presenta dificultad para los operadores pues, en general, ningún elemento puede repetirse, ningún elemento puede faltar y el orden debe conservar sentido. Los cruces tradicionales no suelen funcionar, se usan operadores de cruce específicos.
En un cruce permutacional, dependiendo el problema se intenta preservar distitas propiedades estructurales:
Posiciones: mantener ciertos elementos en ubicaciones similares, como por ejemplo: una tarea debe seguir siendo de las primeras, una ciudad debe mantenerse cerca del inicio de la ruta.
Orden relativo: mantener la secuencia entre elementos. Por ejemplo: \((4,7,2)\), significa que \(4\) ocurre antes que \(7\) y \(7\) antes que \(2\), aunque cambien de posición absoluta, el orden relativo se conserva.
Adyacencias: mantener vecinos consecutivos. Por ejemplo: \((5,8)\), aparecen juntos en buenas soluciones.
Partially Mapped Crossover (PMX)
PMX es uno de los cruces más conocidos en problemas con codificación permutacional. Pretende preservar la información posicional. Esto es, ciertos genes conservan posiciones parecidas, se preserva parte de la estructura absoluta del cromosoma. El procedimiento general del PMX es:
- Seleccionar dos puntos de corte.
- Intercambiar el segmento interno.
- Construir un mapeo de genes.
- Reparar duplicados mediante el mapeo
Ejemplo PMX
- Dados los siguientes padres:
\[\begin{align} x^{(1)}=(1,2,3,4,5,6,7,8) \\ \\ x^{(2)}=(5,7,2,1,8,4,6,3) \end{align}\]
Puntos de corte: \([3,6]\)
Segmentos seleccionados
- Del padre 1: \((3,4,5,6)\)
- Del padre 2: \((2,1,8,4)\)
Construcción inicial: se copia el segmento del padre 1:
\[\begin{align} h=(\_,\_,3,4,5,6,\_,\_) \end{align}\]
- Mapeo:
\[\begin{align} 3 \leftrightarrow 2\\ 4 \leftrightarrow 1\\ 5 \leftrightarrow 8\\ 6 \leftrightarrow 4 \end{align}\]
Se intenta completar el hijo \(h\) usando los genes del padre \(2\). Los genes de \(x^{(2)}\) a utilizar serían en su orden \(5,7,6,3\) pero se repetirían: \(5, 6, 3\) por lo que se usa el mapeo obteniendo:
\[ h = (8,7,3,4,5,6,1,2) \]
PMX preserva:
- Posiciones.
- Relaciones localizadas.
- Estructura parcial.
Order crossover (OX)
OX suele ser un operador de cruce más popular para problemas de secuenciación y rutas. OX busca preservar el orden relativo, por lo cual no interesa conservar posición exacta, lo importante es conservar secuencias útiles. El procedimiento general de OX es:
- Copiar segmento de un padre.
- Recorrer el otro padre circularmente.
- Insertar los elementos faltantes respetando el orden.
Ejemplo OX
- Dados los siguientes padres:
\[\begin{align} x^{(1)}=(1,2,3,4,5,6,7,8) \\ \\ x^{(2)}=(5,7,2,1,8,4,6,3) \end{align}\]
Puntos de corte: \([3,5]\)
Construcción inicial: se copia el segmento del padre 1:
\[\begin{align} h=(\_,\_,3,4,5,\_,\_,\_) \end{align}\]
- Recorrido circular del padre \(2\), se comienza después del corte \(2\):
\[ (4,6,3,5,7,2,1,8) \]
Si se eliminan los repetidos quedan:
\[ (6,7,2,1,8) \]
- Construcción final:
\[ h =(6,7,3,4,5,2,1,8) \]
OX preserva:
- Subsecuencias
- orden relativo
- Patrones secuenciales
Cycle crossover (CX)
Tiene una lógica algo más matemática buscando preservar las relaciones posición-elemento mediante ciclos. Cada posición del hijo proviene completamente de uno de los padres, para lograrlo:
- Cada posición del hijo proviene completamente de uno de los padres,
- Usando ciclos de correspondencia entre ambos cromosomas.
Ejemplo CX
- Dados los siguientes padres:
\[\begin{align} x^{(1)}=(1,2,3,4,5,6,7,8) \\ \\ x^{(2)}=(2,1,4,3,6,5,8,7) \end{align}\]
- Construcción de ciclos: ciclo 1
Posición \(1\)
\[ x^{(1)}(1) = 1 \]
Buscar \(1\) en \(x^{(2)}\) Está en posición \(2\)
Posición \(2\)
\[ x^{(1)}(2) = 2 \]
Buscar \(2\) en \(x^{(2)}\) Está en posición \(1\)
Ciclo cerrado entonces:
\[ Ciclo_1 = (1,2) \]
- Construcción de ciclos: ciclo 2
Posición \(3\)
\[ x^{(1)}(3) = 3 \]
Buscar \(3\) en \(x^{(2)}\) Está en posición \(4\)
Posición \(4\)
\[ x^{(1)}(4) = 4 \]
Buscar \(4\) en \(x^{(2)}\) Está en posición \(3\)
Ciclo cerrado entonces:
\[ Ciclo_2 = (3,4) \]
- Construcción de ciclos: ciclo 3
Posición \(5\)
\[ x^{(1)}(5) = 5 \]
Buscar \(5\) en \(x^{(2)}\) Está en posición \(6\)
Posición \(6\)
\[ x^{(1)}(6) = 6 \]
Buscar \(6\) en \(x^{(2)}\) Está en posición \(5\)
Ciclo cerrado entonces:
\[ Ciclo_3 = (5,6) \]
- Construcción de ciclos: ciclo 4
Posición \(7\)
\[ x^{(1)}(7) = 7 \]
Buscar \(7\) en \(x^{(2)}\) Está en posición \(8\)
Posición \(8\)
\[ x^{(1)}(8) = 8 \]
Buscar \(8\) en \(x^{(2)}\) Está en posición \(7\)
Ciclo cerrado entonces:
\[ Ciclo_4 = (7,8) \]
- Construcción final del hijo: regla de alternancia
- Ciclo \(1\) \(\rightarrow\) \(x^{(1)}\)
- Ciclo \(2\) \(\rightarrow\) \(x^{(2)}\)
- Ciclo \(3\) \(\rightarrow\) \(x^{(3)}\)
- Ciclo \(4\) \(\rightarrow\) \(x^{(4)}\)
Por lo tanto, el hijo resultante es:
\[ h =(1,2,4,3,5,6,8,7) \]
CX preserva:
- Relaciones posición-elemento.
- Consistencia estructural.
- Correspondencia internas.
No produce:
- Duplicados.
- Faltantes.
- Soluciones no válidas.
Edge recombination crossover (ERX)
ERX trata de preservar adyacencias, esto es por ejemplo, si dos ciudades aparecen conectadas frecuentemente, el operador intentará mantener esa conexión. El funcionamiento es el siguiente:
- Construir lista de vecinos.
- Identificar conexiones compartidas.
- Generar rutas preservando esas conexiones.
Ejemplo ERX
- Dados los siguientes padres:
\[\begin{align} x^{(1)} &=(1,2,3,4,5,6,7,8,1) \\ \\ x^{(2)}&= (1,4,8,6,2,3,5,7,1) \end{align}\]
- Construir tabla de adyacencias:
Para padre \(1\)
\[ x^{(1)} =(1,2,3,4,5,6,7,8,1) \]
Para padre \(2\)
\[ x^{(2)} =(1,4,8,6,2,3,5,7,1) \]
| Nodo | Vecinos |
|---|---|
| 1 | 4,7 |
| 2 | 6,3 |
| 3 | 2,5 |
| 4 | 1,8 |
| 5 | 3,7 |
| 6 | 8,2 |
| 7 | 5,1 |
| 8 | 4,6 |
- Construir tabla combinada
Se unen los vecinos de ambos padres:
| Nodo | Vecinos |
|---|---|
| 1 | 8,2,7,4 |
| 2 | 1,3,6 |
| 3 | 2,4,5 |
| 4 | 3,5,1,8 |
| 5 | 4,6,3,7 |
| 6 | 5,7,8,2 |
| 7 | 6,8,5,1 |
| 8 | 7,1,4,6 |
- Elegir nodo inicial.
Usualmente:
- Aleatorio.
- El primero de uno de los padres.
Supongamos \(1\), entonces el hijo comienza como:
\[ h = (1) \]
- Eliminar nodo usado de tabla combinada
| Nodo | Vecinos |
|---|---|
| 2 | 3,6 |
| 3 | 2,4,5 |
| 4 | 3,5,8 |
| 5 | 4,6,3,7 |
| 6 | 5,7,8,2 |
| 7 | 6,8,5 |
| 8 | 7,4,6 |
- Elegir el siguiente nodo
Como Regla del ERX se selecciona el vecino cuya lista sea más pequeña, los vecinos del nodo \(1\) son: \(8,2,7,4\)
Los tamaños de lista son:
| Nodo | Tamano |
|---|---|
| 8 | 3 |
| 2 | 2 |
| 7 | 3 |
| 4 | 3 |
El menor tamaño de lista es \(2\) y lo tiene el nodo \(2\), por lo que el hijo parcial sería:
\[ h = (1,2) \]
Se debe repetir desde el numeral \(4\).
Ademas de los cruces mencionados corresponden al Position Based Crossover (PBX) y el Order bases Crossover (OBX). PBX Selecciona posiciones específicas del primer padre y completa usando el orden del segundo, tratando de preservar posiciones clave. OBX selecciona ciertos elementos y reorganiza el hijo siguiendo el orden relativo del otro padre tratando de preservar el orden parcial y las subsecuencias.
7 Mutación
La mutación corresponde a uno de los operadores fundamentales en algoritmos genéticos, mientras el cruce combina información existente, la mutación introduce nueva información genética. La función de la mutación corresponde a:
- Mantener diversidad,
- Evitar convergencia prematura,
- Explorar regiones nuevas,
- Escapar de óptimos locales.
Mutación en codificaicón binaria.
Como en codificación binaria cada cromosoma es una cadena de bits:
\[ x = (x_1,x_2,..., x_n) \]
Donde \(x_i \in \{ 0,1 \}\)
La mutación consiste en alterar bits individuales para introducir diversidad genética.
Mutación Bit-Flip
Es la mutación clásica de los algoritmos genéticos binarios, las ideas es extremadamente simple:
\[ 0 \leftrightarrow 1 \]
Cada gen tiene una probabilidad \(P_m\) de invertirse. Matemáticamente es:
Sea:
\[ x_i \in \{0,1 \} \]
Entonces:
\[ x_i' = 1-x_i \]
Probabilidad de mutación
Normalmente la probabilidad de mutación:
\[ P_m \in [0.001, 0.05] \]
A menudo se usa:
\[ P_m = \frac{1}{L} \]
\(L\) es la longitud del cromosoma
Mutación para codificación real
Como en codificación real:
\[ x = (x_1,x_2,...x_n) \]
Con \(x_i \in \mathbb{R}\).
La mutación pretende alterar valores enteros continuos, controlando:
- Maginitud de la perturbación
- Exploración
- Estabilidad.
Mutación uniforme
Consiste en reemplazar un gen \(x_i\) por un valor aleatorio uniforme:
Si:
\[ x_i \in [a_i, b_i] \]
Entonces:
\[ x_i' \sim U(a_i, b_i) \]
La mutación ignora el valor previo y produce exploración agresiva, lo que causa exploración global y permite escapar de óptimos locales. Lo anterior también hace a esta mutación algo destructiva y puede eliminar soluciones prometedoras.
Mutación gaussiana
La mutación de este tipo agrega ruído gaussiano:
\[ x_i' = x_i + \epsilon \]
Donde: \(\epsilon \sim N(0, \sigma^2)\).
Lo anterior implica mutaciones pequeñas muy probables y mutaciones grandes poco probables.
\(\sigma\) controla la intensidad mutacional, un \(\sigma\) pequeño produce refinamiento local y explotación, un \(\sigma\) grande produce exploración fuerte y saltos amplios.
Mutación para codificación permutacional
Al igual que el cruce, en codificación permutacional el reto de la mutación corresponde a mantener la factibilidad, sin que existan repetidos o faltantes.
Mutación SWAP.
Consiste en intercambiar dos posiciones o dos genes:
Ejemplo
Cromosoma original: \((1,2,3,4,5,6)\)
Intercambiar posiciones \(2\) y \(5\)
Mutación: \((1,5,3,4,2,6)\)
La estructura global cambia poco, es una mutación bastante simple, poco destructiva y mantiene, generalmente, factibilidad; sin embargo, la exploración es limitada.
Mutación por inserción (relocalización)
Consiste en extraer un elemento o gen e insertarlo en otra posición.
Ejemplo
Cromosoma original: \((1,2,3,4,5,6)\)
Extraer \(3\) e insertarlo después de 5.
Mutación: \((1,2,4,5,3,6)\)
Esta mutación preserva gran parte del orden relativo.
Mutación por inversión
Esta mutacióon invierte una subsecuencia.
Ejemplo
Cromosoma original: \((1,2,3,4,5,6)\)
Se invierte la subsecuencia: \((3,4,5,6)\)
Mutación: \((1,2,6,5,4,3)\)
Mutación Scramble
Selecciona una subsecuencia y lo reordena aleatoriamente.
Ejemplo
Cromosoma original: \((1,2,3,4,5,6)\)
Segemento: \((3,4,5,6)\)
Reordenamiento: \((5,3,6,4)\)
Mutación: \((1,2,5,3,6,4)\)
Es un tipo de mutación exploratoria, introduce diversidad explorando combinaciones locales.
Ejemplo Algoritmo Genético para problema VRP en R
Durante las jornadas electorales en el Departamento de Córdoba, la Registraduría Nacional del Estado Civil debe realizar la recolección del material electoral sensible (urnas, formularios, actas y votos físicos) desde todos los municipios hacia el centro de consolidación ubicado en Montería.
Este proceso debe efectuarse inmediatamente después del cierre de las mesas de votación, debido a que:
El material es confidencial y de alto valor legal.
Debe llegar lo más rápido posible al centro de cómputo departamental.
Se busca minimizar riesgos de pérdida, manipulación o retrasos.
Los recursos de transporte y seguridad son limitados.
Para esta operación se dispone de una flota de \(12\) vehículos oficiales escoltados, cada uno con capacidad máxima de \(1.5\) toneladas, los cuales parten desde Montería, visitan un subconjunto de municipios para recolectar el material electoral y posteriormente regresan al centro de consolidación.
Cada municipio genera una cantidad estimada de material electoral (expresada en peso o número de cajas), por lo que la asignación de municipios a cada vehículo debe respetar la capacidad máxima de transporte. El peso del material electoral por municipio se encuentra disponible en el siguiente enlace: Peso de material electoral por municipio.
Adicionalmente, se dispone de una matriz de distancias en kilómetros entre municipios: Matriz de distancias en km.
Actualmente, las rutas se planifican de forma empírica, lo que genera:
mayores distancias recorridas,
incremento en los tiempos de consolidación de resultados,
mayores costos de combustible,
y mayores riesgos de seguridad por recorridos innecesarios.
En consecuencia, se requiere diseñar un modelo de ruteo de vehículos capacitado (Vehicle Routing Problem, VRP) que permita determinar:
qué municipios debe atender cada vehículo,
el orden óptimo de visita en cada ruta,
y minimizar la distancia total recorrida por la flota.
Datos
library(readxl)
library(dplyr)
#Se lee el archivo de Excel que contiene la matriz de distancias entre municipios
distancias_df<- read_excel("distancias_municipios_cordoba.xlsx")
#Matriz de distancias
municipios <- distancias_df[[1]] #Extraer la primera columna que contiene los nombres de los municipios
D <- as.matrix(distancias_df[,-1]) #Construir la matriz de distancias eliminando la primera columna
rownames(D) <- municipios #Asignar nombres de filas y columnas a la matriz
colnames(D) <- municipios
#dataframe de demandas
demandas_df <- read_excel("demanda.xlsx")
#Matriz de demanda
demandas <- demandas_df$demanda #Crear vector de demandas
names(demandas) <- demandas_df$Municipio #Asignar nombres al vector de demandas para acceder por municipio
#Capacidad del vehículo (toneladas)
Q <- 1.5
#Nodo depósito (punto de origen y regreso de las rutas)
deposito <- "Monteria"
#Tamaño de flota (Número máximo de vehículos disponibles)
K <- 12SPLIT para factibilidad del VRP
Este código implementa un procedimiento conocido como SPLIT dentro de un Algoritmo Genético para el problema de ruteo de vehículos o VRP.
La idea principal es:
- El algoritmo genético normalmente trabaja con una secuencia global de clientes (un cromosoma).
- Pero en un VRP no basta con el orden de clientes; también hay que decidir:
- dónde termina una ruta,
- cuándo un vehículo regresa al depósito,
- y garantizar que no se exceda la capacidad del vehículo.
Entonces, esta función toma una secuencia de clientes y la “parte” en rutas factibles respetando la capacidad \(Q\).
#Función para el SPLIT
split_rutas <- function(secuencia, demandas, Q, deposito){
rutas <- list() # Lista vacía para almacenar todas las rutas construídas
ruta_actual <- c(deposito) # Se inicializa la ruta actual comenzando en el depósito.
carga <- 0 #Variable que almacena la carga acumulada del vehículo actual, inicialmente el vehículo está vacío.
for(cliente in secuencia){ #Se recorre cada cliente del cromosoma en el orden dado por el algoritmo genético.
if(carga + demandas[cliente] <= Q){ #Se verifica si el cliente puede agregarse a la ruta actual sin exceder la capacidad del vehículo.
ruta_actual <- c(ruta_actual, cliente) #Se agrega el cliente a la ruta actual.
carga <- carga + demandas[cliente] #Se actualiza la carga acumulada del vehículo.
} else {
ruta_actual <- c(ruta_actual, deposito) #Si supera la carga, se cierra la ruta agregando el depósito al final.
rutas[[length(rutas)+1]] <- ruta_actual #La ruta terminada se guarda en la lista de rutas.
ruta_actual <- c(deposito, cliente) #Se inicia una nueva ruta:
carga <- demandas[cliente] #La carga del nuevo vehículo ahora es igual a la demanda del cliente recién agregado.
}
}
ruta_actual <- c(ruta_actual, deposito) #La última ruta todavía no había sido cerrada, aquí se agrega el depósito al final.
rutas[[length(rutas)+1]] <- ruta_actual #Se guarda la última ruta construida.
return(rutas) #La función devuelve todas las rutas factibles.
}Función de costo
Necesario para el fitness, corresponde a la función objetivo.
#Función costo total
costo_total <- function(rutas, D){
total <- 0 #Variable acumuladora del costo total
for(r in rutas){ #Se recorren todas las rutas
for(i in 1:(length(r)-1)){ #Se recorren los arcos consecutivos de la ruta
total <- total + D[r[i], r[i+1]] #Se suma la distancia entr nodo actual y nodo siguiente
}
}
return(total) #La función devuelve el costo total de la solución
}Función fitness
Esta función define el fitness de un individuo dentro del VRP resuelto mediante un algoritmo genético.
Es una función central porque conecta:
- la representación genética (cromosoma),
- la factibilidad del VRP,
- y la calidad de la solución.
En otras palabras:
Esta función transforma una secuencia de clientes en una medida numérica de “qué tan buena” es la solución.
fitness <- function(secuencia, D, demandas, Q, deposito){
rutas <- split_rutas(secuencia, demandas, Q, deposito) #Convierte la secuencia del cromosoma en rutas factibles. Función anterior
return(1 / costo_total(rutas, D)) #Se calcula el fitness final. Usa función costo anterior
}Población inicial
Esta función construye la población inicial del algoritmo genético aplicado al VRP.
La población inicial es extremadamente importante porque representa:
- el punto de partida de la evolución,
- la diversidad genética inicial,
- y el espacio inicial de exploración del algoritmo.
En términos biológicos, la población inicial corresponde a la “primera generación” de individuos. Cada individuo es un posible orden de visita de clientes.
#Función para generar la población
generar_poblacion <- function(n_pob, clientes){
poblacion <- list() #Se crea una lista vacía donde se almacenarán todos los individuos
for(i in 1:n_pob){ #Se inicia un ciclo para generar todos los individuos de la población.
poblacion[[i]] <- sample(clientes) #Genera una permutación aleatoria de los clientes.
}
return(poblacion) #La función devuelve la población completa.
}Selección por torneo
Esta función implementa el operador de selección por torneo dentro de un algoritmo genético aplicado al VRP
La selección es uno de los componentes más importantes del AG porque determina:
- qué individuos sobreviven,
- cuáles tendrán descendencia,
- y cómo se transmite la información genética entre generaciones.
En términos evolutivos:
La selección implementa el principio de “supervivencia del más apto”.
#Función de selección
seleccion_torneo <- function(poblacion, D, demandas, Q, deposito, k=3){ #k valor por defecto, número de individuos del torneo
candidatos <- sample(1:length(poblacion), k) #Se seleccionan aleatoriamente k individuos
fit <- sapply(poblacion[candidatos], #Se calcula el fitness de todos los candidatos.
fitness,
D, demandas, Q, deposito)
return(poblacion[[candidatos[which.max(fit)]]])#Se selecciona el ganador del torneo.
}Cruce OX
crossover_OX <- function(p1, p2){
n <- length(p1)
puntos <- sort(sample(1:n, 2))
i <- puntos[1]
j <- puntos[2]
hijo <- rep(NA, n)
# segmento de p1
hijo[i:j] <- p1[i:j]
# completar con orden de p2
restantes <- p2[!p2 %in% hijo]
hijo[is.na(hijo)] <- restantes
return(hijo)
}Mutación SWAP
mutacion <- function(secuencia){
idx <- sample(1:length(secuencia), 2)
temp <- secuencia[idx[1]]
secuencia[idx[1]] <- secuencia[idx[2]]
secuencia[idx[2]] <- temp
return(secuencia)
}Función algoritmo genético
algoritmo_genetico_vrp <- function(D, demandas, Q, deposito,
n_pob = 60,
generaciones = 300,
prob_cruce = 0.9,
prob_mut = 0.2,
elitismo = TRUE){
clientes <- setdiff(names(demandas), deposito)
poblacion <- generar_poblacion(n_pob, clientes)
mejor_global <- poblacion[[1]]
mejor_costo <- Inf
historial <- c()
for(gen in 1:generaciones){
nueva_poblacion <- list()
# ELITISMO
if(elitismo){
costos <- sapply(poblacion, function(ind){
rutas <- split_rutas(ind, demandas, Q, deposito)
costo_total(rutas, D)
})
mejor_idx <- which.min(costos)
nueva_poblacion[[1]] <- poblacion[[mejor_idx]]
start <- 2
} else {
start <- 1
}
for(i in start:n_pob){
padre1 <- seleccion_torneo(poblacion, D, demandas, Q, deposito)
padre2 <- seleccion_torneo(poblacion, D, demandas, Q, deposito)
# CRUCE
if(runif(1) < prob_cruce){
hijo <- crossover_OX(padre1, padre2)
} else {
hijo <- padre1
}
# MUTACIÓN
if(runif(1) < prob_mut){
hijo <- mutacion(hijo)
}
nueva_poblacion[[i]] <- hijo
}
poblacion <- nueva_poblacion
# EVALUACIÓN GLOBAL
for(ind in poblacion){
rutas <- split_rutas(ind, demandas, Q, deposito)
costo <- costo_total(rutas, D)
if(costo < mejor_costo){
mejor_costo <- costo
mejor_global <- ind
}
}
historial[gen] <- mejor_costo
}
return(list(
mejor_secuencia = mejor_global,
mejor_rutas = split_rutas(mejor_global, demandas, Q, deposito),
mejor_costo = mejor_costo,
historial = historial
))
}Ejecución del algoritmo
resultados_ga <- algoritmo_genetico_vrp(
D, demandas, Q, deposito,
n_pob = 60,
generaciones = 300
)Gráficos
plot(resultados_ga$historial, type="l",
main="GA- evolución del costo",
xlab="Generación", ylab="Costo")Cantidad y carga de rutas
resultados_ga$mejor_costo
length(resultados_ga$mejor_rutas)Cargas de cada ruta
sapply(resultados_ga$mejor_rutas,
function(r) sum(demandas[r[r %in% names(demandas)]]))Costo de las rutas
distancia_ruta <- function(ruta, D){
sum(sapply(1:(length(ruta)-1),
function(i) D[ruta[i], ruta[i+1]]))
}Resumen de resultados
data.frame(
Ruta = 1:length(resultados_ga$mejor_rutas),
Distancia_km = sapply(resultados_ga$mejor_rutas, distancia_ruta, D),
Carga = sapply(resultados_ga$mejor_rutas,
function(r) sum(demandas[r[r %in% names(demandas)]]))
)