Evaluación e implementación de algoritmos genéticos para aplicaciones en robótica y otras áreas de Ingeniería Mecatrónica José Pablo Petion Rivas UNIVERSIDAD DEL VALLE DE GUATEMALA Facultad de Ingeniería Evaluación e implementación de algoritmos genéticos para aplicaciones en robótica y otras áreas de Ingeniería Mecatrónica Trabajo de graduación presentado por José Pablo Petion Rivas para optar al grado académico de Licenciado en Ingeniería Mecatrónica Guatemala, 2025 UNIVERSIDAD DEL VALLE DE GUATEMALA Facultad de Ingeniería Evaluación e implementación de algoritmos genéticos para aplicaciones en robótica y otras áreas de Ingeniería Mecatrónica Trabajo de graduación presentado por José Pablo Petion Rivas para optar al grado académico de Licenciado en Ingeniería Mecatrónica Guatemala, 2025 Vo.Bo.: (f) M. Sc. Carlos Esquit Tribunal Examinador: (f) M.Sc. Carlos Esquit (f) (f) Fecha de aprobación: Guatemala, 13 de febrero de 2025. M. Sc. Miguel Enrique Zea Arenales Prefacio Es de mi orgullo y satisfacción presentar este trabajo como re�ejo del esfuerzo y aprendi- zaje durante los 5 años de mi trayectoria universitaria. La elaboración de este trabajo surgió de mi interés por las herramientas de inteligencia computacional. Siempre creí que estas herramientas tendrían un potencial alto en un futuro y harían grandes aportes a la ciencia. Hoy en día me siento orgulloso de haber sido participe del desarrollo de estas herramientas a�nes a mi vocación, contribuyendo de cierta manera a la comunidad ingenieril. De este modo presento esta investigación estando satisfecho con cumplir mi sueño de estudiar una carrera orientada a la robótica. Quiero expresar mi más profundo agradecimiento a todas las personas que me acompa- ñaron durante esta etapa de mi vida. Agradezco en primer lugar a mi familia, en especial a mi papá y a mi mamá, por haber hecho esto posible y por su apoyo incondicional. De igual forma agradezco a la Fundación Amivalle, en especial al Ing. Hugo Elvira Ramos y el Ing. Edgar Ramírez, quienes me otorgaron la beca que me permitió llevar a cabo mis estudios universitarios. También quiero expresarlo al Dr. Luis Alberto Rivera, por compartir con mi persona su conocimiento y seguimiento durante el desarrollo de esta investigación. Adicio- nalmente, quiero agradecerle a mis compañeros quienes estuvieron en cada momento a mi lado durante la carrera, en especial a Sergio Alejandro Boch, quien me acompañó todo el tiempo, gracias a todos por las memorias que creamos juntos. Quiero dedicar este trabajo de graduación a mi familia, como representación del logro académico. Al igual que se lo dedico a la comunidad cientí�ca, esperando que este trabajo sirva de base para futuras investigaciones y contribuya al desarrollo en diferentes áreas. iii Índice Prefacio iii Lista de �guras ix Lista de cuadros x Resumen xi Abstract xii 1. Introducción 1 2. Antecedentes 3 2.1. Inteligencia de enjambre para aplicaciones robóticas y primer avance de algo- ritmos genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2. Algoritmo Ant Colony Optimization (ACO) para aplicaciones de robótica y biomédica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3. Algoritmos genéticos (AG) para plani�cación de rutas aplicados en robots móviles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.4. Algoritmos genéticos para optimización multiobjetivo . . . . . . . . . . . . . . 6 2.5. Aplicación de algoritmos genéticos para evasión de obstáculos . . . . . . . . . 6 3. Justi�cación 7 4. Objetivos 8 4.1. Objetivo general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.2. Objetivos especí�cos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 5. Alcance 9 6. Marco teórico 11 6.1. Inteligencia computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 6.1.1. Computación evolutiva . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 6.2. Algoritmo evolutivo genérico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 iv 6.3. Representación del cromosoma . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.4. Población inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 6.5. Función de aptitud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 6.6. Selección . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 6.6.1. Precisión selectiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 6.6.2. Selección aleatoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 6.6.3. Selección proporcional . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 6.6.4. Selección por competencia (torneo) . . . . . . . . . . . . . . . . . . . . 16 6.6.5. Selección basada en Rank . . . . . . . . . . . . . . . . . . . . . . . . . 16 6.7. Operadores de reproducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 6.8. Condición de detención . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 6.9. Decodi�cación de variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 6.10. Algoritmos genéticos (AG) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 6.10.1. Cruce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 6.10.2. Representaciones binarias . . . . . . . . . . . . . . . . . . . . . . . . . 19 6.11. Plani�cación de movimiento y trayectorias . . . . . . . . . . . . . . . . . . . . 21 6.11.1. Aplicaciones de AG para plani�cación de movimiento . . . . . . . . . . 22 6.11.2. Codi�cación de variables de tipo �otante en path-planning . . . . . . . 23 6.11.3. Función de aptitud para trayectorias . . . . . . . . . . . . . . . . . . . 23 6.11.4. Cruce aritmético . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 6.11.5. Ruleta para cruce y mutación . . . . . . . . . . . . . . . . . . . . . . . 24 6.12. Otras aplicaciones de algoritmos genéticos para problemas de plani�cación de movimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 6.13. Otras aplicaciones exitosas de AG en diferente área . . . . . . . . . . . . . . . 26 6.13.1. Algoritmos genéticos para segmentación de imágenes . . . . . . . . . . 26 6.14. Procesamiento de imágenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 6.14.1. Segmentación de imágenes . . . . . . . . . . . . . . . . . . . . . . . . . 27 6.15. Funciones de costo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 6.16. Funciones de super�cies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 6.17. Controlador no lineal de pose para robots móviles . . . . . . . . . . . . . . . . 30 6.18. Intersección de una recta con un plano limitado en un espacio tridimensional 31 6.18.1. Ecuación para la intersección con el plano y = c . . . . . . . . . . . . . 31 6.18.2. Condición adicional: veri�cación de los límites en x y z . . . . . . . . . 32 6.18.3. Criterio de veri�cación . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 7. Validación general de algoritmo genético 34 7.1. Algoritmos genéticos para optimizar funciones de costo . . . . . . . . . . . . . 34 7.1.1. Resultados de primer escenario para optimización de función de costo 36 7.1.2. Resultados de segundo escenario para optimización de función de costo 37 7.2. Algoritmos genéticos para optimización de máximos y mínimos en funciones algebraicas multivariable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 7.2.1. Primer escenario para optimización de super�cies . . . . . . . . . . . . 40 7.2.2. Segundo escenario para optimización de super�cies . . . . . . . . . . . 42 7.2.3. Tercer escenario para optimización de super�cies . . . . . . . . . . . . 43 v 8. Algoritmo genético para plani�cación de trayectorias 46 8.1. Metodología . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 8.1.1. Selección con base en la aptitud . . . . . . . . . . . . . . . . . . . . . . 49 8.1.2. Función de cruce aritmético . . . . . . . . . . . . . . . . . . . . . . . . 49 8.2. Evaluación de algoritmo genético en mapas 2D . . . . . . . . . . . . . . . . . 49 8.2.1. Implementación de AG para plani�cación de trayectorias, escenario 1 . 49 8.2.2. Implementación de AG para plani�cación de trayectorias, escenario 2 . 51 8.2.3. Validación de AG para plani�cación de trayectorias, escenario 3 . . . . 54 8.2.4. Validación de AG para plani�cación de trayectorias, escenario 4 . . . . 56 8.2.5. Validación de AG para plani�cación de trayectorias, escenario 5 . . . . 58 9. Algoritmos genéticos en aplicaciones dentro de la Ingeniería Mecatrónica 62 9.1. Evaluación de algoritmos genéticos en plani�cación de movimiento para dro- nes en tres dimensiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 9.1.1. Metodología . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 9.1.2. Evaluación de algoritmo genético en mapas 3D . . . . . . . . . . . . . 66 9.2. Evaluación de algoritmos genéticos en procesamiento de imágenes . . . . . . . 91 9.2.1. Metodología . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 9.2.2. Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 9.2.3. Discusión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 10.Algoritmos genéticos aplicados a escenarios prácticos 106 10.1. Implementación de AG para plani�cación de trayectorias en Webots . . . . . 106 10.1.1. Controlador para robot móvil . . . . . . . . . . . . . . . . . . . . . . . 108 10.1.2. Resultados de la implementación AG en simulación de Webots . . . . 108 10.2. Implementación de algoritmo genético en plani�cación de movimiento 3D con cuadricóptero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 10.2.1. Parámetros de simulación . . . . . . . . . . . . . . . . . . . . . . . . . 112 10.2.2. Resultados de la implementación del AG en simulación . . . . . . . . . 112 10.3. Implementación de un algoritmo genético para la segmentación de objetos en un entorno simulado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 10.3.1. Parámetros de simulación . . . . . . . . . . . . . . . . . . . . . . . . . 117 10.3.2. Controlador de pose . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 10.3.3. Resultados de la implementación del AG en simulación . . . . . . . . . 118 11.Conclusiones 121 12.Recomendaciones 123 13.Bibliografía 124 14.Anexos 126 14.1. Evaluaciones adicionales de AG en plani�cación de trayectorias 2D . . . . . . 126 14.2. Códigos adicionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 14.3. Evaluaciones adicionales de AG en segmentación de imágenes . . . . . . . . . 127 14.4. Repositorio en Github . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 vi Lista de �guras 1. Resultados de cuatro funciones de costo aplicando algoritmos genéticos [2] . . 4 2. Resultados de plani�cación de trayectorias con algoritmos genéticos [5] . . . . 6 3. Representación de gen y cromosoma con codi�cación binaria [1] . . . . . . . . 13 4. Representación de gen y cromosoma con codi�cación entera [1] . . . . . . . . 13 5. Representación de gen y cromosoma con codi�cación de punto �otante [1] . . 13 6. Diagrama de funcionamiento general de un AG [1] . . . . . . . . . . . . . . . 19 7. Esquema de cruce por medio de un punto [1] . . . . . . . . . . . . . . . . . . 20 8. Esquema de cruce por medio de dos puntos [1] . . . . . . . . . . . . . . . . . . 20 9. Esquema de cruce uniforme [1] . . . . . . . . . . . . . . . . . . . . . . . . . . 21 10. Entorno de prueba para algoritmo genético [5] . . . . . . . . . . . . . . . . . . 22 11. Codi�cación de solución, representación del cromosoma [5] . . . . . . . . . . . 23 12. Ejemplo de cruce aritmético para cromosomas de 2 dimensiones cartesianas [5] 24 13. Representación del método de ruleta giratoria [5] . . . . . . . . . . . . . . . . 25 14. Solución a la codi�cación de variables de movimiento [11] . . . . . . . . . . . 25 15. Proceso de algoritmo genético para segmentación de imágenes [12] . . . . . . 26 16. Función de aptitud basada en la entropía intra e interregión [13] . . . . . . . . 27 17. Ejemplos de segmentación de imágenes utilizando diferentes técnicas [14] . . . 28 18. Función de Ackley [15] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 19. Función de Booth [15] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 20. Función de Rosenbrock [15] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 21. Función de Rastrigin [15] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 22. Función de paraboloide elíptico [15] . . . . . . . . . . . . . . . . . . . . . . . . 30 23. Función de hiperboloide de 1 hoja [15] . . . . . . . . . . . . . . . . . . . . . . 30 24. Función de campana de Gauss [15] . . . . . . . . . . . . . . . . . . . . . . . . 30 25. Diagrama de �ujo de AG para minimizar costos . . . . . . . . . . . . . . . . . 35 26. Representación y codi�cación del cromosoma para problema de optimización de costo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 27. Funciones de costo vs. generaciones, primer caso . . . . . . . . . . . . . . . . . 37 28. Funciones de costo vs. generaciones, segundo caso . . . . . . . . . . . . . . . . 38 29. Representación y codi�cación del cromosoma para problema de optimización de super�cies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 vii 30. Solución hipérbola f(x, y) vs. generaciones, primer caso . . . . . . . . . . . . 41 31. Solución paraboloide f(x, y) vs. generaciones, primer caso . . . . . . . . . . . 41 32. Solución Gauss f(x, y) vs. generaciones, primer caso . . . . . . . . . . . . . . 41 33. Solución de hipérbola vs. generaciones, segundo caso . . . . . . . . . . . . . . 42 34. Solución de paraboloide vs. generaciones, segundo caso . . . . . . . . . . . . . 43 35. Solución de Gauss vs. generaciones, segundo caso . . . . . . . . . . . . . . . . 43 36. Solución de hipérbola vs. generaciones, tercer caso . . . . . . . . . . . . . . . 44 37. Solución de paraboloide vs. generaciones, tercer caso . . . . . . . . . . . . . . 44 38. Solución de Gauss vs. generaciones, tercer caso . . . . . . . . . . . . . . . . . 45 39. Diagrama de �ujo para AG en plani�cación de trayectorias 2D . . . . . . . . . 48 40. Camino generado con 5 iteraciones por AG, primer caso . . . . . . . . . . . . 50 41. Camino generado con 40 iteraciones por AG, primer caso . . . . . . . . . . . . 50 42. Camino generado con 100 iteraciones por AG, primer caso . . . . . . . . . . . 51 43. Camino generado con 5 iteraciones por AG, segundo caso . . . . . . . . . . . 52 44. Camino generado con 40 iteraciones por AG, segundo caso . . . . . . . . . . . 53 45. Camino generado con 100 iteraciones por AG, segundo caso . . . . . . . . . . 53 46. Camino generado con 30 iteraciones por AG, tercer caso . . . . . . . . . . . . 55 47. Camino generado con 30 iteraciones por AG, tercer caso . . . . . . . . . . . . 55 48. Camino generado con 30 iteraciones por AG, tercer caso . . . . . . . . . . . . 55 49. Camino generado con 30 iteraciones por AG, cuarto caso . . . . . . . . . . . . 57 50. Camino generado con 30 iteraciones por AG, cuarto caso . . . . . . . . . . . . 57 51. Camino generado con 30 iteraciones por AG, cuarto caso . . . . . . . . . . . . 58 52. Mapa con estructura compleja para implementación de AG . . . . . . . . . . 59 53. Camino generado con 10 iteraciones por AG, quinto caso . . . . . . . . . . . . 60 54. Camino generado con 20 iteraciones por AG, quinto caso . . . . . . . . . . . . 60 55. Camino generado con 100 iteraciones por AG, quinto caso . . . . . . . . . . . 60 56. Visualización de mapa genérico 3D desarrollado en MATLAB . . . . . . . . . 63 57. Codi�cación de obstáculos en AG para plani�cación de trayectorias en 3D . . 63 58. Representación y codi�cación del cromosoma en espacio 3D . . . . . . . . . . 64 59. Mapa de exploración en espacio 3D para escenario 1 . . . . . . . . . . . . . . 67 60. Mejores individuos generados con 16 iteraciones por AG en 3D, primer caso . 68 61. Mejores individuos generados con 50 iteraciones por AG en 3D, primer caso . 69 62. Mejores individuos generados con 100 iteraciones por AG en 3D, primer caso 70 63. Representación del cromosoma como mejor solución en escenario 1 . . . . . . 70 64. Mejores individuos generados en la primera corrida por AG en 3D, segundo caso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 65. Mejores individuos generados en la segunda corrida por AG en 3D, segundo caso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 66. Mejores individuos generados en la tercera corrida por AG en 3D, segundo caso 75 67. Mejores individuos generados en la cuarta corrida por AG en 3D, segundo caso 76 68. Mejores individuos generados en la quinta corrida por AG en 3D, segundo caso 77 69. Mejores individuos generados en la primera corrida por AG en 3D, tercer caso 80 70. Mejores individuos generados en la segunda corrida por AG en 3D, tercer caso 81 71. Mejores individuos generados en la tercera corrida por AG en 3D, tercer caso 82 72. Mejores individuos generados en la cuarta corrida por AG en 3D, tercer caso . 83 73. Mejores individuos generados por el AG en 3D, cuarto caso . . . . . . . . . . 86 viii 74. Representación del cromosoma como mejor solución en escenario 4 . . . . . . 87 75. Mejores individuos generados en la primera corrida por AG en 3D, quinto caso 89 76. Mejores individuos generados en la segunda corrida por AG en 3D, quinto caso 90 77. Representación del cromosoma como un vector de umbrales y su codi�cación en regiones homogéneas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 78. Relación entre la entropía intrarregión (Hintra) e interregión (Hinter) en la función de aptitud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 79. Segmentación en imágenes de alto contraste: (a) imagen original, (b) AG, (c) Otsu, (d) K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 80. Segmentación en imágenes de alto contraste con parámetros ajustados: (a) imagen original, (b) AG, (c) Otsu, (d) K-means . . . . . . . . . . . . . . . . . 96 81. Segmentación en imagen con ruido gaussiano (caballo): (a) imagen original, (b) AG, (c) Otsu, (d) K-means . . . . . . . . . . . . . . . . . . . . . . . . . . 98 82. Segmentación en imagen con ruido gaussiano (perro): (a) imagen original, (b) AG, (c) Otsu, (d) K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 83. Segmentación en imagen con ruido gaussiano (gato): (a) imagen original, (b) AG, (c) Otsu, (d) K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 84. Segmentación en imagen industrial (motor): (a) imagen original, (b) AG, (c) Otsu, (d) K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 85. Segmentación en resonancia magnética cerebral con tumor: (a) imagen origi- nal, (b) AG, (c) Otsu, (d) K-means . . . . . . . . . . . . . . . . . . . . . . . . 103 86. Segmentación en radiografía de tórax: (a) imagen original, (b) AG, (c) Otsu, (d) K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 87. Segmentación en radiografía de tórax más de�nida: (a) imagen original, (b) AG, (c) Otsu, (d) K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 88. Mapa para simulación de AG en Webots . . . . . . . . . . . . . . . . . . . . . 107 89. Trayectoria resultante del AG para el mapa en Webots . . . . . . . . . . . . . 109 90. Trayectoria resultante del AG para el mapa en Webots . . . . . . . . . . . . . 110 91. Mapa de simulación de movimiento en 3D con trayectoria generada por AG . 111 92. Robot Crazy�ie utilizado para la simulación . . . . . . . . . . . . . . . . . . . 112 93. Trayectoria en 3D generada por el AG en Webots . . . . . . . . . . . . . . . . 113 94. Trayectoria resultante del AG en 3D recorrida por Crazy�ie . . . . . . . . . . 114 95. Trayectoria resultante del AG en 3D recorrida por Crazy�ie, vista en plano yx115 96. Objeto esférico a segmentar por el AG . . . . . . . . . . . . . . . . . . . . . . 116 97. Conjunto de simulación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 98. Imagen segmentada a una sola región por AG . . . . . . . . . . . . . . . . . . 118 99. Imagen segmentada en la simulación conforma a las poses del robot . . . . . . 119 100. Visualización de las trayectorias generadas por los algoritmos genéticos . . . . 126 101. Visualización de las trayectorias generadas por los algoritmos genéticos . . . . 127 102. Segmentación de imagen usando población de 100 individuos y Pm = 20% . . 128 103. Segmentación de imagen usando población de 80 individuos y Pm = 20% . . . 128 104. Segmentación de imagen usando población de 150 individuos y Pm = 20% . . 129 105. Segmentación de imagen usando población de 70 individuos y Pm = 30% . . . 129 ix Lista de cuadros 1. Parámetros de simulación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2. Resultados optimización costo caso 1 . . . . . . . . . . . . . . . . . . . . . . . 36 3. Resultados optimización costo caso 2 . . . . . . . . . . . . . . . . . . . . . . . 38 4. Parámetros de simulación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5. Resultados de simulación optimización de super�cies . . . . . . . . . . . . . . 40 6. Resultados de optimización de super�cies, segundo caso . . . . . . . . . . . . 42 7. Resultados de optimización de super�cies, tercer caso . . . . . . . . . . . . . . 44 8. Resultados de implementación de AG en mapa 2D primer caso . . . . . . . . 50 9. Resultados de implementación de AG en mapa 2D segundo caso . . . . . . . . 52 10. Resultados de implementación de AG en mapa 2D tercer caso . . . . . . . . . 54 11. Resultados de implementación de AG en mapa 2D cuarto caso . . . . . . . . . 57 12. Parámetros de rendimiento de AG en plani�cación de trayectorias, quinto caso 59 13. Resultados obtenidos para el escenario 1 en las tres corridas del AG en 3D . . 67 14. Resultados obtenidos para el escenario 2 en las tres corridas del AG en 3D . . 72 15. Resultados obtenidos para el escenario 3 en las tres corridas del AG en 3D . . 79 16. Resultados obtenidos para el escenario 4 en las tres corridas del AG en 3D . . 85 17. Resultados obtenidos para el escenario 5 en las tres corridas del AG en 3D . . 89 18. Métricas obtenidas para la segmentación en imágenes de alto contraste . . . . 95 19. Métricas obtenidas para la segmentación con parámetros ajustados . . . . . . 97 20. Métricas obtenidas en imágenes con ruido gaussiano . . . . . . . . . . . . . . 101 21. Métricas obtenidas para imágenes complejas . . . . . . . . . . . . . . . . . . . 105 22. Parámetros de simulación de AG en escenario realista . . . . . . . . . . . . . 107 23. Valores de las constantes del controlador de pose lineal . . . . . . . . . . . . . 108 24. Parámetros de rendimiento del AG en simulación realista . . . . . . . . . . . . 108 25. Parámetros de simulación de AG para búsqueda de trayectorias 3D . . . . . . 112 26. Parámetros de rendimiento del AG en 3D . . . . . . . . . . . . . . . . . . . . 113 27. Parámetros de simulación de AG en escenario para segmentación de imágenes 117 28. Valores de las constantes del controlador de pose lineal en segmentación de imágenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 x Resumen Este trabajo aborda la evaluación e implementación de algoritmos genéticos (AG) pa- ra aplicaciones especí�cas en robótica y la Ingeniería Mecatrónica. Se plantearon objetivos enfocados en la plani�cación de trayectorias, evasión de obstáculos y segmentación de imáge- nes, desarrollando escenarios prácticos para validar la e�cacia de estos algoritmos. Mediante una revisión exhaustiva del marco teórico de la computación evolutiva, se diseñaron AG adaptados que fueron implementados en simulaciones realistas utilizando plataformas como MATLAB y Webots. En el ámbito de la plani�cación de trayectorias, se evaluaron cinco escenarios en mapas 2D y cuatro en entornos 3D. En los mapas 2D, los AG generaron rutas e�cientes tras un número controlado de iteraciones, evitando colisiones con obstáculos estáticos y optimizando las trayectorias en términos de distancia recorrida. En los entornos 3D, los algoritmos demos- traron su capacidad para la navegación de drones, adaptándose a restricciones espaciales y obstáculos complejos, y generando trayectorias precisas. La implementación en simulaciones permitió validar el desempeño de los AG en entornos controlados, asegurando la viabilidad de las soluciones propuestas. En el procesamiento de imágenes, los AG fueron aplicados a la segmentación de imáge- nes complejas, como imágenes médicas y escenarios con ruido. Los algoritmos lograron un desempeño superior en métricas de calidad de segmentación frente a métodos tradiciona- les como Otsu y K-means, destacándose en la agrupación de píxeles y la optimización de regiones homogéneas. Adicionalmente, se desarrolló un escenario especí�co enfocado en la segmentación para la identi�cación de regiones útiles en visión por computadora, mostrando resultados altamente satisfactorios. Con estas implementaciones, el trabajo cumplió con el objetivo general de evaluar e implementar algoritmos genéticos para aplicaciones en robótica y otras áreas de la Ingeniería Mecatrónica, validando su capacidad de optimización en diversos escenarios y consolidando su utilidad como herramienta versátil en la resolución de problemas complejos. xi Abstract This work addresses the evaluation and implementation of genetic algorithms (GA) for speci�c applications in robotics and Mechatronics Engineering. The objectives focused on trajectory planning, obstacle avoidance, and image segmentation, developing practical sce- narios to validate the e�ectiveness of these algorithms. Through an exhaustive review of the theoretical framework of evolutionary computation, adapted GAs were designed and implemented in realistic simulations using platforms such as MATLAB and Webots. In the area of trajectory planning, �ve scenarios were evaluated on 2D maps and four in 3D environments. On 2D maps, the GAs generated e�cient routes after a controlled number of iterations, avoiding collisions with static obstacles and optimizing trajectories in terms of travel distance. In 3D environments, the algorithms demonstrated their ability to navigate drones, adapting to spatial constraints and complex obstacles, and generating precise tra- jectories. The implementation in simulations allowed for validating the performance of GAs in controlled environments, ensuring the feasibility of the proposed solutions. For image processing, GAs were applied to the segmentation of complex images, including medical images and scenarios with noise. The algorithms achieved superior performance in segmentation quality metrics compared to traditional methods such as Otsu and K-means, excelling in pixel grouping and the optimization of homogeneous regions. Additionally, a spe- ci�c scenario was developed for segmentation aimed at identifying regions useful in computer vision, yielding highly satisfactory results. Through these implementations, the work ful�lled the general objective of evaluating and implementing genetic algorithms for applications in robotics and other areas of Mechatronics Engineering, validating their optimization capabilities in diverse scenarios and consolidating their utility as a versatile tool for solving complex problems. xii CAPÍTULO 1 Introducción La creciente demanda de soluciones e�cientes en el campo de la robótica y la Ingenie- ría Mecatrónica ha impulsado el desarrollo de algoritmos inteligentes que permiten abordar problemas complejos, como la plani�cación de trayectorias y la optimización de rutas. Entre las metodologías más destacadas se encuentran los algoritmos genéticos (AG), un tipo de al- goritmo evolutivo basado en los principios de la selección natural, los cuales han demostrado ser altamente efectivos para la resolución de problemas de optimización en entornos diversos. Este trabajo de graduación se enfoca en la evaluación e implementación de algoritmos gené- ticos para aplicaciones en robótica, un área en constante evolución que plantea retos como la evasión de obstáculos, plani�cación de trayectorias y la optimización de movimiento. El estudio no solo aborda las aplicaciones de los AG en la plani�cación de trayectorias para robots móviles, sino que también explora su potencial en otras áreas de la Ingeniería Mecatrónica, como el procesamiento de imágenes y plani�cación de movimiento para drones en el espacio 3D. Esto responde a la necesidad de contar con herramientas computacio- nales que optimicen el comportamiento de sistemas autónomos en entornos simulados y, potencialmente, en escenarios reales. En la literatura revisada, los algoritmos genéticos han mostrado un comportamiento favorable para la plani�cación de rutas libres de colisiones, especialmente cuando se integran en sistemas de navegación para robots con movimiento diferencial. El objetivo principal de este trabajo es evaluar e implementar algoritmos genéticos para optimización en aplicaciones robóticas y otras áreas de la Ingeniería Mecatrónica. Se desa- rrollaron diferentes escenarios prácticos, que incluyen simulaciones realistas, donde se validó la e�cacia de los algoritmos propuestos. Entre los objetivos especí�cos, se destaca la inves- tigación y evaluación de los AG dentro del área de inteligencia computacional, así como su implementación en plani�cación de trayectorias y segmentación de imágenes. Este estudio busca sentar un precedente en la Universidad del Valle de Guatemala, expan- diendo el campo de investigación sobre algoritmos genéticos y su aplicación en ingeniería. A través de simulaciones y pruebas en entornos controlados, se validaron los resultados obteni- dos para ofrecer una referencia sólida a futuras investigaciones en este campo. Los resultados 1 obtenidos podrían ser el punto de partida para futuras implementaciones en escenarios más complejos, como entornos dinámicos y aplicaciones en la vida real. 2 CAPÍTULO 2 Antecedentes Según Engelbrecht, la inteligencia computacional se de�ne como el estudio de mecanismos adaptativos para facilitar el comportamiento inteligente. Este es un avance muy importante en el desarrollo algorítmico para resolver problemas complejos. Estos algoritmos inteligen- tes incluyen redes neuronales arti�ciales, computación evolutiva e inteligencia de enjambre, combinado con lógica y razonamiento deductivo. Todo este tipo de algoritmos inteligentes forman parte del campo de la inteligencia arti�cial (IA) [1]. 2.1. Inteligencia de enjambre para aplicaciones robóticas y primer avance de algoritmos genéticos Anteriormente se desarrollaron y validaron los algoritmos de enjambre para adaptarse a aplicaciones de robótica. En los avances de robótica, para la navegación de un robot móvil, se debe contar con un plani�cador de trayectorias. Por lo que esta investigación [2] se basó en implementar y veri�car algoritmos de inteligencia de enjambre, además, computación evolutiva (algoritmos genéticos), como alternativa de los desarrollados con aterioridad. Di- chos algoritmos son el Ant Colony, basado en comportamiento de hormigas, con el objetivo de econtrar sus parámetros de ecuaciones y validarlo en robots simulados. Para lograrlo, se implementó el algoritmo Simple Ant Colony, seguido de Ant System. Estos se validaron por medio de simulaciones para vizualizar el comportamiento en la colonia, para luego adaptarlos a los modelos de movimiento necesarios para comparar su desempeño en el software de We- bots. Adicionalmente, se indagó en los algoritmos genéticos, adhiriendo su implementación en diferentes funciones de costo, para minimizar trayectorias. El resultado de la investigación, demostró el funcionamiento del algoritmo AS como alternativa de optimización. Otra deducción, se trató sobre qué algoritmo es mejor, cuando se habla de controlar enjambres de robots en forma simultanea. De esta forma se dedujo que Modi�ed Particle Swarm Optimization (MPSO) es mejor que AS. Además, se demostró que los algoritmos genéticos no fueron la alternativa más óptima para la implementación 3 en las funciones de minimización. Sin embargo no se realizaron otras modi�caciones, esto se quedó a un nivel muy super�cial. Cabe a resaltar que el alcance que obtuvo esta investigación, abarcó la implementación de los algoritmos a nivel de simulación. En cuanto a los algoritmos genéticos, no se realizaron modi�caciones para su mejora, dejando la posibilidad de avances en futuro, los resultados de aplicar algoritmos genéticos a funciones de costo se muestran en la Figura 1. Se a�rmó que, unicamente se probó con robots de tipo E-puck, considerando sus limitaciones físicas y orientado a lenguaje de programación MATLAB. Figura 1: Resultados de cuatro funciones de costo aplicando algoritmos genéticos [2] 2.2. Algoritmo Ant Colony Optimization (ACO) para aplica- ciones de robótica y biomédica El objetivo principal de este proyecto [3] se basó en implementar estos algorimos de inteligencia computacional y robótica de enjambre, para desarrollar aplicaciones funcionales. Los algoritmos se utilizaron para exploración de terrenos, plani�cación de trayectorias y evasión de obstáculos, en la rama de robótica. Por otro lado, se procedió a un estudio en la implementación del algoritmo para aplicaciones biomédicas. Para los problemas en la rama de robótica mencionados, se propusieron dos algoritmos Ant Colony Optimization y Ant System. Ambos algoritmos fueron implementados en MATLAB, validando su funcionamiento 4 en tres diferentes mapas. Para la validación en la rama biomédica, se propuso procesamiento de imágenes médicas, siendo implementado en MATLAB. La �nalidad de este algoritmo es transformar imágenes distorsionadas a imágenes de referencia. Como punto concluyente, se validó el funcionamiento del algoritmo de plani�cación de trayectorias utilizando robots diferenciales, logrando que estas evadan obstáculos. Además, se validó la implementación utilizando imágenes de prueba e imágenes médicas. Se lograron transformar las imágenes distorsionadas en las imágenes de referencia. El alcance de este trabajo abarcó la implementación, a nivel de simualción, de dichos algoritmos. De manera similar, en [4] se implementó y validó el algoritmo Ant Colony Optimization y Particle Swarm Optimization en aplicaciones de robótica, a nivel físico. Esta investigación buscó migrar los algoritmos desarrollados anteriormente (ACO y PSO) a los microcontro- ladores físicos, de esta forma validar el desempeño. De este modo fué posible validar el algoritmo en robots móviles y en un entorno real. Los resultados que más destacan son la características que posee el algoritmo ACO de crear rutas óptimas, en una implementación real. 2.3. Algoritmos genéticos (AG) para plani�cación de rutas aplicados en robots móviles En las aplicaciones de robótica, hablando de una manera global, el trabajo presentado en [5] abraca el concepto de los sistemas de navegación en un robot. El objetivo de la inves- tigación, es aplicar algoritmos genéticos cruzados en robots móviles, para que estos puedan plani�car rutas libres de colisiones. Este estudio utilizó un robot móvil de accionamiento dife- rencial como objeto de investigación (DMRR). Se utilizaron cinco puntos de referencia como genes del algoritmo diseñado, el algoritmo genético consta de cromosomas, que representa una solución vectorial. Luego, se veri�có si los 30 cromosomas de la población estan libres de colisión. El resultado del experimento con cinco iteraciones evidenció una trayectoria libre de obstáculos, que mientras más iteraciones posee, muestra una convergencia correcta, como se muestra en la Figura 2. Por lo que la investigación concluyó en que el algoritmo genético propuesto modi�ca el proceso de cruce, mediante el cromosoma que tenga mejor aptitud para ser seleccionado. Esta investigación tuvo un alcance a nivel de simulación, unicamente acotando el espacio de búsqueda y con obstáculos estáticos. Se espera que en un futuro, se pueda aplicar esta solución para plani�cación de rutas en un entorno dinámico. 5 Figura 2: Resultados de plani�cación de trayectorias con algoritmos genéticos [5] 2.4. Algoritmos genéticos para optimización multiobjetivo En el artículo presentado en [6] se propone un nuevo algoritmo genético multiagente para optimización multiobjetivo (MAGAMO). El algoritmo se basa en la interacción dinámica de agentes sincronizados AG interdependientes, que tienen evoluciones propias y separadas de sus poblaciones. Los agentes inteligentes buscan soluciones locales subóptimas para la op- timización global, que se completará como resultado de la interaccion de todos los agentes. Como resultado de esto, se puede reducir signi�cativamente la necesidad de volver a calcu- lar funciones optimización a gran escala. Se puede inferir por medio de esta investigación, que el algoritmo genético multiagente desarrollado para la optimización multiobjeto es un algoritmo novedoso basado en la interacción dinámica. Como resultado de esto, se pueden resolver problemas de optimización multiobjetivo que tienen un número demasiado grande de dismensiones, como en la simulación de sistemas grandes reales. 2.5. Aplicación de algoritmos genéticos para evasión de obs- táculos En la investigación [7], con el objetivo de mejorar la capacidad de evasión de obstáculos en el espacio de un robot, se propuso un método basado en el algoritmo genético mejorado. Para implementarlo, se construyó el modelo con parámetros de�nidos para restricciones de control y la trayectoria de evasión de obstáculos se de�ne como el problema de optimización. La feromona liberada en la evolución genética se utilizó como regla de guía de control de los espacios liberados. Como resultado, se obtuvieron los parámetros mecánicos de movimiento para la evasión de obstáculos, al igual que los de seguimiento de trayectoria. El resultado más importante en la simulación demostró que el algoritmo propuesto es efectivo para evitar obstáculos y mejorar el redimiento de control para el robot. 6 CAPÍTULO 3 Justi�cación Anteriormente, en investigaciones realizadas en Universidad del Valle de Guatemala, se indagó de manera muy super�cial, en la rama de algoritmos genéticos y respecto a sus posibles aplicaciones en ingeniería. En la investigación de Iriarte (2021), se incursionó en la aplicación de estos algoritmos, como una propuesta para métodos de optimización de funciones. Como producto, se demostró que los resultados preliminares de la implementación del AG no fueron óptimos, brindando la posibilidad de hacer cambios en él para su futura mejora. Por ende, esta investigación se basó en desarrollar de una manera amplia el campo de aplicaciones para este tipo de algoritmos. Se validaron algunas aplicaciones funcionales en robótica que puedan ser útiles para proponer alternativas en el uso de algoritmos. Además, poder tener una alternativa sobre herramientas de inteligencia computacional que sea capaz de mejorar la e�ciencia de robots móviles. El objetivo se enfocó en las aplicaciones de algoritmos genéticos para optimización en la planeación de trayectorias y evasión de obstáculos para robots móviles, a nivel de simulación. Además, también se desarrollaron aplicaciones funcionales para procesamiento de señales e imágenes. De esta forma, se amplió la rama de investigación sobre dichos algoritmos en la Universidad del Valle de Guatemala, como una alternativa en el tema de inteligencia computacional. De este modo, se proporcionó un panorama más amplio de la investigación realizada en el tema y sus resultados, con el �n de que futuros estudiantes interesados puedan continuar y expandir este campo 7 CAPÍTULO 4 Objetivos 4.1. Objetivo general Evaluar e implementar algoritmos genéticos para optimización en aplicaciones de robó- tica y otras áreas de Ingeniería Mecatrónica. 4.2. Objetivos especí�cos Investigar y evaluar los algoritmos genéticos, dentro del área de inteligencia compu- tacional, y sus aplicaciones. Evaluar e implementar algoritmos genéticos en aplicaciones de robótica como plani�- cación de trayectorias y evasión de obstáculos. Evaluar los algoritmos genéticos en otras aplicaciones de Ingeniería Mecatrónica. Desarrollar escenarios prácticos para las distintas aplicaciones, y validar la implemen- tación de los algoritmos genéticos mediante simulaciones realistas. 8 CAPÍTULO 5 Alcance Este trabajo de graduación abarca la evaluación e implementación de algoritmos gené- ticos (AG) en aplicaciones de robótica y otras áreas de la Ingeniería Mecatrónica, con un enfoque especí�co en la plani�cación de trayectorias y la evasión de obstáculos. El alcance de esta investigación se centra en el desarrollo y validación de estos algoritmos a nivel de simulación, utilizando entornos 2D y 3D para garantizar la correcta funcionalidad en robots móviles con control de pose lineal. En el contexto de la robótica, los algoritmos genéticos han sido implementados para ge- nerar rutas que permiten a los robots evitar colisiones con obstáculos estáticos. El algoritmo se adapta a mapas de diversas con�guraciones y obstáculos de diferentes tamaños y posicio- nes, validando su desempeño a través de múltiples iteraciones y evaluando la calidad de las soluciones obtenidas. El presente trabajo no sólo busca optimizar las rutas generadas, sino también explorar diferentes con�guraciones de parámetros, como la probabilidad de cruce y mutación, para entender cómo estos in�uyen en la diversidad poblacional y el tiempo de convergencia de los algoritmos. Además de la plani�cación de movimiento en robots móviles, se ha extendido el uso de algoritmos genéticos a aplicaciones como el procesamiento de imágenes. En esta área, se evalúa la capacidad del algoritmo para agrupar píxeles en función de sus características, optimizando parámetros que permitan mejorar la precisión de la segmentación en imágenes complejas, como las que se encuentran en el análisis de regiones de diferentes colores. Es importante resaltar que, aunque la mayor parte del trabajo se ha realizado en entor- nos simulados, los resultados obtenidos sientan las bases para futuras implementaciones en entornos físicos. Si bien no se ha contemplado una aplicación directa en hardware durante esta investigación, el uso de simulaciones realistas en plataformas como Webots demuestra la viabilidad de estos algoritmos en escenarios más complejos y dinámicos. Finalmente, el trabajo no está limitado exclusivamente al ámbito de la robótica. Dado que los algoritmos genéticos se pueden aplicar a una amplia variedad de problemas como optimización multiobjetivo, procesamiento de señales, sistemas de control, entre otros. Esta 9 investigación abre las puertas a futuras implementaciones en otras áreas de la Ingeniería Mecatrónica, donde la búsqueda de soluciones óptimas sea un desafío recurrente. 10 CAPÍTULO 6 Marco teórico 6.1. Inteligencia computacional La inteligencia computacional (IC) pertenece a una rama de la inteligencia arti�cial (IA). Este concepto se de�ne como el estudio de mecanismos adaptativos que permiten o facilitan el comportamiento inteligente en ambientes complejos y cambiantes. Este tipo de mecanismos incluye los paradigmas de IA que demuestran la habilidad de aprender o adaptarse a nuevas situaciones. Entre los paradigmas cubiertos resaltan la computación evolutiva y la inteligencia de enjambre [1]. 6.1.1. Computación evolutiva El objetivo de la computación evolutiva es imitar el proceso de la evolución natural, basándose en el concepto de la supervivencia del más fuerte. Aquellos individuos que son más débiles mueren y las características se descartan. Los algoritmos evolutivos usan una población de ejemplares donde el individuo se denomina cromosoma. El cromosoma de�nirá las características de cada individuo en la población. Las características se denominan genes. El valor de un gen se denomina alelo. La descendencia se genera combinando partes de los padres, en un proceso conocido como cruce. La fuerza de supervivencia de un individuo se mide mediante una función de aptitud que re�eja los objetivos y limitaciones del problema a resolver. Además, las características de comportamiento se pueden utilizar para in�uir en el proceso evolutivo en cambios genéticos y características que evolucionan por separado [1]. Dependiendo de la aplicación, se pueden implementar los diferentes paradigmas: Algoritmos genéticos (AG) Programación genética (GP) Programación evolutiva (PE) 11 Estrategias evolutivas Evolución diferencial Evolución cultural Coevolución 6.2. Algoritmo evolutivo genérico La evolución mediante selección natural de una población de individuos elegida al azar puede considerarse como una búsqueda en el espacio de posibles valores cromosómicos. En ese sentido, un algoritmo evolutivo (AE) es una búsqueda estocástica de una solución óptima a un problema determinado. El proceso de búsqueda evolutiva esta in�uenciado por los siguientes componentes principales de un AE: una codi�cación de soluciones al problema como cromosoma, una función para evaluar la aptitud física o la fuerza de supervivencia de los individuos, inicialización de la población inicial, operadores de selección y operadores de reproducción. En el Algoritmo 6.1 se muestra una la combinación de los componentes para formar un algoritmo genético. Algoritmo 6.1: Algoritmo evolutivo genérico 1 Let t = 0 be the gene ra t i on counter ; 2 Create and i n i t i a l i z e an n_x dimens iona l populat ion , C_(0) , to c o n s i s t o f n_s i nd i v i d u a l s ; 3 whi l e s topping cond i t i on ( s ) not t rue do 4 Evaluate the f i t n e s s , f (x_r_( t ) ) , o f each ind iv idua l , x_i_( t ) ; 5 Perform reproduct i ons to c r e a t e o f f s p r i n g ; 6 S e l e c t the new populat ion , C_( t+1) ; 7 Advance to the new generat ion , i . e . t=t+1; 8 end Los pasos de la implementación del algoritmo se aplica de forma iterativa hasta que se cumpla la condición de parada. Cada iteración del AE se denomina generación, dependien- do la forma en que se implemente el componente del algoritmo dará como resultado los paradigmas como algoritmos genéticos y entre los ya mencionados con anterioridad [1]. 6.3. Representación del cromosoma En la naturaleza los cromosomas son estructuras de moléculas compactadas de ADN entrelazadas que se encuentran en el núcleo de las células orgánicas. Cada cromosoma con- tiene una gran cantidad de genes (unidad de herencia), como se ilustra en la Figura 3. En el contexto de CE, cada individuo representa una solución candidata a un problema de op- timización. Las características de un individuo están presentadas por un cromosoma. Estas características se re�eren a las variables del problema de optimización, para las cuales se 12 busca una asignación óptima. Cada variable que debe optimizarse se denomina gen, la uni- dad más pequeña de información. Las características de un individuo se dividen en genotipos y fenotipos. Un genotipo describe la composición genética de un individuo y un fenotipo son solo los rasgos u comportamiento. En la implementación de algoritmos genéticos, la representación de los cromosomas pue- de variar según el tipo de datos y la naturaleza del problema. Las Figuras 4 y 5 ilustran dos formas comunes de codi�cación de cromosomas: la codi�cación entera y la codi�cación en punto �otante (o real). En la codi�cación entera (Figura 4]), cada gen del cromosoma toma valores discretos, típicamente representando estados especí�cos o decisiones binarias. Esta codi�cación es útil en problemas de combinatoria o cuando las soluciones deben estar limi- tadas a valores discretos. Por otro lado, la codi�cación en punto �otante (Figura 5) permite que los genes adopten valores continuos, siendo ideal para problemas de optimización que requieren una mayor precisión en los parámetros. Estas representaciones son fundamentales en la aplicación de algoritmos genéticos, pues afectan tanto la convergencia del algoritmo como la precisión de los resultados obtenidos. Figura 3: Representación de gen y cromosoma con codi�cación binaria [1] Figura 4: Representación de gen y cromosoma con codi�cación entera [1] Figura 5: Representación de gen y cromosoma con codi�cación de punto �otante [1] En el diseño de AE, el esquema de representación clásico para AG, son vectores binarios de longitud �ja. En el caso de una espacio de búsqueda de n dimensiones, cada individuo consta de n variables y cada variable está codi�cada como una cadena de bits [1]. 13 6.4. Población inicial Debido a que los AE son algoritmos de búsqueda estocástica basados en la población, cada uno mantiene una población de soluciones candidatas. El primer paso en aplicaciones de un AE para resolver un problema de optimización es generar una población inicial. La forma estándar de generar una población inicial es asignar un valor aleatorio del dominio permitido a cada uno de los genes del cromosoma. Si las regiones de búsqueda no están cubiertas por la población inicial, es probable que el proceso de búsqueda descuide esas partes. Un gran número de individuos aumenta la diversidad, mejorando así las capacidades de exploración de la población. Cuantos más individuos mayor será la complejidad computacio- nal por generación [1]. 6.5. Función de aptitud Para determinar la capacidad de supervivencia de un individuo en un AE, se utiliza una función matemática para cuanti�car qué tan buena es la solución representada por un cromosoma. La función de aptitud asigna una representación cromosómica a un valor escalar. La función aptitud se expresa en la ecuación (1). f : Γnx → R (1) Normalmente, la función de aptitud proporciona una medida absoluta de aptitud. Es de- cir, la solución representada por un cromosoma se evalúa directamente utilizando la función objetivo. Es importante comprender que existen diferentes tipos de problemas de optimiza- ción que in�uyen en la formulación de la función aptitud [1]. Por lo que deben mencionarse los diferentes tipos de problemas de optimización: Problemas de optimización sin restricciones Problemas de optimización restringido Problemas de optimización multiobjeto Problemas dinámicos y ruidosos 6.6. Selección El objetivo principal de los operadores de selección es destacar mejores soluciones. Esto se logra en dos de los pasos principales de un AE, siendo la primera selección de la nueva población y la segunda reproducción. A continuación, se proporciona un resumen de los operadores más utilizados. 14 6.6.1. Precisión selectiva Los operadores de precisión selectiva, se caracterizan por su tiempo de adquisición. Se relaciona con el tiempo que se requiere para producir una población uniforme. Se de�ne como la velocidad a la que la mejor solución ocupará a toda la población mediante la aplicación repetida del operador de selección. Este tipo de operador disminuye la diversidad en la población rápidamente llevando a una convergencia prematura. 6.6.2. Selección aleatoria La selección aleatoria es el operador de selección más simple, donde cada individuo tiene la misma probabilidad 1 ns de ser seleccionado. No se utiliza información de aptitud, lo que signi�ca que los mejores y los peores individuos tienen exactamente la misma posibilidad de sobrevivir hasta la siguiente generación. Sin embargo, la selección aleatoria tiene la precisión más baja entre todos los operadores mencionados [1]. 6.6.3. Selección proporcional La selección proporcional, propuesta por Holland, sesga la selección hacia los individuos más aptos. Se crea una distribución de probabilidad proporcional a la aptitud y se seleccionan los individuos muestreando la distribución [1]. φs(xi(t)) = fΥ(xt(t))∑ns l=1 fΥ(xl(t)) (2) donde ns es el numero total de individuos y φs(xi(t)) es la probabilidad de que xi sea seleccionado. fΥ(xt(t)) es la aptitud escalada de xi, para producir un valor de punto �otante positivo. Suponiendo valores de maximizan y aptitud normalizados, la selección de la rueda de la ruleta se resume al algoritmo mostrado en el Algoritmo 6.2 siendo un ejemplo de la estructura del operador de selección proporcional. Algoritmo 6.2: Estructura del algoritmo de selección proporcional 1 Let i = 1 , where i denotes the chromosome index ; 2 Ca l cu la te φ_(x_i ) us ing equ i a t i on 1 ; 3 sum = φ_x_i ; 4 Choose r ~ U(0 , 1 ) ; 5 whi l e sum < r do 6 i = i +1, i . e . advance to the next chromosome ; 7 sum = sum + φ_x_i ; 8 end 9 Return x_i as the s e l e c t e d i nd i v i dua l ; 15 6.6.4. Selección por competencia (torneo) La selección por torneo selecciona un grupo de nts individuos de manera aleatorio dentro de la población, donde nts < ns (ns es el numero total de individuos). Se compara el desempeño de los individuos seleccionados y el operador selecciona y devuelve al mejor individuo de este grupo [1]. 6.6.5. Selección basada en Rank La selección basada en Rank, utiliza el ordenamiento de los valores de aptitud para determinar la probabilidad de selección y no los valores absolutos de aptitud. Por lo tanto, la selección es independiente de los valores reales de aptitud, con la ventaja de que el mejor individuo no dominará el proceso de selección [1]. 6.7. Operadores de reproducción La reproducción es el proceso de producir descendencia a partir de padres seleccionados mediante la aplicación de operadores de cruce y/o mutación. El cruce es el proceso de creación de uno o más individuos nuevos mediante la combinación de material genético seleccionado aleatoriamente de dos o más padres. Si la selección se centra en los individuos más aptos, la precisión de selección pueden causar una convergencia prematura debido a la reducción de la diversidad de las nuevas poblaciones [1]. La mutación es el proceso de cambiar aleatoriamente los valores de los genes en un cromosoma. El principal objetivo de la mutación es introducir nuevo material genético en la población, aumentando así la diversidad genética. La mutación debe aplicarse con cuidado para no distorsionar el material genético bueno en individuos muy aptos [1]. 6.8. Condición de detención Los operadores evolutivos se aplican iterativamente en un AE hasta que se cumple una condición de parada. La condición de parada más simple es limitar el número de generaciones que el AE puede ejecutar o, alternativamente, se impone un límite de número de evaluaciones de la función de aptitud. Este límite no debería ser demasiado pequeño, de lo contrario el asesor no tendrá tiempo su�ciente para explorar el espacio de búsqueda. Además de un límite en e tiempo de ejecución, generalmente se utiliza un criterio de convergencia para detectar si la población converge al valor esperado. La convergencia se de�ne vagamente como el evento en el que la población se estanca. Es decir, cuando no existe ningún cambio genotípico o fenotípico en la población [1]. Se pueden utilizar los siguientes criterios de convergencia: Terminar cuando no se observe ninguna mejora durante varias generaciones consecu- 16 tivas. Terminar cuando no haya cambios en la población. Terminar cuando se haya encontrado una solución aceptable. Terminar cuando la pendiente de la función objetivo sea aproximadamente cero. 6.9. Decodi�cación de variables La decodi�cación en algoritmos genéticos es un proceso fundamental que convierte las soluciones representadas en los cromosomas a un formato adecuado para evaluar su aptitud en el contexto del problema especí�co. Según Engelbrecht [1], la decodi�cación depende de la representación del cromosoma y del dominio de la solución. La representación de los cromosomas puede variar considerablemente, incluyendo codi�cación binaria, entera, y en punto �otante (real), cada una con ventajas y aplicaciones particulares. La elección de la estrategia de decodi�cación in�uye signi�cativamente en el rendimiento del algoritmo genético. Engelbrecht señala que la decodi�cación debe ser compatible con la función de aptitud y el tipo de datos requeridos para asegurar que los cromosomas generen soluciones válidas y e�caces. Un claro ejemplo de decodi�cación sería considerando una cadena binaria de L bits, C = c1c2...c3, que representa un valor en el intervalo [a, b]. Luego se calcula el valor decimal como se muestra en la Ecuación (3). D = L∑ i=1 ci · 2L−i (3) Luego el valor del intervalo D se mapea al intervalo [a, b] usando la Ecuación de escalado lineal (4]). El tipo de decodi�cación x = a+ D 2L − 1 · (b− a) (4) 6.10. Algoritmos genéticos (AG) Los algoritmos genéticos modelan la evolución genética, donde las características de los individuos se expresan mediante genotipos. Los principales operadores impulsores de un AG son la selección (para moldear la supervivencia del mas apto) y la recombinación mediante la aplicación de un operador cruzado (para modelar la reproducción) [1]. El algoritmo genético propuesto por Engelbrecht, contiene los siguientes detalles. Utiliza una representación de cadena de bits. 17 Utiliza selección proporcional para seleccionar padres para recombinación. Utiliza el cruce de un punto como método principal para producir descendencia. Se propuso la mutación uniforme como un operador de fondo. Los algoritmos genéticos combinan la explotación de soluciones conocidas con la explora- ción de nuevas áreas del espacio de posibles soluciones. Su e�cacia depende de una apropiada combinación entre la explotación y la exploración. La selección, de acuerdo a las caracterís- ticas y aptitudes de individuos de una población en combinación con el operador genético de cruza, constituyen la tasa de la explotación. Mientras que el operador de mutación es la base de la exploración de nuevas regiones del espacio de búsqueda. Un algoritmo genético, simula el comportamiento dinámico de una población genética generando una base de cono- cimientos formada por estructuras que se desarrollan en respuesta al desempeño observado en su medio ambiente operacional [8]. En términos generales, los algoritmos genéticos están constituidos por: La codi�cación de una población de individuos La decodi�cación de la población de individuos La selección de individuos para producir los descendientes La reproducción de dichos individuos por medio de operadores genéticos Los algoritmos genéticos di�eren de los métodos tradicionales de búsqueda y optimización en los siguientes puntos: los AG's tratan el problema como una caja negra, usan codi�cación, buscan en una población de posibles soluciones y por último emplean operadores aleatorios. Cabe resaltar que muchos métodos de búsqueda requieren de ciertos antecedentes o informa- ción adicional en el problema de estudio. En el caso de los algoritmos genéticos no necesitan de información adicional. Por lo tanto, estos tratan el problema como una caja negra y solo requieren evaluar la función objetivo. En la Figura 6, se muestra un esquema que explica cómo debe funcionar un AG, desde la selección por medio de la función aptitud hasta el proceso de cruza para generación de nuevos individuos. 18 Figura 6: Diagrama de funcionamiento general de un AG [1] 6.10.1. Cruce Los operadores cruzados se dividen en tres categorías dependiendo el número de padres utilizados. Las categorías son asexual, sexual y recombinación. Los padres se seleccionan utilizando cualquiera de los esquemas de selección discutidos anteriormente. Al seleccionar a los padres deben considerase ciertas cuestiones como seleccionar al mismo individuo, como ambos padres, o que este mismo participe en más de una aplicación del cruce. Cabe a men- cionar que el operador de cruce considera política de remplazo, si se genera una descendencia que sea mejor que el padre puede remplazarlo [1]. 6.10.2. Representaciones binarias La mayoría de los operadores de cruce para representaciones binarias son sexuales y se aplican con dos padres seleccionados. Si x1(t) y x2(t) denotan a los dos padres seleccionados, entonces el proceso de recombinación se resume en el Algoritmo 6.3. Entre los operadores desarrollados se encuentran los siguientes puntos para computadorizar la mascara: Cruce de un punto: los segmentos de genes se intercambian entre padres para crear su descendencia, y no genes simples. En la Figura 7 se muestra un esquema de este tipo de cruce. 19 Figura 7: Esquema de cruce por medio de un punto [1] Cruce de dos puntos: en este caso se seleccionan aleatoriamente dos posiciones de bits y las cadenas de bits entre estos puntos se intercambian como se ilustra en la Figura 8. Figura 8: Esquema de cruce por medio de dos puntos [1] Cruce uniforme: el cruce uniforme es una técnica completamente diferente de las 20 vistas hasta el momento. Cada gen de la descendencia tiene las mismas probabilidades de pertenecer a uno u otro padre. Aunque se puede implementar de muy diversas formas, la técnica implica la generación de una máscara de cruce con valores binarios. Si en una de las posiciones de la máscara hay un 1, el gen situado en esa posición en uno de los descendientes se copia del primer padre. Si por el contrario hay un 0 el gen se copia del segundo padre. Para producir el segundo descendiente se intercambian los papeles de los padres, o bien se intercambia la interpretación de los unos y los ceros de la máscara de cruce [9]. Esta representación se muestra en la Figura 9. Figura 9: Esquema de cruce uniforme [1] Algoritmo 6.3: Estructura del algoritmo de cruza por representación binaria 1 Let x̂1(t) = x1(t) and x̂2(t) = x2(t) ; 2 i f U(0 , 1 ) ≤ pc then 3 Compute the binary mask , m( t ) ; 4 dor j = 1 , . . . , nx do 5 i f mj = 1 then 6 // swap the b i t s 7 x̂1j(t) = x1j(t) 8 x̂2j(t) = x2j(t) 9 end 10 end 11 end 6.11. Plani�cación de movimiento y trayectorias En los robots móviles, el problema de plani�car una trayectoria se puede resolver en- contrando una ruta y de�niendo una ley de sincronización en el camino. Se puede utilizar cualquier esquema de interpolación para plani�car la trayectoria de tal manera que se satisfa- gan las condiciones de frontera apropiadas. La evolución de otras variables de con�guración, junto con las entradas de control asociadas, se pueden calcular algebraicamente. La ruta de espacio de con�guración satisfará automáticamente las restricciones no holonómicas. En cuanto a la plani�cación de trayectorias, una vez determinado el un camino, es posible 21 elegir una ley de tiempo con la que el robot deba seguirla. En general, estos se integran en el procedimiento de diseño como la optimización de un criterio de coste adecuado a lo largo de la trayectoria. Una técnica sencilla para atacar el problema de plani�cación óptima consiste en parametrizar excesivamente el esquema de interpolación adoptado, a �n de perseguir la mejora. Normalmente, se adoptan técnicas numéricas del criterio de coste eligiendo adecuadamente los parámetros redundantes [10]. 6.11.1. Aplicaciones de AG para plani�cación de movimiento Se han utilizado algoritmos genéticos, aprovechando sus capacidades para resolver proble- mas de optimización, para encontrar el camino más seguro y evitar la colisión con obstáculos. En el Artículo [5], se aplica un algoritmo genético para generar el mejor camino para un robot móvil con accionamiento diferencial y que este evite colisiones con obstáculos estáticos en el entorno. El método propuesto propone un proceso de mutación para ampliar el espacio de búsqueda. El método propuesto para la plani�cación consta de un individuo, en este caso el cromo- soma, como una celda de 5 puntos de referencia, es decir, (x0, y0), (x1, y1)...(x4, y4). Estos puntos de referencia actuarán como genes en el algoritmo genético diseñado. El cuanto al modelo ambiental, las condiciones se necesita información sobre obstáculos, como forma, número tamaña y posición. En este estudio el entorno tiene un tamaño de matriz 150× 150 como se muestra en la Figura 10. Este artículo propone un algoritmo genético cruzado mo- di�cado que tiene como objetivo obtener un nuevo cromosoma que tenga buenos valores de aptitud [5]. Figura 10: Entorno de prueba para algoritmo genético [5] Para la veri�cación, se evalúa la colisión de la generación de la población inicial para que el camino sea factible o no. Los pasos comunes para comprobarlo es mediante el cálculo de la distancia euclidiana con la Ecuación (5). 22 d(p,q) = √√√√ n∑ i=1 (pi − qi)2 (5) 6.11.2. Codi�cación de variables de tipo �otante en path-planning El cromosoma en este problema de búsqueda se representa como un vector de solución. La codi�cación que se utiliza en esta técnica son enteros de coordenadas cartesianas. En la Figura 11 se muestra el número de genes de un cromosoma como la representación general, es decir, la forma de expresar la codi�cación. Dos genes representan el punto inicial y �nal, los puntos �jos, siendo los intermedios los que cambian durante el proceso [5]. Figura 11: Codi�cación de solución, representación del cromosoma [5] 6.11.3. Función de aptitud para trayectorias Para encontrar la calidad del cromosoma en este problema, se debe tener un punto de referencia claro, es decir ¾qué cualidad se debe evaluar? Para esto se utiliza la función de aptitud de la Ecuación (6), que en el problema de plani�cación evalúa la distancia más corta y libre de colisiones. Basado en la ecuación, se puede deducir que el mejor cromosoma, con distancia más corta, tendrá el máximo valor de aptitud. f(i, j) = 1√ (xi − xj)2 + (yi − yj)2 (6) 6.11.4. Cruce aritmético En este problema en especial, se tiene un cromosoma en el cual se comparara la aptitud del padre con el hijo. Ya que se de�nió una representación de tipo entero, se seguirá la regla de cruce aritmético. Con el siguiente criterio: Si el valor de aptitud del progenitor es mejor que el del padre, el el progenitor pasa a la nueva generación. Luego se realiza mutación aleatoriamente. Si el valor de aptitud del padre sigue siendo mejor que el del progenitor, se mantiene al padre en la nueva generación. Luego se realiza la mutación aleatoriamente. 23 El padre principal que se usará principalmente para el cruce aritmético será el mejor individuo de la generación. Este será cruzado con otro cromosoma de la misma generación tomado al azar. El propósito de este procedimiento es mantener los buenos genes y here- darlos. Hay varios métodos de cruza, como fueron mencionados anteriormente, pero en este caso, se utilizará el cruce aritmético representado por la Ecuación 7. Este método se explica mejor en la Figura 12 como una suma aritmética de las componentes del gen [5]. C1 = λ1X + λ2Y C2 = λ2X + λ1Y (7) Donde C1 y C2 son los dos progenitores resultantes del cruce aritmético entre los padres con la mejor aptitud. Figura 12: Ejemplo de cruce aritmético para cromosomas de 2 dimensiones cartesianas [5] 6.11.5. Ruleta para cruce y mutación Debido a que en este caso se pretende utilizar el método de �cruce uniforme�, se debe tener una máscara binaria. La máscara permitirá indicar los puntos que se cruzan a favor del progenitor 1 y el progenitor 2. Los puntos de cruce serán seleccionados de manera aleatoria usando el método de la ruleta giratoria. Luego de seleccionar los puntos de cruza se realizará el cruce aritmético [5]. El método de la ruleta se muestra grá�camente en la Figura 13, dependiendo de la longitud del cromosoma, igual será la longitud de la cadena binaria. 24 Figura 13: Representación del método de ruleta giratoria [5] 6.12. Otras aplicaciones de algoritmos genéticos para proble- mas de plani�cación de movimiento El AG debe ser capaz de negociar su ruta desde su punto de partida hasta el punto �nal. También es necesario incluir dentro de la solución la capacidad de optimizar estas rutas para múltiples puntos de inicio [11]. Para codi�car las soluciones, la población es representada por una cadena de valores en la Figura 14. En este esquema se codi�can con base en la dirección de movimiento como North, West, East, etc. Figura 14: Solución a la codi�cación de variables de movimiento [11] Esta es otra manera de representar las variables para el problema de búsqueda para trayectoria libre de obstáculos. Sin embargo, el problema sera la codi�car las cadenas del cromosoma, es posible pero es una tarea larga. Además, tiene un tiempo computacional muy alto según los resultados descritos en [11]. 25 6.13. Otras aplicaciones exitosas de AG en diferente área 6.13.1. Algoritmos genéticos para segmentación de imágenes Se propone utilizar un algoritmo genético para explorar el espacio de soluciones, en el sentido de que cada pixel se agrupa en otros pixeles mediante una función de distancia basada en segmentos ya calculados, tanto locales como globales. Las dos cuestiones que son abordadas para adaptar un AG para la segmentación de imágenes son: Seleccionar una representación apropiada para cada solución potencial. Formular la función de aptitud adecuada en términos de tamaño. Los algoritmos de segmentación de imágenes contienen parámetros que se utilizan para controlar los resultados de la segmentación. El sistema genético puede cambiar dinámica- mente los parámetros para lograr un mejor rendimiento [12]. El proceso del AG basado en segmentación se puede resumir de la manera que se muestra en la Figura 15. En este esque- ma se representa la segmentación como valores aleatorios de una población inicial, después una evaluación de resultados que termina si satisface el resultado, de lo contrario se repite el ciclo por medio de los operadores de reproducción. Figura 15: Proceso de algoritmo genético para segmentación de imágenes [12] Función de aptitud La calidad de cada cromosoma se evaluó mediante una función de aptitud basada en la entropía intrarregión (Hintra) y la entropía interregión (Hinter). La función se de�nió como: f(C) = − ( Hintra Hinter + ϵ ) Donde: 26 Hintra: entropía promedio de las intensidades dentro de cada región. Hinter: entropía de las intensidades entre regiones. ϵ: término pequeño para evitar divisiones por cero. La entropía intrarregión se calculó como: Hintra = 1 k k∑ i=1 ni∑ j=1 −pij log(pij) Donde: k: número de regiones segmentadas. ni: número de píxeles en la región Ri. pij : probabilidad de que un píxel en la región Ri tenga el nivel de intensidad j. La entropía interregión se de�nió en términos de la distribución global de intensidades, calculada como: Hinter = − n∑ j=1 Pj log(Pj) Donde: n: número total de niveles de intensidad. Pj : probabilidad de intensidad global para el nivel j en toda la imagen. f(C) = − ( Hintra Hinter + ϵ ) Figura 16: Función de aptitud basada en la entropía intra e interregión [13] 6.14. Procesamiento de imágenes 6.14.1. Segmentación de imágenes La segmentación de imágenes es una técnica utilizada en el procesamiento digital para dividir una imagen en múltiples regiones basándose en las características de los píxeles, como 27 color o forma. Esto permite separar el fondo del primer plano o agrupar áreas similares, por ejemplo, en aplicaciones médicas para detectar tumores en imágenes cerebrales o de otros órganos. Su objetivo principal es identi�car y resaltar las partes relevantes de la imagen para un análisis más detallado. Se han desarrollado numerosos algoritmos para la segmentación, adaptados a aplicaciones especí�cas como la conducción autónoma, la video vigilancia y la visión arti�cial. Este proceso comienza convirtiendo la imagen en regiones o máscaras etiquetadas, lo que facilita seleccionar y procesar únicamente las áreas de interés, optimizando los recursos y mejorando la e�ciencia del análisis. Técnicas de segmentación de imágenes Thresholding : la umbralización es una técnica de segmentación basada en el esta- blecimiento de un valor límite para separar regiones en una imagen. Los píxeles se asignan a diferentes grupos según si sus valores son mayores o menores al umbral. Es útil en imágenes con contrastes claros entre fondo y objeto, y puede implementarse de manera global o local. Clustering : el agrupamiento clasi�ca los píxeles en grupos homogéneos basados en características como color, intensidad o textura. Técnicas como K-means agrupan pí- xeles según su similitud, generando regiones segmentadas. Es adecuada para imágenes con múltiples colores o texturas. Segmentación basada en grafos: la segmentación basada en grafos representa la imagen como un grafo donde los píxeles son nodos y las conexiones indican similitud. Los algoritmos dividen el grafo en subgrafos o regiones mediante criterios de minimi- zación de cortes, logrando una segmentación e�ciente en imágenes complejas. Basada en crecimiento: el crecimiento de regiones comienza con un conjunto inicial de píxeles o semillas, expandiendo las regiones al agregar píxeles vecinos que cumplan ciertos criterios de similitud. Es útil para segmentar objetos con límites bien de�nidos y propiedades homogéneas. Deep learning : la segmentación basada en aprendizaje profundo, utiliza redes neu- ronales convolucionales (CNNs) para aprender patrones y características directamente de las imágenes. Modelos como U-Net han demostrado ser efectivos para segmentar objetos en escenarios complejos, como imágenes médicas o escenas naturales [14]. (a) Thresholding. (b) Clustering (K-means) (c) Agrupación por grafos Figura 17: Ejemplos de segmentación de imágenes utilizando diferentes técnicas [14] 28 6.15. Funciones de costo Las funciones de costo son un elemento central en problemas de optimización. Estas funciones cuanti�can la calidad de una solución en relación con el problema que se está resolviendo. En términos simples, una función de costo asigna un valor numérico a cada posible solución, representando qué tan �buena� o �mala� es esa solución [15]. En [2], se utilizan para evaluar los costos que requiere el algoritmo Particle Swarm Optimization. Las funciones que se muestran a continuación, son algunas de las funciones y conjuntos de datos comunes que se utilizan para probar algoritmos de optimización. Figura 18: Función de Ackley [15] Figura 19: Función de Booth [15] Figura 20: Función de Rosenbrock [15] Figura 21: Función de Rastrigin [15] 6.16. Funciones de super�cies Las super�cies cuadráticas son super�cies en un espacio tridimensional que se describen mediante ecuaciones cuadráticas en dos variables. Estas super�cies son útiles en problemas 29 de optimización porque suelen tener formas bien de�nidas, lo que permite identi�car fácil- mente los puntos máximos o mínimos en problemas de optimización [16]. A continuación, se presentan 3 diferentes tipos de super�cies. Figura 22: Función de paraboloide elíptico [15] Figura 23: Función de hiperboloide de 1 hoja [15] Figura 24: Función de campana de Gauss [15] 6.17. Controlador no lineal de pose para robots móviles El controlador no lineal de pose para robots móviles utiliza un enfoque basado en la cinemática diferencial para controlar el robot y hacer que siga una trayectoria deseada. Este controlador típicamente usa tres constantes: kρ: ganancia para la distancia objetivo kα: ganancia para el ángulo de orientación respecto al objetivo kβ : ganancia para el ángulo de orientación relativo al objetivo 30 Estos controladores están diseñados para garantizar que el robot se acerque a la trayectoria deseada y siga la dirección correcta para minimizar el error en la posición y orientación del robot. Las ecuaciones típicas del controlador no lineal de pose para robots móviles se basan en la cinemática diferencial, expresándose como en la Ecuación 8, que describe el control de velocidad lineal v y velocidad angular ω [17]. v = Kρρ ω = Kαα+Kββ (8) 6.18. Intersección de una recta con un plano limitado en un espacio tridimensional En la plani�cación de trayectorias 3D es posible encontrar varias formas de medir la coli- sión con obstáculos. En cuanto la experimentación descrita en esta investigación se requirió de un método que calcule de alguna forma la distancia o intersección de una partícula con un plano. Por lo que, se utilizó el método propuesto por un cálculo algebraico que permite conocer si la recta entre dos puntos interseca el plano. Sea un espacio tridimensional R3, donde se obtiene que: Un plano Π dado por la ecuación y = c, limitado por los intervalos: 0 < x < n, 0 < z < k. Una recta parametrizada que conecta dos puntos p1 = (x1, y1, z1) y p2 = (x2, y2, z2), descrita en forma paramétrica como: r(t) = x(t) y(t) z(t)  = (1− t)x1 + tx2 (1− t)y1 + ty2 (1− t)z1 + tz2  , donde t ∈ [0, 1] [18]. Se determinará si la recta r(t) intersecta el plano Π dentro de los límites establecidos. 6.18.1. Ecuación para la intersección con el plano y = c Para encontrar el parámetro t en el que la recta intersecta el plano Π, se utiliza la condición: y(t) = c, donde y(t) = (1− t)y1 + ty2. Sustituyendo esta expresión, se determina: (1− t)y1 + ty2 = c. Reorganizando para despejar t: y1 − ty1 + ty2 = c, 31 y1 + t(y2 − y1) = c, t = c− y1 y2 − y1 . Este valor de t representa el punto en la recta donde y(t) = c [18]. Es importante veri�car si: t ∈ [0, 1]. Si t ∈ [0, 1], la recta intersecta el plano y = c entre los puntos p1 y p2. Si t /∈ [0, 1], la recta no intersecta el plano y = c entre los puntos p1 y p2, aunque podría intersectarlo fuera de este segmento. 6.18.2. Condición adicional: veri�cación de los límites en x y z Si t ∈ [0, 1], la recta intersecta el plano y = c. Sin embargo, el plano Π está limitado a un rectángulo de�nido por 0 < x < n y 0 < z < k. Se debe veri�car si las coordenadas x(t) y z(t) del punto de intersección también cumplen estas restricciones. Las coordenadas x(t) y z(t) se calculan sustituyendo t en las expresiones paramétricas: x(t) = (1− t)x1 + tx2, z(t) = (1− t)z1 + tz2 Luego se veri�can las condiciones: 0 < x(t) < n, 0 < z(t) < k. Si ambas condiciones son satisfechas, el punto de intersección está dentro de la región limitada del plano Π. Si cualquiera de las condiciones no se cumple, el punto de intersección está fuera de los límites permitidos en x y z, por lo que la recta no intersecta la región limitada del plano Π [18]. 6.18.3. Criterio de veri�cación Este criterio se resume a un código computadorizado que realiza los cálculos e�ciente- mente. El procedimiento para determinar si la recta intersecta el plano limitado se resume al siguiente: Calcular el valor de t usando: t = c− y1 y2 − y1 . Veri�car si t ∈ [0, 1]: � Si t /∈ [0, 1], la recta no intersecta el plano Π en el segmento p1p2. 32 � Si t ∈ [0, 1], calcular las coordenadas del punto de intersección: x(t) = (1− t)x1 + tx2, z(t) = (1− t)z1 + tz2. Veri�car las condiciones: 0 < x(t) < n, 0 < z(t) < k. Concluir: � Si ambas condiciones se satisfacen, la recta intersecta la región limitada del plano Π. � Si cualquiera de las condiciones no se cumple, el punto de intersección está fuera de la región limitada del plano Π. 33 CAPÍTULO 7 Validación general de algoritmo genético En este capítulo se presenta la metodología aplicada para la evaluación de los algoritmos genéticos en su forma general. También, se describe el procedimiento realizado para la ob- tención de los resultados de optimizar funciones de costo y matemáticas. Estas pruebas se basan en buscar puntos máximos y mínimos dentro de un dominio. Para las simulaciones en este capítulo se utilizó lenguaje MATLAB versión R2020a. Los resultados obtenidos tienen el objetivo de garantizar el funcionamiento general de los AG en aplicaciones básicas. Con el concepto de este tipo de algoritmo, se aplican estructuras similares adaptadas a otro tipo de aplicación en los siguientes capítulos. 7.1. Algoritmos genéticos para optimizar funciones de costo Previamente se mencionó sobre una aplicación de AG general para evaluar costos en un algoritmo de plani�cación de trayectorias [2]. Esta investigación tuvo como objetivo incur- sionar en el área, planteando el problema para optimizar las funciones de costo (mínimo) requerida en el Particle System Optimization (PSO). El problema consiste en 4 funciones principales descritas en el marco teórico: Rosenbrock, Ackley, Rastrigin y Booth. Para adap- tar el AG a este planteamiento se utiliza la estructura algorítmica de la Figura 6. El proceso consiste en armar la estructura ya mencionada, implementando el algoritmo descrito en 6.1. Para crear el algoritmo del ciclo principal se desarrollaron las diferentes funciones por separado utilizando MATLAB. Las funciones desarrolladas para este algoritmo: generación de población inicial, codi�cación de individuos en población, de�nición de la función objetivo (aptitud), asignación de rango, ruleta, cruce de un punto, mutación, selección y decodi�- cación. Las funciones mencionadas en el marco teórico, están compuestas de los algoritmos descritos para el cruce, para ruleta y codi�cación. La adaptación del algoritmo genético a este problema se describe en el siguiente diagrama de �ujo de la Figura 25. 34 Figura 25: Diagrama de �ujo de AG para minimizar costos Luego de tener listo el algoritmo para la optimización de las funciones costo, se estable- cieron diferentes parámetros de simulación. El objetivo de variar los parámetros es validar distintos escenarios, para poder implementar esta estructura a otro concepto de búsqueda y optimización. En el Cuadro 1, se describe el intervalo cerrado donde se realiza el espacio de búsqueda del AG, para todas las validaciones. Función Dominio x Dominio y Longitud Rosenbrock [-5, 10] [-5, 10] 20 Ackley [-32.768, 32.768] [-32.768, 32.768] 24 Rastring [-5.12, 5.12] [-5.12, 5.12] 20 Booth [-10, 10] [-10, 10] 20 Cuadro 1: Parámetros de simulación en base a su función de costo Una mejor perspectiva de lo que se habló es ver la representación grá�ca de lo que implica codi�car las variables del problema. Para codi�carlas se utiliza el proceso inverso visto en la Sección 6.11. Es decir, utilizando una representación de cromosoma y codi�cación binaria. Esta de�nición se resume en crear una población binaria de longitud l donde los n bits más signi�cativos representan la variable x y los m bits menos signi�cativos la variable y. La Figura 26 representa de manera visual lo descrito anteriormente, con un ejemplo de n = 8 y m = 12, pues este sería nuestro cromosoma codi�cado en binario. 35 Figura 26: Representación y codi�cación del cromosoma para problema de optimización de costo En cuanto a la decodi�cación de las variables para este problema, primero se de�ne que estas se decodi�can únicamente cuando se consigue la población �nal. Esto es con �nes de representar el resultado como una cifra entendible a las variables traducidas, es decir, un valor (x, y). Para lograr la traducción de la variable utilizaremos la Ecuación (9) que contiene la conversión de la parte binaria a decimal para mapear a coordenadas cartesianas la solución. xi = linf + decimal (11001 . . . 112) ( lsup − linf 2lind − 1 ) yi = linf + decimal (11001 . . . 112) ( lsup − linf 2lind − 1 ) (9) 7.1.1. Resultados de primer escenario para optimización de función de costo Para el primer escenario, se realizó la validación de las funciones con los siguientes pará- metros: probabilidad de cruce 90%, probabilidad de mutación 80%, número de individuos 100 por población y la longitud de cada individuo de 20 bits (10 en x y 10 en y). Este escenario se hace con un alto porcentaje de mutación para explorar la capacidad de bús- queda del algoritmo. Al correr el algoritmo en MATLAB, se obtuvieron los resultados que se presentan en el Cuadro 2. Estos resultados describen el costo mínimo encontrado en un intervalo establecido. También se presentan datos relevantes, como tiempo computacional y el número de iteraciones necesarias para el resultado �nal. Función Iteraciones Tiempo (s) Costo (x, y) Rastrigin 100 0.801 0.2475 Rosenbrock 12 0.790 0.0466 Ackley 19 1.015 0.0354 Booth 100 1.049 0.4649 Cuadro 2: Resultados de optimización de funciones costo, primer caso Adicional, en la siguiente Figura 27 se muestran en conjunto las soluciones (costo) en función de las generaciones (iteraciones) realizadas por el algoritmo. Estos grá�cos demues- tran cómo evoluciona el valor hasta el más óptimo con el paso de las generaciones. Se detiene 36 cuando alcanza una tolerancia del 15% o en todo caso, cuando este llega a su número máximo de iteraciones. (a) Función costo de Rastrigin (b) Función costo de Rosenbrock (c) Función costo de Ackley. (d) Función costo de Booth Figura 27: Funciones de costo vs. generaciones, primer caso La Figura 27, muestra la evolución del algoritmo conforme ocurren las generaciones. Se evidencia una pronta convergencia hacia el valor �nal estimado. Dado que el porcentaje mutación es un valor grande, se tiene un espacio de búsqueda más alto. En [2] se nos men- ciona que no son los resultados más óptimos y que estos son preliminares para una primera aplicación. Sin embargo, la estructura algorítmica demostró funcionar para el problema de optimización, independientemente de sus parámetros de funcionamiento. Por lo que esta validación permitió, más adelante, adaptar el algoritmo a otros problemas. 7.1.2. Resultados de segundo escenario para optimización de función de costo Para el segundo escenario, se realizó la validación de las funciones con los siguientes parámetros: probabilidad de cruce 80%, probabilidad de mutación 15%, número de indivi- duos 100 por población y la longitud de cada individuo de 20 bits (10 en x y 10 en y). Este escenario se hace con un bajo porcentaje de mutación para reducir la capacidad de búsqueda del algoritmo y comparar con el de la sección anterior. Al correr el algoritmo en MATLAB, 37 se obtuvieron los resultados que se presentan en el Cuadro 3. Estos resultados describen el costo mínimo encontrado en un intervalo establecido. Al igual que en el caso anterior, se presentan el conjunto de grá�cos de costo, Figura 28. Función Iteraciones Tiempo (s) Costo (x, y) Rastrigin 75 0.496 0.0445 Rosenbrock 33 0.347 0.0333 Ackley 57 0.586 0.0354 Booth 16 0.521 0.0300 Cuadro 3: Resultados de optimización de funciones costo, segundo caso (a) Función costo de Rastrigin (b) Función costo de Rosenbrock (c) Función costo de Ackley (d) Función costo de Booth Figura 28: Funciones de costo vs. generaciones, segundo caso Estos resultados nos muestran una convergencia más rápida. Tenemos cierta varianza con el caso anterior, sin embargo, esto se debe a varios factores. El factor principal es que reducimos el espacio de búsqueda aleatoria (mutación). Esto puede ser de bene�cio en ciertas ocasiones, debido a que para la función de Rastrigin y Booth, se ajustó mejor y tuvo una convergencia mas rápida. Como se mencionó anteriormente, fueron resultados preliminares para la aplicación que se le dio en PSO. En este caso, se esta satisfecho con el hecho de su funcionalidad para adaptarlo a las aplicaciones descritas en los objetivos. 38 Con base en la validación de estos antecedentes, podemos inferir que la estructura men- cionada para un algoritmo evolutivo, algoritmo genético, es válida para generar soluciones como problema de búsqueda u optimización. Se desarrolló, en la siguiente sección, una im- plementación par un problema de optimización más simple y comprensible que replique esta estructura. 7.2. Algoritmos genéticos para optimización de máximos y mí- nimos en funciones algebraicas multivariable En este caso particular, se validó el algoritmo genético enfocado a otro tipo de pro- blema. Este problema se trata de buscar máximos y mínimos en intervalos cerrados, para funciones de tipo f(x, y) en diferentes escenarios. El objetivo es traducir la estructura mos- trada en el Algoritmo 6.1 a problemas de optimización más entendibles, así poder hacer la re-interpretación a conveniencia. Para hacerlo, se utilizaron las funciones propuestas en el marco teórico, sección 6.2, siendo super�cies con puntos máximos y mínimos a simple vista. El proceso para el AG, es el mismo que en la sección anterior, al igual que el diagrama de �ujo mostrado en la Figura 25. En esta caso cambia la interpretación del problema, las funciones y los parámetros de simulación. La condición de detención se basa en el criterio mencionado en el marco teórico: terminar cuando no haya cambios en la población. Por lo tanto, la población será interpretada como los posibles puntos máximos o mínimos de la super�cie f(x, y), generando posibles puntos en x y y. El algoritmo debe encargarse de buscar la solución más apropiada en el intervalo cerrado xb < x < xb y ya < y < yb. Las tres principales funciones a evaluar son una hipérbola, un paraboloide y la campana de Gauss. Estas fueron evaluadas en 3 escenarios distintos con el objetivo de notar cambios radicales importantes. Dado que todas las funciones están centradas en el origen, se utilizaran los siguientes parámetros en común para los 3 casos, mostrados en el Cuadro 4. Función (x,y) Dominio x Rango y Longitud Hipérbola [-5, 5] [-5, 5] 20 Paraboloide [-5, 5] [-5, 5] 20 C. de Gauss [-5, 5] [-5, 5] 20 Cuadro 4: Parámetros de simulación para optimizar super�cies Se eligieron los intervalos dado por conveniencia, debido a que grá�camente es más fácil identi�car los máximos o mínimos. Esto será una ventaja para comparar las pruebas del algoritmo. La resolución o longitud de 20 bits es para tener 10 bits en x y 10 bits en y. Se recomienda usarlo en esa longitud para que no tome mas tiempo computacional. Replicando la representación y codi�cación binaria para el cromosoma, en este caso, se muestra en la forma de la Figura 29. 39 Figura 29: Representación y codi�cación del cromosoma para problema de optimización de super�cies En cuanto a la decodi�cación de las variables de este problema, se utilizó la Ecuación (9). Considerando los límites de dominio y rango para las variables a traducir como cotas superiores e inferiores en la ecuación. Esta función tomará la solución generada en valor decimal para convertirla a un valor entero �otante interpretable. 7.2.1. Primer escenario para optimización de super�cies En este caso, se variaron unicamente la probabilidad de cruce, mutación y las iteracio- nes. Como se mencionó, se usó Pc = 90% y Pm = 1%, las iteraciones incrementan para evidenciar cuanto se tarda en converger. El usar un porcentaje de mutación bajo reducirá la probabilidad de búsqueda aleatoria, para comprobar el comportamiento limitado a una re- gión. Los resultados obtenidos en este escenario se muestran en el Cuadro 5. En este cuadro se muestra el valor encontrado luego de variar las iteraciones, comparado con el valor real. f(x, y) Iteraciones Tiempo (s) Valor AG Valor real 4 0.7523 72.170 Hipérbola e. 30 1.9241 85.000 85.0 100 5.0325 85.000 4 0.4145 4.8985 Paraboloide 30 2.0577 5.0000 5.0 100 6.578 5.0000 4 0.2544 0.7911 C. Gauss 30 2.3354 0.7946 0.795 100 7.7072 0.7950 Cuadro 5: Resultados de optimización de super�cies, primer caso 40 (a) Solución en hipérbola vs. generaciones (b) Valor real en función hipérbola Figura 30: Solución hipérbola f(x, y) vs. generaciones, primer caso (a) Solución en paraboloide vs. generaciones (b) Valor real en función paraboloide Figura 31: Solución paraboloide f(x, y) vs. generaciones, primer caso (a) Solución en Gauss vs. generaciones (b) Valor real en función Gauss Figura 32: Solución Gauss f(x, y) vs. generaciones, primer caso Los resultados en las Figuras 30, 31 y 32, explican grá�camente como evoluciona la solución f(x, y) conforme pasan las generaciones. Se puede apreciar que al cabo de 10 gene- 41 raciones ya converge al valor real para la mayoría de casos. Por lo que se conoce que existe e�ciencia en cuanto a convergencia y dio a conocer la característica más importante para los criterios en los parámetros. Ahora considerando lo mencionado, se agregó una condición de detención favorable para reducir el tiempo computacional en la siguiente sección. 7.2.2. Segundo escenario para optimización de super�cies En este caso se realizó una modi�cación en la condición de detención, que ocurrirá cuando no exista variación en la solución, conforme pasen las generaciones. También se mantuvo el valor de porcentaje de cruza y mutación de Pc = 90% y Pm = 1%. El propósito de realizar este cambio es reducir el tiempo computacional, debido a que en el primer caso se mostró una pronta convergencia. Los resultados de este caso se muestran el Cuadro 6, donde se indican las iteraciones tomadas hasta que se cumpla la condición de detención y la solución �nal. f(x,y) Iteraciones Tiempo (s) Valor AG Valor real. Hipérbola e. 17 0.9293 85.0 85.0 Paraboloide 16 0.7695 4.9902 5.00 C. Gauss 14 1.2821 0.7946 0.795 Cuadro 6: Resultados de optimización de super�cies, segundo caso Figura 33: Solución de hipérbola vs. generaciones, segundo caso 42 Figura 34: Solución de paraboloide vs. generaciones, segundo caso Figura 35: Solución de Gauss vs. generaciones, segundo caso En las Figuras 33, 34 y 35 se muestran los resultados de la ejecución del algoritmo. Se aprecia cómo la función f(x, y) evoluciona mientras ocurren las generaciones, pero a diferencia del caso anterior, esta se detiene cuando no hay variación. De esta forma, pudimos con�rmar que el tiempo de ejecución se reduce y comparado al valor real la diferencia es insigni�cante. Por último, realizó otra validación incrementando la probabilidad de búsqueda autónoma del algoritmo, es decir, variando la mutación. 7.2.3. Tercer escenario para optimización de super�cies En este tercer caso, se planteó validar el funcionamiento ahora con un parámetro de búsqueda aleatoria más alto. De esta forma se comparó el comportamiento que brindó la perspectiva de funcionamiento que se aplicó más adelante. Por lo tanto, en este caso se varía el Pc a 75% y el Pm a 5%. Al igual que el caso anterior, se con�guró el mismo criterio en detención. Los resultados de esta implementación se muestran en el Cuadro 7. 43 f(x,y) Iteraciones Tiempo (s) Valor AG Valor real. Hipérbola e. 24 2.2216 85.0 85.0 Paraboloide 32 2.7656 4.9980 5.00 C. Gauss 36 3.0902 0.7946 0.7950 Cuadro 7: Resultados de optimización de super�cies, tercer caso Figura 36: Solución de hipérbola vs. generaciones, tercer caso Figura 37: Solución de paraboloide vs. generaciones, tercer caso 44 Figura 38: Solución de Gauss vs. generaciones, tercer caso Los resultados de este tercer escenario demostraron que la exploración y explotación se hace más presente. Esto es debido a que el aumento de mutación hace que las soluciones cambien descartando algunos aspectos de los padres. El método de mutación aveces es bueno, como también puede ser malo. En este caso particular, aumenta el número de iteraciones realizadas como consecuencia. En las Figuras 36, 37 y 38, se ve una dispersión más frecuente en las soluciones conforme pasan las generaciones. Esto nos brinda una noción sobre los criterios a utilizar en las aplicaciones más especi�cas que se demostraron en los siguientes capítulos. Este capítulo se centró especí�camente en la evaluación de los AG aplicando la estructura investigada. Esta demostró ser funcional y aplicable a problemas básicos y generales de optimización. También evidenció las limitantes y criterios a tomar en cuenta para la selección de parámetros. 45 CAPÍTULO 8 Algoritmo genético para plani�cación de trayectorias En este capítulo se muestra la metodología implementada para adaptar el AG en plani- �cación de trayectorias en un escenario 2D. También se detalla el procedimiento realizado para implementar la estructura, desarrollar los entornos de búsqueda y los parámetros uti- lizados. En este caso se toma un robot móvil ideal como una masa puntual y los obstáculos como �guras circulares. Los resultados obtenidos en esta sección tienen como objetivo ga- rantizar el funcionamiento para búsqueda trayectorias libres de obstáculos. No buscamos las más optimas, pero sí las mejores soluciones que pueda encontrar el algoritmo. 8.1. Metodología Utilizando la estructura de un AG descrita en el marco teórico, se basó el procedimiento de esta implementación como lo sugiere [5]. Como primer punto, se tomó el supuesto de utilizar un robot móvil con movimiento de control lineal y angular. Este se asume como una masa puntual que recorrerá el camino, dentro del mapa de n× n unidades de longitud arbitrarias, que generará el AG. El camino consiste de un una cadena (x0, y0),... (xk, yk) con k cantidad de puntos intermedios representando el cromosoma. Los valores de punto �otante dentro del punto pk(xk, yk) constituyen un gen, dentro del plano 2D. La codi�cación de los obstáculos se puede apreciar mejor en la representación vectorial de ejemplo en 10. Esta es la representación del cromosoma como un vector trayectoria T de coordenadas < x, y > para n = 5 puntos intermedios. 46 T =  10.5 10.5 25.0 30.0 48.5 41.5 55.5 60.0 70.0 70.0  (10) Para esta implementación no deben decodi�carse las variables de solución. Esto se debe a que los datos ya son interpretables para el tipo de problema, en todo caso la decodi�cación vendría siendo la extracción de un elemento independiente del vector. Es decir, extraerlo y operarlo como un escalar en el paso del cruce aritmético, que se presentó en el Marco teórico 6, respecto al cruce aritmético. El entorno donde se evaluó el algoritmo consta de una cantidad de obstáculos dentro del mapa 2D. Los obstáculos variaron conforme a los casos que se presentan más adelante. También se consideró un radio de obstáculos. Además, se de�nieron los puntos de inicio y los puntos de �nal. Estos no deben coincidir inicialmente con el área del obstáculo y deben estar dentro de las coordenadas del mapa. Utilizando la estructura descrita en el Código 6.1, se realizó el planteamiento y adapta- ción del algoritmo al problema de optimización. En este caso se tiene un vector con puntos intermedios los cuales actuarán como el cromosoma o solución a optimizar. Se evaluará la aptitud de los cromosomas candidatos por medio de cual sea el camino con menor distan- cia. El mejor cromosoma será el padre que heredará las mejores características hasta que se cumpla el criterio de optimización. Por lo tanto, el AG funcionará de la manera descrita en el diagrama de �ujo en la Figura 39. 47 Figura 39: Diagrama de �ujo para AG en plani�cación de trayectorias 2D Una aclaración importante, es que la mutación ocurre de manera aleatoria para este caso. Es un parámetro independiente. Para todos los casos que se desarrollaron en las siguientes secciones se aplica el mismo proceso descrito en la �gura anterior. Unicamente se variaron los obstáculos, número de puntos, tamaño de la población, número de generaciones a crear, 48 dimensiones del mapa y radio de los obstáculos. 8.1.1. Selección con base en la aptitud En esta implementación se utilizó la función de aptitud descrita por la Ecuación 6. La ecuación usa la norma euclidiana como medida de calidad. De esta forma se obtiene el mejor valor de aptitud que representa el crit