CSCI964 - Computational Inteligence - Autumn Session 2018 Page 1
Assignment 3 (Due: 4:30PM, Monday 21 May) 20 marks
--- Part 1 (Genetic Programing, 10 marks) ---
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 10
32
additions. 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.
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 5
th
, 10
th
or 20
th
generation 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 results 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 5
th
or 10
th
or 20
th
generation.)
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.
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.