A comparison of meta-heuristic search for interactive software design

Simons, C. L.; Smith, J. E.; Simons, Chris; Smith, Jim

Abstract

Advances in processing capacity, coupled with the desire to tackle problems where a human subjective judgment plays an important role in determining the value of a proposed solution, has led to a dramatic rise in the number of applications of Interactive Artificial Intelligence. Of particular note is the coupling of meta-heuristic search engines with user-provided evaluation and rating of solutions, usually in the form of Interactive Evolutionary Algorithms (IEAs). These have a well-documented history of successes, but arguably the preponderance of IEAs stems from this history, rather than as a conscious design choice of meta-heuristic based on the characteristics of the problem at hand. This paper sets out to examine the basis for that assumption, taking as a case study the domain of interactive software design. We consider a range of factors that should affect the design choice including ease of use, scalability, and of course, performance, i.e. that ability to generate good solutions within the limited number of evaluations available in interactive work before humans lose focus. We then evaluate three methods, namely greedy local search, an evolutionary algorithm and ant colony optimization (ACO), with a variety of representations for candidate solutions. Results show that after suitable parameter tuning, ACO is highly effective within interactive search and out-performs evolutionary algorithms with respect to increasing numbers of attributes and methods in the software design problem. However, when larger numbers of classes are present in the software design, an evolutionary algorithm using a naïve grouping integer-based representation appears more scalable. © 2013 Springer-Verlag Berlin Heidelberg.

Citation

Smith, J. E., Simons, C. L., Simons, C., & Smith, J. (2013). A comparison of meta-heuristic search for interactive software design. Soft Computing, 17(11), 2147-2162. https://doi.org/10.1007/s00500-013-1039-1

• Journal Article Type: Article
• Publication Date: Nov 1, 2013
• Deposit Date: Jun 17, 2014
• Journal: Soft Computing
• Print ISSN: 1432-7643
• Electronic ISSN: 1433-7479
• Publisher: Springer (part of Springer Nature)
• Peer Reviewed: Peer Reviewed
• Volume: 17
• Issue: 11
• Pages: 2147-2162
• DOI: https://doi.org/10.1007/s00500-013-1039-1
• Keywords: interactive search, meta-heuristics, software design, search-based software engineering
• Public URL: https://uwe-repository.worktribe.com/output/940355
• Publisher URL: http://dx.doi.org/10.1007/s00500-013-1039-1
• Related Public URLs: http://link.springer.com/article/10.1007%2Fs00500-013-1039-1; http://arxiv.org/abs/1211.3371
• Additional Information: Additional Information : The original publication is available at www.springerlink.com