Definiciones: Job Shop, Flow Shop y Flow Shop Permutacional

Flow Shop Permutacional (P)

Descripción: Este es un caso específico y más restrictivo del Flow Shop. En este sistema, todas las piezas (o trabajos) siguen exactamente la misma secuencia de máquinas. Un ejemplo clásico es una cinta transportadora donde el orden físico de entrada se mantiene a lo largo de todo el proceso.

Soluciones posibles: n! (donde n es el número de trabajos/piezas).

Flow Shop Genérico (F)

Descripción: Al igual que en el permutacional, todas las piezas tienen el mismo orden de producción (visitan las etapas en el mismo orden), pero el transporte no es común ni fijo (no existe un mecanismo físico que imponga el mismo orden de forma rígida). Esto permite que el orden de procesamiento de las piezas pueda cambiar de una máquina a otra (adelantamientos si hay almacenes intermedios, por ejemplo).

Soluciones posibles: (n!)^m (donde n es el número de trabajos y m el número de máquinas).

Job Shop (J)

Descripción: Es el entorno más general y flexible. Cada pieza o trabajo tiene su propio recorrido o ruta específica por el taller, pasando por las máquinas en secuencias distintas según sus necesidades.

Soluciones posibles: (n!)^m.

Criterios generales de clasificación de metaheurísticas

Inspiradas en la naturaleza vs. No inspiradas: Dependiendo de si imitan procesos biológicos (por ejemplo, la evolución) o procesos físicos (por ejemplo, el recocido).

Con memoria vs. Sin memoria: Si utilizan información obtenida dinámicamente de la búsqueda para usarla posteriormente (por ejemplo, Tabú) o si son «amnésicas» (por ejemplo, Recocido Simulado).

Deterministas vs. Estocásticas: Si utilizan reglas aleatorias durante la búsqueda o decisiones puramente deterministas.

Iterativas vs. Greedy (codiciosas): Si mejoran una solución completa iterativamente o construyen la solución paso a paso.

Basadas en poblaciones vs. Basadas en trayectorias: Si evolucionan una solución única o un conjunto de ellas simultáneamente.

Diferencia entre metaheurística basada en trayectorias y basada en poblaciones

• Basadas en trayectorias (solución única): Manipulan y transforman una única solución candidata durante la ejecución. Suelen explotar mejor la estructura local (intensificación). Ejemplos: Búsqueda del primer mejor (búsqueda local), Mejor vecino, Recocido Simulado.
• Basadas en poblaciones: Mantienen y mejoran múltiples soluciones de forma simultánea. Están más orientadas hacia la exploración global del espacio de búsqueda. Ejemplo: Algoritmo Genético.

Clasificación de algoritmos concretos

• Búsqueda del primer mejor (Búsqueda local): Basada en trayectorias (solución única); típicamente determinista si la exploración del vecindario sigue un orden fijo.
• Mejor vecino (Búsqueda local): Basada en trayectorias; típicamente determinista.
• Recocido Simulado: Basada en trayectorias; estocástico (acepta soluciones peores con cierta probabilidad para escapar de óptimos locales).
• Algoritmo Genético: Basado en poblaciones; estocástico (selección, cruce y mutación introducen aleatoriedad).

¿En qué casos utilizar técnicas metaheurísticas?

• Complejidad del problema: Problemas NP-duros donde los métodos exactos no son viables.
• Tamaño del problema: Instancias grandes (alta dimensionalidad) que hacen explotar el tiempo de los métodos exactos.
• Limitaciones de tiempo (tiempo real): Necesidad de soluciones rápidas (problemas de control/operacionales) frente a la garantía de optimalidad.
• Naturaleza de la función objetivo: Funciones «caja negra», discontinuas, con ruido o no diferenciables (donde fallan métodos basados en gradiente).
• Precisión requerida: Cuando no es estrictamente necesario el óptimo global, sino que una solución «suficientemente buena» (good enough) es aceptable.

¿Qué garantías proporcionan los algoritmos?

Óptimo global: Algunos métodos estocásticos como la búsqueda aleatoria pura o el recocido simulado pueden, en teoría, converger al óptimo global si se cumplen condiciones ideales (por ejemplo, esquema de enfriamiento apropiado y tiempo de cómputo infinito). En la práctica, esto no garantiza obtener el óptimo en tiempo finito.

Óptimo local: La búsqueda local tiende a converger a un óptimo local (dependiendo de la definición de vecindario y criterios de parada). Se puede decir que la búsqueda local garantiza detenerse en un óptimo local respecto al vecindario explorado, pero rara vez encuentra el óptimo global sin mecanismos adicionales para escapar de cuencas de atracción.

Algoritmo Genético: No garantiza alcanzar el óptimo global ni que se «detenga» en un óptimo local exacto. Sin embargo, es eficaz para explorar regiones prometedoras del espacio de búsqueda y combinar buenos rasgos entre soluciones.

Determinismo y estocasticidad según condición inicial

• Deterministas (dada una condición inicial y una exploración de vecindario fija): Mejor Vecino, Primer Mejor (en su versión determinista).
• Estocásticos: Búsqueda Aleatoria, Recocido Simulado, Algoritmos genéticos (por la selección aleatoria, cruces y mutaciones).

¿Por qué el recocido simulado permite movimientos hacia soluciones peores?

Permite movimientos hacia soluciones peores para escapar de óptimos locales y evitar una convergencia prematura. Si solo aceptara mejoras (como una búsqueda local «greedy»), el algoritmo quedaría atrapado en el primer pico o valle que encontrase.

Factores que influyen en la aceptación de empeoramientos:

• Degradación de la función objetivo (δ): Cuanto peor sea la nueva solución respecto a la actual, menor es la probabilidad de aceptarla.
• Temperatura (T): Es el parámetro de control. A temperaturas altas, es muy probable aceptar soluciones peores (exploración). A medida que T disminuye (enfriamiento), la probabilidad de aceptar empeoramientos decrece, volviéndose el algoritmo más exigente (explotación).

Mecanismo de selección por ruleta

Este es un método estocástico de selección proporcional a la fitness (calidad de la solución). Su objetivo es simular la supervivencia del más apto, pero dando una pequeña oportunidad a individuos menos aptos para mantener la diversidad genética.

Funcionamiento (procedimiento):

1. Se calcula la suma total del fitness de toda la población: F_total = ∑_i=1^N f(i).
2. Se calcula la probabilidad de selección relativa para cada individuo i: p_i = f(i) / F_total.
3. Se generan probabilidades acumuladas para construir la ruleta.
4. Se lanza un número aleatorio uniforme r ∈ [0,1]. El primer individuo cuya probabilidad acumulada supere r es el seleccionado.

De esta forma, los individuos con mayor fitness tienen una mayor probabilidad de ser padres, pero no se garantiza su selección, evitando la convergencia prematura.

Pseudocódigo: Algoritmo Genético

INICIO
  1. Generar población inicial aleatoria (P)
  2. Evaluar la aptitud (fitness) de cada individuo en P
  3. MIENTRAS (no se cumpla criterio de parada) HACER
     3.1 Seleccionar individuos de P para ser padres (ej. Ruleta/Torneo)
     3.2 Cruzar los padres para generar descendencia (crossover)
     3.3 Mutar la descendencia (con baja probabilidad)
     3.4 Evaluar la aptitud de la nueva descendencia
     3.5 Reemplazar la población antigua con la nueva (reemplazo)
  FIN MIENTRAS
  4. Devolver la mejor solución encontrada
FIN

Técnicas de cruce

Para Flow Shop Permutacional (codificación permutacional): Se puede usar el cruce OX (Order Crossover): se selecciona un segmento de un padre y se copia al hijo. Los huecos restantes se rellenan con los genes del otro padre en el orden en que aparecen, saltando los que ya están en el segmento copiado. También son válidos PMX o CX.

Codificación binaria: Cruce en un punto. Se elige un punto de corte aleatorio en los cromosomas de los padres y se intercambian las colas para formar dos hijos.

Optimización de una función con dos variables x e y

Las metaheurísticas se recomiendan para problemas de alta dimensionalidad (superior a 3 variables) o cuando los métodos exactos fallan debido a discontinuidades o ruido.

Consideraciones específicas para el caso de dos variables:

1. Tiene baja dimensionalidad (solo 2 variables, x e y).
2. Las funciones son continuas y derivables (polinomios simples).
3. Existen métodos exactos (cálculo, multiplicadores de Lagrange, condiciones KKT) que garantizan hallar el óptimo de forma mucho más eficiente y precisa que una metaheurística.

Ejemplos de problemas y propuestas de modelado/metaheurística

Problema: Ingeniero que construye robots

a) Representación y tamaño:

Vector binario: x = [x1, x2, …, x20] donde xi = 1 (aceptar pedido) o 0 (rechazar).

Posibles soluciones: 2²⁰ = 1.048.576.

b) Formalización:

Función objetivo: Maximizar Z = ∑_i=1²⁰ Precio_i·x_i.

Restricción: ∑_i=1²⁰ Horas_i·x_i ≤ 350.

Dominio: x_i ∈ {0,1}.

c) Metaheurística (prioridad: calidad sobre rapidez):

Algoritmo: Recocido Simulado.

Parametrización: T₀ alta para máxima exploración inicial; enfriamiento lento (esquema logarítmico o geométrico con α ≈ 0.99); cadenas de Markov largas (muchas iteraciones por temperatura) para aumentar la probabilidad de convergencia al óptimo global.

d) Vecindario:

Definición: Bit flip (seleccionar un pedido al azar e invertir su estado 0 ⇄ 1).

Justificación: Localidad fuerte; permite navegar el espacio de soluciones con cambios mínimos y graduales.

e) Tamaño del vecindario: 20 soluciones vecinas (una por cada pedido que se puede cambiar).

f) Soluciones infactibles:

Método: Función de penalización (exterior).

Ajuste: Z'(x) = Z(x) − λ·max(0, TiempoTotal − 350). Se penaliza el exceso de horas en la función objetivo en lugar de descartar la solución.

Problema: 40 máquinas fotocopiadoras

a) Representación y espacio de búsqueda:

Vector de enteros: x = [x1, x2, …, x40].

Codificación: x_i ∈ {1,2,3,4,5} (indica el centro asignado a la máquina i).

Tamaño del espacio: 5⁴⁰ soluciones posibles.

b) Formalización matemática:

Objetivo: Minimizar la varianza de la capacidad entre centros.

Función a minimizar: f(x) = ∑_j=1⁵ (C_j(x) − u)², donde C_j(x) es la suma de velocidades en el centro j y u es la media ideal (∑ v_i/5).

c) Metaheurística (prioridad: calidad):

Algoritmo: Recocido Simulado.

Justificación: Excelente para problemas de partición con múltiples óptimos locales; evita estancamientos prematuros.

Parametrización: T₀ calculada para aceptar alrededor del 50% de deterioros iniciales; enfriamiento geométrico lento (T_k+1 = 0.99 · T_k).

d) Vecindario:

Concepto: Reasignación simple (shift).

Operador: Tomar una máquina al azar y moverla a otro centro aleatorio distinto al actual.

Justificación: Movimiento mínimo («atómico») que permite el ajuste fino de cargas entre centros.

e) Tamaño del vecindario:

Cálculo: 40 máquinas × 4 destinos alternativos = 160 soluciones vecinas exactas.

Problema: Joyero (Mochila 0/1)

a) Representación y espacio de soluciones:

Vector binario: x = [x1, x2, …, xN] donde x_i = 1 (aceptar oferta) o 0 (rechazar).

Tamaño del espacio: 2^N combinaciones posibles de ofertas.

b) Formalización matemática:

Objetivo: Maximizar Z = ∑_i=1^N Dinero_i·x_i.

Restricción: ∑_i=1^M Esmeralda_i·x_i ≤ Total disponible.

Dominio: x_i ∈ {0,1}.

c) Metaheurística (selección):

Algoritmo: Algoritmo Genético.

Justificación: Ideal para representaciones binarias. Al trabajar con una población, explora combinaciones de ofertas («paquetes») eficientemente mediante el cruce.

d) Operadores genéticos:

• Selección: Torneo (elegir k al azar y quedarse con el mejor).
• Cruce: En un punto (intercambiar las colas de dos soluciones padres).
• Mutación: Bit flip (baja probabilidad de invertir una decisión de oferta).

e) Tratamiento de soluciones infactibles:

Método: Reparación voraz.

Procedimiento: Si una solución consume más esmeraldas de las disponibles, no se descarta. Se eliminan ofertas (cambiar 1 a 0) comenzando por las menos rentables (menor ratio Dinero/Esmeralda) hasta cumplir la restricción. Esto asegura soluciones válidas de alta calidad.