Reference no: EM131468436

Question: The traveling salesman problem (TSP) is a popular problem in combinatorial optimization with applications in various domains, from fast-food delivery to the design of VLSI circuits. In its simplest form, the traveling salesman must visit every city in a given territory exactly once, and then return to the starting city. Given the cost of travel between all cities (e.g., distance or cost in money), the question posed by the TSP is related to what should be the itinerary for the minimal cost of the whole tour. Implement an evolutionary algorithm to solve the pictorial TSP illustrated in Figure. The cities were placed on a regular grid to facilitate analysis and are labeled by a number on their top left corner. Three main aspects deserve careful examination: representation, evaluation function, and genetic operators. First, one has to define a representation for the chromosomes. Is a binary representation, such as the one used in standard genetic algorithms, suitable? If not, explain why, and suggest a new representation. Second, the definition of an evaluation function requires the knowledge of the objective. In this case, assume that the objective is simply to minimize the distance traveled by the salesman. The coordinates of each city on the xy plane can be extracted from Figure. Lastly, if the representation you chose is not binary, what should be the crossover and mutation operators employed? Can you see any relationship between these operators and the biological crossover and mutation?

Figure: Simple TSP with 32 cities. The cities are placed on a regular grid on the x-y plane, in which each point (•) represents a city, the number next to each city corresponds to its index, and each square on the grid corresponds to one unit of distance (uod - e.g., Km).