Damayanti, Aisah Feriera Awip (2019) Forest Optimization Algorithm untuk Menyelesaikan Travelling Salesman Problem. Sarjana thesis, Universitas Brawijaya.
Abstract
Travelling Salesman Problem (TSP) adalah masalah yang sering kita jumpai dalam kehidupan sehari-hari sehingga banyak penelitian dilakukan dalam bidang tersebut. Perkembangan penyelesaian TSP dapat dilakukan dengan metode tradisional dan algoritma heuristik. Namun, kedua metode tersebut memiliki kelemahan sehingga muncul algoritma pendekatan dari algoritma heuristik yaitu algoritma metaheuristik. Beberapa algoritma metaheuristik telah terbukti mampu menyelesaikan masalah tersebut dengan baik seperti algoritma Ant Colony Optimization (ACO), algoritma genetika (GA), dan Particle Swarm Optimization (PSO). Seiring dengan perkembangan zaman muncul beberapa algoritma metaheuristik, salah satunya adalah Forest Optimization Algorithm (FOA). Dalam perkembangannya, algoritma FOA memiliki performa yang cukup baik untuk menyelesaikan masalah optimasi fungsi kontinu dan masalah dengan sifat diskrit dan biner dibandingkan algoritma yang lain. Oleh karena itu, pada skripsi ini akan dibahas metode optimasi Forest Optimization Algorithm (FOA) untuk menyelesaikan Travelling Salesman Problem (TSP) dan hasilnya akan dibandingkan dengan algoritma Ant Colony Optimization (ACO). Data uji yang digunakan adalah data uji TSP WI29, DJ38, dan QA194. Rancangan FOA dibentuk mirip dengan aslinya dengan beberapa modifikasi pada tahap inisialisasi hutan dengan pohon berusia „0‟, tahap local seeding, dan tahap global seeding. Hasil yang diperoleh dari 30 kali simulasi menunjukkan bahwa FOA yang telah dimodifikasi belum berhasil mengungguli kinerja algoritma ACO pada data uji WI29 dan DJ38. Namun, untuk data uji QA194 FOA dapat mencapai kriteria pemberhentian meskipun nilai fitness yang diperoleh tidak lebih baik daripada algoritma ACO.
English Abstract
Traveling Salesman Problem (TSP) is a problem that we often encounter in everyday life so that a lot of research is done in that field. The development of TSP settlement can be done using traditional methods and heuristic algorithms. However, both methods have weaknesses so that the algorithm appears from the heuristic algorithm, namely the metaheuristic algorithm. Several metaheuristic algorithms have been proven to be able to solve the problem well such as the Ant Colony Optimization (ACO) algorithm, the genetic algorithm (GA), and Particle Swarm Optimization (PSO). Along with the development of the era several metaheuristic algorithms have emerged, one of which is Forest Optimization Algorithm (FOA). In its development, FOA algorithm has a good performance to solve continuous optimization problems and problems with discrete and binary properties compared to other algorithms. Therefore, in this paper we will discuss the optimization method of Forest Optimization Algorithm (FOA) to complete the Traveling Salesman Problem (TSP) and the results will be compared with the Ant Colony Optimization (ACO) algorithm. The test data used are TSP WI29, DJ38, and QA194 test data. The FOA design was formed to be similar to the original with some modifications at the forest initialization stage with trees aged '0', the stage of local seeding, and the global seeding stage.The results obtained from 30 simulations show that the modified FOA has not succeeded in surpassing the performance of the ACO algorithm in the WI29 and DJ38 test data. However, for QA194 FOA test data can reach the dismissal criteria even though the fitness value obtained is no better than the ACO algorithm.
Other obstract
-
| Item Type: | Thesis (Sarjana) |
|---|---|
| Identification Number: | SKR/MIPA/2019/160/051910863 |
| Uncontrolled Keywords: | TSP, FOA, ACO, FOA untuk TSP, Data Uji TSP, TSP, FOA, ACO, FOA for TSP, TSP Test Data |
| Subjects: | 500 Natural sciences and mathematics > 518 Numerical analysis > 518.1 Algorithms |
| Divisions: | Fakultas Matematika dan Ilmu Pengetahuan Alam > Matematika |
| Depositing User: | Budi Wahyono Wahyono |
| Date Deposited: | 05 Aug 2020 08:02 |
| Last Modified: | 05 Aug 2020 08:02 |
| URI: | http://repository.ub.ac.id/id/eprint/178583 |
Actions (login required)
 |
View Item |