Is "Sampling" better than "Evolution" for search-based SE?
with Jianfeng Chen, NC State
Increasingly, SE researchers use search-based optimization techniques to solve SE problems with multiple conflicting objectives. These techniques often apply CPU-intensive evolutionary algorithms to explore generations of mutations to a population of candidate solutions.
An alternative approach, proposed recently in our lab, is to start with a very large population and sample down to just the better solutions-- but instead of evaluating all members of that population, just sample and evaluate pairs of distant examples. In studies with a dozen software engineering models, this sampling approach was found to be competitive with standard evolutionary algorithms (measured in terms of hypervolume and spread). Further, as software engineering models get more complex (e.g. heavily-constrained models of operating system kernels) this sampling approach performed as good or better than state-of-the-art evolutionary methods (and did so using up to 333 times fewer evaluations).
That is, sampling algorithms is preferred to evolution algorithms for multi-objective optimization in software engineering domains where (a) evaluating candidates is very expensive and/or slow or (b) models are large and heavily-constrained.Read More