Rock Street, San Francisco

Genetic algorithmThis chapter will explain the Traveling Salesman Problem which will be solved with a genetic algorithm (GA). A GA is great for solving complex search problems. GA’s are based on evolution by natural selection. It essentially replicates the way in which nature uses evolution to find solutions to real world problems.How a Basic Genetic Algorithm WorksThe GA will take the fundamental properties of natural selection and apply them to whatever problem we are trying to solve.The basics for a GA are:InitializationEvaluationSelectionCrossoverMutationRepeat from step 2 until a termination condition is met.InitializationThe population of a GA is randomly generated and can be any size, from just a couple of individuals to hundreds or thousands.EvaluationEach member of the population needs to be evaluated. This evaluation is done by performing a fitness calculation for that specific member. The fitness calculation is a custom calculation for each problem and what the requirements are for the fitness. For example, a quicker algorithm gets a better fitness score or the individual who gets the furthest gets a better fitness score.SelectionThis part of the algorithm focuses on improving the overall population and does this by only keeping the best members and discarding the worst. There are several different selection methods to select the fittest members. Elitism is one of the selection methods. This ensures that the best member, or the top 5 members, of a population is copied to the next population. This method can very rapidly increase the performance of a GA. It does not allow to lose the best members of the population.CrossoverIn the crossover phase of the algorithm new members of the population are created by combining 2 existing members of the previous population. The desired result is to create an even fitter offspring which inherits the best traits from each of its parent.(image caption)Figure x, The Crossover Phase Visualised. Source: (Jacobson, 2018)MutationIf no mutation is added to the algorithm every possible combination we can create would be in our initial population. To tackle this problem mutation, or randomness, is added. Each member of the population has a genome which defines the member. There is a small chance that one part of the genome is randomized into another number, or whatever is used in the genome.RepeatNow all the calculations for an iteration are completed the algorithm starts a new cycle from step 2 evaluating the newly created population on the fitness score and create a new population.Applied to the Traveling Salesman ProblemTo apply the algorithm to the TSP a few modifications had to be done to the standard GA. Lee Jacobson (Jacobson, 2018) wrote a solution to this problem in Java. In his solution Jacobson tackles several problems that occur when applying crossover and mutation to a member of the population. The genome that Jacobson uses is an array of numbers, these numbers specify the order of the traversed cities. As told earlier in Chapter 2, cities can only be visited once. If the standard crossover and mutation methods are used there is a chance that not all the cities are visited or a city gets more than 1 visit. This automatically makes it not the most optimal route and thus is an invalid genome. It is better to ensure this can not happen instead of discarding invalid members and thus not waste any processing power.Crossover Modified for TSPThere is a crossover method named ordered crossover that is able to produce a valid route.