904 Chapter 15 Heuristic Methods for Approximate Discrete Optimization ALGORITHM 15E: GENETIC ALGORITHM SEARCH Step 1: Initialization. Choose a population size p, initial starting feasible solutions x a generation limit? and population subdivisions Pe for elites, for immigrants, and for crossovers. Also set generation index --- Step 1: Stopping. Ift= tmax. 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 pe 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 t + 1 population Step 4: Crossovers. Choose pc/2 nonoverlapping pairs of solutions from the generation 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 te-t+1, and return to Step 1. Solution Encoding for Genetic 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 If solutions are encoded merely by displaying the drilling sequence, two that might come together as crossover parents would be (3.1,2,4.7.8.5.9.10,6) and (7.2.3, 1.6,5.8.4.9.10) Crossing over the solutions after component j = 6 would yield children (3.1.2.4.7.8.8.4.9. 10) and (7.2.3.1.6,5,5,9,10,6) Neither is a feasible drilling sequence because some holes are visited more than once and some never. A poor choice of solution encoding has made it almost impos- sible for crossover to produce useful new solutions Principle 15.13 Effective genetic algorithm search requires a choice for encoding problem solutions that often, if not always, preserves solution feasi- bility after crossover We can obtain a better encoding in the NCB application by a technique known as random keys. Definition 15.14 Random-key methods for genetic algorithms encode solu- tions indirectly as a sequence of random numbers. Then solutions are recov- ered indirectly by making the first encoded index that of the lowest random number, the second the next lowest, and so on. 3. (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 tmax 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: initila 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 hat 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. You may solve this question in Excel for convenience. 904 Chapter 15 Heuristic Methods for Approximate Discrete Optimization ALGORITHM 15E: GENETIC ALGORITHM SEARCH Step 1: Initialization. Choose a population size p, initial starting feasible solutions x a generation limit? and population subdivisions Pe for elites, for immigrants, and for crossovers. Also set generation index --- Step 1: Stopping. Ift= tmax. 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 pe 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 t + 1 population Step 4: Crossovers. Choose pc/2 nonoverlapping pairs of solutions from the generation 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 te-t+1, and return to Step 1. Solution Encoding for Genetic 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 If solutions are encoded merely by displaying the drilling sequence, two that might come together as crossover parents would be (3.1,2,4.7.8.5.9.10,6) and (7.2.3, 1.6,5.8.4.9.10) Crossing over the solutions after component j = 6 would yield children (3.1.2.4.7.8.8.4.9. 10) and (7.2.3.1.6,5,5,9,10,6) Neither is a feasible drilling sequence because some holes are visited more than once and some never. A poor choice of solution encoding has made it almost impos- sible for crossover to produce useful new solutions Principle 15.13 Effective genetic algorithm search requires a choice for encoding problem solutions that often, if not always, preserves solution feasi- bility after crossover We can obtain a better encoding in the NCB application by a technique known as random keys. Definition 15.14 Random-key methods for genetic algorithms encode solu- tions indirectly as a sequence of random numbers. Then solutions are recov- ered indirectly by making the first encoded index that of the lowest random number, the second the next lowest, and so on. 3. (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 tmax 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: initila 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 hat 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. You may solve this question in Excel for convenience