1
Rancang Bangun Aplikasi Prediksi Jumlah Penumpang Kereta Api Menggunakan Algoritma Genetika Annisti Nurul Fajriyah Politeknik Elektronika Negeri Surabaya Institut Teknologi Sepuluh Nopember (ITS) Surabaya Kampus PENS-ITS, Keputih, Sukolilo, Surabaya E-mail :
[email protected] ,
[email protected]
ABSTRAK Algoritma genetika sebagai algoritma untuk optimasi suatu masalah diterapkan untuk meramalkan jumlah penumpang yang akan menggunakan jasa kereta api. Data hasil penjualan tiket kereta api digunakan untuk inputan data training dan data testing yang akan menghasilkan nilai koefisien. Nilai koefisien terkecil dalam populasi akan digunakan untuk dikalikan dengan data hasil penjualan tiket kereta api yang akan menghasilkan nilai estimasi jumlah penumpang kereta api untuk beberapa tahap kedepan. Percobaan dilakukan pada 7 macam kereta yang berbeda dan didapatkan hasil beberapa kereta mempunyai akurasi yang besar yaitu dengan melihat nilai persentase kesalahan (MAPE) yang kecil pada kereta mutiara selatan (15%), mutiara timur eksekutif (18%), sancaka bisnis (17%), sancaka eksekutif (15%) dan turangga (20%). Namun untuk kereta argowilis dan mutiara timur bisnis belum dapat akurat dikarenakan nilai prosentase kesalahan masih di atas 20%. Kata kunci : algoritma genetika, estimasi, penumpang kereta api I. Pendahuluan Dalam era globalisasi dan perkembangan ekonomi yang cukup pesat saat ini, alat transportasi dan komunikasi merupakan kebutuhan yang cukup penting. Terutama alat tarnsportasi darat jarak jauh yang banyak memberikan kontribusi paling banyak untuk kebutuhan masyarakat maupun pemerintah, dalam hal ini kereta api. PT. Kereta Api (Persero) mempunyai beberapa jenis layanan yaitu : kereta api penumpang, kereta api barang, kereta api properti dan kereta komuter. Algoritma genetika merupakan salah satu cabang dari algoritma evolusi merupakan metode adaptive yang biasa digunakan untuk memecahkan suatu nilai dalam sebuah masalah optimasi. Algoritma ini didasarkan pada proses
genetik yang ada dalam makhluk hidup yaitu perkembangan generasi dalam sebuah populasi yang alami, secara lambat laun menikuti prinsip seleksi alam atau “siapa yang kuat, dia yang bertahan (survive)”. Dengan meniru teori evolusi ini, algoritma genetika dapat digunakan untuk mencari solusi permasalahan – permasalahan dalam dunia nyata. Pada tugas akhir ini algoritma genetika diterapkan untuk meramalkan jumlah penumpang yang akan menggunakan jasa kereta api. Sehingga nantinya apabila pada hasil prediksi menunjukkan adanya lonjakan/kenaikan jumlah penumpang, PT KAI dapat menambahkan jumlah rangkaian kereta api. II. Rumusan Masalah dan Batasan A. Rumusan Masalah Adapun permasalahan yang dihadapi dalam menyelesaikan tugas akhir ini adalah: 1. Bagaimana dapat memprediksi jumlah penumpang kereta api 2. Bagaimana implementasi algoritma genetika untuk memprediksi jumlah penumpang kereta api. B. Batasan Masalah Pada permasalahan tersebut akan diberi batasan - batasan masalah sebagai berikut : 1. Data yang digunakan bersifat numerik. 2. Menggunakan data penumpang kereta api selama ± 2 tahun pada hasil penjualan tiket di stasiun kereta api gubeng surabaya. 3. Menentukan data training 75% dari jumlah data secara keseluruhan. 4. Menentukan data testing 25% dari jumlah data training. 5. Algoritma genetika yang digunakan adalah kromosom float, crossover dilakukan dengan jalan pertukaran aritmatika, dan mutasi dilakukan dengan menggunakan shift mutation. III. Tujuan
2
Proyek Akhir yang berjudul “Rancang Bangun Aplikasi Prediksi Jumlah Penumpang Kereta Api Menggunakan Algoritma Genetika” ini bertujuan untuk: 1. Menghasilkan suatu aplikasi yang berfungsi untuk memprediksi jumlah penumpang kereta api. 2. Mengembangkan proses komputasi dengan algoritma genetika untuk menyelesaikan permasalahan peramalan. IV. Tinjauan Pustaka Algoritma genetika pada dasarnya adalah program komputer yang mensimulasikan proses evolusi. Dalam hal ini populasi dari kromosom dihasilkan secara random dan memungkinkan untuk berkembang biak sesuai dengan hukumhukum evolusi dengan harapan akan menghasilkan individu kromosom yang prima. Kromosom ini pada kenyataannya adalah kandidat penyelesaian dari masalah, sehingga bila kromosom yang baik berkembang, solusi yang baik terhadap masalah diharapkan akan dihasilkan. Algoritma genetika ini banyak dipakai pada aplikasi bisnis, teknik maupun pada bidang keilmuan. Algoritma ini dapat dipakai untuk mendapatkan solusi yang tepat untuk masalah optimal dari satu variabel atau multi variabel. Sebelum algoritma ini dijalankan, masalah apa yang ingin dioptimalkan itu harus dinyatakan dalam fungsi tujuan, yang dikenal dengan fungsi fitness. Jika nilai fitness semakin besar, maka sistem yang dihasilkan semakin baik. Walaupun pada awalnya semua nilai fitness kemungkinan sangat kecil (karena algoritma ini menghasilkannya secara random), sebagian akan lebih tinggi dari yang lain. Kromosom dengan nilai fitness yang tinggi ini akan memberikan probabilitas yang tinggi untuk bereproduksi pada generasi selanjutnya. Sehingga untuk setiap generasi pada proses evolusi, fungsi fitness yang mensimulasikan seleksi alam, akan menekan populasi kearah fitness yang meningkat. Algoritma genetika sangat tepat digunakan untuk penyelesaian masalah optimasi yang kompleks dan sukar diselesaikan dengan menggunakan metode yang konvensional. Sebagaimana halnya proses evolusi di alam, suatu algoritma genetika yang sederhana umumnya terdiri dari tiga operator yaitu: operator reproduksi, operator crossover (persilangan) dan operator mutasi.
Gambar 4.1 Gambaran umum algoritma genetika Struktur umum dari suatu algoritma genetika dapat didefinisikan dengan langkahlangkah sebagai berikut: 1. Membangkitkan populasi awal Proses membangkitkan sejumlah individu secara acak melalui prosedur tertentu. Ukuran untuk populasi tergantung pada masalah yang akan diselesaikan dan jenis operator genetika yang akan di implementasikan. Setelah ukuran populasi ditentukan, kemudian dilakukan pembangkitan populasi awal 2. Membentuk generasi baru Dalam membentuk digunakan tiga operator yang telah disebut di atas yaitu operator reproduksi/seleksi, crossover dan mutasi. 3. Evaluasi solusi Proses ini akan mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom dan mengevaluasinya sampai terpenuhi kriteria berhenti. Bila kriteria berhenti belum terpenuhi maka akan dibentuk lagi generasi baru dengan mengulangi langkah 2. Beberapa kriteria berhenti yang sering digunakan antara lain: • Berhenti pada generasi tertentu. • Berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi tidak berubah. • Berhenti bila dalam n generasi berikut tidak didapatkan nilai fitness yang lebih tinggi. V. Metodologi A. Design Sistem Gambaran umum dari proyek akhir “Rancang Bangun Aplikasi Prediksi Jumlah Penumpang Kereta Api Menggunakan Algoritma Genetika” :
3
ε = nilai error MSE = rata-rata error = nilai prediksi pada waktu ke k
d. • • Gambar 1 Gambaran Umum Proyek Akhir Keterangan : • Input : data ini didapatkan dari 75% dari jumlah data keseluruhan. • Test : data ini didapatkan 25% dari jumlah data input • Training : proses ini menggunakan algoritma genetika • α : nilai koefisien model linier • x : perkalian antara training dan test • Forecast : hasil dari peramalan Proses Training Menggunakan Algoritma Genetika : Misalkan P (generasi) adalah populasi dari satu generasi, maka secara sederhana algoritma genetika terdiri dari langkah - langkah: a. Generasi = 0 (generasi awal) Representasi Kromosom Menggunakan persamaan linier :
•
= invers nilai prediksi pada waktu ke k n = jumlah data Kerjakan langkah - langkah berikut hingga generasi mencapai maksimum generasi: Generasi = generasi+1 (tambah generasi) Seleksi populasi tersebut untuk mendapatkan kandidat induk,P’(generasi) è menggunakan Roulette whell Lakukan arithmetic crossover pada P’ (generasi).
Dimana : : induk ke k : anak ke k r : bilangan antara 0 sampai 1 • Lakukan shift mutation pada P’ (generasi). Shif mutation dilakukan dengan cara: § Menentukan dua site secara random § Site pertama ditempatkan ke site kedua, untuk selanjutnya digeser ke kiri • Lakukan evaluasi fitness setiap individu pada P’ (generasi). • Bentuk populasi baru: P (generasi) = { P (generasi 1) yang survive, P’ (generasi)} VI. Uji coba dan Pembahasan
Dimana : : error perkiraan : bobot pengaruh dari waktu ke 1 -n x1(k) ~ xn(k) : data input prediksi pada waktu ke k y(k+1) : data nilai prediksi pada waktu ke k+1 b. Inisialisasi populasi awal, P (generasi), secara acak c. Evaluasi nilai fitness pada setiap individu dalam P (generasi).
Dimana : f = nilai fitness
A. Data Data penumpang kereta api didapatkan dari stasiun kereta api gubeng – Surabaya. Dari keseluruhan sebanyak kurang lebih 2 tahun (730 hari). Dari jumlah total data dibagi menjadi 2 bagian : data training dan data testing.
Gambar 2 Jumlah Data 1 Tahun (365 hari) B. Penentuan Probabilitas Crossover dan Probabilitas Mutasi Terbaik Berdasarkan Nilai Mean Square Error Untuk melakukan penentuan probabilitas crossover dan probabilitas mutasi terbaik, maka digunakan beberapa ketentuan yang nantinya akan digunakan oleh
4
seluruh data. Ketentuannya adalah sebagai berikut : • Jumlah individu yang dipakai sebanyak 32 individu • Nilai probabilitas crossover (Pco) adalah 0.7, 0.8, 0.9 • Nilai probabilitas mutasi (Pm) adalah 0.05, 0.1, 0.15, 0.2. • Iterasi yang dilakukan sebanyak 1000 kali. • Penentuan MSE terbaik adalah berdasarkan nilai MSE terkecil C. Penentuan Nilai Mean Square Error Pada Data Jumlah Penumpang Kereta Argowilis Berikut akan ditampilkan nilai mean square error dengan menggunakan ketentuan-ketentuan pada sub bab B Dat a
PC O
P M 0.0 5 0.1
0.7
0.1 5 0.2
Dat a1 365 Har i
0.0 5 0.1 0.8
0.1 5 0.2 0.0 5 0.1
0.9
0.1 5 0.2
Nilai Mean Square Error P1
P2
P3
P4
P5
1546. 61 1531. 83 1523. 52 1526. 47 1511. 85 1512. 12 1612. 94 1507. 42 1532. 33 1506. 28 1519. 36 1506. 61
1525. 63 1500. 30 1530. 73 1523. 92 1534. 53 1516. 66 1535. 89 1523. 42 1567. 16 1521. 67 1511. 92 1512. 69
1610. 77 1506. 20 1521. 18 1495. 49 1511. 33 1682. 88 1518. 87 1519. 20 1538. 70 1516. 49 1513. 19 1499. 89
1531. 22 1522. 83 1532. 64 1537. 61 1518. 18 1515. 84 1512. 15 1534. 65 1736. 74 1530. 92 1498. 76 1530. 02
1514. 53 1511. 52 1528. 63 1500. 76 1529. 88 1530. 27 1525. 62 1513. 04 1534. 70 1530. 61 1520. 77 1530. 10
Tabel 1 Penggunaan Nilai Probabilitas Crossover dan Probabilitas Mutasi Pada Data Jumlah Penumpang Argowilis Pada percobaan di atas menunjukkan adanya perbedaan nilai MSE yang tidak jauh antara yang satu dan lainnnya. Namun pada data di atas yang pertama ini nampak nilai yang paling kecil adalah nilai MSE yang menggunakan probabilitas crossover (Pco) 0.9 dan probababilitas mutasi (Pm) 0.15. D. Menentukan Hasil Mean Square Error Pada Hasil Estimasi Pada sub-bab ini akan membandingan hasil nilai estimasi yang diperolah menggunakan metode algoritma genetika dan metode ARIMA. Dari hasil estimasi tersebut kemudian
dihitung nilai rata-rata error (mean square error) setiap jumlah periode. Mean square error didapatkan dari rumus :
Dimana : MSE = rata-rata error = nilai prediksi pada waktu ke k = invers nilai prediksi pada waktu ke k n = jumlah periode data E. Perbandingan Nilai Hasil Estimasi dan Nilai Aktual Pada Data Kereta Argowilis Berikut ini akan ditampilkan tabel perbandingan antara data penjualan real dengan estimasi jumlah penumpang pada hari yang sama pada jumlah penumpang hasil penjualan tiket kereta dengan menggunakan ketentuan-ketentuan pada sub bab C Pada peramalan algoritma genetika dibawah ini menggunakan nilai probabilitas crossover sebesar 0,9 dan nilai probabilitas mutasi sebesar 0,15. Tahap
Nilai Aktual
Nilai Estimasi AG
MSE AG
Nilai Estimasi ARIMA
MSE ARIMA
1
41
96
3025
31
100
2
121
118
9
33
7744
3
76
75
1
32
1936
4
98
169
5041
57
1681
5
93
87
36
59
1156
6
81
94
169
68
169
7
86
126
1600
40
2116
8
150
90
3600
26
15376
9
63
76
169
30
1089
10
56
67
121
27
841
11
76
111
1225
57
361
12
84
143
3481
55
841
13
86
56
900
69
289
14
54
53
1
33
441
15
86
93
49
26
3600
16
63
102
1521
29
1156
17
68
64
16
27
1681
18
57
65
64
52
25
19
86
53
1089
53
1089
20
141
114
729
64
5929
Rata – Rata Error
1142
2381
MAD
25,8
39,9
MAPE
0,33
0,44
5
Tabel 2 Hasil Perbandingan Nilai Estimasi Algoritma Genetika dan ARIMA Pada Jumlah Penumpang Kereta Argowilis
Arif, “Algoritma Genetika dan Aplikasinya”, www.cakrawala.co.id, 2007 Arna Fariza, Achmad Basuki, “Peramalan Penjualan Time Series Menggunakan Algoritma Genetika”, SITIA 2003, ITS, 2003, Research Seminar. Edy Satriyanto, “Forecasting Teknik Peramalan dan Aplikasinya”, Politeknik Elektronika Negeri Surabaya
Gambar 3 Grafik Perbandingan Nilai Estimasi Algoritma Genetika dan Arima Pada Jumlah Penumpang Kereta Argowilis
VII. Kesimpulan Dari hasil uji coba dan analisa, dapat disimpulkan beberapa hal antara lain : 1. Aplikasi prediksi jumlah penumpang kereta api dengan menggunakan metode algoritma genetika memiliki kriteria yang sederhana, semakin kecil nilai mean square error, mean absolute error dan mean absolute percentage error, maka semakin baik dan akurat hasil prediksi yang didapatkan. 2. Percobaan dilakukan pada 7 macam kereta yang berbeda dan didapatkan hasil beberapa kereta mempunyai akurasi yang besar yaitu dengan melihat nilai persentase kesalahan (MAPE) yang kecil pada kereta mutiara selatan (15%), mutiara timur eksekutif (18%), sancaka bisnis (17%), sancaka eksekutif (15%) dan turangga (20%). Namun untuk kereta argowilis dan mutiara timur bisnis belum dapat akurat dikarenakan nilai prosentase kesalahan masih di atas 20%.
VIII.
Daftar Pustaka
Achmad Basuki, “Algoritma Genetika Suatu Alternatif Penyelesaian Permasalahan Searching Optimasi dan Machine Learning”, Politeknik Elektronika Negeri Surabaya, 2003 Achmad Basuki, Arna Fariza, “Peningkatan Kinerja Algoritma Genetika pada Peramalan Time Series dengan Klasifikasi Data Berdasarkan Trend”, IES 2003, Politeknik Elektronika Negeri Surabaya, 2003, Research Seminar Achmad Basuki, Arna Fariza, Joko Lianto B, “Peramalan Time Series Menggunakan Algoritma Genetika dengan Pengelompokan Berdasarkan Gradien Data”, SNIKTI 2003, ITS, 2003, Research Seminar.
http://blog.its.ac.id/arif05/2007/11/19/algoritmagenetik-dan-aplikasinya.htm http://creasoft.wordpress.com/2008/04/21/algorit ma-genetika-genetic-algorithm.htm http://www.kereta-api.co.id/ Pangestu Subagyo, “Forecasting Konsep dan Aplikasi”, Yogyakarta : BPFE, 1986 Sanjoyo, “Aplikasi Algoritma Genetika”, 2006
6
