Hashim, Siti Zuraifah (2007) Finding minimum path by using Genetic Algorithm (GA)/ Siti Zuraifah Hashim. Degree thesis, Universiti Teknologi MARA.
Abstract
In this paper we considered finding minimum path problem which is known as shortest path problem. This problem generalizes several traditional shortest path problems and has applications in transportation and communication networks. The objective of this problem is to determine the shortest routes or paths between two points so that it can minimize the cost and time. This problem is simple and can be solved easily. However, practical transportation networks will become much more complicated and needed to solve efficiently. Roadways and telephone systems are the examples of them. Genetic Algorithms (GA), pioneered by John Holland, applies the principle of evolution found in nature to the problem of finding an optimal solution. It makes use of three basic operations in order to optimize this problem. They are: 1) Reproduction means the creation of new generations, 2) Crossover means interchanging of parts of parent strings into the child string, and 3) Mutation means the random bit flip. Although this problem can be solved by GA, other methods also exist. Dijkstra's Algorithm is one of them. This approach solves the singlesource shortest path problem with nonnegative edge weights. In this paper, GA has been applied to find the minimum path, then result will be compared with Dijkstra's algorithm are presented.
Download

Text
TD_SITI ZURAIFAH HASHIM CS 07_5 P01.pdf Download (102kB)  Preview 
Metadata
Item Type:  Thesis (Degree)  

Creators: 


Subjects:  Q Science > QA Mathematics > Instruments and machines > Electronic computers. Computer science Q Science > QA Mathematics > Instruments and machines > Electronic computers. Computer science 

Divisions:  Faculty of Information Technology and Quantitative Sciences  
Item ID:  983  
URI:  http://ir.uitm.edu.my/id/eprint/983 
Actions (login required)
View Item 