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 )