1. MSCI517作业代写,python编程代写

In this coursework, you are to write a program that attempts to solve the group balancing problem using stochastic optimisation techniques. Specifically your program will read in a problem instance from a file and will attempt to produce a solution using stochastic optimisation algorithms. Note that the optimal solutions to such intractable problems, are not currently known and so algorithms seen to quickly achieve low cost solutions are viewed more favourably. Because it is quite challenging, this coursework is designed so that partial submissions can still get a reasonable number of marks.

You have been given the flexibility to structure the code in the way that you think is best following the principles of re-usability, maintainability, information hiding and clarity.

You are required to submit to Moodle a single .py file. The name of this file should be your library number (e.g. 12345678.py, where 12345678 is an example library number). You should also submit a document file named 12345678.docx, where 12345678 is an example library number, containing a copy of your code.

Please do not submit compressed files such as zip and rar files.

In case you want to import any packages apart from pandas, matplotlib, numpy, math, random, tkinter, pickle, seaborn, and norm from scipy.stats, you should contact the module leader first.

This coursework may easily be divided up into tasks (see below) to facilitate development. If you can only do some of these tasks, then submit whatever it is that you can manage to do. You will be penalised for functionality (possibly heavily), but you may well get quite a lot of marks in other categories.

Problem description

The problem instances, which are available in .csv format, contain the number of groups k and the weights of the n items. On Moodle you will find three problem instances: I1.csv, I2.csv and I3.csv. An example of a problem instance file I1.csv is shown below.

In this example, we have n = 8 items to be split into k = 3 groups, with a minimum of k − 1 = 2 items to be assigned to each group. The weights of items 1 to 8 are 1, 4, 3, 2, 5, 3, 2, and 1 respectively.

Task 1: (2 marks) Your first task is to write a Python program that asks the user for the input file name and then reads-in the specified problem instance file.

Task 2: (10 marks) Generate an initial solution to this problem in a randomised fashion of your choosing. In order to obtain a good mark for this task, you will need to add some ‘intelligence’ to the procedure to produce high-quality initial solution. Anything that improves upon the basic initialisation method is acceptable (providing it is a genuine improvement).

Task 3: (8 marks) Implement a Cost method that calculates the cost of the solution in the way described above, i.e. Equation (1). It is critical that your cost function is correct. Thus it is worth checking initial results manually using the very small problem instance file I1.csv.

Task 4: (5 marks) Implement a Feasibility method that returns 1 if the solution is feasible, and 0 otherwise. Considering the example given above, each group contains at least k − 1 = 2 items, hence, the solution S is feasible.

Task 5: (10 marks) Implement a method that improves the initially generated solution using hill climbing method which accepts only non-worsening moves. To do this, you will need to implement an appropriate operator, e.g. randomly move an item from one group to another. Your program should be run for a fixed number of iterations. Ask the user to input the number of iterations. At the end of the run, your best obtained solution should be saved in a .csv file. The file specifies the solution in a single column, and the last two rows display the Cost and the Feasibility of the solution. This format is extremely important, as I will be using my own checker software tool to automatically examine your solution and your calculated Cost and Feasibility. The example solution described above would be displayed:

Task 6: (30 marks) Try to make your solver more efficient and powerful, by:

• Implementing simulated annealing method (you will need to research this yourselves).

• Employing more than one neighbourhood operators. Think carefully about the sort of operators (moves) that will be appropriate with this problem. One of the operators must be clever, which alters the heaviest and lightest groups only.

• When performing a move, you may notice that only few groups are altered during a move. Thus, you may be able to speed up your program by only re-evaluating the effected groups.

Ultimately the goal is to minimise the Cost with no constraint violations (i.e. Feasibility = 1).

Task 7: (5 marks) Update your code to provide a visual representation of the best solution (e.g. a simple one might be a bar chart).

Task 8: (5 marks) Output to the user the following information: an iterations Vs Cost line-graph that demonstrates how the Cost reduces during a run. This will help to monitor the performance of the algorithm. Note that updating the graph in each iteration may make the algorithm slow, so you should update the graph every 100 iterations.