Разработка программного обеспечения на основе поиска
Применение методов метаэвристического поиска в программной инженерии

Поисковая программная инженерия ( SBSE ) применяет метаэвристические методы поиска, такие как генетические алгоритмы , имитация отжига и табу-поиск, к проблемам программной инженерии . Многие виды деятельности в программной инженерии можно сформулировать как задачи оптимизации . Методы оптимизации исследования операций, такие как линейное программирование или динамическое программирование, часто непрактичны для крупномасштабных задач программной инженерии из-за их вычислительной сложности или их предположений о структуре проблемы. Исследователи и практики используют метаэвристические методы поиска, которые накладывают небольшие предположения на структуру проблемы, чтобы найти почти оптимальные или «достаточно хорошие» решения. [1]

Проблемы SBSE можно разделить на два типа:

  • задачи оптимизации «черного ящика», например, распределение людей по задачам (типичная задача комбинаторной оптимизации ).
  • проблемы «белого ящика», где необходимо учитывать операции с исходным кодом. [2]

Определение

SBSE преобразует проблему программной инженерии в проблему вычислительного поиска, которую можно решить с помощью метаэвристики . Это включает определение пространства поиска или набора возможных решений. Это пространство, как правило, слишком велико для исчерпывающего исследования, что предполагает метаэвристический подход. Метрика [3] (также называемая функцией пригодности, функцией стоимости, целевой функцией или мерой качества) затем используется для измерения качества потенциальных решений. Многие проблемы программной инженерии можно переформулировать как проблему вычислительного поиска. [4]

Термин « приложение на основе поиска », напротив, относится к использованию поисковой технологии, а не методов поиска, в другом промышленном приложении.

Краткая история

Одна из самых ранних попыток применить оптимизацию к проблеме программной инженерии была описана Уэббом Миллером и Дэвидом Спунером в 1976 году в области тестирования программного обеспечения . [5] В 1992 году С. Ксантакис и его коллеги впервые применили метод поиска к проблеме программной инженерии . [6] Термин SBSE был впервые использован в 2001 году Харманом и Джонсом. [7] К 2013 году исследовательское сообщество выросло и включало более 800 авторов, охватывая примерно 270 учреждений в 40 странах. [8]

Области применения

Поисковая программная инженерия применима почти ко всем этапам процесса разработки программного обеспечения . Тестирование программного обеспечения является одним из основных приложений. [9] Методы поиска применяются к другим видам программной инженерии , например, анализу требований , [10] [11] проектированию , [12] [13] рефакторингу , [14] разработке , [15] и обслуживанию . [16]

Требования к проектированию

Инженерия требований — это процесс, посредством которого определяются и управляются потребности пользователей и среды программного обеспечения. Методы поиска использовались для выбора и оптимизации требований с целью нахождения наилучшего возможного подмножества требований, которое соответствует запросам пользователей в условиях ограничений, таких как ограниченные ресурсы и взаимозависимости между требованиями. Эта проблема часто рассматривается как проблема принятия решений по нескольким критериям и, как правило, включает предоставление лицу, принимающему решения, набора хороших компромиссов между стоимостью и удовлетворенностью пользователя, а также риском требований. [17] [18] [19] [20]

Отладка и обслуживание

Выявление ошибки в программном обеспечении (или запаха кода ) и последующая отладка (или рефакторинг ) программного обеспечения в значительной степени является ручным и трудоемким занятием, хотя этот процесс поддерживается инструментами. Одной из целей SBSE является автоматическое выявление и исправление ошибок (например, с помощью мутационного тестирования ).

Генетическое программирование , биологически вдохновленная техника, которая включает в себя развитие программ посредством использования кроссинговера и мутации, использовалось для поиска исправлений программ путем изменения нескольких строк исходного кода. Программное обеспечение GenProg Evolutionary Program Repair исправило 55 из 105 ошибок примерно за 8 долларов за один тест. [21]

Коэволюция принимает метафору «хищник и жертва» , в которой набор программ и набор модульных тестов развиваются вместе и влияют друг на друга. [22]

Тестирование

Поисковая программная инженерия применялась к тестированию программного обеспечения, включая автоматическую генерацию тестовых случаев (тестовых данных), минимизацию тестовых случаев и приоритизацию тестовых случаев. [23] Регрессионное тестирование также получило некоторое внимание.

Оптимизация программного обеспечения

Использование SBSE в оптимизации программ или модификации части программного обеспечения для повышения его эффективности с точки зрения скорости и использования ресурсов стало объектом успешного исследования. [24] В одном случае программа из 50 000 строк была генетически улучшена, в результате чего программа стала работать в среднем в 70 раз быстрее. [25] Недавняя работа Basios et al. показывает, что путем оптимизации структуры данных Google Guava обнаружила 9%-ное улучшение времени выполнения, 13%-ное улучшение потребления памяти и 4%-ное улучшение использования процессора по отдельности. [26]

Управление проектом

Ряд решений, которые обычно принимаются менеджером проекта, могут быть выполнены автоматически, например, планирование проекта. [27]

Инструменты

Инструменты, доступные для SBSE, включают OpenPAT, [28] EvoSuite , [29] и Coverage, инструмент измерения покрытия кода для Python. [30]

Методы и приемы

Доступен ряд методов и методик, в том числе:

Принятие в отрасли

Будучи относительно новой областью исследований, SBSE пока не получила широкого признания в отрасли.

Успешные применения SBSE в отрасли можно найти в основном в тестировании программного обеспечения, где возможность автоматически генерировать случайные тестовые входы для обнаружения ошибок в больших масштабах привлекательна для компаний. В 2017 году Facebook приобрела стартап программного обеспечения Majicke Limited, который разработал Sapienz, приложение для поиска ошибок на основе поиска. [32]

В других сценариях применения инженеры-программисты могут неохотно принимать инструменты, над которыми у них мало контроля или которые генерируют решения, которые не похожи на те, которые производят люди. [33] В контексте использования SBSE для исправления или улучшения программ разработчики должны быть уверены, что любая автоматически произведенная модификация не генерирует неожиданное поведение за пределами требований системы и среды тестирования. Учитывая, что полностью автоматизированное программирование еще не достигнуто, желательным свойством таких модификаций будет то, что они должны быть легко поняты людьми для поддержки мероприятий по обслуживанию. [34]

Еще одна проблема заключается в том, что SBSE может сделать инженера-программиста ненужным. Сторонники утверждают, что мотивация SBSE заключается в улучшении отношений между инженером и программой. [35]

Смотрите также

Ссылки

  1. ^ Мохан, М.; Грир, Д. (1 августа 2019 г.). «Использование многоцелевого подхода для исследования автоматизированного рефакторинга». Информационные и программные технологии . 112 : 83– 101. doi : 10.1016/j.infsof.2019.04.009. ISSN  0950-5849.
  2. ^ Харман, Марк (2010). «Почему анализ и обработка исходного кода всегда будут важны». 10-я рабочая конференция IEEE по анализу и обработке исходного кода (SCAM 2010) . 10-я рабочая конференция IEEE по анализу и обработке исходного кода (SCAM 2010). стр.  7–19 . doi :10.1109/SCAM.2010.28.
  3. ^ Харман, Марк; Джон А. Кларк (2004). «Метрики — это тоже функции приспособленности». Труды 10-го Международного симпозиума по метрикам программного обеспечения, 2004. 10-й Международный симпозиум по метрикам программного обеспечения, 2004. С.  58–69 . doi :10.1109/METRIC.2004.1357891.
  4. ^ Кларк, Джон А.; Доладо, Хосе Хавьер; Харман, Марк; Хиеронс, Роберт М.; Джонс, Брайан Ф.; Ламкин, М.; Митчелл, Брайан С.; Манкоридис, Спирос; Риз, К.; Ропер, Марк; Шепперд, Мартин Дж. (2003). «Переформулирование программной инженерии как проблемы поиска». Труды IEE — Программное обеспечение . 150 (3): 161– 175. CiteSeerX 10.1.1.144.3059 . doi :10.1049/ip-sen:20030559 (неактивен 7 декабря 2024 г.). ISSN  1462-5970. {{cite journal}}: CS1 maint: DOI неактивен по состоянию на декабрь 2024 г. ( ссылка )
  5. ^ Миллер, Уэбб; Спунер, Дэвид Л. (1976). «Автоматическая генерация тестовых данных с плавающей точкой». Труды IEEE по программной инженерии . SE-2 (3): 223– 226. doi :10.1109/TSE.1976.233818. ISSN  0098-5589. S2CID  18875300.
  6. ^ S. Xanthakis, C. Ellis, C. Skourlas, A. Le Gall, S. Katsikas и K. Karapoulios, «Применение генетических алгоритмов к тестированию программного обеспечения», в Трудах 5-й Международной конференции по программной инженерии и ее приложениям , Тулуза, Франция, 1992, стр. 625–636
  7. ^ Харман, Марк; Джонс, Брайан Ф. (15 декабря 2001 г.). «Программная инженерия на основе поиска». Информационные и программные технологии . 43 (14): 833– 839. CiteSeerX 10.1.1.143.9716 . doi :10.1016/S0950-5849(01)00189-6. ISSN  0950-5849. 
  8. ^ Харман, Марк; Мансури, С. Афшин; Чжан, Юаньюань (1 ноября 2012 г.). «Разработка программного обеспечения на основе поиска: тенденции, методы и приложения». ACM Computing Surveys . 45 (1): 1– 61. doi :10.1145/2379776.2379787. S2CID  207198163.
  9. ^ Макминн, Фил (2004). «Генерация данных для тестирования программного обеспечения на основе поиска: обзор». Тестирование, проверка и надежность программного обеспечения . 14 (2): 105–156 . CiteSeerX 10.1.1.122.33 . doi :10.1002/stvr.294. ISSN  1099-1689. S2CID  17408871. 
  10. ^ Грир, Дес; Руэ, Гюнтер (15 марта 2004 г.). «Планирование выпуска программного обеспечения: эволюционный и итеративный подход». Информационные и программные технологии . 46 (4): 243–253 . CiteSeerX 10.1.1.195.321 . doi :10.1016/j.infsof.2003.07.002. ISSN  0950-5849. S2CID  710923. 
  11. ^ Коларес, Фелипе; Соуза, Джерффесон; Кармо, Рафаэль; Падуя, Клариндо; Матеус, Джеральдо Р. (2009). «Новый подход к планированию выпуска программного обеспечения». XXIII Бразильский симпозиум по разработке программного обеспечения, 2009 г. SBES '09 . XXIII Бразильский симпозиум по разработке программного обеспечения, 2009 г. SBES '09. стр.  207–215 . doi :10.1109/SBES.2009.23.
  12. ^ Кларк, Джон А.; Джейкоб, Джереми Л. (15 декабря 2001 г.). «Протоколы — это тоже программы: метаэвристический поиск протоколов безопасности». Информационные и программные технологии . 43 (14): 891– 904. CiteSeerX 10.1.1.102.6016 . doi :10.1016/S0950-5849(01)00195-1. ISSN  0950-5849. 
  13. ^ Ряйха, Оути (1 ноября 2010 г.). «Обзор разработки программного обеспечения на основе поиска» (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. ^ Мариани, Тайна; Вергилио, Сильвия Регина (1 марта 2017 г.). «Систематический обзор рефакторинга на основе поиска». Информационные и программные технологии . 83 : 14– 34. doi : 10.1016/j.infsof.2016.11.009. ISSN  0950-5849.
  15. ^ Альба, Энрике; Чикано, Дж. Франциско (1 июня 2007 г.). «Управление программными проектами с помощью GAs». Информационные науки . 177 (11): 2380– 2401. doi : 10.1016/j.ins.2006.12.020. hdl : 10630/8145 . ISSN  0020-0255.
  16. ^ Антониол, Джулиано; Ди Пента, Массимилиано; Харман, Марк (2005). «Методы поиска, применяемые для оптимизации планирования проекта для масштабного проекта по обслуживанию». Труды 21-й Международной конференции IEEE по обслуживанию программного обеспечения, 2005. ICSM'05 . Труды 21-й Международной конференции IEEE по обслуживанию программного обеспечения, 2005. ICSM'05. стр.  240–249 . CiteSeerX 10.1.1.63.8069 . doi :10.1109/ICSM.2005.79. 
  17. ^ Чжан, Юаньюань (февраль 2010 г.). Выборка и оптимизация требований на основе многоцелевого поиска (PhD). Strand, Лондон, Великобритания: Лондонский университет.
  18. ^ Y. Zhang и M. Harman и S. L. Lim, «Оптимизация управления взаимодействием требований на основе поиска», Кафедра компьютерных наук, Университетский колледж Лондона, Исследовательская записка RN/11/12, 2011.
  19. ^ Ли, Линбо; Харман, Марк; Летье, Эммануэль; Чжан, Юаньюань (2014). «Проблема надежного следующего релиза». Труды Ежегодной конференции по генетическим и эволюционным вычислениям 2014 года . Gecco '14. стр.  1247– 1254. doi :10.1145/2576768.2598334. ISBN 9781450326629. S2CID  8423690.
  20. ^ Ли, Л.; Харман, М.; Ву, Ф.; Чжан, И. (2017). «Значение точного анализа при выборе требований» (PDF) . IEEE Transactions on Software Engineering . 43 (6): 580– 596. doi :10.1109/TSE.2016.2615100. ISSN  0098-5589. S2CID  8398275.
  21. ^ Le Goues, Claire; Dewey-Vogt, Michael; Forrest, Stephanie; Weimer, Westley (2012). «Систематическое исследование автоматизированного исправления программ: исправление 55 из 105 ошибок по 8 долларов за каждую». 2012 34-я Международная конференция по программной инженерии (ICSE) . 2012 34-я Международная конференция по программной инженерии (ICSE). стр.  3–13 . doi :10.1109/ICSE.2012.6227211.
  22. ^ Arcuri, Andrea; Yao, Xin (2008). «Новый коэволюционный подход к автоматическому исправлению ошибок в программном обеспечении». Конгресс IEEE по эволюционным вычислениям, 2008. CEC 2008. (Всемирный конгресс IEEE по вычислительному интеллекту) . Конгресс IEEE по эволюционным вычислениям, 2008. CEC 2008. (Всемирный конгресс IEEE по вычислительному интеллекту). стр.  162–168 . CiteSeerX 10.1.1.159.7991 . doi :10.1109/CEC.2008.4630793. 
  23. ^ Харман, Марк; Цзя, Юэ; Чжан, Юаньюань (апрель 2015 г.). «Достижения, открытые проблемы и вызовы для тестирования программного обеспечения на основе поиска». 8-я международная конференция IEEE по тестированию, верификации и валидации программного обеспечения (ICST) 2015 г. Грац, Австрия: IEEE. стр.  1– 12. CiteSeerX 10.1.1.686.7418 . doi :10.1109/ICST.2015.7102580. ISBN  978-1-4799-7125-1. S2CID  15272060.
  24. ^ Memeti, Suejb; Pllana, Sabri; Binotto, Alecio; Kolodziej, Joanna; Brandic, Ivona (2018). «Использование метаэвристик и машинного обучения для оптимизации программного обеспечения параллельных вычислительных систем: систематический обзор литературы». Computing . 101 (8): 893–936 . arXiv : 1801.09444 . Bibcode :2018arXiv180109444M. doi :10.1007/s00607-018-0614-9. S2CID  13868111.
  25. ^ Лэнгдон, Уильям Б.; Харман, Марк. «Оптимизация существующего программного обеспечения с помощью генетического программирования» (PDF) . Труды IEEE по эволюционным вычислениям .
  26. ^ Basios, Michail; Li, Lingbo; Wu, Fan; Kanthan, Leslie; Barr, Earl T. (9 сентября 2017 г.). «Оптимизация дарвиновских структур данных в Google Guava». Search Based Software Engineering (PDF) . Lecture Notes in Computer Science. Vol. 10452. pp.  161– 167. doi :10.1007/978-3-319-66299-2_14. ISBN 978-3-319-66298-5.
  27. ^ Минку, Леандро Л.; Садхолт, Дирк; Яо, Синь (2012). «Эволюционные алгоритмы для задачи планирования проекта: анализ времени выполнения и улучшенный дизайн». Труды четырнадцатой международной конференции по генетическим и эволюционным вычислениям . GECCO '12. Нью-Йорк, штат Нью-Йорк, США: ACM. стр.  1221– 1228. doi :10.1145/2330163.2330332. ISBN 978-1-4503-1177-9.
  28. ^ Mayo, M.; Spacey, S. (2013). «Предсказание сбоев регрессионного теста с использованием выбранных генетическим алгоритмом динамических метрик анализа производительности» (PDF) . Поисковая программная инженерия . Конспект лекций по информатике. Том 8084. С.  158–171. doi : 10.1007/978-3-642-39742-4_13. hdl : 10289/7763 . ISBN 978-3-642-39741-7.
  29. ^ "Главная". evosuite.org .
  30. ^ другие, Нед Батчелдер и 100, покрытие: измерение покрытия кода для Python , получено 14 марта 2018 г.{{citation}}: CS1 maint: числовые имена: список авторов ( ссылка )
  31. ^ «Профилировщики с открытым исходным кодом на Java».
  32. ^ "Sapienz: стремление Facebook автоматизировать тестирование программного обеспечения". VentureBeat . 30 декабря 2018 г. Получено 29 сентября 2020 г.
  33. ^ Джонс, Дерек (18 октября 2013 г.). «Программирование с использованием генетических алгоритмов: разве это не то, что уже делают люди ;-)». Форма кода . Получено 31 октября 2013 г.
  34. ^ Le Goues, Claire; Forrest, Stephanie; Weimer, Westley (1 сентября 2013 г.). «Текущие проблемы автоматического восстановления программного обеспечения». 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. 
  35. ^ Саймонс, Кристофер Л. (май 2013 г.). Куда (прочь) инженеры-программисты в SBSE?. Первый международный семинар по объединению моделирования с разработкой программного обеспечения на основе поиска, Первый международный семинар по объединению моделирования с разработкой программного обеспечения на основе поиска. Сан-Франциско, США: IEEE Press. стр.  49–50 . Получено 31 октября 2013 г.
  • Репозиторий публикаций по SBSE
  • Метаэвристика и программная инженерия
  • Репозиторий инфраструктуры программных артефактов
  • Международная конференция по программной инженерии
  • Генетические и эволюционные вычисления (GECCO)
  • Страница Google Scholar о поисковой разработке программного обеспечения
Взято с "https://en.wikipedia.org/w/index.php?title=Инженерия_программного_обеспечения_на_основе_поиска&oldid=1266655190"