Genetic algorithms and optimization problems
Seth Baldrey
In computer science, there is the field of optimization, which means selecting the best solution possible from a set of given alternatives. The goal of optimization is to achieve not only the best solution but also the most effective and efficient method of acquiring it. 1 But optimization problems can become very hard to solve as the complexity increases. One way developed to produce useful solutions to optimization and search problems is to use genetic algorithms. Genetic algorithms can be described as using the idea of ‘ solutions that evolve ’ 2 which is an algorithm that adapts from the Darwinian idea of ‘ survival of the fittest ’ . 3 The example of an optimization problem that I will use to test the effectiveness of these algorithms is the ‘ Travelling salesman problem ’ . This very old problem, first studied by mathematicians in Vienna at Harvard in the 1930s, 4 can be stated as follows: ‘A salesman is required to travel between n cities. He wishes to travel to all locations exactly once and, using the shortest possible route, he must finish at his starting point. ’ 5 Although the problem is extremely problematic and led to countless studies in an attempt to improve solutions, one potential method was the use of the aforementioned genetic algorithms. Genetic algorithms are used to find quality solutions to computer science problems through a biology- based strategy, a combination of Charles Darwin’s theory of evolution and computation. The three key methods of genetic algorithms are selection, crossover, and mutation. To accomplish these methods, the data and hence potential solutions are converted first into integers and then into a string of integers to represent the original data. This string is described as chromosomes in a process to imitate the process of evolution. Each integer within the chromosome is then described as a gene of the chromosome, e.g. ABCDEF as 123456 and A/1 being a gene. These chromosomes are then to be tested, selected, and manipulated. To start the selection process, an initial group of chromosomes is created randomly as a basis of the evolution process. From this, they are tested by the algorithm to assess their fitness, just as in evolution the ‘f ittest ’ or most optimal chromosomes are selected while the others are discarded. These selected chromosomes are then used to enter into the next stages, crossover, and mutation. In crossover, along with the selected chromosomes, new child chromosomes are created from those selected through this process. The method to interchange genes from one chromosome with another to create parent chromosomes which will then also be tested. Furthermore, the mutation is also a reproductive process that works through randomness, that is, by changing the genes of parents 1 Constrained And Unconstrained Optimization Problems. (n.d.). Retrieved September 2, 2022, from https://thesassway.com/what-is-optimization-in-computer-science/. 2 Dewdney, A. K. (2001). The new Turing omnibus: 66 excursions in Computer Science . Henry Holt. 3 Darwin, C. (1859). On the origin of the species . England. 4 Wikimedia Foundation. (2022, August 18). Travelling salesman problem . Wikipedia. Retrieved September 3, 2022, from https://en.wikipedia.org/wiki/Travelling_salesman_problem#cite_ref-1. 5 Daniells, L. (n.d.). The travelling salesman problem . Libby Daniells. Retrieved September 4, 2022, from https://www.lancaster.ac.uk/stor-i-student-sites/libby-daniells/2020/04/21/the-travelling-salesman-problem/.
62
Made with FlippingBook - Online catalogs