Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Algoritmos Genéticos

No description
by

Shirly Castillo

on 28 May 2011

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Algoritmos Genéticos

ALGORITMOS
GENETICOS



SHIRLEY CASTILLO
Ing de Sistemas 9no .

Métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización.
Están basados en el proceso genético de los organismos vivos.
Por imitación del proceso evolutivo, los AGs son capaces de ir creando soluciones para problemas del mundo real.
Consisten en una función matemática o una rutina de software que toma como entradas a los ejemplares y retorna como salidas cuales de ellos deben generar descendencia para la nueva generación. DEFINICIÓN John Koza:

"Es un algoritmo matemático altamente paralelo que transforma un conjunto de objetos matemáticos individuales con respecto al tiempo usando operaciones modeladas de acuerdo al principio Darwiniano de reproducción y supervivencia del más apto, y tras haberse presentado de forma natural una serie de operaciones genéticas de entre las que destaca la recombinación sexual. Cada uno de estos objetos matemáticos suele ser una cadena de caracteres (letras o números) de longitud fija que se ajusta al modelo de las cadenas de cromosomas, y se les asocia con una cierta función matemática que refleja su aptitud. " .

A finales de los 50 y principios de los 60, primeros ejemplos, programados en computadoras por biólogos evolutivos
A fines de los 60s un investigador de la Universidad de Michigan llamado John Holland consciente de la importancia de la selección natural, desarrolló una técnica cuyo objetivo era lograr que las computadoras aprendieran por sí mismas. A la técnica se le llamó "planes reproductivos".
En 1970, tras la publicación de su libro``Adaptación en Sistemas Naturales y Artificiales'' , la técnica se hizo popular bajo el nombre AGs, llamados así porque se inspiran en la evolución biológica y su base genético-molecular. 
En 1999, por primera vez en la historia, se concedió una patente a un invento no realizado directamente por un ser humano: se trata de una antena de forma extraña, pero que funciona perfectamente en las condiciones a las que estaba destinada. HISTORIA ..



Los AGs establecen una analogía entre el Fenotipo y el conjunto de individuos de una población natural, codificando la información de cada solución en cromosomas..

Fenotipo: conjunto de soluciones de un problema
Cromosoma: Cadena, generalmente binaria
Genotipo: Cuando la representación de los cromosomas se hace con cadenas de dígitos binarios
Genes: símbolos que forman la cadena
Generaciones: iteraciones mediante las cuales los cromosomas evolucionan. En cada generación, los cromosomas son evaluados usando alguna medida de aptitud
Descendencia: Son las siguientes generaciones (nuevos cromosomas), que se forman utilizando dos operadores genéticos, de sobrecruzamiento y de mutación .


Inicialización ------> Se genera aleatoriamente la población inicial, que está constituida por un conjunto de cromosomas los cuales representan las posibles soluciones del problema.
Evaluación ------> A cada uno de los cromosomas de esta población se aplicará la función de aptitud para saber qué tan "buena" es la solución que se está codificando.
Condición de término ------> El AG se deberá detener cuando se alcance la solución óptima, pero ésta generalmente se desconoce, por lo que se deben utilizar otros criterios de detención.
1. Correr el AG un número máximo de iteraciones (generaciones)
2. Detener el AG cuando no haya cambios en la población.
Mientras no se cumpla la condición de término se hace lo siguiente:
Selección.
Sobrecruzamiento.
Mutación.
Reemplazo .

Selección elitista
Selección proporcional a la aptitud.
Selección por rueda de ruleta.
Selección escalada.
Selección por torneo.
Selección por rango.
Selección generacional.
Selección por estado estacionario.
Selección jerárquica. FUNCIONAMIENTO ALGORITMO GENETICO BASICO METODOS DE SELECCIÓN .
Antena genética de .
alambre doblado
(Altshuler y Linden
1997)
Brazo tridimensional
optimizado
genéticamente, con
una respuesta
mejorada a la
frecuencia VENTAJAS .


Son intrínsecamente paralelos cosa que les permite evaluar implícitamente muchos esquemas a la vez (Teorema del esquema) .
Funcionan bien resolviendo problemas cuyo espacio de soluciones potenciales es realmente grande para hacer una búsqueda exhaustiva en un tiempo razonable.
Se desenvuelven bien en problemas con un paisaje adaptativo complejo.
Tienen habilidad para manipular muchos parámetros simultáneamente.
No saben nada de los problemas que deben resolver. Son ``relojeros ciegos'' realizan cambios aleatorios en sus soluciones candidatas y luego utilizan la función de aptitud para determinar si esos cambios producen una mejora.  .


Diseño de topologías de redes computacionales.
Teoría de juegos.
Análisis de expresión de genes.
Aprendizaje de comportamiento de robots.
Aprendizaje de reglas de Lógica difusa.
Infraestructura de redes de comunicaciones móviles.
Optimización de estructuras moleculares.
Predicción.
Bioinformática. GRACIAS APLICACIONES
Full transcript