Algoritmos geneticos

Distribución Óptima de Horarios de Clases utilizando la técnica de Algoritmos Genéticos

Tesis Profesional Que para obtener el Título de

Ingeniero en Computación

Presenta

CARLA LENINCA PACHECO AGÜERO

Acatlima, Huajuapan de León, Oaxaca

Agosto, 2000

Tesis Profesional presentada el 11 de Agosto del 2000 ante los sinodales: Dr. Juan Carlos Mendoza Dra. Virginia Berrón Lara Ing.Francisco Espinoza Maceda Asesores: Dr. Carlos A. Coello Coello Laboratorio Nacional de Inteligencia Artificial Xalapa, Veracruz Dr. Manrique Mata Montero University Memorial of Newfoundland St. John’s, NF,Canadá M.C. Agustín Santiago Alvarado Universidad Tecnológica de la Mixteca

A mis queridos padres, Julio y Antonia, por su apoyo constante, su confianza y su inmenso cariño.

A Iván, porsu amor incondicional y por darme ánimos durante la realización de este trabajo.

A mis hermanos: César, Julio y Mayra, para que este trabajo les sirva como estímulo para que alcancen su meta. A mis sobrinas Tani y Pame por ser los seres mas puros y maravillosos sobre la tierra.

Agradecimientos A mis padres y a Iván por ser parte fundamental de mi vida y porque gracias a su apoyoincondicional he logrado mis metas. Al Dr. Carlos Coello Coello, por su amistad, por compartir su conocimiento conmigo y brindarme su ayuda durante el desarrollo de este trabajo. Al Dr. Manrique Mata Montero, por tener la fortuna de contar con su amistad y apoyo durante el desarrollo de este trabajo.

ÍNDICE
ABSTRACT................................................................................................... INTRODUCCIÓN ........................................................................................... CAPÍTULO 1
MÉTODOS DE OPTIMIZACIÓN

1 2

1.1 Introducción .................................................................................... 1.2 Método del Gradiente ....................................................................... 1.3 Método del hill climbing.................................................................... 1.4 Búsqueda Iterativa ........................................................................... 1.5 Algoritmo Metrópolis ........................................................................ 1.6 Recocido Simulado ........................................................................... 1.7 Búsqueda Tabú............................................................................... 1.8 Búsqueda ciega o sin información ..................................................... 1.8.1 Búsqueda primero en anchura ....................................................... 1.8.2 Búsqueda primero en profundidad .................................................. 1.9 Búsqueda Aleatoria.......................................................................... 1.10 Algoritmos Genéticos y los Métodos de Optimización ........................ CAPÍTULO 2

5 5 6 6 7 8 9 11 11 11 12 13

ALGORITMOS GENÉTICOS

2.1 Introducción ................................................................................... 2.2 Bases Biológicas .............................................................................. 2.2.1 Reproducción Sexual.................................................................... 2.2.2 Operador de Cruza ...................................................................... 2.2.3 Operador de Mutación .................................................................. 2.3 Representación ............................................................................... 2.4 Componentes Básicos...................................................................... 2.4.1 Elementos Fundamentales ............................................................ 2.5 Generación .....................................................................................

14 16 17 20 20 21 22 24 26

2.6 Cuándo aplicar un Algoritmo Genético ............................................... CAPÍTULO 3
DISEÑO DEL ALGORITMO...