A genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem
Open Loop Travelling Salesman Problem (OTSP) is one of the extension of Travelling Salesman Problem (TSP) that finding a shortest tour of a number of cities by visiting each city exactly once and do not rerurning to the starting city. In the past, TSP and OTSP has been applied in various vehicle rou...
Saved in:
Main Author: | |
---|---|
Format: | Thesis |
Language: | English English English |
Published: |
2016
|
Subjects: | |
Online Access: | http://eprints.uthm.edu.my/9943/2/24p%20CHIENG%20HOCK%20HUNG.pdf http://eprints.uthm.edu.my/9943/1/CHIENG%20HOCK%20HUNG%20COPYRIGHT%20DECLARATION.pdf http://eprints.uthm.edu.my/9943/3/CHIENG%20HOCK%20HUNG%20WATERMARK.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
id |
my-uthm-ep.9943 |
---|---|
record_format |
uketd_dc |
spelling |
my-uthm-ep.99432023-09-13T07:31:26Z A genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem 2016-01 Chieng, Hock Hung QA Mathematics QA299.6-433 Analysis Open Loop Travelling Salesman Problem (OTSP) is one of the extension of Travelling Salesman Problem (TSP) that finding a shortest tour of a number of cities by visiting each city exactly once and do not rerurning to the starting city. In the past, TSP and OTSP has been applied in various vehicle routing systems to optimize the route distance. However, in real-life scenario such as transportation problem does not seem similar as pictured in OTSP whereby do not all cities are required to be visited but simply restrain to several number of n cities. Therefore, a new problem called nCities Open Loop Travelling Salesman Problem (nOTSP) is proposed. In the past, Genetic Algorithm (GA) is a popular algorithm that used to solve TSPs. However, GA often suffers from premature convergence due to the difficulty in preventing the loss of genetic diversity in the population. Therefore, Genetic Simplified Swarm Algorithm (GSSA) is proposed in this srudy to overcome the drawback of GA. GSSA is an improved GA based algorithm with Simplified Swarm Optimization (SSO) algorithm's characteristic named Solution Update Mechanism (SUM). The SUM is modified by embedding three GA mutation operators. Then, GSSA is used to optimize nOTSP in terms of finding the shortest tour. Later, the performance of GSSA is compared with GA without crossover operator (GA-XX) and GA with onepoint crossover operator (GA-IX). Performance of the proposed algorithm is measured based on the shortest distance and average shortest distance found by the algorithm. Meanwhile, an investigation on influence of population size towards algorithm was also studied. The experiment results show that GSSA can discover shorter tour than GA-XX and GA-IX. Nevertheless, the study also found that most of the good solutions are discovered in the larger population sizes from 3000 to 5000. 2016-01 Thesis http://eprints.uthm.edu.my/9943/ http://eprints.uthm.edu.my/9943/2/24p%20CHIENG%20HOCK%20HUNG.pdf text en public http://eprints.uthm.edu.my/9943/1/CHIENG%20HOCK%20HUNG%20COPYRIGHT%20DECLARATION.pdf text en staffonly http://eprints.uthm.edu.my/9943/3/CHIENG%20HOCK%20HUNG%20WATERMARK.pdf text en validuser mphil masters Universiti Tun Hussein Onn Malaysia Fakulti Sains Komputer dan Teknologi Maklumat |
institution |
Universiti Tun Hussein Onn Malaysia |
collection |
UTHM Institutional Repository |
language |
English English English |
topic |
QA Mathematics QA299.6-433 Analysis |
spellingShingle |
QA Mathematics QA299.6-433 Analysis Chieng, Hock Hung A genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem |
description |
Open Loop Travelling Salesman Problem (OTSP) is one of the extension of Travelling Salesman Problem (TSP) that finding a shortest tour of a number of cities by visiting each city exactly once and do not rerurning to the starting city. In the past, TSP and OTSP has been applied in various vehicle routing systems to optimize the route distance. However, in real-life scenario such as transportation problem does not seem similar as pictured in OTSP whereby do not all cities are required to be visited but simply restrain to several number of n cities. Therefore, a new problem called nCities Open Loop Travelling Salesman Problem (nOTSP) is proposed. In the past, Genetic Algorithm (GA) is a popular algorithm that used to solve TSPs. However, GA often suffers from premature convergence due to the difficulty in preventing the loss of genetic diversity in the population. Therefore, Genetic Simplified Swarm Algorithm (GSSA) is proposed in this srudy to overcome the drawback of GA. GSSA is an improved GA based algorithm with Simplified Swarm Optimization (SSO) algorithm's characteristic named Solution Update Mechanism (SUM). The SUM is modified by embedding three GA mutation operators. Then, GSSA is used to optimize nOTSP in terms of finding the shortest tour. Later, the performance of GSSA is compared with GA without crossover operator (GA-XX) and GA with onepoint crossover operator (GA-IX). Performance of the proposed algorithm is measured based on the shortest distance and average shortest distance found by the algorithm. Meanwhile, an investigation on influence of population size towards algorithm was also studied. The experiment results show that GSSA can discover shorter tour than GA-XX and GA-IX. Nevertheless, the study also found that most of the good solutions are discovered in the larger population sizes from 3000 to 5000. |
format |
Thesis |
qualification_name |
Master of Philosophy (M.Phil.) |
qualification_level |
Master's degree |
author |
Chieng, Hock Hung |
author_facet |
Chieng, Hock Hung |
author_sort |
Chieng, Hock Hung |
title |
A genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem |
title_short |
A genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem |
title_full |
A genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem |
title_fullStr |
A genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem |
title_full_unstemmed |
A genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem |
title_sort |
genetic simplified swarm algorithm for optimizing n-cities open loop travelling salesman problem |
granting_institution |
Universiti Tun Hussein Onn Malaysia |
granting_department |
Fakulti Sains Komputer dan Teknologi Maklumat |
publishDate |
2016 |
url |
http://eprints.uthm.edu.my/9943/2/24p%20CHIENG%20HOCK%20HUNG.pdf http://eprints.uthm.edu.my/9943/1/CHIENG%20HOCK%20HUNG%20COPYRIGHT%20DECLARATION.pdf http://eprints.uthm.edu.my/9943/3/CHIENG%20HOCK%20HUNG%20WATERMARK.pdf |
_version_ |
1783728972036571136 |