• Author / Uploaded
• Marlon Pachacama

Citation preview

ESCUELA POLITÉCNICA NACIONAL FACULTAD DE INGENIERÍA DE SISTEMAS INGENIERÍA EN SISTEMAS INFORMÁTICOS Y DE COMPUTACIÓN

PERÍODO ACADÉMICO: 2020-B ASIGNATURA: Inteligencia Artificial. PROFESOR: Ing. Myriam Hernández. TIPO DE INSTRUMENTO: Algoritmos Genéticos. NOMBRE: Marlon Pachacama FECHA DE ENTREGA: 04/01/2021 1.

Calcular la función idoneidad de los hijos resultantes del cruce y mutación en el problema de 8 reinas, diapositiva 30 (parte e del gráfico). Comentar si la aplicación del algoritmo mejoró esta función.

2.

Sea la representación de un grupo de ciudades que se quieren visitar en el problema del viajero: 1) 2) 3) 4) 5) 6) 7) 8)

Londres Venecia Dunedin (en Nueva Zelanda) Singapur, Beijing Phoenix Tokio Victoria (Canadá).

Poner las ciudades en un mapa para calcular aproximadamente las distancias. Generar 4 listas de ciudades con el orden de visitas, por ejemplo: Lista1: (3 5 7 2 1 6 4 8) Lista2: (2 5 7 6 8 1 3 4) La función idoneidad es la distancia total recorrida en cada lista de ciudades, se puede calcular en función de sus coordenadas con el programa adjunto. Aplicar los pasos del algoritmo genético. Calcular la función idoneidad en los hijos y comentar los resultados. Pasos:

Padres: Lista1: (6 3 4 8 5 7 1 2) 292 + 81 + 230 + 239 + 23 + 139 + 13 = 1017 Lista2: (8 4 2 3 7 5 1 6) 230 + 101 + 181 + 85 + 23 + 116 + 113 = 849 Lista3: (2 4 6 5 3 7 8 1) 101 + 217 + 228 + 99 + 85 + 262 + 123 = 1115 Lista4: (6 5 7 1 3 4 8 2) 228 + 23 + 139 + 195 + 81 + 230 + 135 = 824 Hijos: Lista1: (4 2 3 8 5 7 1 6) 101 + 181 + 307 + 239 + 23 + 139 + 113 = 833 Lista2: (6 4 8 3 7 5 1 2) 217 + 230 + 307 + 85 + 23 + 116 + 13 = 991 Lista3: (6 1 4 5 3 7 8 2) 113 + 114 + 40 + 99 + 85 + 262 + 135 = 848 Lista4: (2 6 5 1 3 4 8 1) 124 + 228 + 116 + 195 + 81 + 230 + 123 = 1097

Como se puede observar en la tabla, el algoritmo genético resulta de forma favorable, dando como resultado la mínima distancia total al momento de recorrer las 4 listas, por lo tanto, los porcentajes disminuyen.