Nature-Inspired Computing (COMP701) (北美程序代写,加拿大程序代写,Matlab代写)

北美程序代写 加拿大程序代写 Matlab代写

A code editor window should pop up and the Matlab code for the traveling salesman algorithm should be shown

联系我们
微信: biyeprodaixie 欢迎联系咨询

本次CS代写的主要涉及如下领域: 北美程序代写,加拿大程序代写,Matlab代写

Nature-Inspired Computing (COMP701)

1. Workshop in Matlab.

2. Details of assignment 1.

Introduction:

This booklet introduces you to the workshop and associated assignment 1 (the first of your two assignments for the paper). The first assignment uses genetic algorithms (GAs) and the second assignment uses artificial neural networks (ANNs).

You can do both assignments using Matlab or use Weka for the ANN part.

The ANN assignment will be introduced later in the paper.

Recommendation: Do not try to do the assignment without completing and understanding the associated workshops. Do not complete your report writing until you have seen the two specimen research papers included in the ‘Assignments’ folder in the AUT On_Line resources for this paper.

NIC Workshop and Coursework (Part 1) using MATLAB Genetic Algoritihms Toolbox Go to http://www.mathworks.com/help/toolbox/gads/index.html. You may need to refer to the material on these pages at some point in your workshop or coursework for more detailed information. These workshop notes were prepared for earlier versions of Matlab. It is possible that later versions of Matlab will have different screens and layouts as well as have different folder structures.

Objective of Workshop

(a) To get experience of optimization tools in Matlab.
(b) To run the GA demo as well as alter parameter settings.
(c) To prepare you for your GA coursework (at the end of this document).

Workshop activities

  1. Run Matlab. (e.g. Start > All Programs > Maths&Stats Tools > matlab> MATLAB R201 7 b).
  2. At the top you will see the current folder location. Use the small black right arrow to navigate to C:\Program Files\MATLAB\R2017b\examples\globaloptim\main.^1 Click to select this folder. You should see a number of files appear under ‘Current Folder’:
  3. Scroll down this list and select, by double clicking, the travelling_salesman_demo.m file.

1 There may be changes to directory structure depending on which image your computer has.

  1. A code editor window should pop up and the Matlab code for the traveling salesman algorithm should be shown. Matlab code is easy to interpret if you adopt a mathematical perspective. If any of you have used C or Visual BASIC, you won’t have a problem. In any case, the code you will be required to read is heavily commented. Click on the Editor tab at the top if it is not open.
  2. Read the first 27 lines of the file, especially the comments (prefixed by ‘%’) to understand what the code is doing.
  3. Go back to the top (make sure you go back to the very top of the file in the Editor window), and place the cursor at the start of the first line, without changing any of the contents of the file.
  4. Then move the mouse to ‘Run and Advance’ in the Editor window just beneath the Editor banner and click once. The cursor should move to the next section of the code. Nothing else will happen.
  5. You should narrow the Editor window so that you can see the Matlab Command Window, Workspace Window and Command History subwindows in Matlab. Click Run and Advance again and again.
  6. After your fourth ‘Run and Advance’ click, a Figure 1 dialog should appear that shows an outline of a country. Click Run and Advance again. Now you should see the cities that the salesman needs to visit. You may need to move windows around to see the map. Answer the following questions as you read through the code: Q1: Which country is being mapped?
Q2: How many cities are there? (You need to look at the code (line 28) or workspace area to
answer this question and the three following questions.)

Q3: How are the cities located in the country? (To answer this question, look at the x and y
axis labels.)

Q4: How are the distances between cities calculated? (To answer this question, look at line 53
of the code.)

Q5: What is the fitness function? (Look at lines 91-108.)
  1. Keep repeating Run and Advance several times until the algorithm has finished running (i.e. has found the optimal path). You should be watching the Command Window also to see the code running. You should try to read the comments in the code in the Editor window with each advance so that you can see what the algorithm is doing at each stage.
  2. The GA finally runs after about your tenth Run and Advance click. You will know that the algorithm is running when you see the map window (‘Genetic Algorithm’) changing. Wait until the algorithm finishes. You will see a route slowly emerge among the cities you see in the Figure 1 window.
  3. You may not have noticed, but as you clicked your way through the Matlab code, the right hand workspace window in the main Matlab interface was filled with entries. You will now use these entries for the second part of the workshop.
  4. Close the Editor without changing the file. Close the genetic algorithm maps.
  5. Move the Matlab main window to the centre of your screen so that you can access all parts of the right hand workspace.
  6. In the command window, you will see some output from the run you have just made. Make a note of the ‘fval’ value and note the generations in the ‘output =’ text. The ‘fval’ value represents the shortest route found so far. You should note these values by starting an Excel spreadsheet and creating two columns: fval and generations. Below is an example.
Q6: What is the fval value? Can you explain why the value looks so small?

Q7: What is the number of generations taken to find this fval? Look at the output in the
Command Window to answer this question.

Repeat nine times by moving the cursor back to the top of the code in the edit window. Run using
the ‘Run and Advance’ or simply the ‘Run’ button at the top of the Editor window, noting the fval
values and the number of generations after each run on the Excel sheet. Now calculate the average
fval value and average number of generations. You can use the Excel built-in ‘average’ functions for
this. Also identify the best run in terms of (a) fval and (b) number of generations.
Q8a: Are the best fval and number of generations values from the same run? If not, which is
more important, from your point of view?
  1. Return to the Editor window, where the script (code) for the TSP is displayed. Find line 2 8 and you should see “cities = 40” there. Change “40” to “20”. Then save the file. You will not be allowed to save back to the same demo name, so save the file as, say, “travelling_salesman_demo2.m” on a local directory or your memory stick. Then run the script using the ‘Run’ triangle at the top of the window. You may be asked if you want to change the path to include the folder you have recently saved your file to. Accept the change. You should now see the GA working for just 20 cities. Q8b: Compare the average fval and generations values for the 40 city runs with the 20 city runs. What do you notice? And what do you notice about the layout of the cities in the Genetic
Algorithm window each time you ran the GA? Were the cities fixed to the same locations each
time?

Increase the number of cities to any other number and repeat as many times as you like. Remember
to make a note of the fval values.

  1. Now comes the genetic algorithm interface GUI. You will repeat what you have just done, but this time using the GA GUI. Type ‘optimtool’ at the “>>” prompt in the Matlab command window, and you will now see a new window called ‘Optimization Tool’. (Ignore the warning.) In the top left hand corner of this new window, there is a ‘Solver’ subwindow. Find ‘ga – Genetic Algorithm’ and select it in this subwindow. See the next figure for what your screen should contain.

  2. Here comes the tricky bit. Go back to the Matlab workspace window which displayed your results, and copy and paste the fitness function value ‘@(x)traveling_salesman_fitness(x,distances)’ into the GUI ‘Fitness function’space.

  3. Now copy the value of ‘numberOfVariables’ from the workspace to the GUI ‘Number of variables’ space. (The figure above shows 200, but in your case it will be 20.) Finally, go to the Optimization Tool ‘File’ command and click on ‘Import options’. Click on ‘options (struct)’ (not ‘default options’) and then ‘import’. Ignore the warning message you get in the Optimization Tool window. What you have done is to use the travelling salesman demo code to set up a number of variables and parameters, the values of some of which you have now imported into the GA GUI for the remainder of your workshop. You will also need to follow this procedure when undertaking the coursework.

Note: make sure that the number of variables in the GUI is the same as the number of cities in
workspace subwindow. If they are different, you will get an error. If they are different, you will need
to edit the script in the editor window first, run the script to update the options, and then change the
number of variables in the GUI to the same number as the number of cities.

You need to understand the various options available to you. Before answering the question below,
click on the double-right chevron here.

A Quick Reference panel opens. As you answer the following questions concerning the default
parameters/options for the GA, read what the various options are for each selection in this panel.
You may find some of these options useful during your assignment.

Q9: What is the chromosome population size?

Q10: What is the fitness scaling function?

Q11: What is the selection function?

Q12: What is crossover fraction?

Q13: What are the stopping criteria?
  1. In the Optimization Tool GUI, click start. You will now see the same effects as when you ran the program from the Editor window, but you are now using the GUI. Congratulations, you have run your first GA from the GUI.
  2. You may notice that you have not received much information on what the GA has done. In the right hand part of the GUI, under ‘Options’, scroll down to the ‘Plot functions’ and click on ‘Best fitness’, ‘Selection’, ‘Genealogy’ and ‘Scores’. See http://au.mathworks.com/help/gads/genetic-algorithm- options.html for more information on these plot options. Click on ‘Clear Results’ and then Start, and watch what happens. At the end of the run, look at the bottom left hand corner of the Optimization Tool GUI. (You may get a message that there is not enough space to show the results.) Also, look just below the Start button you have clicked in the GUI.
Q14: What is the objective function value (‘fval’) now, and is it different from your answer to
Q6?

Q15: How many iterations/generations were required, and is this different from your answer
to Q7 and Q8?

Q16: If you h ave answered ‘yes’ to either Q14 or Q15 , why is there a difference?
  1. Click start several times to re-run the GA with 20 cities and see if you get any better values. Clear the previous results before you run the GA each time. You may wish to change the number of generations to a larger number to see if this leads to improvement in the shortest path fond.
Q17: After 10 runs, what is the lowest objective function value you get and how many
generations were required to reach it?

Q18: What is the highest objective function value you get and how many generations were
required to reach it?
  1. Keeping the ‘Best fitness’ box checked, check each of the following output options in turn and re- run the algorithm each time: Range; Scores; Selection; Genealogy.
Q19: What does the Range option do?

Q20: What does the Scores option do?

Q21: What does the Selection option do?

Q22: What does the Genealogy option do?

  1. You may have noticed that your actual shortest path solution is not displayed. This may vary from machine to machine due to size limitations of the ‘final point’ window (bottom left hand corner of GUI). After one particular run, click on ‘File’ in the Optimization Tool window, ‘Export to workspace’. In the subwindow, choose the final option ‘Export results to a Matlab structure named’ and click OK. Notice that a new entry now appears in the workspace (top right of main Matlab window, not the GUI). Double click the newly created ‘optimresults’ icon.

  2. Double click on ‘x’, double click on the one cell that is there, and you now have your route. In other words, the route is displayed as a sequence of city numbers on the top line of the table. A line links the specified number of cities together in the map.

  3. Finally, edit line 28 of the Editor window so that the number of cities is 200. Run the program from the editor window and wait until the algorithm stops. Then change the number of variables in the GUI to 200 and click Start. You will now have your first run of the GA on 200 cities.

Coursework #1 (worth 20%)

Your first coursework task is as follows: You are to find the best GA parameters for solving the TSP
for a specific map of 200 cities. First, you need to run the GA with Matlab’s 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 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 your assignment report.

Here are the tasks in more detail. You should pay particular attention to the questions in boldfont.

(a) 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. 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 do this as follows.
(i) Save the ‘distances’ and ‘locations’ variables to a temporary Matlab file in a directory of
your choice (don’t forget to select this directory as your current directory when re-loading).
(ii) Edit the Matlab code by removing (or commenting out) lines 29 to 39, and lines 46 - 56;
add a load command that loads the two variables ‘distances’ and ‘locations’ from the saved file
above;

(iii) Then save the new code version back to the temporary Matlab file. (b) This is just one way of making sure your map does not change with each run. See http://au.mathworks.com/help/matlab/ref/save.html and http://au.mathworks.com/help/matlab/ref/load.html for more information on how to save and load variable values for future use. Also, if you don’t 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. (c) 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’. (d) Now, for your first set of 10 experimental runs, change the number of cities to 40 (and fix the map/network 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. (e) 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. (f) 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. (g) 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. You

may need to use averages here as the method of comparison to identify whether changes lead to better or worse results. (h) 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. Again, you may need to use averages here to identify differences.

(i) 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. You may need to use averages here to identify differences.

(i) 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 (b) above.

Your report should describe the 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 5 double column pages, or 8 single column pages, including any screen shots, maps and tables of results. You can download double-column format templates from AUT Online (in the Assessment folder).

If you follow these instructions closely, you will obtain a good quality grade for your assignment (e.g. B or even B+). You have much scope for enhancing the experiments (and therefore getting extra marks that can take you to an A grade), if you wish, as follows:

  • Change the way that distances are calculated between cities so that the distances appear to represent kilometers/miles
  • Change or add your own chromosome mutation/recombination operators
  • Change or add another selection strategy
  • Change the number of cities
  • Change the problem to an asymmetrical problem
  • See if your chosen parameters continue to be the best parameters for even bigger city networks
  • Use statistical methods such as analysis of variance to identify whether changes lead to significantly different results

Your report should be written in a professional manner and in line with publication expectations. Please look at the paper, ‘A genetic algorithm for solving the travelling salesman problem’ by Philip, Taofiki and Kehinde, IJACSA, 2(1), 26-29, and available in the Assessment folder of AUT Online, for an example of how to construct a report containing experiments.

Notice how the paper first introduces the area and demonstrates to the reader that the authors understand the problem and what they are going to do about it. Then the paper introduces the methods they have adopted, followed by implementation. There is a separate section on results and discussion, followed by a separate conclusion.

If you follow this template, you will stand the best chance of maximizing your coursework marks for this assignment. Also, you will have gained valuable experience in how to present the results of research concisely and with evaluation, which is a skill much valued by employers everywhere.