Gambar 4 Proses Swap Mutation. 8. Evaluasi Solusi dan Kriteria Berhenti Proses evaluasi solusi ini akan mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom sampai terpenuhi kriteria berhenti. Apabila kriteria berhenti belum terpenuhi maka akan dibentuk lagi generasi yang baru dengan mengulangi langkah inisialisasi populasi. Beberapa kriteria berhenti yang sering digunakan dalam Algoritme Genetika antar lain: · Berhenti pada maksimum generasi tertentu. · Berhenti apabila dalam n generasi berikut tidak didapatkan nilai fitness yang lebih tinggi/rendah (stall generation). Kromosom-kromosom yang memiliki nilai fitness yang baik akan memiliki peluang yang lebih tinggi untuk terseleksi. Setelah dilakukan beberapa kali proses generasi, Algoritme Genetika akan menunjukkan kromosomkromosom yang terbaik, yang diharapkan merupakan solusi optimal atau mendekati optimal dari masalah yang dihadapi. METODE PENELITIAN Penelitian ini akan dikerjakan dalam beberapa tahap. Tahap-tahap tersebut disesuaikan dengan metode penelitian yang dapat dilihat pada Gambar 5. Studi Pustaka Dalam tahap ini, kegiatan yang dilakukan adalah mengumpulkan semua informasi atau literatur yang terkait dengan penelitian. Informasi tersebut akan didapatkan dari textbook, jurnal, buku, internet, dan artikel yang membahas tentang Algoritme Genetika dalam menyelesaikan masalah pencarian rute optimum. Selain mencari literatur terkait dengan Algoritme Genetika, literatur yang juga akan dicari yaitu terkait dengan cara dan tutorial pembuatan web client. Literatur-literatur yang digunakan dapat dilihat pada bagian daftar pustaka.
Gambar 5 Metodologi Penelitian. Perumusan Masalah Menentukan rute optimum jalur distribusi dengan menggunakan Algoritme Genetika. Penyelesaian masalah untuk menentukan rute optimum jalur distribusi ini akan sulit dan lama jika dilakukan secara manual. Algoritme Genetika digunakan sebagai cara untuk memecahkan masalah tersebut sehingga diharapkan rute optimum jalur distribusi dapat dicari dengan waktu yang lebih cepat. Pembentukan Data Data yang akan digunakan dalam penelitian ini adalah data peta jalan Kota Bogor. Data peta tersebut akan diubah ke dalam bentuk node dan edge yang merepresentasikan jalur distribusi. Node adalah titik persimpangan jalan sedangkan edge menyatakan ruas jalan yang ada. Pembentukan node dan edge dapat dilihat pada Gambar 6. Dari gambar tersebut terlihat bahwa node 1 menghubungkan dua jalan yaitu jalan Jalak Harupat dan jalan Pangrango, sedangkan node 2 akan menghubungkan jalan Pajajaran dengan jalan Jalak Harupat. Edge yang 5
menghubungkan antara node 1 dan node 2 dinamakan Jalak Harupat.
a) Representasi Kromosom dengan Metode Binary Encoding and Decoding. Pada proses encoding, metode Binary Encoding and Decoding ini menggunakan representasi kromosom dalam bentuk bit string. Panjang kromosom dipengaruhi oleh jumlah node. Dari data yang ada terdapat 44 node. Oleh sebab itu panjang kromosom dinyatakan dalam 44 gen. Sebagai contoh dari representasi kromosom yang dihasilkan adalah sebagai berikut : 01100101000010000101011101000101011101 011011.
Gambar 6 Peta Jalan Kota Bogor (http://maps.google.com). Semua data yang dibutuhkan antara lain data node, data edge, data jarak antar node, data waktu antar node, titik asal dan titik tujuan. Data jarak antar node didapatkan dari penelitian Priasa (2008), sedangkan data waktu antar node didapatkan melalui survei di lapangan. Data waktu yang digunakan ini merupakan data waktu rata-rata dari tiga kali penghitungan waktu. Data node yang merupakan representasi dari peta jalan Kota Bogor selengkapnya dapat dilihat dalam Lampiran 1. Data edge secara lengkap dapat dilihat dalam Lampiran 2. Representasi peta jalan Kota Bogor dalam bentuk graf secara lengkap dapat dilihat dalam Lampiran 3. Pengembangan Sistem Pengembangan sistem mengikuti tahapan yang ada dalam Algoritme Genetika yaitu representasi kromosom, penentuan populasi awal, menghitung nilai fitness, proses elitisme, proses seleksi, proses crossover, proses mutasi, evaluasi dan kriteria berhenti. 1. Representasi Kromosom Dalam penelitian ini representasi kromosom menggunakan dua metode, yaitu Binary Encoding and Decoding dan Priority-based Encoding and Decoding. Encoding merupakan proses untuk menerjemahkan masalah ke dalam bentuk kromosom, sedangkan decoding merupakan proses untuk membangkitkan rute dari kromosom yang dihasilkan dari proses encoding. Dari dua metode representasi yang digunakan dipilih salah satu metode representasi kromosom yang paling tepat.
Kromosom di atas dibangkitkan secara acak. Kromosom ini selanjutnya akan dipotong tiap dua gen. Proses pemotongan kromosom dapat dilihat sebagai berikut : 01|10|01|01|00|00|10|00|01|01|01|11|01|00|01|01| 01|11|01|01|10|11. Pada proses decoding, kromosom dikonversi ke dalam bentuk percabangan, sesuai dengan nilai desimal dari kromosom yang sebelumnya sudah dilakukan pemotongan. Sebagai contoh pada Gambar 7.
Gambar 7 Contoh Representasi Graf Peta Jalan (Thiang dkk 2001 ). Gambar di atas memperlihatkan ada 8 node, maka jumlah gen yang akan digunakan adalah 8 gen. Pada proses decoding kromosom ini, representasi kromosom akan dikonversi ke dalam bentuk biner sehingga untuk nilai 0, 1, 2, dan 3 secara berurutan akan menjadi 00, 01, 10, 11. Misalkan salah satu contoh representasi kromosom yang dihasilkan adalah 00101010, maka representasi kromosom tersebut akan dikonversi menjadi 0222. Rute ditentukan berdasarkan cabang yang ada. Sebagai contoh pada Gambar 7, misal node awalnya adalah 1, dan setelah mengalami decoding kromosom dihasilkan cabang 0222. Proses penentuan rute adalah sebagai berikut : Cabang : 0 2 2 2 Rute : 1 à 2 à 3 à 4 à 5.
6
b) Representasi Kromosom dengan Metode Priority-based Encoding and Decoding. Pada proses encoding, metode ini mengkategorikan kromosom dalam dua faktor, yaitu locus dan allele. Locus menyatakan posisi gen dalam kromosom, sedangkan allele menyatakan nilai dari gen. Dalam metode ini, posisi gen digunakan untuk menyatakan ID node sedangkan nilai dari gen menyatakan prioritas node yang akan digunakan pada proses decoding. Ilustrasi proses encoding dapat dilihat pada Gambar 8.
Gambar 8 Ilustrasi Proses Encoding Kromosom. Posisi gen (lokus) 1 menyatakan node ID 1 dengan prioritas 11, posisi gen 2 menyatakan node ID 2 dengan prioritas 1, posisi gen 3 menyatakan node ID 3 dengan prioritas 10 dan seterusnya. Representasi kromosom yang digunakan dalam penelitian ini adalah berbentuk integer. Panjang kromosom dipengaruhi oleh jumlah node. Dari data yang ada terdapat 44 node, Oleh sebab itu panjang kromosom dinyatakan dalam 44 gen. Kromosom yang dihasilkan terdiri atas gen yang berbentuk integer dengan nilai 1 sampai 44 yang dibangkitkan secara acak. Pseudocode untuk membangkitkan kromosom secara acak adalah sebagai berikut : Prosedur : Priority-based Encoding Input : Jumlah node (n) Output : kromosom (v) Mulai for i=1 hingga n v[i] ß i; for i=1 hingga [n/2] ulangi j ß random[1,n]; l ß random[1,n]; if j != l swap(v[j],v[l]); output v; akhir
Sebagai contoh dari representasi kromosom yang dihasilkan adalah sebagai berikut : 4 21 5 12 39 6 3 38 16 29 10 1 18 7 25 43 19 17 37 34 2 44 22 20 31 26 23 14 36 35 24 13 40 41 42 27 32 33 9 15 28 8 11 30. Pada proses decoding, kromosom yang telah dihasilkan akan diubah ke dalam bentuk rute distribusi. Untuk menentukan rute digunakan prioritas gen. Sebagai contoh pada Gambar 9.
Gambar 9 Contoh Representasi Peta Jalan Dalam Bentuk Graf. Dari gambar di atas misalkan node awal adalah 1, maka node berikutnya yang mungkin dituju adalah node 2, 3, dan 4. Kemudian misalkan kromosom yang dihasilkan adalah seperti pada Gambar 8, dapat dilihat bahwa prioritas node 2, 3 dan 4 secara berurutan adalah 1, 10, dan 3. Node 3 memiliki prioritas paling besar sehingga node berikutnya yang akan dipilih adalah node 3. Node berikutnya yang mungkin dipilih dari node 3 adalah node 4, 6, dan 7. Node 6 memiliki prioritas paling besar sehingga node berikutnya yang terpilih adalah node 6 dan seterusnya. Proses decoding dilakukan hingga mencapai gen terakhir atau proses ini akan berhenti jika node tujuan telah dicapai. Ilustrasi proses decoding ini dapat dilihat dalam Gambar 10.
Gambar 10 Ilustrasi Proses Decoding Kromosom. Pseudocode proses decoding adalah sebagai berikut: Prosedur : Priority-based Encoding Input : jumlah node (n), kromosom (v), node tetangga dengan node i (s), node awal (i) dan node tujuan (k). Output : rute (p) Mulai v(i) ß 0; j’ ß maxPrioritas(v[j], j€s) Jika j’ != k Jika j’ != 0 v[j’] ß 0; p ß j’; i ß j’; Lainnya p ß j’; Selesai Akhir.
7
2. Penentuan Populasi Awal Populasi merupakan kumpulan kromosom yang merupakan alternatif solusi. Hasil dari tahap representasi kromosom adalah sebuah kromosom yang terdiri atas 44 gen. Ukuran populasi adalah jumlah kromosom yang ada dalam satu populasi. Dalam penelitian ini ukuran populasi yang digunakan adalah 300 kromosom. Sehingga dari proses encoding akan dihasilkan sebuah array dua dimensi berukuran 300 x 44, jumlah baris dalam array ini menunjukkan banyaknya kromosom dan jumlah kolom menunjukkan banyaknya gen. Setelah proses decoding, dilakukan evaluasi dengan memilih kromosom yang valid yaitu kromosom yang mengandung node tujuan sehingga populasi awal yang dihasilkan terdiri atas kromosom mengandung informasi node tujuan. 3. Menghitung Nilai Fitness · Hitung Jarak dan Waktu Mekanisme penghitungan jarak dan waktu sesuai dengan rute distribusi yang dilalui, dimulai dari node awal hingga mencapai node tujuan. Jarak dan waktu yang dihasilkan akan digunakan untuk mencari nilai fitness kromosom. · Menghitung Nilai Fitness Kromosom Penelitian ini akan menentukan rute optimum yang dipengaruhi oleh jarak terdekat dan waktu tercepat. Oleh karena itu, fungsi fitness yang akan digunakan dalam penelitian ini ditunjukkan dalam Persamaan 1. (1) , f(x,t) adalah fungsi fitness. j adalah jumlah hop yang diperlukan hingga mencapai titik tujuan, (hop adalah proses perpindahan dari satu titik ke titik lain yang merupakan tetangganya). x adalah jarak antar titik, t adalah waktu antar titik, v adalah kecepatan konstan, %D adalah bobot persentase untuk jarak, dan %W adalah bobot persentase untuk waktu. Optimasi yang diinginkan dalam penelitian ini adalah mencari waktu dan jarak paling minimal, berarti kromosom yang terseleksi adalah kromosom dengan nilai fitness yang terkecil. Metode yang digunakan adalah roulette-wheel, yaitu metode dimana peluang tiap kromosom untuk terpilih adalah sebanding dengan nilai fitness-nya. Artinya semakin besar nilai fitness-nya maka akan semakin besar
peluang untuk terseleksi. Oleh karena itu fungsi fitness-nya akan dibentuk seperti Persamaan 2. ,
(2)
Dengan fn adalah nilai fitness sebelumnya, fn’ adalah nilai fitness baru, fmax adalah nilai fitness maksimum, dan fmin adalah nilai fitness minimum. 4. Proses Elitisme Kromosom terbaik akan bertahan untuk generasi selanjutnya. Supaya kromosom terbaik tidak rusak karena proses algoritme maka dilakukan elitisme. Caranya adalah Jika jumlah populasi genap maka elitisme dalam penelitian ini dilakukan dengan meng-copy dua buah kromosom yang memiliki nilai fitness terbaik. Jika jumlah populasi ganjil maka hanya mengcopy satu buah kromosom yang memiliki nilai fitness terbaik. 5. Proses Seleksi Kromosom Metode yang digunakan adalah roulettewheel, yaitu metode dimana peluang tiap kromosom untuk terpilih adalah sebanding dengan nilai fitness-nya. Artinya semakin besar nilai fitness-nya maka akan semakin besar peluang untuk terseleksi. Pertama, dibuat interval nilai kumulatif (dalam interval [0,1]) dari nilai fitness dibagi total nilai fitness dari semua kromosom. Sebuah kromosom akan terpilih jika bilangan random yang dibangkitkan berada dalam interval kumulatifnya. 6. Proses Crossover Metode crossover yang digunakan dalam penelitian ini adalah weight mapping crossover (WMX). WMX merupakan perluasan dari mekanisme single point crossover dimana hanya ada satu titik potong. Proses penentuan titik potong dilakukan secara acak. Tidak semua kromosom yang akan mengalami crossover, banyaknya kromosom yang akan mengalami crossover ditentukan oleh crossover probability. Kromosom yang memiliki nilai random lebih kecil dari crossover probability maka kromosom tersebut akan mengalami crossover. Ilustrasi proses WMX dapat dilihat dalam Gambar 3. Dalam penelitian ini proses WMX dilakukan dalam 4 langkah yaitu : 1. Memilih titik potong dari dua kromosom hasil seleksi. Pemilihan titik potong ini dilakukan secara acak. Misalkan titik potong yang didapat adalah 40. kromosom induk akan dilakukan crossover 8
pada gen ke-41. Contoh kromosom induk adalah sebagai berikut : Kromosom satu : 23 39 42 5 38 1 7 24 25 30 16 26 15 41 11 17 44 2 27 29 19 20 37 8 4 35 3 28 21 43 12 40 10 22 31 13 9 36 18 6 | 34 33 32 14 Kromosom dua : 41 33 30 7 39 10 14 25 42 17 18 11 27 21 44 31 37 8 43 23 35 16 28 22 19 38 4 13 3 9 32 2 12 34 40 1 29 20 15 5 | 26 36 6 24 2. Menggantikan substring antara kromosom induk. Setelah pemotongan pada gen ke-41 maka dilakukan penggantian nilai gen antara kromosom induk sehingga kromosom baru akan terbentuk sebagai berikut : Kromosom satu : 23 39 42 5 38 1 7 24 25 30 16 26 15 41 11 17 44 2 27 29 19 20 37 8 4 35 3 28 21 43 12 40 10 22 31 13 9 36 18 6 | 26 36 6 24
Kromosom dua baru : 41 33 30 7 39 10 14 25 42 17 18 11 27 21 44 31 37 8 43 23 35 16 28 22 19 38 4 13 3 9 32 2 12 34 40 1 29 20 15 5 36 26 24 6 7. Proses Mutasi Metode mutasi yang digunakan dalam penelitian ini adalah swap mutation. Tidak semua kromosom yang akan mengalami mutasi, banyaknya kromosom yang akan mengalami mutasi ditentukan oleh mutation probability. Kromosom yang memiliki nilai random lebih kecil dari mutation probability maka kromosom tersebut akan mengalam mutasi. Swap mutation akan memilih dua posisi gen secara acak dan kemudian dilakukan penggantian posisi. Misalkan posisi gen yang terpilih adalah 5 dan 42 maka proses swap mutation akan dilakukan sebagai berikut : 23 39 42 5 38 1 7 24 25 30 16 26 15 41 11 17 44 2 27 29 19 20 37 8 4 35 3 28 21 43 12 40 10 22 31 13 9 36 18 6 33 34 14 32
Kromosom dua :
Kromosom baru yang dihasilkan oleh proses swap mutation adalah :
41 33 30 7 39 10 14 25 42 17 18 11 27 21 44 31 37 8 43 23 35 16 28 22 19 38 4 13 3 9 32 2 12 34 40 1 29 20 15 5 | 34 33 32 14
23 39 42 5 34 1 7 24 25 30 16 26 15 41 11 17 44 2 27 29 19 20 37 8 4 35 3 28 21 43 12 40 10 22 31 13 9 36 18 6 33 38 14 32
3. Mapping nilai gen pada posisi yang sesuai.
8. Evaluasi dan Kriteria Berhenti
Setelah dilakukan penggantian substring dapat dilihat bahwa nilai gen 26, 36, 6 dan 24 muncul dua kali dalam kromosom satu. Hal yang sama juga dialami kromosom dua, sehingga harus dilakukan mapping nilai gen ke posisi yang sesuai dengan cara melakukan sorting. Mapping yang dihasilkan adalah sebagai berikut :
Dalam penelitian ini Algoritme Genetika akan berhenti jika memenuhi salah satu dari dua kriteria berhenti yaitu maksimum generasi dan stall generation. Dalam setiap generasi dilakukan proses evaluasi dengan menghitung nilai fitness dari setiap kromosom. Maksimum generasi yang ditentukan adalah 20 generasi, sehingga Algoritme Genetika akan berhenti jika sudah mencapai 20 generasi. Algoritme Genetika juga akan berhenti jika nilai fitness terbesar yang dihasilkan tidak berubah selama beberapa generasi (stall generation).
26 36 6 24 à
6
34 33 32 14 à
14 32 33 34
24 26 36
6
↔ 14
24 ↔ 32 26 ↔ 33 36 ↔ 34
4. Membangkitkan kromosom baru dengan menerapkan hubungan mapping. Kromosom baru yang dihasilkan dengan menerapkan hubungan mapping adalah sebagai berikut : Kromosom satu baru : 23 39 42 5 38 1 7 24 25 30 16 26 15 41 11 17 44 2 27 29 19 20 37 8 4 35 3 28 21 43 12 40 10 22 31 13 9 36 18 6 33 34 14 32
Pengujian dan Analisis Sistem Sistem Algoritme Genetika untuk menentukan rute distribusi optimum yang telah dihasilkan akan diimplementasikan dalam bentuk web client. Proses pengujian dan analisis sistem Algoritme Genetika akan dilakukan dalam dua tahap. Tahap pertama, pengujian sistem dilakukan dengan mengubah nilai parameter Algoritme Genetika yang digunakan, yaitu nilai crossover probability, nilai mutation probability, ukuran populasi dan stall generation. Tahap kedua, menguji rute distribusi optimum yang dihasilkan dari sistem berbasis web client. Input yang dimasukkan 9
