HOT 20 May 2023 (Sat): 12th GI workshop (event page) at ICSE 2023

The 10th International Workshop on Genetic Improvement @ICSE 2021

Navigation: Keynote, Accepted Papers, CFP, Workshops Chairs, PC, Sponsors

Virtual Event

The workshop took place virtually on 30 May 2021, thank you everyone for attending and congratulations to the award winners!

best paper award: CRNRepair: Automated Program Repair of Chemical Reaction Networks by Ibrahim Mesecan, Michael C. Gerten, James I. Lathrop, Myra B. Cohen, and Tomas Haddad Caldas
best presentation award: Using Genetic Improvement to Retarget Quantum Software on Differing Hardware by George O’Brien and John Clark

Playlist of the workshop recordings:

Group photo:

Keynote

We are happy to announce that Stephanie Forrest (Arizona State University) will give the keynote speech in GI@ICSE 2021: Engineering and Evolving Software.
The keynote will be less a reflection of ‘where the genetic improvement field is today’ than putting the micro-level evolution we design for single programs into a larger context of software engineering practice which is inadvertently using evolution at the macro-scale. She hopes also to encourage GI practitioners to start thinking more about evolutionary search rather than focusing so much on designing better mutation operators.

Prof. Stephanie Forrest works at Arizona State University, where she directs the Biodesign Center for Biocomputation, Security and Society in the School of Computing, Informatics and Decision Sciences Engineering (CIDSE). Forrest studies the biology of computation and the computation of biology, including work on computational immunology, computer security, automated software repair, evolutionary computation, and biological modeling.

Accepted Papers

(Genetically) Improving Novelty in Procedural Story Generation
by Erik Fredericks and Byron DeVries
DOI PDF VIDEO VIDEO VIDEO VIDEO URL URL Abstract

Procedural story generation (PCG) tailors a unique narrative experience for a player and can be accomplished via multiple techniques, from matching storylets to grammar-based generation. There exists a rich opportunity for evolutionary algorithms to be applied to this domain for intelligently constructing game narratives. We describe a conceptual procedure for applying genetic improvement to a grammar-driven procedural narrative within the context of a browser-based game.

A Permutation Representation of Covering Arrays
by Ryan Dougherty and Xi Jiang
DOI VIDEO VIDEO VIDEO Abstract

Testing a large-scale system requires understanding how each of the components interact with each other, which is the subject of interaction testing. Covering arrays are a well-studied object, but traditional representations of these arrays in the context of genetic algorithms has not yielded much success. We propose a new representation of covering arrays based on a permutation of the rows considered. Preliminary results for reducing the mean-time-to-failure of these arrays are given.

Applying Automated Program Repair to Dataflow Programming Languages
by Yu Huang, Hammad Ahmad, Stephanie Forrest, and Westley Weimer
DOI VIDEO VIDEO VIDEO Abstract

Dataflow programming languages are used in a variety of settings, and defects in their programs can have serious consequences. However, prior work in automated program repair (APR) emphasizes control flow over dataflow languages. We identify three impediments to the use of APR in dataflow programming, parallelism, state, and evaluation, and highlight opportunities for overcoming them.

CRNRepair: Automated Program Repair of Chemical Reaction Networks
by Ibrahim Mesecan, Michael C. Gerten, James I. Lathrop, Myra B. Cohen, and Tomas Haddad Caldas
DOI PDF VIDEO VIDEO VIDEO URL Abstract

Chemical reaction networks (CRNs) are abstractions of distributed networks that form the foundations of many natural phenomena such as biological processes. These can be encoded and/or compiled into DNA and have been shown to be Turing complete. Before CRNs are implemented in a physical environment, they are often simulated in programming environments. Like traditional programs, these CRN programs must be validated. Researchers have recently designed a software testing framework for CRNs, however, repairing CRN programs is still a manual task. While the programs are often small in size, finding and repairing the faults can be difficult without automated support. we present CRNRepair, a program repair framework for CRN programs. We built our framework on top of an existing APR framework. We use a testing infrastructure built in the Matlab SimBiology package and adapt it to use the SBML representation for its abstract syntax tree. In a case study on 19 mutant versions of 2 programs, we find plausible patches for 90 percent of one of the programs, and 50 percent of the other. We find several common types of repairs, which differ from the correct programs, but are functionally correct.

Engineering and Evolving Software
by Stephanie Forrest
DOI VIDEO URL Abstract

Provides a brief professional biography of the presenter Stephanie Forrest of Arizona State University. The complete presentation was not made available for publication as part of the conference proceedings.

Exploring the Accuracy -- Energy Trade-off in Machine Learning
by Alexander E. I. Brownlee, Jason Adair, Saemundur O. Haraldsson, and John Jabbo
DOI PDF VIDEO VIDEO VIDEO Abstract

Machine learning accounts for considerable global electricity demand and resulting environmental impact, as training a large deep-learning model produces 284000 kgs of the greenhouse gas carbon dioxide. In recent years, search-based approaches have begun to explore improving software to consume less energy. Machine learning is a particularly strong candidate for this because it is possible to trade off functionality (accuracy) against energy consumption, whereas with many programs functionality is simply a pass-or-fail constraint. We use a grid search to explore hyperparameter configurations for a multilayer perceptron on five classification data sets, considering trade-offs of classification accuracy against training or inference energy. On one data set, we show that 77 percent of energy consumption for inference can saved by reducing accuracy from 94.3 percent to 93.2 percent. Energy for training can also be reduced by 30-50 percent with minimal loss of accuracy. We also find that structural parameters like hidden layer size is a major driver of the energy-accuracy trade-off, but there is some evidence that non-structural hyperparameters influence the trade-off too. We also show that a search-based approach has the potential to identify these trade-offs more efficiently than the grid search.

Generating Objected-Oriented Source Code Using Genetic Programming
by Vicente Illanes and Alexandre Bergel
DOI PDF PDF VIDEO VIDEO VIDEO Abstract

Using machine learning to generate source code is an active and highly important research area. In particular,it has been shown that genetic programming (GP) efficiently contributes to software repair. However, most of the published advances on applying GP to generate source code are limited to the C programming language, a statically-typed procedural language. As a consequence, applying GP to object-oriented and dynamically-typed languages may represent a significant opportunity. explores the use of genetic programming to generate objected-oriented source code in a dynamically-typed setting. We found that GP is able to produce missing one-line statements with a precision of 51 percent. Our preliminary results contributes to the state of the art by indicating that GP maybe effectively employed to generate source code for dynamically-typed object-oriented applications.

Open Challenges in Genetic Improvement for Emergent Software Systems
by Penelope Faulkner Rainford and Barry Porter
DOI PDF VIDEO VIDEO VIDEO Abstract

Genetic improvement for emergent software systems faces unique challenges due to its deployment in highly dynamic environments. We discuss four of those challenges along with our initial plans for new research.

Optimising SQL Queries Using Genetic Improvement
by James Callan and Justyna Petke
DOI PDF VIDEO VIDEO VIDEO Abstract

Structured Query Language (SQL) queries are ubiquitous in modern software engineering. These queries can be costly when run on large databases with many entries and tables to consider. We propose using Genetic Improvement (GI) to explore patches for these queries, with the aim of optimising their execution time, whilst maintaining the functionality of the program in which they are used. Specifically, we propose three ways in which SQL JOIN statements can be mutated in order to improve performance. We also discuss the requirements of software being improved in this manner and the potential challenges of our approach.

Partial Specifications for Program Repair
by Linsey Kitt and Myra B. Cohen
DOI PDF VIDEO VIDEO VIDEO Abstract

we argue for using many partial test suites instead of one full test suite during program repair. This may provide a pool of simpler, yet correct patches, addressing both the overfitting and poor repair quality problem. To support this idea, we present some insight obtained running APR partial test suites on the well studied triangle program.

Uniform Edit Selection for Genetic Improvement: Empirical Analysis of Mutation Operator Efficacy
by Marta Smigielska, Aymeric Blot, and Justyna Petke
DOI PDF VIDEO VIDEO VIDEO URL Abstract

Genetic improvement (GI) tools find improved program versions by modifying the initial program. These can be used for the purpose of automated program repair (APR). GI uses software transformations, called mutation operators, such as deletions, insertions, and replacements of code fragments. Current edit selection strategies, however, under-explore the search spaces of insertion and replacement operators. Therefore, we implement a uniform strategy based on the relative operator search space sizes. We evaluate it on the QuixBugs repair benchmark and find that the uniform strategy has the potential for improving APR tool performance. We also analyse the efficacy of the different mutation operators with regard to the type of code fragment they are applied to. We find that, for all operators, choosing expression statements as target statements is the most successful for finding program variants with improved or preserved fitness (50.03 percent, 33.12 percent and 23.85 percent for deletions, insertions and replacements, respectively), whereas choosing declaration statements is the least effective (3.16 percent, 10.82 percent and 3.14 percent for deletions, insertions and replacements).

Using Genetic Improvement to Retarget quantum Software on Differing Hardware
by George O'Brien and John Clark
DOI VIDEO VIDEO VIDEO Abstract

Quantum computers are rapidly developing to a point where they can solve problems faster than any classical computation. As they're developed competing standards for languages, models and architectures are also being created. These standards are often bespoke and aimed at optimizing around a single algorithm or problem. This can make it very difficult to reuse these them should the original hardware become unavailable or obsolete. We demonstrate a method that can compile circuits more generally across hardware constraints with the use of a genetic improvement inspired search technique that includes a realistic model of the hardware. We show that this method is effective at selecting gates that can be more easily implemented and ran compared to generic optimization which reduces the total chance of failure. To ensure that these results are practical, empirical results are generated using different IBM hardware and a selection of real algorithms.

Call For Submissions [pdf]

We invite submissions that discuss recent developments in all areas of research on, and applications of, Genetic Improvement. The International Workshop on Genetic Improvement is the premier workshop in the field and provides an opportunity for researchers interested in automated program repair and software optimisation to disseminate their work, exchange ideas, and discover new research directions. Topics of interest include both the theory and practice of Genetic Improvement. Applications of GI include, but are not limited to:

Improve efficiency
Decrease memory consumption
Decrease energy consumption
Transplant new functionality
Specialise software
Translate between programming languages
Generate multiple versions of software
Repair bugs

We invite submissions of two paper types:

Research papers (eight page limit, including references)
Position papers (two page limit, including references)

We encourage authors to submit early and in-progress work. The workshop emphasises interaction and discussion.

All papers should be submitted via HotCRP: https://icse21-gi10.hotcrp.com/
These papers will be reviewed in a double-blind manner.
All accepted papers must be presented at GI-2021 and will appear in the ICSE workshops volume.

Workshop Chairs

Justyna Petke is a Principal Research Fellow and Proleptic Senior Lecturer (Associate Prof.), conducting research in genetic improvement. She has a doctorate in Computer Science from University of Oxford and is now at the Centre for Research on Evolution, Search and Testing (CREST) in University College London. She has published on applications of genetic improvement. Her work on the subject was awarded a Silver and a Gold ’Humie’ at GECCO 2014 and GECCO 2016 as well as an ACM SIGSOFT Distinguished Paper Award at ISSTA 2015. She was the PC co-Chair for the International Symposium on Search-Based Software Engineering in 2017. She also organised six Genetic Improvement Workshops. She currently serves on the editorial board of the Genetic Programming and Evolvable Machines journal.

Bobby Bruce is a Postdoctoral Scholar at UC Davis where he primarily works on the gem5 computer architecture simulator. Prior to UC Davis, Bobby carried out research into the automatic optimization of Java bytecode at UCLA. His research interests are centred around Search-based Software Engineering, and its application to improving software performance.

Yu Huang is a PhD candidate at the University of Michigan, Ann Arbor. Her research includes applying GI-based automated program repair (APR) techniques in embedded systems and human factors in software automation with a focus on human bias against automated tools in code review. She has served as the organizer for multiple Diversity, Equivalence and Inclusion events hosted at University of Michigan. She was also in charge of the social media for GI 2020 to advertise the event and connect researchers and practitioners in the community. Currently she is serving as the Social Media Chair for GI 2021.

Aymeric Blot is a Research Associate conducting research in genetic improvement at the CREST and SOLAR groups in University College London. He received in 2018 a doctorate from the University of Lille following work on automated algorithm design for multi-objective combinatorial optimisation. His research focuses on strengthening GI techniques using knowledge from automated machine learning, algorithm configuration, and evolutionary computation. He maintains and evolves the community website on genetic improvement.

Westley Weimer is a Professor at the University of Michigan He received his PhD from the University of California at Berkeley. His research interests include reducing the costs associated with software development at scale (particularly through automated program repair) as well as program analysis, formal verification, and human linguistic and visual interaction with software. He is a senior member of the Association for Computing Machinery and his work has led to over eleven thousand citations and several awards, including three ‘Humies’ and ICSE 2019 Most Influential paper for his work on using Genetic Improvement for bug fixing. He also organised five Genetic Improvement workshops.

Special thanks to Bill Langdon for helping with advertising the workshop.

PC