Hispanopedia Wiki
Articulo de referencia

Ingeniería de software basada en búsqueda

La ingeniería de software basada en búsqueda ( SBSE ) aplica técnicas de búsqueda metaheurística , como algoritmos genéticos , recocido simulado y búsqueda tabú, a problemas de ...

Hispanopedia WikiContenido en espanolLectura gratuita

La ingeniería de software basada en búsqueda ( SBSE ) aplica técnicas de búsqueda metaheurística , como algoritmos genéticos , recocido simulado y búsqueda tabú, a problemas de ingeniería de software . Muchas actividades en ingeniería de software pueden plantearse como problemas de optimización . Las técnicas de optimización de la investigación operativa, como la programación lineal o la programación dinámica, suelen ser poco prácticas para problemas de ingeniería de software a gran escala debido a su complejidad computacional o a sus supuestos sobre la estructura del problema. Investigadores y profesionales utilizan técnicas de búsqueda metaheurística , que imponen pocos supuestos sobre la estructura del problema, para encontrar soluciones casi óptimas o "suficientemente buenas". [ 1 ]

Los problemas SBSE se pueden dividir en dos tipos:

  • problemas de optimización de caja negra, por ejemplo, la asignación de personas a tareas (un problema típico de optimización combinatoria ).
  • problemas de caja blanca donde se deben considerar las operaciones sobre el código fuente. [ 2 ]

Definición

SBSE convierte un problema de ingeniería de software en un problema de búsqueda computacional que puede abordarse con una metaheurística . Esto implica definir un espacio de búsqueda, o el conjunto de posibles soluciones. Este espacio suele ser demasiado grande para explorarlo exhaustivamente, lo que sugiere un enfoque metaheurístico . Luego se utiliza una métrica [ 3 ] (también llamada función de aptitud, función de costo, función objetivo o medida de calidad) para medir la calidad de las soluciones potenciales. Muchos problemas de ingeniería de software pueden reformularse como un problema de búsqueda computacional. [ 4 ]

En cambio, el término " aplicación basada en búsqueda " se refiere al uso de tecnología de motores de búsqueda , en lugar de técnicas de búsqueda, en otra aplicación industrial.

Breve historia

Uno de los primeros intentos de aplicar la optimización a un problema de ingeniería de software fue reportado por Webb Miller y David Spooner en 1976 en el área de pruebas de software . [ 5 ] En 1992, S. Xanthakis y sus colegas aplicaron una técnica de búsqueda a un problema de ingeniería de software por primera vez. [ 6 ] El término SBSE fue utilizado por primera vez en 2001 por Harman y Jones. [ 7 ] La comunidad de investigación creció hasta incluir a más de 800 autores para 2013, abarcando aproximadamente 270 instituciones en 40 países. [ 8 ]

Áreas de aplicación

La ingeniería de software basada en búsqueda es aplicable a casi todas las fases del proceso de desarrollo de software . Las pruebas de software han sido una de las principales aplicaciones. [ 9 ] Las técnicas de búsqueda se han aplicado a otras actividades de ingeniería de software , por ejemplo, análisis de requisitos , [ 10 ] [ 11 ] diseño , [ 12 ] [ 13 ] refactorización , [ 14 ] desarrollo , [ 15 ] y mantenimiento . [ 16 ]

Ingeniería de requisitos

La ingeniería de requisitos es el proceso mediante el cual se determinan y gestionan las necesidades de los usuarios y el entorno de un software. Se han utilizado métodos basados ​​en búsqueda para la selección y optimización de requisitos con el objetivo de encontrar el mejor subconjunto posible de requisitos que se ajuste a las solicitudes de los usuarios, teniendo en cuenta restricciones como recursos limitados e interdependencias entre requisitos. Este problema se aborda a menudo como un problema de toma de decisiones multicriterio y, generalmente, implica presentar al responsable de la toma de decisiones un conjunto de compromisos adecuados entre el coste y la satisfacción del usuario, así como el riesgo de los requisitos. [ 17 ] [ 18 ] [ 19 ] [ 20 ]

Depuración y mantenimiento

Identificar un error de software (o un código defectuoso ) y luego depurarlo (o refactorizarlo ) es en gran medida una tarea manual y laboriosa, aunque el proceso cuenta con el apoyo de herramientas. Uno de los objetivos de SBSE es identificar y corregir errores automáticamente (por ejemplo, mediante pruebas de mutación ).

La programación genética , una técnica de inspiración biológica que implica la evolución de programas mediante el uso de cruce y mutación, se ha utilizado para buscar correcciones en programas modificando unas pocas líneas de código fuente. El software GenProg Evolutionary Program Repair reparó 55 de 105 errores por aproximadamente 8 dólares cada uno en una prueba. [ 21 ]

El análisis empírico de patrones de corrección de errores extraídos de repositorios de software se ha utilizado para caracterizar matemáticamente el espacio de búsqueda de la reparación automatizada de programas. [ 22 ] Este espacio de búsqueda se operacionalizó posteriormente en Cardumen, un enfoque de reparación que sintetiza parches a partir de plantillas de código extraídas automáticamente del código fuente de la aplicación que se está reparando. [ 23 ]

La coevolución adopta una metáfora de "depredador y presa" en la que un conjunto de programas y un conjunto de pruebas unitarias evolucionan juntos y se influyen mutuamente. [ 24 ]

Pruebas

La ingeniería de software basada en búsqueda se ha aplicado a las pruebas de software, incluyendo la generación automática de casos de prueba (datos de prueba), la minimización de casos de prueba y la priorización de casos de prueba. [ 25 ] Las pruebas de regresión también han recibido cierta atención.

Optimización de software

El uso de SBSE en la optimización de programas , o la modificación de un software para hacerlo más eficiente en términos de velocidad y uso de recursos, ha sido objeto de investigaciones exitosas. [ 26 ] En un caso, un programa de 50 000 líneas fue mejorado genéticamente, lo que resultó en un programa 70 veces más rápido en promedio. [ 27 ] Un trabajo reciente de Basios et al. muestra que al optimizar la estructura de datos, Google Guava encontró una mejora del 9 % en el tiempo de ejecución, una mejora del 13 % en el consumo de memoria y una mejora del 4 % en el uso de CPU por separado. [ 28 ]

Gestión de proyectos

Varias decisiones que normalmente toma un director de proyecto pueden realizarse automáticamente, por ejemplo, la planificación del proyecto. [ 29 ]

Herramientas

Las herramientas disponibles para SBSE incluyen OpenPAT, [ 30 ] EvoSuite , [ 31 ] y Coverage , una herramienta de medición de cobertura de código para Python. [ 32 ]

Métodos y técnicas

Existen diversos métodos y técnicas disponibles, entre los que se incluyen:

Aceptación de la industria

Al ser un área de investigación relativamente nueva, la SBSE aún no goza de una amplia aceptación en la industria.

Las aplicaciones exitosas de SBSE en la industria se encuentran principalmente en las pruebas de software, donde la capacidad de generar automáticamente entradas de prueba aleatorias para descubrir errores a gran escala resulta atractiva para las empresas. En 2017, Facebook adquirió la startup de software Majicke Limited, que desarrolló Sapienz, una aplicación de búsqueda de errores. [ 34 ]

En otros escenarios de aplicación, los ingenieros de software pueden mostrarse reacios a adoptar herramientas sobre las que tienen poco control o que generan soluciones distintas a las que producen los humanos. [ 35 ] En el contexto del uso de SBSE para corregir o mejorar programas, los desarrolladores deben tener la certeza de que cualquier modificación producida automáticamente no genere un comportamiento inesperado fuera del alcance de los requisitos del sistema y del entorno de pruebas. Dado que aún no se ha logrado la programación totalmente automatizada, una propiedad deseable de dichas modificaciones sería que fueran fácilmente comprensibles para los humanos a fin de facilitar las actividades de mantenimiento. [ 36 ]

Otra preocupación es que SBSE podría volver redundante al ingeniero de software. Los defensores afirman que la motivación de SBSE es mejorar la relación entre el ingeniero y el programa. [ 37 ]

Véase también

Referencias

  1. ↑ Mohan, M.; Greer, D. (1 de agosto de 2019). "Uso de un enfoque multiobjetivo para investigar la refactorización automatizada" . Information and Software Technology . 112 : 83–101 . doi : 10.1016/j.infsof.2019.04.009 . ISSN 0950-5849 . 
  2. ↑ Harman, Mark (2010). "Por qué el análisis y la manipulación del código fuente siempre serán importantes". 10.ª Conferencia de Trabajo IEEE sobre Análisis y Manipulación del Código Fuente (SCAM 2010) . 10.ª Conferencia de Trabajo IEEE sobre Análisis y Manipulación del Código Fuente (SCAM 2010). págs. 7–19 . doi : 10.1109/SCAM.2010.28 . 
  3. ↑ Harman, Mark; John A. Clark (2004). "Las métricas también son funciones de aptitud". Actas del 10.º Simposio Internacional sobre Métricas de Software, 2004. 10.º Simposio Internacional sobre Métricas de Software, 2004. págs. 58–69 . doi : 10.1109/METRIC.2004.1357891 . 
  4. ↑ Clark, John A.; Dolado, José Javier; Harman, Mark; Hierons, Robert M.; Jones, Bryan F.; Lumkin, M.; Mitchell, Brian S.; Mancoridis, Spiros; Rees, K.; Roper, Marc; Shepperd, Martin J. (2003). "Reformulating software engineering as a search problem". IEE Proceedings - Software . 150 (3): 161– 175. CiteSeerX 10.1.1.144.3059 . doi : 10.1049/ip-sen:20030559 (inactivo 12 de julio de 2025). ISSN 1462-5970 .  {{cite journal}}: CS1 maint: DOI inactivo desde julio de 2025 ( enlace )
  5. ↑ Miller, Webb; Spooner, David L. (1976). "Generación automática de datos de prueba de punto flotante". IEEE Transactions on Software Engineering . SE-2 (3): 223– 226. Bibcode : 1976ITSEn...2..223M . doi : 10.1109/TSE.1976.233818 . ISSN 0098-5589 . S2CID 18875300 .  
  6. ↑ S. Xanthakis, C. Ellis, C. Skourlas, A. Le Gall, S. Katsikas y K. Karapoulios, "Aplicación de algoritmos genéticos a las pruebas de software", en Actas de la 5.ª Conferencia Internacional sobre Ingeniería de Software y sus Aplicaciones , Toulouse, Francia, 1992, págs. 625-636
  7. ↑ Harman, Mark; Jones, Bryan F. (15 de diciembre de 2001). "Ingeniería de software basada en búsqueda". Information and Software Technology . 43 (14): 833– 839. CiteSeerX 10.1.1.143.9716 . doi : 10.1016/S0950-5849(01)00189-6 . ISSN 0950-5849 .  
  8. ↑ Harman, Mark; Mansouri, S. Afshin; Zhang, Yuanyuan (1 de noviembre de 2012). "Ingeniería de software basada en búsqueda: tendencias, técnicas y aplicaciones" . ACM Computing Surveys . 45 (1): 1– 61. doi : 10.1145/2379776.2379787 . S2CID 207198163 . 
  9. ↑ McMinn, Phil (2004). "Generación de datos de prueba de software basada en búsqueda: una revisión". Software Testing, Verification and Reliability . 14 (2): 105– 156. CiteSeerX 10.1.1.122.33 . doi : 10.1002/stvr.294 . ISSN 1099-1689 . S2CID 17408871 .   
  10. ↑ Greer, Des; Ruhe, Guenther (15 de marzo de 2004). "Planificación de lanzamientos de software: un enfoque evolutivo e iterativo". Information and Software Technology . 46 (4): 243– 253. CiteSeerX 10.1.1.195.321 . doi : 10.1016/j.infsof.2003.07.002 . ISSN 0950-5849 . S2CID 710923 .   
  11. ↑ Colares, Felipe; Souza, Jerffeson; Carmen, Rafael; Padua, Clarindo; Mateus, Geraldo R. (2009). "Un nuevo enfoque para la planificación del lanzamiento de software". XXIII Simposio Brasileño de Ingeniería de Software, 2009. SBES '09 . XXIII Simposio Brasileño de Ingeniería de Software, 2009. SBES '09. págs. 207–215 . doi : 10.1109/SBES.2009.23 . 
  12. ↑ Clark, John A.; Jacob, Jeremy L. (15 de diciembre de 2001). "Los protocolos también son programas: la búsqueda metaheurística de protocolos de seguridad". Information and Software Technology . 43 (14): 891– 904. CiteSeerX 10.1.1.102.6016 . doi : 10.1016/S0950-5849(01)00195-1 . ISSN 0950-5849 .  
  13. ↑ Räihä, Outi (1 de noviembre de 2010). "Un estudio sobre el diseño de software basado en búsquedas" (PDF) . Computer Science Review . 4 (4): 203– 249. CiteSeerX 10.1.1.188.9036 . doi : 10.1016/j.cosrev.2010.06.001 . ISSN 1574-0137 .  
  14. ↑ Mariani, Thainá; Vergilio, Silvia Regina (1 de marzo de 2017). "Una revisión sistemática sobre la refactorización basada en búsquedas". Information and Software Technology . 83 : 14–34 . doi : 10.1016/j.infsof.2016.11.009 . ISSN 0950-5849 . 
  15. ↑ Alba, Enrique; Chicano, J. Francisco (1 de junio de 2007). "Gestión de proyectos de software con GA". Information Sciences . 177 (11): 2380– 2401. doi : 10.1016/j.ins.2006.12.020 . hdl : 10630/8145 . ISSN 0020-0255 . 
  16. ↑ Antoniol, Giuliano; Di Penta, Massimiliano ; Harman, Mark (2005). "Técnicas basadas en búsqueda aplicadas a la optimización de la planificación de proyectos para un proyecto de mantenimiento masivo". Actas de la 21.ª Conferencia Internacional IEEE sobre Mantenimiento de Software, 2005. ICSM'05 . Actas de la 21.ª Conferencia Internacional IEEE sobre Mantenimiento de Software, 2005. ICSM'05. págs. 240–249 . CiteSeerX 10.1.1.63.8069 . doi : 10.1109/ICSM.2005.79 .  
  17. ↑ Zhang, Yuanyuan (febrero de 2010). Selección y optimización de requisitos mediante búsqueda multiobjetivo (tesis doctoral). Strand, Londres, Reino Unido: Universidad de Londres.
  18. ↑ Y. Zhang y M. Harman y S. L. Lim, " Optimización basada en búsqueda de la gestión de la interacción de requisitos ," Departamento de Ciencias de la Computación, University College London, Nota de investigación RN/11/12, 2011.
  19. ↑ Li, Lingbo; Harman, Mark; Letier, Emmanuel; Zhang, Yuanyuan (2014). "Problema robusto de la próxima versión". Actas de la Conferencia Anual de 2014 sobre Computación Genética y Evolutiva . Gecco '14. págs. 1247–1254 . doi : 10.1145/2576768.2598334 . ISBN  9781450326629. S2CID 8423690 . 
  20. ↑ Li, L.; Harman, M.; Wu, F.; Zhang, Y. (2017). "El valor del análisis exacto en la selección de requisitos" (PDF) . IEEE Transactions on Software Engineering . 43 (6): 580– 596. Bibcode : 2017ITSEn..43..580L . doi : 10.1109/TSE.2016.2615100 . ISSN 0098-5589 . S2CID 8398275 .  
  21. ↑ Le Goues, Claire ; Dewey-Vogt, Michael; Forrest, Stephanie; Weimer, Westley (2012). "Un estudio sistemático de la reparación automatizada de programas: corrección de 55 de 105 errores por 8 dólares cada uno". 34.ª Conferencia Internacional de Ingeniería de Software (ICSE) de 2012. 34.ª Conferencia Internacional de Ingeniería de Software (ICSE) de 2012. pp. 3–13 . doi : 10.1109/ICSE.2012.6227211 . 
  22. ↑ Martínez, Matías; Monperrus, Martín (2015). "Extracción de modelos de reparación de software para el razonamiento en el espacio de búsqueda de la corrección automatizada de programas". Ingeniería de Software Empírica . 20 (1): 176– 205. arXiv : 1311.3414 . doi : 10.1007/s10664-013-9282-8 .
  23. ↑ Martínez, Matías; Monperrus, Martín (2018). "Espacio de búsqueda de reparación ultragrande con plantillas extraídas automáticamente: el modo Cardumen de Astor". Ingeniería de software basada en búsqueda : 65–86 . arXiv : 1712.03854 . doi : 10.1007/978-3-319-99241-9_3 .
  24. ↑ Arcuri, Andrea; Yao, Xin (2008). "Un nuevo enfoque coevolutivo para la corrección automática de errores de software". Congreso IEEE sobre Computación Evolutiva, 2008. CEC 2008. (Congreso Mundial IEEE sobre Inteligencia Computacional) . Congreso IEEE sobre Computación Evolutiva, 2008. CEC 2008. (Congreso Mundial IEEE sobre Inteligencia Computacional). págs. 162–168 . CiteSeerX 10.1.1.159.7991 . doi : 10.1109/CEC.2008.4630793 .  
  25. ↑ Harman, Mark; Jia, Yue; Zhang, Yuanyuan (abril de 2015). «Logros, problemas abiertos y desafíos para las pruebas de software basadas en búsqueda». 2015 IEEE 8.ª Conferencia Internacional sobre Pruebas, Verificación y Validación de Software (ICST) . Graz, Austria: IEEE. págs. 1-12 . CiteSeerX 10.1.1.686.7418 . doi : 10.1109/ICST.2015.7102580 . ISBN   978-1-4799-7125-1. S2CID 15272060 . 
  26. ↑ Memeti, Suejb; Pllana, Sabri; Binotto, Alecio; Kolodziej, Joanna; Brandic, Ivona (2018). "Uso de metaheurísticas y aprendizaje automático para la optimización de software de sistemas de computación paralela: una revisión sistemática de la literatura". Computing . 101 (8): 893– 936. arXiv : 1801.09444 . Bibcode : 2018arXiv180109444M . doi : 10.1007/s00607-018-0614-9 . S2CID 13868111 . 
  27. ↑ Langdon, William B.; Harman, Mark. "Optimización de software existente con programación genética" (PDF) . IEEE Transactions on Evolutionary Computation .
  28. ↑ Basios, Michail; Li, Lingbo; Wu, Fan; Kanthan, Leslie; Barr, Earl T. (9 de septiembre de 2017). "Optimización de estructuras de datos darwinianas en Google Guava". Ingeniería de software basada en búsqueda (PDF) . Notas de clase en ciencias de la computación. Vol. 10452. págs. 161–167 . doi : 10.1007/978-3-319-66299-2_14 . ISBN   978-3-319-66298-5.
  29. ↑ Minku, Leandro L.; Sudholt, Dirk; Yao, Xin (2012). «Algoritmos evolutivos para el problema de la programación de proyectos: análisis del tiempo de ejecución y diseño mejorado». Actas de la decimocuarta conferencia internacional sobre computación genética y evolutiva . GECCO '12. Nueva York, NY, EE. UU.: ACM. págs. 1221–1228 . doi : 10.1145/2330163.2330332 . ISBN  978-1-4503-1177-9.
  30. ↑ Mayo, M.; Spacey, S. (2013). "Predicción de fallos en pruebas de regresión mediante métricas de análisis de rendimiento dinámico seleccionadas por algoritmos genéticos" (PDF) . Ingeniería de software basada en búsqueda . Notas de clase en informática. Vol. 8084. págs. 158–171 . doi : 10.1007/978-3-642-39742-4_13 . hdl : 10289/7763 . ISBN   978-3-642-39741-7.
  31. ↑ "Inicio" . evosuite.org .
  32. ↑ otros, Ned Batchelder y 100, cobertura: medición de la cobertura de código para Python , archivado del original el 28 de julio de 2020 , recuperado el 14 de marzo de 2018{{citation}}: CS1 maint: nombres numéricos: lista de autores ( enlace )
  33. ↑ "Perfiladores de código abierto en Java" .
  34. ↑ "Sapienz: El impulso de Facebook para automatizar las pruebas de software" . VentureBeat . 30 de diciembre de 2018. Consultado el 29 de septiembre de 2020 .
  35. ↑ Jones, Derek (18 de octubre de 2013). "Programación mediante algoritmos genéticos: ¿no es eso lo que ya hacemos los humanos ;-)" . The Shape of Code . Consultado el 31 de octubre de 2013 . 
  36. ↑ Le Goues, Claire ; Forrest, Stephanie; Weimer, Westley (1 de septiembre de 2013). "Desafíos actuales en la reparación automática de software". Software Quality Journal . 21 (3): 421– 443. CiteSeerX 10.1.1.371.5784 . doi : 10.1007/s11219-013-9208-0 . ISSN 1573-1367 . S2CID 16435531 .   
  37. ↑ Simons, Christopher L. (mayo de 2013). ¿Hacia dónde se dirigen los ingenieros de software en SBSE? Primer Taller Internacional sobre la Combinación de Modelado con Ingeniería de Software Basada en Búsqueda. San Francisco, EE. UU.: IEEE Press. págs. 49–50 . Recuperado el 31 de octubre de 2013 . 
  • Repositorio de publicaciones sobre SBSE archivado el 2 de mayo de 2012 en Wayback Machine.
  • Metaheurísticas e ingeniería de software. Archivado el 23 de septiembre de 2011 en Wayback Machine.
  • Repositorio de infraestructura de artefactos de software
  • Conferencia Internacional sobre Ingeniería de Software
  • Computación Genética y Evolutiva (GECCO)
  • Página de Google Scholar sobre ingeniería de software basada en búsquedas