编程代写｜CSCI-561 – 2022 – Foundations of Artificial Intelligence Homework 1

这是一篇来自美国的关于智能家居的编程代写

This is a programming assignment in which you will apply AI search/optimization techniques to a 3D Travelling-Salesman Problem (TSP) such as the one shown in Figure 1. Conceptually speaking, the space of traveling is a set of “cities” located on some grid points with (x, y, z) locations in which your AI agent has to travel. Your agent can travel from any city to any city and the distance between two cities can be calculated as the Euclidean distance between the two grid locations.

Figure 1: Traveling-Salesman Problem in 3D Space.

Your programming task is as follows. XYZ is a student at USC who has to run some errands across campus. The student starts from his house location, travels around USC to complete the errands, and returns home, or else the student will have to sleep on the streets :). Given is a list of 3D coordinates where each coordinate points to a location within the USC campus (the z coordinate represents the floor of the building located at (x, y)). The problem is that the student is lazy, and does not want to walk a lot. Being a Computer Science student, XYZ notices that this problem resembles Traveling Salesman Problem (TSP), and wants to tackle this problem using one of the concepts he studied in CSCI-561 i.e Genetic Algorithm.

TSP is defined as given a list of cities/locations, the person has to go to all the locations exactly

once, return back to the starting point, and cover the minimum distance as a whole.The student is happy that he studied this class and knows that by using Genetic Algorithm the student will be able to find the optimal path. But he forgot how the Genetic Algorithm works.

Now, you being a good friend of XYZ and a current student of CSCI-561 during Fall 2022, have to help your friend solve this problem. Your AI agent should find the path having the shortest distance, visit every location exactly once, and return back to the start location. The shorter the path distance, the better your agent is.

All homework material is checked vigorously for dishonesty using several methods. All detected violations of academic honesty are forwarded to the Office of Student Judicial Affairs. To be safe you are urged to err on the side of caution. Do not copy work from another student or off the web. Keep in mind that sanctions for dishonesty are reflected in your permanent record and can negatively impact your future success. As a general guide:

Do not copy code or written material from another student. Even single lines of code should not be copied.

Do not collaborate on this assignment. The assignment is to be solved individually.

Do not copy code off the web. This is easier to detect than you may think.

Do not share any custom test cases you may create to check your program’s behavior inmore complex scenarios than the simplistic ones considered below.

Do not copy code from past students. We keep copies of past work to check for this.

Even though this problem differs from those of previous years, do not try to copy from homework of previous years.

Do not ask on piazza how to implement some function for this homework, or how to calculate something needed for this homework.

Do not post code on piazza asking whether or not it is correct. This is a violation of academic integrity because it biases other students who may read your post.

Do not post test cases on piazza asking for what the correct solution should be.

Do ask the professor or TAs if you are unsure about whether certain actions constitute dishonesty. It is better to be safe than sorry.

Location: A location is represented as a combination of 3D coordinate points, x, y, and z as shown in the figure above. For example: (10, 0, 30) represents a city with x= 10, y = 0, z= 30.

Path: A list of locations that your agent will visit only once and return to the starting location.

For example: We have 3 locations A, B, C (each represented with 3D coordinates), then a valid path for this would be [A -> B -> C -> A]. Note that the path is a loop and has the starting location (A) as the final endpoint.

Grading for this assignment consists of 2 parts:

Part A – Optimality with respect to TA’s agent (60%)

We will run your search agent on the set of hidden test/grading cases to get the corresponding shortest paths. We will then use your path to calculate the path cost to grade your agent using the following criteria:

Part B – Quality of your solution (40%)

This section will test the quality of your agent and differentiate amongst the agents developed by other students. Students need to research and come up with ways they can improve their Genetic Algorithm.

The path scores obtained in Part A (above) will be ranked against other students’ agents.

Rank-based scores will be calculated for the student’s agent which contributes to 40% of the grade for this assignment.Student’s score = 40 * (1 − (𝑟𝑎𝑛𝑘/𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑠𝑡𝑢𝑑𝑒𝑛𝑡𝑠))

The students can read through the following material in this section and use it as suggestions for their implementation.

NOTE: This section doesn’t list the entire working of the genetic algorithm and is in no way mandated to follow exactly. These can be used as starting points for your assignment. You  are free to choose your implementation methods based on your research.

CreateInitialPopulation(size, cities): Arguments defined below:

Size: An integer representing the size of the list (initial_population) which

needs to be returned.

Cities: A list of cities where a city is represented in 3d coordinates (x,y,z)

Return Value: returns a list of paths (a permutation of cities) of size = size

Students need to implement this function which creates paths randomly

or with some heuristic chosen by you.

CreateMatingPool(population, RankList): Arguments defined below:

Population: A list of paths from which the mating pool is to be created

RankList: A list of tuples of index and fitness scores sorted in descending order.

Return Value: A list of populations selected for mating (List contains paths)

Function Definition: This function defines the best fit individuals and selects them for breeding. You will implement a Roulette wheel-basedselection  (reference link) which is a widely used and most efficient method for selecting parents. Make sure to assign the appropriate probabilities to the parents for roulette-wheel selection.

Parent1: First argument of the function: A list containing the random sequence of cities for the salesman to follow

Parent2: Second argument of the function: A list containing the random sequence of cities for the salesman to follow

Start_index: Start index of the SUBARRAY to be chosen from parent 1

End_index: End index of the SUBARRAY to be chosen from parent 1

Return Value: Return child after performing the crossover (also a list containing a valid sequence of cities)

Function Definition: In this function, students are asked to implement a two-point crossover. Choose the subarray from Parent1 starting at start_index and ending at end_index. Choose the rest of the sequence from Parent 2. For example: if Start_index = 1 and End_Index = 3, then the child created should look like the following:

Parent-1: 1,2,3,4,5

Parent-2: 5,4,3,2,1

Start_index = 1

End_Index = 3

Resulting Parent 1 subarray from Start_index to End_index = 2,3,4

Your function should return the child as:

=> Child: 5,2,3,4,1

Note: For TSP, the child follows the constraints of each city is only visited once. So, any conflicts after copying the substring from parent 1, and the rest of the sequence from parent 2 should be resolved by your function.

For example:

Parent-1: 1,2,3,4,5

Parent-2: 5,2,3,1,4

Start_index = 1

End_Index = 3Resulting Parent 1 substring from Start_index to End_index = 2,3,4

Your function should return the child as:

=> Child: 5,2,3,4,1

Steps to resolve conflict:

Your program will be run in a directory on Vocareum that contains the following input file. Your program should output the output file in the same directory.

Input: The file input.txt in the current directory of your program will be formatted as follows:

Output: Report your path of traveling the cities, that is N locations of the city. For example: