Academico

Universidad de San Carlos de Guatemala Facultad de Ingeniera Escuela de Ingeniería en Ciencias y Sistemas

ALGORITMOS GENÉTICOS

Samuel Orozco

Guatemala, Febrero de 2007

PRESENTACIÓN

Este documento contiene un extracto del trabajo de graduación titulado “Elaboración de pronósticos con algoritmos genéticos” realizado por Samuel David Orozco Orozco, estudiante de la carrera deIngeniería en Ciencias y Sistemas de la Universidad de San Carlos de Guatemala.

Se ha creado este documento con el propósito de servir de apoyo a los estudiantes del curso de Inteligencia Artificial 1 en el estudio de los algoritmos genéticos. Este documento incluye teoría general sobre algoritmos genéticos y un ejemplo sencillo de su aplicación.

Al final del documento se incluye una lista de lasfuentes de información que fueron consultadas para su elaboración, que pueden revisarse si se desea profundizar más en el tema.

Algoritmos genéticos

1. ALGORITMOS GENÉTICOS

1.1. Introducción a los algoritmos genéticos

Un algoritmo genético (AG) es una técnica de programación que imita a la evolución biológica como estrategia para resolver problemas. Dado un problema específico aresolver, la entrada del AG es un conjunto de soluciones potenciales a ese problema, codificadas de alguna manera, y una métrica llamada función de aptitud que permite evaluar cuantitativamente a cada candidata. Estas candidatas pueden ser soluciones que ya se sabe que funcionan, con el objetivo de que el AG las mejore, pero se suelen generar aleatoriamente [1]. Los algoritmos genéticos son algoritmosde búsqueda basados en los mecanismos de la selección natural que combinan la supervivencia de las secuencias mejores adaptadas con cambios aleatorios de información [2]. Los algoritmos genéticos pueden verse como una familia de procedimientos de búsqueda adaptativos. Su nombre se deriva de que están basados en modelos de cambio genético en una población de individuos. Esto es [3]: • • • NociónDarwiniana de aptitud (fitness) que influye en generaciones futuras. Apareamiento que produce descendientes en generaciones futuras. Operadores genéticos que determinan la configuración genética de los descendientes.

1

Algoritmos genéticos

Un punto clave de estos modelos, es que el proceso de adaptación no se hace cambiando incrementalmente una sola estructura, sino manteniendo unapoblación de estructuras a partir de las cuales se generan nuevas estructuras usando los operadores genéticos. Cada estructura en la población está asociada con una aptitud y los valores se usan en competencia para determinar qué estructuras serán usadas para formar nuevas estructuras. Una de sus características es su habilidad de explotar información acumulada acerca de un espacio de búsqueda inicialmentedesconocido para guiar la búsqueda subsecuente a subespacios útiles. Su aplicación está enfocada sobre todo a espacios de búsqueda grandes, complejos y poco entendidos. El precio es que se pueden necesitar un número grande de muestras para que se tenga suficiente información para guiar muestras subsecuentes a subespacios útiles. En su forma más simple, un algoritmo genéticos está orientado adesempeño (por ejemplo, hacer cambios estructurales para mejorar el desempeño). Una de las ideas más importantes es definir estructuras admisibles en el sentido que estén bien definidas y puedan ser evaluadas. Los algoritmos genéticos difieren con los métodos tradicionales de búsqueda y optimización en los siguientes aspectos [3]: • Trabajan con un conjunto de parámetros codificados y no con losparámetros mismos.

2

Algoritmos genéticos

• • •

Inician la búsqueda desde un conjunto de puntos, no de uno solo. Usan una función a optimizar en lugar de la derivada u otro conocimiento adicional. Usan reglas de transición probabilísticas no determinísticas.

1.2. Anatomía de un algoritmo genético

Un algoritmo genético esta compuesto por [3]: • Módulo evolutivo: mecanismo de...