A novel solution to traveling salesman problem using fuzzy sets, gravitational search algorithm, and genetic algorithm
Throughout the history, many researchers have come across a problem in their real lives, called the Traveling Salesman Problem (TSP). This problem is to find the shortest route of a traveling salesperson that starts at a home city, visits a prescribed set of other cities and returns to the starting...
Saved in:
Main Author: | |
---|---|
Format: | Thesis |
Language: | English |
Published: |
2010
|
Subjects: | |
Online Access: | http://eprints.utm.my/id/eprint/11060/1/AmirAtapouriAbarghoueiMFSKSM2010.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
id |
my-utm-ep.11060 |
---|---|
record_format |
uketd_dc |
spelling |
my-utm-ep.110602018-05-30T02:32:45Z A novel solution to traveling salesman problem using fuzzy sets, gravitational search algorithm, and genetic algorithm 2010-04 Abarghouei, Amir Atapour QA75 Electronic computers. Computer science Throughout the history, many researchers have come across a problem in their real lives, called the Traveling Salesman Problem (TSP). This problem is to find the shortest route of a traveling salesperson that starts at a home city, visits a prescribed set of other cities and returns to the starting city. The distance travelled in such a tour obviously depends on the order in which the cities are visited and, thus, the problem is to find an optimal ordering of the cities. TSP is a representative of a large class of problems known as the combinatorial optimization problems. TSP is among the most important areas to explore, since it is very easy to describe, but very difficult to solve. There are several real-life applications of the TSP in several areas of knowledge including mathematics, computer science, operations research, genetics, engineering, and electronics. Many of the existing methods by which the TSP solved, suffer from considerable problems, such as lack of accuracy and speed. In this study, a hybrid method of TSP is proposed that can yield accurate results and relatively fast, without being trapped in a local optimum during the searching. In this approach, suitable fuzzy matrices are used to illustrate the details of the problem. A new optimization algorithm, called the Gravitational Search Algorithm (GSA) is applied to solve TSP as precise as possible, and finally the Genetic Algorithm (GA) finds the final answer in an acceptable amount of time. The results have illustrated that the proposed method are convincing compared to other related methods. 2010-04 Thesis http://eprints.utm.my/id/eprint/11060/ http://eprints.utm.my/id/eprint/11060/1/AmirAtapouriAbarghoueiMFSKSM2010.pdf application/pdf en public masters Universiti Teknologi Malaysia, Faculty of Computer Science and Information Systems Faculty of Computer Science and Information System |
institution |
Universiti Teknologi Malaysia |
collection |
UTM Institutional Repository |
language |
English |
topic |
QA75 Electronic computers Computer science |
spellingShingle |
QA75 Electronic computers Computer science Abarghouei, Amir Atapour A novel solution to traveling salesman problem using fuzzy sets, gravitational search algorithm, and genetic algorithm |
description |
Throughout the history, many researchers have come across a problem in their real lives, called the Traveling Salesman Problem (TSP). This problem is to find the shortest route of a traveling salesperson that starts at a home city, visits a prescribed set of other cities and returns to the starting city. The distance travelled in such a tour obviously depends on the order in which the cities are visited and, thus, the problem is to find an optimal ordering of the cities. TSP is a representative of a large class of problems known as the combinatorial optimization problems. TSP is among the most important areas to explore, since it is very easy to describe, but very difficult to solve. There are several real-life applications of the TSP in several areas of knowledge including mathematics, computer science, operations research, genetics, engineering, and electronics. Many of the existing methods by which the TSP solved, suffer from considerable problems, such as lack of accuracy and speed. In this study, a hybrid method of TSP is proposed that can yield accurate results and relatively fast, without being trapped in a local optimum during the searching. In this approach, suitable fuzzy matrices are used to illustrate the details of the problem. A new optimization algorithm, called the Gravitational Search Algorithm (GSA) is applied to solve TSP as precise as possible, and finally the Genetic Algorithm (GA) finds the final answer in an acceptable amount of time. The results have illustrated that the proposed method are convincing compared to other related methods. |
format |
Thesis |
qualification_level |
Master's degree |
author |
Abarghouei, Amir Atapour |
author_facet |
Abarghouei, Amir Atapour |
author_sort |
Abarghouei, Amir Atapour |
title |
A novel solution to traveling salesman problem using fuzzy sets, gravitational search algorithm, and genetic algorithm |
title_short |
A novel solution to traveling salesman problem using fuzzy sets, gravitational search algorithm, and genetic algorithm |
title_full |
A novel solution to traveling salesman problem using fuzzy sets, gravitational search algorithm, and genetic algorithm |
title_fullStr |
A novel solution to traveling salesman problem using fuzzy sets, gravitational search algorithm, and genetic algorithm |
title_full_unstemmed |
A novel solution to traveling salesman problem using fuzzy sets, gravitational search algorithm, and genetic algorithm |
title_sort |
novel solution to traveling salesman problem using fuzzy sets, gravitational search algorithm, and genetic algorithm |
granting_institution |
Universiti Teknologi Malaysia, Faculty of Computer Science and Information Systems |
granting_department |
Faculty of Computer Science and Information System |
publishDate |
2010 |
url |
http://eprints.utm.my/id/eprint/11060/1/AmirAtapouriAbarghoueiMFSKSM2010.pdf |
_version_ |
1747814803282329600 |