Fundamentos de Algoritmos Evolutivos y Optimización Bioinspirada

Algoritmos Genéticos

• Fitness: Se realiza mediante la elección por ruleta o torneo.
• Reproducción: Incluye el cruzamiento, que puede ser de 1 punto (mitad), 2 puntos (tercio) o uniforme (azar por bit).
• Mutación: Definida por una probabilidad Pm. Se aplica en dominio binario o mediante TSP (permutar variables).
• Reemplazo: Puede ser generacional (los hijos sobreviven) o por elitismo. El tamaño de la población se mantiene constante.

Differential Evolution (DE)

• Utiliza números continuos para optimizar funciones no diferenciables o problemas multiobjetivo.
• P₀: Población inicial aleatoria de tamaño K. Cada individuo es un vector x_ij de dimensión D.
• Cambio: Se basa en una combinación lineal. La operación es C += A - B, y posteriormente el resultado se enfrenta al individuo original.

Coevolución Cooperativa

Consiste en la evolución complementaria de especies cercanas. El problema se divide en subproblemas y, al finalizar el proceso, los representantes de cada especie se unen.

Es una técnica especialmente útil en redes neuronales y problemas de optimización de gran escala.

Inteligencia de Enjambre

PSO (Particle Swarm Optimization)

Cada partícula tiene una posición X_i, la cual cambia en función de su mejor posición histórica individual (p_i) y la mejor posición global del enjambre (p_g). El vecindario puede ser global o local.

El cambio se define por la velocidad anterior, las constantes C1 y C2, y valores aleatorios p1 y p2 en el rango {0,1}. El parámetro W pondera la influencia de la velocidad anterior.

ACO (Ant Colony Optimization)

Se basa en el rastro de feromonas. La cantidad de feromona depositada es 1/Lk, donde Lk representa el costo del camino.

Las feromonas pueden evaporarse o no. Con evaporación, la fórmula se expresa como 1/Lk + (1-p)Tij, donde p indica qué tan rápido se evapora el rastro.

Cada camino tiene una probabilidad asociada vinculada a la cantidad de feromona (alpha) y lo atractivo del camino (beta).

Sintonización y Búsqueda Local

Sintonización

• Racing: Un método estadístico que evalúa iterativamente cada algoritmo. Se mide a través del fitness, entendido como la habilidad de hacer evolucionar a una población.

Búsqueda Local

Consiste en comenzar de forma aleatoria e ir mejorando la solución gradualmente. El ILS (Iterated Local Search) incluye el concepto de random walk (caminata aleatoria).

Técnicas de Control

• Control dinámico: El parámetro cambia solo cada cierto tiempo predefinido.
• Control adaptativo: El ajuste es de carácter global.
• Control auto-adaptativo: El ajuste se realiza de forma específica para cada individuo.

Optimización Multi-Objetivo

Optimalidad de Pareto

• Mejora de Pareto: Consiste en moverse hacia una solución que no empeore ningún objetivo.
• Pareto óptimas: Son soluciones que no pueden ser mejoradas en un objetivo sin perjudicar otro; es decir, una solución no mejorable.
• Solución dominada: Es aquella que es peor en cada una de las componentes al ser evaluada en la Función Objetivo (FO).
• Frente de Pareto: Es el conjunto de todas las soluciones no dominadas, representando el compromiso o sacrificio entre objetivos.

NSGA-II (Non-dominated Sorting Genetic Algorithm II)

• Gestiona varios frentes no dominados.
• Si dos soluciones pertenecen al mismo frente, tienen el mismo ranking. En este caso, se prefiere aquella ubicada en la zona menos poblada.
• Se prioriza la solución con una mayor distancia de aglomeración (crowding distance) para asegurar un conjunto más diverso.
• Selección: Se realiza mediante torneo. Se elige al individuo con mejor ranking; en caso de empate, se decide por la distancia de crowding.