博客

CMPT 317

Fall 2020

Introduction to Artifificial Intelligence

新加坡计算机代写 Note that dening the neighborhood of a state (i.e. the states that are considered adjacent to a given state) is up to you!

Assignment 4 

Local Search

Question 1 (10 points):

Purpose: To practice problem specication design for local search

AIMA Chapter(s): 4.1

For this question, you will write the code to apply Local Search to the Robot DNA problem.

The following basic Local Search strategies have been provided for you:

• Random Guessing: Randomly choose a new state from all possible states.
• Random Search: Randomly move to a neighbouring state.
• Hill Climbing: Move to the best neighbouring state.
• Stochastic Hill Climbing: Move to a random better neighbouring state.
• Random Restart Hill Climbing: Repeat Hill Climbing, with random initial positions.  新加坡计算机代写

These functions are complete and have been tested, and you should be condent that they work. To apply these methods, you will implement a State class and a Problem class, as per the following interface.

Problem Class

The Local Search strategies all assume that a Problem class exists with the following methods:

• random_state(): returns a completely random state
• random_step(state): returns a neighbour one step away from the given state at random
• best_step(state): returns the best neighbour one step away from the given state
• random_better(state): returns a randomly chosen better neighbour of state

Note that dening the neighborhood of a state (i.e. the states that are considered adjacent to a given state) is up to you! There is no single correct answer. This is a design problem, and like all design problems, there are multiple reasonable designs and a great many bad ones. Along with your code, you need to submit a short written paragraph that describes your design.

State Class  新加坡计算机代写

The Local Search strategies also assume that a State class exists with the following methods:

• is_better_than(self, other): Returns True if the State object self is better, in terms of the objective function, than the State object other

• is_equal_to(self, other): Returns True if the State object self is equal, in terms of the objective function, to the State object other.

The State and Problem classes are interdependent (see the provided code template). Simply implement all of the incomplete methods in this template. You can of course add additional helper functions if you wish, but the Local Search code you have been given will ONLY call the methods described above.

Keep in mind that the Problem and State methods may be called thousands of times. Make sure your implementation is correct, and when you are sure, you can try to nd ways to be more efficient with time and memory.

What to Hand In

• A file named a4q1.py containing your implementation of the State and Problem classes.
• A written document named a4q1.txt (or .rtf, .pdf, .docx) that describes your definition of adjacency for the Robot DNA problem, and any additional notes if there is any trickiness to its implementation.Be sure to include your name, NSID, student number, and course number at the top of all documents.

Evaluation

• 8 marks: Your implementation of the Problem and State classes is correct, readable, and well-documented
• 2 marks: Your adjacency specication is reasonable and well-described.

Question 2 (4 points):  新加坡计算机代写

Purpose: To explore the performance of Local Search algorithms

AIMA Chapter(s): 4.1

For this question, you will run the provided Local Search algorithms, using the State and Problem classes that you created for the previous question, on the four provided robot DNA problem files.

A solver script is provided to you, which you can use to run the tests and produce your data. For each problem file, you should submit a neat and readable table of results in the following format:

The Energy column is the average energy of the best solution found by each stategy, and the Time column is the average run time (the solver script runs each strategy multiple times so as to compute a more reliable performance average).

Note that there are two versions of Random-Restart Hill-climbing. They each use the given number of total steps, but dier in how long they wait before trying a random restart.

1. Variation 1: 20 steps before restarting
2. Variation 2: 100 steps before restarting

What to Hand In  新加坡计算机代写

• Your document that includes your data tables as described above. You can use a plain text file, or you can submit a MSWord document, or PDF. Name your document a4q2 with an appropriate extension(e.g., txt, pdf, docx, etc).

Be sure to include your name, NSID, student number, and course number at the top of each document or file.

Evaluation

• 4 marks: Results are plausible and well-formatted for all four data files

更多代写：加拿大econ代考价格  GRE家考作弊  会计网课作业代做  Essay代写机构哪个好  环境学论文代写   计算机专业作业代写

合作平台：essay代写 论文代写 写手招聘 英国留学生代写