ECMM409 Nature-Inspired Computation Assignment One: Problem Solving with an Evolutionary Algorithm Hand-out date: 28th October 2020 Hand-in date: 18th November 2020 Feedback: 9th December 2020 This CA is worth 30% of the overall module mark This is an individual assessment and you are reminded of the University's Regulations on Collaboration and Plagiarism. Task What you will do in this assignment is implement an evolutionary algorithm and apply it to the problem shown below. You will do a variety of experiments to help find out what parameters for the algorithm are best for this problem. Implementation of the algorithm can be in the programming language of your choice. In the following sections, basic details of the problem are provided, then basic details of the algorithm, and finally a step by step guide of what you are expected to do. The final section indicates what should be in your report to be handed in. The Problem Working for a bank, you have been asked to develop an evolutionary algorithm based system which will find the largest amount of money that can be packed into a security van. The money is separated into 100 bags of different denominations and the weight and value of the money of each bag is shown on the outside of the bag. e.g. Bag 1 Value = £94, Weight = 5.7Kg Bag 2 Value = £74, Weight = 9.4Kg . . . Bag N Value = £x, Weight = iKg The security van can carry only a limited weight, so your system must try and decide which bags to put on the van, and which ones to leave behind. The best solution will be the one which packs the most money (in terms of value) into the van without overloading it. • Your system should read in the 100 bag values from the file which is posted on the ELE site for this module • The file contains the weight limit for the security van and the values and weights for each bag of money. Weights are all in kilos and the values are all in pounds sterling. • You must decide how to represent this problem to the evolutionary algorithm, you must also decide what the fitness function should be. The Evolutionary Algorithm The evolutionary algorithm should be implemented as follows: 1. Generate an initial population of p randomly generated solutions (where p is a reasonable population size discussed in lectures and in the module reading), and evaluate the fitness of everything in the population. 2. Use the binary tournament selection twice (with replacement) to select two parents a and b. 3. Run crossover on these parents to give 2 children, c and d. 4. Run mutation on c and d to give two new solutions e and f. Evaluate the fitness of e and f. 5. Run weakest replacement, first using e, then f. 6. If a termination criterion has been reached, then stop. Otherwise return to step 2. Termination Criterion: Will simply be having reached a maximum number of fitness evaluations which is 10,000 (see Implementation and Experimentation below) Binary Tournament Selection: Randomly choose a chromosome from the population; call it a. Randomly choose another chromosome from the population; call this b. The fittest of these two (breaking ties randomly) becomes the selected parent. Single-Point Crossover: Randomly select a ‘crossover point’ which should be smaller than the total length of the chromosome. Take the two parents, and swap the gene values between them ONLY for those genes which appear AFTER the crossover point to create two new children. Mutation: This is dependent on your representation, look at the lecture slides for some ideas on which mutation to implement given your representation. Your mutation function must take a single integer parameter which will determine how many times it is repeated on a solution (e.g. M(1) – one mutation per chromosome, M(3) – 3 mutations). Weakest Replacement: If the new solution is fitter than the worst in the population, then overwrite the worst (breaking ties randomly) with the new solution. Implementation and Experimentation Implement the described EA in such a way that you can address the above problem and then run the experiments described below and answer the subsequent questions. Note that, in all of the below, a single trial means that you run the algorithm once and stop it when 10,000 fitness evaluations have been reached. Different trials of the same algorithm should be seeded with different random number seeds. You should devise your own set of experiments to determine what effect (if any) the following parameters have on the performance of the optimisation: 1. Tournament size(t) 2. Population size (p) 3. Mutation rate (i.e. the parameter identified in the mutation operator above) (m) Your experiments should assess the performance of the algorithm over a number of randomly seeded trials for each setting of t, p, m, to provide robust results. Analysis Record the best fitness reached at the end of each trial and any other variables during the run that you think will be important in answering the following questions. Hint: You should think carefully about how best to present your results to show the behaviour of the algorithm during your trials Question 1: Which combination of parameters produces the best results? Question 2: Why do you think this is the case? Question 3: What was the effect when you removed mutation? What about crossover? Question 4: If you were to extend your EA to work with a multi-objective version of this problem, which functions in your program would you change and why? In your answers, describe your observations of the results, and describe any tentative explanations or conclusions you feel like making, in addition to any further experiments you felt it interesting or useful to do to answer the above questions or to further your understanding of the algorithm parameters. Submission Report: Submit your report via E-BART by 12noon on the hand-in date shown above. The report should have a maximum of 5 pages (5 sides of A4) which should include a description of your experiments where tables and/or graphs of results should take up no more than 3-4 sides, with the remaining space used to answer the questions above. Code: Submit your clearly commented code as a zip file using the CEMPS electronic ‘CA Submit’ system (http://empslocal.ex.ac.uk/submit/) by 12noon on the hand-in date shown above. If you are unsure how to use this system, please ask me. Marking Scheme Correct and efficient implementation of the algorithm 15% Documentation of code 5% Correct results from the EA runs 20% Quality (e.g. readability & usefulness) of tables and graphs 20% Answers to Questions 20% Tentative Conclusions & Further Experiments 20% Overlength submissions (per page) -10%
欢迎咨询51作业君
