Coursework should be submitted online via Moodle by 4pm on Friday 20 January 2023. You should submit a report and two (either Python or Macro-Enabled MS Excel, depending on the workshop you attended) files that contain your algorithm codes. You should also include the codes of your algorithms in the appendix of your reports.

The exercise has to be done as group work. Late work or evidence of collusion with other groups will be penalised in the manner specified in the department's teaching code of practice.

You should describe every change in code or new algorithm in detail. You can use describe the changes in detail in your reports and add comments to your codes that you are submitting with your report. Furthermore. you can also use the example instances to describe each step of new algorithms you developed in detail.

Discuss the experimentation process by presenting the results from several runs for different data sets with various parameters (for Questions A4 and B). Describe in detail what experiments did you conduct and how did you make sure that how they are improving the performance of your algorithms for different data sets.

In both parts A and B, up to 15% of your mark will be awarded by evaluating the performance of your algorithms on different instances (some will be shared in Moodle). For this purpose, your code should not run more than 30 seconds and after 30 seconds, it should provide a feasible solution. These feasible solutions should be using the resources as much as possible. In other words, one should only be able to add an item to the knapsack solutions provided by your code, by removing one of the items from the knapsack.

A set of input files are provided in Moodle. Each value is separated with commas and new lines. In the first line of the (0-1) Knapsack Problem input files, the number of items and weight limit are provided. Then, from the next line, every line contains the ID of the item (items are numbered with consecutive integers starting from zero), the profit of the item and the weight of the item. In Multidimensional (0-1) Knapsack Problems’ input files, the number of items and the number of dimensions are provided in the first line. The weight limit for each dimension is provided in the second line. Then, every consecutive line contains the ID of the item (items are numbered with consecutive integers starting from zero), the profit of the item and the weights of the item for each dimension.

A set of example output files are provided in Moodle. The first line of each output file contains the profit and the weight (or the weights for each dimension in the multidimensional case) of the solution. The next line shows the ID of the items that are selected for the knapsack.

Part A:

The (0-1) Knapsack Problem is an optimisation problem. The knapsack problem takes a set of items with their profits and weights, and a weight limit for the knapsack as parameters. The problem aims to find the set of items that maximises the sum of the profit of the items selected while satisfying the constraint that the sum of the weights of the selected items does not exceed the weight limit.  It is a combinatorial optimisation problem, and finding the optimal solutions using an exact algorithm for larger instances could take a long time. As a result, heuristic approaches are widely applied to knapsack problems. There is already the code for a heuristic approach that uses a constructive and two local search algorithms, uploaded to Moodle (check the folder that belongs to your computer workshop group).

Question A1 (20 marks)

One of the heuristic approaches used to solve the knapsack problems is the steepest ascent method. This method starts with a constructive algorithm and then runs one or many local search heuristics consecutively to  improve the current solution. The steepest ascent  method  moves to a  neighbour solution only if the neighbour solution improves the current solution. However, the code uploaded to Moodle does not do that. Check the code and correct it. Describe how you achieve this in your own words in detail

Question A2 (20 marks)

In the code uploaded to Moodle, there are one constructive and two local search algorithms. Develop one more constructive and one more local search algorithms. Both developed algorithms should return solutions to which no items can be added without removing an item from the knapsack. In your codes, call the two constructive algorithms at the beginning of the heuristic and continue with the solution that gives a better result. Then, call your  local search algorithms one after the other  in every  iteration.  Describe your  new constructive and local search algorithms in your own words.

Question A3 (15 marks)

When there are multiple local search algorithms developed for the same problem, one of the approaches that works quite well is the Variable Neighbourhood Search (VNS). In variable neighbourhood search, there is an internal process that chooses better-performing neighbourhoods with a higher probability. However, it is also important to make sure that none of the local search algorithms’ selection probability is becoming zero.

Your heuristic should start with the same probability for the three local search algorithms. Then every time an algorithm is improving the best solution, the heuristic should increase the better performing local search algorithm’s  probability.  If the  probability of the algorithm that found a  better solution is p, increase the probability by 0. 1 × (1 − p) and decrease the probabilities of the other methods by the same amount in total to make the sum of selection probabilities of the algorithms 1.

Here is an example showing how you should update your probabilities: If you have three algorithms, A1, A2 and A3, they will start with the same probability, p1 = p2 = p3 = 1/3  = 0.333 at the beginning of your heuristics. Then you should generate a random number and check what range it falls into. If it is between 0 and p1, then A1 is selected as the next local search algorithm. If the probability is between p1 and p1 + p2, then A2 is selected as the next local search algorithm. If the probability is between p1 + p2 and 1, then A3 is selected as the next local search algorithm. Let’s assume the first random number generated is 0.65 (it would be selected randomly in your algorithms so would be different) so your algorithm should choose A2 since it falls between p1 and p1 + p2. Then, if A2 improves the best solution by finding a solution better than the best solution so far before the call of A2, update the probability of A2 by 0. 1 × (1 − 0.333) =  0.067. This should make p2 = 0.333  +  0.067 = 0.4, p1 = 0.333– 0.067/2 = 0.3 and p3 = 0.333 − 0.67/2 = 0.3. Continue updating the selection of your local search algorithms and choose the algorithm with a random number until the end of the algorithm.

Question A4 (10 marks)

In the steepest ascent algorithm, the current solution is updated only if the solution is improved by the next neighbourhood. However, this may result in being stuck in a local optimum. We may prevent this by using an algorithm that moves to inferior solutions with some probability in a structured way. In this question, you should do this by using the simulated annealing metaheuristic.