SISTEM PENATAAN TEMPAT DUDUK PESERTA UJIAN SECARA RANDOM DENGAN MENGGUNAKAN ALGORITMA SEMUT (STUDI KASUS : SMP MAITREYAWIRA TANJUNGPINANG) Fendy Mahasiswa Informatika, FT UMRAH,
[email protected] ABSTRAK Ujian yang dilakukan pada sekolah biasa nya untuk mengukur kemampuan peserta didik dalam proses belajar. Tetapi dalam proses pembelajaran dalam kelas bagaimana siswa dapat menguasai dan memahami bahan ajar secara tuntas masih merupakan masalah yang sulit. Hal tersebut dikarenakan bahwa masih belum bisa terukur secara pasti bahwa ujian yang dikerjakan siswa tersebut secara jujur atau tidak, di karenakan banyak beragaman jenis siswa yang berbeda. Oleh karena itu seperti studi kasus di SMP Maitreyawira Tanjungpinang di lakukan pengacakan seluruh kelas agar tidak saling kenal dalam ruangan ujian tersebut. Akan tetapi proses pengacakan di SMP Maitreyawira Tanjungpinang masih dilakukan secara manual sehingga proses pengacakan tersebut membutuhkan proses yang lama. Skripsi ini akan membicarakan bagaimana membangun sebuah aplikasi pengacakan tempat duduk peserta ujian dengan menggunakan algoritma semut. Sistem yang ingin di bangun adalah sebuah aplikasi desktop dengan hasil akhir sebauh denah pengacakan tempat duduk ujian tanpa ada peserta ujian yang duduk bersebelahan dengan teman sekelas. Dari hasil penelitian dengan penerapan Algoritma Semut, dapat menghasilkan error terbaik 0,0% dengan rata – rata siklus terbaik 4,687 % sedangkan pengacakan biasa menghasilkan error terbaik 6.25% dengan rata – rata siklus terbaik 22.5%. akan tetapi, waktu proses pada pengacakan fisher-yates suffle lebih cepat dibandingkan dengan pengacakan algoritma semut. Semakin banyak siklus yang diproses semakin lama waktu prosesnya. Kata Kunci : Pengacakan tempat duduk, meta-heuristic, algoritma semut ABSTRACT The general purpose of conducting an examination at school is to measure the ability of the students in learning process. But how the students can understand and master the lesson completely is still hard to achieve. The main reason is because the students still haven’t done the examination honestly and the students themselves are various in honesty. Therefore,as a case study in Maitereyawira Secondary school, the school randomize the students by their classrooms, so that they will not meet with theirclassmates surround their seats. But the randomization process is still done manually so that it takes a long process and time to do. This final task will discuss how to build an application to randomize the seats of examinees using Ant Colony Optimizer (ACO) algorithm. The system that will be built is a desktop application with a final result of randomization sketch of student seat without examinees sitting around their classmates. At the research result with Ant Colony Optimizer, cam make a best error 0,0% with average 4.687% and with fisher-yates suffle can make a best error 6.25% with average 22.5%. but at fisher-yates suffle the prosses time is more faster than ant colony optimizer. The more iteration are prosessed, the application prosessed are more longer. Key Word: Randomization exam seat, meta-heuristic, ant colony optimizer 1
penelitiannya aplikasi penjadwalan mata kuliah ini bertujuan untuk membangkitkan sebuah jadwal perkuliahan yang sudah terbebas dari masalah bentrok Berdasarkan latar belakang masalah tersebut, penulis memandang penting mengangkat kasus di atas ke dalam Skripsi ini dengan mengambil judul “Sistem Penataan Tempat Duduk Peserta Ujian Secara Random Dengan Menggunakan Algoritma Semut (Studi Kasus: SMP Maitreyawira Tanjungpinang)”. Sistem yang ingin dibangun adalah sebuah aplikasi desktop dengan hasil akhir sebuah denah pengacakan tempat duduk ujian tanpa ada peserta ujian yang duduk bersebelahan dengan teman sekelas.
I. PENDAHULUAN 1.1. Latar Belakang Dalam proses pembelajaran bahwa penguasaan pengetahuan dan keterampilan hidup yang dibutuhkan siswa dalam menghadapi kehidupan ril adalah merupakan tujuan pendidikan. Tetapi dalam proses pembelajaran dalam kelas bagaimana siswa dapat menguasai dan memahami bahan ajar secara tuntas masih merupakan masalah yang sulit. Hal tersebut dikarenakan bahwa masih belum bisa terukur secara pasti bahwa ujian yang dikerjakan siswa tersebut secara jujur atau tidak, di karenakan banyak beragaman jenis siswa yang berbeda. Dari perbedaan tersebut maka dapat menimbulkan beragamnya sikap dan anak didik di dalam ruang ujian. Menjadi tugas guru bagaimana menjadikan ruang ujian yang baik agar terhindari dari menyontek pada jawaban ujian. Seperti contohnya pada SMP Maitreyawira Tanjungpinang saat ujian semester semua kelas mulai dari kelas 7 sampai dengan kelas 9 di acak sehingga dalam satu ruang agar tidak terjadi menyontek pada jawaban ujian yang di lakukan oleh siswa, akan tetapi di karenakan pemetaan siswa yang dilakukan dengan menggunakan manual sehingga membutuhkan waktu yang lama dalam penyusunan tempat duduk ujian. Sehingga agar pemetaan tempat duduk ujian di susun dengan cepat di perlu kan suatu sistem agar susunan tempat duduk ujian yang dilakukan dapat meminimalisir terjadinya menyontek Algoritma semut adalah salah satu jenis meta-heuristic yang sudah terbukti dapat menyelesaikan banyak sekali permasalahan kombinatorial yang sulit (Fernandes, 2012). Seperti menyelesaikan masalah Traveling Salesman Problem (TSP), masalah penyusunan jadwal mata pelajaran, dan masalah penjadwalan serta rute kereta api. Pada penelitian yang dilakukan Fernandes (2012) dalam penyelesaian permasalahan penjadwalan kuliah dengan menggunakan algoritma semut. Dalam
II. TINJAUAN PUSTAKA 2.1. Penelitian Terdahulu Penelitian yang dilakukan oleh Socha dkk. (2003) dalam penyelesaian penjadwalan (timetable) di universitas menggunakan algoritma Ant. Dalam penelitiannya mereka menggunakan algoritma Ant dasar dan variasinya (Max Min Ant System / MMAS). Kedua algoritma tersebut diuji untuk tiga kasus penjadwalan dan menyimpulkan bahwa variasi MMAS lebih baik kinerjanya dibandingkan dengan algoritma Ant dasar. Penelitian yang dilakukan oleh Mutakhiroh dkk. (2007) dalam penyelesaian pencarian jalur terpendek dengan menggunakan algortima semut. Dalam penelitiannya mereka menggunakan model matematis dalam penyelesaian pencarian jalur terpendek. Dengan menggunakan graf dan menentukan jarak antar kota dalam pencarian jarak terpendek yang akan dilalui. Penelitian yang dilakukan oleh Fernandez (2012) dalam penyelesaian permasalahan penjadwalan kuliah dengan menggunakan algoritma semut. Dalam penelitiannya aplikasi penjadwalan mata kuliah ini bertujuan untuk membangkitkan sebuah jadwal perkuliahan yang sudah terbebas dari masalah bentrok dengan proses
2
acak local search dan dipercepat oleh algoritma semut. Penelitian yang dilakukan Fitriyani (2015) dalam analisa pencarian jalur terpendek ke penginapan di kota Batam dengan menggunakan algoritma Ant Colony, dalam penelitiannya pencarian jalur terpendek dengan menentukan jarak yang di berikan kordinat x dan y dan di susun rute dengan menggunakan algoritma semut untuk mencari jalur alternatif untuk mencapai penginapan dalam jalur pariwisata kota Batam.
6. Feromon yang ditinggalkan oleh semut di jalur yang lebih pendek aromanya akan lebih kuat dibandingkan feromon di jalur yang lebih panjang seperti Gambar 2.1.d 7. Semut – semut lain akan lebih tertarik menyikuti jalur bawah karena aroma feromon lebih kuat.
2.2. Algoritma Semut Algoritma Semut (Ant Algorithm) merupakan algoritma yang dimunculkan sebagai suatu pendekatan multi-agen terhadap optimasi berbagai permasalahan yang berkaitan dengan graf (Paninalone, 2011). Sampai saat ini, berbagai upaya pengembangan dilakukan untuk memperluas pemanfaatan dari algoritma semut. Berbagai pemanfaatan yang sudah umum digunakan antara lain untuk menyelesaikan permasalahan rute kendaraan, penyurutan sekuensial, pewarnaan graf, permasalahan routing pada jaringan dan berbagai permanfaatan lainnya. Munurut Fernandez (2012) cara kerja algoritma semut sebagai berikut : 1. Pada Awalnya, semut keliling dengan acak. 2. Ketika semut – semut menemukan jalur yang berbeda misalnya sapai pada persimpangan, mereka akan mulai menentukan arah jalan secara acak seperti Gambar 2.1.a 3. Sebagian semut memilih berjalan ke atas dan sebagian lagi akan memilih berjalan ke bawah seperti Gambar 2.1.b 4. Ketika menemukan makanan mereka kembali ke koloninya sambil memberikan tanda dengan jejak feromon. 5. Karena jalur yang ditempuh lewat jalur bawah lebih pendek, maka semut yang bawah akan tiba lebih dulu dengan asumsi kecepatan semua semut adalah sama seperti Gambar 2.1.c
Gambar 2.1. Tingkah laku semut (Sumber : Fernandez, 2012)
Menurut Muttakhiroh dkk. (2007) dalam algoritma semut diperlukan variable dan langkah –langkah untuk menentukan jarak terpendek, yaitu : Langkah 1 : a) Inisialisasi harga parameter – parameter algoritma. Parameter – parameter yang di inisialisasikan adalah : 1) Intensitas jejak semut antar kota dan perubahannya (𝜏𝑖𝑗 ) 2) Banyak kota (n) termasuk kordinat (x,y) atau jarak antar kota (𝑑𝑖𝑗 ) 3) Kota berangkat dan kota tujuan 4) Tetapan siklus – semut (Q) 5) Tetapan pengendali intensitas jejak semut (𝛼), nilai 𝛼 ≥ 0 6) Tetapan pengendali visibilitas ( 𝛽 ), nilai 𝛽 ≥ 0 1 7) Visibilitas antar kota = 𝑑 (𝜂𝑖𝑗 ) 𝑖𝑗
8) Banyak Semut (m) 9) Tetapan penguapan jejak semut (𝜌), nilai 𝜌 harus > 0 dan < 1 untuk mencegah jejak pheromone tak terhingga. 3
10) Jumlah siklus maksimum ( 𝑁𝐶𝑚𝑎𝑥 ) bersifat tetap selama algoritma dijalankan, sedangkan 𝜏𝑖𝑗 akan selalu diperbahrui harganya pada setiap siklus algoritma mulai dari sklus pertama ( 𝑁𝐶 = 1 ) sampai tercapai jumlah siklus maksimum (𝑁𝐶 = 𝑁𝐶𝑚𝑎𝑥 ) atau sampai terjadi konvergensi. b) Inisialisasi kota pertama setiap semut. Setelah inisialisasi 𝜏𝑖𝑗 dilakukan, kemudian m semut ditempatkan pada kota pertama tertentu secara acak.
Dengan i sebagai indeks kota asal dan j sebagai indeks kota tujuan. Stelah mendapatkan nilai probalitas yang ingin dikunjungi maka langkah selanjut nya adalah mencari nilai kumulatid dengan persamaan 𝑘 𝑘𝑢𝑚𝑢𝑙𝑎𝑡𝑖𝑓𝑘 = 𝑝𝑖𝑗 + 𝑘𝑢𝑚𝑢𝑙𝑎𝑡𝑖𝑓𝑘−1 ........................................................... (2.3) Setalah mendapatkan nilai kumulatif langkah selanjut nya adalah mengambil nilai random dari kumulatif1 sampai dengan kumulatifn untuk mencari kota tujuan yang akan dikunjungi selanjutnya oleh semut.
Langkah 2 : Pengisian kota pertama ke dalam tabu list. Hasil inisialisasi kota pertama setiap semut dalam langkah 2 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 tabuk(1) bisa berisi indeks kota antara 1 sampai n sebagaimana hasil inisialisasi pada langkah 2.
Langkah 4 : a) 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 masung – masing dengan persamaan berikut : 𝐿𝑘 = 𝑑𝑡𝑎𝑏𝑢𝑘 (𝑛),𝑡𝑎𝑏𝑢𝑘(𝑖)
Langkah 3 : Penyusunan rute kunjungan setiap semut ke setiap kota. Koloni semut 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 masing – masing, koloni semut akan melanjutkan perjalanan dengan memilih salah satu dari kota – kota yang tidak terdapat pada tabuk Jika s menyataka indeks urutan kunjungan, kota asal dinyatakan sebagai tabuk(s) dan kota – kota lainnya dinyatakan sebagai { N-tabuk }, maka untuk menentukan kota tujuan digunakan persamaan probabilitas kota untuk dikunjungi sebagai berikut : 𝛼
𝑘 𝑝𝑖𝑗
=
𝑛−1
+ ∑ 𝑑𝑡𝑎𝑏𝑢𝑘 (𝑠),𝑡𝑎𝑏𝑢𝑘(𝑠+1) … … … … . (2.4) 𝑠=1
Dengan 𝑑𝑖𝑗 adalah jarak antara kota I ke kota j yang dihitung berdasarkan persamaan : 𝑑𝑖𝑗 = √(𝑥𝑖 − 𝑥𝑗 )2 + (𝑦𝑖 − 𝑦𝑗 )2 ....... (2.5) b) 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 c) 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 :
𝛽
[𝑇𝑖𝑗 ] .[𝑛𝑖𝑗 ]
𝛼
𝛽
∑𝑘′ ∈[𝑁−𝑡𝑎𝑏𝑢 ][𝑇𝑖𝑘′ ] .[𝑛𝑖𝑘′ ] 𝑘
untuk
𝑗∈
{𝑁 − 𝑡𝑎𝑏𝑢𝑘 } .....................................(2.1) Dan 𝑘 𝑝𝑖𝑗 = 0 untuk j lainnya .....................(2.2)
4
𝑚
Perhitungan ini dapat digunakan untuk membandingkan model peramalan yang berbeda, mengawasi peramalan, dan memastikan peramalan berjalam dengan baik. Ukuran kesalahan yang digunakan, menurut Savira (2014) ada 3 macam perhitungan yaitu :
∆𝑇𝑖𝑗 = ∑ 𝑇𝑖𝑗𝑘 … … … … … … … … … … (2.6) 𝑘=1
𝑘 Dengan ∆𝜏𝑖𝑗 adalah perubahan harga intensitas jejak kaki semut antar kota setiap semut yang dihitung berdasarkan persamaan : 𝑄 ∆𝑇𝑖𝑗𝑘 = 𝐿 , untuk (𝑖, 𝑗) ∈ kota asal dan kota
1. MAD Ukuran pertama kesalahan peramalan keseluruhan untuk sebuah model adalah Mean Absolute Deviation (MAD). Nilai ini di hitung dengan mengambil jumlah nilai absolute dari setiap kesalahan peramalah di bagi dengan jumlah periode data (n), yaitu : ∑ 𝑎𝑘𝑡𝑢𝑎𝑙 𝑝𝑒𝑟𝑎𝑚𝑎𝑙𝑎𝑛 𝑀𝐴𝐷 = ........ (2.10) 𝑛
𝑘
tujuan dalam 𝑡𝑎𝑏𝑢𝑘 (2.7) ∆𝑇𝑖𝑗𝑘 = 0 , untuk (𝑖, 𝑗) lainnya ...........(2.8)
Langkah 5 : a) Perhitungan harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya. Harga intensitas jejak kaki semut antar kota pada semua lintasan antar kota ada kemungkinan berubah karena adanya penguapan dan perbedaan 2. MSE jumlah semut yang melewati. Untuk Merupakan cara kedua untuk mengukur siklus selanjutnya, semut yang akan kesalahan peramalan keseluruhan. Mean melewati lintasan tersebut harga Squared Error (MSE) merupakan rataan intensitasnya telah berubah. Harga selisih kuadrat antara nilai yang intensitas jejak kaki semut antar kota diramalkan dan yang diamati. Rumusnya untuk siklus selanjutnya dihitung dengan adalah : persamaan : ∑(𝐾𝑒𝑠𝑎𝑙𝑎ℎ𝑎𝑛 𝑝𝑒𝑟𝑎𝑚𝑎𝑙𝑎𝑛)2 𝑀𝑆𝐸 = . (2.11) 𝑇𝑖𝑗 = 𝜌. 𝑇𝑖𝑗 + ∆Tij ...................................................................................(2.9) 𝑛 b) Atur ulang harga perubahan intensitas jejak kaki semut antar kota. 3. MAPE Untuk siklus selanjutnya perubahan Mean Absolute Percentage Error harga intensitas jejak semut antar kota (MAPE) dihitung rataan diferensisasi perlu diatur kembali agar memiliki nilai absolute antara nilai yang diramal dan sama dengan nol actual, dinyatakan sebagai persentase nilai actual. Jika memiliki nilai yang Langkah 6 : diramal dan actual untuk n periode, Pengosongan tabu list, dan ulangi langkah 2 dihitung dengan persamaan : ∑ 𝑘𝑒𝑠𝑎𝑙𝑎ℎ𝑎𝑛 𝑎𝑏𝑠𝑜𝑙𝑢𝑡 jika diperlukan, Tabu list perlu dikosongkan 𝑀𝐴𝑃𝐸 = 𝑥 100 𝑛 untuk diisi lagi dengan urutan kota yang ..................................................... (2.12) baru pada siklus selanjutnya, jika jumlah siklus maksimum belum tercapai atau belum terjadi konvergensi, Algoritma diulang lagi dari langkah 2 dengan harga parameter intensitas jejak kaki semut antar kota yang sudah diperbaharui.
2.4. Pengacakan Fisher-Yates Suffle Diambil dari nama Ronald Fisher dan Frank Yates atau juga dikenal dengan nama Knuth shuffle (diambil dari nama Donald Knuth) merupakan sebuah algoritmauntuk menghasilkan suatu permutasi acak dari suatu himpunan yang terhingga, atau dengan kata lain untuk mengacak suatu himpunan tertentu (Nugraha,
2.3. Perhitungan Kesalahan Peramalan Menurut Savira (2014), ada beberapa perhitungan yang biasa digunakan untuk menghitung kesalahan peramalan total. 5
2015). Apabila diimplementasikan secara benar, maka akan mendapatkan hasil yang tidak akan berat sebelah, sehingga setiap permutasi akan memiliki kemungkinan yang sama Algoritma Fisher-Yates dipilih karena algoritma ini merupakan metode pangacakan yang lebih baik atau dapat dikatakan sesuai untuk pengacakan angka, dengan waktu eksekusi yang cepat serta tidak memerlukan waktu yang lama untuk melakukan suatu pengacakan. Algoritma Fisher-Yates terdiri dari dua metode yakni, metode orisinal dan metode modern. Metode modern dipilih karena metode ini memang khusus digunakan untuk pengacakan dengan sistem komputerisasi, dikarenakan hasil pengacakan bisa lebih variatif. Menurut Nugraha (2015) metode modern yang digunakan untuk menghasilkan suatu permutasi acak untuk angka 1 sampai N adalah sebagai berikut : 1. Tuliskan angka dari 1 sampai N. 2. Pilih sebuah angka acak K diantara 1 sampai dengan jumlah angka yang belum dicoret. 3. Dihitung dari bawah, coret angka K yang belum dicoret, dan tuliskan angka tersebut di lain tempat. 4. Ulangi langkah 2 dan langkah 3 sampai semua angka sudah tercoret. 5. Urutan angka yang dituliskan pada langkah 3 adalah permutasi acak dari angka awal.
Gambar 3.1. Model Waterfall (Sumber : http://agusdar.wordpress.com/, 2013) Berikut adalah penjelasan dari model waterfall di atas: 1. Analisa Kebutuhan Proses menganalisis dan pengumpulkan kebutuhan system yang sesuai studi kasus yang diperlukan. 2. Desain Sistem Dalam tahap ini penulis akan merancang desain dan model aplikasi yang dikembangkan seperti Diagram Konteks, Data Flow Diagram (DFD), Entitas Relationship Diagram (ERD), dan Perancangan Interface yang akan di kembangkan berdasarkan hasil analisa pada tahap sebelumnya. 3. Penulisan Kode Program Penulisan Kode Program merupakan proses menerjemahkan desain ke dalam bahasa yang bisa dimengerti oleh komputer. 4. Pengujian Program Proses pengujian berfokus pada logika internal software, memastikan bahwa semua pernyataan sudah diuji, dan pada eksternal fungsional, yaitu mengarah pengujian untuk menemukan kesalahan – kesalahan dan memastikan bahwa input yang dibatasi akan memberikan hasil actual yang sesuai dengan hasil yang dibutuhkan. Pada penelitian ini penulis menggunakan teknik black box untuk menguji fitur – fitur system yang telah dibangun.
III. METODE PENELITIAN Penelitian yang dilakukan ini mengggunakan model pengembangan Waterfall. Proses pengembangan dilakukan melalui beberapa tahap yaitu : Analisa kebutuhan, Design, Koding, Pengujian, dan Pemeliharaan, pada metodologi pengembangan ini hanya sampai pengujian (testing) saja.
6
IV. PEMBAHASAN
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
4.1. Perhitungan Penataan Tempat Duduk dengan Algoritma Semut Algoritma Ant Colony Optimazation atau algoritma semut pada dasarnya dapat menemukan rute terpendek antar sarang dan sumber makanan berdasarkan jejak feromon pada lintasan yang telah dilalui. Semakin besar jumlah semut dan siklusnya, maka hasil dari algoritma tersebut akan semakin besar pula kemungkinan untuk menemukan jarak terpendek. Sedangkan siklus perjalanan mempengaruhi banyaknya jalur yang ditempuh oleh semut. Study kasus pada penelitian ini berlokasi di SMP Maitreyawira, Sekolah yang berlokasi di kota tanjungpinang. Berikut adalah salah satu contoh langkahlangkah perhitungan penataan tempat duduk ujian dengan menggunakan algoritma semut.
31 32
4.1.1. Inisial Parameter
KELAS
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Agnes Marethia Levana April Susanto Kurniawan Septavia Valeada Vivian Grace Agnes Ryan Kenidy Vannes Lee Dareck Desmond Maximilian Ratih Angelina Shinta Dewi
7a 7a 7a 7a 7a 7a 7b 7c 7c 7d 7d 7d 7d 7d
9c 9c
Alpha : 1.0 Beta : 1.0 Rho : 0.5 Q : 1.0 NCmax : 5 Jumlah Siswa : 32 Jumlah Semut : 32 Tij Awal : 0,01
Tabel 5.1. Tabel Data Siswa Ruang 1 NAMA
7e 7e 7e 8b 8b 8b 8c 8c 8c 8d 8d 8d 9a 9b 9c 9c
Pada Tahap Pertama Adalah Menetukan Parameter – parameter pada Algoritma Semut, Berikut adalah parameter – parameter Algoritma Semut:
Berikut adalah tabel data siswa pada ruang 1 yang akan digunakan untuk proses algoritma semut .
NO
Dessy Silvia Steven Irfando Moris Vivi Wu Vincent Calvin Kwok Elviria Fendy Evi Yulinda Lusi Ratnawati Megy Chang Novianti Augustina Veronica Ervina Febru Andy Hiroshi Everiil Jonathan Masli Ricky Ardianto
4.1.2. Penyisian Siswa Pertama Dalam Tabu List Pada tahap pengisian siswa pertama ke dalam tabu list. Hasil inisialisasi siswa pertama setiap semut dalam langkah ini harus diisikan sebagai elemen pertama tabu list. Berikut penyisian siswa pertama dalam tabu list : Posisi Awal Semut 1 : 3 Posisi Awal Semut 2 : 2 Posisi Awal Semut 3 : 25 7
(0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) = 0.3100000000000001
Posisi Awal Semut 4 : 9 Posisi Awal Semut 5 : 12 Posisi Awal Semut 6 : 32 Posisi Awal Semut 7 : 30 Posisi Awal Semut 8 : 26 Posisi Awal Semut 9 : 15 Posisi Awal Semut 10 : 1 Posisi Awal Semut 11 : 22 Posisi Awal Semut 12 : 24 Posisi Awal Semut 13 : 20 Posisi Awal Semut 14 : 16 Posisi Awal Semut 15 : 4 Posisi Awal Semut 16 : 7 Posisi Awal Semut 17 : 13 Posisi Awal Semut 18 : 21 Posisi Awal Semut 19 : 27 Posisi Awal Semut 20 : 18 Posisi Awal Semut 21 : 5 Posisi Awal Semut 22 : 10 Posisi Awal Semut 23 : 31 Posisi Awal Semut 24 : 17 Posisi Awal Semut 25 : 8 Posisi Awal Semut 26 : 28 Posisi Awal Semut 27 : 11 Posisi Awal Semut 28 : 6 Posisi Awal Semut 29 : 23 Posisi Awal Semut 30 : 19 Posisi Awal Semut 31 : 14 Posisi Awal Semut 32 : 29
probalitas siswa 3 ke 1 = (0.011 . 11) / 0.3100000000000001 = 0.032258064516129024 probalitas siswa 3 ke 2 = (0.011 . 11) / 0.3100000000000001 = 0.032258064516129024 [….] Nilai Komulatif Semut 1 : 0.032258064516129024; 0.06451612903225805; 0.06451612903225805; 0.09677419354838707; 0.1290322580645161; 0.16129032258064513; 0.19354838709677416; 0.2258064516129032; 0.2580645161290322; 0.2903225806451612; 0.3225806451612902; 0.3548387096774192; 0.3870967741935482; 0.4193548387096772; 0.4516129032258062; 0.4838709677419352; 0.5161290322580643; 0.5483870967741933; 0.5806451612903223; 0.6129032258064513; 0.6451612903225803 ; 0.6774193548387093; 0.7096774193548383; 0.7419354838709673; 0.7741935483870963; 0.8064516129032253; 0.8387096774193543; 0.8709677419354833; 0.9032258064516123; 0.9354838709677413; 0.9677419354838703; 0.9999999999999993;
4.1.3. Menyusun Rute Kunjungan Penyusunan rute kunjungan setiap semut ke setiap siswa. Koloni semut sudah terdistribusi ke sejumlah atau setiap siswa, akan mulai melakukan perjalanan dari siswa pertama masing – masing sebagai siswa asal dan salah satu siswa – siswa lainnya sebagai siswa tujuan. Semut 1 giliran 2 ∑𝑘 ′ ∈[𝑁−𝑡𝑎𝑏𝑢𝑘][𝑇𝑖𝑘 ′ ]𝛼 . [𝑛𝑖𝑘 ′ ]𝛽 = (0.011 . 11) + (0.011 . 11) + (0.01 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) + (0.011 . 11) +
Nilai Random : 0.5759948030019463 Jalur Selanjutnya : 19 8
Jalur 1 - 2 = (0.5 x 0,01) + 0 = 0.005, dimana 0,001 ≥ Tij ≤ 1.00, jadi Tij = 0.001 Sampai dengan semua semut telah mengunjungi seluruh siswa – siswa langkah berikut nya adalah menyisi jalur tersebut kedalam tabu list. Berikut adalah tabu list iterasi 1 :
Jalur 1 - 3 = (0.5 x 0,01) + 0 = 0.005, dimana 0,001 ≥ Tij ≤ 1.00, jadi Tij = 0.001 Jalur 1 - 4 = (0.5 x 0,01) + 0 = 0.005, dimana 0,001 ≥ Tij ≤ 1.00, jadi Tij = 0.001
Jalur Semut 1 : 3 - 19 - 5 - 13 - 25 - 30 - 31 - 14 - 22 - 2 - 16 - 17 - 9 - 6 - 21 - 32 - 20 18 - 15 - 12 - 7 - 26 - 28 - 29 - 24 - 1 - 11 23 - 4 - 27 - 8 – 10
Jalur 1 - 5 = (0.5 x 0,01) + 0 = 0.005, dimana 0,001 ≥ Tij ≤ 1.00, jadi Tij = 0.001 Jalur 1 - 6 = (0.5 x 0,01) + 0 = 0.005, dimana 0,001 ≥ Tij ≤ 1.00, jadi Tij = 0.001
4.1.4. Perhitungan Error Sebelum melakukan perhitungan telebih dahulu melakukan penataan tempat duduk yang ada pada tabu list agar dapat dihitung error nya, Berikut adalah gambar denah sementara berdasarkan urutan siswa yang ada pada tabel 5.1.
Jalur 1 - 7 = (0.5 x 0,01) + 0 = 0.005, dimana 0,001 ≥ Tij ≤ 1.00, jadi Tij = 0.001 Jalur 1 - 8 = (0.5 x 0,01) + 0 = 0.005, dimana 0,001 ≥ Tij ≤ 1.00, jadi Tij = 0.001 Jalur 1 - 9 = (0.5 x 0,01) + 0 = 0.005, dimana 0,001 ≥ Tij ≤ 1.00, jadi Tij = 0.001 Jalur 1 - 10 = (0.5 x 0,01) + 0 = 0.005, dimana 0,001 ≥ Tij ≤ 1.00, jadi Tij = 0.001 Jalur 1 - 11 = (0.5 x 0,01) + (1 / 18.75) = 0.0633, dimana 0,001 ≥ Tij ≤ 1.00, jadi Tij = 0.0633 […..] Sampai dengan semua jalur telah dihitung. Dan mengisi berubahan Tij untuk langkah berikutnya.
Gambar 5.1. Denah Sementara Semut 1 6 𝑥 100 = 18,75 % 32 Jadi error pada semut 1 adalah 18.75 %
4.1.6. Pengosongan Tabulist
𝑒𝑟𝑟𝑜𝑟 =
Kosongkan semua tabu list dan ulangi ke langkah 4.1.2. sampai dengan iterasi = NCmax baru mencari jalur terbaik dari setiap iterasi, Berikut adalah hasil seluruh Jalur Terbaik setelah iterasi = NCmax :
4.1.5. Perhitungan Harga Itensitas Jejak Kaki Semut Pada langkah berikut ini adalah menghitung harga itensitas kaki semut pada siswa yang telah dilewati semut. Berikut adalah perhitung harga itensitas jejak kaki semut pada semut 1:
Iterasi 1 : 27 - 29 - 3 - 22 - 30 - 9 - 5 - 17 - 6 - 25 - 13 - 23 - 4 - 10 - 31 - 20 - 11 - 15 - 7 14 - 32 - 1 - 12 - 24 - 26 - 18 - 21 - 16 - 2 28 - 19 - 8 - = 12.5% 9
Iterasi 2 : 29 - 19 - 17 - 5 - 14 - 24 - 31 - 1 - 27 - 23 - 32 - 7 - 28 - 15 - 6 - 10 - 2 - 9 26 - 22 - 13 - 21 - 4 - 30 - 12 - 18 - 8 - 20 25 - 16 - 3 - 11 - = 6.25% Iterasi 3 : 31 - 24 - 14 - 5 - 17 - 27 - 1 - 25 - 16 - 3 - 11 - 29 - 21 - 4 - 30 - 28 - 15 - 6 10 - 32 - 7 - 18 - 12 - 26 - 9 - 2 - 23 - 8 20 - 13 - 22 - 19 - = 6.25% Gambar 5.2. Hasil Simulasi 1 Algoritma
Iterasi 4 : 8 - 3 - 16 - 26 - 9 - 11 - 29 - 27 23 - 28 - 15 - 6 - 14 - 17 - 2 - 10 - 22 - 7 32 - 19 - 18 - 12 - 30 - 4 - 21 - 13 - 20 - 25 - 1 - 31 - 24 - 5 - = 6.25%
Semut Pada gambar di atas dapat di lihat bahwa dengan penataan tempat duduk ujian dengan mengganakan algoritma semut dengan NCmax = 5 menghasilkan error = 6.25 % dan memiliki siswa yang duduk bersebelahan berjumlah 2 siswa.
Iterasi 5 : 30 - 22 - 14 - 24 - 9 - 11 - 3 - 16 - 4 - 21 - 19 - 31 - 1 - 6 - 15 - 28 - 8 - 32 25 - 10 - 2 - 18 - 27 - 17 - 5 - 29 - 23 - 26 7 - 13 - 20 - 12 - = 9.375% Jadi Jalur Terbaik Pada Iterasi ke 4 Adalah : 8 - 3 - 16 - 26 - 9 - 11 - 29 - 27 - 23 - 28 15 - 6 - 14 - 17 - 2 - 10 - 22 - 7 - 32 - 19 18 - 12 - 30 - 4 - 21 - 13 - 20 - 25 - 1 - 31 24 - 5 - dengan total error 6.25%
4.2. Analisa Hasil Perbandingan Pengacakan Algoritma Semut dan Fisher-Yates Suffle Pada tabel dibawah ini adalah hasil simulasi yang dilakukan selama penelitian, simulasi dilakukan sebanyak 4 kali dengan jumlah iterasi yang berbeda untuk membandingkan hasil terbaik, rata- rata hasil siklus, dan waktu proses.
Tabel 5.2. Data Simulasi Pengacakan Algoritma Semut Pengacakan Algoritma Semut Simulasi 1 Iterasi
Error
Simulasi 2 Iterasi
Error
Simulasi 3 Iterasi
Error
Simulasi 4 Iterasi
Error
1
12.5 %
1
0.0%
1
6.25%
1
6.25%
2
6.25 %
2
0.0%
2
6.25%
2
9.375%
3
6.25 %
3
6.25%
3
6.25%
3
12.5%
4
6.25 %
4
6.25%
4
6.25%
4
6.25%
5
9.375%
5
15.625%
5
12.5%
5
12.5%
6
9.375%
6
15.625%
6
6.25%
10
7
3.125%
7
15.625%
7
12.5%
8
0.0%
8
6.25%
8
9.375%
9
6.25%
9
6.25%
9
12.5%
10
0.0%
10
6.25%
10
9.375%
11
0.0%
11
6.25%
12
6.25%
12
0.0%
13
6.25%
13
0.0%
14
6.25%
14
6.25%
15
6.25%
15
0.0%
16
0.0%
17
0.0%
18
0.0%
19
0.0%
20
0.0%
20
0.0%
Hasil Terbaik 4
6.25%
10
0.0%
11
0.0%
Rata – Rata Hasil Siklus 8.125 %
4.6875 %
7.5 %
5.46875 %
Waktu Proses 49 Detik
99 Detik
150 Detik
201 Detik
Pada tabel 5.2. data simulasi pengacakan algoritma semut dapat dilihat semakin besar siklus error terbaik bisa hingga 0.0 % dengan rata – rata hasil siklus 5.47 % tetapi waktu proses mencapai 201 detik
Tabel 5.3. Data Simulasi Pengacakan Fisher-Yates Suffle Pengacakan Fisher-Yates Suffle Simulasi 1 Iterasi
Error
1
25.0%
2
Simulasi 2 Iterasi 1
Error
Simulasi 3 Iterasi
Error
Simulasi 4 Iterasi
Error
18.75%
1
37.5%
1
18.75%
34.375% 2
15.625%
2
18.75%
2
31.25%
3
12.5%
3
15.625%
3
18.75%
3
18.75%
4
6.25%
4
21.875%
4
12.5%
4
12.5%
11
5
34.375% 5
21.875%
5
28.125%
5
25.0%
6
28.125%
6
31.25%
6
31.25%
7
43.75%
7
21.875%
7
18.75%
8
40.625%
8
37.5%
8
25.0%
9
31.25%
9
25.0%
9
21.875%
10
21.875%
10
25.0%
10
15.625%
11
50.0%
11
46.875%
12
25.0%
12
21.875%
13
25.0%
13
15.625%
14
34.375%
14
6.25%
15
25.0%
15
15.625%
16
28.125%
17
31.25%
18
40.625%
19
31.25%
20
31.25%
14
6.25%
Hasil Terbaik 4
6.25%
3
15.625%
4
12.5%
Rata – Rata Hasil Siklus 22.5%
23.75%
27.71%
24.375%
Waktu Proses 2 Detik
2 Detik
2 Detik
2 Detik
Pada tabel 5.3. data simulasi pengacakan algoritma fisher-yates suffle dapat dilihat error terbaik hanya 6.25 % dengan rata – rata hasil siklus 24.375 % tetapi waktu proses hanya membutuhkan 2 detik.
12
Gambar 5.5 Grafik Perbandingan Waktu Proses dan pada gambar 5.5. dapat dilihat bahwa algoritma semut membutuhkan waktu proses yang lama semakin tinggi siklis semakin lama di proses dari gambar diatas dapat dilihat bahwa pada simulasi 4 menggunakan 20 siklus membutuhkan waktu 201 detik. Dari hasil di atas dapat disimpulkan bahwa pengacakan dengan algoritma semut dapat menghasilkan error terbaik 0,0% dengan rata – rata siklus terbaik 4,687 % sedangkan pengacakan fisher-yates suffle menghasilkan error terbaik 6.25% dengan rata – rata siklus terbaik 22.5%. akan tetapi, waktu proses pada pengacakan fisher-yates suffle lebih cepat dibandingkan dengan pengacakan algoritma semut. Semakin banyak siklus yang diproses semakin lama waktu prosesnya.
Gambar 5.3. Grafik Perbandingan Hasil Terbaik Data pada gambar 5.3. dapat dilihat pengacakan algoritma semut lebih baik di bandingkan dengan pengacakan fisheryates suffle dengan error sebesar 0.0%
V. KESIMPULAN DAN SARAN Kesimpulan yang di dapat di ambil dari penelitian ini yaitu bahwa dengan penerapan Algoritma Semut, dapat menghasilkan error terbaik 0,0% dengan rata – rata siklus terbaik 4,687 % sedangkan pengacakan fisher-yates suffle menghasilkan error terbaik 6.25% dengan rata – rata siklus terbaik 22.5%. akan tetapi, waktu proses pada pengacakan fisher-yates suffle lebih cepat dibandingkan dengan pengacakan algoritma semut. Semakin banyak siklus yang diproses semakin lama waktu prosesnya.
Gambar 5.4. Grafik Perbandingan Rata – Rata Siklus dan pada gambar 5.4. dapat dilihat bahwa pengacakan algoritma semut dapat menghasilkan rata – rata error paling sedikit 5.46875 % sedangkan pada fisheryates suffle dapat mencapai 27.71%.
Saran untuk penelitian selanjutnya yaitu menggunakan dua perbandingan algoritma dalam penataan tempat duduk agar dapat mencapai hasil yang lebih optimal.
13
DAFTAR PUSTAKA
Fernandez, A., 2012, Pembangunan Aplikasi Penyusunan Jadwal Kuliah Menggunakan Algoritma Semut, Skripsi, Universitas Diponegoro, Semarang. Fitriani, D. R., 2015, Analisa Pencarian Jalur Terpendek Ke Penginapan Di Kota Batam Dengan Menggunakan Algoritma Semut, Skripsi, Universitas Maritim Raja ali Haji, Kepulauan Riau. Socha, K., Sampels, M., and Manfrin, M. , 2003, Ant Algorithms for the University Course Timetabling Problem with Regard to the State-of-the-Art, Université Libre de Bruxelles, Belgium Mutakhiroh, I., Indrato, dan Hidayat, T., 2007, Pencarian Jalur Terpendek Menggunakan Algoritma Semut, Skripsi, Universitas Islam Indonesia, Yogyakarta. Nugraha, R., 2015, Penerapan Algoritma Fisher Yates Pada Aplikasi The Lost Insect Untuk Pengenalan Jenis Serangga Berbasis Unity 3D, Skripsi, STMIK Global Informatika MDP, Palembang. Paninalone, (2011), Algoritma Semut (Ant Algorithm), https://paninalone.wordpress.com/2011/11/11/algoritma-semut-ant-algorithm/, 1 October 2015 Savira, M., 2014, Analisis Peramalan Penjualan Obat Generik Berlogo (OGB) Pada PT. Indonesia Farma, Skripsi, Universitas Telkom, Bandung Sudrajat, A., (2008), Penataan Tempat Duduk Siswa sebagai Salah Satu Bentuk Pengelolaan Kelas, https://akhmadsudrajat.wordpress.com/2008/07/28/penataantempat-duduk-siswa-sebagai-bentuk-pengelolaan-kelas/, 1 October 2015
14
