Implement constructive and perturbative local search algorithms for the Multidimensional 0/1 Knapsack Problem (MKP) whose problem description is as follows .
SmartPDF阅读器
SmartPDF阅读器
Exercise 1.2
a) Implement first-improvement (FI) and best-improvement (BI) algorithms for the MKP. Apply each of these algorithms to an initial solution generated by CH1–CH3. Execute the FI and BI algorithms that start from CH1 fifteen times on each instance and average the results (use the same random seeds). The FI and BI algorithms that start from CH2 and CH3 can be run once on each instance. Hence, six different algorithms should be tested, obtained combining the three initial heuristics with the two iterative improvement algorithms.
Before every iteration of FI, shuffle the list of items in the solution. For BI and FI, scan the neighbourhood removing k = 1 items and insert as many items as possible, using the ordering of the items of the corresponding initial heuristic. That is, for CH1 shuffle the list of items currently not in the solution, and try to insert the items in such order; for CH2 (CH3) sort the non-inserted items according to their profit, highest profit first (profit/weigth ratio, highest ratio first), and try to insert in such order. The item removed cannot be added back immediately to the solution. For the FI algorithm, accept the first move that results in an improved solution. For the BI algorithm, evaluate the improvement given by removing each item present in the solution and inserting as many items as possible according to the initial heuristic used.
SmartPDF阅读器
SmartPDF阅读器