Assignment11.We will consider the routing problem shown in Figure1.We aim at finding a route from S to T,where S is the starting point and T is the goal point.The number on every edge refers to the cost(e.g.,time/distance).An example path is S→A→D→T and the cost of this path is70+80+300=450.Figure11.1Please write down the points to be visited in order using Breath-First Search (BFS),then calculate the cost of the solution.(12marks)[0]{[S,0]}[1]{[S→A,70];[S→B,40];[S→C,90]}[2]{[S→B,40];[S→C,90];[S→A→D,150]}[3]{[S→C,90];[S→A→D,150];[S→B→F,200]}[4]{[S→A→D,150];[S→B→F,200];[S→C→E,210]}[5]{[S→B→F,200];[S→C→E,210];[S→A→D→T,450]}[6]{[S→C→E,210];[S→A→D→T,450];[S→B→F→T,230]}[7]{[S→A→D→T,450];[S→B→F→T,230];[S→C→E→T,490]}The length of the shortest path is230.The path is S→B→F→T.1.2Please write down the points to be visited in order using Depth-First Search (DFS),then calculate the cost of the solution.(12marks)[0]{[S,0]}[1]{[S→A,70];[S→B,40];[S→C,90]}[2]{[S→A→D,150];[S→B,40];[S→C,90]}[3]{[S→A→D→T,450];[S→B,40];[S→C,90]}[4]{[S→A→D→T,450];[S→B→F,200];[S→C,90]}[5]{[S→A→D→T,450];[S→B→F→T,230];[S→C,90]}[6]{[S→A→D→T,450];[S→B→F→T,230];[S→C→E,210]}[7]{[S→A→D→T,450];[S→B→F→T,230];[S→C→E→T,490]}The length of the shortest path is230.The path is S→B→F→T.1.3Please write down the points to be visited in order using Uniform-Cost Search(UCS),then calculate the cost of the solution.(12marks)[0]{[S,0]}[1]{[S→A,70];[S→B,40];[S→C,90]}[2]{[S→A,70];[S→B→F,200];[S→C,90]}[3]{[S→A→D,150];[S→B→F,200];[S→C,90]}[4]{[S→A→D,150];[S→B→F,200];[S→C→E,210]}[5]{[S→A→D→T,450];[S→B→F,200];[S→C→E,210]}[6]{[S→A→D→T,450];[S→B→F→T,230];[S→C→E,210]}[7]{[S→A→D→T,450];[S→B→F→T,230];[S→C→E→T,490]}The length of the shortest path is230.The path is S→B→F→T.2.Consider the Travelling Salesman Problem(TSP).Given a set of cites and the distances between each pair of cities,we aim at finding the shortest route that visits each city once and only once and returns to the origin city.Figure2is an example solution to a TSP problem,the solution is1→2→3→4→1,which leads to the shortest distance890.Figure2Figure3Consider a TSP problem illustrated in Figure3.2.1How will you represent solutions to TSP in an evolutionary algorithm?(5 marks)The ordinal representation.parent1(125643):113321parent2(135246):1231112.2What would be an appropriate fitness function for measuring the quality of solutions?(5marks)Subtract each tour length to the maximum tour length found in the current population.2.3Design an appropriate crossover operator.Justify your design.(10 marks)The two parent chromosomes encode the tours125643and135246,respectively. After cutting at position2,a feasible offspring(125346)is created.parent1(125643):11|3321parent2(135246):12|3111offspring(125346):1131112.4Design an appropriate mutation operator.Justify your design.(10marks)The offspring is created by first replacing the substring31in parent2by the substring33.Hence,2replaces3,and1replaces city3(step1)(125364).Outside of the cut points,1replaces2,and2replaces1(step2)(125346).parent1(125643):11|33|21parent2(135246):12|31|11offspring(step1)(125364):113121(step2)(125346):1131123.For the tours13654287and14236578(path representation),the initial edge map is shown in the following figure.Here,we consider the Edge recombination crossover(ER)in the adjacency representation.What is the final tour if city1is selected as the starting city?Write down the derivation process and justify your conclusion.(34marks)(a)From city1,we can go to cities3,4,7or8.Cities3,4,7and8have two active edges.Hence,a random choice is made between cities3,4,7and8.(b)Assume that city3is selected.From3,we can go to cities2and6.(c)City2has two active edges and city6only one,so city6is selected.From city6, there is no choice but to go to city5.(d)City5is selected.From City5,cities4and7have two active edges.(e)Assume that city4is randomly selected.From city4,there is no choice but to go to city2.(f)City2is selected.From city2,there is no choice but to go to city8.(g)City8is selected.From city8,we must go to city7.(h)City7is selected.So the final tour is13654287and all edges are inherited from both parents.。
