Introducción

La computación inteligente, una rama fundamental de la inteligencia artificial, ofrece paradigmas computacionales eficientes para resolver problemas complejos mediante la simulación de fenómenos naturales como la evolución biológica y la inteligencia colectiva. Este documento explora los principios de los algoritmos evolutivos, detalla diversas variantes del algoritmo genético, y presenta algoritmos de inteligencia de enjambre como la optimización por enjambre de partículas y la colonia de hormigas, acompañados de implementaciones prácticas en Python.

1. Algoritmos Evolutivos: Fundamentos

Los algoritmos evolutivos (AE) constituyen una familia de métodos de búsqueda estocástica y adaptable inspirados en los procesos de selección natural y genética. Su objetivo es hallar soluciones óptimas a problemas complejos, emulando mecanismos como la reproducción, el cruce, la mutación y la selección basada en la aptitud.

1.1 Principios de Diseño

El diseño de un AE efectivo se rige por principios clave: la definición de una función de aptitud que evalúe la calidad de las soluciones, el mantenimiento de la diversidad genética en la población para evitar la convergencia prematura, la aplicación de operadores genéticos para evolucionar las soluciones, y el ajuste cuidadoso de parámetros como el tamaño de la población y las tasas de operadores.

2. Algoritmos Genéticos y sus Variantes

El algoritmo genético (AG) es un tipo de AE que codifica las soluciones como "cromosomas" y las mejora iterativamente mediante selección, cruce y mutación.

2.1 Codificación y Operadores

Las estrategias de codificación comunes incluyen la binaria, la de números reales y la simbólica. La selección por ruleta favorece a los indiivduos más aptos. El cruce combina material genético de dos progenitores, mientras que la mutación introduce variaciones aleatorias para explorar nuevas regiones del espacio de búsqueda.

2.2 Implementación Básica

El siguiente código implementa un AG básico para maximizar la función f(x) = x² en un intervalo dado. La implementación utiliza codificación binaria y los operadores genéticos estándar.

import numpy as np
import matplotlib.pyplot as plt
from typing import List, Tuple

plt.rcParams['font.family'] = 'DejaVu Sans'

class AlgoritmoGeneticoBasico:
    def __init__(self, tam_pob: int = 100, long_crom: int = 22, gen_max: int = 200,
                 prob_cruce: float = 0.8, prob_mut: float = 0.01, rango_x: Tuple[float, float] = (-10, 10)):
        self.tam_pob = tam_pob
        self.long_crom = long_crom
        self.gen_max = gen_max
        self.prob_cruce = prob_cruce
        self.prob_mut = prob_mut
        self.rango_x = rango_x
        self.poblacion = np.random.randint(0, 2, (tam_pob, long_crom))
        self.mejor_aptitud = 0.0
        self.mejor_x = 0.0
        self.historial_aptitud = []

    def decodificar_cromosoma(self, cromosoma: np.ndarray) -> float:
        valor_decimal = sum(gen * (2 ** (self.long_crom - 1 - i)) for i, gen in enumerate(cromosoma))
        escala = (self.rango_x[1] - self.rango_x[0]) / (2 ** self.long_crom - 1)
        return self.rango_x[0] + valor_decimal * escala

    def funcion_aptitud(self, x: float) -> float:
        return x ** 2

    def evaluar_poblacion(self) -> np.ndarray:
        aptitudes = np.array([self.funcion_aptitud(self.decodificar_cromosoma(ind))
                              for ind in self.poblacion])
        idx_mejor = np.argmax(aptitudes)
        if aptitudes[idx_mejor] > self.mejor_aptitud:
            self.mejor_aptitud = aptitudes[idx_mejor]
            self.mejor_x = self.decodificar_cromosoma(self.poblacion[idx_mejor])
        self.historial_aptitud.append(np.mean(aptitudes))
        return aptitudes

    def seleccion_por_ruleta(self, aptitudes: np.ndarray) -> np.ndarray:
        prob_acumulada = np.cumsum(aptitudes / np.sum(aptitudes))
        nueva_pob = np.zeros_like(self.poblacion)
        for i in range(self.tam_pob):
            selector = np.random.random()
            for j in range(self.tam_pob):
                if selector <= prob_acumulada[j]:
                    nueva_pob[i] = self.poblacion[j].copy()
                    break
        return nueva_pob

    def cruce_simple(self, padres: np.ndarray) -> np.ndarray:
        descendientes = padres.copy()
        for i in range(0, self.tam_pob, 2):
            if i + 1 < self.tam_pob and np.random.random() < self.prob_cruce:
                punto = np.random.randint(1, self.long_crom)
                descendientes[i, punto:], descendientes[i + 1, punto:] = \
                    descendientes[i + 1, punto:].copy(), descendientes[i, punto:].copy()
        return descendientes

    def mutacion_uniforme(self, individuos: np.ndarray) -> np.ndarray:
        mascara_mutacion = np.random.random(individuos.shape) < self.prob_mut
        individuos[mascara_mutacion] = 1 - individuos[mascara_mutacion]
        return individuos

    def ejecutar(self) -> Tuple[float, float, List[float]]:
        for gen in range(self.gen_max):
            aptitudes = self.evaluar_poblacion()
            seleccionados = self.seleccion_por_ruleta(aptitudes)
            cruzados = self.cruce_simple(seleccionados)
            self.poblacion = self.mutacion_uniforme(cruzados)
            if gen % 20 == 0:
                print(f"Gen {gen}: Mejor aptitud = {self.mejor_aptitud:.2f}")
        return self.mejor_aptitud, self.mejor_x, self.historial_aptitud

# Ejemplo de uso
if __name__ == "__main__":
    ag = AlgoritmoGeneticoBasico()
    aptitud, valor_x, historial = ag.ejecutar()
    print(f"Solución óptima: x = {valor_x:.4f}, f(x) = {aptitud:.4f}")

2.3 Algoritmos Genéticos Mejorados

Para superar limitaciones del AG básico se han desarrollado variantes avanzadas. El AG diploide simula cromosomas con genes dominantes y recesivos. El AG de doble población utiliza dos subpoblaciones que exploran y explotan el espacio de búsqueda de manera diferente, intercambiando individuos mediante migración. El AG adaptativo ajusta dinámicamente las tasas de cruce y mutación según la aptitud de los individuos, favoreciendo la exploración en soluciones pobres y la conservación en soluciones prometedoras.

3. Aplicación en el Problema del Viajante (TSP)

Los AG son efectivos para problemas de optimización combinatoria como el TSP. La solución se codifica como una permutación de ciudades. Se utilizan operadores específicos como el cruce de orden (OX) y la mutación por intercambio para mantener la validez de las permutaciones.

class ResolvedorTSP:
    def __init__(self, num_ciudades: int = 20, tam_pob: int = 100, gen_max: int = 300):
        self.num_ciudades = num_ciudades
        self.tam_pob = tam_pob
        self.gen_max = gen_max
        self.coordenadas = np.random.rand(num_ciudades, 2) * 100
        self.matriz_distancias = self._calcular_matriz_distancias()
        self.poblacion = np.array([np.random.permutation(num_ciudades) for _ in range(tam_pob)])
        self.mejor_ruta = None
        self.mejor_distancia = float('inf')

    def _calcular_matriz_distancias(self) -> np.ndarray:
        from scipy.spatial.distance import cdist
        return cdist(self.coordenadas, self.coordenadas)

    def calcular_distancia_ruta(self, ruta: np.ndarray) -> float:
        dist_total = 0.0
        for i in range(len(ruta) - 1):
            dist_total += self.matriz_distancias[ruta[i], ruta[i + 1]]
        dist_total += self.matriz_distancias[ruta[-1], ruta[0]]
        return dist_total

    def seleccion_y_cruce(self) -> np.ndarray:
        # Implementación simplificada de selección y cruce OX
        nueva_poblacion = []
        for _ in range(self.tam_pob):
            padre1, padre2 = self.poblacion[np.random.choice(self.tam_pob, 2, replace=False)]
            hijo = self._cruce_ox(padre1, padre2)
            nueva_poblacion.append(hijo)
        return np.array(nueva_poblacion)

    def _cruce_ox(self, padre1, padre2):
        # Implementación del operador de cruce de orden
        inicio, fin = sorted(np.random.choice(self.num_ciudades, 2, replace=False))
        hijo = np.full(self.num_ciudades, -1, dtype=int)
        hijo[inicio:fin+1] = padre1[inicio:fin+1]
        pos_actual = (fin + 1) % self.num_ciudades
        for ciudad in padre2:
            if ciudad not in hijo:
                if pos_actual > fin:
                    hijo[pos_actual] = ciudad
                    pos_actual = (pos_actual + 1) % self.num_ciudades
                else:
                    hijo[pos_actual] = ciudad
                    pos_actual = (pos_actual + 1) % self.num_ciudades
        return hijo

    def ejecutar(self) -> Tuple[np.ndarray, float]:
        for gen in range(self.gen_max):
            distancias = np.array([self.calcular_distancia_ruta(ruta) for ruta in self.poblacion])
            idx_mejor = np.argmin(distancias)
            if distancias[idx_mejor] < self.mejor_distancia:
                self.mejor_distancia = distancias[idx_mejor]
                self.mejor_ruta = self.poblacion[idx_mejor].copy()
            # Proceso de selección, cruce y mutación (omitted for brevity)
            nueva_pob = self.seleccion_y_cruce()
            # Aplicar mutación por intercambio...
            self.poblacion = nueva_pob
        return self.mejor_ruta, self.mejor_distancia

4. Algoritmos de Inteligencia de Enjambre

Estos algoritmos están inspirados en el comportamiento colectivo de organismos sociales. Carecen de un control centralizado; la inteligencia global emerge de interacciones locales simples entre individuos (partículas, hormigas, etc.).

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

En PSO, cada partícula representa una solución potencial que se mueve por el espacio de búsqueda. Su posición se actualiza basándose en su mejor posición conociad (pbest) y la mejor posición global del enjambre (gbest). Las ecuaciones de movimiento están gobernadas por una inercia, un componente cognitivo y un componente social.

class EnjambreParticulas:
    def __init__(self, funcion_obj, dim: int = 2, tam_enjambre: int = 50, iter_max: int = 100):
        self.funcion_obj = funcion_obj
        self.dim = dim
        self.tam_enjambre = tam_enjambre
        self.iter_max = iter_max
        self.posiciones = np.random.uniform(-10, 10, (tam_enjambre, dim))
        self.velocidades = np.random.uniform(-1, 1, (tam_enjambre, dim))
        self.pbest_pos = self.posiciones.copy()
        self.pbest_val = np.array([funcion_obj(p) for p in self.posiciones])
        idx_gbest = np.argmin(self.pbest_val)
        self.gbest_pos = self.pbest_pos[idx_gbest].copy()
        self.gbest_val = self.pbest_val[idx_gbest]

    def actualizar(self, w=0.7, c1=1.5, c2=1.5):
        r1, r2 = np.random.random((self.tam_enjambre, self.dim)), np.random.random((self.tam_enjambre, self.dim))
        self.velocidades = (w * self.velocidades +
                            c1 * r1 * (self.pbest_pos - self.posiciones) +
                            c2 * r2 * (self.gbest_pos - self.posiciones))
        self.posiciones += self.velocidades
        self.posiciones = np.clip(self.posiciones, -10, 10)
        # Actualizar pbest y gbest...

    def optimizar(self):
        for _ in range(self.iter_max):
            self.actualizar()
        return self.gbest_pos, self.gbest_val

4.2 Algoritmo de Colonia de Hormigas (ACO)

ACO simula el comportamiento de búsqueda de alimento de las hormigas. Las hormigas depositan feromonas en los caminos recorridos. Las soluciones se construyen probabilísticamente, guiadas por la concentración de feromonas y heurísticas de visibilidad (ej., inverso de la distancia). Las feromonas se evaporen con el tiempo y se refuercan en los caminos de soluciones de alta calidad. Se aplica comúnmente a problemas de rutas como el TSP.

4.3 Parámetros Clave de ACO

Los parámetros críticos incluyen: el número de hormigas, la importancia relativa de las feromonas (α) y la información heurística (β), la tasa de evaporación de feromonas (ρ), y la cantidad de feromona depositada (Q). Su correcta calibración es esencial para el rendimiento del algoritmo.

5. Conclusión

Los algoritmos de computación inteligente, tanto evolutivos como de enjambre, proporcionan herramientas robustas y adaptables para la solución de problemas de optimización complejos. Su naturaleza paralela y basada en poblaciones les permite explorar eficientemente grandes espacios de búsqueda, encontrando aplicaciones en campos tan diversos como la logística, el diseño de ingeniería y el aprendizaje automático.