BAB 2 TINJAUAN PUSTAKA 2.1 Tinjauan Literatur Algoritma genetik merupakan salah satu algoritma yang biasanya digunakan dalam optimalisasi data. Namun penggunaan algoritma genetik dalam melakukan peramalan juga pernah dilakukan oleh (Mandal, Ghosh, Roy, Choudhury, and Chaudhury, 2012) yang membandingkan hasil peramalan menggunakan algoritma genetik dengan fuzzy time series dan artificial neural network dengan fuzzy input. Dan didapatkan hasil peramalan menggunakan algoritma genetik lebih baik dibandingkan yang lainnya. Sedangkan pertumbuhan jumlah kendaraan sendiri sudah pernah dibahas oleh seperti (Wu, Zhao, and Ou, 2014) memprediksi kepemilikan kendaraan bermotor berdasarkan pendapatan per kapita suatu negara, (Resmana, Thiang and Kuntjoro, 1999) memprediksi jumlah kendaraan berdasarkan tingkat kebisingan lalu lintas, dan (Sya’diyah, 2012) memprediksi jumlah kendaraan dengan menggunakan algoritma backpropagation.
5
6
Tabel 2.1 –Perbandingan dengan penelitian lain Pengarang dan tahun Khair (2011)
Metode ARIMA dan Regresi Linear
Case Peramalan beban listrik jangka pendek
Variable input Beban listrik terdahulu + suhu + daya listrik
Variable output hasil peramalan beban listrik
Mandal, Ghosh, Roy, Choudhury, and Chaudhury (2012)
Genetic Algorithm
Membandingkan Algoritma genetik dengan algoritma lain
Panjang batang dari tanaman mustard
Hasil peramalan panjang batang dengan menggunakan algoritma genetik
Resmana, Thiang, and Kuntjoro (1999)
Fuzzy Logic
Meramalkan jumlah kendaraan bermotor berdasarkan tingkat kebisingan lalu lintas
Tingkat Kebisingan Lalu Lintas
Jumlah Kendaraan Bermotor
Sya'diyah (2012)
Backpropagation
Meramalkan jumlah kendaraan bermotor dengan Backpropagation
Jumlah Kendaraan bermotor tahun-tahun sebelumnya
Hasil peramalan jumlah kendaraan bermotor.
Tauryawati, dan Irawan (2014)
ARIMA dan Fuzzy time Series
Membandingkan hasil peramalan dari kedua metode tersebut.
Data IHGS sebelumnya
Hasil peramalan Data IHGS
Unsihuay-Vila, Zambroni de Souza, Marangon-Lima, and Balestrassi (2010)
Evolutionary Computation Combined with Chaotic Nonlinear Model
Meramalkan listrik yang dibutuhkan dan harganya
harga dan listrik yang digunakan per jam
Hasil peramalan harga listrik
Wu, Zhao, and Ou (2014)
Gompetz Function Per capita
Meramalkan jumlah kendaraan di China
GDP dan Stok kendaraan
Jumlah Kendaraan Bermotor
Berdasarkan tabel di atas diketahui berbagai perbedaan dari seluruh literatur yang digunakan dalam penelitian ini. Selain itu, diketahui juga bahwa sebagai perbedaan, penelitian ini sendiri berpusat pada penggunaan algoritma genetik sebagai metode untuk mengoptimalisasi variabel-variabel dan kemudian memprediksi
jumlah
kendaraan
dengan
menggunakan
ANN.
Namun
menggunakan variabel pengukuran yang berbeda yaitu jumlah kendaraan di Jakarta.
2.2 Algoritma Genetik Algoritma genetika pada dasarnya adalah program komputer yang mensimulasikan proses evolusi. Dalam hal ini populasi dari kromosom dihasilkan
7
secara random dan memungkinkan untuk berkembang biak sesuai dengan hukum-hukum 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 sangat tepat digunakan untuk penyelesaian masalah optimasi yang kompleks dan sukar diselesaikan dengan menggunakan metode yang konvensional. (Fajriyah, 2010)
Gambar 2.1 – Gambaran umum Algoritma Genetik
Algoritma genetik terdiri dari beberapa set solusi(kromosom) yang disebut populasi. Populasi baru dibuat dari sebuah populasi lama yang diharapkan akan mendapatkan populasi yang lebih baik. Solusi yang dipilih untuk membuat solusi baru(offspring) yang dipilih berdasarkan evaluasi nilai fitness mereka. Semakin cocok solusinya semakin besar kesempatan mereka bisa menghasilkan solusi baru. Proses ini diulang terus sampai suatu kondisi tercapai. (Mandal, Ghosh, Roy, Choudhury, and Chaudhury , 2012)
8
2.2.1 Kromosom Semua makhluk hidup terdiri dari banyak sel. Dalam setiap sel, terdapat set kromosom yang menjadi bagian dari DNA yang berperan sebagai ”blueprint” untuk makhluk tersebut. Dalam algoritma genetik, kromosom adalah nilai dalam pencarian dan diwakilkan dengan string yang terdiri dari 0 dan 1.
2.2.2 Operator Genetik Ada tiga tipe operator dalam algoritma genetik : 1. Seleksi Seleksi dilakukan berdasarkan prinsip ketahanan dari nilai fitness. Hal ini bisa menciptakan sebuah generasi baru dari kromosom yang berbeda dari generasi sebelumnya. Kromosom dengan nilai fitness yang lebih baik meningkat jumlahnya sedangkan kromosom dengan nilai yang lebih kecil semakin berkurang jumlahnya dan mungkin akan hilang nantinya. 2. Crossover Operator ini memilih acak sebuah bagian
antara dua set
kromosom yang memiliki ukuran yang sama untuk menciptakan dua offspring. Posisi dari set kromosom yang akan diambil ditentukan secara acak. Crossover ini meniru kombinasi biologis antara dua kromosom.
9
3. Mutasi Operator ini memilih secara random sebuah bit dalam kromosom yang dalam kode binary berarti mengubah 1 menjadi 0 atau sebaliknya. Mutasi bisa terjadi pada setiap posisi bit dalam string dengan beberapa kemungkinan, biasanya nilainya sangat kecil. Saat mutasi digunakan dengan reproduksi dan crossover, hal ini meningkatkan variasi dan kemungkinan lain dalam pencarian menggunakan algorima genetik.
2.2.3 Algoritma genetik sebagai feature selection Algoritma genetik merupakan suatu algoritma pencarian berdasarkan mekanisme seleksi alam dan genetika alam. Algoritma genetik dimulai dengan sekumpulan solusi awal (individu) yang disebut populasi. Satu hal yang sangat penting adalah bahwa satu individu menyatakan satu solusi. Populasi awal akan berevolusi menjadi populasi baru melalui serangkaian iterasi(generasi). Pada akhir iterasi, algoritma genetik mengembalikan satu anggota populasi yang terbaik sebagai solusi untuk masalah yang dihadapi. Pada setiap iterasi, proses evolusi yang terjadi adalah sebagai berikut : 1.
Dua individu dipilih sebagai orang tua(parent) berdasarkan mekanisme tertentu. Kedua parent ini kemudian dikawinkan melalui operator crossover untuk menghasilkan dua individu anak atau offspring.
10
2.
Dengan probabilitas tertentu, dua individu anak ini mungkin mengalami pengubahan gen melalui operator mutasi.
3.
Suatu skema penggantian tertentu sehingga menghasilkan populasi baru.
4.
Proses ini terus berulang sampai kondisi berhentu tertentu. Kondisi berhenti bisa berupa jumlah iterasi tertentu, waktu tertentu, atau ketika variasi individu-individu dalam populasi tersebut sudah lebih kecil dari suatu nilai tertentu yang diinginkan. (Wahyuni, Sutojo, Luthfiarta, 2014)
2.3 Metode Peramalan Time Series Time series adalah suatu himpunan pengamatan yang dibangun secara berurutan dalam waktu. Waktu atau periode yang dibutuhkan untuk melakukan suatu peramalan itu biasanya disebut sebagai lead time yang bervariasi pada tiap persoalan. Berdasarkan himpunan pengamatan yang tersedia maka time series dikatakan kontinu jika himpunan pengamatan tersebut adalah kontinu dan dikatakan diskrit bila himpunan pengaamatan tersebut juga diskrit. Dalam time series diskrit. interval waktunya seragam seperti, menit, jam, hari, minggu, bulan, kwartal atau tahunan. Berikut ini adalah algoritma yang sering digunakan untuk melakukan prediksi time series :
11
-
ARIMA Model ARIMA merupakan penggabungan dari dua metode yaitu Autoregressive dan MovingAverage. ARIMA mencari pola yang paling cocok dalam kesatuan waktu denganmenggunakan nilai masa lalu, dan meramalkan pola masa depan dalam jangkapendek. ARIMA cocok jika observasi time series secara statistik berhubungan satu sama lain.
-
Support Vector Regression Support Vector Regression (SVR) merupakan Support Vector Machines (SVM) untuk regresi yang merepresentasikan fungsi dengan sebagian training data, yang biasa disebut support vectors. Implementasi SVM untuk prediksi time series menunjukkan performance yang sangat baik.
Algortima lainnya yang digunakan untuk prediksi antara lain: -
Decision Tree Decision tree adalah sebuah diagram alur dengan struktur seperti pohon. Setiap node berisi menandakan suatu tes pada atribut. Setiap cabang mewakili hasil tes. Node daun merepresentasikan kelas distribusi. Struktur decision tree
menunjukkan aturan “jika-maka” (bukan
persamaan matematika) sehingga hasilnya mudah untuk ditafsirkan. Penelitian decision tree berkembang di bidang-bidang seperti rekayasa, bisnis, kedokteran dan pendidikan mengembangkan model decision tree unruk memprediksi kinerja siswa dalam dinamika teknik.
12
-
Naive Bayes Naive bayes merupakan teknik sederhana yang sangat cocok saat dimensi dari input tinggi. Meskipun sederhana, naive bayes seringkali dapat mengungguli metode klasifikasi yang lebih canggih. Aturan naive bayes merupakan dasar dari banyak machine learning dan metode data mining. Aturan naive bayes digunakan untuk membuat model dengan kemampuan prediksi. Algoritma ini digunakan saat:
-
•
Dimensi dari input tinggi
•
Atributnya tidak bergantung satu sama lain
•
Ingin output yang lebih efisien
Logika Fuzzy Logika
fuzzy
merupakan
sebuah
metodologi
sistem
kontrol
penyelesaian masalah yang cocok diimplementasikan dalam sistem, mulai dari sistem yang sederhana, kecil, embedded micro-controllers, hingga yang besar, jaringan, multi chanel PC dan sistem kontrol. Logika fuzzy menyediakan sebuah cara yang sederhana untuk mendapatkan kesimpulan berdasarkan informasi yang kabur, ambigu, tidak tepat atau bahkan yang hilang. Umumnya, logika fuzzy adalah metode cukup efektif untuk sistem yang model matematikanya tidak diketahui atau tidak dapat dibuat. (Sari, 2012)
13
2.4 Jaringan Syaraf Tiruan JST dibentuk sebagai generalisasi model matematika dari jaringan otak manusia, dengan asumsi bahwa : 1.
pemrosesan informasi terjadi pada banyak elemen sederhana (neuron).
2.
Sinyal dikirim diantara neuron-neuron melalui penghubung-penghubung.
3.
Penghubung antar neuron memiliki bobot yang akan memperkuat atau memperlemah sinyal.
4.
Setiap neuron memiliki fungsi aktivasi yang akan menentukan nilai sinyal output.
Jaringan
syaraf
dapat
digolongkan
menjadi
berbagai
jenis
berdasarkan pada arsitekturnya, yaitu pola hubungan antar neuron-neuron, dan algoritma pelatihannya (training), yaitu cara penentuan nilai bobot pada penghubung. Salah satu algoritma pelatihan JST yang banyak dimanfaatkan dalam bidang pengenalan pola adalah backpropagation. Algoritma ini umumnya digunakan pada JST yang berjenis multi layer feed forward yang tersusun dari beberapa lapisan dan sinyal dialirkan secara searah dari input dan output. Algoritma pelatihan backpropagation pada dasarnya terdiri dari tiga tahapan, yaitu: 1. Input nilai data pelatihan sehingga diperoleh nilai output 2. Propagasi balik dari nilai error yg diperoleh 3. penyesuaian bobot koneksi untuk meminimalkan nilai error. Ketiga tahapan tersebut diulangi terus menerus sampai mendapatkan nilai error yang diinginkan. Setelah training selesai dilakukan, hanya tahap
14
pertama yang diperlukan untuk memanfaatkan JST tersebut. Backpropagation memiliki beberapa unit yang ada dalam satu atau beberapa layar tersembunyi seperti terlihat pada gambar 2.2.
Gambar 2.2 - Arsitektur Jaringan Backpropagation Seperti yang digambarkan pada proses pelatihan, maka pada proses pengujian hanya membutuhkan proses propagasi maju, sinyal masukan (=xi) dipropagasikan ke layar tersembunyi dengan fungsi aktivasi yang ditentukan. Keluaran dari setiap unit layar tersembunyi dengan fungsi aktivasi yang ditentukan. Keluaran dari setiap unit layar tersembunyi (=zj) tersebut selanjutnya dipropagasikan maju lagi ke layar tersembunyi diatasnya menggunakan fungsi aktivasi tertentu. Demikian seterusnya hingga menghasilkan keluaran jaringan (=yk). Selanjutnya untuk mencari nilai dari delta hasil pada pola yang diujikan dapat dilakukan dengan mengurangi nilai input (=xi) terhadap batas error. Setelah nilai dari delta hasil didapat, dilanjutkan dengan memandingkan nilai delta terhadap keluaran pada jaringan (=yk). Nilai-nilai perbandingan itulah yang digunakan untuk mendapatkan nilai biner yang selanjutnya
15
akan dibandingkan terhadap pola biner pada citra yang sudah dilatih secara berurutan. Setelah semua citra dibandingkan akan menghasilkan nilai yang paling mendekati terhadap pola yang sedang diujikan. Hasil nilai perbandingan yang paling mendekati itulah yang digunakan untuk menentukan pola tersebut terkenali atau tidak. (Analis, and Setyaningsih, 2012)
2.4.1 Prediksi Menggunakan Jaringan Syaraf Tiruan Prediksi menggunakan jaringan syaraf tiruan memiliki kelebihan
antara
lain
adalah
kemampuannyadalammemodelkansuatukondisinonlinear;modelJSTtidak mengidentifikasi
membutuhkaninformasiaprioridalam
hubunganantarvariable;
arsitekturnya
relative
fleksibel untuk berbagai kondisi nilai input dan output; dan adanyamappinginputdanoutputmelalui prosespenyesuaianweightmenjadikan hubungan antara input dan output dapat ditemukan, jaringan lebih mudah beradaptasi, dan toleransi kesalahan dapat ditentukan sejak awal. Prediksi dengan menggunakan jaringan syaraf tiruan akan dilakukan dengan menggunakan backpropagation dan langkah-langkah yang akan dilakukan adalah sebagai berikut :
1. Inisialisasi semua bobot dengan bilangan acak kecil. Misal dengan nilai random antara -0.5 sampai 0.5. 2. Loopingaktivitas3hingga7.Syaratdariloopingadalahselamaepoch belum
16
mencapaikondisitertentu(untukmenghindariinfiniteloop)dan mean squared error belum mencapai nilai yang diinginkan. 3. Looping aktivitas 4 hingga 6, untuk tiap lapisan dalam jaringan. 4. Feedforward : pembobotan untuk hidden layer dan output dengan mengalikan nilai pada tiap lapisan dengan nilai weight, yang kemudian diperhitungkan dalam fungsi aktivasi yang digunakan. 5. Backpropagation : perhitungan error pada tiap lapisan, dan kemudian dihitung secara mundur sesuai dengan tingkat error masing-masing lapirsan, sesuai dengan learing rate yang ditentukan di awal. 6. Update weight dan biases: Penyesuaian weight tiap lapisan, sesuai dengan selisih yang dihasilkan pada proses sebelumnya di mana nilai momentum digunakan. 7. Test stopping condition. Untuk meningkatkan performa algoritma backpropagation, dilakukan beberapa langkah berikut ini : 1. Menggunakan fungsi aktivasi sigmoid, yaitu fungsi yang menghasilkan nilai -1 hingga 1. 2. Normalisasi input, dengan membentuk input yang memiliki covariance yang kurang lebih sama, sehingga setiap input memiliki kecepatan belajar yang sama.
