首页 >
> 详细

ISE 5113 Advanced Analytics and Metaheuristics

Homework #4

Instructor: Charles Nicholson

See course website for due date

Requirement details

1. Submit all of your well-documented (e.g. commented) Python code.

2. Provide appropriate output of your code. Please no more than 1 page of output per problem.

3. You may work in teams of 2 for this problem. Teams will not be assigned, you can ask around. You

may also work solo.

4. You cannot use available Python packages that do all of the work for you { you must code the logic to

receive a grade!

In this assignment for several problems you will modify some provided Python code to implement heuristic

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:

Algorithm Iterations Objective

Local Search (Best Improvement) 3102 117

Local Search (First Improvement) 951 112

Local Search (Random Restarts) 9,681 147

Local Search (Random Restarts) + allowed infeasible solutions 14,412 194

Simulated Annealing 2102 184

etc.

Knapsack Problem De nition

Given n di erent 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 n = 100 and use a seed value (for the random

number generator) of 5113.

Question 1: Strategies for the problem (14 points)

(a) (2 points) De ne and explain a strategy for determining an initial solution to the this knapsack

problem for a neighborhood-based heuristic.

(b) (3 points) Recommend 3 neighborhood structure de nitions that you think would work well with

the example knapsack problem in this assignment.

(c) (3 points) What is the size of each of the neighborhoods you recommended?

1

(d) (4 points) Identify 2 neighborhood structure de nitions that you think would NOT work well with

the example knapsack problem in this assignment. Explain why.

(e) (2 points) In the evaluation of a given solution, an infeasible may be discovered. In this case,

provide 2 strategies for handling infeasibility.

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

space

Complete the original Python Local Search code provided to implement Hill Climbing with Best Im-

provement. Note you will need to implement your strategy for determining an initial solution, handling

infeasibility, and possible your neighborhood structures.

Apply the technique to the random problem instance and determine the best solution and objective

value using your revised algorithm.

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

space

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

Apply the technique to the random problem instance and determine the best solution and objective

value using your revised algorithm.

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

space

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:

a136 Make the number of random restarts an easily modi able variable.

a136 Keep track of the best solution found across all of the restarts.

Apply the technique to the random problem instance and determine the best solution and objective

value using your revised algorithm.

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

space

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:

a136 Make the probability of random walk an easily modi able variable.

Apply the technique to the random problem instance and determine the best solution and objective

value using your revised algorithm.

Question 6: Simulated Annealing (20 points)

space

Using the completed Python code as a base, implement Simulated Annealing. Make sure to include the

following:

a136 Explanation of how you determined the initial temperature.

a136 Well-de ned the temperature schedule (the temperature update procedure, the number of iterations

performed at a given temperature, etc.)

a136 Explanation of the stopping criterion.

Apply the technique to the random problem instance and determine the best solution and objective

value using your revised algorithm.

Page 2

Question 7: Tabu Search or Variable Neighborhood Search (30 points)

space

Using the completed Python code as a base, implement either a Tabu Search or Basic VNS to solve

the knapsack problem.

For TS, make sure to include the following:

a136 Explain the tabu criterion, tabu tenure, aspiration criterion, etc. and any other parameters you

include.

a136 Long-term memory is optional.

For Basic VNS, make sure to include the following:

a136 You must de ne and use at least 3 di erent neighborhood structures.

a136 De ne the local search component.

Apply the technique to the random problem instance and determine the best solution and objective

value using your revised algorithm.

Question 8: Summary (5 points)

space

What are your thoughts regarding the performance of the neighborhood-based heuristics that you im-

plemented? Which technique would you recommend for this problem? Did you try any variations (e.g.,

allowing infeasible moves, changing the initial solution strategy, di erent cooling processes, di erent

stopping criteria, etc.?) If so, what seemed to be most e ective?

Page 3

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp

- 95-712留学生作业代做、代写java编程设计作业、代做polymorph 2019-10-18
- 代做ols留学生作业、代写r程序语言作业、代做r编程设计作业、代写linea 2019-10-18
- Sdgb 7844作业代做、R编程设计作业代做、代写markdown留学生作 2019-10-18
- 代写math4/68091作业、代做statistical Computin 2019-10-18
- Analytics留学生作业代做、代写data Visualisation作 2019-10-18
- 代写frt留学生作业、代写r语言作业、代做datasets课程作业、R编程设 2019-10-18
- 代做sta 442课程作业、代写effects Models作业、Pytho 2019-10-17
- Se 3316A作业代做、代写web Technologies作业、Java 2019-10-17
- 代写csi213留学生作业、代做data Structures作业、代写ja 2019-10-17
- Cse 325作业代写、C/C++编程设计作业调试、Program留学生作业 2019-10-17
- 代做fit2014留学生作业、代做c++课程设计作业、Information 2019-10-17
- Scm 460课程作业代做、代写r编程设计作业、代做r实验作业、代写data 2019-10-17
- 代写rad留学生作业、代做r, Matlab/C++编程语言作业、代写r课程 2019-10-17
- Comp5338作业代写、Sql程序语言作业调试、代写schema Desi 2019-10-17
- 代做159.20留学生作业、代写rle课程作业、Java编程设计作业调试、P 2019-10-17
- 代做gu4206/Gr5206作业、代写r程序语言作业、代写data留学生作 2019-10-16
- Fit2104留学生作业代做、代写sql语言作业、Sql编程语言作业调试、代 2019-10-16
- 代写glfrustum课程作业、代做python程序语言作业、代写java， 2019-10-15
- 代写software留学生作业、代做information Technolo 2019-10-15
- 31927留学生作业代做、Net Applications作业代写、C++程 2019-10-15