In Partial Fulfillment of the Requirements for the Degree of Master of Science
will defend his thesis
Improved Genetic Algorithms for Route Optimization
Route optimization is a problem that has been studied for centuries. There exists numerous solutions to the problem, especially for scenarios that have a pre-defined discrete search space such as in the case of a network of roads, a network of cellular nodes, etc. However, in scenarios such as path-planning for long-distance electricity transmission lines, underground pipelines, railway tracks, etc., there does not exist any pre-defined network of roads. In such scenarios, many route optimization algorithms yield sub-optimal results because the size of the search space is an order of magnitude greater than conventional road network-based routing problems. The genetic algorithm has historically proven to yield good results in complex optimization scenarios. This paper identifies a suitable way to model genetic algorithms for such problems by using GIS data over a geographical region. The paper then purposes two algorithms inspired by the conventional genetic algorithm. The first algorithm introduces variations such as Performance-Based Mutation and use of the Steepest Descent Method in the genetic algorithm to yield better optimization results in large search spaces. It is found that the proposed algorithm outperforms the conventional genetic algorithm in terms of accuracy by 39.6%. The second algorithm takes into consideration the obstacles over a geographical region and avoids them by incorporating penalties into the genetic algorithm. The paper also identifies an underlying problem associated with the penalty-based approach (i.e. rapid loss of diversity) and introduces a novel Island Selection technique to avoid losing diversity within the population. Results show that the Island Selection technique helps in maintaining a diverse population for a greater number of generations, hence improving the overall accuracy of the algorithm when compared to the conventional genetic algorithm.
Date: Monday, April 27, 2020
Time: 4:00 PM
Place: Online Presentation - Skype
Advisor: Dr. Shishir K. Shah
Faculty, students, and the general public are invited.