CSCI964 - Computational Inteligence - Autumn Session 2018 Page 1 Aim: This asignment is intended to provide basic experience in solving dificult problems with Genetic Algorithms (GAs). After having completed this asignment you should know how to implement a GA in C++ and find a near optimal solution to hard problems like the Traveling Sales Person Problem (TSP). Preliminaries: In the TSP, the goal is to find the shortest distance betwen N different cities. The path that the sales person takes is called a tour. The following example shows a near optimal tour betwen 10 cities. To test every posible path for an N city tour requires N! math aditions. For example, a 30 city tour would be 2.65 X 1032additions. Asuming 1 bilion additions per second, this would take over 8,000,000,000,000,000 years. Adding just one more city would cause the number of aditions to increase by a factor of 31. Obviously, this is an imposible solution to find mathematically. However, a genetic algorithm (like that shown above) can be used to find a near perfect solution in very little time. The basic concept of Genetic Algorithms is to simulate Darwinian evolution by implementing survival of the fitest. To solve the traveling sales person problem using a GA, first create a group of many random tours in what is called a population. These tours are stored as a sequence of numbers representing cities. Second, produce a new population by repeatedly picking 2 of the beter (shorter) tours from the population (ie parents) and by combining them using the crosover operator to create 2 new solutions (ie children) in the hope that they create a better solution. The mutation operator can also be applied to improve the chance of finding a shorter tour. Crossover is performed by picking a one or two random points in the parents’ sequences and switching the numbers (representing cities) in the sequence betwen the points. The dificulty in using a GA to solve the TSP is in crosing over the cities of parent solutions to produce child solutions. For example, as show below, crosing over the cities in the parents has resulted in City 1 occurring twice in Child 1 and City 5 occuring twice in Child 2. Furthermore, City 1 is mising in Child 2 and City 5 is mising in Child 1. Consequently, a more complicated crosover operator must be used to prevent this occurring. CSCI964 - Computational Inteligence - Autumn Session 2018 Page 2 Parent 1 1 2 3 4 5 Parent 2 3 5 2 1 4 Child 1 1 2 3 1 4 Child 1 3 5 2 4 5 Assignment Specification: To complete this asignment you are to implement a genetic algorithm for solving the TSP Tol Road problem. The TSP Toll Road problem is the same as the general TSP problem except that the cities have types (1:capital, 2:regional 3:country) and the cost (cents/km) of traveling betwen two cities depends on their type. The objective is to visit al cities at minimum cost. The table below shows the cost of traveling betwen diferent types of cities: For example, to travel betwen a regional city (type-2) and a capital city (type-1) that are 100km apart it would cost 10km x 7.5c = $7.50 . Data: Thre data files are provided containing 10, 20 and 50 data items. Each data item represents the coordinates (x, y) of each city (in kms) and the city type (1:capital, 2:regional, 3:country). To asist with this task, a bare-bones GA writen in C++ is provide in the file “ga.cp”. However, this GA is for solving problems represented with bit strings and wil ned considerable modifications and enhancements to make it capable of finding solutions to the TSP. Your completed program should acept the filename of the TSP data file as a comand line argument. If no filename is given your program should ask the user to enter the filename via the keyboard. The output of your program should show the minimum tour distance achieved by each generation. However, if this produces more than two pages of output, in your final program, modify your code so that every 5th, 10thor 20thgeneration is displayed. To receive ful marks for this asignment the folowing steps must be completed. (Note: these steps do not have to be implemented in the order given. Step 1 is worth 4 arks. Step 2 is worth 1 mark, Step 3 is worth 2 marks and Step 4 is worth 3 marks.) Step 1: To implement the TSP on the code in the file ga.cpp, begin by writing a function to read a data file containing the locations of the cities and their type into a dynamically allocated array. Then alter the Init(), Crosover(), Mutate() and EvaluateFitnes() functions apropriately to handle the TSP Toll Road problem. You are encouraged to design your own algorithms for these functions to get your GA performing optimally (se Step 4). However, to help you get started, the folowing sugestions are offered. Init() must be modified to load the initial pop members with random cities. Cities are represented with the numbers 0..n-1 where n is the number of cities in the data file. Make sure no city ocurs more than once in each member. (Note: the first number in the given data files is the number of cities in the file. Use this number to appropriately alocate the size of member arays etc. so your code wil run on any of the given data files. City locations are represented by (x,y) coordinates (ie integers: 0..999).) Crosover() can be implemented in a variety of ways. A search of the internet should reveal some useful examples. You should make sure that the crosover operation does not result in any ofspring containing duplicate cities. This can be done by locating any duplicate cities and replace each duplicate city with a mising city. (But which mising city?) Mutate() can be implemented by swapping two or more randomly selected cities in the member. Feel free to experiment with this to obtain increased performance. CSCI964 - Computational Inteligence - Autumn Session 2018 Page 3 EvaluateFitnes() should calculate the fitness by ading al the distances betwen visited cities times their cost to get the tour cost. This wil result in the fitest cities having the smallest cost. Thus you may have to modify how the BestMember is obtained and how parent selection is done. (Step 3 has more info on this.) Step 2: To avoid the large expense of calculating the same distances during each fitnes evaluation, provide an n x n lokup table of the cost of traveling between cities where n is the number of cities to be visited. Thus, when fitneses are calculated the cost of traveling betwen two cities can be loked up from the table more quickly. Step 3: involves providing your GA with two parent selection options. To do this, implement roulette whel selection and provide a global constant to switch your GA betwen Tournament or Roulete Whel selection. The folowing algorithm is ofered as a sugestion for implementing roulete whel selection: Copy fitneses into a temp aray Subtract the minimum pop fitnes from each fitnes to normalise them Subtract each normalised fitnes from the normalized maximum pop fitnes to get the scaled fitneses Generate a random number between 0 and the sum of all the scaled fitnesses Set TempSum to 0 for i=0;iRandomNumber) return i; } This should work, however beter performance may be achieved by scaling the fitneses such that the fitest member ocupies no more than 2 times as much space on the roulete whel as members with average fitnes. Step 4: Run your GA on al thre data sets and experiment with diferent parameters (e.g crosover mutation types and mutation crosover probabilities) so that your GA finds the cheapest path in the minimum number of generations. Write up the res代做留学生UNIX 程序、C/C++ TSP课程设计代写、代写留学生Autumn Session程序ults in your report. Step 5: Now modify your crosover and mutation operators so that the amount of change they cause to individuals becomes les as evolution progreses. Describe the modifications you have chosen to make in your report. Provide a brief coment block at the botom of your program to explain the measures you have taken and the parameters you have chosen to achieve your result. Submit your code with your optimal parameters in place so your optimal solution can be demonstrated. Make sure the output from your program does not occupy more than one or two pages. (Note: it is ok to just print the fitnes of every 5thor 10thor 20thgeneration.) The above is to be taken as a guide only. It is advised to do research on GAs and the TSP problem and make any changes you think fit to improve the performance of the GA on the TSP problem. Please provide references if you use techniques found via your research. Your report should contain suficient description, discussion and analysis, in particular, (1) Details of each step (above) of your implementation and any improvements. (2) The settings, results and performance (graphs) of your GA based on your experiments. (3) Atach a printout of your code. Ensure it is neat, wel comented and easy to understand. --- Part 2 (Dep Learning, 10 marks) --- Aim: This asignment is intended to provide basic experience in using the recently released open source software library TensorFlow developed by Google Brain Team to implement and design simple neural networks for image clasification. After having completed this asignment you should know how to realize a linear and convolutional neural network with TensorFlow, understand its training proces, and interpret the classification result. CSCI964 - Computational Inteligence - Autumn Session 2018 Page 4 Assignment Specification: 1. Instal TensorFlow by folowing the instruction at https:/ww.tensorflow.org/instal/. After that, verify it by following https:/ww.tensorflow.org/instal/instal_mac#ValidateYourInstalation. 2. (2 marks) Run the simple multinomial logistic regresion (a three-layer neural network without a hidden layer) by reading and following https:/ww.tensorflow.org/get_started/mnist/beginners. Ensure that you can obtain the clasification acuracy around 92%. Describe what this network does and the key steps (such as defining the networks, training, and test) with your own words. Vary the parameters like the number of training example, the learning rate, and the batch size to observe the classification accuracy. Describe your observation. 3. (3 marks) Run the basic convolutional neural networks (a multi-layer neural network with hidden layers) by reading and folowing https:/ww.tensorflow.org/get_started/mnist/pros. Ensure that you can obtain the clasification acuracy around 9%. Describe what this network does and the key steps (such as defining the networks, training, and test) with your own words. Vary the parameters like the patch size and the number of features (defined in [5, 5, 1, 32] and [5, 5, 32, 64]) to observe the clasification acuracy. Describe your observation. 4. (5 marks) The folowing images are from the international competition on cel image clasification hosted by International Conference on Patern Recognition in 2014. The images have ben pre-partitioned into training set (8701 images), validation set (2175 images), and test set (2720 images), which are provided with this assignment instruction. In adition, a .csv file is enclosed. It contains the category of each image. This file consists of two columns: the first column is the image IDs of all the 13,596 images, and the IDs are consistent with the names of the images in the thre sets; and the second column is the category of the cel image. This is an open task. You are expected to use the knowledge learned from this subject to achieve the clasification acuracy on the test set as high as possible. Note that you are fre to use any classification techniques, toolboxes, software packages, and programing languages to acomplish this task. For your reference, our research shows that the clasification accuracy of 96% is achievable. In adition, a journal paper is enclosed in this asignment for your reference. 5. Write a report on each of the three parts (parts 1 and 2 shal be put into one single report). It shall include 1) A brief introduction on the MNIST data set used in part 2; 2) As indicated in the point 2 above, describe what this network does and the key steps (such as defining the networks, training, and test) with your own words. Vary the parameters like the number of training example, the learning rate, and the batch size to observe the clasification accuracy. Describe your observation; 3) As indicated in the point 3 above Describe what this network does and the key steps (such as defining the networks, training, and test) with your own words. Vary the parameters like the patch size and the number of features (defined in [5, 5, 1, 32] and [5, 5, 32, 64]) to observe the classification accuracy. Describe your observation; 4) For the open task in point 4 above: a. Describe the clasification technique, the tolboxes and the language you use; b. Describe and plot the structure of the clasification system with a diagram; c. Describe how you proces and prepare the image data when aplicable; d. Describe how you chose the parameter of this clasification system; e. Describe the training and validation acuracy and plot them when applicable; f. Report the final clasification acuracy on the test set; g. Elaborate your observation during the course and provide detailed analysis. Submit: Submit your program on UNIX via the submit comand before the deadline and hand in your report with a cover page to in the lecture. For part 1: C/C++ code that is compliable and runable on the UNIX platform; Before submiting your code check the format to ensure the format and newlines appear corect on UNIX. (Marks wil be deducted for untidy or incorrectly formated work.) To avoid formating problems avoid using tabs and use 4 spaces instead of tab to indent you code. Make sure your file is named: tsp.cp. CSCI964 - Computational Inteligence - Autumn Session 2018 Page 5 For part 2: Provide all the source code of your programs for this part (including points 2, 3 and 4). Since you may use programing languages other than C/C+ and other libraries or packages, it is not required that your code be runable on the UNIX platform. However, you may be asked to demonstrate your program on your laptop or a computer that has al the needed environments. Put both part 1 and part 2 into a single report. Do not write two separated reports. Submit using the submit facility on UNIX ie: $ submit -u login -c CSCI964 -a 3 assignment3.zip where login is your UNIX login ID. We wil atempt to run your program of part 1 on banshee. If problems are encountered running your program, you may be required to demonstrate your program to the coordinator at a prearanged time. If a request for a demonstration is made and no demonstration is done, a penalty of 2 marks (minimum) wil be applied. Marks wil be awarded for a comprehensive report, corect progra design, ipleentation, style. and performance. Any request for an extension of the submission deadline must be made by aplying for academic consideration before the submision deadline. Suporting documentation must acompany the request for any extension. Late asignment submisions without granted extension wil be marked but the mark awarded wil be reduced by 1 mark for each day late. Asignments wil not be acepted if more than one wek late. & 转自：http://ass.3daixie.com/2018052758777229.html