PDF de programación - Informática Evolutiva para la Optimización de Problemas

Informática Evolutiva para la
Informática Evolutiva para la
Optimización de Problemas
Optimización de Problemas

Prof. Wílmer Pereira

Universidad Católica Andrés Bello

Universidad Simón Bolívar

http://www.ldc.usb.ve/~wpereira
http://www.ldc.usb.ve/~wpereira

Informática Evolutiva y Optimización

Prof. Wílmer Pereira

UCAB/USB

Resolución de problemas
Resolución de problemas
complejos ...
complejos ...


Hilbert formula 23 problemas en París. El segundo (mostrar la consistencia
de las matemáticas a partir de su axiomática) era esperanzador … pero …
Russel&Whitehead se topan con problemas … además existen, según el teorema
de incompletitud de Gödel, problemas indecidibles … IGNORABIMUS ...
Entre los problemas decidibles, tenemos problemas cuya exigencias en
tiempo de cálculo o peticiones de memoria crece exponencialmente,
es decir, problemas intratables:

NP-Exp
NP-Duros
NP-Completos ...

Soluciones posibles:

Dividir el problema y paralelizarlo pero … sería necesario un crecimiento
exponencial en la cantidad de procesadores disponibles :-( ...

Introducir heurísticas particulares al problema que se pretende resolver
pero … no es general (deep blue) y no hay garantía de que las intuiciones

conduzcan a una estrategia que permita llegar a las soluciones óptimas :-( ...
UCAB/USB

Prof. Wílmer Pereira

Informática Evolutiva y Optimización

Ejemplo de Intratabilidad:
Ejemplo de Intratabilidad:
satisfactibilidad
satisfactibilidad


Dada una tabla de verdad con 5 o 6 variables -> 25 = 32 o 26 = 64 filas.
Un humano con suficiente paciencia no tendría mayores problemas
Hasta cierto límite, un computador también puede realizar la tarea sin
mayores inconvenientes ...

Imaginemos un computador con el cual podemos procesar el valor de verdad
de cada fila de la tabla en 1 ηseg (10-9 seg). Una tabla de 40 variables implica
240 filas es decir 1012 – alrededor de un billon de filas –
Con un cálculo sencillo, el tiempo estimado sería de

… lo cual representa alrededor de 16 minutos de procesamiento.

1012*10-9 = 1000 seg

Con 100 variables, implica aproximadamente un quintillon de filas (1030).

1030*10-9 = 1021 seg

lo que representa 3.17 * 1011 siglos de cálculo ... solo para llenar la tabla ...
Esto sin tomar en cuenta el espacio necesario para contener la tabla de
un quintillon de filas en el disco del computador ...

Informática Evolutiva y Optimización

Prof. Wílmer Pereira

UCAB/USB

Genética y Evolución
Genética y Evolución

Base para la herencia y variabilidad de los
Base para la herencia y variabilidad de los

seres vivos
seres vivos

Dentro del núcleo se encuentra el ADN que permite ensamblar las proteinas.
El ADN formado por cadenas de bases nitogenadas:

Adenina
Citosina

Guanina
Timina

La fecundación se realiza mediante el cruce (en la meiosis) y la mutación

Selección natural debida a la competencia (Darwin) y la presión ecológica (Wallace)
Gradualismo vs Equilibrio puntuado
Coevolución

Huesped-Parásito, Presa-Depredador o Conflicto Sexual

Competitiva

Cooperativa

Simbiosis

Informática Evolutiva y Optimización

Prof. Wílmer Pereira

UCAB/USB

Algoritmos Genéticos
Algoritmos Genéticos
John Holland (1960)
John Holland (1960)


Codificación:

Gen: son las variables del problema codificadas en binario
Cromosoma:individuos:o soluciones del problema

Función de Aptitud:



Heurística para indicar la bondad de una solución
o que tan apto es un individuo

Criterios de Selección:

Ruleta: la probabilidad de seleccionar cada individuo es proporcional
Torneo: selección por turnos de soluciones para escojer las dos mejores
Elitista: los individuos con mejor aptitud son seleccionados

Operadores Genéticos:

Cruce: nuevas soluciones a partir de dos padres
Mutación: probabilidad de cambiar aleatoriamente un bit de una variable

1

1

0

1

0

0

1

1

Informática Evolutiva y Optimización

Prof. Wílmer Pereira

UCAB/USB

CruceCruce

1

0

1

1

1

0

0

1

0

1

1

0

1

1

1

0

1

0

1

0

1

1

1

0

0

1

1

1

1

0

0

1

Informática Evolutiva y Optimización

Prof. Wílmer Pereira

UCAB/USB

Algoritmo Genético de Base
Algoritmo Genético de Base

Generar una población de soluciones inicial

Seleccionar los individuos de la población

(Soluciones del problema)

Cruzar los individuos

Mutar los individuos con una

baja probabilidad

Insertar los nuevos individuos de la

próxima generación

Parar según un criterio de satisfacción

Informática Evolutiva y Optimización

Prof. Wílmer Pereira

UCAB/USB

Condiciones de Aplicación
Condiciones de Aplicación
de un Algoritmo Genético
de un Algoritmo Genético

¿Cómo codificar el problema, es decir, cuales son las
variables relevante para resolverlo?

¿Qué método de selección es el adecuado para obtener los
mejores resultados?

¿Cómo definir la función de aptitud para determinar que es
una buena solución?

¿Cómo combinar la carga genética de los individuos para
aumentar el valor de la función de aptitud?

¿Cuántas generaciones son necesarias para el mejor
sub-óptimo posible?

La respuesta a cada pregunta es dependiente del problema y no hay manera
de saber con certeza la mejor opción … afortunadamente se demostró la
convergencia de la estrategia genética … al menos ...

Informática Evolutiva y Optimización

Prof. Wílmer Pereira

UCAB/USB

Redes Neurales Naturales
Redes Neurales Naturales

Estructura celular del cerebro donde residen las capacidades
Estructura celular del cerebro donde residen las capacidades
intelectuales del hombre. Desde 100x109 hasta 10x1012 neuronas …
intelectuales del hombre. Desde 100x109 hasta 10x1012 neuronas …
Neurona:
Soma:
Dendritas:
Sinapsis:

Célula nerviosa
Núcleo celular
Ramificaciones entre neuronas
Punto de unión entre dendritas
10.000 en promedio por neurona

Reacciones
Electroquímicas

Impulsos Inhibidores o
Impulsos Excitatorios

Interneuronas
Neuronas motoras
(directo al músculo)
Neuronas receptoras
(directo desde el órgano
sensor)

Informática Evolutiva y Optimización

Prof. Wílmer Pereira

UCAB/USB

Cerebro vs Computador
Cerebro vs Computador

Almacenamiento:

Velocidad.

Tolerancia a fallas:

Más neuronas que bits aunque la evolución
computacional es vertiginosa (mucho mayor
que la evolución de cerebro)
Computador orden de los h seg
Cerebro del orden de los mseg
pero ... el cerebro es masivamente paralelo y
en definitiva el cerebro es 1010 veces más rápido
Una neurona natural dañada afecta de manera
marginal el comportamiento del cerebro
Cualquier mínimo error altera todo el
procesamiento a nivel del computador

Complejidad de ejecución: El cerebro realiza tareas muy complejas

Procesamiento:

que son sencillas al humano pero difíciles
para cualquier computador
Centralizado vs Distribuido
Computador Cerebro

Informática Evolutiva y Optimización

Prof. Wílmer Pereira

UCAB/USB

Redes Neurales Artificiales
Redes Neurales Artificiales

Unidades enlazadas a través de conexiones
Unidades enlazadas a través de conexiones

cargadas por pesos numéricos
cargadas por pesos numéricos

El aprendizaje se basa en la actualización de esos pesos que se inicializan en la
fase de entrenamiento de la red

Está formada por unidades de entrada y unidades de salida
(neuronas de entrada y neuronas de salida)

El nivel de activación de la neurona artificial (equivalente al impulso excitatorio)
es un cálculo individual en cada neurona, sin control global

Entradas:
Digitales
o
Continuas

Salidas:
McCulloch_Pitts: 0 ó 1
Ising: -1 ó +1
Potts: -2,-1,0,1,2

Informática Evolutiva y Optimización

Prof. Wílmer Pereira

UCAB/USB

Componentes de la Neurona
Componentes de la Neurona

Función de Propagación
Función de Propagación

Suma Ponderada

Distancia Euclediana

ini = S
ini = S

Wj,iaj

aj – Wj,i

Funciones de Activación
Funciones de Activación

Manhattan, Sigma-Pi, ...

Función de salida normalmente
es la identidad aunque puede ser
Estocástica

La activación de toda la red puede
ser síncrona o asíncrona

Informática Evolutiva y Optimización

Prof. Wílmer Pereira

UCAB/USB

Condiciones de Estabilización
Condiciones de Estabilización

Las redes unidireccionales no tiene problemas de estabilidad pero
Las retroalimentadas si … deben cumplir ciertas condiciones para
Converger a un estado estable o punto fijo …

Condiciones y función de Lyapunov:

a) El sistema está en reposo sólo en el origen
b) Existen variables de entrada que describen todo el dominio
c) las variables están acotadas
Sean V las variables xi de entrada V: Rn -> R

.
V

= Σn

i=1 dV / dxi <= 0, para todo xi

Además computacionalmente como una red neural puede representar
un NAND el cual a su vez puede representar cualquier función booleana
significa que son capaces de representar cualquier problema

Informática Evolutiva y Optimización

Prof. Wílmer Pereira

UCAB/USB

Perceptrón (feed forward)
Perceptrón (feed forward)

Red neural lineal a dos capas
Red neural lineal a dos capas

(sólo neuronas de entrada y salida)
(sólo neuronas de entrada y salida)

El perceptrón aprende comenzando con pesos aleatorios ajustandolos mientras se entrena
(sencillo pues las neuronas de entrada van conectadas directamente con las de salida)

Err = T – O
Si Err > 0 aumentar O sino disminuir O
Wj = Wj + a .Ij.Err

O : ejemplo predicho
T : ejemplo correcto
a : velocidad de aprendizaje

Informática Evolutiva y Optimización

Prof. Wílmer Pereira

UCAB/USB

Problemas del Perceptrón
Problemas del Perceptrón

Minsky y Papert publicaron en 1969, un artículo donde mostraron
Minsky y Papert publicaron en 1969, un artículo donde mostraron

las limitaciones de los perceptrones
las