Метаэвристические методы генерации парных тестовых наборов

Размещено на http://www.allbest.ru/

Международная компания-разработчик программного обеспечения «Yucca Digital»

Метаэвристические методы генерации парных тестовых наборов

Шевчук В.И. инженер по контролю качества программного обеспечения

г. Витебск, Беларусь

Аннотация

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

Ключевые слова: тестирование, программное обеспечение, парное тестирование, тестовый набор, метаэвристический метод, преимущества и недостатки. метаэвристический генерация имитированный отжиг

Abstract

Shauchuk V.I. software quality assurance engineer, International software company «Yucca Digital» (Vitebsk, Belarus)

METAHEURISTIC METHODS FOR GENERATING PAIRWISE TEST SUITES

The purpose of this article is to review metaheuristic methods for generating pairwise test suites. These methods are based on optimization or search techniques that mimic natural phenomena or intelligent behavior, such as evolutionary algorithms, swarm intelligence, simulated annealing. The article describes the principles of using these methods, as well as the advantages and disadvantages of their application in generating pairwise test suites.

Keywords: testing, software, pairwise testing, test suite, metaheuristic method, advantages and disadvantages.

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

Один из наиболее распространенных метаэвристических методов основан на эволюционных алгоритмах (ЭА) [1, с. 25]. ЭА вдохновлены биологическим процессом эволюции, когда популяция особей подвергается отбору, скрещиванию и мутациям для получения новых особей, которые более приспособлены к окружающей среде. Данные алгоритмы могут использоваться для генерации парных наборов тестов путем кодирования каждого тестового примера как отдельного (например, вектора входных значений) и определения функции пригодности, которая измеряет попарный охват или качество набора тестов. В следующей таблице (табл. 1) показан процесс оценки для четырех параметров (A, B, C, D), каждый из которых имеет три возможных значения (1,2,3).

Таблица 1. Генерация парных наборов на основе эволюционного алгоритма

Преимущество использования ЭА заключается в том, что они могут генерировать разнообразные и высококачественные наборы парных тестов с помощью гибкого и адаптивного алгоритма. Недостатком является то, что для получения хорошего решения может потребоваться большое количество итераций или оценок, и они могут не гарантировать оптимальность или полноту решения. Для повышения производительности или надежности алгоритма были предложены некоторые усовершенствования или вариации ЭА, такие как генетические алгоритмы [2, с. 437], генетическое программирование, дифференциальная эволюция и коэволюция [3, с. 1].

Другой метаэвристический метод основан на роевом интеллекте (РИ) [4, с. 187]. РИ вдохновлен коллективным поведением социальных животных или насекомых, таких как муравьи, пчелы, птицы или рыбы, которые сотрудничают и общаются друг с другом для достижения общей цели или решения сложной проблемы. РИ можно использовать для генерации парных наборов тестов путем моделирования каждого тестового примера как агента (например, муравья или пчелы), который перемещается и взаимодействует с другими агентами в пространстве поиска (например, графике или матрице) в соответствии с некоторыми правилами или стратегиями. В следующей таблице (табл. 2) показан процесс РИ для четырех параметров (A,B,C,D), каждый из которых имеет три возможных значения (1,2,3).

Таблица 2. Генерация парных наборов на основе роевого интеллекта

Преимущество использования РИ заключается в том, что они могут генерировать разнообразные и высококачественные наборы парных тестов с помощью простого и надежного алгоритма. Недостатком использования РИ является то, что они могут зависеть от некоторых параметров или факторов, влияющих на поведение или производительность агентов, таких как количество агентов, начальные позиции агентов, механизмы коммуникации или сотрудничества и т.д. Поэтому были предложены некоторые улучшения или вариации РИ для оптимизации или адаптации этих параметров или факторов, такие как оптимизация колонии муравьев, оптимизация колонии пчел, оптимизация роя частиц и оптимизация искусственного косяка рыб [5, с. 369].

Третий метаэвристический метод основан на моделировании отжига (МО) [6, с. 671]. Написано, вдохновленное физическим процессом отжига, когда твердый материал нагревается, а затем медленно охлаждается до низкоэнергетического состояния или минимальной конфигурации. МО можно использовать для генерации парных наборов тестов, начиная с исходного набора тестов (например, сгенерированного случайным образом) и затем итеративно улучшая его, внося небольшие изменения (например, меняя местами или заменяя значения) с некоторой вероятностью, которая зависит от параметра температуры. В следующей таблице (табл. 3) показан процесс МО для четырех параметров (A, B, C, D), каждый из которых имеет три возможных значения (1,2,3).

Таблица 3. Генерация парных наборов на основе моделирования отжига

Преимущество использования заключается в том, что он может генерировать почти оптимальные или достаточно хорошие наборы попарных тестов с гибким и адаптивным алгоритмом. Недостатком использования МО является то, что может потребоваться тщательная настройка или калибровка температурного параметра и графика охлаждения, чтобы избежать застревания в локальных оптимумах или преждевременного сближения. Для повышения производительности и надежности алгоритма были предложены некоторые улучшения или вариации МО, такие как адаптивный МО, параллельный МО и квантовый МО [7, с. 31].

Список литературы

1. Eiben A.E. and Smith J.E. Introduction to Evolutionary Computing // Springer- Verlag Berlin Heidelberg. 2003. С. 25-46

2. Cohen D.M., Dalal S.R., Fredman M.L. and Patton G.C. The AETG system: an approach to testing based on combinatorial design // IEEE Transactions on Software Engineering № 23(7). 1997. С. 437-444.

3. Potter M.A. and De Jong K.A. Cooperative coevolution: an architecture for evolving coadapted subcomponents // Evolutionary Computation № 8(1). 2000. С. 129.

4. Kennedy J. and Eberhart R. Swarm Intelligence // Morgan Kaufmann Publishers. 2001.

5. Ahmed B.S. A dynamic parameter tuning of particle swarm optimization for software testing // International Journal of Bio-Inspired Computation 5(6). 2013. С.369-384.

6. Kirkpatrick S., Gelatt C.D. Jr. and Vecchi M.P. Optimization by simulated annealing // Science № 220. 1983. С. 671-680

7. Alba E. and Troya J.M. A survey of parallel distributed genetic algorithms // Complexity. 2002. С. 31-52

Размещено на Allbest.ru