Download Agentes Racionales Inteligencia Computacional

Agentes Racionales
Inteligencia Computacional
Ing. Enrique González Ph.D
Departamento de Ingeniería de Sistemas
Facultad de Ingeniería
Pontificia Universidad Javeriana
Agenda General
• Agentes Racionales
– Conceptos y Arquitecturas
– Cooperación en SMA
• Redes Neuronales
– Supervisadas
– No Supervisadas
• Lógica Difusa
– Control Difuso
• Métodos Evolutivos
– Algoritmos Genéticos
Agentes Racionales
Agenda – Agentes Racionales
• Introducción Agentes Racionales
– Definiciones básicas
– Características de un agente
• Mapeo
– Técnicas de IA para toma de decisiones
• Arquitecturas para Agentes Racionales
– Estructuras generales
– Arquitecturas típicas
• Cooperación en Sistemas MultiAgentes
– Organizaciones SMA
– Interacción y cooperación
Por Qué Agentes?
Entidad Autónoma
Entidad Racional
Entidad Social
E
n
c
a
p
s
u
l
a
C
o
o
p
e
r
a
Conocimiento
Recursos
Servicios
Conducta
Complejidad
Manejable !!
Qué es ser Racional?
Hacer lo Correcto
Actuar Racionalmente
Ideal : Maximizar
Metas
Evaluar
Características de un Agente
Situado
Habita Ambiente
Agente
Autónomo
Efectua Acciones
Control Parcial
Puede
Influenciarlo
No Intervenció n
Externa
Estado Interno
Comportamiento
ProActivo
Alcanza Objetivos
Decidir y
Actuar
Agenda – Agentes Racionales
• Introducción Agentes Racionales
– Definiciones básicas
– Características de un agente
• Mapeo
– Técnicas de IA para toma de decisiones
• Arquitecturas para Agentes Racionales
– Estructuras generales
– Arquitecturas típicas
• Cooperación en Sistemas MultiAgentes
– Organizaciones SMA
– Interacción y cooperación
Agente y su Entorno
Sensores
Ambiente
Ti
Efectores
Ambiente
Ti+1
Mapeo Percepción/Acción
Ambiente
Ti
Secuencia de Percepción
Metas
Mapeo
Ambiente
Ti+n
Acción 1
...
Acción M
?
Acción
Correcta
Mapeo – Toma de Decisiones
• Sistema Basados en Reglas
– Reglas tipo “SI <condición> ENT <acción>
– Evaluación concurrente y disparo controlado
• Sistemas Difusos
– Reglas basadas en variables lingüísticas
– Manejo explicito de la ambigüedad
• Redes Neuronales
– Unidades de procesamiento multi-conectadas
– Capacidad de aprendizaje a partir de ejemplos
• Algoritmos Genéticos
– Evolución del sistema basado en su calidad para alcanzar
sus metas en un ambiente particular
Arquitectura del Agente
Arquitectura
Hardware
Software
Operativo
Programa Agente
Tipos de Agentes
Tipo de
Agente
Aspecto
Planificación
Representación
del Mundo
Agentes
Cognitivos
Agentes
Reactivos
SI - Capacidad de
NO Hay
Anticipar y Predecir
Reacciones Directas
Eventos Futuros
a los Estímulos
SI - Razonar sobre
NO Hay
las Representaciones
Representación
del Mundo
Explícita
Tipos de Agentes
Ejemplo Agente Cognitivo
Pb. → Abrir puerta cerrada con llave
Plan Abrir_Puerta
- Ir hasta sito donde está la llave
- Tomar la llave
- Ir hasta la puerta
- Abrir la puerta con la llave
Tipos de Agentes
Ejemplo Agente Reactivo
Pb. → Abrir puerta cerrada con llave
Reglas Condición-Acción
R1. Estoy frente a la puerta y tengo la llave
→ Abrir puerta con llave
R2. Estoy frente a la puerta y no tengo la llave
→ Ir a buscar la llave
R3. Puerta no abre y no tengo la llave
→ Ir a buscar la llave
R4. Llave frente a mi
→ Tomar la llave e ir a la puerta
Agenda – Agentes Racionales
• Introducción Agentes Racionales
– Definiciones básicas
– Características de un agente
• Mapeo
– Técnicas de IA para toma de decisiones
• Arquitecturas para Agentes Racionales
– Estructuras generales
– Arquitecturas típicas
• Cooperación en Sistemas MultiAgentes
– Organizaciones SMA
– Interacción y cooperación
Estructura Agente Reactivo
Agente
Sensores
Percepción
Decisión
Efectores
Ambiente
Reglas condición-acción
Estructura Agente Deliberativo
Agente
Sensores
Estado Interno
Secuencia de Percepción
Modelo
del Mundo
Reglas condición-acción
Decisión
Efectores
Ambiente
Efectos de mis Acciones
Estructura Agente Predictivo
Agente
Sensores
Estado Interno
Modelo
del Mundo
Secuencia de Percepción
Predicción
Metas Explícitas
Decisión
Efectores
Ambiente
Efectos de mis Acciones
Arquitectura de Agente
Arquitecturas por Capas
Capas Horizontales
Conexión Sensor-Acción
Capas de Diferente
Nivel de Abstracción
Simplicidad
Reducción de Interacciones
Capa N
Competencia entre Capas
Mediador
Sensor
Capa N-1
......
Capa 1
Acción
Arquitectura de Agente
Arquitecturas por Capas
Capas Horizontales
Conexión Sensor-Acción
Capas de Diferente
Nivel de Abstracción
Capas Verticales
Un Nivel Sensor-Acción
Simplicidad Conceptual
Capas Independientes
Capa N
Capa N-1
......
Sensor
Capa 1
Secuencialidad
No Tolerancia a Fallas
Acción
Arquitectura de Agente
Arquitecturas por Capas
Capas de Diferente
Nivel de Abstracción
Capas Horizontales
Conexión Sensor-Acción
Capas Verticales
Un Nivel Sensor-Acción
Simplicidad Conceptual
Capas Independientes
Capa N
......
Acción
Capa 1
Secuencialidad
No Tolerancia a Fallas
Capa N-1
Sensor
Arquitectura de Agente
Arquitecturas por Capas
Capas de Diferente
Nivel de Abstracción
Capas Horizontales
Conexión Sensor-Acción
Capas Verticales
Un Nivel Sensor-Acción
Capa 1
......
......
Capa N
Capa 1
......
......
Capa N
Sensor
Capas Híbridas
Acción
Agenda – Agentes Racionales
• Introducción Agentes Racionales
– Definiciones básicas
– Características de un agente
• Mapeo
– Técnicas de IA para toma de decisiones
• Arquitecturas para Agentes Racionales
– Estructuras generales
– Arquitecturas típicas
• Cooperación en Sistemas MultiAgentes
– Organizaciones SMA
– Interacción y cooperación
Organizaciones MultiAgentes
Diferentes Roles
Recursividad Sistémica
Tipos de Interacción
Objetivos
Recursos
Capacidad
Situaciones
Categoría
Compatibles
Suficientes
Suficientes
Independencia
Indiferencia
Insuficientes
Cooperación
Simple
Insuficientes
Suficientes
Estorbo
Insuficientes
Cooperación
Coordinada
Cooperación
Tipos de Interacción
Objetivos
Recursos
Capacidad
Situaciones
Categoría
No
Compatibles
Suficientes
Suficientes
Competición
Individual
pura
Antagónico
Insuficientes
Competición
Colectiva
pura
Suficientes
Conflictos
individuales
por Recursos
Insuficientes
Conflictos
colectivos por
recursos
Insuficientes
Cooperación
+
Colaboración
Asignación Tareas/Recursos
Coordinación de Acciones
Planificar y Sincronizar
Solución de Conflictos
Objetivos y Recursos
Cooperación
Protocolos de Interacción
Comunicación
Explícita - Mensajes
Implícita - Ambiente
Asignación por Oferta
Red Contractual
Petición
Mediador
Petición
Oferta
Oferta
Aceptación
Petición
Bibliografía Agentes y SMA
– Stuart J. Russell, Peter Norvig. "Inteligencia Artificial: Un
Enfoque Moderno", Prentice Hall, 1996.
– Jacques Ferber. "Multi-Agent Systems: An Introduction To
Distributed Artificial Intelligence". Addison Wesley, 1999.
– Gerhard Weiss. "Multiagent Systems". MIT Press, 1999.
– Michael N. Huhns. "Readings in Agents". Morgan Kaufmann
Publishers, 1998.
– Michael Woolridge. "Introduction to MultiAgent Systems". John
Wiley & Sons, 2002.
– Joseph P. Bigus, Jennifer Bigus. "Constructing Intelligent
Agents Using Java: Professional Developer's Guide". John
Wiley & Sons, 2001.
– González E., Bustacara C. “Desarrollo de Aplicaciones
Basadas en Sistemas MultiAgentes”, 1era Edición, Editorial
PUJ, 2007.
•
Pontificia Universidad Javeriana
Ing. Enrique González
Lógica Difusa
Agenda Lógica Difusa
• Introducción
– Naturaleza de lo Difuso
• Marco Conceptual
– Conjuntos Difusos
– Variables Lingüísticas
• Control Difuso
– Fuzzyficación
– Inferencia Difusa
– Defuzzyficación
Introducción Lógica Difusa
• Es un método alternativo para inferir.
• Los modelos de lógica difusa son:
– Más entendibles
• Definidos en lenguaje casi natural
– Más maleables.
– Más mantenibles.
– Menos complejos.
• Permiten el manejo de la ambigüedad y la
incertidumbre
Aproximación Clásica
Verdadero (1)
Lógica Clásica
Proposiciones
Falso (0)
Conjuntos Clásicos
Crisp sets
X universal, A ⊆ X, x ∈ A v x ∉ A
XA (x) = 0
XA (x) = 1
Limita a Ser o No Ser → No Admite Puntos Medios
Aproximación Difusa
• No tiene valor excluyentes
– Verdadero vs Falso
• Rango de valores continuo
–
–
–
–
Verdadero
Casi verdadero
Medio falso
Falso
Naturaleza de lo Difuso
• Dada la medición de una variable, cómo
determinar su clase??
– Por ejemplo se mide una temperatura de 100°
• Puedo afirmar que es frío
• Puedo afirmar que es tibio
• Puedo afirmar que es caliente
– Dónde pongo el umbral entre las diferentes
clases??
Naturaleza de lo Difuso
Tibio
Caliente
V
F
40
Temp
50
60
70
80
90
100
110
120
130
Naturaleza de lo Difuso
Tibio
V
Tibio = {50,60,70,80}
F
40
Temp
50
60
70
80
90
100
110
120
130
Naturaleza de lo Difuso
Caliente
V
Caliente = {90,100,110,...}
F
40
Temp
50
60
70
80
90
100
110
120
130
Naturaleza de lo Difuso
Caliente = {(90,0.0) ,(110,0.1),(130,0.4),(150,.09),(180,1.0),...}
Verdadero = 1.0
Caliente
Falso = 0.0
Temp
90
110
130
150
180
Naturaleza de lo Difuso
Tibio
Caliente
V
Temp
F
50
60
70
80
90 100 110
120
130
140
Naturaleza de lo Difuso
Tibio
Caliente
V
Temp
F
70
80
90
100
110
120
130
140
Agenda Lógica Difusa
• Introducción
– Naturaleza de lo Difuso
• Marco Conceptual
– Conjuntos Difusos
– Variables Lingüísticas
• Control Difuso
– Fuzzyficación
– Inferencia Difusa
– Defuzzyficación
Conjuntos Difusos
• Definición
– Si X es un universo y A es un predicado
vago/impreciso definido en X, entonces
A={x ∈ X / ( x / µA(x) )}
µA
1
A = { (x1,0.5) ,
A
(x2,1.0),
0.5
(x3,0.5) }
0
x1 x2 x3
xi
Funciones de Pertenencia
• Función Triangular
• Función Pi
Operadores Difusos
• Intersección (AND)
• Unión (OR)
Operadores Difusos
• Complemento (NOT)
Representación “Alrededor de”
1
A(x)
0
10
20
30
40
50
Representación “Alrededor de”
Representación Trapezoidal
1
µ(x)
0
§1
§2
§3 §4
Dominio
§5 §6
§7
Ejemplo Conjuntos Difusos
Representación Gráfica
Ejemplo Conjuntos Difusos
Representación por Tabla
Fuzzy vs. Crisp
Variables Difusas
Variables Lingüísticas
• Son variables cuyo valores son símbolos
representados por palabras o sentencias
• Se enmarcan en un lenguaje predeterminado
• Es una quíntupla: (X,T(X),U,G,M)
– X nombre de la variable
– T(x) Conjunto
» Intersección
» Unión
» Complemento
– U Universo
– G Gramática que genera los nombres
– M Serie de reglas semánticas para asociar cada X
con su significado
Variables Lingüísticas Ejemplo
Agenda Lógica Difusa
• Introducción
– Naturaleza de lo Difuso
• Marco Conceptual
– Conjuntos Difusos
– Variables Lingüísticas
• Control Difuso
– Fuzzyficación
– Inferencia Difusa
– Defuzzyficación
Controlador Difuso
I(t)
Defuzzificación
Iµ a , Iµ M , I µ B
Salida
Actuador
I
Proceso
lógico
Tµ a , Tµ M , Tµ B
Pµ a , Pµ M , Pµ B
IF
.
.
.
T
H
E
N
.
.
.
Depósito de
conocimiento
Reglas de
conjuntos
difusos
Dispositivo
Físico
Sensor
P
Fuzzificador
T
P(t), T(t)
Entrada
Ejemplo Caldera
Sensor de
Temperatura
Sensor de
Presión
T(t)
Controlador
de
Regulación
de Inyección
de Gasolina
P(t)
I(t)
Turbina
Variables Lingüísticas
• Temperatura
– {Frío, Fresco, Normal, Tibio, Caliente}
• Presión
– {Débil, Baja, Normal, Fuerte, Alta}
• Acción
– {NA, NM, NB, ZR, PB, PM, PA}
•
•
•
•
•
N: Negativa
P: Positiva
A: Alta
M: Media
B: Baja
Conjuntos Difusos
Temperatura
Fresco
Frío
Tibio
Normal
Caliente
1
0
110
220
330
Conjuntos Difusos
Presión
Baja
Débil
Fuerte
Normal
Alta
1
0
10
120
230
Conjuntos Difusos
Acción del Regulador
NA
NM
NB ZR PB
PM
PA
1
0
-60
0
+60
Fuzzificación
• Etapa Inicial
– Soportada por la definición de las Variables Lingüísticas
– Convierte una señal de entrada en una representación
de valor difuso
• Para cada conjunto difuso se calcula el valor de la función
de pertenencia asociado al valor de la entrada física
Ejemplo 1
Fresco
Baja Normal
1
1
0.57
0.48
0.25
0
110
T(t)=115 220
0
• Temperatura
– T(t) = 115 → Fresco(115) = 0.48
• Presión
– P(t) = 70 → Baja(70) = 0.57
– P(t) = 70 → Normal(70) = 0.25
10
P(t)=70
Base de Conocimiento
• Base de Reglas
– Caracterizar las acciones a realizar en función
de las entradas
– Escritas en términos de las variables lingüísticas
– Permite la toma de decisiones mediante la
operación del motor de inferencia
IF <condiciones> THEN <acciones>
• Ejemplo 1:
– IF temp es FRESCO AND presión es BAJA THEN acción
es PM
– IF temp es FRESCO AND presión es NORMAL THEN
acción es ZR
Reglas tienen la acción DIFERENTE
• Ejemplo 2:
– IF temp es FRESCO AND presión es BAJA THEN
acción es PM
– IF temp es FRIO AND presión es BAJA THEN
acción es PM
Reglas tienen la MISMA acción
TEMPERATURA
Tabla de Inferencia
Frío
Fresco
Normal
Tibio
Caliente
D
PA
PA
PM
PM
PB
B
PM
PM
PB
PB
PB
Presión
N
F
PB NB
ZR NM
ZR NB
NB NM
NM NA
A
NM
NM
NM
NA
NA
Inferencia Difusa
• Ejemplo 1:
– Temperatura
• T(t) = 115 → Fresco(115) = 0.48
– Presión
TEMPERATURA
• P(t) = 70 → Baja(70) = 0.57
• P(t) = 70 → Normal(70) = 0.25
Frío
Fresco
Normal
Tibio
Caliente
D
PA
PA
PM
PM
PB
B
PM
PM
PB
PB
PB
Presión
N
F
PB
NB
ZR
NM
ZR
NB
NB
NM
NM NA
A
NM
NM
NM
NA
NA
Reglas tienen la acción DIFERENTE
Inferencia Difusa
IF temp es FRESCO AND presión es BAJA THEN acción es PM
TEMPERATURA
IF temp es FRESCO AND presión es NORMAL THEN acción es ZR
Frío
Fresco
Normal
Tibio
Caliente
D
PA
PA
PM
PM
PB
B
PM
PM
PB
PB
PB
Presión
N
F
PB
NB
ZR
NM
ZR
NB
NB
NM
NM NA
A
NM
NM
NM
NA
NA
Reglas tienen la acción DIFERENTE
Inferencia Difusa
FRESCO and BAJA => PM
0.48
min
0.48
0.57
FRESCO and NORMAL=>ZR
0.48
min
0.25
0.48
Reglas tienen la acción DIFERENTE
0.25
ZR
PM
1
0.48
0.25
0
-60
0
Reglas tienen la acción DIFERENTE
+60
Defuzzificación
• Etapa Final
– Transformar acciones de tipo difuso a tipo
cuantitativo o determinístico
• Si la salida es simple, la transformación es directa
• Si la salida es compuesta, hay que combinar las salidas
para producir un único valor aplicable al control del
proceso
Ejemplo - Acción del Regulador
ZR
PM
1
0.48
0.25
0
-60
0
+20+42
+60
Ejemplo - Acción del Regulador
ZR
PM
1
0
-60
0
+23
+60
Redes Neuronales
Agenda Redes Neuronales
• Introducción
– Motivación y Aplicaciones
• Neurociencias
– Redes Neuronales Naturales
• Neuronas Artificiales
– Modelo y Topologías
– Clasificación
• Aprendizaje
– Modelo Supervisado y Metodología
• Adalina
– Problema de Separación Lineal
Agenda Redes Neuronales
• Redes Prealimentadas
– Perceptrón
– Retropropagación
– Metodología de Desarrollo RN
• Redes Auto-Organizadas
– Mapas AutoOrganizados de Kohonen
– LVQ
• Ejemplos de Aplicación
• Taller de Aplicación
Introducción - Neurociencias
• Base Biológica de la Mente
– Encéfalo
• compuesto de 1011 neuronas
– procesamiento relativamente lento
• posee regiones especializadas
• facultades elaboradas
– producto de la interconexión
serie/paralelo de funciones elementales
– Comportamiento de la Mente
• afectado y modulado por el medio
• produce la individualidad de ser humano
• conocimiento se almacena por
subcategorías
Introducción - Aplicaciones
• Reconocimiento de Patrones
– Minería de datos
– Lectura de códigos postales
– Análisis e interpretación de fonemas
• Automatización y Control
– Regulación de sistemas dinámicos
– Robótica y percepción
– Modelos predictivos
Agenda Redes Neuronales
• Introducción
– Motivación y Aplicaciones
• Neurociencias
– Redes Neuronales Naturales
• Neuronas Artificiales
– Modelo y Topologías
– Clasificación
• Aprendizaje
– Modelo Supervisado y Metodología
• Adalina
– Problema de Separación Lineal
Neurociencias – Neurona Natural
• Componentes
– Dendritas apicales y basales
– Nucleo y soma
– Axón y terminales presinápticas
Neurociencias – Organización
– Divergencia → sistemas sensoriales
– Convergencia → motoneuronas
Neurociencias – Funcionamiento
• Regiones Funcionales
–
–
–
–
Entrada → señales locales graduadas
Activador → generación de potencial de acción
Conductor → propaga potencial todo o nada
Salida → libera trasmisores
Agenda Redes Neuronales
• Introducción
– Motivación y Aplicaciones
• Neurociencias
– Redes Neuronales Naturales
• Neuronas Artificiales
– Modelo y Topologías
– Clasificación
• Aprendizaje
– Modelo Supervisado y Metodología
• Adalina
– Problema de Separación Lineal
Neurona Artificial – Modelo
• Componentes
– xi → señales de
entrada
– wki → pesos sinápticos
– Σ → integrador de
señal
– ϕ → función activación
– θk → umbral de
disparo
– yk → señal de salida
Neurona Artificial – Modelo
• Analogía Neuronas Naturales
Neurona Artificial – Modelo
• Función Activación
– Umbralizada - Signo
– Lineal por Segmentos
Neurona Artificial – Modelo
• Función Activación
– Sigmoide
Neurona Artificial – Modelo
• Representación Gráfica
n
Grafo de Flujo de Señales
n
Grafo Arquitectural
Neurona Artificial – Topología
• Red Prealimentada
n
Monocapa
n
Multicapa
Neurona Artificial – Topología
• Red Prealimentada
n
Conexión Parcial
• Retroalimentada
n
Recurrente
Neurona Artificial – Clasificación
• Supervisadas
– requieren maestro → proporciona ejemplos
• basada en reducción del «error»
• basada en «matching»
• NO-Supervisadas
– auto-organizadas → descubren propiedades
• competitivas
• correlacionales
• Retroalimentadas
– redes dinámicas → atractores en función
energía
Neurona Artificial – Clasificación
• Adalina → Estimador Lineal
Agenda Redes Neuronales
• Introducción
– Motivación y Aplicaciones
• Neurociencias
– Redes Neuronales Naturales
• Neuronas Artificiales
– Modelo y Topologías
– Clasificación
• Aprendizaje
– Modelo Supervisado y Metodología
• Adalina
– Problema de Separación Lineal
Aprendizaje – Modelo Supervisado
• Presentar Ejemplos
– Asociación Conocida
• entrada → salida deseada
• Calcular Pesos
– Adaptación
• corrección minimiza error
– Generalización
• entradas similares
producen salidas similares
Aprendizaje – Modelo Supervisado
• Ajuste Pesos Sinápticos → Depende del Error
Aprendizaje – Modelo Supervisado
• Ajuste Pesos Sinápticos → Depende del Error
Aprendizaje – Metodología
• Generar Ejemplos → deben ser representativos
– Separar Ejemplos → aleatoriamente
• conjunto entrenamiento → usados para calcular pesos
• conjunto prueba → usados para verificar calidad RN
• Calcular Pesos Sinápticos
– Entrenamiento Red → hasta minimizar error
• determinar topología → capas-conexiones-funciones
• inicializar red → aleatorio uniforme en rango pequeño
• aplicar algoritmo de aprendizaje → ajustar parámetros
– Validar Calidad
• evaluar error con conjunto de prueba → generalización
Aprendizaje – Ejemplo
• Clasificación de Formas
n
n
4 clases de aviones
48 descriptores → características medibles
Aprendizaje – Ejemplo
• Clasificación de
Formas
n
n
n
48 descriptores
n número neuronas capa
entrada
4 clases de aviones
n número neuronas capa
salida
26 neuronas en capa oculta
n inferior al número de capa
entrada
Agenda Redes Neuronales
• Introducción
– Motivación y Aplicaciones
• Neurociencias
– Redes Neuronales Naturales
• Neuronas Artificiales
– Modelo y Topologías
– Clasificación
• Aprendizaje
– Modelo Supervisado y Metodología
• Adalina
– Problema de Separación Lineal
Adalina - Widrow-Hoff
• Adapter Lineal Element → Estimador Lineal
Adalina – Estimador Lineal
• Minimizar Error Cuadrático
– → Descenso por Gradiente
Adalina – Separación Lineal
• Frontera → Línea Recta/Hiperplano
– clases deben ser linealmente separables
Adalina – Separación Lineal
• Ejemplos → Reconocimiento Patrones
– proceso progresivo de aprendizaje
RN – Separación Por Rectas
• Ejemplos → Separación por Líneas Rectas
– reconstruir cualquier frontera → requiere 3 capas
Conclusiones – Redes Neuronales
• RN emulan el comportamiento de las neuronas naturales
• sin embargo es muy difícil lograr en forma artificial el nivel de
complejidad de los sistemas naturales
• Familias de RN dependiendo del tipo de aprendizaje
• supervisado se debe suministrar un conjunto significativo de
ejemplos a partir de los cuales la red pueda generalizar
• no-supervisado se basa en la auto-organización
• Desarrollo de una RN es un trabajo “artesanal”
• requiere generación de ejemplos significativos
• determinación la topología y características de la red
• Aplicaciones más corrientes de la RN son las de “mapeo”
• reconocimiento de patrones o respuesta a estimulos.
Conclusiones – Comparación
Redes Neuronales Biológicas
Redes Neuronales Artificiales
Neuronas
Unidades de proceso
Conexiones sinápticas
Conexiones ponderadas
Efectividad de las sinápsis
Peso de las conexiones
Efecto excitatorio o inhibitorio
Signo del peso de una conexión
Efecto combinado de las sinápsis
Función de propagación o de red
Activación → tasa de disparo
Función de activación → Salida
Bibliografía Redes Neuronales
• Ham F.M., Principles of Neurocomputing for Science &
Engineering, McGraw Hill, 2001.
• Haykin S., Neural Networks : a Comprehensive Foundation,
Prentice Hall, 1994.
• Freeman J., Redes Neuronales : Algoritmos, Aplicaciones y
Técnicas de Programación, Addison-Wesley, 1993.
• Li H.X., Fuzzy Neural Intelligent Systems : Mathematical
Foundation and the Applications in Engineering, CRC Press,
2001.
• Martín del Río B., Redes Neuronales y Sistemas Difusos, Alfa
Omega, 2002.
Métodos Evolutivos
Agenda Métodos Evolutivos
• Introducción
– Computación Evolutiva
• Algoritmos Genéticos
– Aplicaciones e Inspiración Natural
– Componentes, Elementos y Algoritmo
– Validación Teórica
• Computación Evolutiva
–
–
–
–
Programación Evolutiva
Estrategías Evolutivas
Programación Genética
Clasificadores con Aprendizaje
Computación Evolutiva
• Idea Básica
– Hacer evolucionar una población de soluciones candidatas a
un problema.
• Origenes → años 50’s
–
–
–
–
–
Propósito Aprendizaje de Máquina y Optimización
Idea de búsqueda evolutiva (Turing)
Autómata autoreplicante (Von Newman)
Generación autonóma de programas (Friedberg)
Evolución simulada para solución de problemas
matemáticos (Bremermann)
Tipos de Aplicaciones
“El gran campo de aplicación de
los Algoritmos Genéticos se
relaciona con aquellos problemas
para los cuales
no existen
técnicas o modelos
especializados“
Agenda Métodos Evolutivos
• Introducción
– Computación Evolutiva
• Algoritmos Genéticos
– Aplicaciones e Inspiración Natural
– Componentes, Elementos y Algoritmo
– Validación Teórica
• Computación Evolutiva
–
–
–
–
Programación Evolutiva
Estrategías Evolutivas
Programación Genética
Clasificadores con Aprendizaje
Conceptos Básicos AGs
“A lo largo de las generaciones las
buenas características se propagan a
través de la población“
Elementos Básicos AGs
• Búsqueda en el Espacio del Problema
– Generación de estados a partir de los conocidos
Elementos Básicos AGs
• Evaluación de Alternativas
– Evaluación de Calidad
• Criterio de optimización ligado al problema
Elementos Básicos AGs
• Explotación
– Generar alternativas a partir de lo
conocido
• Mezclar las conocidas como buenas
Elementos Básicos AGs
• Exploración
– Buscar nuevas alternativas
• Modificar las ya conocidas como
buenas
Conceptos Básicos AGs
• Población de Individuos
– Individuo representa una solución factible a un problema
• equivale al conjunto de organismos que están vivos
Conceptos Básicos AGs
• Evaluación de Individuos
– Cada individuo es evaluado para medir su calidad
• calidad con respecto al problema
• asigna de un valor ó puntuación
– Equivale a la efectividad de un organismo para
competir
• por unos determinados recursos
• en un ambiente determinado
Conceptos Básicos AGs
• Selección
– A mayor adaptación del individuo, mayor es la probabilidad
de ser seleccionado para reproducirse
• solo los mejores sobreviven
Conceptos Básicos AGs
• Reproducción
– Se produce una nueva población de posibles soluciones
• individuos generados mediante operadores genéticos
• reemplazo de la población anterior
– El proceso evolutivo no tiene memoria
• un nuevo individuo no recuerda quienes son sus antecesores
Algoritmo Genético Básico
Generar
Población Inicial
Producir Nueva
Generación
Generar Descendientes
Evaluar
Población Inicial
Aplicar Operadores
Genéticos
Computar Función de
Evaluación de los
Descendientes
NO
Producir Nueva
Generación
Insertar Descendientes
en la Población
Verificar si la
Población ha
Convergido
SI
FIN
Conclusiones AGs
– Los AGs se basan en reproducir la idea básica de
la evolución
• las buenas características se propagan a
través de la población
– Los elementos básicos de un AG son:
• la población
• el fitness
• la selección y los operadores genéticos
Conclusiones AGs
– Matemáticamente se puede demostrar que los
AGs convergen a una buena solución
• en la práctica es indispensable diseñar una
buena función de fitness
– El principal tipo de aplicación de los AGs es la
búsqueda de una solución “óptima” en un
espacio-problema
Bibliografia AGs
• E. Falkenauer, “Genetic Algorithms and Grouping
Problems”, 1998.
• D. Dumitrescu, “Evolutionary Computation”, CRC
Press, 2000.
Gracias por su Atención
• Ing. Enrique González Ph.D.
– Pontificia Universidad Javeriana
– Departamento Ingeniería de Sistemas
– email: [email protected]