Automated program repair techniques aim to aid software developers with the challenging task of fixing bugs. In heuristic-based program repair, a search space of mutated program variants is explored to find potential patches for bugs. Most commonly, every selection of a mutation operator during search is performed uniformly at random, which can generate many buggy, even uncompilable programs. Our goal is to reduce the generation of variants that do not compile or break intended functionality which waste considerable resources. In this paper, we investigate the feasibility of a reinforcement learning-based approach for the selection of mutation operators in heuristic-based program repair. Our proposed approach is programming language, granularity-level, and search strategy agnostic and allows for easy augmentation into existing heuristic-based repair tools. We conducted an extensive empirical evaluation of four operator selection techniques, two reward types, two credit assignment strategies, two integration methods, and three sets of mutation operators using 30,080 independent repair attempts. We evaluated our approach on 353 real-world bugs from the Defects4J benchmark. The reinforcement learning-based mutation operator selection results in a higher number of test-passing variants, but does not exhibit a noticeable improvement in the number of bugs patched in comparison with the baseline, uniform random selection. While reinforcement learning has been previously shown to be successful in improving the search of evolutionary algorithms, often used in heuristic-based program repair, it has yet to demonstrate such improvements when applied to this area of research.

Genetic improvement (GI) uses automated search to improve existing software. It has been successfully used to optimize various program properties, such as runtime or energy consumption, as well as for the purpose of bug fixing. GI typically navigates a space of thousands of patches in search for the program mutation that best improves the desired software property. While genetic programming (GP) has been dominantly used as the search strategy, more recently other search strategies, such as local search, have been tried. It is, however, still unclear which strategy is the most effective and efficient. In this article, we conduct an in-depth empirical comparison of a total of 18 search processes using a set of eight improvement scenarios. Additionally, we also provide new GI benchmarks and we report on new software patches found. Our results show that, overall, local search approaches achieve better effectiveness and efficiency than GP approaches. Moreover, improvements were found in all scenarios (between 15% and 68%). A replication package can be found online:https://github.com/bloa/tevc_2020_artefact.

PyGGI is a research tool for Genetic Improvement (GI), that is designed to be versatile and easy to use. We present version 2.0 of PyGGI, the main feature of which is an XML-based intermediate program representation. It allows users to easily define GI operators and algorithms that can be reused with multiple target languages. Using the new version of PyGGI, we present two case studies. First, we conduct an Automated Program Repair (APR) experiment with the QuixBugs benchmark, one that contains defective programs in both Python and Java. Second, we replicate an existing work on runtime improvement through program specialisation for the MiniSAT satisfiability solver. PyGGI 2.0 was able to generate a patch for a bug not previously fixed by any APR tool. It was also able to achieve 14% runtime improvement in the case of MiniSAT. The presented results show the applicability and the expressiveness of the new version of PyGGI. A video of the tool demo is at: https://youtu.be/PxRUdlRDS40.

Automatic algorithm configuration (AAC) is becoming a key ingredient in the design of high-performance solvers for challenging optimisation problems. However, most existing work on AAC deals with configuration procedures that optimise a single performance metric of a given, single-objective algorithm. Of course, these configurators can also be used to optimise the performance of multi-objective algorithms, as measured by a single performance indicator. In this work, we demonstrate that better results can be obtained by using a native, multi-objective algorithm configuration procedure. Specifically, we compare three AAC approaches: one considering only the hypervolume indicator, a second optimising the weighted sum of hypervolume and spread, and a third that simultaneously optimises these complementary indicators, using a genuinely multi-objective approach. We assess these approaches by applying them to a highly-parametric local search framework for two widely studied multi-objective optimisation problems, the bi-objective permutation flowshop and travelling salesman problems. Our results show that multi-objective algorithms are indeed best configured using a multi-objective configurator.

Multi-objective optimisation algorithms expose various parameters that have to be tuned in order to be efficient. Moreover, in multi-objective optimisation, the correlation between objective functions is known to affect search space structure and algorithm performance. Considering the recent success of automatic algorithm configuration (AAC) techniques for the design of multi-objective optimisation algorithms, this raises two interesting questions: what is the impact of correlation between optimisation objectives on (1) the efficacy of different AAC approaches and (2) on the optimised algorithm designs obtained from these automated approaches? In this work, we study these questions for multi-objective local search algorithms (MOLS) for three well-known bi-objective permutation problems, using two single-objective AAC approaches and one multi-objective approach. Our empirical results clearly show that overall, multi-objective AAC is the most effective approach for the automatic configuration of the highly parametric MOLS framework, and that there is no systematic impact of the degree of correlation on the relative performance of the three AAC approaches. We also find that the best-performing configurations differ, depending on the correlation between objectives and the size of the problem instances to be solved, providing further evidence for the usefulness of automatic configuration of multi-objective optimisation algorithms.

Multi-objective local search (MOLS) algorithms are efficient meta-heuristics, which improve a set of solutions by using their neighbourhood to iteratively find better and better solutions. MOLS algorithms are versatile algorithms with many available strategies, first to select the solutions to explore, then to explore them, and finally to update the archive using some of the visited neighbours. In this paper, we propose a new generalisation of MOLS algorithms incorporating new recent ideas and algorithms. To be able to instantiate the many MOLS algorithms of the literature, our generalisation exposes numerous numerical and categorical parameters, raising the possibility of being automatically designed by an automatic algorithm configuration (AAC) mechanism. We investigate the worth of such an automatic design of MOLS algorithms using MO-ParamlLS, a multi-objective AAC configurator, on the permutation flowshop scheduling problem, and demonstrate its worth against a traditional manual design.