Preliminary Evaluation of SWAY in Permutation Decision Space via a Novel Euclidean Embedding

Abstract

The cost of a fitness evaluation is often cited as one of the weaknesses of Search-Based Software Engineering - to obtain a single final solution, a meta-heuristic search algorithm has to evaluate the fitness of many interim solutions. Recently, a sampling-based approach called SWAY has been introduced as a new baseline that can compete with state-of-the-art search algorithms with significantly fewer fitness evaluations. However, SWAY has been introduced and evaluated only in numeric and Boolean decision spaces. This paper extends SWAY to permutation decision space. We start by presenting the theoretical formulation of the permutation decision space and the distance function required by SWAY, and subsequently present a proof-of-concept study of Test Case Prioritisation (TCP) problem using our permutative SWAY. The results show that our embedding works well for permutative decision spaces, producing results that are comparable to those generated by the additional greedy algorithm, one of the most widely used algorithms for TCP.

Junghyun Lee

PhD Student

PhD student at GSAI, KAIST, jointly advised by Prof. Se-Young Yun and Prof. Chulhee Yun. Interested in mathematical and theoretical AI, where I am interested in explaining the recent success of machine/deep learning algorithms and designing mathematically well-grounded algorithms for various scenarios.