Genetic improvement (computer science)

Last updated

In computer software development, genetic Improvement is the use of optimisation and machine learning techniques, particularly search-based software engineering techniques such as genetic programming to improve existing software. [1] [2] The improved program need not behave identically to the original. For example, automatic bug fixing improves program code by reducing or eliminating buggy behaviour. [3] In other cases the improved software should behave identically to the old version but is better because, for example: it runs faster, [4] it uses less memory, [5] it uses less energy [6] or it runs on a different type of computer. [7] GI differs from, for example, formal program translation, in that it primarily verifies the behaviour of the new mutant version by running both the new and the old software on test inputs and comparing their output and performance in order to see if the new software can still do what is wanted of the original program and is now better.

Contents

Genetic improvement can be used to create multiple versions of programs, each tailored to be better for a particular use or for a particular computer.

Genetic improvement can be used with multi-objective optimization to consider improving software along multiple dimensions or to consider trade-offs between several objectives, such as asking GI to evolve programs which trade speed against the quality of answers they give. Of course it may be possible to find programs which are both faster and give better answers.

Mostly Genetic Improvement makes typically small changes or edits (also known as mutations) to the program's source code but sometimes the mutations are made to assembly code, byte code [8] or binary machine code. [9]

Related Research Articles

<span class="mw-page-title-main">Evolutionary algorithm</span> Subset of evolutionary computation

In computational intelligence (CI), an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the quality of the solutions. Evolution of the population then takes place after the repeated application of the above operators.

<span class="mw-page-title-main">Particle swarm optimization</span> Iterative simulation method

In computational science, particle swarm optimization (PSO) is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. It solves a problem by having a population of candidate solutions, here dubbed particles, and moving these particles around in the search-space according to simple mathematical formula over the particle's position and velocity. Each particle's movement is influenced by its local best known position, but is also guided toward the best known positions in the search-space, which are updated as better positions are found by other particles. This is expected to move the swarm toward the best solutions.

A fitness function is a particular type of objective function that is used to summarise, as a single figure of merit, how close a given design solution is to achieving the set aims. Fitness functions are used in evolutionary algorithms (EA), such as genetic programming and genetic algorithms to guide simulations towards optimal design solutions.

Neuroevolution, or neuro-evolution, is a form of artificial intelligence that uses evolutionary algorithms to generate artificial neural networks (ANN), parameters, and rules. It is most commonly applied in artificial life, general game playing and evolutionary robotics. The main benefit is that neuroevolution can be applied more widely than supervised learning algorithms, which require a syllabus of correct input-output pairs. In contrast, neuroevolution requires only a measure of a network's performance at a task. For example, the outcome of a game can be easily measured without providing labeled examples of desired strategies. Neuroevolution is commonly used as part of the reinforcement learning paradigm, and it can be contrasted with conventional deep learning techniques that use gradient descent on a neural network with a fixed topology.

Code review is a software quality assurance activity in which one or more people check a program, mainly by viewing and reading parts of its source code, either after implementation or as an interruption of implementation. At least one of the persons must not have authored the code. The persons performing the checking, excluding the author, are called "reviewers".

A memetic algorithm (MA) in computer science and operations research, is an extension of the traditional genetic algorithm (GA) or more general evolutionary algorithm (EA). It may provide a sufficiently good solution to an optimization problem. It uses a suitable heuristic or local search technique to improve the quality of solutions generated by the EA and to reduce the likelihood of premature convergence.

Kalyanmoy Deb is an Indian computer scientist. Deb is the Herman E. & Ruth J. Koenig Endowed Chair Professor in the Department of Electrical and Computing Engineering at Michigan State University. Deb is also a professor in the Department of Computer Science and Engineering and the Department of Mechanical Engineering at Michigan State University.

Autoconstructive evolution is a process in which the entities undergoing evolutionary change are themselves responsible for the construction of their own offspring and thus for aspects of the evolutionary process itself. Because biological evolution is always autoconstructive, this term mainly occurs in evolutionary computation, to distinguish artificial life type systems from conventional genetic algorithms where the GA performs replication artificially. The term was coined by Lee Spector.

Search-based software engineering (SBSE) applies metaheuristic search techniques such as genetic algorithms, simulated annealing and tabu search to software engineering problems. Many activities in software engineering can be stated as optimization problems. Optimization techniques of operations research such as linear programming or dynamic programming are often impractical for large scale software engineering problems because of their computational complexity or their assumptions on the problem structure. Researchers and practitioners use metaheuristic search techniques, which impose little assumptions on the problem structure, to find near-optimal or "good-enough" solutions.

In artificial immune systems, clonal selection algorithms are a class of algorithms inspired by the clonal selection theory of acquired immunity that explains how B and T lymphocytes improve their response to antigens over time called affinity maturation. These algorithms focus on the Darwinian attributes of the theory where selection is inspired by the affinity of antigen-antibody interactions, reproduction is inspired by cell division, and variation is inspired by somatic hypermutation. Clonal selection algorithms are most commonly applied to optimization and pattern recognition domains, some of which resemble parallel hill climbing and the genetic algorithm without the recombination operator.

<span class="mw-page-title-main">HyperNEAT</span>

Hypercube-based NEAT, or HyperNEAT, is a generative encoding that evolves artificial neural networks (ANNs) with the principles of the widely used NeuroEvolution of Augmented Topologies (NEAT) algorithm developed by Kenneth Stanley. It is a novel technique for evolving large-scale neural networks using the geometric regularities of the task domain. It uses Compositional Pattern Producing Networks (CPPNs), which are used to generate the images for Picbreeder.orgArchived 2011-07-25 at the Wayback Machine and shapes for EndlessForms.comArchived 2018-11-14 at the Wayback Machine. HyperNEAT has recently been extended to also evolve plastic ANNs and to evolve the location of every neuron in the network.

<span class="mw-page-title-main">Roberto Battiti</span>

Roberto Battiti is an Italian computer scientist, Professor of computer science at the University of Trento, director of the LIONlab, and deputy director of the DISI Department and delegate for technology transfer.

LIONsolver is an integrated software for data mining, business intelligence, analytics, and modeling and reactive business intelligence approach. A non-profit version is also available as LIONoso.

The MOEA Framework is an open-source evolutionary computation library for Java that specializes in multi-objective optimization. It supports a variety of multiobjective evolutionary algorithms (MOEAs), including genetic algorithms, genetic programming, grammatical evolution, differential evolution, and particle swarm optimization. As a result, it has been used to conduct numerous comparative studies to assess the efficiency, reliability, and controllability of state-of-the-art MOEAs.

<span class="mw-page-title-main">Symbolic regression</span> Type of regression analysis

Symbolic regression (SR) is a type of regression analysis that searches the space of mathematical expressions to find the model that best fits a given dataset, both in terms of accuracy and simplicity.

EvoSuite is a tool that automatically generates unit tests for Java software. EvoSuite uses an evolutionary algorithm to generate JUnit tests. EvoSuite can be run from the command line, and it also has plugins to integrate it in Maven, IntelliJ and Eclipse. EvoSuite has been used on more than a hundred open-source software and several industrial systems, finding thousands of potential bugs.

Automatic bug-fixing is the automatic repair of software bugs without the intervention of a human programmer. It is also commonly referred to as automatic patch generation, automatic bug repair, or automatic program repair. The typical goal of such techniques is to automatically generate correct patches to eliminate bugs in software programs without causing software regression.

Multi-task optimization is a paradigm in the optimization literature that focuses on solving multiple self-contained tasks simultaneously. The paradigm has been inspired by the well-established concepts of transfer learning and multi-task learning in predictive analytics.

Software diversity is a research field about the comprehension and engineering of diversity in the context of software.

This is a chronological table of metaheuristic algorithms that only contains fundamental algorithms. Hybrid algorithms and multi-objective algorithms are not listed in the table below.

References

  1. ↑ Langdon, William B. (2015). "Genetically Improved Software". Handbook of Genetic Programming Applications. pp. 181–220. doi:10.1007/978-3-319-20883-1_8. ISBN   978-3-319-20882-4.
  2. ↑ Justyna Petke and Saemundur O. Haraldsson and Mark Harman and William B. Langdon and David R. White and John R. Woodward (2018). "Genetic Improvement of Software: a Comprehensive Survey" (PDF). IEEE Transactions on Evolutionary Computation. 22 (3): 415–432. doi:10.1109/TEVC.2017.2693219. hdl: 1893/25358 . S2CID   30314751.
  3. ↑ Weimer, Westley; et al. (2010). "Automatic program repair with evolutionary computation". Communications of the ACM. 53 (5): 109–116. CiteSeerX   10.1.1.170.188 . doi:10.1145/1735223.1735249. S2CID   7408151.
  4. ↑ Langdon, William B.; Harman, Mark (2015). "Optimizing Existing Software With Genetic Programming". IEEE Transactions on Evolutionary Computation. 19: 118–135. doi:10.1109/TEVC.2013.2281544. S2CID   9891830.
  5. ↑ Wu, Fan; Weimer, Westley; Harman, Mark; Jia, Yue; Krinke, Jens (2015). "Deep Parameter Optimisation". Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. pp. 1375–1382. doi:10.1145/2739480.2754648. ISBN   9781450334723. S2CID   17820784.
  6. ↑ Bruce, Bobby R.; Petke, Justyna; Harman, Mark (2015). "Reducing Energy Consumption Using Genetic Improvement". Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. pp. 1327–1334. doi:10.1145/2739480.2754752. ISBN   9781450334723. S2CID   207224618.
  7. ↑ Langdon, William B.; Harman, Mark (2014). "Genetically Improved CUDA C++ Software". Genetic Programming. pp. 87–99. doi:10.1007/978-3-662-44303-3_8. ISBN   978-3-662-44302-6.{{cite book}}: |journal= ignored (help)
  8. ↑ Orlov, Michael; Sipper, Moshe (2011). "Flight of the FINCH Through the Java Wilderness". IEEE Transactions on Evolutionary Computation. 15 (2): 166–182. CiteSeerX   10.1.1.298.6272 . doi:10.1109/TEVC.2010.2052622. S2CID   14616802.
  9. ↑ Schulte, Eric M.; Weimer, Westley; Forrest, Stephanie (2015). "Repairing COTS Router Firmware without Access to Source Code or Test Suites". Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation. pp. 847–854. doi:10.1145/2739482.2768427. ISBN   9781450334884. S2CID   14772346.

Tools

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.