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 Geneticos

Inteligencia Artificial
by

Saul Sanchez Cuevas

on 24 September 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Algoritmos Geneticos

Inteligencia Artificial Algoritmos Geneticos Un algoritmo es una serie de pasos organizados que describe el proceso que se debe seguir, para dar solución a un problema específico.
En los años 1970, de la mano de John Henry Holland, surgió una de las líneas más prometedoras de la inteligencia artificial, la de los algoritmos genéticos. Son llamados así porque se inspiran en la evolución biológica y su base genético-molecular. Algoritmo genético Estos algoritmos hacen evolucionar una población de
individuos sometiéndola a acciones aleatorias semejantes
a las que actúan en la evolución biológica (mutaciones y
recombinaciones genéticas), así como también a una Selección
de acuerdo con algún criterio, en función del cual
se decide cuáles son los individuos
más adaptados,que sobreviven, y cuáles los
menos aptos, que son descartados. Un algoritmo genético es un método de búsqueda dirigida basada en probabilidad. Bajo una condición muy débil
(que el algoritmo mantenga elitismo, es decir, guarde siempre al mejor elemento de la población sin hacerle ningún cambio) se puede demostrar que el algoritmo converge en probabilidad al óptimo. En otras palabras, al aumentar el número de iteraciones, la probabilidad de tener el óptimo en la población tiende a 1 (uno). Funcionamiento Los algoritmos entre el conjunto de soluciones de un problema, llamado fenotipo, y el conjunto de individuos de una población natural, codificando la información de cada solución en una cadena, generalmente binaria, llamada cromosoma. Los símbolos que forman la cadena son llamados los genes. Cuando la representación de los cromosomas se hace con cadenas de dígitos binarios se le conoce como genotipo. Los cromosomas evolucionan a través de iteraciones, llamadas generaciones. En cada generación, los cromosomas son evaluados usando alguna medida de aptitud. Las siguientes generaciones (nuevos cromosomas), operadores genéticos, de sobre cruzamiento y de mutación. Lucia Torrijo Gutierrez
Stphany Cruz Rivera
Ana Maria Castro Maciel
Alejandro Antonio Lopez Patiño
Saul Sanchez Cuevas
Los algoritmos genéticos son de probada eficacia en caso de querer calcular funciones no derivables (o de derivación muy compleja) aunque su uso es posible con cualquier función.

Deben tenerse en cuenta también las siguientes consideraciones:

• Si la función a optimizar tiene muchos máximos/mínimos
locales se requerirán más iteraciones del algoritmo para "asegurar" el máximo/mínimo global.
• Si la función a optimizar contiene varios puntos muy cercanos
en valor al óptimo, solamente podemos "asegurar" que
encontraremos uno de ellos (no necesariamente el óptimo). Cuándo usar estos algoritmos Un algoritmo genético puede presentar diversas variaciones,
dependiendo de cómo se aplican los operadores genéticos
(cruzamiento, mutación), de cómo se realiza la selección
y de cómo se decide el reemplazo de los individuos para
formar la nueva población. En general, el pseudocódigo
consiste de los siguientes pasos: Funcionamiento de un algoritmo genético básico Algoritmo genético
i: inicialización,
f(X): evaluación,
?: condición de término,
Se: selección,
Cr: cruzamiento,
Mu: mutación,
Re: reemplazo,
X*: mejor solución. Se genera aleatoriamente la población inicial, que está constituida por un conjunto de cromosomas los cuales representan las posibles soluciones del problema. En caso de no hacerlo aleatoriamente, es importante garantizar que dentro de la población inicial, se tenga la diversidad estructural de estas soluciones para tener una representación de la mayor parte de la población posible o al menos evitar la convergencia prematura. Inicializació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. Evaluación: 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. Normalmente
se usan dos criterios: correr el AG un
número máximo de iteraciones (generaciones)
o detenerlo cuando no haya cambios en
la población. Mientras no se cumpla la
condición de término se hace lo siguiente: Condición de término Después de saber la aptitud de
cada cromosoma se procede a
elegir los cromosomas que serán
cruzados en la siguiente generación.
Los cromosomas con mejor aptitud
tienen mayor probabilidad de ser
seleccionados. Selección La recombinación es el principal
operador genético, representa la
reproducción sexual, opera sobre
dos cromosomas a la vez para
generar dos descendientes
donde se combinan las
características de ambos
cromosomas padres. Recombinación Modifica al azar parte del cromosoma
de los individuos, y permite alcanzar
zonas del espacio de búsqueda que no
estaban cubiertas por los individuos
de la población actual. Mutación Una vez aplicados los operadores
genéticos, se seleccionan los
mejores individuos para conformar
la población de la generación siguiente Reemplazo • Diseño automatizado
• Diseño automatizado de equipamiento industrial.
• Diseño automatizado de sistemas de comercio en el sector financiero.
• Construcción de árboles filogenéticos.
• Optimización de carga de contenedores.
• Diseño de sistemas de distribución de aguas.
• Diseño de topologías de circuitos impresos.
• Diseño de topologías de redes computacionales.
• En Teoría de juegos, resolución de equilibrios.
• Análisis de expresión de genes.
• Aprendizaje de comportamiento de robots.
• Aprendizaje de reglas de Lógica difusa.
• Análisis lingüístico, incluyendo inducción gramática, y otros aspectos de Procesamiento de lenguajes naturales, tales como eliminación de ambigüedad de sentido.
• Infraestructura de redes de comunicaciones móviles.
• Optimización de estructuras moleculares.
• Planificación de producción multicriteria.
• Predicción.
• Aplicación de Algoritmos Genéticos al Dilema del prisionero Iterado
• Optimización de sistemas de compresión de datos, por ejemplo, usando wavelets.
• Predicción de Plegamiento de proteínas.
• Optimización de Layout.
• Predicción de estructura de ARN.
• En bioinformática, Alineamiento múltiple de secuencias.
• Aplicaciones en planificación de procesos industriales, incluyendo planificación job-shop.
• Selección óptima de modelos matemáticos para la descripción de sistemas biológicos.
• Manejo de residuos sólidos.
• Ingeniería de software.
• Construcción de horarios en grandes universidades, evitando conflictos de clases.
• Problema del viajante.
• Hallazgo de errores en programas.
• Optimización de producción y distribución de energía eléctrica.
• Diseño de redes geodésicas (Problemas de diseño).
• Calibración y detección de daños en estructuras civiles. Aplicaciones
Full transcript