Jurnal METHODIKA.
Vol.
3 No.
1 MARET 2017 ISSN : 2442-7861
IMPLEMENTASI TWO POINT CROSSOVER PADA KNAPSACK PROBLEM
Rijois Iboy Erwin Saragih Komputerisasi Akuntansi.
Universitas Methodist Indonesia Email:erwin_saragih@yahoo.
Jl.
Hang Tuah No.
8 Medan.
Sumatera Utara
ABSTRACT
Genetic algorithm is heuristic searching algorithm which based on nature selection of mechanism and nature genetic.
The basic concept that inspires the genetic algorithm is that evolution theory.
One of crossover operator in genetic algorithm is two-point This operator can make better improvement in solving combinatorial problem.
Previous research has done with onepoint crossover and it is compared with tow-point crossover in this research.
Knapsack is a combinatorial problem which is to find good solution with constraint.
Evaluation is done 10 times execution on genetic algorithm (GA), and experimental results show that two-point crossover can gives a quite good result in solving optimization problem.
Keywords: Genetic Algorithm.
Two-Point Crossover.
Knapsack Problem
PENDAHULUAN
Algoritma genetika adalah kelas populasi berdasarkan teknik pencarian acak yang semakin banyak digunakan di sejumlah aplikasi praktis.
Biasanya algoritma ini mempertahankan sejumlah solusi potensial untuk masalah yang sedang ditangani, yang dapat dilihat sebagai bentuk memori kerja ini dikenal sebagai populasi.
Poin iteratif baru dalam ruang pencarian yang dihasilkan untuk evaluasi dan opsional dimasukkan ke dalam populasi (Smith, 2.
Permasalahan umum pada algoritma genetika yang sering terjadi adalah lokal optima dan hal ini terjadi karena hilangnya perbedaan populasi .
opulation diversit.
awal dengan populasi selanjutanya (Zhu & Liu, 2.
Jika perbedaan populasi terlalu kecil akan memungkinkan terjadinya lokal optima, dan jika terlalu besar akan mengakibatkan lamanya waktu yang dibutuhkan algoritma genetika dalam menghasilkan solusi terbaik.
Banyak penelitian yang telah dilakukan terkait dengan permasalahan diatas untuk menghindari lokal optima serta meningkatkan performansi algoritma genetika.
Salah satu pendekatan yang dilakukan melalui perbaikan kinerja dari operator genetika itu sendiri.
seperti operator seleksi.
Persilangan dan mutasi.
Menurut Varnamkhasti etal .
, performansi algoritma genetika dipengaruhi oleh operator genetika.
seleksi, persilangan dan mutasi secara umum.
Menurut Singh .
, permasalahan knapsack adalah suatu permasalahan optimasi kombinatorial.
Sebagai contoh diberikan satu set item dengan berat dan nilai, kemudian dilakukan pemilihan dari item-item tersebut untuk dimasukan kedalam ransel .
dengan kapasitas terbatas.
Jadi item-item yang dimasukan beratnya harus lebih kecil atau sama dengan kapasitas dari ransel tersebut, tetapi total nilai sebesar mungkin.
Penelitian terdahulu telah dilakukan menggunakan onepoint crossover, pada penelitian sekarang akan dilakukan menggunakan two-point crossover dengan harapan dapat memberikan hasil yang lebih baik terhadap permasalahan knapsack problem.
Berdasarkan penelitian di atas maka penulis tertarik untuk melakukan penelitian implementasi two-point crossover dalam menyelesaikan permasalahan METODE PENELITIAN Data knapsack problem adalah suatu permasalahan optimasi kombinatorial.
Data tersebut telah diuji oleh pelbagai algoritma yang berbeda untuk mencari solusi Sebagai perbandingan juga digunakan data penelitian terkait dengan 50 item serta nilai weight dan Data diambil dari penelitian sebelumnya .
Table 1 Data Knapsack Problem Item Weight Value Inisialisasi Populasi Pada populasi awal terdiri dari 6 kromosom yang dibentuk dari 10 item barang data knapsack problem pada tabel 3.
Kesepuluh item barang tersebut membentuk sebuah Jurnal METHODIKA.
Vol.
3 No.
1 MARET 2017 ISSN : 2442-7861
kromosom atau individu, dimana kromosom tersebut disusun dari beberapa gen yang berisi nilai.
Nilai gen ditentukan berdasarkan item barang yang dipilih atau Item barang yang dipilih diberi tanda 1 sedangkan item barang yang tidak dipilih diberi tanda 0.
Kedua tanda tersebut dapat direpresentasikan seperti pada gambar 3.
Tabel 2 Hasil pengujian pada 10 Individu dan 50 Pengujian Generasi Fitness Gambar 1 Representasi Kromosom Pada Knapsack Problem Nilai Fitness Nilai finess dapat dihitung dengan menjumlahkan nilai semua barang yang dipilih, tetapi dibatasi berat Nilai finess dan berat total dapat dihitung dengan menggunakan rumus:
F = Ocycuycn=1 ycaycn ycycn Gambar 2 Grafik pengujian untuk fitness .
Pada tabel 3.
1 terlihat bahwa nilai fitness dari setiap pengujian hasilnya berbeda, dan pengujian dilakukan sebanyak sepuluh kali.
Nilai fitness Wtot = Ocycuycn=1 ycaycn ycycn .
HASIL DAN PEMBAHASAN
Pada ditampilkan hasil pengujian two-point crossever pada algoritma genetika.
Penilaian dilakukan terhadap nilai maksimum yang didapat dan kecepatan menemukan solusi terbaik pada generasi keberapa.
Adapun hasil pengujian akan ditampilkan dalam bentuk tabel dan grafik.
Parameter yang digunakan untuk penerapan two-point crossover pada algoritma genetika adalah sebagai berikut.
tersebut mewakili jumlah item barang yang dapat dipilih untuk dimasukkan ke dalam knapsack .
Pada pengujian diatas nilai fitness tertinggi sebesar 900 pada generasi ke 77, sedangkan nilai fitness terendah terdapat pada generasi ke 55 sebesar 615.
Jumlah Individu = 10, 20, dan 50 Batas Generasi = 50, 80 dan 100 Probabilitas persilangan = 0.
Gambar 3 Grafik pengujian untuk generasi Berdasarkan nilai fitness terbaik pada tabel 3.
yaitu sebesar 900 maka pada tabel 3.
2 ditampilkan proses pencarian fitness terbaik per generasi serta solusi.
Tabel 3.
2 Pencarian fitness terbaik per generasi Jurnal METHODIKA.
Vol.
3 No.
1 MARET 2017 ISSN : 2442-7861
Generasi Fitness 1 4 5 7 8 11 12 14 15 16 17 18 Tabel 4 Hasil Pengujian Solusi Crossover Fitness One-point Two-point (Item barang terpili.
Pada tabel 2 terlihat bahwa pencarian fitness terbaik terjadi pertama di generasi ke 25, meskipun generasi berikutnya bernilai fitness sama.
Solusi merupakan item-item barang yang dipilih pada knapsack.
Adapun contoh hasil perhitungan ditampilkan pada lampiran 1.
Gambar 4 Grafik fitness per generasi Pada tabel 4 terlihat bahwa hasil pengujian pada two-point crossover ada peningkatan nilai fitness atau nilai value item yang dapat dimasukkan ke dalam ransel .
napsack proble.
dibandingkan dengan one-point crossover.
KESIMPULAN
Berdasarkan pembahasan serta pengujian yang dilakukan pada penelitian ini, maka kesimpulan yang dapat diambil Dari hasil penelitian yang telah terlihat bahwa twopoint crossover lebih baik dibandingkan dengan onepoint crossover pada penelitian ini.
Hasil best fitness two-point crossover pada permasalahan knapsack adalah 900 sedangkan hasil best fitness one-point crossover pada penelitian sebelumnya adalah 877 dengan data yang sama .
REFERENSI