Time: Sep 2021~ Oct 2021
Role: Developing algorithms for the shortest path
Skills Gained: Concept of genetic algorithm, Method of Preventing from stranding in local Minimum, Pros and Cons of hill climbing and crossover
Among 1000 points, we aim to find the shortest path using different type of designed algorithms. Find out the best algorithms and compared with others
Random Search:
For the method of random search, the distance for each evaluation is calculated by a completely random assortment of the given list of coordinates. For the shortest path, if the distance for an evaluation is higher than the previous evaluation, it is removed and the previous distance is used. If the obtained distance is lower, it becomes the new minimum distance.
Random Mutation Hill Climb:
For the method of hill climb, the goal is to reach the minimum distance by switching the order of one city with the next. In order to implement this algorithm, a random number within the number of indices is chosen. The chosen index and the neighboring city are switched, generating a new distance. In the end, this algorithm results in a local minimum.
Genetic Algorithm-Tournament:
A genetic algorithm is created such that crossovers happen among 1000 sets of shuffled lists of coordinates, and it has a mutation rate of 30%. The crossover was a two-point crossover, in which the placements of the crossover are generated as two unique random locations of the indices to create offspring. The mutation follows the RMHC algorithm. The selection method is through a tournament: after calculating the distances of all parents and offspring, they are ranked according to the lowest distance. 50% of those in the tournament pass the selection process.
Genetic Algorithm-Tournament (Added variation):
In this variation of the previous GA, an additional probability of 5% is included that allows some of the sets of coordinates that lost the tournament to survive to be able to create offspring in the next run. This introduces good genes that might have been neglected due to other bad genes and increases diversity in the algorithm. While it may slow down the process to get to a certain fitness as the original GA, it will result in a lower value after further evaluations. The other parameters such as the mutation rate and selection method are kept the same.
