Diseño con algoritmos genéticos

Sistemas Inteligentes de Control: EsquemaMódulo I. Control de Sistemas.Módulo II. Fundamentos de Lógica Difusa.Módulo III. Sistemas Basados en Reglas Difusas.

Módulo IV. Aprendizaje y Adaptación en Sistemas Basados en Reglas Difusas.

Tema 8. Diseño Automático de Sistemas Basados en Reglas Difusas para Control.

Tema 9. Diseño Ad Hoc.Tema 10. Diseño con Algoritmos Genéticos.

MÓDULO IV: Aprendizaje y adaptación en sistemas basados en reglas difusas

Tema 10. Diseño con algoritmos genéticos

Tema 10: Diseño con Algoritmos Genéticos

1. Conceptos básicos sobre algoritmos genéticos 1.1.Introducción1.2.¿Cómo se construye?1.3.Sobre su utilización1.4.Diversidad, exploración, explotación

2. Diseño evolutivo de sistemas difusos 2.1.Diseño de la base de reglas2.2.Diseño de la base de datos2.3.Diseño combinado

Evolución natural. Evolución artificial

¿Qué es un algoritmo genético?

Los ingredientes

El ciclo de la evolución

Estructura de un algoritmo genético

Dominios de aplicación

1.1. Introducción a los algoritmos genéticos


Evolución natural

En la naturaleza, los procesos evolutivos ocurren cuando se satisfacen las siguientes condiciones:

Una entidad o individuo tiene la habilidad de reproducirse

Hay una población de tales individuos que son capaces de reproducirse

Existe alguna variedad, diferencia, entre los individuos que se reproducen

Algunas diferencias en la habilidad para sobrevivir en el entorno están asociadas con esa variedad


Evolución natural

Los mecanismos que conducen esta evolución no son totalmente conocidos, pero sí algunas de sus características, que son ampliamente aceptadas:

La evolución es un proceso que opera sobre los cromosomas más que sobre las estructuras de la vida que están codificadas en ellos


Evolución natural

La selección natural es el enlace entre los cromosomas y la actuación de sus estructuras decodificadas

El proceso de reproducción es el punto en el cual la evolución toma parte, actúa

La evolución biológica no tiene memoria

Referencia: Darwin, C. (1859). On the Origin of Species by Means of Natural Selection or the Preservations of FavoredRaces in the Struggle for Life. London: John Murray.


Evolución artificial

COMPUTACION EVOLUTIVA

Está compuesta por modelos de evolución basados en poblaciones cuyos elementos representan soluciones a problemas

La simulación de este proceso en un ordenador resulta ser una técnica de optimización probabilística, que con frecuencia mejora a otros métodos clásicos en problemas difíciles


Evolución artificial

Existen cuatro paradigmas básicos:

Algoritmos Genéticos que utilizan operadores genéticos sobre cromosomas

Estrategias de Evolución que enfatizan los cambios de comportamiento al nivel de los individuos

Programación Evolutiva que enfatizan los cambios de comportamiento al nivel de las especies

Programación Genética que evoluciona expresiones representadas como árboles

Existen otros modelos de evolución de poblaciones


Los Algoritmos Genéticos

son algoritmos deoptimización,búsqueda yaprendizajeinspirados en los procesos de

Evolución Natural y

Evolución Genética

¿Qué es un algoritmo genético?


Cruce(o recombinación)

t t + 1

mutación

reproducción

selección

Los ingredientes


Cruce

Mutación

Selección

Reemplazamiento

PADRES

POBLACIÓN

DESCENDIENTES

El ciclo de la evolución


Algoritmo Genético BásicoInicio (1)

t = 0inicializar P(t)evaluar P(t)

Mientras (no se cumpla la condición de parada) hacerInicio(2)

t = t + 1seleccionar P’(t) desde P(t-1)P’’(t) ← cruce P’(t)P(t) ← mutación P’(t)evaluar P(t)

Final(2)

Final(1)

Estructura de un algoritmo genético


Generación de trayectorias

Planificación de sistemas de Producción

Optimización estructural

1 2 m1nDiseño de circuitosVLSI

AprendizajeClasificación

Control de procesos químicos



• Optimización combinatoria y en dominios reales

• Modelado e identificación de sistemas

• Planificación y control

• Ingeniería

• Vida artificial

• Aprendizaje y minería de datos

• Internet y Sistemas de Recuperación de Información

• ...



Los pasos para construir un Algoritmo Genético

1. Diseñar una representación

2. Decidir cómo inicializar la población

3. Diseñar una correspondencia entre genotipo y fenotipo

4. Diseñar una forma de evaluar un individuo

5. Diseñar un operador de mutación adecuado

6. Diseñar un operador de cruce adecuado

7. Decidir cómo seleccionar los individuos para ser padres

8. Decidir cómo reemplazar a los individuos

9. Decidir la condición de parada

1.2. ¿Cómo se construye?


1.2.1. RepresentaciónDebemos disponer de un mecanismo para codificar un individuo como un genotipo

Existen muchas maneras de hacer esto y se escoge la más relevante para el problema en cuestión

Una vez elegida una representación, tenemos que tener en cuenta cómo serán evaluados los genotipos y qué operadores genéticos hay que utilizar

DEFINICIONES

Cromosoma: vector completo que codifica la soluciónGen: elemento mínimo del cromosomaAlelos: valores que puede tomar cada gen


CROMOSOMACROMOSOMA

GENGEN

La representación de un individuo se puede hacer mediante unacodificación discreta, y en particular binaria

1.2.1. Representación binaria

ALELOS={0,1}ALELOS={0,1}


Genotipo

8 bits

Fenotipo

• Entero

• Número real

• Secuencia

• ...

• Cualquier otra?



El fenotipo pueden ser números enteros

Genotipo:

1*21*27 7 + 0*2+ 0*26 6 + 1*2+ 1*25 5 + 0*2+ 0*24 4 + 0*2+ 0*23 3 + 0*2+ 0*22 2 + 1*2+ 1*21 1 + 1*2+ 1*200

== 128 + 32 + 2 + 1 = 163128 + 32 + 2 + 1 = 163

= 163Fenotipo:



El fenotipo pueden ser números reales

Ejemplo: un número real entre 2.5 y 20.5 utilizando8 dígitos binarios

( ) 9609.135.25.20256

1635.2 =−+=x

= 13.9609Genotipo: Fenotipo:



Una forma natural de codificar una solución es utilizando valores reales como genes

Muchas aplicaciones tienen esta forma natural de codificación

Los individuos se representan como vectores de valores reales:

La función de evaluación asocia a un vector un valor real de evaluación:

1.2.1. Representación real

Rx

x

x

x

X i

n

∈

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

= ,2

1

M

RR:f n →


Los individuos se representan como permutaciones

Se utilizan para problemas de secuenciación

Ejemplo famoso: Viajante de Comercio, donde cada ciudad tiene asignado un único número entre 1 y n

Necesita operadores especiales para garantizar que el resultado de aplicar un operador sigue siendo una permutación

1.2.1. Representación de orden


1.2.2. Inicialización

Uniforme sobre el espacio de búsqueda … (si es posible)

Cadena binaria: 0 ó 1 con probabilidad 0.5

Representación real: uniforme sobre un intervalo dado (para valores acotados)

Elegir la población a partir de los resultados de una heurísticaprevia


Algunas veces la obtención del fenotipo a partir del genotipo es un proceso obvio

En otras ocasiones el genotipo puede ser un conjunto de parámetros para algún algoritmo, el cual trabaja sobre los datos de un problema para obtener un fenotipo

Datos de un Problema

Fenotipo

Algoritmode obtención

Genotipo(Codificación)

1.2.3. Correspondencia entre genotipo y fenotipo


Este es el paso más costoso para una aplicación real

Puede ser una subrutina, un simulador, o cualquier proceso externo (ej. Experimentos en un robot, ....)

Se pueden utilizar funciones aproximadas para reducir el costo de evaluación

Cuando hay restricciones, éstas se pueden introducir en el costocomo penalización

Con múltiples objetivos se busca una solución de compromiso

1.2.4. Evaluación de un individuo


Podemos tener uno o más operadores de mutación para nuestra representación

Algunos aspectos importantes a tener en cuenta son:

Debe permitir alcanzar cualquier parte del espacio de búsqueda

El tamaño de la mutación debe ser controlado

Debe producir cromosomas válidos

1.2.5. Operador de mutación


1 1 1 1 1 1 1antes

1 1 1 0 1 1 1después

La mutación ocurre con una probabilidad pm para cada gen, o para cada cromosoma

gen mutado

Ejemplo: Mutación para representación binaria


Perturbación de los valores mediante un valor aleatorio

Generalmente, mediante una distribución normal N(0,σ), donde

0 es la media

σ es la desviación típica

x’i = xi + N(0,σi)

para cada parámetro

Ejemplo: Mutación para representación real


7 83 41 2 6 5

7 83 46 2 1 5

Intercambio de dos genes seleccionados aleatoriamente

Ejemplo: Mutación para representación de orden


Podríamos tener uno o más operadores de cruce para nuestra representación

Algunos aspectos importantes a tener en cuenta son:

Los hijos deberían heredar algunas características de cada padre. Si éste no es el caso, entonces estamos ante un operador de mutación

Se debe diseñar de acuerdo a la representación

La recombinación debe producir cromosomas válidos

1.2.6. Operador de cruce


Población: . . .

Cada cromosoma se corta en n partes que son recombinadas

(Ejemplo para n = 1)

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

padres

corte corte

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

descendientes

Ejemplo: Cruce para representación binaria


Cruce uniforme (recombinación discreta):

a db fc e g h

FD GE HCBA

a b C Ed Hgf

Ejemplo: Cruce para representación real


Cruce aritmético (recombinación aritmética):

a db fc e

FD ECBA

(a+A)/2 (b+B)/2 (c+C)/2 (e+E)/2(d+D)/2 (f+F)/2

↓

Ejemplo: Cruce para representación real


7 83 41 2 6 5 78 16 5234

81 2

7, 3, 4, 6, 5

4, 3, 6, 7, 5

ordenar

7 85 41 2 3 6

Padre 1 Padre 2

Hijo 1

Ejemplo: Cruce para representación de orden


Debemos garantizar que los mejores individuos tengan una mayor posibilidad de ser padres (reproducirse) frente a los individuos menos buenos

Esta idea nos define la presión selectiva que conducirá la reproducción

No obstante, debemos ser cuidadosos para dar una posibilidad de reproducirse a los individuos menos buenos. Éstos pueden incluir material genético útil en el proceso de reproducción

1.2.7. Estrategia de selección


El número de veces que un individuo debe reproducirse es

∑=

jj

ii f

fps

Mejor

Peor

Los mejores individuos tienen:

Más espacio en la ruleta

Más probabilidad de ser seleccionados

Ejemplo: Selección proporcional


La presión selectiva se ve también afectada por la forma en que los cromosomas de la población son reemplazados por los nuevos descendientes

Podemos utilizar métodos de reemplazamiento aleatorios, o determinísticos

Podemos decidir no reemplazar al mejor cromosoma de la población: Elitismo

1.2.8. Estrategia de reemplazamiento


Cuando se alcanza el óptimo

Recursos limitados de CPU: fijar el máximo número de evaluaciones

Límite sobre la paciencia del usuario: Después de algunas iteraciones sin mejora

1.2.9. Criterio de parada


1.3. Utilización

Nunca sacar conclusiones de una única ejecución utilizar medidas estadísticas (medias, medianas, ...)con un número suficiente de ejecuciones independientes

“Se puede obtener lo que se desea en una experimentación de acuerdo a la dificultad de los casos utilizados” – No se debe ajustar/chequear la actuación de un algoritmo sobre ejemplos simples si se desea trabajar con casos reales

Desde el punto de vista de las aplicaciones: doble enfoque y diferente diseño

Encontrar una solución muy buena al menos una vez

Encontrar al menos una solución muy buena en cada ejecución

1.3. Utilización

1.4. Diversidad, exploración, explotación

Diversidad genética

Asociada a las diferencias entre los cromosomas en la población

Falta de diversidad genética = todos los individuos en la población son parecidos

Falta de diversidad convergencia al vecino más cercano

En la práctica es irreversible. Solución: Inclusión de mecanismos de diversidadReinicialización


Exploración vs Explotación

Exploración = muestrear regiones desconocidas

Excesiva exploración = búsqueda aleatoria, no converge

Explotación = trata de mejorar el mejor individuo

Excesiva explotación = solo búsqueda local, convergencia a un óptimo local



Resumen de los algoritmos genéticos

Basados en una metáfora biológica: evolución

Gran potencialidad de aplicación

Muy populares en muchos campos

Muy potentes en diversas aplicaciones

Altas prestaciones a bajo costo

2. Diseño evolutivo de sistemas difusos

AlgoritmosEvolutivos

Funcionesde escalado

ReglasDifusas

Funciones depertenencia

Base de Conocimiento

Entradaescalada Fuzificación

Motor deinferencia Defuzificación

Salidaescalada

Procesamiento Difuso

Dis

eño

Evo

luti

vo



Objetivo del proceso de aprendizaje de un SBRD

Encontrar una Base de Conocimiento tal que el SBRD que la incluya resuelva un problema dado.

¿Qué partes del SBRD se van a optimizar?

Procesos de aprendizaje: Diseño de algunos componentes de la Base de Conocimiento o de la Base de Conocimiento al completo.

Procesos de ajuste: Optimización de un SBRD existente.


R1: Si X1 es Alto y X2 es Bajo -> Y es MedioR2: Si X1 es Bajo y X2 es Medio -> Y es Alto

...


Interfaz deFuzificación

Interfaz deDefuzificación

Base deReglas

Base deDatos


Mecanismo de Inferencia

BajoMedio

X1Bajo Medio Alto

X2Bajo Medio Alto

Y

Alto

Pre

def

inid

a

Factores de escala

Predefinidos


PredefinidaR1: Si X1 es Alto y X2 es Bajo -> Y es MedioR2: Si X1 es Bajo y X2 es Medio -> Y es Alto

...




Base deReglas

Base deDatos



BajoMedio

X1Bajo Medio Alto

X2Bajo Medio Alto

Y

Factores de escala

Alto

Pre

def

inid

a


PredefinidaR1: Si X1 es Alto y X2 es Bajo -> Y es MedioR2: Si X1 es Bajo y X2 es Medio -> Y es Alto

...




Base deReglas

Base deDatos



BajoMedio

X1Bajo Medio Alto

X2Bajo Medio Alto

Y

Factores de escala

Alto

Predefinidos


R1: Si X1 es Alto y X2 es Bajo -> Y es MedioR2: Si X1 es Bajo y X2 es Medio -> Y es Alto

...




Base deReglas

Base deDatos



BajoMedio

X1Bajo Medio Alto

X2Bajo Medio Alto

Y

Alto

Factores de escala



Según las componentes que se optimicen:

Espacio de búsqueda más pequeño

Proceso de aprendizaje más sencillo y rápido

Las soluciones pueden ser suboptimales

Espacio de búsqueda más completo

Proceso de aprendizaje más complejo e ineficiente

Mayor granularidad en el aprendizaje, mejor consideración de la interdependencia, mayor probabilidad de encontrar soluciones óptimas



Equilibrio entre completitud y granularidad

Tipos de SBRDs Genéticos:

Sistemas con ajuste genético de la Base de Datos

Sistemas con aprendizaje genético de la Base de Reglas

Sistemas con aprendizaje genético de la Base de Conocimiento

Sistemas con aprendizaje genético del Mecanismo de Inferencia (poco usuales)


2.1. Diseño de la base de reglas

PROCESO DEAPRENDIZAJE

Módulo deevaluación (BR)

Base de Reglas (BR)

Base de Datospredefinida

Aprendizaje genético de la base de reglas


2.1. Diseño de la base de reglasEl aprendizaje genético de la base de reglas asume la existenciade un conjunto predefinido de funciones de pertenencia

Objetivo de la búsqueda: Un conjunto adecuado de reglas difusas

Esquema de representación: Alternativas:

Un cromosoma representa una base de reglas al completo(Enfoque Pittsburgh) ⇒ Apto para diseño off-line

Un cromosoma representa una regla y la población al completo, labase de reglas(Enfoque Michigan) ⇒ Apto para diseño on-line

Operadores: Adaptados al esquema de representación


2.1. Diseño de la base de reglasEjemplo: Problema de control con dos variables de entrada y una de

salida. Existe una base de datos definida a través de conocimiento experto, que determina las funciones de pertenencia para las siguientes etiquetas:

Error {N, C, P} ∇ Error {N, C, P} Potencia {B, M, A}

2 6 9

2 6 9 1 6 8 1 ...

(2) (6)

(9)

1 2 3 4 5 6 7 8 9

R1: Si el Error es Cero y la Variación_Error es Positivaentonces la Potencia es Alta

R2R1



Si en el antecedente de las reglas es necesario que aparezcan todas las variables de entrada(variable, etiqueta) (variable, etiqueta) ...

Si Error es Cero entonces Potencia es Alta

Si en un cromosoma representamos toda una Base de Reglas, generalmente se utilizará un esquema de codificación de longitud variable

1 2 3 9


2.2. Diseño de la base de datos


Módulo deevaluación (BD)

Base de Datos (BD)

Base de Reglaspredefinida

Ajuste de la base de datos

1. Ajuste de las funciones de escala2. Ajuste de las funciones de pertenencia


2.2. Diseño de la base de datos1. Ajuste de las funciones de escala

Trasladan el universo de discurso en los que se definen las variables de entrada y salida al dominio en el que se definen los conjuntos difusos.

Se adaptan para que el universo de discurso escalado se corresponda mejor con el rango de la variable.

Parámetros:Factor de escala

Cota superior e inferior (función de escala lineal)

Parámetros de contracción/expansión (función de escala no lineal)

Forma de codificación: esquema real de longitud fija


2.2. Diseño de la base de datos2. Ajuste de las funciones de pertenencia

Componente a optimizar: Funciones de pertenencia de los términos lingüísticos utilizados en las reglas difusas

Cada individuo = Base de datos al completo

Forma de codificación. Depende deTipo de función de pertenencia utilizadaTipo de SBRD:

descriptivo, todas las funciones se adaptan de forma global a la base de reglas, o

aproximativo, cada variable se asocia a un conjunto difuso distinto en cada regla


2.2. Diseño de la base de datosEjemplo: Ajuste de las funciones de pertenencia de un SBRD descriptivo con una variable de entrada y una de salida, con trestérminos lingüísticos para cada variable y funciones de pertenencia triangulares

1 cromosoma representará 2 (variables) · 3 (etiquetas) = 6 funciones de pertenenciaCada función de pertenencia triangular son 3 valores realesPor tanto, hay que optimizar 6 · 3 = 18 valores reales

Codificación: binaria o real (recomendable)

Función de adaptación: Error cuadrático medio (ECM)

Operadores de Cruce y Mutación: Adecuados para la codificación(binaria o real) y las restricciones del problema (forma correcta de las funciones de pertenencia, grado mínimo de emparejamiento, etc.)



-0.5 0.5 0.5 0.50 0 1 1 1.5 -0.5 0.5 0.5 0.50 0 1 1 1.5

-0.5 0.5 0.5 0.50 0.25 0.75 1 1.5 -0.35 0.35 0.5 0.50 0.3 0.7 1 1.5

Bajo

Bajo Bajo

Bajo

Medio

Medio

Medio

Medio

Alto

Alto

Alto

Alto

X

X Y

Y

R1: Si X1 es Bajo entonces Y es AltoR2: Si X1 es Medio entonces Y es Medio

. . .

La base de reglas difusaspermanece intacta!!


Operador de cruce

¿Válido para la representación utilizada?


1 0 1 1 1 0 0 1 1 0

0 0 0 0 1 1 1 1 0 0

1 0 1 0 1 1 1 1 0 0

0 0 0 1 1 0 0 1 1 0

0 0.35 0.4 0.6 ...

-0.3 –0.1 0 0.2 ...

0 0.35 0 0.2 ...

-0.3 –0.1 0.4 0.6 ...

¡Error!


Operador de cruce

Alternativas:

Algoritmo de reparación a posteriori

Obligar a que el punto de cruce se determine aleatoriamente

entre puntos extremos de las funciones de pertenencia (intercambio de una etiqueta), o

entre los extremos de la información relativa a una variable (intercambio de la partición de una variable)

Usar otro cruce que respete las restricciones



Operador de Mutación

¿Válido para la representación utilizada?


0.2 0.35 0.4 ...

0.2 0 0.4 ...

¡Error!

1 0 1 1 1 0 0 1 1 0

1 0 1 1 1 1 0 1 1 0


Operador de Mutación

Alternativas:

Mutación aleatoria dentro del rango de variación

siendo X un número aleatorio perteneciente a (0.2, 0.4)

Construir de nuevo el conjunto difuso completo (los tres parámetros)


0.2 0.35 0.4 ... 0.2 X 0.4 ...


2.3. Diseño combinado: SBRDs con aprendizaje genético de la base de conocimiento (BD + BR)

El proceso de aprendizaje de la Base de Conocimiento debe determinar:

Funciones de pertenenciaReglas difusas

y algunas veces también

Factores (o funciones) de escalaTérminos lingüísticos

Espacio de búsqueda grande y complejoCromosomas con longitud variableUna regla por cromosoma



Algunos enfoques intentan mejorar la definición de la base de datos, una vez aprendida la base de reglas

Etapas:

1. Aprendizaje inicial de la base de reglas (base de datos predefinida)

2. Aprendizaje de la base de datos (base de reglas aprendida en el paso anterior)



Aprendizaje inicial de la base de reglas yaprendizaje posterior de la base de datos

PROCESO DEAPRENDIZAJE 1

Base de Reglas (BR)


Base deDatospredefinida


Base deReglasdefinitiva

Base deDatos





Módulo deevaluación (BC)

Base deDatos

Base deReglas


Aprendizaje de la base de conocimiento



Elementos a codificar en un cromosoma:

Factores de escalaFunciones de pertenenciaReglas difusas

Cada tipo de elemento será una parte independiente del cromosoma

Formas de combinar estas partes con los operadores genéticos:Mezclando subestructurasComo dos estructuras no relacionadasAplicando un proceso secuencial cuando el resultado de cruzar una subestructura afecte al cruce de la segunda subestructura

Codificación con longitud fija o variable


R1: Si el Error es Negativo entonces Potencia es Alta

R2: ...

0 0 0.5 0.3 0.5 0.8


Ejemplo: Problema con dos variables y tres etiquetas por variable

Error: {N, C, P} Potencia: {B, M, A}

Error Potencia Reglas

0.8 1 1.3 0 0 0.3 0.2 0.5 0.8 0.7 1 1 1 5 9 ...



Descomposición del proceso de aprendizaje en dos etapas dependientes:

1. Aprendizaje de la base de datos

2. Generación de la base de reglas

Ventajas:Reducción del espacio de búsquedaIncremento de la posibilidad de encontrar soluciones óptimas




Base deDatos

Base deReglas

Módulo de evaluación(Base de Datos yBase de Reglas)


Aprendizaje de la base de conocimiento mediantela derivación genética de la Base de Datos


Bibliografía recomendadasobre sistemas difusos genéticos

Básica:

O. Cordón, F. Herrera, F. Hoffmann y L. Magdalena. Genetic Fuzzy Systems. Evolutionary Tuning and Learning of Fuzzy Knowledge Bases. World Scientific, 2001.

Complementaria:

L. Reznik. Fuzzy Controllers. Newnes, 1997.

Bibliografía recomendadasobre algoritmos genéticos

Básica:Z. Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, 1996.

T. Bäck, D.B. Fogel y Z. Michalewicz. Handbook of Evolutionary Computation. Oxford University Press, 1997.

Complementaria:D.B. Fogel. Evolutionary Computation: Towards a New Philosophy of Machine Intelligence. John Wiley & Sons, 1999.

D.E. Goldberg. The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Kluwer Academic Pub., 2002.

Documents

Diseño con algoritmos genéticos