Clase 1 — Introducción a la Computación Bioinspirada

Resumen Ejecutivo

Esta sesión introductoria presenta el marco general de la optimización bioinspirada, situándola como evolución natural de los algoritmos exactos (deterministas) hacia los algoritmos heurísticos y metaheurísticos. Se explica por qué surgen estos algoritmos (limitaciones computacionales de los métodos exactos en problemas grandes) y se presentan las tres grandes familias: algoritmos genéticos (evolutivos), algoritmos de enjambre (adaptación social) y redes neuronales. Se repasan brevemente los conceptos de optimización mono-objetivo y multi-objetivo como base para la asignatura.

Conceptos Clave

Algoritmo exacto (determinista): Busca la solución óptima garantizada, pero con un coste computacional que crece enormemente en problemas grandes. ⚠️ EXAMEN
Algoritmo heurístico: Busca una buena solución en un tiempo razonable, sin garantizar el óptimo. ⚠️ EXAMEN
Metaheurística: Combinación de varias heurísticas (por ejemplo, usar una heurística para generar el punto de partida de otra), logrando mejores resultados.
Algoritmo bioinspirado: Algoritmo heurístico/metaheurístico que se inspira en procesos observados en la naturaleza (comportamiento animal, genética, neurociencia) para resolver problemas de optimización. ⚠️ EXAMEN
Fitness: Nombre que recibe la función objetivo en el contexto de algoritmos bioinspirados; mide la calidad de una solución. ⚠️ EXAMEN
Búsqueda local: Metaheurística que parte de un único punto y explora su vecindad (ej.: Tabu Search, Simulated Annealing, Hill Climbing).
Búsqueda poblacional: Metaheurística que trabaja con múltiples soluciones simultáneamente, explorando regiones más amplias del espacio de búsqueda.
Óptimo local: Solución que es la mejor en su vecindad pero no necesariamente la mejor global; los algoritmos bioinspirados incorporan mecanismos para escapar de ellos.

Desarrollo del Temario

1. De los algoritmos exactos a los heurísticos

La optimización clásica busca el óptimo exacto: derivar, igualar a cero y encontrar el valor óptimo. Esto funciona bien en problemas pequeños (2-3 variables, resolubles a mano o con método gráfico), pero en problemas reales con miles o millones de variables, incluso los supercomputadores se quedan cortos.

Ejemplo: En el doctorado, un problema heurístico muy grande tardaba más de una semana en un servidor potente. Ni siquiera el supercomputador MareNostrum de Barcelona resuelve el problema si el algoritmo no es eficiente: "Por más power que tú tengas, si no haces un algoritmo eficiente, no vas a llegar."

La eficiencia algorítmica importa más que el hardware. Desde el nivel del if (qué condición evaluar primero), el for (cuántas iteraciones), hasta qué operaciones matemáticas se piden: no es lo mismo una suma que un millón de sumas.

Los algoritmos heurísticos nacen como respuesta: renuncian a garantizar el óptimo a cambio de obtener buenas soluciones en tiempo razonable. ⚠️ EXAMEN

Ejemplo: "Si estoy en la Fórmula 1 y las variables me las das en una semana, la carrera se acabó hace dos horas. Pero si estás en una empresa y una planificación de una semana es razonable, depende de dónde estemos."

2. Clasificación de los algoritmos de optimización

El mapa general de algoritmos se organiza así:

Algoritmos de optimización
├── Exactos (deterministas)
│   ├── Simplex
│   └── Punto interior (más rápidos, van por dentro de la región factible)
│
└── Heurísticos / No deterministas
    └── Metaheurísticas
        ├── Búsqueda local (un punto inicial)
        │   ├── Tabu Search
        │   ├── Simulated Annealing
        │   └── Hill Climbing
        │
        └── Búsqueda poblacional (múltiples puntos)
            ├── Algoritmos genéticos (evolutivos)
            ├── Algoritmos de enjambre (adaptación social)
            │   ├── Colonia de hormigas (ACO)
            │   ├── Enjambre de partículas (PSO)
            │   └── Colonia de abejas (ABC)
            └── Redes neuronales

Diferencia clave búsqueda local vs. poblacional: ⚠️ EXAMEN - Local: parte de un solo punto y busca en su vecindad. - Poblacional: parte de varios puntos simultáneamente, cubriendo una región de búsqueda más amplia.

3. Algoritmos genéticos (evolutivos)

Se inspiran en la evolución biológica de Darwin. Los pasos básicos son: ⚠️ EXAMEN

Población inicial: se genera un conjunto de individuos (soluciones candidatas).
Evaluación (fitness): se mide la calidad de cada individuo según la función objetivo.
Selección: se eligen los mejores individuos para reproducirse.
Cruce (reproducción): los individuos seleccionados se combinan para generar descendencia.
Mutación: se introducen cambios aleatorios para evitar quedarse en óptimos locales.
Nueva generación: se repite el proceso con la nueva población.

Ejemplo: "Si yo solo escojo los mejores y hago esos cruces, me quedo en óptimos locales. Es como los reyes que siempre se cruzaban con reyes, y luego llegamos a la historia de que no era tan buena idea. Lo mismo pasa en las matemáticas. Entonces, hay que meterle una mutación para salir del óptimo local."

La mutación es clave porque permite explorar nuevas regiones del espacio de soluciones, evitando la convergencia prematura. ⚠️ EXAMEN

No hay un "director de orquesta" que guíe a los agentes; cada uno tiene un conocimiento básico y un comportamiento social que beneficia al grupo. ⚠️ EXAMEN

Colonia de hormigas (ACO)

Se mueven inicialmente en \(\mathbb{R}^2\) (dos dimensiones, tierra). ⚠️ EXAMEN
Se comunican mediante feromonas: cada hormiga deja un rastro químico por el camino que recorre.
Las feromonas son volátiles: se disipan con el tiempo, favoreciendo los caminos más cortos (más hormigas los recorren → más feromonas acumuladas).

Enjambre de partículas (PSO — Particle Swarm Optimization)

Basado en el comportamiento de aves o peces que se mueven en \(\mathbb{R}^3\) o \(\mathbb{R}^n\). ⚠️ EXAMEN
Cada partícula mantiene una memoria personal (su mejor solución encontrada).
Existe una memoria global del grupo (la mejor solución encontrada por cualquier partícula).
Las partículas se mueven influenciadas por ambas memorias, siguiendo al líder sin aglomerarse.

Colonia de abejas (ABC — Artificial Bee Colony)

Incorporan roles diferenciados: abejas exploradoras (buscan nuevas fuentes de néctar), abejas obreras (explotan fuentes conocidas) y abejas observadoras.
Cambio de rol: si una abeja obrera agota una fuente, se convierte en exploradora.

Diferencia clave entre ACO y PSO: Las hormigas operan originalmente en \(\mathbb{R}^2\) (tierra), mientras que las aves/partículas operan en \(\mathbb{R}^3\) o más dimensiones. Además, en PSO todos los agentes tienen el mismo rol, mientras que en ABC hay roles diferenciados.

5. Redes neuronales (introducción breve)

Simulan el comportamiento del cerebro: trabajan sobre nodos interconectados.
Cada nodo recibe entradas, resuelve un problema de optimización interno y produce salidas que alimentan otros nodos.
La salida de un nodo es la entrada del siguiente → se van descartando variables irrelevantes y quedándose con las que aportan valor.
Se conectan con el mundo del machine learning.

Ejemplo: "Que el ordenador aprende, ¿cómo aprende? Tú le das variables de entrada, cada nodo las analiza como un problema de optimización, y la salida va a ser la entrada de otro nodo. Vas descartando las variables que no sirven y te vas quedando con las que sí."

6. Mono-objetivo vs. Multi-objetivo (repaso)

Mono-objetivo: optimizar una única función objetivo (maximizar o minimizar).
Multi-objetivo: optimizar varias funciones objetivo simultáneamente, que suelen estar en conflicto.

Ejemplo: "Quiero tiempo y dinero. Quiero comer y no engordar. Tener dinero para ir de vacaciones Y tener el tiempo para poder ir."

En la práctica, se suelen combinar los objetivos en una función ponderada (50% un objetivo, 50% otro) para reducirlo a mono-objetivo. También se pueden subir las restricciones a la función objetivo mediante penalizaciones. ⚠️ EXAMEN

7. Problemas estocásticos (mención)

Son problemas donde las variables tienen componente probabilística (variables aleatorias).
Se modelan múltiples escenarios posibles.

Ejemplo: "El del granjero: si llueve, ¿me va a crecer lo que sembré? La probabilidad de que llueva, no llueva, llueva poco. Todos esos escenarios se montan, pero al final lo que haces es un problemota gigante."

8. Características comunes de los algoritmos bioinspirados

No deterministas: incorporan aleatoriedad en su funcionamiento.
No garantizan el óptimo: buscan buenas soluciones, no necesariamente la mejor.
Sin control centralizado: no hay un "director" que guíe a los agentes.
Comportamiento emergente: la inteligencia del sistema surge de la interacción de agentes simples.
Parámetros de control: variables de entorno que regulan el comportamiento del algoritmo (tasa de mutación, volatilidad de feromonas, etc.).
Adaptabilidad: los algoritmos se ajustan durante su ejecución.
En continua evolución: constantemente se publican nuevas variantes inspiradas en diferentes fenómenos naturales (halcones, tiburones, etc.).

Preguntas de Autoevaluación

¿Cuál es la diferencia fundamental entre un algoritmo exacto y un algoritmo heurístico? ¿Qué sacrifica cada uno?
¿Qué es una metaheurística y en qué se diferencia de una heurística simple?
Describe los pasos básicos de un algoritmo genético. ¿Por qué es necesaria la mutación?
¿Qué papel juegan las feromonas en el algoritmo de colonia de hormigas? ¿Por qué es importante que sean volátiles?
¿Cuál es la diferencia principal entre la colonia de hormigas (ACO) y el enjambre de partículas (PSO) en cuanto al espacio de búsqueda?
En el PSO, ¿qué dos tipos de memoria utiliza cada partícula para decidir su movimiento?
¿Qué diferencia a los algoritmos de búsqueda local de los de búsqueda poblacional?
¿Por qué no basta con aumentar la potencia computacional (más cores, supercomputadores) para resolver problemas de optimización grandes?
¿Qué significa que un algoritmo bioinspirado no tiene "director de orquesta"?
¿Cómo se transforma un problema multi-objetivo en uno mono-objetivo en la práctica?

Guía generada automáticamente a partir de transcripción con faster-whisper + Claude Sonnet.