SEBASE: Software Engineering By Automated SEarch
Lead Research Organisation:
University of Birmingham
Department Name: School of Computer Science
Abstract
Current software engineering practice is a human-led search for solutions which meet needs and constraints under limited resources. Often there will be conflict, both between and within functional and non-functional criteria. Naturally, like other engineers, we search for a near optimal solution. As systems get bigger, more distributed, more dynamic and more critical, this labour-intensive search will hit fundamental limits. We will not be able to continue to develop, operate and maintain systems in the traditional way, without automating or partly automating the search for near optimal solutions. Automated search based solutions have a track record of success in other engineering disciplines, characterised by a large number of potential solutions, where there are many complex, competing and conflicting constraints and where construction of a perfect solution is either impossible or impractical. The SEMINAL network demonstrated that these techniques provide robust, cost-effective and high quality solutions for several problems in software engineering. Successes to date can be seen as strong pointers to search having great potential to serve as an overarching solution paradigm. The SEBASE project aims to provide a new approach to the way in which software engineering is understood and practised. It will move software engineering problems from human-based search to machine-based search. As a result, human effort will move up the abstraction chain, to focus on guiding the automated search, rather than performing it. This project will address key issues in software engineering, including scalability, robustness, reliability and stability. It will also study theoretical foundations of search algorithms and apply the insights gained to develop more effective and efficient search algorithms for large and complex software engineering problems. Such insights will have a major impact on the search algorithm community as well as the software engineering community.
People |
ORCID iD |
Xin Yao (Principal Investigator) |
Publications
Chen T
(2012)
A large population size can be unhelpful in evolutionary algorithms
in Theoretical Computer Science
Wang Z
(2010)
A Memetic Algorithm for Multi-Level Redundancy Allocation
in IEEE Transactions on Reliability
Sudholt D
(2013)
A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms
in IEEE Transactions on Evolutionary Computation
Sudholt D
(2011)
A Simple Ant Colony Optimizer for Stochastic Shortest Path Problems
in Algorithmica
Lässig J
(2011)
Algorithms and Computation
Lässig J
(2014)
Analysis of speedups in parallel evolutionary algorithms and ( 1 + ? ) EAs for combinatorial optimization
in Theoretical Computer Science
Kötzing T
(2010)
Ant colony optimization and the minimum cut problem
Description | This project investigated the intersection between search algorithms and software engineering. A number of significant discoveries were made. Firstly, a deeper understanding of randomised search algorithms, especially evolutionary algorithms, was gained. We have analysed computational time complexity of different evolutionary algorithms on different problems, including hard problems in software engineering, e.g., the unique input-output sequence problem in finite state machine testing and branch coverage in software testing. We now know much in depth (theoretically) the interactions among different algorithmic components, e.g., mutation and selection. Secondly, we pioneered the idea of using genetic programming and co-evolution for automatic software bug-fixing. This work were followed up by many researchers, including leading software engineering research groups in the USA, who have developed the idea and approach further, Thirdly, we pioneered novel use of multi-objective evolutionary algorithms in software engineering, from software module clustering to testing resource allocation, and to software development effort estimation. Fourthly, we have developed a number of new search algorithms, which have been shown experimentally to outperform other algorithms. |
Exploitation Route | At present, we are collaborating with a company, who is interested in potential uses of some of the techniques we developed for its e-commerce work. This collaboration is being funded through EPSRC Follow-on fund's Knowledge Transfer Scheme (KTS), managed by the University of Birmingham. 25% of the project funding was provided by the company. We have been publicising our research findings through various presentations to non-academic audience. We have also communicated our work with people from companies. |
Sectors | Digital/Communication/Information Technologies (including Software) |
URL | http://www.cercia.ac.uk/projects/research/SEBASE/ |
Description | DaimlerChrysler |
Organisation | Daimler AG |
Country | Germany |
Sector | Private |
PI Contribution | Publications addressing the research challenges from the partner. |
Collaborator Contribution | Providing some research challenges. |
Impact | The outputs are in the form of publications. |
Start Year | 2006 |
Description | IBM |
Organisation | IBM |
Country | United States |
Sector | Private |
Start Year | 2004 |
Description | Motorola |
Organisation | Motorola Ltd |
Country | United Kingdom |
Sector | Private |
PI Contribution | Publications that addressed some of the research challenges posed by the partner. |
Collaborator Contribution | Provided some research challenges to our research. |
Impact | The outputs are in the form of publications. |
Start Year | 2006 |