Travelling Salesman Problem (TSP) is a very popular problem, which aims to find a minimumdistance path between some number of cities that a salesman might follow on a business trip.
computer science
Description
Travelling Salesman Problem (TSP) is a very popular problem, which aims to find a minimumdistance path between some number of cities that a salesman might follow on a business trip. The best path is the path that has the shortest total round-trip distance--from an arbitrary starting city, though all other cities, and back to the starting city. Unfortunately, finding the best path is an NP-complete problem. In this assignment, we target to develop a GA-based solution for TSP problem.
Details of GA-Based Solution
• String Representation: We will consider path representation where the order in a solution defines the order that the traveling salesman will visit the other cities.
• Initialization: 80% of the population is initialized randomly. For the remaining part, we consider nearest-neighbor strategy, a very simple and intuitive way for initialization. In this strategy, first a city x is selected randomly. Then, it selects the city that is closest to city x and that has not been selected yet; now the new city becomes the base and this step is repeated until all cities are selected. Note that it will prevent duplicates of selecting the first city “x”.
• Fitness Function: It is defined as the total distance of travel represented by the order of cities. Note that we consider a closed TSP where it will begin and end to the same city.
• Population Size: Population size is set to 50, unless otherwise stated.
• Crossover Operator: You will implement two different crossover operators, which are
the Order Crossover (OX) and Sequential Constructive Crossover (SCX). Literature survey
is required. (ScienceDirect and/or IEEE Explore)
