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.
(To be filled out)
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, i.e., essentially any machine learning challenges necessitating mathematical analysis. Recently focused on statistical problems arising from RLHF, including interactive machine learning and low-dimensional structure recovery.