T4: Algoritmos Genéticosaic.uniovi.es/ssii/SSII-T4-AlgoritmosGeneticos.pdf · Sistemas Inteligentes – T4: Algoritmos Genéticos . Centro de Inteligencia Artificia l Universidad

Centro de Inteligencia Artificial

Universidad de Oviedo

SISTEMAS INTELIGENTES

T4: Algoritmos Genéticos

{jdiez, juanjo} @ aic.uniovi.es

Sistemas Inteligentes – T4: Algoritmos Genéticos



La idea es… •  ¿Qué pretende la IA?

Producir agentes inteligentes

•  ¿Cuál es el mejor ejemplo de agente inteligente? El Hombre

•  ¿Cómo ha logrado ser inteligente? Gracias a la … EVOLUCIÓN!!!

•  La evolución se ha mostrado como una solución exitosa dentro de los sistemas biológicos

•  La inteligencia humana es el mejor ejemplo del poder de la evolución

•  Idea: seguir la teorías neo-darwinistas para hacer evolucionar los agentes inteligentes de un problema




¿Cómo funcionan? •  Simulan vagamente la evolución biológica

•  Parten de una población de agentes (hipótesis) diseñados para realizar una determinada tarea

•  La población evoluciona… ¿cómo? °  Sobreviven los mejores agentes: ¡ SELECCIÓN ! °  Combinamos dos agentes: ¡ REPRODUCCIÓN ! °  Alteramos agentes: ¡ MUTACIÓN !

•  Tras cada generación, la población resuelve mejor la tarea para la que se diseñó

•  Al final nos quedaremos con el mejor agente Sistemas Inteligentes – T4: Algoritmos Genéticos



El Ciclo Evolutivo

Cruce Mutación

Padres Selección

Descendencia

Población




Desmitificando un poco… •  No producen hombres, ni nada parecido (de

momento) •  Son sistemas de búsqueda •  Es una búsqueda informada, similar a la

búsqueda por haz local (con cruce) •  ¿Cuándo dejamos de evolucionar? •  A pesar de todo, tienen ventajas:

°  Trabajan en espacios de búsqueda complejos °  Fácilmente paralelizables

•  Éxito indudable en ciertas tareas




Técnicas evolutivas •  Programación evolutiva [Fogel, 60]

°  Evolución al nivel de las especies °  Usa la mutación y la selección es probabilística °  No usan el cruce

•  Estrategias Evolutivas [Alemania, 64] °  Evolución al nivel de los individuos °  Usan operadores de recombinación °  La selección es determinista

• Algoritmos Genéticos [Holland, 60] °  Programación Genética




Algoritmos Genéticos •  John Holland, 60s, y 70s, Univ. Michigan

•  Idea original estudio teórico de la adaptación y los “planes reproductivos” (nombre original)

•  Se evoluciona el genotipo y no el fenotipo

•  Representación genética independiente del dominio: cadenas binarias

•  Selección probabilística

•  Operación principal: cruce

•  La mutación desempeña un papel secundario Sistemas Inteligentes – T4: Algoritmos Genéticos



¿Qué necesitamos para definir un GA? •  Representación de las soluciones

(genotipos)

•  Función de evaluación

•  Estrategia de selección

•  Operadores genéticos (cruce, mutación, …)

•  Parámetros: °  Tamaño de la población °  Porcentaje de elitismo/cruce °  Probabilidad de mutación °  Criterio de parada (calidad de la solución, nº máximo de

generaciones, …) Sistemas Inteligentes – T4: Algoritmos Genéticos



Algoritmo genérico (genético) GA ( F, F_T, p, r, m) F: función de evaluación, valora cada genotipo F_T: nivel de aceptación p: número de individuos (hipótesis) en la población r: porcentaje de la población reemplazada por cruce m: probabilidad de mutación

P = generar p hipótesis (aleatoriamente) (Población inicial) Para cada h ∈ P, evaluar F(h) Mientras ( maxh∈P F(h) < F_T ) hacer Crear una nueva población Ps 1) Ps = Selección probabilística de (1-r)*p miembros de P Cada hipótesis tiene Pr(h)=F(h)/ΣF(h) de ser elegida 2) Cruce: seleccionar r*p/2 parejas de individuos de P Cada pareja genera 2 descendientes → Ps 3) Mutación: selección uniforme de m*p miembros de Ps Se actualiza P: P = Ps Para cada h ∈ p, evaluar F(h) Fin Mientras Retornar el mejor individuo: h, tal que F(h)=maxh∈P F(h) Fin GA Sistemas Inteligentes – T4: Algoritmos Genéticos



Representación de los genotipos •  Hay que definir cómo se representan las

características genéticas de los individuos (soluciones, hipótesis) de la población

•  Aspecto muy importante en la definición de GA •  La representación afecta a la definición de los

operadores genéticos (selección, cruce, mutación) •  Muchos tipos de representación:

°  Cadenas de bits (la más típica) °  Código Gray (mantiene la adyacencia) °  Punto Flotante (Binaria, Real) °  Entera °  LISP, Expresiones, … (Programación

Genética)




Representación: Cadenas de bits (I) •  Se utilizan cadenas de bits para representar los

distintos genotipos existentes

•  Es un tipo de representación que se adapta a casi cualquier problema

Ej. Problema n-reinas: Podemos usar una matriz de bits

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0

Demasiadas reinas




Representación: Cadenas de bits (II) •  Ej. Optimizar la función x*sen(10*pi*x)+2 en [-1,2]

Para 6 decimales de precisión habrá 3.000.000 valores (long. intervalo 3)

2097152 = 221 < 3000000 < 222 = 4194304

(1000101110110101000111) representa al número 0.637197 (fenotipo)

En esta caso: cada genotipo representa un fenotipo (OK!)




Representación: Cadenas de bits (III) •  Ej. Problema “Nadar”, atributos:

Pronóstico: Soleado, Nublado, Lluvia Temperatura: Baja, Moderada, Alta Humedad: Normal, Alta Viento: Flojo, Fuerte Nadar: Si, No (Clase)

Cada individuo representa una regla:

Pronóstico Temperatura Humedad Viento Nadar

0 0 1 0 0 0 0 0 0 1 0 1 SI Pronóstico = Lluvia Y Viento = Fuerte ENTONCES Nadar = No




Interpretación biológica

Pronóstico Temperatura Humedad Viento Nadar

0 0 1 0 0 0 0 0 0 1 0 1

Cromosoma

Gen#1 Gen#2 Gen#3 Gen#4 Gen#5

•  Cromosoma: cadena de ADN que contiene la información genética de un individuo

•  Gen: sección de ADN que codifica una cierta función bioquímica (p.e. producir una proteína)

•  Alelo: cada valor posible para una cierta posición genética




Representación: otros aspectos •  Cromosomas de longitud variable

Nadar: cada individuo es un conjunto de reglas

100 000 10 00 10 100 000 01 00 01 SI (Pronóstico = Soleado ) Y (Humedad = Normal) ENTONCES Nadar = Si SI (Pronóstico = Soleado ) Y (Humedad = Alta) ENTONCES Nadar = No

•  Individuos correctos La representación de los individuos y los operadores genéticos deben diseñarse para producir siempre individuos correctos

100 000 10 00 10 100 000 Faltan genes!!!




Cadenas de bits: Ventajas •  Representación universal

•  Es la que usan los ordenadores

•  Justificación teórica (y biológica): °  Representación con muchos genes y con pocos alelos

posibles °  Es lo habitual en los cromosomas naturales

•  Se favorece la diversidad y la formación de buenos bloques constructores

°  Bloque constructor: grupo pequeño de genes que ha co-evolucionado y que si se introdujera en un cromosoma incrementaría probablemente su aptitud




Cadenas de bits: Problemas •  Escalabilidad, cromosomas demasiado grandes •  Precisión limitada •  Diferencias entre el espacio genotípico y el

fenotípico 5 (entero) = 101 6 (entero) = 110 Distancia 1 en el espacio fenotípico, y 2 en el genotípico Posible solución: usar código Gray

•  Pero: °  Todas las representaciones tienen inconvenientes °  Es la representación más usada




Otras representaciones: enteros •  n-reinas: un entero por cada columna indicando

en qué fila está la reina

Individuo: 1 6 2 5 7 4 8 3

•  TSP: se representa cada ciudad con un número {1,…,n} y cada individuo será una permutación de esos números indicando el orden de recorrido

Individuo: 1 8 4 5 2 7 6 10 3 9 Sistemas Inteligentes – T4: Algoritmos Genéticos



¿Cómo diseñar buenas representaciones? •  La representación no debe tener sesgos, todos los

individuos se deben encontrar representados de manera equitativa en el conjunto de genotipos posibles. Es decir, los genotipos deben representar bien los fenotipos

•  La representación no debería permitir soluciones no factibles

•  La función de evaluación debe aplicarse fácilmente (de forma rápida) sobre los genotipos de los individuos

•  La representación debe poseer localidad (cambios pequeños en el genotipo resultan en cambios pequeños en el fenotipo)

•  La representación debe ajustarse a un conjunto de operadores genéticos de tal forma que se transmitan los bloques constructores de padres a hijos

•  Una buena representación debe minimizar la epístasis (la medida en que la contribución de aptitud de un gen depende de los valores de los otros genes)




Función de evaluación (o de fitness) •  Mide la aptitud de cada individuo. Nos permiten evaluar

la calidad de los genotipos •  Hay muchas posibles:

°  Precisión de la hipótesis °  Coste de la solución (TSP) °  Nivel de complejidad: se prefiere la más simple (Occam) °  Híbridas

•  Es dependiente del problema •  Debe ser rápida, se ejecuta muchísimas veces •  Es clave en el algoritmo, en base a ella se decide la

selección de individuos, y de ella depende en gran medida la velocidad de ejecución (y por tanto las soluciones que se pueden alcanzar)




Selección de individuos •  Permite que las poblaciones mejoren sucesivamente •  Normalmente siempre se suele incluir el mejor

individuo en la siguiente generación (elitismo) •  La selección no se debe basar en elegir sólo a los

mejores individuos (problema de crowding) •  Aunque los mejores deben tener siempre más

probabilidad de ser elegidos (convergencia) •  Hay muchísimas técnicas de selección

°  Proporcional °  Por torneo °  Ranking °  …




•  Este nombre describe un grupo de esquemas de selección originalmente propuestos por Holland

•  Eligen individuos de acuerdo a su contribución de aptitud con respecto al total de la población

•  Pueden provocar poca diversidad, propiciando que predominen los mejores individuos (crowding)

•  Variantes: °  Ruleta °  Sobrante Estocástico °  Universal Estocástica °  …

Selección Proporcional

( ) [ ][ ]∑ =

= p

1j j

ii

hfhfhP




Selección por torneo y ranking •  Torneo:

°  Se seleccionan uniformemente un grupo de individuos k °  Con probabilidad p se selecciona el mejor individuo °  El parámetro p permite controlar el crowding

•  Ranking °  Similar al proporcional °  Se ordenan los individuos de acuerdo a su aptitud °  La probabilidad de selección es proporcional a la

posición en el ranking




Operador de cruce •  Combina individuos (típicamente 2) para generar descendientes

(usualmente 2) •  Máscara de cruce: máscara de bits que indica los miembros del

primer y del segundo padres que se transmiten a la descendencia •  Single-Point

Padres: 11101001000 00001010101 Máscara: 11111000000 Descendientes: 11101010101 00001001000

•  Two-Point Padres: 11101001000 00001010101 Máscara: 00111110000 Descendientes: 11001011000 00101000101

•  Uniform (bit aleatoriamente elegidos) Padres: 11101001000 00001010101 Máscara: 10011010011 Descendientes: 10001000100 01101011001




Operador de mutación •  Idea: introducir cambios aleatorios en las

estructuras (genes)

•  Provoca: una búsqueda estocástica por el espacio de hipótesis

•  Single-Point Individuo: 11101001000 Individuo mutado: 11101011000 (bit aleatorio)

•  Multi-Point Se invierten múltiples bits (elegidos aleatoriamente)




Ejemplo: las n reinas (I) •  Representación: entera, cada dígito indica la fila dentro de

la columna i-ésima donde está situada la reina i •  Fitness: pares de reinas no atacadas

•  Selección: proporcional •  Cruce y mutación: single-point

Ejemplo: 32752411




Ejemplo: las n reinas (II)




Esquemas •  Objetivo: identificar bloques constructores •  Describen familias de individuos •  Definición: cadena contiene tres símbolos, 0, 1,

*. El * representa que en esa posición da igual un 1 ó un 0

•  Ejemplo: ***010*** •  Caracterizan las poblaciones de acuerdo al

número de individuos que representan cada esquema

°  m(s,t)= nº de individuos con el esquema s en la población del instante t




Programación Genética

•  Uso de estructuras de árboles para representar programas de computadora

•  Se predetermina la máxima profundidad de los árboles, pero no su topología precisa

•  El tamaño, forma y contenido de los árboles puede cambiar dinámicamente durante el proceso evolutivo




Funciones más utilizadas •  Operaciones aritméticas: +,-,*,… •  Funciones matemáticas: seno, exp,… •  Operaciones Booleanas: AND, OR,.. •  Operadores condicionales: IF •  Iteraciones: DO-UNTIL •  Recursión •  Cualquier función específica




Cruce




Aplicaciones •  Problemas de optimización combinatoria •  Problemas de ajuste de parámetros •  Problemas de satisfacción de restricciones,

planificación y asignación de recursos espaciales y temporales

•  Optimización (estructural, de topologías, numérica, combinatoria, etc.)

•  Reconocimiento de patrones •  Generación de gramáticas (regulares, libres de

contexto)


Documents

T4: Algoritmos Genéticosaic.uniovi.es/ssii/SSII-T4-AlgoritmosGeneticos.pdf · Sistemas Inteligentes – T4: Algoritmos Genéticos . Centro de Inteligencia Artificia l Universidad