skip to Main Content

Genetic Algorithms

Genetic algorithms (GAs) describe probabilistic search procedures designed to work on large problem spaces that are based on the principles of natural selection and genetics (Goldberg & Holland, 1988; Sastry, Goldberg, & Kendall, 2014). GAs employ methods which move from one population of ‘chromosomes’ to a new population, mimicking the principles of natural selection, whilst also utilising the genetics-inspired operators of crossover, mutation, and inversion (Mitchell, 1998).

In seeking a solution to a problem, a problem is encoded as an artificial chromosome or chromosomes, which can exist as strings of 1s and 0s, permutation codes, parameter lists, or complex computer codes (Goldberg, 2013). From here, a fitness function choses those chromosomes in the population that will be permitted to reproduce, with the fitter chromosomes producing more offspring than the less fit ones on average according to a survival-of-the-fittest mechanism (Mitchell, 1998; Goldberg, 2013). With the problem encoded in a chromosomal manner and a fitness function chosen for discriminating between good and bad solutions, solutions to the search problem are evolved as follows (Sastry, Goldberg, & Kendall, 2014):

Initialisation – the initial population of candidate solutions is generated across the search space, either randomly or in accordance with domain-specific knowledge.
Evaluation – Offspring population is created from the initial population, with candidate solutions evaluated according to the fitness function.
Selection – Solutions with better fitness values are allocated more copies according to a survival-of-the-fittest mechanism for candidate solutions.
Recombination – Components of one or more parental solutions are combined to create new, possibly better solutions (i.e. offspring) according to a specified recombination mechanism.
Mutation – One or more changes to an individual solution’s trait or traits are made randomly to modify the solution.
Replacement – The offspring population created via selection, recombination, and mutation replaces the original parent population.
Repeat – Steps 2 to 6 are repeated until one or more stopping criterion is met.

In this way, GAs can accommodate a wide range of problem-solving and optimisation-based applications, where the algorithms scale well in terms of the solution time required as the size and difficulty of the problem grows (Goldberg, 2013). Given their inherent parallelism, where many different possibilities can be explored simultaneously in an efficient manner, GAs thus lend themselves particularly well to computational problems which require adaptive, innovative, and complex solutions (Goldberg & Holland, 1988; Mitchell, 1998). For example, GAs have been employed to optimise stopping patterns for passenger rail transportation (Lin & Ku, 2014), undertake image enhancement and segmentation (Paulinas & Ušinskas, 2015), construct school timetable solutions (Pillay, 2014), and evolve neural networks (David & Greental, 2014). However, while GAs can be successfully utilised to solve increasingly difficult problems across a wide spectrum of areas, clear and robust design principles are needed to ensure the development of competent GAs which can solve hard problems, quickly, reliably and accurately, with a premium on efficiency (Sastry, Goldberg, & Kendall, 2014).

More reading and references

  • David, O. E., & Greental, I. (2014). Genetic algorithms for evolving deep neural networks. ACM Genetic and Evolutionary Computation Conference (GECCO), Canada, 1451-1452. 10.1145/2598394.2602287
  • Goldberg., D. E. (2013). The design of innovation: Lessons from and for competent genetic algorithms. Springer Science & Business Media.
  • Goldberg, D. E., & Holland, J. H. (1988). Genetic algorithms and machine learning. Machine learning, 3(2), 95-99.
  • Lin, D. Y., & Ku, Y. H. (2014). Using genetic algorithms to optimize stopping patterns for passenger rail transportation. Computer‐Aided Civil and Infrastructure Engineering, 29(4), 264-278. 10.1111/mice.12020
  • Mitchell, M. (1998). An introduction to genetic algorithms. MIT Press.
  • Paulinas, M., & Ušinskas, A. (2007). A survey of genetic algorithms applications for image enhancement and segmentation. Information Technology and Control, 36(3), 278-284.
  • Pillay, N. (2014). A survey of school timetabling research. Annals of Operations Research, 218(1), 261-293.
  • Sastry, K., Goldberg, D. E., & Kendall, G. (2014). Genetic algorithms. In E. K. Burke & G. Kendall (Eds.) Search methodologies, Springer, Berlin, 93 -117.
Back To Top

Pin It on Pinterest

Share This