Algoritmos Genéticos

Diego Herrera

Oscar Sanhueza

http://www.educagratis.org

• En el Aula Virtual online de Educagratis ( http://www.educagratis.org ) es posible encontrar un curso gratis de Inteligencia Artificial (http://computacion.educagratis.org ) en el cual se tratan los siguientes contenidos:

• - BILIOGRAFIA DEL CURSO• - INTRODUCCION A LA IA• - BUSQUEDA• - LENGUAJE DE IA• - HIPERGRAFOS• - ARBOLES DE JUEGOS• - REPRESENTACION DEL CONOCIMIENTO CON LOGICA DE PREDICADOS• - SOFTWARE DE INTELIGENCIA ARTIFICIAL• - ENLACES IMPORTANTES• - TEMAS Y SITIOS RELACIONADOS CON IA

Historia

Los algoritmos genéticos (AG), fueron inventados en

1975 por John Holland, de la Universidad de

Michigan.

Se los llamó "genéticos", porque se basaban en los

modelos biológicos, inspirados en ellos, y también

tenía relación con lo molecular.

¿Que son los algoritmos genéticos?

Los AG son métodos de búsqueda y optimización.

Se utilizan en problemas donde no se pueden

encontrar soluciones o estas no son satisfactorias

Son algoritmos basados en los principios de la

genética y evolución natural.

Estructura de los A.G.

Un algoritmo genético esta compuesto por una

serie de pasos que permite evaluar las

soluciones candidatas.

Función Objetivo

Selección

Representación

Operadores genéticos

Estructura de los A.G.

Función Objetivo: Asignar a cada individuo (x) de una

población un valor optimo que le corresponda utilizando para

este mecanismos de selección que identifican las mejores

soluciones.

La Selección: una vez se tiene una población y se evalúa, se

asigna una probabilidad de supervivencia directamente

proporcional a lo obtenido en la evaluación del individuo.

Luego aleatoriamente se eligen los individuos que pasaran a la

siguiente etapa.

http://computacion.educagratis.org

Estructura de los A.G.

Representación: Es la forma en que el usuariorepresenta los resultados de la ejecución del algoritmocon la selección del mejor(es) individuo(s).

Tipos:• Representación binaria: Cada gen es un valor 1 ó 0.

1 0 1 1 0 1

• Representación entera: Cada gen es un valor entero.

1 0 3 -1 0 4

• Representación real: Cada gen es un valor real.

1,78 2,6 7 0 -1,2 6,5

http://computacion.educagratis.org

Estructura de los A.G.

Operadores Genéticos: Una vez que la selección ha

elegido a los individuos aptos, éstos deben ser

alterados aleatoriamente con la esperanza de mejorar

su aptitud para la siguiente generación.

• Mutación

• Crossover (cruza)

http://computacion.educagratis.org

Estructura de los A.G.Mutación:

El termino mutación quiere decir “cambio”, así como en la naturaleza lasespecies cambian para sobrevivir en un entorno cambiante, en la IA se buscaobtener las mejores soluciones a través de la variación de dichas soluciones.

Método Clásico: escoger aleatoriamente cierta cantidad de cromosomas y alterarlos aleatoriamente.

Es útil para:

– Regresar genes perdidos durante la selección para probarlos en otro contexto

– Trayendo genes no presentes en la población inicial

Parámetro Clásico: “Tasa de Mutación”. Pm=% de los genes a mutar

Si Pm es alto:

– los hijos perderán los rasgos de los padres. El algoritmo deja de aprender.

Si Pm es bajo:

– muchos genes que pudiesen ser útiles, dejan de ser explorados.

Estructura de los A.G. Crossover (cruza):

Implica elegir a dos individuos para que intercambien segmentos de su código, produciendo una “descendencia'' artificial cuyos individuos son combinaciones de sus padres.

Método Clásico: escoger aleatoriamente un punto de corte en ambos padres y generar hijos combinando los segmentos a cada lado del corte.

Es útil para:

– Incentivar la mezcla de rasgos de los padres, en busca de hijos mejores que ambos padres

Parámetro Clásico: “Tasa de Crossover”. Pc=|C|/|P|

Si Pc es alto:

– poca probabilidad de atascamiento en un óptimo local

– alto costo explorando regiones poco prometedoras

http://computacion.educagratis.org

Ventajas

No necesitan conocimientos específicos sobre el

problema que intentan resolver.

Operan de forma simultánea con varias soluciones, en

vez de trabajar de forma secuencial como las técnicas

tradicionales.

Resulta sumamente fácil ejecutarlos en las modernas

arquitecturas masivas en paralelo.

Desventajas

No hay un marco teórico genérico establecido.

Si la población inicial es cercana a la solución óptima, los AG

tardarán más que las técnicas de resolución tradicionales.

• El AG perderá mucho tiempo comprobando soluciones

sub-óptimas.

Hacen buenas estimaciones de la solución óptima, pero no la

calculan exactamente.

El usuario debe determinar cómo de cerca está la solución

estimada de la solución real.

• La proximidad a la solución real dependerá de la

aplicación en concreto.

Aplicaciones de A.G.

Aprendizaje de comportamiento de robots.

Optimización de estructuras moleculares.

Diseño de topologías de redes

computacionales.

Diseño automatizado de equipamiento

industrial.

Aplicaciones de A.G.

FILTRO EN LA TRANSACCIÓN DE ACCIONES

Le permite a los agentes involucrados definir una estrategia

sobre cuándo comprar o vender sus acciones, a partir de la

determinación de ciertos parámetros.

Aplicaciones de A.G.

MEJORAR EL PROCESO DE PROGRAMACIÓN DEL RODAJE EN LA

INDUSTRIA DEL CINE INDEPENDIENTE

El proceso busca programar la filmación de cada una de las

escenas de una película con el mínimo costo posible y sin

comprometer la calidad del proyecto cinematográfico.

Aplicaciones de A.G.

Google y Facebook

Ocupan algoritmos genéticos para decidir cuales son

las páginas web más importantes y como se

relacionan los usuarios.

Aplicaciones de A.G.

Seguridad informática

Los investigadores Michael Crouse y Errin Fulp de la universidad de

Harvard están creando la primera computadora que de forma automática

ajusta su configuración para defenderse de ataques informáticos.

Ellos utilizan los algoritmos para seleccionar las mejores

configuraciones; configuraciones adaptables, que van mejorando de

generación en generación.

A.G. en el Cine

Tron legacy: Plantea una evolución de los actuales algoritmos

genéticos, lo cual provoca programas que no están hechos por

programadores.

SW de Algoritmos Genéticos

Gatree

• Versión gratuita

• Versión comercial € 200 (más IVA).

• Licencia de Estudiante € 30 (más IVA).

http://computacion.educagratis.org

SW de Algoritmos Genéticos

FET :

crea un posible horario, este horario se somete a muchoscambios con los que se van seleccionando los mejoreshorarios, para obtener finalmente un horariorazonablemente bueno.

Funciona en: Win2000 en adelante

Idioma: Español

Tamaño: 154 Mb

Licencia: gratis

Open Source

• En el Aula Virtual online de Educagratis ( http://www.educagratis.org ) es posible encontrar un curso gratis de Inteligencia Artificial (http://computacion.educagratis.org ) en el cual se tratan los siguientes contenidos:

• - BILIOGRAFIA DEL CURSO• - INTRODUCCION A LA IA• - BUSQUEDA• - LENGUAJE DE IA• - HIPERGRAFOS• - ARBOLES DE JUEGOS• - REPRESENTACION DEL CONOCIMIENTO CON LOGICA DE PREDICADOS• - SOFTWARE DE INTELIGENCIA ARTIFICIAL• - ENLACES IMPORTANTES• - TEMAS Y SITIOS RELACIONADOS CON IA

http://computacion.educagratis.org

VISITANOS EN:

http://www.educagratis.org

.. Y para más cursos relacionados con Inteligencia Artificial, Ciencias de la Computación, Sistemas Expertos y mucho más:

Y muchos otros cursos de diversas áreas:

- Animales, Aves y Peces ( http://animales.educagratis.org )- Artes, Diseño, Pintura y Dibujo ( http://artes.educagratis.org )- Autoayuda ( http://autoayuda.educagratis.org )- Belleza y Moda ( http://belleza.educagratis.org )- Ciencias Alternativas ( http://alternativas.educagratis.org )- Ciencias Naturales ( http://ciencias.educagratis.org )- Ciencias Sociales y Juridicas ( http://sociales.educagratis.org )- Cocina, Bebidas, Pastelería y Repostería ( http://cocina.educagratis.org )- Computación e Informática ( http://computacion.educagratis.org )- Construcción, Arquitectura y Paisajismo ( http://construccion.educagratis.org )

- Deportes y Educación Física ( http://deportes.educagratis.org )- Educación, Religión y Filosofía ( http://educacion.educagratis.org )- Historia, geografía, tradiciones y cultura ( http://historia.educagratis.org- Hogar, Tejido, Borado y Jardín ( http://hogar.educagratis.org )- Idiomas, Lenguaje y Letras ( http://idiomas.educagratis.org )- Juegos, Recreación y Pasatiempos ( http://juegos.educagratis.org )- Matemáticas ( http://matematicas.educagratis.org )- Mecánica, Autos y Motos ( http://mecanica.educagratis.org )- Medicina, Psicología y Salud ( http://medicina.educagratis.org )- Musica, Baile y Danza ( http://musica.educagratis.org )- Negocios, Empresa y Economía ( http://negocios.educagratis.org )- Técnicos, Oficios y Manualidades ( http://tecnicos.educagratis.org )