Computación bioinspirada Computación evolutiva José M. Sempere Departamento de Sistemas Informáticos y Computación Universidad Politécnica de Valencia

Computación Evolutiva 1. 2. 3. 4. 5. 6. 7. 8.

Algunos paradigmas evolutivos: Darwin, Lamarck y Baldwin Principales paradigmas de la computación evolutiva Esquema genérico de los algoritmos evolutivos Operadores genéticos y de selección. Mecanismos de competición Estrategias Evolutivas Algoritmos Genéticos Programación Genética y Evolutiva Sistemas de Aprendizaje de Clasificación

Bibliografía T. Mitchell. Mitchell. Machine Learning. Learning. McGrawMcGraw-Hill. 1997. A.Y. A.Y. Zomaya (Ed.) Ed.) Handbook of NatureNature-Inpired and Innovative Computing. Computing. Springer. Springer. 2006. L. Kallel, Kallel, B. Naudts, Naudts, A. Rogers (Eds.) Eds.) Theoretical Aspects of Evolutionary Computing. Computing. Springer. Springer. 2001

1

Evolución biológica: Darwin, Lamarck y Baldwin Si existen organismos que se reproducen, y Si la progenie hereda características de sus progenitores, y Si existen variaciones de características y Si el medio ambiente no admite a todos los miembros de una población en crecimiento Entonces aquellos miembros de la población con características menos adaptadas (según lo determine su medio ambiente) morirán con mayor probabilidad y Entonces aquellos miembros con características mejor adaptadas sobrevivirán más probablemente. Charles Robert Darwin (1809-1882)

El resultado de la repetición de este esquema a lo largo del tiempo es la evolución de las especies.

Los individuos pueden adquirir o mejorar caracteres físicos durante su vida y éstos son transmitidos a su descendencia. De esta forma, las especies evolucionan acumulando los caracteres útiles que han adquirido en vida sus antepasados.

Jean Baptiste Lamarck (1744-1829)

Evolución biológica: Darwin, Lamarck y Baldwin El “efecto Baldwin”: interrelación entre aprendizaje y evolución si existen cambios en el ambiente, la evolución tiende a favorecer individuos con la capacidad de aprender a adaptarse al nuevo medio ambiente acelerando cambios genéticos entre individuos parecidos James Mark Baldwin (1861-1934)

Las tres anteriores teorías han influenciado e inspirado distintos aspectos de la Computación Evolutiva

2

Principales paradigmas de la computación evolutiva • Estrategias evolutivas • Algoritmos genéticos • Programación genética • Programación evolutiva • Sistemas de aprendizaje de clasificación (Learning Classifier Systems) Las anteriores aproximaciones tienen en común algunos aspectos: (1) (2) (3) (4) (5)

Participan o se inspiran en algunas teorías biológicas sobre la evolución Incorporan el concepto de “población de individuos” Incorporan el concepto de “capacidad de un individuo” (fitness) Siguen el ciclo de nacimiento/defunción de individuos Incorporan técnicas para la herencia, la reproducción, la variación y la selección/competición entre individuos

Un esquema genérico para la computación evolutiva Resolución de un problema Π Paso 0: Construir una representación (individuo) para las soluciones potenciales del problema Π (codificación) t←0 Paso 1: Crear aleatoriamente una población inicial de individuos P(t) Paso 2: Evaluar la capacidad de cada individuo (fitness evaluation) Paso 3: Si la condición de terminación se cumple ir al Paso 5 Paso 4: Aplicar operadores genéticos y de selección sobre P(t) (opcionalmente) Aplicar mecanismos de competición (opcionalmente) Aplicar algoritmos de búsqueda local t ← t+1 Ir al paso 2 Paso 5: (opcionalmente) Si no se reinicia el proceso ir al paso 7 Paso 6: t ← 0 Generar una población inicial modificada P(t) Ir al Paso 2 Paso 7: Considerad el mejor individuo de P(t) como la solución a Π

3

De los fenotipos a los genotipos … Dado el problema Π definiremos F como el espacio de soluciones del problema (fenotipos) y G como el espacio de soluciones codificadas del problema (genotipos)

x… x1

σ

Ψ

x2 x3 xn

y…

g

F

población inicial

x… ω operadores genéticos

G

g es una función de codificación ω es una función de reproducción σ es una función de selección Ψ es una función de reemplazamiento

Operadores Genéticos • Recombinación (“crossover”) La recombinación pretende recoger la información almacenada por dos individuos y transmitirla a un descendiente. Si tomamos cadenas binarias podemos establecer (entre otras) dos operaciones (a) Cruce puntual (“point crossover”) 10010101101 100101 01101001011 001101 (punto de cruce)

10010101101 001101

(a) Cruce uniforme (“uniform crossover”) máscara 001001001001001001 padres 111111111111111111 000000000000000000

110110110110110110

4

Operadores Genéticos • Recombinación Si tomamos vectores n-dimensionales podemos establecer (entre otras) las siguientes operaciones (x1, x2, …, xn) (padres) (y1, y2, …, yn)

(z1, z2, …, zn) (descendiente)

(a) Recombinación aritmética

(b) Recombinación geométrica

( x + yi ) zi = i 2

zi = xi ⋅ yi

(c) Recombinación plana zi = α ⋅ xi + (1 − α ) ⋅ yi (α es un valor aleatorio entre 0 y 1)

(e) Recombinación borrosa (“fuzzy”)

(d) Recombinación BLX-α zi = ri + β ⋅ ( si − ri ) ri = min ( xi , yi ) − α ⋅ xi − yi si = max ( xi , yi ) − α ⋅ xi − yi (α y β son valores aleatorios entre 0 y 1)

zi = Q( xi , yi ) (Q es una conectiva borrosa)

Operadores Genéticos • Mutación La mutación pretende introducir ciertas componentes de aleatoriedad en las nuevas poblaciones con el fin de favorecer las búsquedas locales evitando que los algoritmos tiendan a mínimos locales. (a) En cadenas binarias 1001010110 1 100101

1001010110 0 100101

(punto de mutación) (b) En vectores n-dimensionales zi = xi + N i (0, σ i ) (Ni(a,b) es una distribución Gaussiana)

5

Operadores de selección La selección de individuos para poblaciones futuras se basa en un análisis de su función de capacidad (fitness). La función de capacidad es totalmente dependiente del problema que se esté intentando resolver (i.e., en clasificación de patrones el número de aciertos, en juegos interactivos el número de partidas ganadas, etc.). Una vez evaluada la capacidad de cada individuo podemos establecer distintos criterios de selección. La mayoría de ellos se basan en establecer para cada individuo una probabilidad de ser seleccionado de acuerdo con la siguiente fórmula

pi =

fi

∑f

j

j∈P

donde P denota la población en curso, i es un individuo de la población y fi es el valor de su función de capacidad.

Operadores de selección Algunos criterios (operadores) de selección son los siguientes • Método de la ruleta: Girar la siguiente ruleta para seleccionar al individuo 2 3 4 1 p1 • Selección mediante ranking: Se ordenan los individuos de acuerdo con su función de capacidad. Se asignan nuevas probabilidades de acuerdo con el orden preestablecido y se aplica el método de la ruleta. • Selección mediante torneo: Se seleccionan k individuos de la población (aleatoriamente). Se selecciona el mejor de los k individuos.

6

Mecanismos de competición Los mecanismos de competición se aplican cuando se desea eliminar algunos individuos de la población con el objetivo de que ésta no crezca de forma incontrolada. También se aplican para refinar más los mecanismos de selección de forma que ésta se haga sobre los mejores individuos. Habitualmente, la generación de nuevos individuos reemplazan a una fracción de individuos de la población. Algunos mecanismos de competición son los siguientes: Elitismo: Los n individuos mejores (generados o ya existentes) pasan a la siguiente población. Truncamiento: Se selecciona un porcentaje de los mejores individuos a cuyos padres se les aplica los operadores de selección para la siguiente generación.

Algoritmos de búsqueda local Los algoritmos de búsqueda local permiten incrementar de forma iterativa las soluciones que ofrece una población en curso. Se utilizan habitualmente en los algoritmos genéticos. Algunos algoritmos de búsqueda local son los siguientes: • next ascent bit-climbing • steepest ascent bit-climbing • random bit-climbing • Evolución Lamarckiana • Efecto Baldwin • (1+1)-ES • random mutation hill-climbing • random walk with uniform distribution • quad search • consecutive exchange

7

Estrategias Evolutivas Las estrategias evolutivas fueron desarrolladas a principios de los 60’ por Rechenberg y Schwefel como un método de resolución de problemas de optimización en ingeniería Habitualmente trabajan con espacios de genotipos igual a Rn Se utilizan los siguientes parámetros: µ Tamaño de la población inicial λ Tamaño de la población descendente ρ Tamaño de la familia (padres) (1≤ ρ ≤ µ) Un individuo de la población se define por el par (x,σ) donde x es un punto en el espacio Rn definido por (x1, x2, …, xn) y σ es un vector de desviaciones definido como (σ1, σ2, …, σn).

Algunas Estrategias Evolutivas La estrategia evolutiva (1+1)

Se la conoce también como estrategia evolutiva con dos individuos. En el momento t=0 se genera una población con un único individuo. Se genera una población con único descendiente mediante un operador de mutación. De los dos individuos, se selecciona el que mejor función de capacidad obtenga y se continúa hasta satisfacer la condición de terminación

8

Algunas Estrategias Evolutivas La estrategia evolutiva (µ+1)

Se parte de una población inicial de µ > 1 individuos Se seleccionan aleatoriamente dos individuos de la población y se genera un descendiente (generalmente a partir de recombinación) Se aplica el operador de selección para eliminar el peor de los µ+1 individuos de la población y se continúa hasta satisfacer la condición de terminación

Algunas Estrategias Evolutivas La estrategia evolutiva (µ+λ) Es una generalización de la estrategia (µ+1) Se parte de una población inicial de µ > λ individuos Se generan λ individuos a partir de los µ padres iniciales (generalmente a partir de recombinación) Los λ individuos nuevos son mutados Se aplica el operador de selección para eliminar los peores λ individuos de los µ+1 existentes en la población y se continúa hasta satisfacer la condición de terminación

9

Algunas Estrategias Evolutivas La estrategia evolutiva (µ,λ) Es una modificación de la estrategia (µ+λ) Se parte de una población inicial de µ individuos Se generan λ > µ individuos a partir de los µ padres iniciales (generalmente a partir de recombinación) Los λ individuos nuevos son mutados Se aplica el operador de selección sobre los λ individuos hasta reducir la nueva población a µ y se continúa hasta satisfacer la condición de terminación

Algunas Estrategias Evolutivas Otras estrategias evolutivas En la actualidad se están explorando nuevas estrategias evolutivas que combinan las estrategias anteriores. Algunas técnicas bajo estudio son las siguientes: Combinar las sustituciones de las poblaciones µ y λ. Introducir parámetros de caducidad: Cada individuo tiene una cuota de vida (i.e., dos o tres generaciones) Cada individuo tiene una cuota de fertilidad Cada individuo tiene un número máximo de antecesores, etc.

10

Algoritmos genéticos Los algoritmos genéticos fueron desarrollados a finales de los 60’ por J. Holland y sus colaboradores. Posteriormente, fueron redefinidos por De Yong, Goldberg, Michalewicz y otros. El Algoritmo Genético Simple (SGA) difiere de otras aproximaciones como las Estrategias Evolutivas o los Algoritmos Evolutivos en los dos siguientes aspectos: 1. Se utiliza un espacio de búsqueda de genotipos que se representan como cadenas binarias (Paso 0 del algoritmo) 2. Se utiliza la siguiente secuencia para la selección y la aplicación de operadores (Paso 4 del algoritmo) Selección estocástica Recombinación Mutación

Algunas variantes de los algoritmos genéticos • SGA con elitismo • GA híbridos • Genitor • CHC

• GENOCOP • Criaderos de GA • GAVaPS

Algoritmos de “niching ” “niching” Los algoritmos de “niching” intentan dar solución a los problemas relacionados con (1) Mantener la diversidad de la población (2) Converger a varias soluciones (3) Prevenir una convergencia prematura cuando sólo se exige una solución Algunos mecanismos utilizados son los de (1) crowding, (2) fitness sharing, (3) mating restriction, (4) deterministic crowding, (5) probabilistic crowding, etc.

11

Programación genética La programación genética es una técnica de optimización evolutiva propuesta inicialmente por Koza en 1992. Las principales diferencias con otras aproximaciones son: 1. Las soluciones se representan como árboles (Paso 0 del algoritmo) (que permiten describir programas en LISP, funciones, estructuras de programación, etc.) 2. La aplicación de selección y aplicación de operadores obedece al siguiente esquema (Paso 4 del algoritmo) i=0 Repetir Elegir operador (PS, PC, PM) Aplicar operador (selección, recombinación, mutación) i = i+1 hasta i = n

Programación evolutiva La programación genética es otra técnica evolutiva propuesta por Fogel y sus colaboradores en 1966. Las principales diferencias con otras aproximaciones son: 1. Las soluciones se representan mediante máquinas de estados finitos (autómatas) (Paso 0 del algoritmo) 2. No se utiliza recombinación como operador genético (Paso 4 del algoritmo)

El esquema genérico se asimila a una estrategia evolutiva (µ+µ) donde se aplica una mutación de tipo estadístico (“gaussiana”) sobre µ individuos y la selección se realiza mediante torneo.

12

Sistemas de aprendizaje de clasificación Básicamente son sistemas de aprendizaje basado en reglas donde las reglas se generan y modifican mediante algoritmos genéticos. Actualmente existen dos aproximaciones relevantes: (1) La aproximación de Pittsburg (propuesta por Bacardit y Garrel en 2003) (2) La aproximación de Michigan Las principales diferencias con otras aproximaciones son: 1. Las soluciones se representan mediante máquinas de estados finitos (autómatas) (Paso 0 del algoritmo) 2. No se utiliza recombinación como operador genético (Paso 4 del algoritmo)

13