Presentacion_Algoritmos_Geneticos_1C2015

Universidad Tecnológica Nacional
Facultad Regional Buenos Aires

ALGORITMOS GENÉTICOS

Inteligencia Artificial
Ciclo lectivo – 2015
Docentes: M. Ing. María Florencia Pollo Cattaneo
Dr. Pablo Pytel
Ing. Cinthia Vegega
Ing. Hugo Ramón

INTELIGENCIA ARTIFICIAL
Problemas que no se pueden resolver por un enfoque algorítmico
tradicional
Permite manejar la imprecisión e incertidumbre

A LG O R IT MO S GE N É T IC O S
“Los Algoritmos Genéticos son algoritmos matemáticos de
optimización de propósito general basados en
mecanismos naturales de selección y genética,
proporcionando excelentes soluciones en problemas
complejos con gran número de parámetros”

UTN FRBA

Inteligencia Artificial (AG v. 10)

1

TEORÍA EVOLUTISTA
PRINCIPALES POSTULADOS
• Las formas de vida no son estáticas sino queevolucionan.
• El proceso de la evolución es gradual, lento y continuo.
• Los organismos parecidos se hallan emparentados y descienden de un
antepasado común.
• La selección natural es la llave, que explica todo el sistema.

UTN FRBA

Inteligencia Artificial (AG v. 10)

TEORÍA EVOLUTISTA
SELECCIÓN NATURAL
- La producción de variabilidad: generación de modificaciones
espontáneas en los individuos.

- Lasupervivencia del más fuerte (apto) en la lucha por la vida.

UTN FRBA

Inteligencia Artificial (AG v. 10)

2

TEORÍA EVOLUTISTA
CONCEPTOS
 Ecosistema
 Población
 Individuo

UTN FRBA

Inteligencia Artificial (AG v. 10)

TEORÍA EVOLUTISTA
CONCEPTOS

 Genotipo

 Fenotipo

UTN FRBA

Inteligencia Artificial (AG v. 10)

3

ALGORITMOS GENÉTICOS
Teoría Evolución

Algoritmos Genéticos

Ecosistema /Ambiente

Problema

Individuo

Posible Solución

Genotipo / Cromosoma

Descripción de la Solución

Gen

Característica o Atributo

Fenotipo

Función de Aptitud

UTN FRBA

Inteligencia Artificial (AG v. 10)

ALGORITMOS GENÉTICOS
[Holland, 1975]

 Genotipo /
Cromosoma

Gen 1

Gen 2

Gen 3

…

Gen N

…
( cadena de bits )

 Fenotipo /
Función de Aptitud

f (x) : Cromosoma  
UTN FRBA

InteligenciaArtificial (AG v. 10)

4

ALGORITMOS GENÉTICOS
Máximo
Óptimo
Máximo
Local
Máximo
Local

f (x )
Gen i

Gen j

UTN FRBA

Inteligencia Artificial (AG v. 10)

EJEMPLO: “el acertijo de Einstein”
Tenemos 5 casas de cinco colores diferentes y en cada una de ellas vive una persona de una
nacionalidad diferente. Cada uno de los dueños bebe una bebida diferente, fuma una marca de
cigarrillos diferente ytiene una mascota diferente.
Se tienen las siguientes pistas:
• El británico vive en la casa roja.
• El sueco tiene un perro.
• El danés toma té.
• La casa verde esta a la izquierda de la blanca.
• El dueño de la casa verde toma café.
• La persona que fuma Pall Mall tiene un pájaro.
• El dueño de la casa amarilla fuma Dunhill.
• El que vive en la casa del centro toma leche.
• El noruego vive en laprimera casa.
• La persona que fuma Brends vive junto a la que tiene un gato.
• La persona que tiene un caballo vive junto a la que fuma Dunhill.
• El que fuma Bluemasters bebe cerveza.
• El alemán fuma Prince.
• El noruego vive junto a la casa azul.
• El que fuma Brends tiene un vecino que toma agua.
Se pregunta: ¿quién es el dueño del pececito?

UTN FRBA

Inteligencia Artificial (AG v. 10)

5EJEMPLO: “el acertijo de Einstein”
Casa

1. Definición del Cromosoma

tiene
Bebida

 Conceptos:

bebe

fuma

Dueño

Cigarrillo

tiene
Mascota

 Variables:
•

Nacionalidad del Dueño

= { británico, sueco, danés, alemán, noruego }

•

Ubicación de la Casa

= { primera, segunda, tercera, cuarta, quinta }

•

Color de la Casa

= { roja, verde, blanca, amarilla, azul }

•

Tipo de Bebida

= { té,café, leche, cerveza, agua }

•

Nombre del Cigarrillo

= {Pall Mall, Dunhill, Brends, Bluemasters, Prince }

•

Tipo de Mascota
británico

casa-ubic.

Gen Principal

Genes Auxiliares

= { perro, pájaro, gato, caballo, pececito }
sueco

casa-color

danés

bebida

UTN FRBA

alemán

cigarrillo

noruego

mascota

Inteligencia Artificial (AG v. 10)

EJEMPLO: “el acertijo de Einstein”
2. Definición de la...