International Workshop on Automatic Software Optimisation

5th edition of GI @ GECCO 2018 in Kyoto, Japan

5th Edition of the GI workshop will take place with GECCO 2018 in Kyoto, 15-19 July

It is scheduled for Monday 16th, 14:00-17:40
and the program is as follows.

  • 14:00 - 15:40
    • Welcome, Markus Wagner
    • Quantum Genetic Programming, David R. White (Keynote)
    • Synthesizing Customized Network Protocols using Genetic Programming
      Roohitavaf, Zhu, Kulkarni, Biswas
    • Towards Modular Large-Scale Darwinian Software Improvement
      Orlov
  • 15:40 - 16:00: Coffee
  • 16:00 - 17:40
    • Novelty Search for software improvement of a SLAM system
      López-López, Trujillo, Legrand
    • Genetic Configuration Sampling: Learning a Sampling Strategy for Fault Detection of Configurable Systems
      Xuan, Gu, Ren, Jia, Fan
    • Assessing Single-Objective Performance Convergence and Time Complexity for Refactoring Detection
      Nader-Palacio, Rodríguez-Cárdenas, Gomez Perdomo
    • Dynamic Fitness Functions for Genetic Improvement in Compilers and Interpreters
      Krauss, Mössenböck, Affenzeller

Papers and abstracts

Regarding the copyright, we’d like to mention that the PDFs are pre-print or author-prepared versions of the papers. They are solely provided for timely communication among scholars, without permission for further distribution. The definitive version of a paper is the published version.

The synthesis and improvement of quantum circuits and programs (Keynote)
David R. White and John Clark

Quantum computing is a qualitatively different form of computation. We are increasing understanding of what quantum computing is suited for and how it can be used alongside traditional computational approaches. The notion of quantum software engineering is beginning to take hold. There is real scope for the automated generation of artifacts such as circuits or programs targeted for execution on a quantum computer.
In this talk we will outline some of the ways approaches from evolutionary computation have been used to generate small artifacts in such spaces. We will also indicate some of the non-functional issues that must be taken into account when working with quantum hardware.
Thus, we can see how synthesis and improvement can be addressed within an evolutionary framework.

Synthesizing Customized Network Protocols using Genetic Programming
Mohammad Roohitavaf, Ling Zhu, Sandeep Kulkarni, and Subir Biswas

pdf

Given the advances in areas such as home automation, agricultural networks, smart cities, designers often need to design protocols that utilize the features of that network while dealing with its limitations. Utilizing standardized protocols for such networks may not be appropriate as they may not address limitations of the network such as heterogeneous nodes or limited capability of some nodes. While designing a customized protocol for that network would be desirable, it is extremely time-consuming unless we can automate the development of the required protocol. In this paper, we present NetSynth, a GP based mechanism to develop customized routing protocol for the given network. NetSynth lets us conveniently describe a network using an XML ile, and it synthesizes a routing protocol that suits the input network by considering the characteristics specific to the given network. We show how NetSynth creates protocols that perform comparably to best-known protocols for the case where we want to broadcast a set of messages to all nodes in a grid. We also show how NetSynth helps us design protocols that provide a tradeof between throughput and energy.

Towards Modular Large-Scale Darwinian Software Improvement
Michael Orlov

pdf

This paper proposes to explore a software engineer-assisted method for evolutionarily improving large-scale software systems. A framework is outlined for selecting and evolving specific components of such systems, while avoiding treating the complete software as a single independent individual in the population, thereby forgoing the high costs of that approach.

Novelty Search for software improvement of a SLAM system
Víctor R. López-López, Leonardo Trujillo, and Pierrick Legrand

pdf

Genetic Improvement (GI) performs a search at the level of source code to find the best variant of a baseline system that improves non-functional properties while maintaining functionality, with noticeable results in several domains. There a many aspects of this general approach that are currently being explored. In particular, this work deals to the way in which the search is guided to efficiently explore the search space of possible software versions in which GI operates. The proposal is to integrate Novelty Search (NS) within the GISMOE GI framework to improve KinectFusion, which is a vision-based Simultaneous Localization and Mapping (SLAM) system that is used for augmented reality, autonomous vehicle navigation, and many other real-world applications. This is one of a small set of works that have successfully combined NS with a GP system, and the first time that it has been used for software improvement. To achieve this, we propose a new behaviour descriptor for SLAM algorithms, based on state-of-the-art benchmarking and present results that show that NS can produce significant improvement gains in a GI setting, when considering execution time and trajectory estimation as the main performance criteria.

Genetic Configuration Sampling: Learning a Sampling Strategy for Fault Detection of Configurable Systems
Jifeng Xuan, Yongfeng Gu, Zhilei Ren, Xiangyang Jia, and Qingna Fan

pdf

A highly-configurable system provides many configuration options to diversify application scenarios. The combination of these configuration options results in a large search space of configurations. This makes the detection of configuration-related faults extremely hard. Since it is infeasible to exhaust every configuration, several methods are proposed to sample a subset of all configurations to detect hidden faults. Configuration sampling can be viewed as a process of repeating a pre-defined sampling action to the whole search space, such as the one-enabled or pair-wise strategy. In this paper, we propose genetic configuration sampling, a new method of learning a sampling strategy for configuration-related faults. Genetic configuration sampling encodes a sequence of sampling actions as a chromosome in the genetic algorithm. Given a set of known configuration-related faults, genetic configuration sampling evolves the sequence of sampling actions and applies the learnt sequence to new configuration data. A pilot study on three highly-configurable systems shows that genetic configuration sampling performs well among nine sampling strategies in comparison.

Assessing Single-Objective Performance Convergence and Time Complexity for Refactoring Detection
David Nader-Palacio, Daniel Rodríguez-Cárdenas, and Jonatan Gomez

pdf

The automatic detection of refactoring recommendations has been tackled in prior optimization studies involving bad code smells, semantic coherence and importance of classes; however, such studies informally addressed formalisms to standardize and replicate refactoring models. We propose to assess the refactoring detection by means of performance convergence and time complexity. Since the reported approaches are diicult to reproduce, we employ an Artiicial Refactoring Generation (ARGen) as a formal and naive computational solution for the Refactoring Detection Problem. ARGen is able to detect massive refactoring’s sets in feasible areas of the search space. We used a refactoring formalization to adapt search techniques (Hill Climbing, Simulated Annealing and Hybrid Adaptive Evolutionary Algorithm) that assess the performance and complexity on three open software systems. Combinatorial techniques are limited in solving the Refactoring Detection Problem due to the relevance of developers’ criteria (human factor) when designing reconstructions. Without performance convergence and time complexity analysis, a software empirical analysis that utilizes search techniques is incomplete.

Dynamic Fitness Functions for Genetic Improvement in Compilers and Interpreters
Oliver Krauss, Hanspeter Mössenböck, and Michael Affenzeller

pdf

When attempting to improve the non-functional requirements of software, specifically run-time performance of code, an important requirement is to preserve the correctness of the optimized code. Additionally when attempting to integrate Genetic Improvement into a compiler or interpreter, the large search spaces resulting from the amount of operators and operands a language provides needs to be dealt with. This publication explores dynamic fitness functions as a foundation for a use in Genetic Improvement to optimize programs. An approach of using a test suite to verify code correctness in the Truffle Framework [19, 20] and Graal Compiler [11] is presented. Two types of fitness functions are explored, which split the test suite according to their complexity and attempt to generate correct solutions with a growing set of increasingly complex tests. One of them increases the amount of tests sequentially over several iterations. The parallel fitness function attempts to split a test suite and to re-combine the results with increasingly large suites. The results show that these functions only marginally improve the fitness landscape on their own, but show that more partially correct solutions can be found with dynamic fitness functions. In the future, our approach may be improved by implementing specific crossover and mutator operations to accompany the dynamic fitness functions.