Optimizacion

Tesis Doctoral

B ÚSQUEDAS GENÉTICAS :
MÉTODOS DE OPTIMIZACIÓN GLOBAL Y OPTIMIZACIÓN COMBINATORIA

Doctorando: Juan José Domínguez Jiménez Directora de la tesis: Dra. Inmaculada Medina Bulo

Depto. Lenguajes y Sistemas Informáticos Universidad de Cádiz Diciembre, 2008

A Belén por su cariño y que sin duda no hubiese hecho realidad esta tesis sin su apoyo, a nuestra hija Sandra y a mispadres.

CONFORMIDAD DEL DIRECTOR DE TESIS PARA LA TRAMITACIÓN DE LA TESIS DOCTORAL

Dª Inmaculada Medina Bulo, profesora del Departamento de Lenguajes y Sistemas Informáticos de la Universidad de Cádiz, siendo Directora de la Tesis titulada

“Búsquedas Genéticas: Métodos de optimización global y optimización combinatoria”, realizada por el doctorando D. Juan José Domínguez Jiménez dentrodel programa de doctorado Ingeniería en Automática y Electrónica Industrial, Ingeniería Informática y Sistemas Eléctricos perteneciente al bienio 2003/05, para proceder a los trámites

conducentes a la presentación y defensa de la tesis doctoral arriba indicada, en aplicación del art. 30 de la Normativa Reguladora de Estudios de Tercer Ciclo de la Universidad de Cádiz, informa que se autoriza latramitación de la tesis.

En Cádiz, a quince de diciembre de 2008

Fdo.: _________________________

Índice general
Índice de figuras Índice de tablas Índice de algoritmos 1. Introducción 1.1. Antecedentes y motivación . . . . 1.2. Objetivos . . . . . . . . . . . . . . . 1.3. Estructura de la tesis . . . . . . . . 1.3.1. Fundamentos teóricos . . . 1.3.2. Optimización global . . . . 1.3.3.Optimización combinatoria 1.3.4. Conclusiones . . . . . . . . 1.3.5. Anexos . . . . . . . . . . . . 1.4. Publicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . .
IX XIII XV

1 1 4 5 5 6 8 10 11 11

I Fundamentos Teóricos
2. Optimización de funciones 2.1. Introducción . . . . . . . . . . . . . . . . . . 2.2. Condiciones de optimalidad . . . . . . . . . 2.3. Optimización unidimensional . . . . . . . . 2.3.1. Búsqueda dicotómica . . . . . . . . 2.3.2. Búsqueda de Fibonacci . . . . . . . . 2.3.3. Búsqueda mediante la sección áurea 2.4.Optimización multidimensional . . . . . . . 2.4.1. Métodos de descenso . . . . . . . . . 2.4.2. Métodos de descenso coordenado . 2.4.3. Métodos de resolución global . . . . 2.5. Optimización combinatoria . . . . . . . . . 2.5.1. Métodos de búsqueda local . . . . .
III

15
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 17 18 19 20 21 23 24 25 33 35 36 37

IV

´NDICE GENERAL I

3. Algoritmos genéticos 3.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . 3.2. AG básico . . . . . . . . . . . . . . . . . . . . . . . . 3.3. Elementos del AG . . . . . . . . . . . . . . . . . . . . 3.3.1.Codificación . . . . . . . . . . . . . . . . . . . 3.3.2. Función de aptitud . . . . . . . . . . . . . . . 3.3.3. Población inicial . . . . . . . . . . . . . . . . 3.3.4. Selección de individuos . . . . . . . . . . . . 3.3.5. Operadores genéticos . . . . . . . . . . . . . 3.3.6. Criterios de parada . . . . . . . . . . . . . . . 3.3.7. Sustitución de individuos . . . . . . . . . . . 3.3.8.Renovación de la población . . . . . . . . . . 3.4. Clasificación de AGs . . . . . . . . . . . . . . . . . . 3.5. Nichos . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6. Teorema de esquemas . . . . . . . . . . . . . . . . . 3.6.1. Definiciones . . . . . . . . . . . . . . . . . . . 3.6.2. La ecuación de crecimiento de los esquemas 3.6.3. El teorema fundamental de los AGs . . . . .

. . . . . . ....