C042007 Coursework

Set by: Ben Paechter

Due Dates: Part 1 - Tutorial Week 7

Part 2 - Tutorial Week 10, End of week 10

The equal grouping problem involves splitting a number of items into a number of groups in such a way that the collective weight of the items in each group is as equal as possible. The groups can contain different numbers of items. For this exercise we will always split the items into 10 groups. The measure of how good a candidate solution is will be the difference in weight between the heaviest group and the lightest group - this value should be minimised.

Outline Java code using a direct representation is provided on the “teaching” part of Ben Paechter’s web site:

This code performs some basic operations:

  • a weight file is read in
  • a population is initialised
  • a method for evaluating chromosomes is provided
  • a loop for running the EA is given which terminates after one minute.

You are not required to use this code and it is anticipated that some of the best submissionswill either not use the code directly or will have made substantial changes to it.

What to Do

Part 1 (Marks - 10%): Write a program to solve the equal grouping problem using an evolutionary algorithm. Your program should be designed to solve a problem with 500 possible items given 1 minute of run time on the machines in your tutorial cluster. The program should automatically stop and write the output file after 1 minute. To score 10 marks on this part of the problem you must demonstrate your program at the tutorial in week 7. You are not expected to have optimised the algorithm at this demonstration.

Part 2:

Experiment with your program to improve it as much as possible. You can experiment with population sizes, new operators and so on. If you wish, you may extend your program to include new features, such as population seeding, hybridisation with other methods etc. During the tutorials in week 10 you will be given three new input files and we will have a competition to see how the finished programs compare with each other. Up to 5 marks will be awarded for each file depending on how the single run compares with that of other students. (Competition Marks - 15%).

Input file:

The input file called “input.gpg” will be in the following text format (all values are integers)–

1st line – Number of items

For each item, one line containing the weight

Sample input files (500 items) are available on the web page.

Output File:

Your program must produce an output file called “output.gpg” in exactly the following form:

One line for each item containing an integer between 0 and 9 representing the group into which that item has been placed.

A program for checking output files (which requires one file called input.gpg and one called output.gpg to be in the directory that the program is run in) is available at the web site.

Programming Language:

You can write the program in any language you like. Some languages, e.g. Visual Basic, may be slow to run and so less can be achieved in the one minute run.

Part 2 Hand in:

You should hand in the following at before Friday 3.00pm of week 10:

  • A report containing
  • Cover sheet
  • An abstract giving an overview of the algorithm (representation, operators, parameters, etc) that you finally used and methods you discounted through experimentation – maximum one sheet A4 12 point. (Marks 20%)
  • An experimental plan – showing the experiments that you decided to conduct (remember that since evolutionary algorithms are non-deterministic you should use several runs and statistical methods to compare algorithms) – maximum one sheet A4 12 point. (Marks 20%)
  • Summary of Results – summarising the results of the experiments – maximum one sheet A4 12 point. Graphs of results and meaningful statistical analysis of the results will attract marks(Marks 15%)
  • Conclusions – detailing the conclusions that you made, and the lessons you learnt, from the experimental results and the exercise as a whole– maximum one sheet A4 12 point. (Marks 20%)

Please don’t go over the maximum section sizes as this will result in you losing marks. You can include appendices if you wish, so long as they are referenced in the main report – however, there is no guarantee that these will be read when marking the report.

  • You must also e-mail your source code and executable. The e-mail message must contain the subject “EC Coursework”. Attached to the e-mail should a zipped directory containing:
  • your source code
  • a compiled program
  • a text file called readme.txt which contains instructions for running the program

Marking Scheme Summary

Part 1 Demo10%

Competition15%

Abstract20%

Exp. plan20%

Results15%

Conclusions20%