Algoritmos genéticos

Description

ALGORITMOS GENÉTICOS......Page 1 PAGINA LEGAL......Page 7 ÍNDICE GENERAL......Page 200 PREFACIO......Page 10 1.1 LA NATURALEZA COMO OPTTMIZADORA......Page 14 1.2 UN POCO DE BIOLOGÍA......Page 16 FIGURA F.I.2.A:......Page 17 FIGURA F.I.2.B:......Page 18 1.3.1 Codificación del dominio......Page 19 1.3.2 Evaluación de la población......Page 20 1.3.3 Selección......Page 21 1.3.4 Cruzamiento......Page 22 1.3.6 El algoritmo genético simple (AGS)......Page 23 En éste se considera que los códigos genéticos están en binario. Explicado con detalle, el proceso de un AGS es:......Page 24 FIGURA F.I.3.A: Selección proporcional o por ruleta.......Page 25 1.3.7 Un ejemplo......Page 26 FIGURA F.I.3.C:......Page 27 TABLA T.I.3.A: Codificación y evaluación de los elementos del dominio de la función f(x) del ejemplo.......Page 28 Para efectuar la selección se hace lo siguiente:......Page 29 TABLA T.I.3.C:......Page 31 1.4.1.1 Método de Newton......Page 32 1.4.1.2 Búsqueda de Fibonacci......Page 34 FIGURAF.IAB: Ilustración del método de búsqueda de Fibonacci.......Page 35 1.4.1.3 Ascenso de máxima pendiente (steepest ascent)......Page 36 1.4.1.4 Simplex......Page 38 Antes de continuar se establecerán algunas definiciones.......Page 39 1.4.2.1 Búsqueda tabú......Page 42 FIGURA F.I.4.E:......Page 43 1.4.2.2 Recocido simulado......Page 44 1.4.3 Comparaciones......Page 46 3.......Page 48 6.......Page 49 1.......Page 50 1.7 REFERENCIAS......Page 51 II. 1.2 Esquemas......Page 54 II.2.1 Selección......Page 55 II.2.2 Cruzamiento......Page 57 II.2.3 Mutación......Page 58 b)......Page 59 II.2.4.1 Cruzamiento de un punto......Page 60 II.2.4.3 Cruzamiento uniforme......Page 61 d)......Page 62 II. 4 PARALELISMO IMPLÍCITO Y LA HBC......Page 63 II. 5 EXPLORACIÓN Y EXPLOTACIÓN......Page 64 2.......Page 65 II. 6.1.1 Los tipos de problemas engañosos mínimos......Page 68 FIGURA F.II.6.A: Cuatro esquemas de orden 2 y su adaptación promedio,......Page 69 FIGURA F.II.6.B.2: Problema engañoso mínimo de Tipo II.......Page 71 FIGURAF.II.6.B.2: Problema engañoso mínimo de Tipo II.......Page 0 II.6.1.2 Análisis de los problemas engañosos......Page 72 TABLA T.II.6.A: Análisis de cruces de los esquemas.......Page 73 De manera análoga, para los demás esquemas:......Page 74 FIGURA F.II.6.C:......Page 75 FIGURA F.II.6.E:......Page 76 II.6.2.1 Definición del problema......Page 77 FIGURA F.II.6.G: Fragmento del código en C que implanta las ecuaciones I1.6.K-II.6.N.......Page 78 FIGURA F.II.6.H: Los bloques constructivos de una cadena que maximiza la función camino regio utilizada como ejemplo.......Page 80 ESCALADA DE ASCENSO DE MÁXIMA PENDIENTE (SAHC):......Page 81 ESCALADA LLEGANDO AL APOYO MÁS PRÓXIMO (NAHC)......Page 82 II.6.2.2 Resultados......Page 83 1. Considere los siguientes esquemas:......Page 84 5. Supóngase que se utiliza un alfabeto de cardinalidad.........Page 85 2.......Page 86 II. 9 REFERENCIAS......Page 87 1.1.1 Codificación binaria......Page 88 FIGURA F.III. 1 .A: Una posible codificación para el problema del agente viajero.......Page 89 III. 1.1.2 Codificación no binaria......Page 90 III. 1.2 Operadores......Page 91 III. 1.2.2 Cruzamiento uniforme ordenado......Page 92 III. 1.2.3 Mutación......Page 93 III. 1.3 La función de adaptación......Page 94 III. 1.4 Síntesis......Page 95 III.2.1.1 Codificación en punto fijo......Page 96 III.2.1.2 Codificación binaria pesada......Page 97 III.2.1.4 Codificación en punto flotante......Page 98 TABLA T.III.2.A:......Page 99 III.2.1.5 ¿Cuál es la mejor opción?......Page 100 FIGURA F.III.2.E: Individuos después de la cruza.......Page 101 III. 2.2 Tres algoritmos......Page 102 III. 2.3 Experimentos......Page 104 TABLA T.III.2.B: Rango de parámetros para AGE.......Page 105 III. 2.4 Resultados......Page 106 FIGURA F.III.2.B: Promedios para representación con punto flotante en AGS/AGT.......Page 107 FIGURA F.III.2.D: Adaptación promedio para AGS con punto fijo.......Page 108 FIGURA F.III.2.F: Adaptación promedio del AGT.......Page 109 FIGURA F.III.2 .H: Adaptación promedio para AGT con punto flotante.......Page 110 FIGURA F.III.2.J: Evolución de la probabilidad de mutación promedio en el AGE.......Page 111 III. 3 EJERCICIOS......Page 112 III. 5 REFERENCIAS......Page 113 IV. 2 UN ALGORITMO GENÉTICO IDEALIZADO......Page 114 ALGORITMO A.rv.2.1......Page 115 IV. 3 MODELOS DE CADENAS DE MARKOV......Page 116 IV.3.1 Conclusiones......Page 118 IV.4.1 Elitismo......Page 119 IV.4.2 Selección determinística......Page 120 IV.4.4 Modelo de Vasconcelos......Page 121 IV 4.5 Autoadaptación......Page 122 FV.4.5.1 Algoritmo genético autoadaptable individual......Page 123 IV.4.6 Un algoritmo genético ecléctico......Page 126 IV 4.6.1 Selección, elitismo y autoadaptación......Page 127 IV.4.6.2 Escalador adaptivo......Page 129 FIGURA F.IV.4.E:......Page 130 3.......Page 132 IV. 6 PROGRAMACIÓN......Page 133 IV. 6.1 Representación de números en un genoma......Page 134 IV. 7 REFERENCIAS......Page 135 V.2 ALGORITMOS GENÉTICOS COEVOLUTTVOS......Page 136 V.2.1 Algoritmo de coevolución......Page 137 TABLA T.V.2 A: Matriz de pago para el dilema del prisionero.......Page 138 V.2.3 Algoritmo DPI......Page 140 V.3 AUTÓMATAS GENÉTICOS......Page 141 V.3.1 Máquinas de Turing......Page 142 FIGURA F.V.3.B: La Unidad de control de una máquina de Turing.......Page 143 TABLA T.V.3.A: Una tabla de transición.......Page 144 TABLA T.V.3.C: Codificación hexadecimal de una MT.......Page 145 T.V.3.D: Codificación binaria de una MT.......Page 146 FIGURA F.V.3.C: Cruzamiento anular.......Page 147 V.3.3.1 Determinación de la validez del modelo......Page 148 FIGURA F.V.3.E: Memoria de los procesos genéticos.......Page 149 V.3.3.2 Generalidad del modelo......Page 150 V.3.3.4 Coeficiente de correlación predictiva......Page 151 FIGURA F.V.3.G:......Page 152 V.4 SISTEMAS CLASIFICADORES EVOLUTIVOS......Page 153 V.4.1 Sistema de reglas de producción......Page 154 FIGURA F.V.4.B: Operador de unión.......Page 155 FIGURA F.V.4.C: Ejemplo de clasificadores.......Page 157 V 4.2 Asignación de crédito......Page 158 FIGURA F.V .4.E-. Algoritmo de cascada.......Page 159 V 4.3 Algoritmo de descubrimiento de clasificadores......Page 161 V.4.4 Jerarquías por omisión......Page 162 V 4.4.1 Ejemplo de jerarquías por omisión......Page 163 TABLA T.V.5.A: Tabla de valores característicos.......Page 166 V.5.1.1 Solución al conjunto VI......Page 167 V.5.1.2 Un ejemplo numérico......Page 171 FIGURA F.V.5 A: Puntos del vector original.......Page 172 V.5.1.4 Algoritmo de ascenso......Page 173 TEOREMA DEL INTERCAMBIO......Page 174 V. 5.2 Solución de sistemas singulares......Page 175 FIGURA F.V.5.D: Desplazamiento aleatorio.......Page 177 ALGORITMO DE CONDICIONAMIENTO......Page 178 FIGURA F.E. 1 .E: Arreglo de neuronas en 3D.......Page 190 FIGURA F.E. 1.F: Patrones de entrada/salida.......Page 191 V. 5.3 Solución de sistemas completos......Page 181 V. 5.4 Algoritmo genético de orden......Page 182 ANTECEDENTES......Page 186 FIGURA F.E. LA: Modelo de una neurona (perceptrón).......Page 187 ALGORITMO DE RETROPROPAGACIÓN......Page 188 FIGURA F.E.1.D: Distintos tipos de fuentes.......Page 189 SISTEMAS CLASIFICADORES EVOLUTIVOS......Page 192 V.7 PROGRAMACIÓN......Page 193 V.8 REFERENCIAS......Page 194 ÍNDICE ANALÍTICO......Page 196