Fill in
Family Name: /Fill In
Other Names: /Fill In
G52AIM (Artificial Intelligence Methods)
Lecturers: Graham Kendall & Rong Qu
Academic Year 2009-2010
(Coursework I –The 0-1 Multidimensional Knapsack Problem)
1
Name:UsernameG52AIM : Combinatorial Optimization using AI methods Page :
Part I. Instructions
These instructions give you guidance as to how you should write the report for your coursework. Once you have read these instructions you can delete Part I.
Before you start, double click the header and footer and replace “Name/Username” with your own name and your user name.
You should use the supplied headings for your report. If you change them, then there is a good chance you will lose marks as I will have trouble marking it.
Do not exceed three sides of A4 and do not use a font size smaller than 10 point. This limit does not include the title page.
The deadline for this coursework is Tuesday 23rd March 2010 at 16:00. You need to submit your report as hardcopy to the school reception office A31.
Anybody handing in their work after the deadline will suffer a 5% reduction of their mark for each day (or part) that their work is late. Please note, that late work still has to be submitted to A31. I cannot accept work from you.
Any work handed in after 16:00 on 7th April 2010 will receive zero marks.
This coursework accounts for 5% of the marks for this course.
You must be very careful not to commit plagiarism! Cite your sources, and if you need to quote other work then make it very clear that it is a quote and not your own work. If at all in doubt about what is acceptable then ask for guidance!
Assignment
During the course so far we have looked at various domains and search techniques. This assignment asks you to investigate the 0-1 Multidimensional Knapsack Problem (MKP), and provide a report as to how the search techniques have been found to work on this domain, or might be applied to the domain. This coursework is deliberately rather open-ended and loosely specified. It is intended to test whether you can discuss ‘AI Methods’ but in a context not provided in the lectures.
Answer the following:
A.Inyour own words give a brief description of the 0-1 MKP.
B. Give a mathematic description of the 0-1 MKP, and briefly explain it.
C.For the 0-1 MKP, describe how optimisation methods/algorithms:
1.Have already been applied.
2.Might be applied.
Remarks and Hints
This probably entails that you do a short literature/web search. Generally, the idea is that you web-search for the topic with appropriate keywords, and try to find appropriate research papers. On this well-known topic many sources should be easily found. Often Wikipedia is a good starting place. If stuck, then try one of the papers in the textbook, and then look at one of the papers that it cites. For the 0-1 MKP problem, be clear about constraints, decision variables, fitness function (when appropriate), etc.
For the search be clear about (as appropriate) meta-heuristics, neighbourhoods, etc. Note that not all methods will have been covered by this point of the course, and so if possible focus on those that have been covered, or just report the methods used in other meta-heuristics.
Marking Scheme & Evaluation Criteria
I am not expecting you to demonstrate a deep understanding of the domain and methods; however, you will be evaluated on being able to demonstrate that you have understood at least some of the basic ideas.
You should structure your answers using the following headings, i.e. A. B. and C in Part II.
Part II. Report
A. A brief description of the 0-1 MKP. (25%)
B. A mathematic description of the 0-1 MKP, and a brief explanation. (25%)
C. Optimisation methods for the 0-1 MKP. (50%)