Fundamentos de computación evolutiva E-Book

Enrique J. Carmona Suárez

• Herausgeber: Marcombo
• Kategorie: Bildung
• Sprache: Spanisch
• Veröffentlichungsjahr: 2021

Seitenzahl: 857

Beschreibung

La computación evolutiva puede mejorar su vida y la del resto de personas. ¿Quiere saber cómo? Adéntrese en este libro y descubra la computación evolutiva, una rama de la inteligencia artificial formada por una familia de algoritmos de optimización global: los algoritmos evolutivos. Inspirados en la evolución natural, los algoritmos evolutivos son capaces de obtener soluciones equiparables a las de expertos humanos en gran variedad de problemas. Además, son atractivos por aportar soluciones novedosas y brillantes que podrían ser difíciles de lograr por un humano. A lo largo de las últimas décadas, han surgido diferentes variantes de algoritmos evolutivos como resultado del gran interés que han despertado en la comunidad científica. En esta guía encontrará explicaciones detalladas de: oLas subáreas de la computación evolutiva, desde las ideas pioneras hasta las más actuales y novedosas. oLos principales tipos de algoritmos evolutivos. oLas técnicas avanzadas que dotan a estos algoritmos de mayor potencia y versatilidad. Si quiere conseguir una perspectiva global sobre la computación evolutiva, tiene a su alcance el libro adecuado: no pierda la oportunidad de leerlo. Los autores del libro son profesores titulares en el área de Ciencia de la Computación e Inteligencia Artificial y pertenecen al Departamento de Inteligencia Artificial de la Universidad Nacional de Educación a Distancia (UNED). Además de su actividad en docencia, realizan investigación en diferentes campos de la inteligencia artificial y de la computación evolutiva.

Leseprobe

Fundamentos de la computación evolutiva

© 2020 Enrique J. Carmona Suárez y Severino Fernández Galán

Primera edición, 2020

© 2020 MARCOMBO, S. L.

www.marcombo.com

Diseño de la cubierta: ENEDENÚ DISEÑO GRÁFICO

Correctora: Laura Seonae

Directora de producción: Ma Rosa Castillo

«Cualquier forma de reproducción, distribución, comunicación pública o transformación de esta obra solo puede ser realizada con la autorización de sus titulares, salvo excepción prevista por la ley. Diríjase a CEDRO (Centro Español de Derechos Reprográficos, www.cedro.org) si necesita fotocopiar o escanear algún fragmento de esta obra.»

ISBN: 978-84-267-3334-4

Producción del ePub: booqlab

A Inma, mi motor evolutivoEnrique J. Carmona Suárez

A mi esposa María y a mi hija Daira, con todo mi amorSeverino Fernández Galán

Índice general

Prólogo

I Algoritmos evolutivos

1 Introducción a la computación evolutiva

1.1 Inspiración en la biología

1.1.1 Teoría de la evolución

1.1.2 Del ADN a las proteínas

1.1.3 Reproducción

1.1.4 Mutación

1.2 Historia de la computación evolutiva

1.3 Algoritmo evolutivo canónico

1.3.1 Representación de individuos

1.3.2 Función de adaptación

1.3.3 Población

1.3.4 Inicialización de la población

1.3.5 Selección de padres

1.3.6 Operadores de variación

1.3.7 Selección de supervivientes

1.3.8 Condición de terminación

1.4 Algoritmos evolutivos como métodos de búsqueda

1.5 Campos de aplicación de la computación evolutiva

1.5.1 Aplicaciones en clasificación

1.5.2 Aplicaciones en control

1.5.3 Aplicaciones en diseño

1.5.4 Aplicaciones en planificación

1.5.5 Aplicaciones en simulación

2 Algoritmos genéticos

2.1 Ejemplo introductorio: el problema del viajante

2.2 Representación de individuos

2.2.1 Representación binaria

2.2.2 Representación entera

2.2.3 Representación real

2.2.4 Representación mediante permutaciones

2.3 Inicialización de la población

2.4 Selección de padres

2.4.1 Selección proporcional al valor de adaptación

2.4.2 Selección por ordenación

2.4.3 Selección por torneo

2.4.4 Muestreo de distribuciones de probabilidad

2.5 Recombinación

2.5.1 Operadores de recombinación para representación binaria

2.5.1.1 Cruce por un punto

2.5.1.2 Cruce por n puntos

2.5.1.3 Cruce uniforme

2.5.2 Operadores de recombinación para representación entera

2.5.3 Operadores de recombinación para representación real

2.5.3.1 Recombinación discreta

2.5.3.2 Recombinación aritmética

2.5.4 Operadores de recombinación para representación mediante permutaciones.

2.5.4.1 Cruce por orden

2.5.4.2 Cruce por ciclos

2.5.4.3 Cruce parcialmente mapeado

2.5.4.4 Cruce por enlaces

2.6 Mutación

2.6.1 Operadores de mutación para representación binaria

2.6.2 Operadores de mutación para representación entera

2.6.3 Operadores de mutación para representación real

2.6.4 Operadores de mutación para representación mediante permutaciones

2.6.4.1 Mutación por intercambio

2.6.4.2 Mutación por inserción

2.6.4.3 Mutación por mezcla

2.6.4.4 Mutación por inversión

2.7 Selección de supervivientes

2.8 Algoritmos de estimación de distribuciones

2.9 Ejemplo de aplicación: el problema del viajante

3 Estrategias evolutivas

3.1 Introducción: algoritmo EE-(1+1)

3.2 Estrategia evolutiva estándar

3.3 Representación de individuos

3.4 Inicialización de la población

3.5 Selección de padres

3.6 Recombinación

3.7 Mutación

3.7.1 Interpretación geométrica

3.7.2 Mutación no correlacionada de 1-tamaño de paso

3.7.3 Mutación no correlacionada de n-tamaños de paso

3.7.4 Mutación correlacionada

3.8 Selección de supervivientes

3.9 Variantes de estrategias evolutivas

3.9.1 CMA-ES: Estrategia evolutiva basada en la adaptación de la matriz de covarianza

3.10 Ejemplo de aplicación: problema de resolución de ecuaciones diferenciales

4 Programación evolutiva

4.1 Ejemplo introductorio: el problema de la hormiga artificial

4.2 Representación de individuos

4.3 Inicialización, selección de padres y recombinación

4.4 Mutación

4.5 Selección de supervivientes

4.6 Ejemplo de aplicación: diseño de redes neuronales artificiales

4.6.1 Introducción a las redes neuronales artificiales

4.6.2 Redes neuronales artificiales evolutivas

4.6.2.1 Evolución de los pesos de las conexiones

4.6.2.2 Evolución de la topología

4.6.2.3 Evolución conjunta de pesos y topología: EPNet

5 Evolución diferencial

5.1 Ejemplo introductorio

5.2 Evolución diferencial canónica.

5.3 Representación de individuos

5.4 Algoritmo clásico en ED: “DE/rand/1/bin”

5.5 Inicialización de la población

5.6 Selección de padres

5.7 Operadores de variación

5.7.1 Mutación

5.7.2 Recombinación (discreta o binomial)

5.8 Selección de supervivientes

5.9 Otras variantes en evolución diferencial

5.9.1 Formas de seleccionar el vector base

5.9.2 Incremento del número de diferenciales

5.9.3 Otros tipos de recombinación

5.9.4 Otras variantes usadas en entornos complejos

5.10 Aspectos prácticos en evolución diferencial

5.10.1 Inicialización de la población

5.10.2 Restringir la búsqueda al espacio de búsqueda

5.10.3 Acerca del valor de F

5.10.4 Acerca del valor de CR

5.10.5 Recomendaciones generales

5.11 Aplicaciones

5.12 Ejemplo de aplicación: optimización de una función multimodal

6 Programación genética

6.1 Ejemplo introductorio: regresión simbólica

6.2 Algoritmo estándar en programación genética

6.3 Representación de individuos

6.4 Inicialización de la población

6.4.1 Método de crecimiento uniforme

6.4.2 Método de crecimiento no uniforme

6.4.3 Método de crecimiento mixto

6.5 Selección de padres

6.6 Operadores de variación

6.6.1 Reproducción

6.6.2 Recombinación

6.6.3 Mutación

6.6.4 Mutación vs. recombinación

6.7 Selección de supervivientes

6.8 Funciones definidas automáticamente

6.9 El efecto engorde

6.10 Variantes

6.10.1 Evolución gramatical

6.10.2 Programación de expresiones de genes

6.11 Ejemplo de aplicación: diseño de circuitos electrónicos analógicos

6.11.1 Definición del problema

6.11.2 Diseño de circuitos analógicos basado en EG

7 Sistemas clasificadores evolutivos

7.1 Ejemplo introductorio: el multiplexor

7.2 Sistema clasificador evolutivo genérico

7.3 Sistema clasificador evolutivo basado en fuerza: ZCS

7.4 Sistema clasificador evolutivo basado en exactitud: XCS

7.5 Enfoque tipo Pittsburgh

7.6 Representaciones alternativas de reglas

7.6.1 Representación basada en intervalos

7.6.2 Representación basada en hiperelipsoides

7.6.3 Representación basada en envolturas convexas

7.6.4 Representación basada en redes neuronales

7.6.5 Representación desordenada

7.6.6 Representación basada en expresiones S

7.6.7 Representación basada en expresiones de genes

7.6.8 Representación basada en lógica difusa

7.7 Ejemplo de aplicación: diagnóstico de cáncer

8 Algoritmos meméticos

8.1 Introducción

8.2 Características de un algoritmo memético

8.2.1 Heurísticas y metaheurísticas

8.2.2 Algoritmo memético canónico

8.3 Búsqueda local

8.3.1 Espacios de búsqueda combinatorios

8.3.2 Espacios de búsqueda continuos

8.4 Algoritmos meméticos basados en la hibridación de un algoritmo evolutivo

8.4.1 Representación

8.4.2 Inicialización de la población

8.4.3 Operadores de variación basados en conocimiento

8.4.4 Operadores de selección basados en conocimiento

8.5 Aspectos prácticos de implementación en algoritmos meméticos

8.5.1 Elección del algoritmo de búsqueda local

8.5.2 Frecuencia de la búsqueda local

8.5.3 Probabilidad de la búsqueda local

8.5.4 Intensidad de la búsqueda local

8.5.5 Coste de la función de adaptación

8.5.6 Manejo de la pérdida de diversidad

8.6 Algoritmos meméticos avanzados

8.7 Aplicaciones de los algoritmos meméticos

9 Evaluación de algoritmos evolutivos

9.1 Qué evaluar en un algoritmo evolutivo

9.2 Índices promedio de prestaciones

9.2.1 Tasa de éxito

9.2.2 Valor de adaptación medio del mejor individuo

9.2.3 Tiempo medio para alcanzar el éxito

9.3 Medidas de robustez

9.3.1 Robustez a cambios del valor de un parámetro

9.3.2 Robustez a cambios de la instancia de un problema

9.3.3 Robustez frente a las diferentes ejecuciones realizadas

9.4 Estudio del comportamiento estadístico

9.4.1 Margen de error e intervalo de confianza

9.4.2 Test de hipótesis

9.5 Visualización de resultados

9.5.1 Curva de progreso

9.5.2 Comportamiento frente al cambio de escala del problema

9.5.3 Otras formas de visualizar resultados

9.6 Uso de problemas de referencia para evaluar AEs

II Técnicas avanzadas en computación evolutiva

10 Manejo de restricciones

10.1 Región factible

10.2 Tipos de problemas que manejan restricciones

10.2.1 Problemas de optimización libre de restricciones

10.2.2 Problemas de optimización con restricciones

10.2.3 Problemas de satisfacción de restricciones

10.3 Manejo de restricciones en algoritmos evolutivos

10.3.1 Funciones de penalización

10.3.1.1 Penalización estática

10.3.1.2 Penalización dinámica

10.3.1.3 Penalización adaptativa

10.3.2 Funciones decodificadoras

10.3.3 Separación de función objetivo y restricciones

10.3.3.1 Memoria conductual

10.3.3.2 Reglas de factibilidad

10.3.3.3 Ordenación estocástica

10.3.3.4 Método ε-restringido

10.3.4 Operadores especiales que garantizan la factibilidad

10.3.4.1 Operadores que preservan la factibilidad

10.3.4.2 Operadores de reparación

11 Mantenimiento de la diversidad

11.1 Algoritmos evolutivos paralelos de grano grueso

11.2 Algoritmos evolutivos paralelos de grano fino

11.3 Reparto de adaptación

11.4 Restricción del emparejamiento

11.4.1 Métodos tradicionales de restricción del emparejamiento

11.4.2 Generalización del método de restricción del emparejamiento

11.5 Agrupamiento

11.5.1 Variantes del método original de agrupamiento

11.5.2 Generalización del método de agrupamiento

11.5.2.1 Agrupamiento generalizado adaptativo basado en diversidad

11.5.2.2 Agrupamiento generalizado autoadaptativo

12 Configuración de parámetros

12.1 Sintonización de parámetros

12.1.1 Inconvenientes de la sintonización manual

12.1.2 Definición del problema y nomenclatura

12.1.3 Taxonomía de métodos de sintonización

12.1.4 Ejemplos de métodos de sintonización de parámetros

12.1.4.1 Métodos de competición

12.1.4.2 Meta-optimizadores

12.1.4.3 Métodos basados en modelo

12.1.4.4 El método LUS

12.1.4.5 Consideraciones finales

12.2 Control de parámetros

12.2.1 Introducción al control de parámetros

12.2.2 Taxonomía de métodos de control de parámetros

12.2.3 Ejemplos de control de parámetros

12.2.3.1 Tamaño de la población

12.2.3.2 Función de adaptación.

12.2.3.3 Cruce

12.2.3.4 Mutación

12.2.3.5 Selección de supervivientes

12.2.3.6 Modificación de varios parámetros simultáneamente

12.2.3.7 Consideraciones finales

13 Problemas multiobjetivo

13.1 Dominancia y frente de Pareto

13.2 Tipos de algoritmo evolutivo multiobjetivo

13.2.1 Técnicas “a priori”

13.2.2 Técnicas progresivas

13.2.3 Técnicas “a posteriori”

13.2.3.1 Muestreo independiente

13.2.3.2 Selección por criterio

13.2.3.3 Función de adaptación mediante dominancia

13.3 Técnicas avanzadas en algoritmos evolutivos multiobjetivo

13.3.1 AEMOs basados en descomposición

13.3.2 AEMOs meméticos

13.3.3 Tratamiento de restricciones mediante AEMOs

13.3.4 Aplicación de AEMOs a problemas multimodales

13.3.5 Aplicación de AEMOs a problemas dinámicos

13.3.5.1 Mantenimiento de la diversidad

13.3.5.2 Introducción de diversidad tras un cambio en la función de adaptación

13.3.5.3 Predicción de cambios en la función de adaptación

13.3.5.4 Uso de memoria

13.3.5.5 Poblaciones múltiples

13.4 Ejemplo de aplicación: asignación de horarios de clase

14 Modelos matemáticos de algoritmos evolutivos

14.1 Teorema del esquema

14.2 Cadenas de Markov

14.2.1 Modelo de Markov para selección uniforme

14.2.2 Modelo de Markov para un algoritmo genético estándar

14.2.3 Modelo de Markov para estados agrupados

14.3 Sistemas dinámicos

14.3.1 Sistema dinámico para un algoritmo genético estándar

14.4 Métodos reduccionistas

14.5 Mecánica estadística

14.6 Espacios de búsqueda continuos

Anexo A: Traducción de términos relevantes del libro

Bibliografía

Prólogo

La computación evolutiva es una rama de la inteligencia artificial que aborda la resolución automática de problemas de optimización. Para tal fin, se inspira en la evolución natural de cara a diseñar algoritmos, denominados algoritmos evolutivos, que permitan encontrar soluciones óptimas o casi óptimas de forma eficiente. Una muestra del enorme interés que ha suscitado la computación evolutiva en la comunidad científica internacional es el importante número de congresos y revistas científicas que están dedicados al estudio y divulgación de esta área.

Lo que hace atractivos a los algoritmos evolutivos no es solo su capacidad de obtener soluciones equiparables a las de expertos humanos en gran variedad de campos, sino también la sorprendente facilidad con que aportan soluciones novedosas y brillantes que quedan fuera del razonamiento humano. Por ejemplo, algunas antenas diseñadas mediante algoritmos evolutivos se han utilizado en misiones espaciales de la NASA.

El presente libro trata de las bases de la computación evolutiva, intentando dar una perspectiva global del campo. Los principales tipos de algoritmos evolutivos son revisados en detalle y, además, se explican una serie de técnicas avanzadas que dotan a estos algoritmos de mayor potencia y versatilidad. En cada capítulo se aportan gran cantidad de referencias bibliográficas que permiten profundizar en el conocimiento de cada uno de los temas tratados. Este libro puede ser de utilidad para estudiantes, programadores o investigadores interesados en adquirir un conocimiento amplio de la computación evolutiva o en desarrollar nuevos métodos evolutivos que mejoren los ya existentes.

El libro queda dividido en dos partes. La parte I (capítulos 1-9) se titula “Algoritmos evolutivos” y repasa las variantes más importantes que han aparecido en computación evolutiva a lo largo de los años. La parte II (capítulos 10-14) lleva el título de “Técnicas avanzadas en computación evolutiva” y detalla diferentes métodos surgidos gracias a la investigación desarrollada en determinadas subáreas de la computacion evolutiva. El trabajo relacionado con cada subárea es revisado de manera exhaustiva, desde las ideas pioneras hasta las más actuales y novedosas, pasando por aquellas que supusieron un avance destacado en su tiempo. Al final de cada capítulo del libro se incluye una serie de ejercicios propuestos de interés.

La parte I sobre “Algoritmos evolutivos” consta de los siguientes capítulos:

• El “capítulo 1: Introducción a la computación evolutiva” comienza describiendo cómo diferentes aspectos de la biología y la evolución natural han servido de inspiración a la computación evolutiva. A su vez, se realiza un repaso histórico de esta disciplina. Seguidamente, se explican las fases de un algoritmo evolutivo canónico, encaminadas a desarrollar un tipo particular de búsqueda en un espacio de estados. Finalmente, se clasifican los distintos campos de aplicación de la computación evolutiva y se revisan algunas de las aplicaciones más relevantes a que ha dado lugar.

• El “capítulo 2: Algoritmos genéticos” explica la variante más popular de los algoritmos evolutivos. Se hace énfasis en cómo realiza la representación de individuos, la inicialización de la población, la selección de padres, la recombinación, la mutación y la selección de supervivientes. Esta misma estructura se repite en los capítulos siguientes de la parte I.

• El “capítulo 3: Estrategias evolutivas” describe una nueva variante de algoritmo evolutivo cuya principal característica es la de incorporar ciertos parámetros relacionados con la mutación en el propio cromosoma de cada individuo y hacerlos evolucionar junto con el resto de variables del problema. Esta forma de hacer evolucionar las variables junto con los parámetros de estrategia del propio algoritmo evolutivo es lo que se conoce como autoadaptación.

• El “capítulo 4: Programación evolutiva” trata otra variante de la computación evolutiva que se caracterizó inicialmente por una forma muy concreta de representar los individuos: usando máquinas de estados finitos.

• El “capítulo 5: Evolución diferencial” aborda una nueva variante que, a pesar de ser la última en entrar en la familia de algoritmos evolutivos, ha alcanzado un gran éxito en la actualidad en problemas de optimización definidos en espacios de búsqueda continuos.

• El “capítulo 6: Programación genética” describe un nuevo paradigma evolutivo caracterizado por abordar un objetivo más ambicioso que las variantes descritas anteriormente. Se trata ahora de optimizar, no solo los parámetros de un modelo, sino también la estructura del propio modelo. Esto da lugar también a una nueva forma de representar los individuos basada en árboles.

• El “capítulo 7: Sistemas clasificadores evolutivos” describe cómo se puede utilizar aprendizaje por refuerzo conjuntamente con técnicas evolutivas para desarrollar sistemas basados en reglas que permitan abordar problemas de clasificación.

• El “capítulo 8: Algoritmos meméticos” explica la hibridación de técnicas evolutivas con otras técnicas de búsqueda que permiten incluir conocimiento del dominio. Es interesante reseñar que esta idea ha dado lugar a algoritmos muy eficaces a la hora de alcanzar soluciones óptimas.

• Por último, el “capítulo 9: Evaluación de algoritmos evolutivos” analiza cómo se debe evaluar adecuadamente el rendimiento de un algoritmo evolutivo. No solo interesa evaluar la calidad de la mejor solución obtenida, sino también la rapidez con la que se obtiene.

La parte II sobre “Técnicas avanzadas en computación evolutiva” contiene los capítulos siguientes:

• El “capítulo 10: Manejo de restricciones” revisa una serie de técnicas evolutivas que resultan de utilidad para abordar problemas de optimización con restricciones. Debido a que muchos de los problemas de optimización que se presentan en el mundo real están sujetos a restricciones de diverso tipo, este capítulo resulta de gran interés práctico.

• El “capítulo 11: Mantenimiento de la diversidad” aborda una de las cuestiones capitales en computación evolutiva: cómo alcanzar el equilibrio que debe existir entre la exploración de nuevas regiones del espacio de búsqueda y la explotación de las mejores soluciones ya encontradas. Este equilibrio es difícil de conseguir, ya que depende de la complejidad del problema particular de optimización abordado. Por un lado, se puede caer en una convergencia prematura del algoritmo y, por otro lado, en una búsqueda aleatoria o casi aleatoria de carácter ineficiente.

• El “capítulo 12: Configuración de parámetros” describe diferentes técnicas dedicadas a determinar cuál es la mejor configuración de parámetros de un algoritmo evolutivo que garantice, no solo el éxito en la búsqueda de la solución, sino que dicho éxito se consiga también de la forma más eficiente posible.

• El “capítulo 13: Problemas multiobjetivo”, al igual que el capítulo sobre manejo de restricciones, es de gran interés práctico. Hay problemas del mundo real que cuentan con varios objetivos dependientes entre sí que hay que optimizar. Las soluciones de interés en estos problemas son las que conforman el denominado conjunto de Pareto, es decir, aquellas que no están dominadas por otras soluciones en el espacio de búsqueda completo. El reto de los algoritmos evolutivos multiobjetivo es aproximarse tanto como se pueda al conjunto de Pareto, aportando un conjunto de soluciones no dominadas lo más diverso posible.

• Finalmente, para concluir el libro, el “capítulo 14: Modelos matemáticos de algoritmos evolutivos” presenta un punto de vista teórico de la computación evolutiva. Para tal fin, se revisan una serie de modelos que intentan predecir el comportamiento de la población de individuos de un algoritmo evolutivo. Por tanto, este capítulo ayuda al lector a adquirir una perspectiva más formal del funcionamiento de un algoritmo evolutivo.

Los autores del libro somos profesores titulares en el área de Ciencia de la Computación e Inteligencia Artificial y pertenecemos al Departamento de Inteligencia Artificial de la Universidad Nacional de Educación a Distancia (UNED). Desde mediados de los 90 hemos impartido docencias y realizado investigación en diferentes campos de la inteligencia artificial, en general, y de la computación evolutiva, en particular. Concretamente, el presente libro es el resultado de la docencia e investigación llevadas a cabo durante más de una década en el contexto de la asignatura “Computación Evolutiva”, perteneciente al Máster Universitario en Investigación en Inteligencia Artificial, que se imparte en la Escuela Técnica Superior de Ingeniería Informática de la UNED.

El esfuerzo que los autores hemos dedicado a la redacción de este libro ha sido realmente inmenso, pero habría resultado estéril si no hubiéramos contado con la colaboración, en mayor o menor grado, de una serie de personas que han enriquecido nuestra visión de la computación evolutiva. Sus comentarios, consejos o ideas han sido una fuente de inspiración que se ha visto reflejada en cada página del libro. En este sentido, los autores deseamos transmitir nuestro más sincero agradecimiento a los profesores del Departamento de Inteligencia Artificial de la UNED, en especial, a José Ramón Álvarez Sánchez, José Manuel Cuadra Troncoso y Emilio Letón Molina. Asimismo, Severino Fernández Galán hace extensivo dicho agradecimiento a Ole Jakob Mengshoel. Por último, nos gustaría resaltar la enriquecedora interacción con nuestros alumnos de máster y doctorado, que ha sido determinante a la hora de emprender y acabar la redacción de este libro.

Enrique J. Carmona Suárez y Severino Fernández Galán

Madrid, noviembre de 2019

Parte I

Algoritmos evolutivos

Capítulo 1

Introducción a la computación evolutiva

La computación evolutiva [Bäck et al., 2000a, Bäck et al., 2000b, Eiben & Smith, 2003, de Jong, 2006] es una rama de las ciencias de la computación que usa métodos de búsqueda estocástica basados en la evolución natural de cara a resolver problemas de optimización en campos como planificación, diseño o control, entre otros muchos. En estos campos son numerosas las aplicaciones de interés a que ha dado lugar la computación evolutiva en las últimas décadas. Los algoritmos evolutivos resultan atractivos tanto por su capacidad de obtener soluciones equiparables a las de expertos humanos como por la sorprendente facilidad con que aportan soluciones novedosas y brillantes que quedan fuera del razonamiento humano.

El presente capítulo, que introduce los conceptos básicos utilizados en computación evolutiva y ofrece una perspectiva global de la misma, queda organizado del siguiente modo. En primer lugar, la sección 1.1 revisa los conceptos fundamentales de la evolución natural en los que se inspira la computación evolutiva. Seguidamente, la sección 1.2 repasa el desarrollo histórico de la computación evolutiva. La sección 1.3 trata diferentes aspectos de carácter genérico de un algoritmo evolutivo canónico. A continuación, la sección 1.4 analiza los algoritmos evolutivos como método de búsqueda en un espacio de estados. Por último, la sección 1.5 revisa un conjunto relevante de aplicaciones a que ha dado lugar la computación evolutiva en diferentes dominios del mundo real.

1.1 Inspiración en la biología

La computación evolutiva es un área de investigación que trata de resolver problemas inspirándose en el proceso de la evolución natural. Por ello, puede resultar revelador realizar un primer acercamiento a cómo la teoría de la evolución, tanto a nivel macroscópico como microscópico, permite explicar el origen de la diversidad biológica y describir cuáles son, y cómo actúan, los mecanismos más importantes que intervienen en el proceso evolutivo.

1.1.1 Teoría de la evolución

El conocido libro El origen de las especies (The origin of species en inglés) o, más exactamente, El origen de las especies mediante la selección natural o la conservación de las razas favorecidas en la lucha por la vida, fue escrito por Charles Darwin en 1859 [Darwin, 1859]. En dicho libro, el autor expuso por primera vez sus ideas científicas sobre la teoría de la evolución y la selección natural. La teoría de la evolución fue admitida por la comunidad científica aun en vida de su autor, y la selección natural se convirtió en la explicación general del proceso de evolución, formando en la actualidad la base del pensamiento evolucionista contemporáneo. Una versión adaptada de su pensamiento constituye la base de la biología moderna y, a partir de ella, se consigue obtener una explicación lógica unificadora de la biodiversidad.

En la evolución, desde un punto de vista macroscópico, la selección natural juega un papel crucial: dado un entorno que puede alojar un número limitado de individuos, que poseen el instinto básico de reproducirse, el mecanismo de selección favorecerá a aquellos individuos con mayor aptitud para reproducirse. Normalmente, esta aptitud reproductiva es directamente proporcional a la capacidad de los individuos para competir por los recursos. Individuos más competitivos tienen más probabilidad de sobrevivir y, por tanto, de reproducirse. Es lo que se conoce como supervivencia del más apto.

Si bien la selección natural es un mecanismo crucial para que exista evolución, esta requiere también de variación genética. Aquí entra en juego la genética molecular, aportando el punto de vista microscópico de la evolución. De acuerdo a la genética, cada individuo es una entidad dual: sus propiedades fenotípicas expresan lo que marcan sus genes. El fenotipo corresponde al conjunto de propiedades morfológicas, fisiológicas, bioquímicas y conductuales exhibidas por un organismo y que directamente intervienen en la respuesta provocada por su relación con el entorno, incluyendo otros individuos, determinando así su grado de adaptación. De otro lado, los genes son unidades funcionales de herencia que codifican propiedades fenotípicas, es decir, el genotipo de un individuo codifica su fenotipo. En los organismos biológicos, la relación entre genes y características fenotípicas no es necesariamente una a una: un gen podría afectar a varios rasgos fenotípicos y, a su vez, un rasgo fenotípico podría ser expresado por más de un gen. Las variaciones fenotípicas son causadas siempre por variaciones genéticas, las cuales, a su vez, son provocadas por recombinación de genes durante la reproducción sexual o por mutación genética.

Las diferentes versiones de un mismo gen reciben el nombre de alelos. Por ejemplo, los humanos pueden tener los alelos A, B u O, que determinan diferentes propiedades de su tipo de sangre. La mayoría de los animales, incluyendo los humanos, están formados por células diploides, es decir, células que contienen una dotación doble de cromosomas (23 pares en el caso humano). Por tanto, existen dos alelos de cada gen en cada locus, uno heredado de la madre y el otro heredado del padre. Un locus es la localización de un gen en un cromosoma. Los humanos pueden ser AA, AB, AO, BB, BO u OO en el locus que codifica cada grupo de sangre. La excepción a esta regla son los gametos, células que intervienen en el proceso de reproducción, y que poseen una dotación simple de cromosomas (células haploides).

El genoma constituye la información genética completa de un individuo, mientras que el acervo genético es el conjunto de todos los genes de una especie o población. Los genes de cada individuo se agrupan en estructuras lineales formando cromosomas, 46 en el ser humano y, a su vez, la materia prima de la que está constituida cada cromosoma es el ADN (ácido desoxirribonucleico), es decir, la famosa doble hélice que codifica la totalidad de un organismo. El proceso mediante el cual un gen es capaz de expresar su fenotipo se abordará en la siguiente sección.

1.1.2 Del ADN a las proteínas

A finales del siglo XIX, Mendel fue el primero en investigar y comprender la herencia en organismos diploides. Posteriormente, la genética moderna ha añadido muchos detalles a la primera aportación mendeliana, pero aún hoy día estamos lejos de comprender completamente todos los procesos genéticos. Lo que sí se sabe es que toda la vida en la Tierra está basada en la molécula de ADN. Básicamente, el ADN es una doble cadena, adoptando la configuración de una doble hélice, en la que aparecen cuatro tipos de eslabones, denominados nucleótidos, cuyos nombres son: ácido adenílico, ácido guanílico, ácido citosílico y ácido timílico. Si comparásemos los cuatro tipos de nucleótidos con los caracteres de un alfabeto, se puede considerar el ADN total de un organismo como un libro en el que todas las letras, palabras, frases y párrafos están ensamblados conjuntamente, constituyendo una larga cadena que codifica todas las partes y funciones de dicho organismo.

En la analogía anterior, los genes, que son fragmentos de la cadena, equivalen aproximadamente a las frases del libro. Así, un gen es una secuencia de letras (nucleótidos) que codifica una determinada estructura o función de un organismo. Los genes están engarzados uno a continuación de otro en la larguísima cadena de ADN. Diferentes tripletas de nucleótidos en un gen forman los denominados codones, cada uno de los cuales codifica un aminoácido específico. Finalmente, una cadena de aminoácidos permite sintetizar una proteína.

Las proteínas constituyen el material más importante del que están hechos los seres vivos. El resto de componentes, tales como el agua, sales minerales, vitaminas, hidratos de carbono y grasas, son elementos auxiliares de las proteínas. De hecho, las proteínas no solo constituyen la mayoría de nuestra masa corporal, sin contar el agua, sino que de ellas parten nuestro calor, acciones, pensamientos y deseos, todo cuanto somos y cuanto hacemos. Estructuralmente, las proteínas son cadenas moleculares formadas por 20 tipos de eslabones, denominados aminoácidos, cuya longitud, aun siendo larga, no lo es tanto como la cadena de ADN. El orden de aminoácidos en una proteína determinada siempre es el mismo. Las cadenas proteínicas, una vez completas, se pliegan y retuercen sobre sí mismas como un ovillo. La manera de plegarse, a su vez, determina su forma, sus propiedades, así como su función. Por ejemplo, el gen para las proteínas musculares instruye a la maquinaria de elaborar proteínas para formar una larga fibra que presenta la propiedad de deslizarse respecto a sus fibras vecinas, lo cual permite la contracción muscular; en otro ejemplo, la hemoglobina, proteína transportadora del oxígeno en las células sanguíneas, se pliega según una configuración tridimensional, la única capaz de captar y liberar oxígeno.

Figura 1.1 Esquema del proceso de transformación de ADN en proteína. Inicialmente, se copia un gen en una molécula de ARN mensajero (ARNm) (a) y este se encarga de llevar la información hasta el ribosoma, cuya misión es decodificar la información del gen, contenida ahora en el ARNm, en su correspondiente proteína (b).

Atendiendo a los conocimientos de la genética molecular, el flujo de información de genotipo a fenotipo es de un solo sentido. Esto significa que las características fenotípicas no pueden alterar la información genotípica. Esto tiene varias consecuencias: (i) el material genético de la población solo puede surgir de los mecanismos que utiliza la evolución: selección natural, mutación y recombinación, pero nunca del aprendizaje de los individuos; (ii) todas las variaciones, mutación y recombinación, surgen a nivel genotípico, mientras que la selección depende de las prestaciones reales del individuo en un entorno dado, es decir, de aquellas que emergen a nivel fenotípico; y (iii) las primeras teorías que afirmaban que las características adquiridas durante el tiempo de vida de un individuo podían pasar a su descendencia a través del mecanismo de herencia, tal y como establece la denominada teoría de Lamarck, no tienen validez desde el punto de vista de la biología.

1.1.3 Reproducción

La combinación de las características de ambos padres en la descendencia de organismos diploides es una consecuencia de la fertilización mediante la fusión de dos gametos: el espermatozoide haploide se une con el óvulo, también haploide, para formar una célula diploide, el zigoto. En el zigoto, cada par de cromosomas está formado por uno procedente de la madre y otro del padre. El nuevo organismo se construye mediante la duplicación sucesiva del zigoto y, a partir de aquí, todas las células duplicadas conservan el mismo material genético.

En computación evolutiva, la combinación de características de dos individuos en la descendencia es llamada a menudo cruce o recombinación. No obstante, es importante destacar que este mecanismo no opera de forma estrictamente análoga a como lo hacen los organismos biológicos diploides. En estos últimos, el intercambio de material genético entre cromosoma no se produce solo durante la fertilización del óvulo con el espermatozoide, sino también en las glándulas sexuales, durante la formación de los gametos, mediante un proceso denominado meiosis: un tipo especial de división celular que produce cuatro células haploides a partir de una célula diploide. El proceso se visualiza esquemáticamente en la figura 1.2, aplicado solo a un par de cromosomas homólogos, uno del padre y otro de la madre, de la célula diploide. Así, inicialmente, cada uno de los dos cromosomas pertenecientes al par (figura 1.2.a) se duplica formando lo que se denomina una cromátida, es decir, dos cromosomas idénticos que quedan unidos por un punto común (centrómero), tal y como muestra la figura 1.2.b. Seguidamente, los dos pares de cromátidas se mueven para alinearse físicamente tomando como referencia el centrómero (figura 1.2.c) y, posteriormente, se rompen en un punto aleatorio para intercambiar su material genético (figura 1.2.d). El resultado de este proceso son cuatro cromosomas: dos idénticos a los cromosomas parentales y dos nuevos, resultado de mezclar el material genético heredado del padre y de la madre. Seguidamente, se producen dos fases de división celular. En la primera fase, se divide la célula obtenida en el paso anterior, dando lugar a dos nuevas células, cada una de las cuales contiene un par de cromosomas (figura 1.2.e); en la segunda fase, cada célula del paso anterior se divide a su vez en dos nuevas células, cada una de las cuales contiene un cromosoma del par de cromátidas correspondiente. Se obtienen así cuatro células haploides o gametos (figura 1.2.f). Finalmente, hay que tener en cuenta que, aunque todo el proceso se ha descrito a partir de una pareja de cromosomas homólogos, el proceso de meiosis real incluye toda la dotación de pares de cromosomas homólogos de la célula.

1.1.4 Mutación

La maquinaria celular que copia el ADN comete errores algunas veces. Cada uno de estos errores, que altera la secuencia de un gen, recibe el nombre de mutación. Hay muchos tipos de mutación. En una mutación puntual, una “letra” del código genético es cambiada por otra. También se pueden borrar o insertar en un gen algunos fragmentos de ADN. Finalmente, un gen o parte de él puede llegar a invertirse o duplicarse. La proteína resultante de la traducción del gen mutado se verá afectada por dicha mutación. El resultado será una proteína alterada, debido a la presencia de un eslabón (aminoácido) distinto en la cadena y, consecuentemente, su función también se verá alterada.

Figura 1.2 Esquema simplificado de los diferentes pasos implicados en el proceso de meiosis. Véase la sección 1.1.3 para más información.

Las mutaciones presentan una característica muy importante: son copiadas cuando se copia el ADN. Ahora bien, cuando se produce una mutación en el ADN de una célula somática, es decir, aquella célula no germinal que forma parte de los miles de millones de células que constituyen los órganos y tejidos de un organismo, lo más probable es que nunca se manifieste el cambio. Existe, no obstante, una excepción a este caso: la mutación que produce que una célula se vuelva cancerosa, produciéndose una duplicación incesante e incontrolada de la misma y de sus células hijas. De otro lado, cuando se produce una mutación en un gameto, la situación es completamente distinta. Concretamente, la división de un zigoto formado a partir de un gameto mutado provocará que la mutación sea copiada en todas las células descendientes. De este modo, todas las células corporales del adulto resultante tendrán una copia de la mutación con sus consecuencias correspondientes (positivas o negativas). Adicionalmente, todas las células sexuales de dicho adulto mostrarán también la mutación, pudiéndose transmitir así la mutación a la descendencia.

Aunque las mutaciones son raras, han sido, junto con el proceso de recombinación, los dos instrumentos más importantes del cambio evolutivo. Concretamente, las mutaciones beneficiosas han producido cambios en las proteínas de los organismos, que les han conferido alguna ventaja en su interacción con el ambiente. No obstante, la mayoría de las mutaciones son perjudiciales. Se descubren casi a diario nuevas enfermedades humanas producidas por mutaciones. Por tanto, el efecto beneficioso de este tipo de mecanismo en los individuos de una población solo puede analizarse desde el punto de vista de la selección natural y del efecto acumulado durante más de tres mil millones de años de evolución.

La evolución natural ha servido de inspiración, y aún hoy día lo sigue siendo, de los diferentes mecanismos y algoritmos asociados a los distintos paradigmas que conforman el campo de la computación evolutiva. Evidentemente, aunque son muchas las limitaciones y las derivaciones a las que ha dado lugar esta inspiración de “lo natural”, la metáfora está servida, tal y como muestra la figura 1.3 a modo de resumen.

Figura 1.3 La computación evolutiva como inspiración de la evolución biológica.

1.2 Historia de la computación evolutiva

El término “computación evolutiva” (CE) fue creado en 1990 durante la celebración de la primera conferencia de la serie Parallel Problem Solving from Nature en Dortmund (Alemania). Con este término se englobaron todas aquellas técnicas que aplicaban los principios de la evolución natural a la resolución automática de problemas. La presente sección repasa el desarrollo histórico de dichas técnicas, las más importantes de las cuales dieron lugar a distintas variantes de la CE que se desarrollaron de forma independiente durante varias décadas.

Alan M. Turing realizó en 1948 el primer intento significativo de diseñar un método basado en la evolución natural que permitiera obtener soluciones a problemas [Turing, 1992, página 12]. En concreto, Turing sugirió la idea de “búsqueda genética o evolutiva” como un medio para dotar de inteligencia a una máquina. En 1954, mientras trabajaba en el Instituto de Estudios Avanzados de Princeton, Nils A. Barricelli fue probablemente el primer investigador que utilizó una computadora para llevar a cabo experimentos sobre evolución artificial [Barricelli, 1954, Barricelli, 1957]. Posteriormente, en 1962, Hans J. Bremermann realizó destacables experimentos sobre “optimización mediante evolución y recombinación” en una computadora [Bremermann, 1962]. Una amplia y exhaustiva revisión de los trabajos pioneros en el campo de la CE se puede encontrar en [Fogel, 1998].

Las primeras variantes evolutivas de interés no empezaron a consolidarse hasta bien entrada la década de los 60 y principios de los 70. John H. Holland desarrolló en la Universidad de Michigan los algoritmos genéticos [Holland, 1975] y los sistemas clasificadores evolutivos (conocidos en inglés como learning classifier systems) [Holland, 1976]. Ingo Rechenberg y Hans P. Schwefel crearon en la Universidad Técnica de Berlín las estrategias evolutivas [Rechenberg, 1971, Schwefel, 1975]. Otra variante relevante se debe a Lawrence J. Fogel, quien propuso la programación evolutiva [Fogel, 1964, Fogel et al., 1966]. En el año 1964, Fogel realizó en la Universidad de California en Los Ángeles la primera tesis doctoral sobre CE [Fogel, 1964]. Aunque estas corrientes se desarrollaron de forma independiente durante varios años, fueron englobadas bajo el término “computación evolutiva” a principios de los 90. Una nueva variante surgió precisamente en esta época gracias al trabajo de John R. Koza en la Universidad de Stanford, quien desarrolló la programación genética [Koza, 1992]. Por último, la variante denominada evolución diferencial [Storn & Price, 1995, Storn & Price, 1997] fue desarrollada a mediados de la década de los 90 por Rainer Storn y Kenneth Price, alcanzando en la actualidad gran éxito y difusión debido a su simplicidad y eficiencia.

El principal motivo que históricamente provocó la aparición de variantes en CE fue el uso de tipos diferentes de representación para las soluciones o individuos. Mientras que los algoritmos genéticos utilizaron mayoritariamente cadenas binarias, los sistemas clasificadores evolutivos se basaron en el uso de reglas, las estrategias evolutivas emplearon vectores que combinaban variables reales y parámetros de estrategia, la programación evolutiva usó inicialmente máquinas de estados finitos y, por último, la programación genética se basó en representaciones con estructura de árbol.

1.3 Algoritmo evolutivo canónico

Un algoritmo evolutivo (AE) es un método de optimización inspirado en los postulados de la evolución biológica. A pesar de que existen distintas variantes de algoritmos evolutivos, la idea que subyace detrás de todas ellas es la misma: dada una función de calidad a ser optimizada, se crea aleatoriamente un conjunto de individuos o soluciones candidatas (población inicial) y se aplica la función de calidad como una medida del grado de adaptación de cada solución. Utilizando como criterio el valor del grado de adaptación, se selecciona un subconjunto de soluciones candidatas que desempeñarán el papel de padres de la descendencia. La descendencia se obtiene aplicando los operadores de variación adecuados y los nuevos individuos así obtenidos compiten con los antiguos para obtener un lugar en la población de la siguiente generación. Este proceso se repite hasta que se encuentra una solución candidata con suficiente calidad o hasta que se alcanza una condición de terminación establecida previamente. A modo de resumen, el algoritmo 1.1 muestra el pseudocódigo del algoritmo evolutivo canónico y, la figura 1.4, un diagrama de flujo de dicho pseudocódigo.

Obsérvese que en todo el proceso indicado anteriormente hay dos mecanismos fundamentales que forman la base de todos los paradigmas evolutivos. Por un lado, los operadores de variación (recombinación y mutación), que producen la diversidad genética necesaria para obtener nuevos individuos, es decir, para explorar nuevas soluciones en el espacio de búsqueda. Por otro lado, los operadores de selección de padres y de supervivientes, cuya función es la de emular el mecanismo biológico de la selección natural, es decir, favorecer que la calidad de la población de soluciones candidatas aumente a lo largo del tiempo. Además, nótese que algunos de los mecanismos implicados en el proceso evolutivo son estocásticos, es decir, su comportamiento, además de ser aleatorio, es función del tiempo. Esto ocurre con los operadores de selección, de recombinación y de mutación.

Algoritmo 1.1 Algoritmo evolutivo canónico.

Entrada: función a optimizar que representa el problema a resolver.

Salida: solución encontrada (soluc).

 1: begin

 2:   INICIALIZAR población;

 3:   EVALUAR individuos de población;

 4:   while not (condición_de_terminación) do

 5:     SELECCIONAR padres de la población;

 6:     RECOMBINAR pares de padres para obtener hijos;

 7:     MUTAR hijos para obtener descendencia;

 8:     EVALUAR individuos de descendencia;

 9:     SELECCIONAR_SSUPERVIVIENTES para obtener nueva población;

10:   end-while

11:   soluc ← Mejor individuo encontrado durante la ejecución;

12: end

Figura 1.4 Diagrama de flujo correspondiente a un algoritmo evolutivo canónico. El flujo de información indicado por la línea discontinua representa el hecho de que existen estrategias de selección de supervivientes que toman como entrada, además del conjunto de individuos de la descendencia, el conjunto de individuos de la población actual.

Por consiguiente, desde un punto de vista genérico, se puede hablar de una serie de conceptos, procedimientos y operadores que son comunes a todo AE. Los más importantes son los siguientes:

• representación de individuos

• función de adaptación (función de evaluación)

• población

• procedimiento de inicialización de individuos

• selección de padres

• operadores de variación

• selección de supervivientes (reemplazo)

• condición de terminación

1.3.1 Representación de individuos

El primer paso a la hora de diseñar un AE es definir la forma de representar los distintos individuos de la población o soluciones candidatas que participarán en el proceso evolutivo. Para ello es necesario establecer una correspondencia entre las soluciones candidatas en el dominio del problema original (fenotipos) y sus equivalentes en el dominio del AE (genotipos). Esta correspondencia ha de definirse en los dos sentidos, es decir, cómo una solución en el espacio original fenotípico se transforma en el espacio genético (codificación) e, inversamente, cómo una solución, perteneciente a este último espacio, se transforma en el primero (decodificación). Adicionalmente, habrá que decidir qué tipo de estructura de datos se utilizará en el espacio genotípico. Se supone que la representación de las soluciones en el espacio original vendrá dada por las especificaciones del problema. Hay que tener en cuenta que la búsqueda de la solución siempre se realiza en el espacio genotípico y que este puede ser muy diferente al espacio fenotípico.

Tal y como se verá en los capítulos siguientes, la representación de un individuo dependerá en gran medida del tipo de AE usado. Por ejemplo, con algoritmos genéticos, es típico utilizar cadenas de símbolos de tamaño fijo; con estrategias evolutivas y evolución diferencial, se utilizan vectores de variable real de tamaño fijo; en programación evolutiva, originariamente, se utilizaban representaciones en términos de máquinas de estados finitos y, en programación genética, se utilizan estructuras arbóreas de tamaño variable.

La terminología en CE usa muchos sinónimos para nombrar los elementos de los dos espacios (fenotípico y genotípico), y gran parte de ella procede directamente del campo de la evolución natural. Así, solución candidata, fenotipo e individuo son las etiquetas que se suelen utilizar para denotar puntos en el espacio de posibles soluciones o espacio fenotípico. De otro lado, genotipo, cromosoma e individuo, son las que se suelen utilizar para los puntos del espacio transformado o espacio genotípico. Se utiliza la etiqueta variable, locus (plural loci), posición o gen para designar cada una de las diferentes partes homogéneas (contenedores) que constituyen un individuo. Finalmente, se denomina valor o alelo al contenido almacenado en cada contenedor.

1.3.2 Función de adaptación

En CE, la función de adaptación es también conocida con el nombre de función de evaluación. Si el problema a resolver es de optimización, se suele también utilizar con frecuencia el término función objetivo. En este caso, la función de adaptación suele ser idéntica a la función objetivo dada o a una transformación de la misma.

Aunque el concepto de grado de adaptación de un individuo suele estar asociado a problemas de maximización, el individuo es mejor cuanto mayor sea su grado de adaptación, en general, se puede hablar de problemas de optimización para referirse tanto a problemas de maximización como de minimización. Desde un punto de vista matemático es inmediato intercambiar ambos tipos de problemas. Así, si se quiere transformar un problema de maximización (minimización), formalizado mediante f (x) , en un problema de minimización (maximización), formalizado mediante f′(x), se puede realizar alguna de las siguientes transformaciones:

•f′(x) =−f (x).

1.3.3 Población

La población representa el conjunto de soluciones en una generación determinada. Los individuos son objetos estáticos que ni cambian ni se adaptan. Al contrario, la población sí lo hace como resultado de incorporar a la generación (i + 1)-ésima nuevos individuos resultantes de aplicar operadores de variación a los individuos de la generación i-ésima. En oposición a los operadores de variación, que trabajan sobre individuos, los operadores de selección (selección de padres o de supervivientes) trabajan a nivel de población. En casi todas las aplicaciones de algoritmos evolutivos, el tamaño de la población es constante y no cambia durante el proceso evolutivo.

Finalmente, la diversidad de la población es una medida del número de soluciones fenotípicas diferentes presentes en la población. No obstante, existen también diferentes formas indirectas de medir la diversidad. Por ejemplo, contabilizando el número de valores diferentes del grado de adaptación de sus individuos, contando el número de genotipos diferentes existentes o usando medidas estadísticas tales como la entropía.

1.3.4 Inicialización de la población

La inicialización de la población tiene como objetivo el de crear la primera población de individuos. Esto se puede realizar aleatoriamente o utilizando diferentes heurísticas. Estas últimas inyectan conocimiento del dominio en el proceso de obtener la población inicial, permitiendo así generar una población de individuos con grados de adaptación relativamente altos ya desde el inicio. Si merece la pena o no el mayor esfuerzo computacional que supone esta segunda opción respecto de la primera, dependerá en todo momento de las especificaciones del problema concreto que se quiera resolver y del criterio del propio diseñador.

1.3.5 Selección de padres

El objetivo de la selección de padres es extraer un subconjunto de individuos de la población actual, en función de su calidad, que desempeñarán el papel de padres de la futura descendencia. Los individuos más adaptados tienen mayor probabilidad de ser seleccionados que aquellos menos adaptados pero, no obstante, estos últimos siempre tienen una probabilidad, aunque baja, de ser finalmente elegidos. Junto con la selección de supervivientes, son los dos mecanismos responsables de forzar la mejora de la calidad de los individuos de la población en sucesivas generaciones.

1.3.6 Operadores de variación

El papel de los operadores de variación es el de generar nuevos individuos (hijos) a partir de individuos ya existentes en la población (padres). Pueden ser de dos tipos: de mutación y de recombinación. Su implementación depende en gran medida de la representación elegida. De la misma forma, el uso de cada tipo de operador depende también del tipo de AE elegido. Así, el operador de mutación, por ejemplo, no suele utilizarse en programación genética; en algoritmos genéticos, se considera como un operador importante que aporta variedad a la población de genes y, en programación evolutiva, es el único operador de variación que se usa. Por su parte, el operador de recombinación es a menudo el único operador de variación que se utiliza en programación genética; en algoritmos genéticos suele ser el operador principal de búsqueda y, en programación evolutiva, nunca se usa.

El comportamiento de ambos tipos de operadores de variación es estocástico. Así, durante el proceso de recombinación, tanto la selección de los individuos a cruzar como los genes de cada par de padres a ser recombinados se hace aleatoriamente. Del mismo modo, durante el proceso de mutación, tanto la selección de los individuos a mutar como los genes de los individuos a ser mutados se hace también aleatoriamente.

1.3.7 Selección de supervivientes

El mecanismo de selección de supervivientes es similar al de selección de padres, pero se utiliza en una etapa distinta del ciclo evolutivo: una vez que se ha creado la descendencia de los padres seleccionados. Aunque el concepto de edad se utiliza en algunas ocasiones, el criterio de selección se suele basar en el grado de adaptación, favoreciendo aquellos individuos con calidad más alta. En oposición a la selección de padres, la selección de supervivientes es a menudo determinista. Por ejemplo, se podría establecer como criterio que, en cada generación, el conjunto formado por padres y descendencia se ordene de mayor a menor por su grado de adaptación y, finalmente, se elija un subconjunto con los individuos de grado de adaptación más bajo (asumiendo un problema de minimización). Otro criterio podría ser el de seleccionar como supervivientes solo la descendencia producida, asumiendo que el tamaño de esta es igual al de la población. En el primer caso, la selección estaría guiada por el grado de adaptación y, en el segundo caso, por la edad (cada individuo sobrevive una generación). La selección de supervivientes es también conocida en la literatura por el nombre de estrategia de reemplazo.

1.3.8 Condición de terminación

En primera instancia, parecería inmediato que la condición de terminación de un AE dependiera solo de si se alcanza o no la solución óptima del problema que se quiere resolver. No obstante, esto requiere que la solución óptima sea conocida de antemano y no siempre es así. En algunas ocasiones, se conoce la mejor solución al problema (pero no la óptima) o, en otras, se puede imponer un umbral de adaptación que, una vez alcanzado, la solución podría considerarse óptima. Sin embargo, dada la naturaleza estocástica de los algoritmos evolutivos, el algoritmo puede, en alguna ejecución, quedar atrapado indefinidamente en un óptimo local o, en otros casos, por especificaciones del problema, puede haber restricciones del tiempo máximo necesario para obtener una solución. Por consiguiente, es necesario añadir una condición de terminación que garantice que el algoritmo no se ejecuta indefinidamente. Generalmente, las opciones usadas para este propósito son las siguientes:

• El mejor individuo alcanza la solución o su grado de adaptación alcanza un umbral preestablecido.

• Transcurre un tiempo máximo medido, por ejemplo, en ciclos de CPU, número de generaciones o número de evaluaciones de la función de adaptación.

• Durante un periodo de tiempo de duración dado (medido en algunas de las formas indicadas en el punto anterior), la mejora del grado de adaptación del mejor individuo no varía o casi no varía (el rango de variación permanece por debajo de un valor umbral ϵ → 0).

• La diversidad de la población cae por debajo de un umbral dado.

Entonces, la condición de parada final se construye mediante un encadenamiento disyuntivo de la primera condición mencionada en la lista anterior y una o más de las restantes.

1.4 Algoritmos evolutivos como métodos de búsqueda

Una parte importante de los problemas que se plantean en campos como las ciencias de la computación o la inteligencia artificial se suelen abordar como procesos de búsqueda en un espacio de estados. Si un estado representa una solución candidata al problema planteado y se puede establecer matemáticamente la bondad de cada solución, la búsqueda perseguirá alcanzar el estado óptimo. A modo de ejemplo, esto ocurre en el problema del viajante, donde se busca un recorrido de longitud mínima entre varias ciudades que las visite una sola vez, partiendo y llegando a la misma ciudad. En el problema del viajante, cada estado se asocia a un recorrido particular entre las ciudades.

Formalmente, un problema de optimización está compuesto por una dupla, (Ω, f), donde Ω es el dominio de definición de una función f tal que:

y el objetivo es encontrar aquel elemento, x* ∈ Ω, que cumpla:

Esta definición se corresponde realmente con un problema de maximización, siendo idéntica la definición para un problema de minimización sin más que emplear f (x*) ≤ f (x) en la desigualdad (1.2).

Un AE se puede considerar como un proceso de búsqueda en un espacio de estados, Ω, donde cada elemento, x ∈ Ω, representa una solución candidata al problema planteado. Existe una función, f, definida a partir de la expresión (1.1), que mide la bondad de cada solución candidata. En el contexto de la CE, cada elemento x recibe el nombre de individuo y la función f se denomina función de adaptación (también conocida como función de evaluación). Cuando f admite una representación gráfica, dicha representación es denominada paisaje de adaptación (fitness landscape en inglés). El objetivo de un AE es encontrar una solución óptima al problema, x*. Esto no será siempre posible, ya que en general solamente será examinada una pequeña fracción de todo el espacio de soluciones candidatas. En concreto, únicamente una población finita de individuos es considerada en cada generación de un AE.

Los AEs tienen carácter estocástico, es decir, el mismo algoritmo aplicado al mismo problema particular no tiene por qué producir el mismo resultado en cada una de sus ejecuciones. Incluso puede tener lugar el efecto conocido como deriva genética (genetic drift en inglés), según el cual incluso un individuo muy adaptado podría con cierta probabilidad desaparecer de la población si se ve desfavorecido por el azar. El efecto combinado de la deriva genética y de la selección de individuos puede producir la pérdida prematura de diversidad en la población y, en consecuencia, la convergencia a un óptimo local, distinto del óptimo global.

Todo método de búsqueda en un espacio de estados queda caracterizado, por un lado, por la forma de generar el estado o estados iniciales y, por otro lado, por la manera de pasar del estado actual al estado siguiente. Los capítulos 2 al 8 del presente libro explican detalladamente diferentes aspectos de estos dos puntos para el caso de los AEs.

1.5 Campos de aplicación de la computación evolutiva

La CE ha dado lugar a numerosas aplicaciones de interés en diferentes dominios. Una exhaustiva revisión de dichas aplicaciones se puede encontrar en [Bäck et al., 2000a, capítulo 2], [Coello et al., 2002, capítulo 6] y [Chiong et al., 2012]. Todas estas aplicaciones se caracterizan por la búsqueda de una solución a un determinado problema, que proporcione un comportamiento óptimo respecto a determinado criterio. Esta sección divide las aplicaciones dependiendo de su pertenencia a uno de los siguientes tipos de tarea: clasificación, control, diseño, planificación y simulación. Dicha división no pretende ser exhaustiva, sino dar una idea general del amplio y significativo conjunto de aplicaciones que ha proporcionado la CE.

Muchas de las aplicaciones que se enumeran en esta sección, así como un buen número de otras aplicaciones de interés, se pueden encontrar en las actas de los principales congresos sobre CE:

•International Conference on Genetic Algorithms (ICGA), celebrada bianualmente desde 1985 hasta 1997.

•Annual Genetic Programming Conference (GP), celebrada desde 1996 hasta 1998.

•Genetic and Evolutionary Computation Conference (GECCO), celebrada anualmente a partir de 1999 tras surgir de la unión entre ICGA y GP.

•Annual Conference on Evolutionary Programming (EP), celebrada desde 1992 hasta 1998.

•IEEE International Conference on Evolutionary Computation (ICEC), celebrada anualmente desde 1994 hasta 1998.

•Congress on Evolutionary Computation (CEC), celebrado anualmente desde 1999 como resultado de la unión entre EP e ICEC.

•Parallel Problem Solving from Nature (PPSN), celebrado bianualmente desde 1990.

•Foundations of Genetic Algorithms (FOGA), celebrado bianualmente desde 1990.

Otra fuente de artículos sobre aplicaciones relevantes de la CE está constituida por un conjunto de revistas científicas internacionales, especializadas en el campo, como son:

•Evolutionary Computation, publicada por la editorial MIT Press desde el año 1993.

•IEEE Transactions on Evolutionary Computation, publicada por la IEEE Computational Intelligence Society desde el año 1997.

•Genetic Programming and Evolvable Machines, publicada por la editorial Springer desde el año 2000.

•Evolutionary Intelligence, publicada por la editorial Springer desde el año 2008.

1.5.1 Aplicaciones en clasificación

La visión artificial puede ser abordada a partir de métodos evolutivos [Cagnoni et al., 2008, Carmona et al., 2008]. Generalmente, los AEs aplicados en este campo permiten clasificar características de diferente nivel de complejidad existentes en una imagen.

El etiquetado léxico (grammatical tagging en inglés) es una tarea básica para el procesamiento del lenguaje natural, que se puede realizar partiendo de un punto de vista evolutivo [Alba et al., 2006]. Dado un texto, su etiquetado léxico consiste en clasificar cada una de las palabras del mismo según una etiqueta que indique su función léxica: artículo, nombre, verbo, etc. Por otra parte, el análisis sintáctico de textos (text parsing en inglés) también ha sido llevado a cabo a partir de AEs [Araujo, 2006]. Este tipo de análisis consiste en clasificar la estructura sintáctica correcta de una frase, dado un conjunto de estructuras sintácticas posibles.

Un sistema clasificador evolutivo [Holland, 1976, Sigaud & Wilson, 2007] es un enfoque que permite aprender un sistema basado en reglas a partir de la combinación de técnicas de aprendizaje por refuerzo y de técnicas evolutivas. Dadas ciertas entradas al sistema clasificador evolutivo, este debe producir unas salidas predeterminadas. Mediante aprendizaje por refuerzo se beneficia a las reglas que mejor lleven a cabo la tarea de clasificación. Un AE es el encargado de generar nuevas reglas y de seleccionar las mejores. El capítulo 7 del presente libro se centra en el estudio de los sistemas clasificadores evolutivos.

1.5.2 Aplicaciones en control

Se puede utilizar un AE como un módulo activo que participe en el proceso de control de un sistema. En particular, se han empleado controladores evolutivos para sistemas dinámicos [Fogel et al., 1966, de Jong, 1980, Ursem et al., 2002]. También existen sistemas de guía y sistemas de navegación que desarrollan métodos de control basados en técnicas evolutivas [Krishnakumar & Goldberg, 1992, Walker et al., 2003].

1.5.3 Aplicaciones en diseño

Se han aplicado AEs al diseño de redes neuronales artificiales [Miller et al., 1989, Fogel et al., 1990, Weiss, 1994, Yao, 1999]. En concreto, el diseño de la topología de la red y la búsqueda de los valores óptimos de los pesos asociados a sus conexiones han sido las dos tareas más estudiadas.

El problema del coloreado de grafos (graph coloring problem en inglés) consiste en, dado un grafo no dirigido donde existe como máximo un enlace entre dos nodos cualesquiera, asignar un color a cada nodo tal que dos nodos vecinos no posean el mismo color y el número de colores usado sea mínimo. Ejemplos de cómo se puede plantear este problema mediante métodos evolutivos se encuentran en [Eiben et al., 1998, Galinier & Hao, 1999, Malaguti et al., 2008].

Los AEs también han sido aplicados a proyectos de diseño estructural en ingeniería y arquitectura [Bramlette & Bouchard, 1991, Watabe & Okino, 1993, Kicinger et al., 2005, Chaquet et al., 2012], así como al diseño de circuitos electrónicos analógicos o digitales [Etter et al., 1982, Schaffer & Eshelman, 1993, Beielstein et al., 2002, Castejón & Carmona, 2018].

1.5.4 Aplicaciones en planificación

La determinación de rutas óptimas entre diferentes puntos es un problema típico de optimización combinatoria. Cuando el criterio a optimizar es simplemente la longitud de la ruta, se tiene el problema del viajante (traveling salesman problem en inglés) [Goldberg & Lingle, 1985, Davis, 1985a, Whitley et al., 1989], que ya fue definido brevemente en la sección 1.4.

La programación eficiente de tareas es un problema de planificación que ha sido abordado mediante AEs. Por ejemplo, en el problema de la secuenciación de operaciones en un taller (job shop scheduling problem en inglés) [Davis, 1985b, Yamada & Nakano, 1992, Vázquez & Whitley, 2000, Ponnambalam et al., 2001], el objetivo es calcular un orden de ejecución de un conjunto de operaciones sobre las máquinas de un taller, de manera que se minimice el tiempo total de realización del conjunto de operaciones programadas.

El empaquetado ordenado de objetos también se puede considerar desde un punto de vista evolutivo. A modo de ejemplo, en el problema de la mochila binario (binary knapsack problem en inglés) [Gordon et al., 1993, Michalewicz, 1994], dada una mochila con cierta capacidad y varios objetos con un determinado volumen y valor, se trata de determinar qué objetos hay que introducir en la mochila para maximizar el valor total de los objetos contenidos en la misma. En este problema se debe cumplir que la suma de los volúmenes de los objetos introducidos en la mochila no exceda la capacidad de la misma.

1.5.5 Aplicaciones en simulación

Con frecuencia resulta necesario simular el comportamiento del modelo de un sistema de cara a comprobar su validez. La CE ofrece el contexto apropiado para servir de marco de simulación de modelos