Thesis Defense - University of Houston
Skip to main content

Thesis Defense

In Partial Fulfillment of the Requirements for the Degree of Master of Science

Ansh Dedha

will defend his thesis

Improved Genetic Algorithms for Route Optimization


Abstract

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
https://join.skype.com/Cpd2RGf9i62M
Advisor: Dr. Shishir K. Shah

Faculty, students, and the general public are invited.