Optimising Functions Using Genetic Algorithms

For this assessment, you are asked to optimise two functions (problems) using genetic algorithms. The assessment will be marked by machine. It is therefore very important that you follow the  instructions given to you very carefully. Failure to do so will result in substantial loss of marks, even zero.

The first problem is a black box function that takes 20 real-valued numbers as input. The function has a unique minimum fitness of 0 for a specific input. Your task is to write a genetic algorithm to find this minimum value. You can safely assume that the minimum can be found for input values between -5.0 and +5.0 for all variables/dials. So, you do not need to search smaller or larger values than that.

The second problem is a version of the well-known knapsack problem. The idea is that you want to pack a bag. You have 100 items that you would like to take with you. Each item has a utility value and a weight (assumed to be expressed in kg). You want to maximise your utility (which is the sum of the utilities of all the items you take with you) but you are not allowed to pack more than 500 kgs of weight altogether. This means that you need to choose the items that maximise your total utility while staying within the weight limit.

Marking criteria

Your final submission will be assessed by compiling and running it on raptor using the above two commands. It is your responsibility to ensure before submission that they work and produce the desired result. If this does not work, you will be awarded 0 marks.

Rules on use of APIs: Example.java includes, at the moment java.lang.Math

These allow you to use mathematical functions in java and ArrayLists. You are not allowed to use any APIs beyond that. In particular, do not use any graphics or GUI. This is not necessary and not allowed.

· You will get up to 20 marks for a program that compiles, runs, displays functionality and completes within 60 seconds on raptor.

· You will get up to 30 marks for the first problem. The number of marks will depend on the quality of the solution. The closer the solution fitness to 0 the higher the mark. Note that you are asked for the perfect solution. Do not assume that a fitness of gets full marks, but attempt to find the 0 fitness solution. That said, you will get partial marks for good solutions.

· You will get up to 30 marks for the second problem. The higher the utility (while staying within the weight constraints) the more marks. If your solution is above the weight limit (even by a little bit), it will not get any marks.

· Your program must completed within 60 seconds, for both tasks. You will get up to 20 marks for execution speed – therefore it is to your benefit to optimise the code to run as fast as possible while still meeting the quality of solutions. The time will be measured on raptor. Note that if you have a very slow or very fast machine at home, execution times can be substantially different. So, make sure that you check the run-time on raptor.

The work you submit must be your own, except where its original author is clearly referenced. Checks will be run on submitted work in an effort to identify possible plagiarism, and take disciplinary action against anyone found to have committed plagiarism. When you use other peoples’ material, you must clearly indicate the source of the material.