Coursework: Memetic Algorithm for Multi-Knapsack Problem
模因算法Coursework代写 Multi-dimensional knapsack problem is a classic NP-Hard combinatorial optimisition problem used to test the performance metaheuristics.
1.Introduction
Multi-dimensional knapsack problem is a classic NP-Hard combinatorial optimisition problem used to test the performance metaheuristics. In this coursework, you are asked to write a C/C++ program to solve this problem using a memetic algorithm (a variant of genetic algorithm). In addition to submitting source code, a report (no more than 2000 words and 6 pages) is required to describe the algorithm, the experimental results, discussions and reflections on results and performance of the algorithm. This coursework carries 50% of the module marks. The rest of module marks comes from the final written exam.模因算法Coursework代写
2. Multi-dimensional Knapsack Problem
Multi-dimensional knapsack problem is an extension of the 1D knapsack problem by adding capacity constraints in multiple dimensions. The problem can be formally defined as follows. Given a set of n items numbered from 1 up to n, each with a size vector v=(v1j, v2j, v3j, …, vmj) where vij is the i-th dimensional size of item j. bi is the i-th dimensional size of knapsack. pj is the profit of item j if it is included in the knapsack. Denote xj be the binary variables to indicate whether item j is included in the knapsack (=1) or not (=0). The problem to be solved is then formulated as follows
3. Problem instances 模因算法Coursework代写
In this lab, you are asked to attempt some more challenging instances from paper: P.C. Chu and J.E.Beasley “A genetic algorithm for the multidimensional knapsack problem”, Journal of Heuristics, vol. 4, 1998, pp63-86. All the data files are compressed in mknap- instances.zip, downloadable from Moodle. The zip file includes 9 problem instance files (each containing 30 instances), 1 data format file file-format.txt and 1best known solution file best-feasible-slns.txt.
4. Experiments conditions and requirements 模因算法Coursework代写
The following requirements should be satisfied by your program:
(1)You are required to submit two files only. The first file should contain all your program source codes. The second file is your report.
(2)Your source code should be properly commented.模因算法Coursework代写
(3)Your report should include the details of your algorithm (pseudo-code), a description of the parameter tuning process, the results that your algorithm obtains incomparison with the best results in the literature (i.e. gap% to the best results), a short reflection/discussion on the strengths and weaknesses of GA/MA methods.
(4)Name your program file after your student id. For example, if your student number is 2019560, name your program as 2019560.c (orcpp).
(5)Your program should compile without errors using one of the following commands (assuming your student id is 2019560 and your program is named after yourid):
gcc -std=c99 2019560.c -o 2019560
or
g++ 2019560.cpp -o 2019560 模因算法Coursework代写
(6)After compilation, your program should be executable using the followingcommand:
./2019560 -s data_file -o solution_file -t max_time where 2019560 is the executable file of your program, data_file is one of problem instance files specified in Section 3. max_time is the maximum time permitted for a single run of your MA algorithm. soluton_file is the file for output the best solutions by your MA algorithm. The format should be as follows:
# of problems
objective value of instance 1 x1 x2 x3 … x_n
objective value of instance 2 x1 x2 x3 … x_n
… …
objective value of last instance x1 x2 x3 … x_n 模因算法Coursework代写
An example solution file for problem data file “mknapcb1.txt” is available on moodle.
(7)The solution file that your algorithm (solution_file) is expected to pass a solution checking test successfully using the followingcommand:
./mk_checker -s problem_file -c solution_file
where problem_file is one of problem data files in Section 3. If your solution file format is correct, you should get the following command line message “All solutions are feasible with correct objective values.”模因算法Coursework代写
The solution checker can be downloaded from moodle page. The checker is runnable on CS linux server only.
(8)Your program should take no more than 10 min (i.e. 10 min max_time is set as your stopping criteria of your MAalgorithm).
5. Marking criteria 模因算法Coursework代写
The quality of the experimental results(30%).
The quality of codes(30%)
Report(40%)
其他代写：代写CS C++代写 java代写 r代写 金融经济统计代写 matlab代写 app代写 作业代写 物理代写 数学代写 考试助攻 algorithm代写
