ISE 5113 Advanced Analytics and Metaheuristics Homework #6 Solved

In this assignment for several problems you will modify some provided Python code to implement algorithms to solve the same instance of the knapsack problem. After implementing all of the code and solving the problem, you must provide a single table of all results similar to the following:

Table 1: Example of results summary (numbers are not realistic)

Algorithm
Iterations
# Items Selected
Weight
Objective





Local Search (Best Improvement)
3102
49
97
117
Local Search with Random Restarts (k = 100)
9510
121
21
147
Local Search with Random walk (p = 0.25)
2102
87
32
184
etc.










Knapsack Problem Definition Given n different items, where each item i has an assigned value (vi) and weight (wi), select a combination of the items to maximize the total value without exceeding the weight limitations, W , of the knapsack.

IMPORTANT!: When generating random problem instance set you must use the code provided and values:

n = 150; max weight of 2500; and, use a seed value (for the random number generator) of 51132023.

1

Question 1: Strategies for the problem (15 points)

    (a) (5 points) Define and defend two strategies for determining an initial solution to this knapsack problem for a neighborhood-based heuristic. Copy and paste relevant excerpts of commented Python code to implement your preferred choice.

    (b) (5 points) Describe two neighborhood structure definitions that you think would work well for this problem. Compute the size of each neighborhood.

    (c) (5 points) During evaluation of a candidate solution, it may be discovered to be infeasible. In this case, provide two strategies for handling in feasibility. Copy and paste relevant excerpts of commented Python code for the handling infeasibility.


Question 2: Local Search with Best Improvement (10 points)

Complete the original Python Local Search code provided to implement Hill Climbing with Best Im-provement. You will need to implement your strategy for determining an initial solution and handling infeasibility, etc., and complete the code as needed.

    (a) (10 points) Apply the technique to the random problem instance and determine the best solution and objective value using your implemented algorithm.


Question 3: Local Search with First Improvement (14 points)

Modify the Python Local Search code to implement Hill Climbing with First Improvement.

    (a) (10 points) Apply the technique to the random problem instance and determine the best solution and objective value using your implemented algorithm.

    (b) (4 points) Using Python code excerpts, identify the logic differences between the code for Question 2 and Question 3.


Question 4: Local Search with Random Restarts (16 points)

Modify the completed Python Local Search code to implement Hill Climbing with Random Restarts. You may use Best Improvement or First Improvement (just clearly state your choice). Make sure to include the following:

        ◦ Make the number of random restarts, k, an easily modifiable parameter. Keep track of the best solution found across all of the restarts.

    (a) (8 points) Apply the technique to the random problem instance and determine the best solution and objective value using your algorithm.

    (b) (4 points) Report results for at least two different values of k.

    (c) (4 points) Include relevant excerpts of commented Python code to implement the solution.


Question 5: Local Search with Random Walk (20 points)

Modify the completed Python Local Search code to implement Hill Climbing with Random Walk. You may use Best Improvement or First Improvement (just clearly state your choice). Make sure to include theˆ following:

Make the probability, p, of random walk an easily modifiable parameter.




Page 2

    (a) (12 points) Apply the technique to the random problem instance and determine the best solution and objective value using your implemented algorithm.

    (b) (4 points) Report results for at least two different values of p.

    (c) (4 points) Include relevant excerpts of commented Python code to implement the solution.


Question 6: Stochastic Hill Climbing (25 points)

Modify the completed Python Local Search code to implement Stochastic Hill Climbing. You may use Best Improvement or First Improvement (just clearly state your choice).

    (a) (15 points) Apply the technique to the random problem instance and determine the best solution and objective value using your implemented algorithm.

    (b) (6 points) xplanation of how you determine probabilities for the stochastic solution choices.

    (c) (4 points) Include relevant excerpts of commented Python code to implement the solution.















































Page 3