'l ;.
t!
i,
-'. i, "-''1'
,
.:
,,..-*f, .--. :.l
i' :'
i:
PROSIDING
r
',:::.'' ::
i,.
-
rr -
r I
t,: :, 1
/
/
:
Y"gyotonto, 1l-16uJuni OO11
l' .i
't'rt '' :l
Prosiding
SeminarNasional Aplikasi Teknologi Informasi 2OII Yogyakarta,17-18Juni 20ll
JurusanTeknik Informatika FakultasTeknologiIndustri,UniversitasIslam Indonesia Yogyakarta
DAFTARISI A. APLIKASI PADA BIDANG BISNIS DAN EKONOMI Strategi Adopsi Teknologi Informasi Berbasis Cloud Computing untuk UsahaKecil dan Menengahdi Indonesia AdiskaFardani,Kridanto Surendro
A-1
Chief Information Officer dan Perannya dalam Aktualisasi Manaiemen A-7 Strategi AgungDarono frrwnsible Business Reporting Language (XBRL): Implikasi Paradigma dan Rantai Pasok Pelaporan Keuangan Arif Perdana
pada
Isomorfisma dalamAdopsi Teknologi Informasi pada UsahaMikro, Kecil dan Menengah (UMKM) Arif Perdona
A-I4
A-21
Sistem Pendukung Keputusan Pembiayaan Mikro Berbasis Client Server A-29 Studi Kasuspada PerusahaanPembiayaanBandar Lampung Ernain,Rusliyawati, lmelda Sinaga Ileteksi Indikasi Fraud dengan Teknologi Audit Fiti Annisa,Lutfi Harris
A-35
Slstem Informasi Akuntansi Pembelian Material pada Perusahaan A-4L bnfaktor LionawatiChristian,Dinna MeutiaAzzahra Slstem Informasi Akuntansi Pengeluaran Kas (Studi Kasus : BNI Syariah A-47 fahawati Jakarta Selatan) llia Kumaladewi,NurAeni Hidayah,Tri RizkiAmalia lplikasi Metode Fuzzy Multi Criteria Decision trfiaking (FMCDM) untuk @imalisasi PenentuanLokasi Promosi Produk tlwhirtamely Kahar,Nova Fitri
A-58
hgaruh Teknologi Informasi dan Perubahan Organisasidalam Bisnis futtto FernandiWijaya
A-64
fencang Bangun Aptikasi Media Reservasi Makanan Berbasis Bluetooth A-7L (fudi l(asus D'cost Restaurant) &tryosn, RezaKurniawan lbrgenalan Waiah Pelanggan Toko tunuil Tjihorjadi
A-77
Sistem Informasi Surat Elektronik MochamadKarjadi,AgusHeksoPambudi
E-6L
Sistem Pendukung Keputusan untuk Menentukan Pilihan Minat E-66 Perguruan Tinggi di Kota ]ambi dengan Menggunal
E-87
Sistem Informasi Penelitian dan Pengabdian Dosen Guna Otomatisasi E-92 Penentuan Angka Kredit Dosen dan Mendukung Aktivitas Tridharma Perguruan Tinggi Hari Setiaji,RahadianKurniawan SIRKELLibrary ManagementSystem (Slims) RakhmatSyarifudin,RendyRessaSutrisno,DhomasHatta Fudholi
E-99
Aplikasi Cloud Computing untuk Mendukung Collaborative Research E-106 pada Pembimbingan TugasAkhir di furusan Teknik Informatika FTI UII YudiPrayudi F. APLIKASI PADA BIDANG TEKNIK hplementasi faringan Syaraf Tiruan Recurrent dengan Metode F-1 Fembetaiaran Gradient Descent Adaptive Learning Rate untuk Fendugaan Curah Huian ,ffin GalihSalman Xlisain Directional 3 DB Coupler untuk Sistem Keamanan Transmisi F-9 WDill Fiber Optik fullniHeryana,Ary Syahriar PerencanaanStrategis Sistem Informasi dan Teknologi Informasi pada F-13 Fcrrrsahaan Otomotif dengan Menggunakan Metodologi Tozer fufui Wijaya,DanaIndra Sensuse
Integrasi Arsitektur dan Manaiemen Layanan TI Untuk Pencapaian F-19 Fleksibilitas Teknologi Informasi pada Organisasi Aradea Model Analysis-By-Synthesis Aplikasi Pembangkit Suara Gamelan F-26 Sintetik Aris Tjahyanto,YoyonK Suprapto,Diah PuspitoWulandari Implementasi Metode Frame untuk Mendiagnosa Kepribadian Dramatik Menggunakan Sistem Pakar AsaharJohar,DesQtDwitia Palupi
Gangguan F-32
Program Simulasi Perhitungan Populasi Fluks Neutron dalam Teras F-37 Reaktor Nuklir BagusTri Atmoyo,Syarip,Supriyono Implementasi object Relational lvlapping (oRM) Menggunakan F-43 Hibernate (studi Kasus : Aplikasi Peminiaman Inventaris Program studi Informatika Unsoed) BangunWijayanto Implementasi dan Analisa Kineria Algoritma Ant system (AS) dalam F-48 Penyelesaian Multiple Travelling Salesman Prgblem (MTSP) Boko Susilo,RusdiEfendi,SitiMaulinda L.' Analisa Pengujian Optimalisasi Kineria Website Diyurman Gea
F-Ss
Estimasi Citra Polarisasi Langit Edi Susanto,Dwi Nuri Putri Dharma, RiwaldiPudja,RemiSenjaya
F-60
Dampak Penerapan Prioritas Investasi Bidang Teknologi Informasi Menggunal
F-66
Aplikasi faringan Syaraf Tiruan Propagasi Balik pada System Olfaktori Elektronik Larik SensorGasuntuk Deteksi fenis Bahan Herbal Fajar Hardoyono,Kuwat Triyana, BambangHeru Iswanto
F-74
Pengelompokan Sunspot pada Citra Digitat Mahatari Menggunakan F-81 Metode Clustering Dbscan Gregoriussatia Budhi, Rudy Adipranata, Matthew Sugiarto, Bachtiar Anwar, BambangSetiahadi Pengoptimalan Software S-PlusGuna Estimasi Model Regresiuntuk Data F-86 dengan Kesalahan Pengukuran Menggunakan Metode Bayes Hartatik
SeminarNasionalAplikasi Telonlogi Infonnasi 201I (SNATI201I) Yogtakarta,I 7-18Juni 201I
ISSN:1907-5022
IMPLEMENTASI DAN ANALISA KINERJA ALGORIT MA ANT ^SY,SZEM (AS) DALAM PENYELESAIAN MULTIPLE TRAVELLING SALESMAN PROBLEM (MTSP) Boko Susilo, Rusdi Efendi, Siti Maulinda Program Studi Teknik Informatika, Fakultas Teknik, (Jniversitas Bengkulu E'mail : adiluhung| [email protected], r -efendi@yahoo. com, lindsay. maul inda@gmait. com ABSTRAK Penelitian ini bertuiuan untuk membangun dan menganalisa kinerja suatu sistem algoritma Ant System (AS) untuk penyelesaian Multiple Travelling Salesman Problem (MTSP). WSP odalah periasalahan disiibusi yang membutuhkan lebih dqri satu salesman untuk mengunjungi sejumlah titik dqn kembali ke titik awal. Sistqs dibangun dengan menggunakan pemrograman Delphi 7 dan dstabqse IzIySQL. Hasil dari keseluruhan proset pada sistem ditampilkan dalam bentuk teks maupun visuqlisasi yang menunjukkan rute perjalanan dari setiq salesman. Sistem ini cukup efedif dalam penentuan rute dan jarak minimum untui pirmasalahan It[Iip tersebut. Pengujian dengan kasus-kasus yang berbeda menunjukkan adanya p"ngo*i iumlah titik, junld sqlesman dan nilai parameter (a, p dan p) terhadap performa algoritma. Kata kanci: Ant System (A$, MTSP, rute, jarak
1. PENDAIIULUAN Multiple TravellingSalesmanProblem (MTSP) adalah pengembangandari permasalahanTSP. MTSP adalah permasalahan distribusi yang membutuhkan lebih dari satu salesman untuk mengunjungi sejumlah titik dan kembali ke titik awal. Penelitian yang telah dilakukan Leksono (2009) menemukanbahwa salahsatu algoitma Ant Colony Optimization (ACO) yaitu pendekatanAnt System (AS) merupakan pendekatanyang bagus untuk mencari solusi yang mendekati minimum untuk permasalahanTravelling SalesmanProblem (TSP). Oleh karena algoritma AS telah terbukti cukup mampu dalam pemecahanmasalah TSp, makatujuan penelitianini adalahmembangunsuatu aplikasialgoritmaAS untukpenyelesaian kasusTSp yang lebih kompleks yaitu Multiple Travelling SalesmanProblem (MTSP).Ant System(AS) adalah algoritma yang mengadaptasi perilaku/aktivitas semut dalam mencari jalur terpendek ke suatu sumber dan dapat digunakanuntuk menyelesaikan kasussepertiMTSP.Bagianyangakandibahasjuga mencakuppengaruhnilai parameter-parameter yang digunakanalgoritmaAS dalamprosespembangunan solusiyangminimum. Dalampengembangan sistem,batasanmasalah yang digunakanmelingkupihal-hal sebagaiberikut : o Jenis graf yang digunakanadalah graf lengkap (completegroph) tak-berarahdan memiliki bobot yangmerepresentasikan jarak antartitik. r Jenis permasalahanMTSP yang dibahasadalah kasusdepot tunggal.Padapenelitianini, Titik ke-l ditetapkan sebagaititik yang dijadikan depot. o Jumlahsalesman yangdiperbolehkan tidak boleh melebihi aturanyang telah disesuaikandengan jumlah titik.
o Visualisasi graf berupa simulasi tanpa sb denganj arak sebenarnya. Dengan demikian, penelitian ini dihar4h dapat menjadi salah satu referensi dalr pengembangan penyelesaian kasus MTS selanjutnya.
2. LAI\IDASAI\ TEORI 2.1 Graf Menurut Pradhana (2006) *Graf himpunansimpul yang dihubungkandengan busur. Setiap busur diasosiasikan dengan tepa simpul".
Munir (2006) menyatakan graf G matematissebagaipasangan himpunan(I/,E) Z = himpunantidak kosongdari simpul : himpunan busur Iv,,vr...,vn|, E menghubungkan sepasang simpul vi: {erer_* Busur e1: (v6v) adalahpasangansimpul c V dan nilai ij : 1,2,3,... Berdasarkan pengertian diatas,
disimpulan bahwa sebuahgraf G sebagai pasangan (V,E), dimana y sekumpulantitik dan E adalahrelasi biner yang artinya E adalahkumpulan busur y4 menghubungkantitik-titik Z. Contoh grd dilihat sepertiGambar2.1berikut:
Pemodelangraf padakasusMTSP dibahaspada penelitian ini terbataspade termasuk jenis graf lengkap (complete
berarahdan memiliki bobotyang F-48
SeminarNasionalAplilcasiTehologi Informasi 201t (SNATI201t) Yognlarta, 17-18Juni 201I
jarak. Graf lengkap adalah graf sederhanayang setiap titiknya mempunyai busur ke semua titil lainnya-Graf tak-berarahadalahgraf yang busurnya tidak memiliki orientasi arah.- Sedangkan Graf berbobot (wetghtedgraph) adalahgraf yang setiap busurnya diberi harga(bobot) yangdalampenelitian ini nilai bobot adalahpanjangjarak. Gambar2.2 menunjukkancontohgraf lengkapyang tak-berarah danberbobot.
ISSN:1907-5022
Menurut Setiyono (2002) secara matematis persoalan MTSP dapat diformulasikan sebagai berikut:
"=*"[iE"*,,]
(2.1)
Kendalanya adalah : T
r
L*r, i-1
= l tnhrkJ = 1,2,3,...,?-1
(2.2)
*
r = luntr* i = tr,&3,...,a;f L*rt j=t Gambar2.2 Contohgraf lengkapyangtakberarahdanberbobot
f,
2.2 Muftiple Travelling Salesmanproblem Dalamteoremagraf, MTSp dapatdigambarkan sebagaiberikut : Bila diketahui suatugrafberbobot penuh dan lengkap (dimana tiap titiknya merepresentasikan titik-titik, tiap busur merepresentasikan tiap jalan dari satu titik ke titik lainnya, dan tiap bobot busur merepresentasikan jarak ataubiaya yang dibutuhkanuntuk menempuh jalan dari satu titik ke titik lainnya), maka tujuan penyelesaianMTSP adalah mencari sirkuit-sirkuit Hamilton dari setiapperjalanansalesmanyangbobot totalnyapaling kecil. Sirkuit Hamilton adalahsuatu lintasanpadagraf yang melalui setiaptitik tepatsatu kali dan akan kembali ke titik awal, tetapi tidak perlu melalui melalui semuasisi yang adapadagraf. lirkuit hamilton setiap salesmanselanjutnyaakan disebutrute salesman. Contoh solusi MTSP dapat dilihat pada Gambar2.3. Gambartersebutadalahcontoh solusi yang dikerjakanoleh 3 orangsalesman.Depot (agen pusat) diberi tanda dengantitik l. Sedangkanruterute yang berhasildibentuk ketiga salesmansebagai berikut: o Salesmanl:1)3+7)l o Salesman2:l)2)6)l o Salesman3:l)5)4)l ('
:')
o
/
4
,--t
t
lRute sal"sman
a\
/\
a Sirpul depot
6
)
(2.3)
2
Gambar 2.3 Contoh solusi MTSp (Junjie dan Dingwei,2007)
F-49
T L *t'= * i=l
(2.4)
r
T Ltti
= *
(2.5)
j=t
Dengan Z: totalnilai minimum Xii = l, jika ada perjalanansalesmandari titik , menujutitikT xU: 0, jika tidak adapedalanansalesmandari titik t menujutitikT ci.; : menyatakanjarak antaratitik i menujutitik j dengan i darrj: 1,2,3... Persamaan(2.1) merupakanfungsi objektif yang akan dicari. Persamaan(2.2) dan (2.3) menjamin bahwa setiap titik hanya dikunjungi sekali, sedangkan persamaan (2.4) dan 12.5; menjamin bahwa sejumlah rz salesmanmelakukan ruteperjalanan. 2.3 Ant System(AS) Menurut Dorigo dan Gambardella (dalam L-9ksono,2009), Ant Colony Optimization(ACO) diadopsi dari perilaku koloni semut yang dikenal sebagaisistemsemut.Sedangkan Ant System(AS) sendiri adalah sebuah algoritma dalam kelompok ACO yang diaptikasikan untuk masalah TSp. Beberapajenis pendekatanACO yang lain yaiatAnt System(AS), E/rr,rr Ant System(EAS), Rank-based Ant System(ASRank), dan Max-min Ant System (MLIAS). Secarainformal, khususnyauntuk kasus TSp murni, AS bekerja sebagaiberikut : Setiap semut memulai rutenya melalui sebuahtitik yang dipilih -secTaacak (setiap semut memiliki titik awal yang berbeda).Secaraberulangkali, satu per satu titil yang adadikunjungi oleh semutdengantujuanuntuk menghasilkansebuahrute. pemilihan titik-titik yang akan dilaluinya didasarkan pada suatu fungsi
SeminarNasionalAplikasi Telonlogi Informasi 2011 (SNATI 2011) Yogtakarta,I 7-I 8 Juni 20I I
probabilitas, dinamai aturan kansisi status (s/cte transition rule), dengan mempertimbangkan visibility (invers dari jarak) titik tersebutdanjumlah feromon yang terdapat pada ruas yang menghubungkan titik tersebut. Perbedaanmendasarsistem kerja AS pada kasusTSP dan MTSP terletakpadainisialisasiawal semut. Sepertidijelaskandiatas,pada kasusTSP, inisialisasi awal dilakukan dengan meletakkan semut-semutpada titik awal secaraacak, dimana setiapsemutakanmemiliki titik awal yangberbeda. Kemudiansemut-semuttersebutharus mengunjungi semua titik yang belum dikunjungi untuk menghasilkanrute-nya masing-masing.Sedangkan untuk kasus MTSP, inisialisasi awal dilakukan dengan meletakkan semut-semutpada suatu titik awal (yang akan dianggap sebagaidepot tunggal). Kemudiansemutpertamaterlebihdahulumenempuh sejumlah titik yang belum dikunjungi. Misalkan jumlah titik yang harus dikunjungi semut ke-i ditetapkan dengan notasi tni, maka ketentuan nilainya harus mengikuti persamaanberikut (Junjie danDingwei,2007): 2
(2.6)
+
Q'7)
)"0
=z-t
i
Dengan /; : jumlah maksimal titik yang dapat ditempuh semuti rz : jumlah salesman n : jumlahtitik dengani : 1,2,3,... Saat semut i sedang membangun rute perjalanan,jika jumlah titik yang dikunjungi semuti samadengantn;, fi:m,kahal ini berarti bahwa semut selanjutnyasiap untuk memulai perjalanannyadari depot. Semut selanjubryaharus mengunjungititiktitik yang belum dikunjungi semut sebelumnya. Titik-titik yang telah dikunjungi akan disimpan dalam tabulist. Setelah semua titik telah berhasil dikunjungi, maka perhitungan jarak perjalanan setiapsemutakandijumlahkan. Aturan-aturan AS yang berlaku pada kasus TSPjuga digunakanpadapenyelesaian kasusMTSP, namun dengan penyesuaianlebih lanjut. Aturanaturantersebutadalahsebagaiberikut : 2.3.1 Aturan Transisi Status (State Transition Rule') Transisi status dapat disamakan dengan perpindahansatu titik ke titik lain. Anggap bahwa probabilitas semut k bergerakdari titik i ke titik j adalah S, menggunakanrumus probabilitas berikut(JunjiedanDingwei,2007):
ISSN:1907-5022
h,iG)'l[atn1 rikaieA1' E -J"JGit (2.8) Jika sebaliknya Dengan i danj : indeks titik dengan i danj : 1,2,3,...,n-I dengan n adalah banyak titik t1i : intensitas feromon pada busur (iy) yang akan selalu diperbaharui pada setiap siklus
dii : jarak dari titik i ke titikT. Jika jarak antartitik hanya diketahui koordinatnya saja maka d,7 =
Jtrr - x;)F* (lt -r.
4;; : fungsi bobot pilihan (visibilitasantartitik)atau invers jarak. Nilai 4;;: (di)a atau
16 : himpunan titik-titik yang semut k belun kunjungi. Ap n-tabu1,O dengan tabuy G) menunjukkantitik-titik yang semutk telah kunjungi dan n menunjukkanbanyaktitik. o, : tetapan pengendali intensitas feromon semul dengannilai (a) > 0 p : tetapanpengendalivisibilitas dengannilai (p) > 0. 2.3.2 Aturan Pembaruan Feromon (Upda PheromoneTrail) Pembaruan feromon adalah elemen krmci untuk mengadaptasi teknik pembelajaran ACOPeranandari aturanpembaruanferomon ini adalah untuk mengacak arah rute-rute yang sed"'!g dibangun, sehingga titik-titik yang telah dilervai sebelumnyaoleh rute seekor semut mungkin akm dilewati kemudian oleh rute semut yang lain Dengan kata lain, pengaruh dari pembaruan ini adalahuntuk membuattingkat ketertarikanru{ts-nnr yang ada berubahsecaradinamis: setiapkali seekc semut menggunakansebuah ruas maka ruas ini dengan segera akan berkurang tingfr ketertarikannya (karena ruas tersebut kehilangn sejumlahferomonnya),secaratidak langsungs€ml yang lain akan memilih ruas-ruaslain yang beluu dikunjungi. Konsekuensinya, semut tidak ah memiliki kecenderungan untuk berkumpulpadajafrr yang sama, sehingga terdapat kemungkinan 1q lebih tinggi dimana salah satu dari mereka ah menemukansolusi yang lebih baik daripadajilr mereka semua berkumpul dalam rute yang samHal ini dilakukan denganpersamaanharga ferorrrr berikut: ril=
Ptti*Ari;
(2.S
Dengan p : parameterkecepatanpenguapanferomondengr nilai 0
SeminarNasionalAplikasi Tehologi Informasi 201I (SNATI201l) Yogtakana,I7-18 Juni 201I
ISSN:1907-5022
f,l
a",r=f l"g l=f
(2.10)
Dengan k: indekssemutdengannilai k :1,2,3,..., rn-L m: jumlahsemut Ar;,I adalah perubahan harga intensitas jejak feromon antartitik setiap semut yang dihitung berdasarkanpersamaanUeiitut : n
*ltn, ^ _n | 4rfi.1 L O,
iikanen€Elrm*erbusur(ii)
(2.1l)
iikasebalihrya
Dengan Q: tetapansiklussemutyangbernilaikonstan Ls: jarakyangtelahditempuhsemut-& Lk dapat dihitung dengan menggunakan persarnaan berikut : l* =
f,-l f-r
.L
dto.tnXrtr"rn*rn*$+ 4t'n4h)rdrnk(r)
Q.l2)
t=l
Dengan s : indekstitik dengannilai : 1,2,3,...,n-2 dtouo,lt).to.t,1tr : jarak busur dari titik s sampai ke titik s+/ padatabulist yang ditempatisemut& 4oanrt"p"l". : jarak antara titik r (akhir) dan titik pertama (awal) pada tabulist yang ditempati semut&. Dalam hal ini, nilai Lp sama artinya dengan pqnjang sirkuit hamilton bagi setiap semut (salesman).Perhitungantotal jarak yang ditempuh s€mua semut dapat dihitung dengan persamaan berikut:
Gambar3.4FlowchartSistemAplikasi SecaraUmum 3.2 Flowchart Algoritma AS Flowchart algoritma Ant System (AS) yang menggambarkan alur tahapanalgoritrnadapatdilihat padaGambar3.5.
flf,
r rotal = LLx t=r
(2.r3)
Dengan demikian, model penyelesaian MTSP dengan menggunakan algoritma AS diformulasikan menjadi persamaan berikut : \-r
z= ntuLLr
(2.r4)
*=l
Dengan
m : jumlah semut(salesman) Z:nilai minimumyangdicari k : indekssemutdengannilai k = 1,2,3,...,m-l 3. Analisisdan Perancangan Sistem 3.1 Flowchart Sistem Flowchart sistem secara umum yang menggambarkan alur kerja sistemdapatdilihat pada Gambar3.4.
Gambar3.5Flowchart AlgoitmaAnt System F-51
ISSN:1907-5022
Seminar NasionalAplilwsi TelmologiInformasi 2011 (SNATI2011) Yognkana, 17-I 8 Juni 201I
3.3 ImplementasiAntarmuka Imilementasi antarmukauntuk penggunadapat dilihatpadaGambar3.6 danGambar3.7. Antarmuka Input terdiri dari PanelIsian Jumlah Titik, Panel Isian Parameter, dan Tabel-tabel Bantuanyang melingkupi Matriks Jarak Antartitik, Tabel Koordinat, Tabel Visibilitas dan Tabel Feromon yang menampilkan intensitas feromon pada setiapbuiur. Setelahsemuainput dimasukkan, mat
4.1 Analisis BerdasarkanJumlah Titik Analisis berdasarkanjumlah titik ini dilakukan dengan memberikan masukan yang memrrut spesifikasi awal dan pengetahuanyang diijinkan' Pengujiandilakukandenganmasukandatakecil (10 titik dengan2 salesman),data menengah(25 titik dengan5 salesman),dan data besar(40 titik dengan 8 ialesman) yang masing-masing dilakukan sebanyak10 kali dengandatayang sama' Hasil pengujian tersebut dapat ditampilkan seoertisrafik oadaGambar4.1.
1000 8oo
tr = E := tr
;
600
-10drt
4oo
-25titit
E 2oo
Eo t-
-40titt 12 3 4 5 6 v I910 ke' Percqbaan
Jumlah Gambar4.1 Hasil PengujianBerdasarkan Titik Gambar3.6 AntarmukaInPut Antarmuka Output terdiri dari grafik minimum per Siklus, rincian per siklus, serta hasil minimum didapatkan dari siklus-siklus tersebut' yutg -sedingkan PanelGraf Minimum akanmenampilkan bentuk graf lintasan setiap salesman yang
Gambar3.7 AntarmukaOutPut 4. HASIL DAN PEMBAHASAN Implementasi untuk menganalisis kinerja sistem dibutuhkan untuk mengetahui kehandalan sistem dan keoptimalan hasil yang didapatkan' Analisis yang dilakukan melingkupi perubahan masukanjumlah titik, jumlah salesman,dan jumlah salesman.
Dari hasil pengujian tersebut maka dapat diambil beberapakesimpulansebagaiberikut : 1. Semakin banyak jumlah titik, maka semakin banyak waktu proses yang dibutuhkan unnrk j arakminimum' mendapatkan 2. Semakin banyak jumlah titik, maka semakin banyak variasi hasil jarak minimum yang didapatkan. Hal ini disebabkan peningkatan jumlah probabilitas titik yang akan dipilih selanjutnya. 3. Semakinsedikitjumlah titik, semakinstabiljant minimum yang dihasilkan pada setiap sikhrs" Dengan kata lain, semakin sedikit jumlah titit' maka akan semakin dekat dengan nilai peling minimal. Hal ini terlihat pada grafik yang menunjukkanbahwakurva grafik padapengujia data kecil lebih terlihat stabil kar@ menghasilkan jarak minimum dengan selisih yang relatif kecil' Sedangkanpengujian dan iedangdan databesarrelatifkurang stabil kareor menghasilkan jarak-jarak dengan perbedam selisihyangbesar. 4. Semakin sedikit jumlah titik, semakin cePil terjadinya konvergensi. Hal ini terlihat bahwe prosespadapengujiandatasedangdan databesr ielalu berhenti pada siklus maksimal yang telah ditentukanyaitu 10 siklus, sedangkanpengujim data kecil terdapat 5 hasil pengujian png prosesnya telah berhenti sebelum mencapd siklus maksimal. 4.2 AnatisisBerdasarkanJumlah Salesman Analisis terhadapjumlah salesmandiperluh untuk mengetahui pengaruh jumlah salesmm F-52
ISSN:1907-5022
SeminarNasionalAplilasi Telnalogi Informasi201I (SNATI201I) Yognkana, I 7-l 8 Juni 20I I
terhadap jarak minimum yang dihasilkan. Pada pengujian ini akan digunakan 10 titik. Untuk pengujiandengantitik, makajumlah salesmanyang dibolehkan yaitu : 2, 3, dan 4. Setiap pengujian menggunakanjarak antartitik yang samadan setiap salesmandilalcukansebanyak5 kali. Hasil pengujian dalambentukerafik dapatdilihat padaGambar42 600
5 soo
300
5 2so E 2oo = 150
F 1oo ;so go 0.2 0.5 0.8
€ 4oo E 3oo i 2oo s 1oo Eo t:
1
1.2 1.5 1.8
2
Gambar4.3 PengaruhNilai a dan p terhadap PerformaAlgoritma
E
a50
.E 2oo € lso Gambar4.2 Grafik Hasil Minimum Berdasarkan JumlahSalesman dapat Dari hasil Pengujian tersebut : disimpulkanbahwa 1. Semakinbanyakjumlah salesmanmaka semakin panjangjarak yang didapatkandan semakinlama waktu prosesyang dibutuhkan.Dengankata lain, peningkatanjumlah salesmanpadajumlah titik jarak jarak- Hal yang samaakanmemperpanjang ini dikarenakansemakinbanyaktambahanjarak busur untuk menutup rute masing-masing salesmankembalike titik awal (depot). 2- Grafik peningkatan jumlah salesman untuk jurnlah titik yang samamembentukgrafik yang mendekatilinier.
{jl AnalisisBerdasarkanNilai Parameter Parameter- parametero, p, dan p mempunyai Fngaruh terhadap performa hasil yang diperoleh mda algoritmaAnt System.Padapengujianini akan dbahas nilai - nilai parameter tersebut terhadap &lrasi hasil perhitungan minimum untuk luyelesaian masalah MTSP. Nilai parametertrmeter tersebutakandiuji dengannilai a e {0.2; G 5 ;0 . 8 ;1 ; 1 . 2 ; 1 . 5 ; 1 . 82;) , P e { 0 . 2 ;0 . 5 ;0 . 8 ;1 ; , a np e { 0 . 1 ; 0 . 3 ; 0 . 5 ; 0 . 7 ; 01. 9} .; l l ; 1 . 5 ;1 . 8 ; 2 ) d .Ita salahsatuparameterdiganti nilainya, makanilai lain akan dibuat tetap Pengujian lraoeter drkukan dengan membandingkanpengaruh nilai lrmeter untuk 15 titik dengan3 salesman.Nilai irak antartitik pada setiap percobaanakan dibuat -na.
Setelahmelakukaneksperimen,makapengaruh dhi parameteru dan p dapat dilihat pada Gambar {3, dan pengaruhnilai parameterp dapat dilihat Fda Gambar4.4.
t 1oo l'
850 € F0
0.1
0.3
0.5
a.7
0.9
Gambar4.4 PengaruhNilai p terhadapPerforma Algoritma Dari hasil pengujian tersebut maka dapat disimpulkanbahwa: 1. Pengaruhnilai a, F dan p menghasilkanjarak yang bervariasi dan tidak mengikuti pola tertentu. Hal ini terlihat pada kurva grafik yang selaludinamis. 2. Dat'r ketiga parameter tersebut didapatkan kombinasi yang paling bagusuntuk memperoleh hasilyangterbaikyaituc :0.2,8: 1 danp: 0,5 . Meskipun demikian, tidak ada pemilihan nilai parameter yang pasti untuk memperoleh total jarak yang paling minimun5 karena nilai parameter dan jumlah titik serta jarak yang dihasilkan tidak memiliki pola tertentu. Hal ini juga tergantung pada besarnya masalah yang diselesaikan. 5. KESIMPULAN Berdasarkanhasil penelitian dan pembahasan yang telah dilakukan,dapatdisimpulkanbahwa: l. Algoitma Ant System (AS) telah berhasil dibangun dan diimplementasikandengancukup efektif digunakandalampenyelesaianMTSP' 2. Hasil percobaan menujukkan bahwa semakin banyakjumlah titik, maka: o semakinbanyakvariasi hasil jarak minimum yang didapatkan o semakin tidak stabil jarak minimum yang dihasilkanpadasetiaPsiklus o semakinlamaterjadinyakonvergensi.
F-53
Seninar NasionalAplikasi Telnalogi Informasi 201I (SNATI201I) Yogtalrarta,I7-18 Juni 201I
3. Hasil percobaanmenujukkanbahwapeningkatan jumlah salesmanpada jumlah titik yang sama jamk yangdidapatkan. akanmemperpanjang 4. Hasil percobaan menunjukkan pengaruh parametersebagaiberikut : o Pengaruhnilai u, F dan p menghasilkanjarak yangbervariasidan dinamis. o Kombinasi yang paling bagus untuk memperolehhasil yang terbaik yaitu tr : 0.2, p = I dan p:0,5 . Meskipundemikian,tidak ada pemilihan nilai parameter yang pasti untuk memperolehtotal jarak yang paling minimum, karenanilai parameterdanjumlah titik serta jarak yang dihasilkan tidak memiliki pola tertentu. DAFTAR PUSTAKA Amin R" dkk. 2006. Travelling SalesmanProblem. Tersedia : [Online] www.informatika.org/- r inaldi/ StmiA MokaIald MakalahStmik3 O.pdf[2] Maret 20I 0/ Beltas, Tolga. 2004. *The multiple traveling problem:an overviewof formulations salesman and solution procedures".Omega 34 (2006) 209 : 219. [Online] Tersedia : han4.tem.nctu.edu.tw/Thesis/.../The multiple traveling salesman problem-an overview of formulations and solution procedures.pdf 12 Juni20101 Deny. 2000. Stnthur Data dan Algorilma. Fakultas Ilmu Komputer.UniversitasIndonesia. Efendi, Rusdi. 2003. PenerapanAlgoritma Semut Untuk Pemecahqn Masalah Spanning Tree pada kosus pemctsangan Jaringan Kabel Telepon. Fakultas Teknologi Industri. UniversitasIslam Indonesia : Skripsi Tidak Diterbitkan. Feryanto, Aris. 2009. Ant Colony System untuk PenyelesaianMasalah Travelling Salesman Problem. Tersedia : [Online] www.informatika.org/-r inaldi/StmiV2009.../ M akalahlF305I -2009-02Lpdf pl Maret20101 Hasibuan,Zainal. 2007. MetodologiPenelitianPada Bidang Ilmu Komputer Dan Telmologi Informasi. Fakultas Ilmu Komputer. UniversitasIndonesia. Junjie, P dan Dingwei, W. 2006. An Ant Colony Optimization Algorithm for Multiple Travelling SalesmanProblem.Proceedingsof the First International Conference on Innovative Computing, Information and Control (ICICIC'06). [Online] Tersedia : doLieeecomputers ociety.org/I 0.I I 09/I CICIC.2 006.40p Juni20101 Kusumadewi, S dan Purnomo, H. 2005. Penyelesaian Masalah Optimasi dengan Teknik-telcnikHeuristik. Yogyakarta : Graha Ilmu Leksono, Agus. 2009. Algoritma Ant Colony Optimization (ACO) Untuk Menyelesaikan Traveling SalesmanProblem (TSP). Fakultas F-54
ISSN:1907-5022
Maternatika dan Ilmu Pengetahuan Alam. Universitas Diponegoro. [Online] Tersedia : eprints.undip.ac.id/7314/ I /Tugas_Akhir_(full). pdff2Jr:llriz0nl Liu, C.L. 1985. Elements Of The Discrete Mathematics{SecondEdition). Departmentof Computer Science. University of Illionis af Urbana-Champaign. Pradhana, Bayu. 2006. Studi Dan Implementasi Persoalan Lintasan Terpendek Suatu Graf Dengan Algoritma Dijksha Dan Algoritrna Bellman-Ford. [Online] Tersedia : www.informat ika.org/-r inaldi/Matdis/ 2\Juntsa -26.pdfpl F ebrvri 20t0l n 06.../Makalah0607 Rachmah" N. 200. Aplikasi Algoritma Dijkstra dalam Pencarian Lintasan Terpendek Graf Tersedia : IOnline] www. info tm at iko. or g/-r i nal d i/... / Maka Iohl F 2 I
53-0708-II3.pdf [2r Maret2010] Refianti R, dan Mutiara A. 2005. Solusi Optimal Travelling Salesman Problem Dengan Ant Colony System (ACS). Jurusan Teknik Informatika. Universitas Gunadarma.[Online] Tersedia : p aper.abmutiara.info/Ant%o2 0CoIony%o2 0 Syste m/paper_J_GND_2005 _3doc.pdf [22 Maret 20101 Saleh,Chairul. 2000. Zlgoritma Genetik unt* Pernecahan Traveling Sqlesman ProbleilJurnalTEKNOIN. Yogyakarta Maria A, dkk. 2008. PenyelesaianMasalah Travelling Salesman Problem Menggunak*n Ant Colony Optimization (ACO). tonlinel Tersedia : www.informatika.org/- r inaldi/ StmiHMakalahl Mqlwlahstmik29.pdf[22 Maret 2010] Mario, T. 2006. Implementasi Perbondingn Algoritma Ant Colony System Dengn Algoritma SubsetDynamicProgrammingP& Kasus Travelling SalesmanProblem. Semim Nasional Aplikasi Teknologi Informasi 2(ff (sNATr 2006). Munir, Rinaldi.2006.Diktat Kuliah IF2l53 MatematikaDiskrit Edisi Keempat. DepartemenTeknik Informatika,Institut TeknologiBandung. Muttakhiroh, I'ing. 2007. Menentukan Jalu Terpendek Menggunakan Algoritma SemAFakultasTeknologi Industri. flniys6ifts ldn Indonesia. Tersedia : [Online] ienx.wordpres s.com/ 2008/0I /03/pencarianj aIurl erpendek-menggunakan-aIgor i tmasemut/129November20I 0l Vitra, I. 2004. Perbandinganmetode-metode &algoritma genetika untuk Travelling Salm Problem. Proceedings Seminar Nasfod Aplikasi TeknologiInformasi2004
