Разработка программного обеспечения на основе поиска
Разработка программного обеспечения на основе поиска ( 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 Evolutionary Program Repair исправило 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] ЭвоСюит , [28] и Coverage — инструмент измерения покрытия кода для Python. [29]
Методы и приемы [ править ]
Доступен ряд методов и техник, в том числе:
- Профилирование [30] с помощью инструментов , чтобы контролировать определенные части программы во время ее выполнения.
- Получение абстрактного синтаксического дерева , связанного с программой, которое можно автоматически изучить, чтобы получить представление о его структуре.
- Приложения разделения программ , имеющие отношение к SBSE, включают обслуживание программного обеспечения , оптимизацию и анализ программ .
- Покрытие кода позволяет измерить, какая часть кода выполняется с заданным набором входных данных.
- Статический анализ программы
Принятие промышленности [ править ]
Будучи относительно новой областью исследований, SBSE еще не получила широкого признания в отрасли.
Успешное применение SBSE в отрасли можно найти в основном при тестировании программного обеспечения, где возможность автоматически генерировать случайные тестовые входные данные для выявления ошибок в больших масштабах привлекательна для компаний. В 2017 году Facebook приобрел стартап программного обеспечения Majicke Limited, который разработал Sapienz, приложение для поиска ошибок на основе поиска. [31]
В других сценариях применения инженеры-программисты могут неохотно использовать инструменты, над которыми у них мало контроля или которые создают решения, непохожие на те, которые создают люди. [32] В контексте использования SBSE для исправления или улучшения программ разработчики должны быть уверены, что любая автоматически созданная модификация не приведет к неожиданному поведению, выходящему за рамки требований системы и среды тестирования. Учитывая, что полностью автоматизированное программирование еще не создано, желательным свойством таких модификаций было бы то, что они должны быть легко понятны людям для поддержки операций по техническому обслуживанию. [33]
Другая проблема заключается в том, что SBSE может сделать разработчика программного обеспечения ненужным. Сторонники утверждают, что целью SBSE является улучшение отношений между инженером и программой. [34]
См. также [ править ]
Ссылки [ править ]
- ^ Харман, Марк (2010). «Почему анализ и манипулирование исходным кодом всегда будут важны». 10-я рабочая конференция IEEE по анализу и манипулированию исходным кодом (SCAM 2010) . 10-я рабочая конференция IEEE по анализу и манипулированию исходным кодом (SCAM 2010). стр. 7–19. дои : 10.1109/SCAM.2010.28 .
- ^ Харман, Марк; Джон А. Кларк (2004). «Метрики тоже являются фитнес-функциями». Материалы 10-го Международного симпозиума по метрикам программного обеспечения, 2004 г. 10-й Международный симпозиум по метрикам программного обеспечения, 2004 г., стр. 58–69. дои : 10.1109/METRIC.2004.1357891 .
- ^ Кларк, Джон А.; Доладо, Хосе Хавьер; Харман, Марк; Хиеронс, Роберт М.; Джонс, Брайан Ф.; Люмкин, М.; Митчелл, Брайан С.; Манкоридис, Спирос; Рис, К.; Ропер, Марк; Шепперд, Мартин Дж. (2003). «Реформулирование разработки программного обеспечения как проблема поиска». Труды IEE — Программное обеспечение . 150 (3): 161–175. CiteSeerX 10.1.1.144.3059 . дои : 10.1049/ip-sen:20030559 . ISSN 1462-5970 .
- ^ Миллер, Уэбб; Спунер, Дэвид Л. (1976). «Автоматическое создание тестовых данных с плавающей запятой». Транзакции IEEE по разработке программного обеспечения . СЭ-2 (3): 223–226. дои : 10.1109/TSE.1976.233818 . ISSN 0098-5589 . S2CID 18875300 .
- ^ С. Ксантакис, К. Эллис, К. Скурлас, А. Ле Галл, С. Кацикас и К. Карапулиос, «Применение генетических алгоритмов для тестирования программного обеспечения», в материалах 5-й Международной конференции по программной инженерии и ее приложениям , Тулуза, Франция, 1992, стр. 625–636.
- ^ Харман, Марк; Джонс, Брайан Ф. (15 декабря 2001 г.). «Поисковая разработка программного обеспечения». Информационные и программные технологии . 43 (14): 833–839. CiteSeerX 10.1.1.143.9716 . дои : 10.1016/S0950-5849(01)00189-6 . ISSN 0950-5849 .
- ^ Харман, Марк; Мансури, С. Афшин; Чжан, Юаньюань (1 ноября 2012 г.). «Разработка программного обеспечения на основе поиска: тенденции, методы и приложения» . Обзоры вычислительной техники ACM . 45 (1): 1–61. дои : 10.1145/2379776.2379787 . S2CID 207198163 .
- ^ Макминн, Фил (2004). «Генерация тестовых данных программного обеспечения на основе поиска: опрос». Тестирование, проверка и надежность программного обеспечения . 14 (2): 105–156. CiteSeerX 10.1.1.122.33 . дои : 10.1002/stvr.294 . ISSN 1099-1689 . S2CID 17408871 .
- ^ Грир, Дес; Руэ, Гюнтер (15 марта 2004 г.). «Планирование выпуска программного обеспечения: эволюционный и итеративный подход». Информационные и программные технологии . 46 (4): 243–253. CiteSeerX 10.1.1.195.321 . дои : 10.1016/j.infsof.2003.07.002 . ISSN 0950-5849 . S2CID 710923 .
- ^ Коларес, Фелипе; Соуза, Джерффесон; Кармо, Рафаэль; Падуя, Клариндо; Матеус, Джеральдо Р. (2009). «Новый подход к планированию выпуска программного обеспечения». XXIII Бразильский симпозиум по разработке программного обеспечения, 2009 г. SBES '09 . XXIII Бразильский симпозиум по разработке программного обеспечения, 2009 г. SBES '09. стр. 207–215. дои : 10.1109/SBES.2009.23 .
- ^ Кларк, Джон А.; Джейкоб, Джереми Л. (15 декабря 2001 г.). «Протоколы тоже программы: метаэвристический поиск протоколов безопасности». Информационные и программные технологии . 43 (14): 891–904. CiteSeerX 10.1.1.102.6016 . дои : 10.1016/S0950-5849(01)00195-1 . ISSN 0950-5849 .
- ^ Райха, Оути (1 ноября 2010 г.). «Опрос по разработке программного обеспечения на основе поиска» (PDF) . Обзор компьютерных наук . 4 (4): 203–249. CiteSeerX 10.1.1.188.9036 . дои : 10.1016/j.cosrev.2010.06.001 . ISSN 1574-0137 .
- ^ Мариани, Тайна; Верджилио, Сильвия Регина (1 марта 2017 г.). «Систематический обзор рефакторинга на основе поиска». Информационные и программные технологии . 83 : 14–34. дои : 10.1016/j.infsof.2016.11.009 . ISSN 0950-5849 .
- ^ Альба, Энрике; Чикано, Дж. Франциско (1 июня 2007 г.). «Управление программными проектами с помощью GA». Информационные науки . 177 (11): 2380–2401. дои : 10.1016/j.ins.2006.12.020 . hdl : 10630/8145 . ISSN 0020-0255 .
- ^ Антониоль, Джулиано; Ди Пента, Массимилиано; Харман, Марк (2005). «Методы поиска, применяемые для оптимизации планирования проекта масштабного технического обслуживания». Материалы 21-й Международной конференции IEEE по сопровождению программного обеспечения, 2005 г. ICSM'05 . Материалы 21-й Международной конференции IEEE по сопровождению программного обеспечения, 2005 г. ICSM'05. стр. 240–249. CiteSeerX 10.1.1.63.8069 . дои : 10.1109/ICSM.2005.79 .
- ^ Чжан, Юаньюань (февраль 2010 г.). Выбор и оптимизация требований на основе многоцелевого поиска (доктор философии). Стрэнд, Лондон, Великобритания: Лондонский университет.
- ^ Ю. Чжан, М. Харман и С.Л. Лим, « Оптимизация управления взаимодействием требований на основе поиска », факультет компьютерных наук, Университетский колледж Лондона, исследовательская записка RN/11/12, 2011 г.
- ^ Ли, Лингбо; Харман, Марк; Летье, Эммануэль; Чжан, Юаньюань (2014). «Надежная проблема следующего выпуска». Материалы ежегодной конференции по генетическим и эволюционным вычислениям 2014 года . Гекко '14. стр. 1247–1254. дои : 10.1145/2576768.2598334 . ISBN 9781450326629 . S2CID 8423690 .
- ^ Ли, Л.; Харман, М.; Ву, Ф.; Чжан, Ю. (2017). «Значение точного анализа при выборе требований» (PDF) . Транзакции IEEE по разработке программного обеспечения . 43 (6): 580–596. дои : 10.1109/TSE.2016.2615100 . ISSN 0098-5589 . S2CID 8398275 .
- ^ Ле Гу, Клэр; Дьюи-Фогт, Майкл; Форрест, Стефани; Веймер, Уэстли (2012). «Систематическое исследование автоматического восстановления программ: исправление 55 из 105 ошибок по 8 долларов каждая». 2012 34-я Международная конференция по программной инженерии (ICSE) . 2012 34-я Международная конференция по программной инженерии (ICSE). стр. 3–13. дои : 10.1109/ICSE.2012.6227211 .
- ^ Аркури, Андреа; Яо, Синь (2008). «Новый коэволюционный подход к автоматическому исправлению ошибок программного обеспечения». Конгресс IEEE по эволюционным вычислениям, 2008 г. CEC 2008. (Всемирный конгресс IEEE по вычислительному интеллекту) . Конгресс IEEE по эволюционным вычислениям, 2008. CEC 2008. (Всемирный конгресс IEEE по вычислительному интеллекту). стр. 162–168. CiteSeerX 10.1.1.159.7991 . дои : 10.1109/CEC.2008.4630793 .
- ^ Харман, Марк; Цзя, Юэ; Чжан, Юаньюань (апрель 2015 г.). «Достижения, открытые проблемы и проблемы тестирования программного обеспечения на основе поиска». 2015 8-я Международная конференция IEEE по тестированию, верификации и валидации программного обеспечения (ICST) . Грац, Австрия: IEEE. стр. 1–12. CiteSeerX 10.1.1.686.7418 . дои : 10.1109/ICST.2015.7102580 . ISBN 978-1-4799-7125-1 . S2CID 15272060 .
- ^ Мемети, Суэйб; Планана, Сабри; Бинотто, Алесио; Колодзей, Джоанна; Брандич, Ивона (2018). «Использование метаэвристики и машинного обучения для оптимизации программного обеспечения параллельных вычислительных систем: систематический обзор литературы». Вычисление . 101 (8): 893–936. arXiv : 1801.09444 . Бибкод : 2018arXiv180109444M . дои : 10.1007/s00607-018-0614-9 . S2CID 13868111 .
- ^ Лэнгдон, Уильям Б.; Харман, Марк. «Оптимизация существующего программного обеспечения с помощью генетического программирования» (PDF) . Транзакции IEEE в эволюционных вычислениях .
- ^ Басиос, Михаил; Ли, Лингбо; Ву, Фан; Кантан, Лесли; Барр, Эрл Т. (9 сентября 2017 г.). «Оптимизация дарвиновских структур данных в Google Guava». Разработка программного обеспечения на основе поиска (PDF) . Конспекты лекций по информатике. Том. 10452. стр. 161–167. дои : 10.1007/978-3-319-66299-2_14 . ISBN 978-3-319-66298-5 .
- ^ Минку, Леандро Л.; Судхолт, Дирк; Яо, Синь (2012). «Эволюционные алгоритмы решения задачи планирования проекта: анализ времени выполнения и улучшенный дизайн». Материалы четырнадцатой международной конференции по генетическим и эволюционным вычислениям . ГЕККО '12. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 1221–1228. дои : 10.1145/2330163.2330332 . ISBN 978-1-4503-1177-9 .
- ^ Мэйо, М.; Спейси, С. (2013). «Прогнозирование неудачных регрессионных тестов с использованием показателей динамического анализа производительности, выбранных генетическим алгоритмом» (PDF) . Разработка программного обеспечения на основе поиска . Конспекты лекций по информатике. Том. 8084. стр. 158–171. дои : 10.1007/978-3-642-39742-4_13 . hdl : 10289/7763 . ISBN 978-3-642-39741-7 .
- ^ "Дом" . evosuite.org .
- ^ другие, Нед Батчелдер и 100, покрытие: измерение покрытия кода для Python , получено 14 марта 2018 г.
{{citation}}: CS1 maint: числовые имена: список авторов ( ссылка ) - ^ «Профилировщики с открытым исходным кодом в Java» .
- ^ «Sapienz: стремление Facebook автоматизировать тестирование программного обеспечения» . ВенчурБит . 30 декабря 2018 года . Проверено 29 сентября 2020 г.
- ^ Джонс, Дерек (18 октября 2013 г.). «Программирование с использованием генетических алгоритмов: разве не этим уже занимаются люди ;-)» . Форма кода . Проверено 31 октября 2013 г.
- ^ Ле Гу, Клэр; Форрест, Стефани; Веймер, Уэстли (1 сентября 2013 г.). «Текущие проблемы автоматического восстановления программного обеспечения». Журнал качества программного обеспечения . 21 (3): 421–443. CiteSeerX 10.1.1.371.5784 . дои : 10.1007/s11219-013-9208-0 . ISSN 1573-1367 . S2CID 16435531 .
- ^ Саймонс, Кристофер Л. (май 2013 г.). Куда (отсутствуют) инженеры-программисты из SBSE? . Первый международный семинар по совмещению моделирования с разработкой программного обеспечения на основе поиска, Первый международный семинар по совмещению моделирования с разработкой программного обеспечения на основе поиска. Сан-Франциско, США: IEEE Press. стр. 49–50 . Проверено 31 октября 2013 г.
Внешние ссылки [ править ]
- Репозиторий публикаций на СБФБ
- Метаэвристика и программная инженерия
- Репозиторий инфраструктуры программных артефактов
- Международная конференция по программной инженерии
- Генетические и эволюционные вычисления (GECCO)
- Страница Академии Google, посвященная разработке программного обеспечения на основе поиска
