@misc{13286,
  author = {Shuai Wang and Shaukat Ali and Tao Yue and Marius Liaaen},
  title = {UPMOA: An Improved Search Algorithm to Support User- Preference Multi-Objective Optimization},
  abstract = {Multi-objective search algorithms (e.g., non- dominated sorting genetic algorithm II (NSGA-II)) have been applied extensively to solve various multi-objective optimization problems in software engineering such as problems in testing. However, existing multi-objective algorithms usually treat all the objectives with equivalent priorities and do not provide a mechanism to reflect various user preferences when guiding search. The need to have such a mechanism was observed in one of our industrial projects on applying search algorithms for test optimization of a product line of Videoconferencing Systems (VCSs) called Saturn, where user preferences must be incorporated into optimization objectives, based on domain knowledge of test engineers for VCS testing. To address this, we propose an extension to the most commonly-used multi-objective search algorithm NSGA-II, which has shown promising results with user preferences. We name the extension as User-Preference Multi-Objective Optimization Algorithm (UPMOA), which includes a user preference indicator p and is based on existing weight assignment strategies. We empirically evaluated UPMOA with two industrial problems focusing on optimizing the test execution system for Saturn in Cisco. To assess the performance and scalability of UPMOA, inspired by the two industrial problems, in total we created 64000 artificial problems with 128 different sets of user preferences. The evaluation includes two aspects: 1) Three weight assignment strategies together with UPMOA were empirically evaluated to identify a best weight assignment strategy for p. Results show that the Uniformly Distributed Weights (UDW) strategy can assist UPMOA in achieving the best performance; 2) UPMOA was compared with three representative multi-objective search algorithms (including NSGA-II) and results show that UPMOA significantly outperformed the others and has the ability to solve problems with a wide range of complexity.},
  year = {2015},
  journal = {The 26th IEEE International Symposium on Software Reliability Engineering (ISSRE). Gaithersburg, USA, November 2-5.},
  pages = {393-404},
}