Algoritmos Geneticos

FACULTAD DE INGENIERÍA INGENIERÍA DE SISTEMAS Inteligencia Artificial Algoritmos Genéticos

Ing. Carlos A. Ríos López
Carlos_rios1@hotmail.com

Índice
• Introducción a los Algoritmos Evolutivos

• El Algoritmo Genético Simple: fundamentos
• Otros Algoritmos Evolutivos • Aplicaciones a problemas de Optimización y Aprendizaje

Inspiración
• En la naturaleza los individuos compiten porlos recursos del medio ambiente. Algunos son mejores que otros, esos son los que tienen mas posibilidades de sobrevivir y propagar su material genético. • En un AG los genes son evaluados según una función llamada Fitness function y los mejores son los que pasarán a la próxima iteración.

¿Qué son los Algoritmos Evolutivos?
• Algoritmos de búsqueda (de la solución que optimiza una funciónobjetivo dentro de un espacio de soluciones potenciales) basados en la mecánica de la evolución, en particular – La selección natural – La herencia genética
• Combinan la “supervivencia del más fuerte” con “intercambio de información” entre individuos para generar descendientes • Así se consigue crear sistemas de cómputo artificiales con características propias de los sistemas naturales, tales como– Robustez, Flexibilidad, Auto-organización, Reproducción, ...

Un poco de historia de los AEs
• Fueron introducidos por John Holland y algunos colegas en la Universidad de Michigan en los años 70. Sus objetivos fueron
– Abstraer y explicar el proceso adaptativo de los sistemas naturales – Diseñar sistemas artificiales que emulasen los mecanismos esenciales de los sistemas naturales

•Primera monografía [Holland 1975]: “Adaptation in Natural and Artificial Systems” • Otras referencias relevantes más recientes
– [Goldberg 1989] : “Genetic Algoritms in Search Optimization and Machine Learning” – [Michalewick 1992, 1994, 1996] : “Genetic Algoritms = Data Structures + Evolution Programs”

¿A qué se debe el éxito de los AEs?
• Han demostrado ser útiles en problemas de búsqueda enmuchos campos
– Ingenierías, Ciencias, Administración, Industria, ...

• Son simples, fáciles de entender y de diseñar • No tienen limitaciones sobre la función objetivo
– Continuidad, derivabilidad y unimodalidad

• Son robustos y razonablemente eficientes, y además ...
• Son divertidos

Características de los AEs
• Utilizan codificaciones de las soluciones (normalmente cadenas desímbolos) • Buscan a partir de un conjunto de puntos del espacio de búsqueda

• Solamente utilizan el valor de la función objetivo (en lugar de derivadas u otras propiedades): NO REQUIEREN MÁS INFORMACIÓN DEL DOMINIO DEL PROBLEMA
• Usan reglas de transición probabilistas en lugar de deterministas

La metáfora
Lo Natural
Entorno o Ecosistema Individuo o Fenotipo Problema Solución potencial delProblema

Lo Artificial

Cromosoma o Genotipo
Grado de Adaptación al Entorno Superviviencia, Reproducción, Mutación

Cadena de Símbolos
Fitness o Calidad de la Solución Operadores de Selección/Aceptación, Cruce, Mutación

Componentes esenciales de un AE
• Un método de codificación de los individuos o soluciones potenciales del problema, por ejemplo una cadena de bits (codificación binaria)• Una función de evaluación (fitness) • Una forma de generar la población inicial • Operadores genéticos: Selección, Cruce, Mutación, ... • Un montón de parámetros: Pc, Pm, Tamaño de la Población, Número de Generaciones, ...

Pasos de un algoritmo genético
1. 2. 3. 4. Generar una población de n genes aleatoreos. Evaluar a todos los individuos según la función de aptitud (fitness function).Generar nuevos individuos utilizando funciones como Mutar, Cruzar (crossover), Variar, etc. Seleccionar a los individuos que formarán la próxima generación. (Seleccionar a los hijos (offsprings) o seleccionar a los n mejores) Volver a 2 hasta que se encuentre un valor predefinido o se hallan cumplido una cantidad predeterminada de iteraciones.

5.

Estructura de un AE
Algoritmo Evolutivo...