Finding minimum path by using Genetic Algorithm (GA)/ Siti Zuraifah Hashim

Hashim, Siti Zuraifah (2007) Finding minimum path by using Genetic Algorithm (GA)/ Siti Zuraifah Hashim. Degree thesis, Universiti Teknologi MARA.

Download

[thumbnail of TD_SITI ZURAIFAH HASHIM CS 07_5 P01.pdf]
Preview
Text
TD_SITI ZURAIFAH HASHIM CS 07_5 P01.pdf

Download (102kB) | Preview

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 single-source
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.

Metadata

Item Type: Thesis (Degree)
Creators:
Creators
Email
Hashim, Siti Zuraifah
UNSPECIFIED
Subjects: Q Science > QA Mathematics > Instruments and machines > Electronic Computers. Computer Science
Divisions: Universiti Teknologi MARA, Shah Alam > Faculty of Computer and Mathematical Sciences
Item ID: 983
URI: https://ir.uitm.edu.my/id/eprint/983

Fulltext

Fulltext is available at:
  • UNSPECIFIED
  • ID Number

    983

    Indexing


    View in Google Scholar

    Edit Item
    Edit Item