Solving shortest path problem using genetic algorithms
| dc.contributor.author | Jayasooriya, C. I. E. | |
| dc.date.accessioned | 2024-11-17T12:41:07Z | |
| dc.date.available | 2024-11-17T12:41:07Z | |
| dc.date.issued | 2007 | |
| dc.description.abstract | This project report presents a Genetic Algorithmic (GA) approach to the Shortest Path (SP) routing problem. Genetic Algorithm (GA) is a relatively new optimization technique which can be applied to various problems including those that are NP-hard (Nondeterministic Polynomial). The technique does not ensure an optimal solution, however it usually gives good approximations in a reasonable amount of time. This therefore, would be a good algorithm to try on the Shortest Path Problem (SPP), one of the most famous NP-hard problems. Genetic Algorithms (GA) are loosely based on natural evaluation and use a survival of the fittest technique, where the best solution survive and are varied until we get a good result. It will explain in detail, including the various methods of encoding, crossover, mutation and evaluation. Variable length chromosomes (strings) and their genes (parameters) have been used for encoding the problem. The crossover operation exchanges partial chromosomes (partial routs) at positional independent crossing sites and the mutation operation maintain the genetic diversity of the population. The proposed algorithm can cure all the infeasible chromosomes with a simple repair function. Crossover and mutation together provide a search capability that results in improved quality of solution and enhanced rate of convergence. The proposed algorithm exhibits a much better quality of solution and much higher rate of convergence than other algorithms. The results are relatively independent of problem types (network types and topologies) for almost all sources — destination pair. | |
| dc.identifier.uri | https://ir.lib.pdn.ac.lk/handle/20.500.14444/3588 | |
| dc.language.iso | en_US | |
| dc.publisher | The University of Peradeniya | |
| dc.subject | Computer sciences | |
| dc.subject | Genetics | |
| dc.subject | Algorithms | |
| dc.title | Solving shortest path problem using genetic algorithms | |
| dc.type | Thesis |