oleh pengguna sistem adalah node awal dan node tujuan pengguna. Lingkungan Pengembangan Sistem Implementasi Algoritme Genetika dalam bentuk web client menggunakan bahasa pemrograman PHP dan DBMS MySQL. Spesifikasi perangkat keras dan perangkat lunak komputer yang digunakan dalam penelitian ini sebagai berikut : · Perangkat keras : Prosesor AMD Turion X2 dual core CPU 2.0 GHz, Memori 2.5 GB DDR2, hardisk 160 GB, mouse. · Perangkat lunak : Microsoft Windows XP SP 2, XAMPP 1.7.1, PHP 5.2.6, Firefox 3.0.6, Notepad++ . HASIL DAN PEMBAHASAN Perancangan supply chain network dalam menentukan jalur distribusi optimum dengan menggunakan Algoritme Genetika diawali dengan pembentukan representasi peta jalan Kota Bogor ke dalam bentuk graf. Perancangan tersebut diimplementasikan dalam web client dengan tujuan mempermudah pengguna dalam menggunakan rancangan tersebut. Tampilan web client yang telah dibuat dapat dilihat pada Lampiran 4. Algoritme Genetika yang digunakan untuk menentukan rute optimum jalur distribusi ini terdiri atas beberapa tahapan, yaitu representasi kromosom, penentuan populasi awal, menghitung nilai fitness, proses elitisme, proses seleksi, crossover, mutasi dan evaluasi kriteria berhenti algoritme. Untuk tahapan representasi kromosom, dari dua metode representasi kromosom yang dicoba dipilih salah satu metode representasi kromosom yang paling tepat. Dari percobaan yang dilakukan sebelumnya dalam penelitian ini menunjukkan bahwa metode Binary Encoding and Decoding membutuhkan waktu eksekusi program yang lebih lama daripada metode representasi kromosom Priority-based Encoding and Decoding. Oleh karena itu, metode Prioritybased Encoding and Decoding lebih tepat untuk merepresentasikan masalah yang dihadapi ke dalam bentuk kromosom sehingga penelitian ini menggunakan representasi kromosom dengan metode Priority-based Encoding and Decoding. Algoritme Genetika memerlukan pemilihan parameter yang tepat agar dapat memaksimalkan kinerja algoritme tersebut. Oleh karena itu tahap pengujian dalam penelitian ini terdiri atas dua kali percobaan. Percobaan pertama adalah menentukan
parameter optimal Algoritme Genetika. Percobaan kedua adalah menguji hasil keluaran sistem Algoritme Genetika berbasis web. Percobaan 1 Percobaan ini bertujuan menentukan parameter Algoritme Genetika yang paling optimal, yang terdiri atas pengujian parameter ukuran populasi, crossover probability, mutation probability, dan stall generation. Percobaan dilakukan dengan pengulangan masing-masing 10 kali dan untuk setiap percobaan node awal dan node tujuan ditetapkan masing-masing secara berurutan yaitu Node 21 dan Node 24. Percobaan untuk menentukan parameter ukuran populasi yang optimal dilakukan dengan cara mengubah nilai parameter ukuran populasi, sedangkan parameter yang lain dibuat tetap. Percobaan untuk menentukan parameter optimal crossover probability, mutation probability, dan stall generation dilakukan dengan cara yang sama dan parameter bukan uji dibuat tetap. Dalam menentukan parameter optimal ukuran populasi, parameter Algoritme Genetika yang terdiri atas crossover probability, mutation probability, dan stall generation nilainya dibuat tetap, secara berurutan yaitu 0.5, 0.1, dan 5. Nilai parameter ukuran populasi yang akan diuji adalah 50, 100 , 150, 200, 250, 300, 350, dan 400. Pengujian akan dilakukan masing-masing sebanyak 10 kali pengulangan. Hasil pengujian dapat dilihat pada Lampiran 5. Parameter ukuran populasi yang optimal didapatkan dengan memilih nilai ukuran populasi yang memiliki nilai fitness rata-rata paling kecil sehingga akan menghasilkan rute yang paling optimum. Parameter dan hasil uji dapat dilihat pada Tabel 2. Tabel 2 Parameter ukuran populasi dengan nilai fitness rata-rata. Ukuran Populasi
Crossover Probability = 0.5 Mutation Probability = 0.1 Stall Generation = 5
50
4580.6
100
4474.2
150
4350.6
200
4254.1
250
4312.1
300
4150
350
4150
400
4150 10
Pada Gambar 11 dapat dilihat hubungan parameter ukuran populasi dengan rata-rata nilai fitness.
Nilai parameter crossover probability yang akan diuji adalah 0.5, 0.6, 0.7, 0.8, dan 0.9. Ukuran populasi yang digunakan dalam pengujian ini adalah 300 kromosom yang merupakan ukuran populasi optimal berdasarkan hasil percobaan sebelumnya. Hasil pengujian dapat dilihat pada Lampiran 6. Parameter dan hasil uji dapat dilihat pada Tabel 3. Tabel 3 Parameter crossover probability dengan nilai fitness rata-rata. Crossover Probability
Ukuran Populasi = 300 Mutation Probability = 0.1 Stall Generation = 5
0.5
4150
0.6
4150
Gambar 11 Hubungan Ukuran Populasi dan Nilai Fitness Rata-Rata.
0.7
4150
0.8
4150
Dari Gambar 11 dapat dilihat kecenderungan bahwa semakin besar ukuran populasi akan menghasilkan nilai fitness ratarata yang sama atau semakin kecil. Ukuran populasi yang menghasilkan nilai fitness ratarata paling kecil adalah 300, 350, dan 400 kromosom dengan nilai fitness rata-rata 4150. Namun untuk memilih nilai ukuran populasi yang lebih baik untuk digunakan adalah dilihat dari hubungan ukuran populasi dengan waktu eksekusi program. Pada Gambar 12 diperlihatkan hubungan nilai ukuran populasi dengan waktu eksekusi program. Pada Gambar 12 dapat dilihat bahwa semakin besar nilai ukuran populasi maka waktu eksekusi yang diperlukan akan semakin lama, sehingga hasil pengujian menunjukkan bahwa parameter ukuran populasi yang optimal adalah 300 kromosom.
0.9
4150
Pada Gambar 13 diperlihatkan hubungan parameter crossover probability dengan nilai fitness rata-rata. Pada Gambar 13 dapat dilihat bahwa untuk setiap nilai crossover probability akan menghasilkan nilai fitness rata-rata yang sama.
Gambar 13 Hubungan Crossover Probability dan Nilai Fitness.
Gambar 12 Hubungan Ukuran Populasi dan Waktu Eksekusi Program.
Hal ini memperlihatkan bahwa semua nilai crossover probability tersebut menghasilkan nilai rata-rata fitness optimum, namun untuk memilih nilai crossover probability yang lebih baik untuk digunakan adalah dilihat dari hubungan antara nilai crossover probability dengan akhir generasi yang dihasilkan yang dapat dilihat pada Gambar 14.
11
Pada Gambar 15 dapat dilihat hubungan parameter mutation probability dengan nilai fitness rata-rata.
Gambar 14 Hubungan Crossover Probability dan Akhir Generasi. Gambar 14 diperlihatkan semua nilai crossover probability yang menghasilkan nilai fitness rata-rata sama. Dari nilai crossover probability ini dapat dilihat perbedaan akhir generasi yang dihasilkan. Akhir generasi ini memperlihatkan penggunaan crossover probability, semakin besar akhir generasi yang didapatkan untuk menghasilkan rute optimum maka crossover probability yang menghasilkan akhir generasi tersebut akan semakin baik digunakan. Hasil pengujian menunjukkan bahwa parameter crossover probability yang optimal adalah 0.6. Nilai parameter mutation probability yang akan diuji adalah 0.1, 0.2, 0.3, 0.4, 0.5, dan 0.6. Parameter ukuran populasi dan crossover probability yang digunakan dalam pengujian ini secara berurutan adalah 300 dan 0.6 yang merupakan parameter optimal berdasarkan hasil percobaan sebelumnya. Hasil pengujian dapat dilihat pada Lampiran 7. Parameter dan hasil uji dapat dilihat pada Tabel 4.
Gambar 15 Hubungan Mutation Probability dan Nilai Fitness. Dari Gambar 15 dapat dilihat bahwa nilai mutation probability 0.1, 0.2, 0.3, 0.4, 0.5, dan 0.6 menghasilkan nilai fitness rata-rata yang sama sehingga dari hubungan ini tidak bisa ditentukan nilai parameter mutation probability optimal. Penentuan parameter mutation probability yang lebih baik untuk digunakan adalah dilihat dari hubungan antara nilai mutation probability dengan akhir generasi yang dihasilkan. Hubungan parameter mutation probability dengan akhir generasi rata-rata dapat dilihat pada Gambar 16.
Tabel 4 Parameter mutation probability dengan nilai fitness rata-rata. Mutation Probability
Ukuran Populasi = 300 Crossover Probability = 0.6 Stall Generation = 5
0.1
4150
0.2
4150
0.3
4150
0.4
4150
0.5
4150
0.6
4150
Gambar 16 Hubungan Mutation Probability dan Akhir Generasi. Pada Gambar 16 ditunjukkan semua nilai mutation probability yang menghasilkan nilai fitness rata-rata sama. Dari nilai-nilai mutation probability ini dapat dilihat perbedaan akhir generasi yang dihasilkan. Akhir generasi ini 12
memperlihatkan penggunaan mutation probability, semakin besar akhir generasi yang didapatkan untuk menghasilkan rute optimum maka mutation probability yang menghasilkan akhir generasi tersebut akan semakin baik digunakan. Hasil pengujian menunjukkan bahwa parameter mutation probability yang optimal adalah 0.5.
Dari Gambar 17 dapat dilihat bahwa semua nilai stall generation menghasilkan nilai fitness yang sama. Oleh sebab itu hubungan ini tidak bisa digunakan untuk menentukan parameter stall generation yang lebih baik untuk digunakan. Penentuan parameter stall generation ditentukan oleh waktu eksekusi program.
Nilai parameter stall generation yang akan diuji adalah 5, 10, 15, dan 20. Parameter ukuran populasi, crossover probability dan mutation probability yang digunakan dalam pengujian ini secara berurutan adalah 300, 0.6, dan 0.5 yang merupakan parameter optimal berdasarkan hasil percobaan sebelumnya. Salah satu kriteria berhenti Algoritme Genetika adalah apabila nilai fitness tidak mengalami perubahan selama generasi yang ditentukan yang disebut dengan stall generation. Hasil pengujian dapat dilihat pada Lampiran 8. Parameter dan hasil uji dapat dilihat pada Tabel 5.
Pada Gambar 18 ditunjukkan hubungan parameter stall generation dengan waktu eksekusi. Semakin besar nilai parameter stall generation yang digunakan maka akan menghasilkan waktu eksekusi program yang lebih lama. Hasil pengujian menunjukkan bahwa parameter stall generation yang optimal adalah 5, karena dengan menggunakan nilai parameter stall generation yaitu 5 hanya akan membutuhkan waktu eksekusi program rata-rata sebesar 3 detik.
Tabel 5 Parameter stall generation dengan nilai fitness rata-rata. Stall Generation
Ukuran Populasi = 300 Crossover Probability = 0.6 Mutation Probability = 0.5
0.1
4150
0.2
4150
0.3
4150
0.4
4150
0.5
4150
0.6
4150
Gambar 18 Hubungan Stall Generation dan Waktu Eksekusi. Percobaan 2
Hubungan parameter stall generation dengan nilai fitness rata-rata dapat dilihat dalam Gambar 17.
Gambar 17 Hubungan Stall Generation dan Nilai Fitness.
Algoritme Genetika ini diimplementasikan dalam sebuah web client dengan menggunakan parameter optimal yang telah didapatkan yaitu parameter ukuran populasi, crossover probability, mutation probability, dan stall generation secara berurutan adalah 300, 0.6, 0.5, dan 5. Pada percobaan ini akan dilakukan pengujian rute distribusi optimum yang dihasilkan dari sistem berbasis web. Input yang dimasukkan oleh pengguna sistem adalah node awal dan node tujuan pengguna. Pada percobaan ini, node awal yang dipilih adalah Node 21, sedangkan node tujuan yang dipilih adalah Node 42. Rute dari Node 21 menuju Node 42 dapat dilewati melalui beberapa alternatif rute. Beberapa alternatif rute tersebut secara berurutan dapat dilihat pada Gambar 19, Gambar 20, Gambar 21, Gambar 22, Gambar 23, Gambar 24. 13
Gambar 19 Rute Alternatif 1.
Gambar 23 Rute Alternatif 5.
Gambar 20 Rute Alternatif 2.
Gambar 24 Rute Alternatif 6. Pada Tabel 6 dapat dilihat jarak tempuh, waktu tempuh rata-rata, dan nilai fitness yang dihasilkan dengan menggunakan perhitungan secara manual dari masing-masing gambar di atas. Tabel 6 Jarak tempuh, waktu tempuh rata - rata, dan nilai fitness.
Gambar 21 Rute Alternatif 3.
Gambar 22 Rute Alternatif 4.
Alternatif Rute
Jarak (meter)
Waktu RataRata (detik)
Nilai Fitness
Rute 1
1189
603
3006.5
Rute 2
1434
202
1473
Rute 3
1217
492
2576.5
Rute 4
1422
616
3175
Rute 5
1586
456
2617
Rute 6
1921
535
3100.5
Dari Tabel 6 dapat dilihat bahwa rute yang paling optimum adalah rute alternatif 2, yaitu Node 21 – 35 – 14 – 15 – 27 – 28 – 42. Rute ini memiliki nilai fitness terkecil sehingga dianggap merupakan rute paling optimum. 14
Rute optimum antarnode sebagai representasi dari jalur distribusi yang dihasilkan oleh sistem berbasis web dengan node awal adalah Node 21 dan node akhir adalah Node 42 sebagai berikut : Rute : Node 21 - Node 35 - Node 14 - Node 15 - Node 27 - Node 28 - Node 42. Jalan yang dilalui : Kapten Muslihat - Kapten Muslihat - Ir.H.Juanda Ir.H.Juanda - Sudirman Sudirman. Jarak tempuh : 1434 meter. Waktu tempuh rata-rata : 202 detik. Tampilan sistem yang menghasilkan rute optimum ini dapat dilihat pada Lampiran 9. Rute optimum yang dihasilkan oleh sistem berbasis web sama dengan rute optimum yang dihasilkan dengan perhitungan secara manual di atas. Hal ini menunjukkan bahwa sistem berbasis web tersebut berjalan dengan baik. KESIMPULAN DAN SARAN Kesimpulan Berdasarkan hasil penelitian beberapa kesimpulan, yaitu :
hubungan crossover probability dan mutation probability dengan akhir generasi algoritme. 5. Hubungan stall generation dengan nilai fitness rata-rata tidak bisa digunakan untuk menentukan nilai parameter stall generation yang paling optimum, sehingga digunakan hubungan stall generation dengan waktu eksekusi program. Saran Beberapa saran yang dapat dilakukan untuk penelitian berikutnya, yaitu: 1. Mengembangkan sistem ini dengan mengakomodasi masalah kepadatan lalu lintas dengan membedakan antara waktu sibuk dan waktu tidak sibuk. 2. Mengembangkan visualisasi yang baik untuk sistem penentuan rute optimum ini. 3. Mempercepat proses eksekusi program Algoritme Genetika dengan memanfaatkan Algoritme Genetika parallel. DAFTAR PUSTAKA
didapat
Ayers B. 2001. Handbook of Supply Chain Management. USA : st.Lucie Press.
1. Perancangan supply chain network dalam menentukan rute optimum jalur distribusi yang dilakukan dengan menggunakan Algoritme Genetika dan diimplementasikan dalam bentuk web client sudah dapat berjalan dengan baik.
Gen M, Cheng R. 2000. Genetic Algorithm and Engineering Optimization. Canada. John Wiley & Sons, Inc.
2. Kinerja Algoritme Genetika dalam penelitian ini yang bertujuan menentukan rute optimum jalur distribusi dalam supply chain network dengan menggunakan data peta jalan Kota Bogor akan mencapai optimal pada kombinasi nilai parameter untuk ukuran populasi, crossover probability, mutation probability, dan stall generation secara berurutan adalah 300, 0.6, 0.5 dan 5. 3. Hubungan jumlah kromosom dengan nilai fitness rata-rata tidak bisa digunakan untuk menentukan nilai parameter ukuran populasi yang paling optimum, sehingga digunakan hubungan jumlah kromosom dan waktu eksekusi program. 4. Hubungan crossover probability dan mutation probability dengan nilai fitness rata-rata tidak bisa digunakan untuk menentukan nilai parameter crossover probability dan mutation probability yang paling optimum, sehingga digunakan
Gen M, Cheng R. 2008. Network Models and Optimization. London. Springer-Verlag London. Goldberg D. 1989. Genetic Algorithms in Search, Optimization, and Machine Learning. England : Addison-Wesley Publishing Company. Hugos M. 2003. Essentials of Supply Chain Management. Canada : John Wiley & Sons, Inc. Priasa A. 2008. Perancangan Supply Chain Network Untuk Penentuan Lokasi Produksi dan Jalur Distribusi [skripsi]. Bogor. Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Sivanandam S, Deepa S. 2008. Introduction to Genetic Algorithms. New York. Springerverlag Berlin Heidelberg. Suyanto. 2005. Algoritma Genetika Dalam Matlab. Yogyakarta : Andi. Thiang, dkk. 2001. Implementation of Genetic Algorithm on MCS51 Microcontroller for 15
