Empirical Comparison of Search Heuristics for Genetic Improvement of Software

Created by W.Langdon from gp-bibliography.bib Revision:1.7630

@Article{blot:2021:tevc,

• author = "Aymeric Blot and Justyna Petke",
• title = "Empirical Comparison of Search Heuristics for Genetic Improvement of Software",
• journal = "IEEE Transactions on Evolutionary Computation",
• year = "2021",
• volume = "25",
• number = "5",
• pages = "1001--1011",
• month = oct,
• keywords = "genetic algorithms, genetic programming, genetic improvement, GI, Search-Based Software Engineering, SBSE, Stochastic Local Search, PyGGI, Uniform interleaved crossover",
• ISSN = "1089-778X",
• URL = "http://www.cs.ucl.ac.uk/staff/a.blot/publis/#blot:2021:tevc",
• URL = "http://www.cs.ucl.ac.uk/staff/a.blot/files/blot_tevc_2021.pdf",
• code_url = "https://github.com/bloa/tevc_2020_artefact",
• DOI = "doi:10.1109/TEVC.2021.3070271",
• size = "11 pages",
• abstract = "Genetic improvement uses automated search to improve existing software. It has been successfully used to optimise various program properties, such as runtime or energy consumption, as well as for the purpose of bug fixing. Genetic improvement typically navigates a space of thousands of patches in search for the program mutation that best improves the desired software property. While genetic programming 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 paper, we conduct an in-depth empirical comparison of a total of 18 search processes using a set of 8 improvement scenarios. Additionally, we also provide new genetic improvement benchmarks and we report on new software patches found. Our results show that, overall, local search approaches achieve better effectiveness and efficiency than genetic programming approaches. Moreover, improvements were found in all scenarios (between 15percent and 68percent). A replication package can be found online: https://github.com/bloa/tevc_2020_artefact.",
• notes = "Supplement http://www.cs.ucl.ac.uk/staff/a.blot/files/blot_tevc_2021_supp.pdf

  computational speed: 'number of CPU instructions as measured by the Linux perf' Table 3 'at least 5 percent faster than the original software'.

  Over fitting: 'On average, 84 percent of the significant improvements confirmed during validation are also significant in the entire dataset'

  Table IV numbers less than 100 represent speed up. 'Speedups from 15 percent to 68 percent can be found for all scenarios'.

  'the search space is largely neutral'. 'new benchmarks and target software for non-functional genetic improvement'.

  MiniSAT (two both C++), Sat4j (Java), Combinatorial Interaction Testing CIT, SATLIB. OptiPNG (three all C), MOEA/D (C++) and NSGA-II (C++).

  Random search.

  GP (pop=100) crossover mutation. Four types of GP crossover: Concatenation, Single-point, Uniform concatenation, Uniform interleaved. Mutation: deletion, append. GP: ' best individual in the last generation', 'the best individual evaluated over the entire search'. 'eassessed over a larger subset of [test] inputs.

  Local search (hill climbing, iterative improvement): mutation only. first improvement, best improvement, and tabu search. Neutral moved accepted. No restarts. unnecessary edits. 'reasonable fixed-size subsets of S neighbours of the neighbourhood of the current solution'. 'fixed-length tabu list'.

  'two-stage validation step.'

  k-fold cross-validation.

  Centos-7 multi core 3.4GHz Intel i7-2600, 16GB ram, GCC 4.8.5.

  'local search and genetic programming found identical or semantically equivalent software variants in most cases'. 'all been manually verified to be semantically valid.

  NSGA-II 'several algorithmic changes are found'.

  'Across all repetitions the best performances have been obtained in around 12 percent of all runs.'

  'Local search approaches clearly outperform all other approaches on the test data.'

  'genetic programming and random search perform similarly' !!!!

  'GI performance could be significantly improved if better search approaches are considered'.

  'GP use most of the training budged recombining known mutations, while local search have more opportunities to explore software variants.'

  also known as \cite{9392013}",

}

Genetic Programming entries for Aymeric Blot Justyna Petke

Citations