G5BAIM Coursework for Academic Year 2001-2002

Introduction

The closing date for this coursework is Thursday 2nd May 2002 at 16:00. You should hand in your work to the secretaries in B33.

However, the secretaries will accept the coursework up until 9th May 2002 at 16:00. This extra week is to allow for anybody who has problems with their printer, their disc crashing, job interviews, colds, flus, other minor illnesses etc. etc. That is, I am granting an automatic extension for anybody who has problems.

Anybody handing in their work after the 9th May still has to hand it into the secretaries but you will suffer a 5% reduction of your mark for each day (or part) that the work is late.

Any work handed in after 16th May will receive zero marks.

In summary, you should finish the coursework by 2nd May. If you can’t do that, because of some catastrophe, then I am granting an automatic weeks extension. There will be no further extensions.

DO NOT TREAT THE 9th May AS THE DEADLINE IN CASE YOU HAVE PROBLEMS

This coursework accounts for 25% of the marks for this course.

Hand in requirements

  1. You are required to hand in the following
  2. Title Page (see Appendix A)
  3. A report using the headings given below. The report should not exceed four sides of A4 (excluding the title page) and should be in a font size of ten or greater. The report MUST be typed.
  4. A listing of your program. Print in an 8 point font and use wide margins.
    The program listing will not be used in the marking scheme, but will be used to check for plagiarism. The plagiarism method will compare your program against programs written by other students and also against programs that are downloadable from the web. Any form of plagiarism will result in a 0% mark for the coursework and possibly withdrawal of the credits for the course.
  5. No other sheets are necessary (i.e. do not add any additional appendices)
  6. Every page should, at least, have a page number and your username on it
  7. When you hand in your assignment, please do not put it inside a plastic/cardboard wallet/folder. Stapled, top left, is best (rather than a paper clip)

Some of the above may sound a bit pedantic but when I have many pieces of coursework to mark, small things such as those listed above really do help 

Assignment

Your task is to write an evolutionary or meta-heuristic algorithm that is able to minimise the functions given below. That is you must find suitable values for x such that the value returned by f(x) is the lowest you can find.

You are allowed to choose from any of the techniques we have covered on the course but you must use the same technique for each function. If you would prefer to use another technique then you must check with me first but it is likely that I will refuse as I feel you have enough techniques to choose from that have been covered as part of the course.

The functions you need to minimise are as follows. I have written them is pseudo program code so that you might find it easier to convert to a suitable programming language.

Function 1

f1(x)=10·n+sum(x[i]^2-10·cos(2·pi·x[i]))

wheren = 10

i=1..n

and x[i] is constrained to –5.12..5.12 (i.e. –5.12 <= x[i] <= 5.12)

For example, given the values below for x, then f1(x) would return 140.4048625 (I am showing you these values so you can check that you have implemented the function correctly).

x[1]=1.8605

x[2]=3.4505

x[3]=1.776

x[4]=2.0405

x[5]=4.0625

x[6]=0.931

x[7]=-1.2945

x[8]=-5.1015

x[9]=1.759

x[10]=0.279

Function 2

f2(x)=sum(100·(x(i+1)-x(i)^2)^2+(1-x(i))^2)

wheren = 10

i=1..n-1

and x[i] is constrained to –2.048..2.048 (i.e. –2.048 <= x[i] <= 2.048)

For example, given the values below for x, then f2(x) would return 2662.738336 (I am showing you these values so you can check that you have implemented the function correctly).

x[1]=1.62

x[2]=0.675

x[3]=0.87

x[4]=-1.677

x[5]=-0.78

x[6]=-0.65

x[7]=1.042

x[8]=1.09

x[9]=-0.12

x[10]=0.008

Function 3

f3(x)=sum(-x(i)·sin(sqrt(abs(x(i)))))

wheren = 10

i=1..n

and x[i] is constrained to –500..500 (i.e. –500 <= x[i] <= 500)

For example, given the values below for x, then f3(x) would return -108.5722199 (I am showing you these values so you can check that you have implemented the function correctly).

x[1]=200.762

x[2]=-10.765

x[3]=-67.78

x[4]=120.67

x[5]=12.675

x[6]=8.098

x[7]=-10

x[8]=-19.567

x[9]=-256.67

x[10]=12.67

Report

Don’t forget, no more than 4 A4 sides, a font size of 10 or larger and it must be typed.

Use the headings given below to structure your report.

Take into account the marks for each section of the report and use those marks as a guideline as to how much each section requires.

1. Choice of Technique

Why have you chosen the technique you have, what other techniques did you consider and why did you not use them?

3%

2. Representation

How have you chosen to represent the problem (e.g. binary, floating point etc.) and why did you choose that representation? What alternatives did you consider?

2%

3. Program Design

Give an overview of the design of your program.

2%

4. Operators

Describe the operators you have chosen for your choice of technique. For example, if you have used simulated annealing or tabu search how do you move from one solution to another. If you used a genetic algorithm what crossover and mutation operators have you used?

5%

4. Operators

Describe the parameters you used and why. For example, what was your simulated annealing cooling schedule, what was the population size for your genetic algorithm etc?

5%

5. Run Time & Graphs

How long did it run for each function (not elapsed time, give the number of f(x) evaluations executed). Present three graphs showing the value of f(x) plotted against the number of evaluations of the objective function.

2%

6. Results

For each of the three functions what was the best result you achieved (give the values of x[i] and also the value of f(x).

1%

7. Discussion

Comment on your results and discuss what you have learnt from this assignment.

5%

Revision 1.00 (25th January 2002)Print Date : 30-Jan-01

Appendix A – Title Page

Login Name:
Family Name:
Other Names:

G5BAIM (Artificial Intelligence Methods)

Lecturer : Graham Kendall

Coursework for Academic Year 2001-2002

(Function Optimisation)

Revision 1.00 (25th January 2002)Print Date : 30-Jan-01