Fundamentos de Algoritmos de Optimización: Genéticos, PSO, ACO y Pareto

Algoritmo Genético

El Algoritmo Genético (AG) es una metaheurística inspirada en la evolución biológica. Se aplica principalmente a problemas con valores discretos, aunque puede trabajar con valores continuos mediante una representación binaria.

Una variante importante es la Evolución Diferencial (DE), enfocada en valores continuos, que se diferencia por su operación de cruzamiento, la cual realiza una operación lineal.

Conceptos Clave en Algoritmos Genéticos

• Fitness: Mide qué tan apto es un individuo. Está sujeto a la Función Objetivo (FO) y determina la probabilidad de selección para la reproducción.

Fases del Algoritmo Genético

1. Selección

Proceso para elegir individuos que se reproducirán, basándose en su fitness. Métodos comunes incluyen:

• Ruleta: Asigna una probabilidad a cada individuo dependiendo de su fitness (similar a un gráfico de torta).
• Torneo: Escoge k individuos aleatorios y selecciona al mejor entre ellos.

2. Reproducción (Cruzamiento)

Genera nuevos individuos a partir de un operador binario que hereda características de los dos padres. Ejemplos de operadores de cruzamiento:

• CrossOver-1: Separa el cromosoma en dos puntos.
• CrossOver-2: Separa el cromosoma en tres puntos.
• CrossOver Uniforme: Intercambia bits de forma aleatoria (ej: 101 → 010).

3. Mutación

Operador unitario que introduce variabilidad en la población. Un ejemplo es el operador SWAP, que cambia la ubicación de un gen en el cromosoma.

Estrategias de Cambio de Población

• Elegir hijo, eliminar padre: El nuevo individuo reemplaza a uno de sus padres.
• Elitismo: Un porcentaje de los mejores individuos se mantiene directamente para la siguiente generación, asegurando la conservación de las mejores soluciones encontradas.

Optimización por Enjambre de Partículas (PSO)

El PSO (Particle Swarm Optimization) está enfocado en problemas continuos. Su característica transversal es el componente de población, donde las partículas cambian de posición respecto a dos referencias:

1. La mejor posición encontrada por sí misma (Lbest): Ayuda a la exploración.
2. La mejor posición encontrada por el enjambre (Gbest) o un subconjunto: Ayuda a la explotación.

Siempre hay comunicación con el líder (Gbest). Por otro lado, se pueden tener múltiples líderes en topologías de varios grupos, donde cada uno tiene un líder, lo que ayuda a la exploración.

El peso de inercia (W) influye en el comportamiento del algoritmo:

• Un W más grande implica mayor exploración.
• Un W más pequeño implica mayor explotación.

Esto se relaciona con la velocidad con inercia. Para actualizar la posición de una partícula, se necesita que la nueva posición sea mejor que Lbest y Gbest.

Optimización por Colonia de Hormigas (ACO)

El ACO (Ant Colony Optimization) es ideal para encontrar la ruta óptima entre dos puntos. Sus conceptos clave son la evaporación y el proceso de refuerzo de feromonas.

• Sin evaporación: Mayor explotación (acumulación de feromonas).
• Con evaporación: Mayor exploración (penalización de feromonas).
• Mucha evaporación: Comportamiento aleatorio.

El costo y las feromonas se utilizan para calcular la probabilidad de cada camino y escoger el mejor, similar al método de la Ruleta.

Con la Función Objetivo (FO) se actualizan las feromonas en los caminos.

Sintonización y Control de Parámetros

La sintonización de parámetros es crucial para el rendimiento de los algoritmos de optimización. Un buen espacio de búsqueda comienza explorando el espacio para luego explotar zonas favorables.

1. Sintonización

Es un proceso previo a la ejecución del algoritmo. Puede ser:

• Manual
• Estadístico
• Meta-algorítmico

2. Control

Es un proceso durante la ejecución del algoritmo. Puede ser:

• Dinámico: De forma determinista respecto a la medición del tiempo.
• Adaptativo: Basado en la información de búsqueda.
• Auto-adaptativo: Similar al anterior, pero propio de cada solución (común en Algoritmos de Población).

Técnicas Relacionadas

• Racing: Testeo estadístico para evaluar el rendimiento. Permite la evolución de una población medida por el fitness del campeón.
• Búsqueda Local: Comenzar con un valor inicial e ir cambiando los valores de los parámetros hasta que no exista una configuración que mejore el desempeño.
• ILS (Iterated Local Search): La clave es la perturbación. Si es pequeña, no mejora; si es muy grande, el comportamiento será muy aleatorio.

Optimalidad de Pareto

La Optimalidad de Pareto se refiere a soluciones que son óptimas y eficientes, lo que significa que no se puede mejorar una Función Objetivo (FO) sin empeorar al menos otra FO.

• Puntos juntos: Indican poca diversidad, lo que puede hacer que el algoritmo no avance.
• Puntos separados: Indican mayor diversidad, permitiendo al algoritmo explorar más el espacio de soluciones.

Distancia de Crowding

La Distancia de Crowding mide la diversidad de las soluciones en base a sus vecinos. Cuanto más juntos estén los puntos, mayor probabilidad de que sean conservados. Cuanto más lejana sea la distancia, mayor diversidad (soluciones más dispersas).

En la generación de población, se utiliza un torneo donde ganan los individuos con ranking 1. Luego se realiza un torneo con los individuos de ese ranking y, en caso de empate, se utiliza la Distancia de Crowding para desempatar y mantener la diversidad.