(25 points) Apply the genetic algorithm (Algorithm 15E) on page 904 in Chapter 15 to a TSP with 10 cities. Let the population size be 10. Start with random solutions. Use random keys for your solution encoding to overcome the duplication issue during crossover. Let tmas be 10. At each iteration randomly choose two solutions as parents and a crossover point, and then generate two children. Keep the population size constant at 10, i.e. discard the worst two solutions at the end of each iteration. Also at the end of each iteration, apply-with 5% probability, i.e. not always-a mutation operator to a randomly chosen solution. The mutation operator you should apply should simply interchange two randomly chosen cities in the solution. Make sure to provide all the details of the algorithm: initial population, chosen parents at each iteration, crossover points at each iteration, produced children at each iteration, applied mutation at each iteration (if any), discarded solutions, all of the generated random numbers. Moreover, provide a table that shows the best and worst solution value at each iteration, and the incumbent. Also make sure to provide your distance matrix. Remember that the total traveling distance should include the return trip to the origin form the last visited city. Solve this question in Excel. 904 Chapter 15 Heuristic Methods for Approximate Discrete Optimization ALGORITHM 15E: GENETIC ALGORITHM SEARCH Step 0: Initialization. Choose a population size p, initial starting feasible solutions x)..... x), a generation limit tmax, and population subdivisions pe for elites, p for immigrants, and pe for crossovers. Also set generation index to. Step 1: Stopping. Ift-t max. stop and report the best solution of the cur- rent population as an approximate optimum. Step 2: Elite. Initialize the population of generation t + 1 with copies of the p best solutions in the current generation. Step 3: Immigrants/mutations. Arbitrarily choose p new immigrant fea- sible solutions, or mutations of existing ones and include them in the 1 + 1 population Step 4: Crossovers. Choose pc/2 nonoverlapping pairs of solutions from the generation t population, and execute crossover on each pair at an in- dependently chosen random cut point to complete the generation t + 1 population Step 5: Increment Increment + 1. and return to Step 1 Solution Encoding for Generic Algorithm Search Just as design of an ordinary improving search requires careful construction of a move set (principle 15.5), implementations of genetic algorithms require judicious choice of a scheme for encoding solutions in a vector. To see the difficulty, return to our NCB drilling application It solutions are encoded merels by displaving the drilling sequence. two that