ALGORITMA ANT COLONY OPTIMIZATION (ACO) UNTUK MENYELESAIKAN TRAVELING SALESMAN PROBLEM (TSP)

Main Authors: Leksono, Agus, Sarwadi, Sarwadi
Format: Thesis NonPeerReviewed application/pdf
Terbitan: , 2009
Subjects:
Online Access: http://eprints.undip.ac.id/7314/1/Tugas_Akhir_(full).pdf
http://eprints.undip.ac.id/7314/
ctrlnum 7314
fullrecord <?xml version="1.0"?> <dc schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ http://www.openarchives.org/OAI/2.0/oai_dc.xsd"><title>ALGORITMA ANT COLONY OPTIMIZATION (ACO) UNTUK&#xD; MENYELESAIKAN TRAVELING SALESMAN PROBLEM (TSP)</title><creator>Leksono, Agus</creator><creator>Sarwadi, Sarwadi</creator><subject>QA Mathematics</subject><description>Traveling Salesman Problem (TSP) merupakan persoalan yang penting dalam&#xD; sistem distribusi. Masalah traveling salesman secara umum digambarkan sebagai&#xD; suatu kasus dimana seseorang harus mengunjungi sejumlah kota dari suatu pusat&#xD; fasilitas dan kembali lagi ke tempat pemberangkatan semula, dengan asumsi jarak&#xD; diketahui. Tujuan dari masalah ini adalah untuk meminimalkan total jarak tempuh&#xD; salesman. Masalah traveling salesman termasuk kelas NP-Hard, sehingga sangat&#xD; sulit untuk diselesaikan menggunakan algoritma eksak. Untuk menyelesaikan&#xD; masalah tersebut biasanya digunakan algoritma heuristik. Algoritma Ant Colony&#xD; Optimization (ACO) merupakan salah satu metode metaheuristik yang&#xD; menerapkan semut sebagai agen dengan update Pheromone-nya untuk dapat&#xD; melakukan proses pencarian solusi yang efektif dan efisien. Algoritma ACO yang&#xD; dibandingkan sebanyak lima yaitu Ant System (AS), Elitist Ant System (EAS),&#xD; Rank-based Ant System (ASRank), Max-min Ant System (MMAS), dan Ant Colony&#xD; System (ACS). Simulasi dilakukan dengan mencari solusi mendekati optimal dari&#xD; beberapa kasus TSP dengan jumlah titik n = 20 sampai n = 115. Hasil mendekati&#xD; optimal diperoleh dengan melakukan beberapa kali percobaan untuk setiap kasus.&#xD; Selanjutnya hasil perhitungan untuk setiap kasus dan setiap algoritma&#xD; dibandingkan. Hasil perbandingan kelima algoritma ACO tersebut, terlihat bahwa&#xD; untuk jumlah titik sampai n = 40 solusi yang dihasilkan semua algoritma sama&#xD; baiknya. Untuk kasus dengan jumlah titik yang lebih banyak algoritma ACS&#xD; mempunyai solusi yang terbaik dan algoritma AS yang terjelek dari kelima&#xD; algoritma tersebut.</description><date>2009-07</date><type>Thesis:Thesis</type><type>PeerReview:NonPeerReviewed</type><type>File:application/pdf</type><identifier>http://eprints.undip.ac.id/7314/1/Tugas_Akhir_(full).pdf</identifier><identifier>Leksono, Agus and Sarwadi, Sarwadi (2009) ALGORITMA ANT COLONY OPTIMIZATION (ACO) UNTUK MENYELESAIKAN TRAVELING SALESMAN PROBLEM (TSP). Undergraduate thesis, Mathematics and Natural science.</identifier><relation>http://eprints.undip.ac.id/7314/</relation><recordID>7314</recordID></dc>
format Thesis:Thesis
Thesis
PeerReview:NonPeerReviewed
PeerReview
File:application/pdf
File
author Leksono, Agus
Sarwadi, Sarwadi
title ALGORITMA ANT COLONY OPTIMIZATION (ACO) UNTUK MENYELESAIKAN TRAVELING SALESMAN PROBLEM (TSP)
publishDate 2009
topic QA Mathematics
url http://eprints.undip.ac.id/7314/1/Tugas_Akhir_(full).pdf
http://eprints.undip.ac.id/7314/
contents Traveling Salesman Problem (TSP) merupakan persoalan yang penting dalam sistem distribusi. Masalah traveling salesman secara umum digambarkan sebagai suatu kasus dimana seseorang harus mengunjungi sejumlah kota dari suatu pusat fasilitas dan kembali lagi ke tempat pemberangkatan semula, dengan asumsi jarak diketahui. Tujuan dari masalah ini adalah untuk meminimalkan total jarak tempuh salesman. Masalah traveling salesman termasuk kelas NP-Hard, sehingga sangat sulit untuk diselesaikan menggunakan algoritma eksak. Untuk menyelesaikan masalah tersebut biasanya digunakan algoritma heuristik. Algoritma Ant Colony Optimization (ACO) merupakan salah satu metode metaheuristik yang menerapkan semut sebagai agen dengan update Pheromone-nya untuk dapat melakukan proses pencarian solusi yang efektif dan efisien. Algoritma ACO yang dibandingkan sebanyak lima yaitu Ant System (AS), Elitist Ant System (EAS), Rank-based Ant System (ASRank), Max-min Ant System (MMAS), dan Ant Colony System (ACS). Simulasi dilakukan dengan mencari solusi mendekati optimal dari beberapa kasus TSP dengan jumlah titik n = 20 sampai n = 115. Hasil mendekati optimal diperoleh dengan melakukan beberapa kali percobaan untuk setiap kasus. Selanjutnya hasil perhitungan untuk setiap kasus dan setiap algoritma dibandingkan. Hasil perbandingan kelima algoritma ACO tersebut, terlihat bahwa untuk jumlah titik sampai n = 40 solusi yang dihasilkan semua algoritma sama baiknya. Untuk kasus dengan jumlah titik yang lebih banyak algoritma ACS mempunyai solusi yang terbaik dan algoritma AS yang terjelek dari kelima algoritma tersebut.
id IOS2852.7314
institution Universitas Diponegoro
institution_id 69
institution_type library:university
library
library Perpustakaan Universitas Diponegoro
library_id 485
collection Diponegoro University Institutional Repository
repository_id 2852
city SEMARANG
province JAWA TENGAH
repoId IOS2852
first_indexed 2016-09-15T18:01:54Z
last_indexed 2016-09-22T20:48:00Z
recordtype dc
_version_ 1765880514350153728
score 17.13294