You are to find the best GA paramaters for solving the TSP for a specific map of 200 cities. First, you need to run the GA with Matlabs fixed default parameters 10 times on the same 200-city network topology and record the fval values after each run. You will then experiment with different parameter settings for 40 cities and 100 cities (again using the same city network topology so that you can compare the effectiveness of your parameter changes.) You will run the GA again for ten times for different parameter settings for 40 and 100 cities. The task is for you to identify, on the basis of the results for 40 and 100 cities, what the best set of parameters will be for 200 cities. You will then use those parameters for 10 runs and compare the results with the original 10 runs for 200 cities against the default parameters. You will need to submit your results in a report. Here are the tasks in more detail. You should pay particular attention to the questions in boldfont. And dont forget that the spreadsheets have been introduced for a reason.

1. Your first task is to learn how to fix the 200 cities and their locations so that the map does not change each time you run the algorithm. Load the travelling salesman demo following the instructions from your first workshop. At line 28, you can change the number of cities to 200 or any number you like. When you save the file, you will need to save it in a separate folder. Add the path to your new file without changing the folder. If you change the folder, not all the functions in Matlab will be available to you. After you run the algorithm the first time, you will find the random distributions of the cities in the variable locations (a 200x2 matrix) and the distances between them in distances. You can fix the map on a University computer if you have a memory stick or use the desktop as a temporary filespace.

(i) After your first run with 200 cities, edit the Matlab code by removing (or commenting out with a % sign at the start of each line) lines 29 to 39, and lines 46-56.

(ii) Then save the new code version back to your memory stick or to your desktop or other temporary filespace. Call your code my_travelling_salesman_demo. Your file will have an .m suffix automatically to denote a Matlab code file. You will not be allowed to save the code back to the Matlab demos directory for obvious reasons. Do not change folder. Instead, add the path to your file when asked by Matlab.

(iii) For the remainder of your session, your map and distances are fixed. If you suspend your work and want to start again at a future time, load your my_travelling_salesman_demo file to get your fixed city network back.

2. This is just one way of making sure your map does not change with each run. If you use the GUI, you can use the same random city network as for the first run, but you will need to finish all your experiments in one session.

Also, if you dont like the way that distance is calculated based on graph coordinates in the range 0-1, you can multiply the distance calculation in line 53 of the code by, say, 1000, to give more realistic distances.

3. First, before you do anything else, run the GA with the default parameters 10 times on the same map of 200 cities, and store the results of the default population size, the output fval and generation values in three columns in a spread sheet. Call these columns ga_200_default.
4. Now, for your first set of 10 experimental runs, change the number of cities to 40 (and fix the topology using save and load). Change the population size to 40 and store the 10 fval results in separate columns of a spreadsheet, with a clear header. Then change the population size to 100 and run again for 10 times, storing the results of fval next to the previous results.
5. Now set the number of cities to 100 (with fixed topology) and repeat (c) with population sizes 40 and 100.

Does the change in population size between 40 and 100 make a difference between 40 and 100 cities? Explain and justify your answer. Depending on your answer, decide on the ideal population size for the remainder of your experiments.

6. Go back to your 40 city network and your chosen population size. Change the fitness scaling to proportional from the default rank. Run the algorithm 10 times and store the results of fval. Keeping the same parameter values, run the algorithm 10 times for 100 cities and store the results.
7. Change the number of cities back to 40. Change the fitness scaling to Top and run the algorithm 10 times, storing each result of fval. Do the same for 100 cities. (Your population size is fixed at this stage, so there is no need to change that.)

What is the best scaling method? Justify and explain your answer. Depending on your answer, decide on the ideal scaling method for the remainder of your experiments.

8. Go back to your 40 city network. Change the Selection method from stochastic uniform to Roulette. Run the algorithm 10 times, storing each result of fval. Change the selection method to Tournament and run the algorithm 10 times, storing each result of fval. Now repeat for your 100 city network.

Do the changes in selection method make a difference? Explain and justify your answer. Depending on your answer, decide on the ideal selection method for the remainder of your experiments.

1. Finally, return to your 40 city network. Change the number of generations from 500 to 1000 and run the algorithm 10 times, storing the results of fval. Repeat for your 100 city network.

Does the change in the number of generations make a difference? Explain and justify your answer. Depending on your answer, decide on the ideal number of generations for the remainder of your experiments.

(j) Now that you have decided on your best parameters based on your experiments with 40 and 100 cities, run the algorithm on 200 cities 10 times, using your own chosen parameters. Compare the fval results with your original results using default parameters in (c) above.

Your assignment report should describe your choice of best parameters for solving the TSP for 200 cities. Your analysis should explain why your parameter changes made a difference in comparison to the original default parameters. Your report for this part of the coursework should be no more than 6 double column pages, or 8 single column pages, including any screen shots, maps and tables of results.