2018-19 Spring Semester Assignment #1
How to submit it: Submit your written answers as a pdf file. Submit your code for the last question as a zip file
Penalties on late papers: 20% off each day (anytime after the due time is considered late by one day)
Problem 1. (30%) Consider a 10×10 grid without any obstacles, and a robot with the same specification as our boundary following robot: eight sensors and four actions.
• Design a reactive production system to control the robot to go to one of the four corners, wherever its initial position is.
• Show that it is not possible to have a reactive production system to make the robot visit every cell in the grid.
• Design a state machine to achieve the above task. In addition to having memory about previous action taken and previous sensory input, you can have internal variables (mental states) and actions to change the values of these variables.
Problem 2. (15%) Which boolean function does the following TLU implement? The TLU has five inputs. Its weight vector is (1.1, 3.1, −1, −2, 0.5), and the threshold is 1.
Problem 3. (20%) Consider the problem of training a TLU to do logical disjunction (logical “or”) using the error-correction procedure that we talked about in class. Notice that this operator takes two inputs, but to apply the procedure, you need to add one more input whose value is always 1, and use 0 as the threshold. Suppose that we start with the initial weights all equal to 0, and learning rate c = 1. Find a minimal set of training instances that will correctly train the TLU according to the procedure. Here a training set is minimal if removing any instance in it will not produce a TLU for the logical disjunction. Please show the details of your work inlcuding the converging sequence of the weights.
Problem 4. (Programming) (35%) Design and implement a genetic programming system to evolve some perceptrons that match well with a given training set. A training set is a collection of tuples of the form (x1, …, xn, l), where xi’s are real numbers and l is either 1 (positive example) or 0 (negative example). So for your genetic programming system, a “program” is just a tuple (w1,…,wn,θ) of numbers (weights and the threshold). Answer the following questions:
1. What’s your fitness function?
2. . What’s your crossover operator?
3. What’s your copy operator?
4. What’s your mutation operator, if you use any?
5. What’s the size of the initial generation, and how are programs generated?
6. When do you stop the evolution? Evolve it up to a fixed iteration, when it satisfies a
condition on the fitness function, or a combination of the two?
7. What’s the output of your system for the training set in the next page? This training set
will be uploaded to canvas as a csv file.
In addition to answer these questions, please also upload your source code and executable (in any language and platform) as a zip archive file and name it as YourStudentID.zip on canvas.