ISE 5113 Advanced Analytics and MetaheuristicsHomework #4Instructor: Charles NicholsonSee course website for due dateRequirement details1. 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. Youmay also work solo.4. You cannot use available Python packages that do all of the work for you { you must code the logic toreceive a grade!In this assignment for several problems you will modify some provided Python code to implement heuristicalgorithms to solve the same instance of the knapsack problem. After implementing all of the code andsolving the problem, you must provide a single table of all results similar to the following:Algorithm Iterations ObjectiveLocal Search (Best Improvement) 3102 117Local Search (First Improvement) 951 112Local Search (Random Restarts) 9,681 147Local Search (Random Restarts) + allowed infeasible solutions 14,412 194Simulated Annealing 2102 184etc.Knapsack Problem De nitionGiven n di erent items, where each item i has an assigned value (vi) and weight (wi), select a combinationof 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 randomnumber 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 knapsackproblem for a neighborhood-based heuristic.(b) (3 points) Recommend 3 neighborhood structure de nitions that you think would work well withthe 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 withthe 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)spaceComplete 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, handlinginfeasibility, and possible your neighborhood structures.Apply the technique to the random problem instance and determine the best solution and objectivevalue using your revised algorithm.Question 3: Local Search with First Improvement (5 points)spaceModify 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 objectivevalue using your revised algorithm.Question 4: Local Search with Random Restarts (8 points)spaceModify 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 toinclude 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 objectivevalue using your revised algorithm.Question 5: Local Search with Random Walk (8 points)spaceModify the completed Python Local Search code to implement Hill Climbing with Random Walk. Youmay use Best Improvement or First Improvement (just clearly state your choice). Make sure to includethe 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 objectivevalue using your revised algorithm.Question 6: Simulated Annealing (20 points)spaceUsing the completed Python code as a base, implement Simulated Annealing. Make sure to include thefollowing:a136 Explanation of how you determined the initial temperature.a136 Well-de ned the temperature schedule (the temperature update procedure, the number of iterationsperformed 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 objectivevalue using your revised algorithm.Page 2Question 7: Tabu Search or Variable Neighborhood Search (30 points)spaceUsing the completed Python code as a base, implement either a Tabu Search or Basic VNS to solvethe knapsack problem.For TS, make sure to include the following:a136 Explain the tabu criterion, tabu tenure, aspiration criterion, etc. and any other parameters youinclude.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 objectivevalue using your revised algorithm.Question 8: Summary (5 points)spaceWhat 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 erentstopping criteria, etc.?) If so, what seemed to be most e ective?Page 3本团队核心人员组成主要包括硅谷工程师、BAT一线工程师，精通德英语！我们主要业务范围是代做编程大作业、课程设计等等。我们的方向领域：window编程 数值算法 AI人工智能 金融统计 计量分析 大数据 网络编程 WEB编程 通讯编程 游戏编程多媒体linux 外挂编程 程序API图像处理 嵌入式/单片机 数据库编程 控制台 进程与线程 网络安全 汇编语言 硬件编程 软件设计 工程标准规等。其中代写编程、代写程序、代写留学生程序作业语言或工具包括但不限于以下范围:C/C++/C#代写Java代写IT代写Python代写辅导编程作业Matlab代写Haskell代写Processing代写Linux环境搭建Rust代写Data Structure Assginment 数据结构代写MIPS代写Machine Learning 作业 代写Oracle/SQL/PostgreSQL/Pig 数据库代写/代做/辅导Web开发、网站开发、网站作业ASP.NET网站开发Finance Insurace Statistics统计、回归、迭代Prolog代写Computer Computational method代做因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱：99515681@qq.com 微信：codehelp
网友评论