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
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
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.</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 |