IMPLEMENTASI DAN SIMULASI ALGORITMA KUMPULAN SEMUT (ANT COLONY) UNTUK MENCARI JALUR TERPENDEK Nur Ani1, Haryanto2 Program Studi Sistem Informasi1,2 Fakultas Ilmu Komputer Universitas Mercu Buana e-mail: 1
[email protected], 2
[email protected]
ABSTRAK Dalam kehidupan sehari-hari seorang pengendara sering melakukan perjalanan dari satu tempat ke tempat lain dengan mempertimbangkan efisiensi, waktu, dan biaya. Hal tersebut menyebabkan diperlukannya ketepatan dalam penentuan jalur terpendek antar tempat. Hasil penentuan jalur terpendek akan menjadi pertimbangan dalam pengambilan putusan untuk menunjukkan jalur yang akan ditempuh. Masalah tersebut telah mengundang banyak solusi, sedangkan solusi yang diharapkan adalah solusi dengan kompleksitas algoritma. Perancangan ini bertujuan untuk membangun sebuah program aplikasi untuk menentukan jalur terpendek antar kota dengan menggunakan algoritma ant colony (kumpulan semut). Ant Colony yang digunakan dalam perancangan ini adalah suatu metode pemecahan masalah dengan menggunakan sifat koloni hewan. Dalam perancangan digunakan model waterfall. Hasil perancangan ini adalah sebuah program pencarian solusi rute terpendek bagi pengendara. Kata kunci :
Ant Colony, Metode rekayasa perangkat lunak ,waterfal modell.
1. PENDAHULUAN Seiring dengan perkembangan zaman, peran komputer semakin mendominasi kehidupan. Lebih daripada itu, komputer diharapkan dapat mengerjakan segala sesuatu yang biasanya dikerjakan oleh manusia baik dalam bidang pendidikan, kesehatan, industri, maupun kehidupan sehari-hari, sehingga peran komputer dan manusia akan saling melengkapi. Beberapa hal yang menjadi kekurangan manusia diharapkan dapat digantikan oleh komputer, begitu juga dengan komputer yang tidak akan berguna tanpa sentuhan manusia. Dalam kehidupan, sering dilakukan perjalanan dari satu tempat atau kota ke tempat lain dengan mempertimbangkan efisiensi, waktu, dan biaya sehingga diperlukan ketepatan dalam penentuan jalur terpendek antar kota. Hasil penentuan jalur terpendek akan menjadi pertimbangan dalam pengambilan putusan untuk menunjukkan jalur-jalur yang akan ditempuh oleh seorang pengendara. Hasil yang didapatkan juga membutuhkan kecepatan dan ketepatan dengan bantuan komputer. Secara umum, pencarian jalur terpendek dapat dibagi menjadi dua metode, yaitu metode konvensional dan metode heuristik. Metode konvensional adalah metode yang menggunakan penghitungan matematis biasa. Ada beberapa metode konvensional yang biasa digunakan untuk melakukan pencarian jalur terpendek, antara lain: algoritma Djikstra, algoritma FloydWarshall, dan algoritma Bellman- Ford. Sedangkan Volume II/No.2/November/2010
Metode Heuristik adalah subbidang dari kecerdasan buatan yang digunakan untuk melakukan pencarian dan optimasi. Ada beberapa algoritma pada metode heuristik yang biasa digunakan dalam permasalahan optimasi, antara lain algoritma genetika, algoritma semut, logika fuzzy, jaringan syaraf tiruan, simulated annealing, dan lain-lain. Pemanfaatan teknologi informasi pada pencarian jalur terpendek menghasilkan suatu hasil atau keluaran yang tepat untuk membantu perjalanan seseorang pengendara. Untuk kasus yang berbeda, tiap algoritma akan memberikan hasil yang berbeda, tidak dapat dipastikan bahwa algoritma semut atau genetik yang terbaik. Metode konvensional cenderung lebih mudah dipahami daripada metode heuristik, tetapi jika dibandingkan, hasil yang diperoleh dari metode heuristik lebih variatif dan waktu penghitungan yang diperlukan lebih singkat (http:// id.wikipedia.org/ wiki/Algoritma _semut).
Kelemahan metode konvesional pada keakuratan hasil yang didapatkan serta tingkat kesalahan yang dihasilkan dalam penghitungan. Hal tersebut tidak akan menjadi masalah jika data yang dibutuhkan hanya sedikit, jika sebaliknya maka akan menyebabkan peningkatan tingkat kesalahan penghitungan dan penurunan keakuratan. Implementasi penyusunan penelitian ini mempunyai batasan masalah sebagai berikut: 19
Bobot antara titik yang ditentukan hanyalah bobot jarak (m). Dengan pengabaian bobot-bobot lainnya, jalur terpendek ditentukan berdasarkan jarak terpendek antara titik. b) Pencarian titik selanjutnya dihitung berdasarkan probabilitas (kebolehjadian) antar kota. c) Dalam penghitungan jumlah semut, nilai α dan β telah ditentukan nilainya. d) Keluaran yang dihasilkan adalah pelaporan proses Ant colony. e) Perangkat lunak dibangun dengan menggunakan bahasa pemprograman Java.
= {e1 , e2 , ... , en }
a)
atau dapat ditulis : G = (V, E) artinya graf G memiliki V simpul dan E busur. Simpul-simpul pada graf dapat merupakan obyek sembarang seperti kota, nama anak, dan sebagainya. Busur dapat menunjukkan hubungan (relasi) sembarang seperti rute penerbangan, jalan raya, sambungan telepon, dan lain-lain. 1
1 e1
2
Penelitian ini bertujuan: a) membuat suatu perangkat lunak yang dapat mensimulasikan Ant colony dalam kasus pencarian jalur terpendek antara kota yang telah diketahui koordinatnya; b) memberikan alternatif pada pengendara untuk menetukan jalur atau rute mana saja yang akan dilalui untuk menuju suatu tempat (kota). 2. LANDASAN TEORI Definisi Graf Graf adalah suatu pasangan himpunan yang terdiri atas simpul-simpul (verteces atau node) dan sisisisi (edges atau ares). Graf G didefinisikan sebagai pasangan himpunan (V , E), dalam hal ini: Graf G = (V, E), yang dalam hal ini: V = himpunan yang terbatas dan tidak kosong dari simpul-simpul. = { v1 , v2 , ... , vn } E = himpunan sisi sepasang simpul
(edges) yang menghubungkan
•
Pada G2, sisi e3 = (1, 3) dan sisi e4 = (1, 3) dinamakan sisi-ganda (multiple edges atau paralel edges) karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3. • Pada G3, sisi e8 = (3, 3) dinamakan gelang atau kalang (loop) karena ia berawal dan berakhir pada simpul yang sama. Jenis-Jenis Graf • Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis: 1. Graf sederhana (simple graph). Graf yang tidak mengandung gelang maupun sisiganda dinamakan graf sederhana. G1 pada Gambar 1 adalah contoh graf sederhana Volume II/No.2/November/2010
3
e2
2 e5
4
G1
e3
1 e4
e1 3
e6 e7
e3
e2
2
e4
3
e6
e5
e8
e7
4
4
G2
G3
Gambar 1 (a) graf sederhana, (b) graf ganda, dan (c) graf semu Pada Gambar 2.1 G1 adalah graf dengan V = { 1, 2, 3, 4 } E = { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) } G2 adalah graf dengan V = { 1, 2, 3, 4 } E = { (1, 2), (2, 3), (1, 3), (2, 4), (3, 4), (3, 4) } = { e1, e2, e3, e4, e5, e6, e7} G3 adalah graf dengan V = { 1, 2, 3, 4 } E = { (1, 2), (2, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) } = { e1, e2, e3, e4, e5, e6, e7, e8}
2. Graf tak-sederhana (unsimple-graph). Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph). G2 dan G3 pada Gambar 1 adalah contoh graf taksederhana. • Berdasarkan jumlah simpul pada suatu graf, secara umum graf dapat digolongkan menjadi dua jenis, yaitu: 1. Graf berhingga (limited graph) Graf berhingga adalah graf yang jumlah simpulnya n berhingga. 2. Graf tak-berhingga (unlimited graph) Graf yang jumlah simpulnya n tidak berhingga banyaknya disebut graf tak-berhingga. 20
Secara umum langkah-langkah dalam Ant Colony adalah [3][8]: - Langkah 1: Inisialisasi harga parameter-parameter algoritma. - Langkah 2: Pengisian kota pertama ke dalam tabu list. Hasil inisialisasi kota pertama setiap semut dalam langkah 1 harus diisikan sebagai elemen pertama tabu list. Hasil dari langkah ini adalah terisinya elemen pertama tabu list setiap semut dengan indeks kota tertentu, yang berarti bahwa setiap tabuk (1) bisa berisi indeks kota antara 1 sampai n sebagaimana hasil inisialisasi pada langkah 1. - Langkah 3: Penyusunan rute kunjungan setiap semut ke setiap kota. Koloni semut yang sudah terdistribusi ke sejumlah atau setiap kota, akan mulai melakukan perjalanan dari kota pertama masing-masing sebagai kota asal dan salah satu kota kota lainnya sebagai kota tujuan. Kemudian dari kota kedua tiap koloni semut akan melanjutkan perjalanan dengan memilih salah satu dari kota yang tidak terdapat pada tabuk sebagai kota tujuan selanjutnya. Perjalanan koloni semut berlangsung terus menerus sampai semua kota satu persatu dikunjungi atau telah menempati tabuk. Lambang huruf s menyatakan indeks urutan kunjungan, kota asal dinyatakan sebagai tabuk (s) dan kota lainnya dinyatakan sebagai {N-tabuk}.
- Langkah 4: Perhitungan panjang rute setiap semut. Perhitungan panjang rute tertutup (length closed tour) atau Lk setiap semut dilakukan setelah satu siklus diselesaikan oleh semua semut. Perhitungan ini dilakukan berdasarkan tabuk
masing-masing. Lk = dtabuk(n),tabuk(1) + tabuk(s),tabuk(s+1).........(3) dengan dij adalah jarak antara kota i ke kota j yang dihitung berdasarkan persamaan: dij =
Pencarian rute terpendek. Setelah Lk setiap semut dihitung, akan didapat harga minimal panjang rute tertutup setiap siklus atau LminNC dan harga minimal panjang rute tertutup secara keseluruhan adalah atau Lmin. Perhitungan perubahan harga intensitas jejak kaki semut antar kota. Koloni semut akan meninggalkan jejak-jejak kaki pada lintasan antar kota yang dilaluinya. Adanya penguapan dan perbedaan jumlah semut yang lewat, menyebabkan kemungkinan terjadinya perubahan harga intensitas jejak kaki semut antar kota. Persamaan perubahan ini adalah : Δτij =
……………………........…........…….(5) adalah perubahan harga intensitas dengan jejak kaki semut antar kota setiap semut yang dihitung berdasarkan persamaan: = , untuk (i,j) kota asal dan kota tujuan dalam tabuk ….................................……(6) =0, untuk i,j lainnya.................................(7) - Langkah 5: Penghitungan harga intensitas jejak kaki semut antar kota untuk siklus berikutnya. Harga intensitas jejak kaki semut antar kota pada semua lintasan antar kota ada kemungkinan berubah karena adanya penguapan dan perbedaan jumlah semut yang melewati. Untuk siklus selanjutnya, semut yang akan melewati lintasan tersebut harga intensitasnya telah berubah. Harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya dihitung dengan persamaan: τij = ρ.τij + Δτij ……………....................……..(8) Reset harga perubahan intensitas jejak kaki semut antar kota. Untuk siklus selanjutnya perubahan harga intensitas jejak semut antar kota perlu diatur kembali agar memiliki nilai sama dengan nol. - Langkah 6: Pengosongan tabu list. Ulangi langkah 2 jika diperlukan. Tabu list perlu dikosongkan untuk diisi lagi dengan urutan kota yang baru pada siklus selanjutnya, jika jumlah siklus maksimum belum tercapai
................................(4)
Volume II/No.2/November/2010
21
3. HASIL DAN PEMBAHASAN 1. Metode Perancangan Metode perancangan yang dikembangkan untuk membangun pencarian jalur terpendek adalah UML (Unified Modelling Language) yang kemudian diperjelas perancangan terstruktur (structure design method) atau diagram alir (flow chart). Diagram alir pada dasarnya merupakan konsep perancangan yang mudah dengan penekanan pada sistem modular (Top Down Design) dan pemrograman terstruktur(structure programming). Perancangan sistem ini akan dibagi menjadi beberapa subsistem yaitu: Perancangan UML Perancangan aplikasi yang dibangun menggunakan 4 (tiga) model diagram UML (Unified Modelling Language) yaitu: use case diagram, class diagram, activity diagram dan sequence diagram.
dalam menangkap struktur dari semua kelas yang membentuk arsitektur sistem yang dibuat.
Gambar 2 Diagram use case aplikasi implementasi dan simulasi algoritma Kumpulan Semut (AntColony) untuk pengendara.
•
Diagram Use Case Diagram use Case yang bekerja dengan cara mendeskripsikan tipikal interaksi antara user (pengguna) sebuah sistem dan suatu sistem tersendiri melalui sebuah cerita bagaimana sebuah sistem dipakai. Diagram use case menggambarkan fungsionalitas yang diharapkan dari sebuah sistem. Diagram use case terdiri atas sebuah aktor dan interaksi yang dilakukannya, aktor tersebut dapat berupa manusia, perangkat keras, sistem lain, ataupun yang berinteraksi dengan sistem. Aktor pada program aplikasi ini adalah pengendara. Pada aplikasi pencarian jalur terpendek antar kota digunakan algoritma semut (ant colony), use case menjelaskan hubungan antara sistem dengan aktor (pengendara). Hubungan ini dapat berupa masukan (input) aktor (pengendara) ke sistem ataupun keluaran (output) ke aktor (pengendara). Use-case merupakan dokumen naratif yang mendeskripsikan kasus-kasus atau kejadian-kejadian dari aktor dalam penggunaan system untuk menyelesaikan sebuah proses. Berikut ini adalah gambar yang menjelaskan aplikasi pencarian jalur terpendek antara kota menggunakan algoritma semut (ant colony) dalam model diagram use-case. •
Diagram Class Class adalah sebuah spesifikasi yang jika diinstansiasi akan menghasilkan sebuah objek dan merupakan inti dari pengembangan dan perancangan berorientasi objek. Class menggambarkan keadaan (atribut/properti) suatu sistem dan menawarkan layanan untuk memanipulasi keadaan tersebut (metoda/fungsi). Diagram Class menggambarkan struktur dan deskripsi class, package, dan objek beserta hubungan satu sama lain. Selam proses perancangan, diagram class berperan Volume II/No.2/November/2010
Gambar 3 Diagram Class aplikasi implementasi dan simulasi algoritma Kumpulan Semut (ant colony) untuk Pengendara. •
Diagram Aktivitas Diagram altivitas menggambarkan berbagai aliran aktivitas dalalm system yang sedang dirancang, bagaimana tiap aliran berawal, putusan yang mungkin terjadi dan bagaimana mereka berakhir. Diagram aktivitas juga dapat menggambarkan proses pararel yang mungkin terjadi pada beberapa eksekusi. Berikut ini adalah diagram aktivitas dari aplikasi pencarian jalur terpendek menggunakan algoritma semut.
22
b. c.
Private string asal digunakan untuk pendeklarasian kota-kota asal yang bertipe string. Private string tujuan digunakan untuk pendeklarasian kota-kota tujuan yang bertipe string.
Kode program1. Program HaryAnt.java:
Gambar 4. Diagram aktivitas aplikasi implementasi dan simulasi algoritma kumpulan semut (Ant Colony) untuk pengendara. 2.
public class HaryAnt extends Jframe { private String Asal[] = {"","Cengkareng","Duri Kosambi","Green Garden","Kedoya","Jalan Panjang","Keb.Jeruk","Puri Indah","Kembangan","Mercu Buana","Joglo"}; private String Tujuan[] = {"","Cengkareng","Duri Kosambi","Green Garden","Kedoya","Jalan Panjang","Keb.Jeruk","Puri Indah","Kembangan","Mercu Buana","Joglo"}; public HaryAnt() { super("Implementasi dan Simulasi Pencarian Jalur Terpendek dengan Algoritma Semut ( Ant Colony )"); JMenuBar menubar = new JMenuBar();
Algoritma Ant Colony Begin Initialize Pheromone matrix Read and initialize distance matrix i := 1 (number of ants completed their tours) Do while I < MaxIteration If current node is node last node, choose next feasible node on the basis of pheromone density, at equal situation, choose it randomly. Increase the amount of pheromone on chosen arc by α. If current node is the last node, the ant’s tour is finished, evaporate pheromone on every arc by β percent. i := I + 1 Analyze the pheromone matrix to identifity the shortes path End
3.
Pengkodean dan Antarmuka Pada subbab ini penulis akan menjelaskan potongan-potongan dari kode sumber aplikasi untuk implementasi dan simulasi pencarian jalur terpendek. Kode sumber untuk aplikasi implementasi dan simulasi pencarian jalur terpendek tersebut dikembangkan dengan menggunakan bahasa pemrograman Java versi Java 2 Standard Edition (J2SE). Keterangan kode program.1 : a. Class HaryAnt menggunakan klausa extend yang mengidentifikasi bahwa class tersebut merupakan super kelas dari kelas itu sendiri. Volume II/No.2/November/2010
Kode program 2 HaryAntTest.java public class Hary extends Jpanel { protected Point2D[] mPoints; protected Point2D mSelectedPoint; public Hary() { protected Point2D mSelectedPoint; public Hary() { mPoints = new Point2D[13]; // Cubic curve. mPoints[0] = new Point2D.Double(20, 150);//Cengkareng mPoints[1] = new Point2D.Double(200, 50);//Green Garden mPoints[2] = new Point2D.Double(400, 30);//Jalan panjang mPoints[3] = new Point2D.Double(600, 40);//pos Pengumben mPoints[4] = new Point2D.Double(700, 90);//Joglo mPoints[5] = new Point2D.Double(500, 120);//Keb.Jeruk mPoints[6] = new Point2D.Double(80, 250);//Duri Kosambi mPoints[7] = new Point2D.Double(400, 200);//Puri Indah mPoints[8] = new Point2D.Double(600, 150);//kembangan mPoints[9] = new Point2D.Double(650, 125);//Mercu Buana mPoints[10] = new Point2D.Double(850, 140);//Ciledug mPoints[11] = new Point2D.Double(350, 150);//Pasar Puri mPoints[12] = new Point2D.Double(300, 50);//kedoya } public void paintComponent(Graphics g) { Graphics2D g2 = (Graphics2D) g.create(); g2.setColor(Color.GREEN);
Keterangan kode program 2 : a. Program di atas digunakan untuk membuat titiktitik/ node-node pada tampilan program untuk pendefinisian tata letak kota. b. Public void paint Component (Graphics g) digunakan untuk menset warna titik/ node. 23
c)
Kode program 3. Panel.java public class Panel extends JPanel { protected void paintComponent(Graphics g) { Graphics2D g2 = (Graphics2D) g.create(); GradientPaint paint = new GradientPaint(0, Color.BLACK, 0, getHeight(), Color.GREEN.brighter());
0,
g2.setPaint(paint); g2.fillRect(0, 0, getWidth(), getHeight()); }}
Keterangan program 3 : Potongan kode di atas digunakan untuk menge-set tampilan warna program aplikasi. 4. KESIMPULAN DAN SARAN A. Kesimpulan Dari hasil pembahasan dan pembuatan program Aplikasi Implementasi dan Simulasi Penentuan Jalur Terpendek menggunakan Algoritma semut (Ant Colony) dapat disimpulkan sebagai berikut: a) Dalam tahap pengujian, Aplikasi Implementasi dan Simulasi simulasi pencarian jalur terpendek menggunakan algoritma semut (Ant Colony) ini dapat digunakan seperti yang diharapkan, sehingga aplikasi ini dapat membantu pengendara, khususnya bagi pengguna jalan sekitar jakarta barat untuk mempercepat dalam memilih jalur mana saja untuk menuju suatu tempat dengan harapan efisiensi waktu dan biaya. b) Dengan menggunakan metode rekayasa perangkat lunak waterfall pada tahap analisis masalah, diperoleh permasalahan pada Aplikasi ini, yaitu bagaimana membangun suatu program aplikasi yang dapat membantu seseorang pengendara untuk memperoleh jalur terpendek menuju alamat tujuan menggunakan program java menjadi program yang utuh dan siap digunakan.
Volume II/No.2/November/2010
Dalam tahap pengujian, Aplikasi menunjukan bahwa Aplikasi ini secara fungsional bekerja dengan baik sesuai kebutuhan yang telah didefinisikan pada tahap analisis sampai perancangan. Metode pengujian yang digunakan oleh penulis adalah metode black box dan White Box.
B. Saran Ada beberapa masukan untuk pengembangan aplikasi ini, dengan harapan semakin meningkatnya fungsi-fungsi dari aplikasi dan semakin tepatnya antara kebutuhan sistem dengan fungsional aplikasi, yaitu: 1. Pengembangan aplikasi implementasi dan simulasi pencarian jalur terpendek menggunakan algoritma semut tidak hanya berdasarkan jarak terpendeknya saja tetapi juga berdasarkan lama perjalanan dan waktu perjalanan yang paling efisien. 2. Pengembangan aplikasi dilakukan dengan penggunaan teknologi yang mampu mengidentifikasi titik kemacetan serta titik yang tidak mengalami kemacetan.
DAFTAR PUSTAKA Dharwiyanti, Sri dan Wahono, Romi Satria. Pengantar Unified Modeling Language(UML). Http://www.ilmukomputer.com, 2003. Juwaeni, Ahmad. Unified Modeling Language (UML). Http://www.enciety.com , 2009. Darigo M.,Gi. Dcaro. “The ant colony optimization meta-heuristic”. New York : McGraw-Hill,1999. Wikipedia Indonesia. (2006). “Algoritma semut”.http://id.wikipedia.org/wiki/Algoritma _semut/. Waktu akses : 30 Desember 2009 pukul 23.00
24
