Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Определение [ править ]

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

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

Краткая история [ править ]

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

Области применения [ править ]

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

Разработка требований [ править ]

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

Отладка и обслуживание [ править ]

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

Генетическое программирование , метод, вдохновленный биологией, который включает развитие программ за счет использования кроссовера и мутации, использовался для поиска исправлений программ путем изменения нескольких строк исходного кода. Ремонт GenProg Эволюционная Программа программного обеспечения отремонтировано 55 из 105 ошибок приблизительно 8 $ каждый в одном тесте. [20]

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

Тестирование [ править ]

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

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

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

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

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

Инструменты [ править ]

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

Методы и приемы [ править ]

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

  • Профилирование [30] с помощью инструментовки для отслеживания определенных частей программы по мере ее выполнения.
  • Получение связанного с программой абстрактного синтаксического дерева , которое может быть автоматически исследовано для понимания ее структуры.
  • Приложения нарезки программ, относящиеся к SBSE, включают обслуживание программного обеспечения , оптимизацию и анализ программ .
  • Покрытие кода позволяет измерить, какая часть кода выполняется с заданным набором входных данных.
  • Статический анализ программы

Принятие в отрасли [ править ]

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

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

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

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

См. Также [ править ]

  • Программный анализ (информатика)
  • Динамический анализ программы
  • Генетическое улучшение

Ссылки [ править ]

  1. ^ Харман, Марк (2010). «Почему анализ исходного кода и манипуляции с ним всегда будут важны». 10-я рабочая конференция IEEE по анализу и обработке исходного кода (SCAM 2010) . 10-я рабочая конференция IEEE по анализу и обработке исходного кода (SCAM 2010). С. 7–19. DOI : 10,1109 / SCAM.2010.28 .
  2. ^ Харман, Марк; Джон А. Кларк (2004). «Метрики - тоже фитнес-функции». Труды 10 - й Международный симпозиум по разработке программного обеспечения Метрики, 2004 . 10-й Международный симпозиум по метрикам программного обеспечения, 2004 г., стр. 58–69. DOI : 10,1109 / METRIC.2004.1357891 .
  3. ^ Кларк, Джон А .; Доладо, Хосе Хавьер; Харман, Марк; Hierons, Роберт М .; Джонс, Брайан Ф .; Лумкин, М .; Митчелл, Брайан С .; Манкоридис, Спирос; Rees, K .; Ропер, Марк; Шепперд, Мартин Дж. (2003). «Переформулирование программной инженерии как поисковой задачи». IEE Proceedings - Программное обеспечение . 150 (3): 161–175. CiteSeerX 10.1.1.144.3059 . DOI : 10.1049 / IP-сен: 20030559 . ISSN 1462-5970 .  
  4. ^ Миллер, Уэбб; Спунер, Дэвид Л. (1976). «Автоматическое создание тестовых данных с плавающей запятой». IEEE Transactions по разработке программного обеспечения . SE-2 (3): 223–226. DOI : 10.1109 / TSE.1976.233818 . ISSN 0098-5589 . S2CID 18875300 .  
  5. ^ С. Ксантакис, К. Эллис, К. Скурлас, А. Ле Галл, С. Кацикас и К. Карапулиос, «Применение генетических алгоритмов для тестирования программного обеспечения», в материалах 5-й Международной конференции по разработке программного обеспечения и его приложениям , Тулуза, Франция, 1992, стр. 625–636.
  6. ^ Харман, Марк; Джонс, Брайан Ф. (15 декабря 2001 г.). «Поисковая инженерия». Информационные и программные технологии . 43 (14): 833–839. CiteSeerX 10.1.1.143.9716 . DOI : 10.1016 / S0950-5849 (01) 00189-6 . ISSN 0950-5849 .  
  7. ^ Харман, Марк; Мансури, С. Афшин; Чжан, Юаньюань (1 ноября 2012 г.). «Разработка программного обеспечения на основе поиска: тенденции, методы и приложения» . ACM Computing Surveys . 45 (1): 1–61. DOI : 10.1145 / 2379776.2379787 . S2CID 207198163 . 
  8. ^ Макминн, Фил (2004). «Генерация тестовых данных программного обеспечения на основе поиска: обзор». Тестирование, проверка и надежность программного обеспечения . 14 (2): 105–156. CiteSeerX 10.1.1.122.33 . DOI : 10.1002 / stvr.294 . ISSN 1099-1689 .  
  9. ^ Грир, Дес; Руэ, Гюнтер (15 марта 2004 г.). «Планирование выпуска программного обеспечения: эволюционный и итеративный подход». Информационные и программные технологии . 46 (4): 243–253. CiteSeerX 10.1.1.195.321 . DOI : 10.1016 / j.infsof.2003.07.002 . ISSN 0950-5849 .  
  10. ^ Коларес, Фелипе; Соуза, Джеффесон; Кармо, Рафаэль; Падуа, Клариндо; Матеус, Джеральдо Р. (2009). «Новый подход к планированию выпуска программного обеспечения». XXIII Бразильский симпозиум по разработке программного обеспечения, 2009 г. SBES '09 . XXIII Бразильский симпозиум по разработке программного обеспечения, 2009 г. SBES '09. С. 207–215. DOI : 10,1109 / SBES.2009.23 .
  11. ^ Кларк, Джон А .; Джейкоб, Джереми Л. (15 декабря 2001 г.). «Протоколы - это тоже программы: метаэвристический поиск протоколов безопасности». Информационные и программные технологии . 43 (14): 891–904. CiteSeerX 10.1.1.102.6016 . DOI : 10.1016 / S0950-5849 (01) 00195-1 . ISSN 0950-5849 .  
  12. ^ Räihä, Ути (1 ноября 2010). «Обзор разработки программного обеспечения на основе поиска» (PDF) . Обзор компьютерных наук . 4 (4): 203–249. DOI : 10.1016 / j.cosrev.2010.06.001 . ISSN 1574-0137 .  
  13. ^ Мариани, Тайна; Вергилио, Сильвия Регина (1 марта 2017 г.). «Систематический обзор рефакторинга на основе поиска». Информационные и программные технологии . 83 : 14–34. DOI : 10.1016 / j.infsof.2016.11.009 . ISSN 0950-5849 . 
  14. ^ Альба, Энрике; Чикано, Дж. Франциско (1 июня 2007 г.). «Управление программными проектами с помощью GA». Информационные науки . 177 (11): 2380–2401. DOI : 10.1016 / j.ins.2006.12.020 . ЛВП : 10630/8145 . ISSN 0020-0255 . 
  15. ^ Антониол, Джулиано; Ди Пента, Массимилиано; Харман, Марк (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 . 
  16. ↑ Чжан, Юаньюань (февраль 2010 г.). Выбор и оптимизация требований на основе многоцелевого поиска (PhD). Стрэнд, Лондон, Великобритания: Лондонский университет.
  17. ^ Ю. Чжан, М. Харман и С. Л. Лим, « Оптимизация на основе поиска для управления взаимодействием требований », Департамент компьютерных наук, Университетский колледж Лондона, Research Note RN / 11/12, 2011.
  18. ^ Ли, Лингбо; Харман, Марк; Летье, Эммануэль; Чжан, Юаньюань (2014). Проблема робастного следующего выпуска: устранение неопределенности во время оптимизации . Труды ежегодной конференции по генетическим ресурсам и эволюционные вычисления 2014 . Gecco '14. С. 1247–1254. DOI : 10.1145 / 2576768.2598334 . ISBN 9781450326629. S2CID  8423690 .
  19. ^ Li, L .; Harman, M .; Wu, F .; Чжан, Ю. (2017). «Значение точного анализа при выборе требований» (PDF) . IEEE Transactions по разработке программного обеспечения . 43 (6): 580–596. DOI : 10.1109 / TSE.2016.2615100 . ISSN 0098-5589 . S2CID 8398275 .   
  20. ^ Ле Гуэ, Клэр; Дьюи-Фогт, Майкл; Форрест, Стефани; Веймер, Уэстли (2012). «Систематическое исследование автоматического восстановления программ: исправление 55 из 105 ошибок по 8 долларов каждая». 2012 34-я Международная конференция по программной инженерии (ICSE) . 2012 34-я Международная конференция по программной инженерии (ICSE). С. 3–13. DOI : 10.1109 / ICSE.2012.6227211 .
  21. ^ Аркури, Андреа; Яо, Синь (2008). «Новый коэволюционный подход к автоматическому исправлению ошибок программного обеспечения». Конгресс IEEE по эволюционным вычислениям, 2008 г. CEC 2008 г. (Всемирный конгресс IEEE по вычислительному интеллекту) . Конгресс IEEE по эволюционным вычислениям, 2008 г. CEC 2008 г. (Всемирный конгресс IEEE по вычислительному интеллекту). С. 162–168. DOI : 10,1109 / CEC.2008.4630793 .
  22. ^ Харман, Марк; Цзя, Юэ; Чжан, Юаньюань (апрель 2015 г.). «Достижения, открытые проблемы и вызовы для тестирования программного обеспечения на основе поиска». 2015 IEEE 8-я Международная конференция по тестированию, проверке и валидации программного обеспечения (ICST) . Грац, Австрия: IEEE: 1–12. CiteSeerX 10.1.1.686.7418 . DOI : 10.1109 / ICST.2015.7102580 . ISBN  978-1-4799-7125-1. S2CID  15272060 .
  23. ^ Memeti, Suejb; Пллана, Сабри; Бинотто, Алецио; Колодзей, Иоанна; Брандич, Ивона (2018). «Использование метаэвристики и машинного обучения для оптимизации программного обеспечения параллельных вычислительных систем: систематический обзор литературы». Вычислительная техника . 101 (8): 893–936. arXiv : 1801.09444 . Bibcode : 2018arXiv180109444M . DOI : 10.1007 / s00607-018-0614-9 . S2CID 13868111 . 
  24. ^ Лэнгдон, Уильям Б .; Харман, Марк. «Оптимизация существующего программного обеспечения с помощью генетического программирования» (PDF) . IEEE Transactions по эволюционным вычислениям .
  25. ^ Басиос, Михаил; Ли, Лингбо; Ву, Фань; Кантан, Лесли; Барр, Эрл Т. (9 сентября 2017 г.). Оптимизация дарвиновских структур данных в Google Guava (PDF) . Разработка программного обеспечения на основе поиска . Конспект лекций по информатике. 10452 . С. 161–167. DOI : 10.1007 / 978-3-319-66299-2_14 . ISBN  978-3-319-66298-5.
  26. ^ Минку, Леандро Л .; Судхольт, Дирк; Яо, Синь (2012). «Эволюционные алгоритмы для задачи планирования проекта: анализ времени выполнения и улучшенный дизайн». Материалы четырнадцатой международной конференции по генетическим и эволюционным вычислениям . GECCO '12. Нью-Йорк, Нью-Йорк, США: ACM. С. 1221–1228. DOI : 10.1145 / 2330163.2330332 . ISBN 978-1-4503-1177-9.
  27. ^ Мэйо, М .; Спейси, С. (2013). Прогнозирование сбоев регрессионных тестов с помощью выбранных генетическим алгоритмом показателей динамического анализа производительности (PDF) . Материалы 5-го Международного симпозиума по поисковой инженерии программного обеспечения (SSBSE) . 8084 . С. 158–171. DOI : 10.1007 / 978-3-642-39742-4_13 .
  28. ^ ( http://www.evosuite.org/ )
  29. ^ другие, Нед Батчелдер и 100, охват: Измерение покрытия кода для Python , получено 14 марта 2018 г.
  30. ^ «Профилировщики с открытым исходным кодом на Java» .
  31. ^ «Сапиенц: толчок Facebook для автоматизации тестирования программного обеспечения» . VentureBeat . 30 декабря 2018 . Проверено 29 сентября 2020 года .
  32. ↑ Джонс, Дерек (18 октября 2013 г.). «Программирование с использованием генетических алгоритмов: разве это не то, чем люди уже занимаются ;-)» . Форма кода . Проверено 31 октября 2013 года .
  33. ^ Ле Гуэ, Клэр; Форрест, Стефани; Веймер, Уэстли (1 сентября 2013 г.). «Актуальные проблемы автоматического восстановления программного обеспечения». Журнал качества программного обеспечения . 21 (3): 421–443. CiteSeerX 10.1.1.371.5784 . DOI : 10.1007 / s11219-013-9208-0 . ISSN 1573-1367 . S2CID 16435531 .   
  34. ^ Саймонс, Кристофер Л. (май 2013 г.). Куда (подальше) программисты в SBSE? . Первый международный семинар по объединению моделирования с разработкой программного обеспечения на основе поиска, Первый международный семинар по объединению моделирования с разработкой программного обеспечения на основе поиска. Сан-Франциско, США: IEEE Press. С. 49–50 . Проверено 31 октября 2013 года .

Внешние ссылки [ править ]

  • Репозиторий публикаций на SBSE
  • Метаэвристика и программная инженерия
  • Репозиторий инфраструктуры программных артефактов
  • Международная конференция по программной инженерии
  • Генетические и эволюционные вычисления (GECCO)
  • Страница Академии Google, посвященная разработке программного обеспечения на основе поиска