BAB 3 ANALISIS DAN PERANCANGAN PROGRAM
3.1
Analisis Permasalahan TSP merupakan suatu masalah klasik yang telah ada sejak tahun 1800-an, sejauh
ini telah cukup banyak metode yang diciptakan untuk menyelesaikan TSP. Dalam hal ini metode-metode yang bekerja secara heuristik dianggap lebih baik daripada metodemetode eksak karena dapat memberikan hasil yang mendekati optimal (bahkan pada kasus tertentu benar-benar optimal) dalam waktu yang sangat singkat, walaupun ukuran permasalahan yang dihadapi besar (n > 100). Algoritma genetik dan Tabu Search merupakan dua dari sekian banyak metode heuristik yang tersedia, yang bekerja sangat baik dalam penyelesaian kasus optimisasi pada TSP. Dalam hal ini metode-metode tersebut memiliki cakupan parameter yang sangat luas dan hampir tidak terhingga banyaknya, dalam skripsi ini akan dicari kombinasi yang terbaik dari parameter-parameter yang ada untuk menyelesaikan TSP. Arti kata terbaik di sini adalah menghasilkan nilai solusi yang terbaik (jarak yang terpendek, cepat dan hasil yang konsisten).
3.2
Perancangan Kebutuhan Data Data untuk program ini didapatkan dengan menggunakan program tambahan
untuk membuat file data TSP dari permasalahan TSP yang ingin diselesaikan. Data tersebut disimpan dalam format file teks dimana isi dari tiap variabel data dipisahkan oleh tab, seperti pada struktur sebagai berikut:
31
... Dalam hal ini merupakan posisi koordinat kota ke i (koordinat xi dan yi dimana nilai dari koordinat-koordinat tersebut berkisar antara 0 dan 480).
3.3
Perancangan Program Untuk perancangan program penyelesaian TSP, digunakan bahasa pemrograman
Java 6 SE yang bekerja di atas sistem operasi Microsoft Windows XP SP2.
3.3.1 Algoritma Genetik Dalam implementasinya, algoritma genetik membutuhkan populasi awal dengan anggota populasi yang beragam (nilainya diacak). Kemudian populasi ini akan dihitung nilai fitness-nya, dan diurutkan berdasarkan nilai fitness tersebut mulai dari yang terbesar hingga yang terkecil. Individu-individu yang terpilih sebagai individu-individu elit akan dipastikan masuk ke dalam populasi pada generasi berikutnya sedangkan individu-individu lain di dalam populasi kemudian diseleksi dengan menggunakan metode tournament untuk dimasukkan ke dalam mating pool, dimana semua individu di dalam populasi (termasuk individu-individu elit) tetap terkena seleksi.
32 Semua individu di dalam mating pool tersebut kemudian dikawinkan / disilangkan dengan menggunakan metode order crossover, untuk menghasilkan anakanak yang sama banyaknya dengan jumlah individu awal di dalam populasi. Kemudian sebagian dari anak-anak tersebut akan mengalami mutasi, hal ini dicapai dengan menggunakan metode swap. Semua anak yang dihasilkan dalam suatu generasi akan dihitung kembali nilai fitness-nya, untuk kemudian diurutkan mulai dari nilai fitness yang terbesar ke nilai fitness yang terkecil. Anak-anak tersebut akan dimasukkan ke dalam populasi untuk generasi berikutnya. Karena sudah terdapat beberapa individual elit di dalam populasi, maka untuk menjaga keseimbangan jumlah populasi (dan menuju pada perbaikan kualitas populasi secara keseluruhan) anak yang memiliki nilai fitness yang sangat rendah tidak akan masuk ke dalam populasi untuk generasi berikutnya.
Gambar 3.1
Algoritma genetik dengan elitisme
33 Secara garis besar terdapat empat proses utama di dalam implementasi algoritma genetik: 1.
Proses inisialisasi untuk pembuatan populasi awal.
2.
Proses perhitungan fitness dari populasi, dan populasi diurutkan berdasarkan nilai fitness yang terbesar ke yang terkecil.
3.
Proses pemilihan individu-individu elit untuk dimasukkan ke populasi pada generasi berikutnya.
4.
Proses pembuatan populasi baru berdasarkan populasi lama.
3.3.2
Tabu Search Proses optimisasi menggunakan tabu search dimulai dengan mengeset variabel
MAX-TRIES dan ITER untuk jumlah iterasi algoritma, yang dilanjutkan dengan membuat sebuah solusi awal secara acak. Solusi baru kemudian dicari berdasarkan neighborhood dari solusi lama dengan menggunakan algoritma 2-opt. Kemudian akan dipilih solusi baru yang terbaik dan valid dari neighborhood dipilih, proses pemilihan ini bersifat deterministik. Untuk menambahkan unsur non-deterministik ke dalam tabu search, dapat digunakan probabilitas untuk pemilihan solusi yang terbaik dan yang valid dari neighborhood. Kemudian memori tabu search diperbaharui untuk mendapatkan solusi baru, proses ini dilanjutkan sampai jumlah counter = ITER. Sehingga akan dihasilkan nilai yang bersifat local optima. Untuk membuat algoritma ini lebih tersebar, maka setelah local optima ditemukan maka solusi awal akan dibuat kembali secara acak untuk selanjutnya
34 melakukan pencarian solusi baru kembali sampai jumlah counter_total mencapai nilai MAX-TRIES. Secara garis besar ada lima proses utama di dalam algoritma genetik: 1.
Proses inisialisasi untuk pembuatan solusi awal
2.
Proses evaluasi rute untuk menentukan nilai dari solusi
3.
Proses pencarian solusi lain di dalam neighborhood solusi awal
4.
Proses penggantian solusi baru dengan menggunakan probabilitas jika solusi baru lebih baik dan memenuhi syarat.
5.
Proses pembaharuan memori
3.4
Perancangan Layar Program utama memiliki dua interface yang berbeda, command line interface
dan graphical user interface. Dalam hal ini command line interface dapat digunakan untuk kinerja sistem yang lebih baik, jika user tidak membutuhkan GUI ( Graphical User Interface ). Sedangkan GUI akan memudahkan user untuk menjalankan program utama, dengan sedikit penurunan kinerja GUI yang digunakan pada program utama terdiri dari tiga layar yaitu layar utama, layar hasil dan layar about. Sedangkan program tambahan untuk membuat TSP memiliki satu layar utama.
3.4.1
Layar Utama Layar utama ini digunakan sebagai TSP solver interface, dimana parameter-
parameter untuk algoritma genetik dan tabu search ditentukan di layar ini.
35
Gambar 3.2 Perancangan layar utama program Dalam layar ini terdapat informasi lokasi file TSP, parameter-parameter untuk algortima genetik (jumlah populasi, jumlah generasi, probabilitas persilangan, probabilitas mutasi dan persentasi elitisme) dan parameter-parameter untuk tabu search (nilai panjang memori, jumlah pencarian solusi baru, jumlah pembaharuan solusi dan probabilitas pemilihan solusi). Setelah semua informasi yang diperlukan diisi, user dapat menekan tombol Run untuk menyelesaikan masalah TSP yang telah dipilih oleh user. Hasil akan ditampilkan pada layar hasil.
3.4.2
Layar Hasil Layar hasil ini dirancang untuk menampilkan hasil penyelesaian TSP. Hasil
ditampilkan secara grafis, dan detail mengenai rute dan jarak yang ditempuh ditampilkan pada text box dibawah gambar rute.
36 Hasil Penyelesaian TSP
Algoritma Genetik
Tabu Search
Rute terpendek adalah 1-2-4-5-3 Jarak rute terpendek adalah 10
Rute terpendek adalah 1-2-4-5-3 Jarak rute terpendek adalah 10
Tutup
Gambar 3.3
3.4.3
Layar hasil penyelesaian TSP
Layar About Layar about dirancang untuk menampilkan hak cipta pembuatan program ini.
Gambar 3.4
Layar about
37 3.4.4
Layar Utama Program Pembuat TSP Layar utama dari program ini bertujuan untuk membuat masalah TSP, yang
dapat dibuat secara manual oleh user ataupun dibuat secara acak oleh program. Program Pembuat TSP
Randomize
Jumlah kota: 9
Gambar 3.5
Open File
Save File
Layar utama program pembuat TSP
Erase
38 Pada layar ini user dapat menentukan sendiri letak kota dengan cara mengklik pada layar, disamping juga memilih lokasi kota secara acak dengan menekan tombol Randomize dan memasukkan jumlah kota yang diinginkan. Setelah selesai membuat masalah TSP, user kemudian dapat menyimpan masalah TSP tersebut ke dalam suatu file dengan cara menekan tombol Save File. Selain itu file TSP yang telah ada, dengan cara menekan tombol Open File untuk membuka file TSP yang telah jadi.
3.5
Spesifikasi Proses / Pseudocode
3.5.1
Algoritma Genetik
3.5.1.1 Spesifikasi Proses Inisialisasi Algoritma Genetik Inisialisasi merupakan proses pemberian nilai awal untuk tiap parameter yang akan dipakai di dalam algoritma genetik. Nilai-nilai yang akan diinialisasi adalah file TSP yang akan diselesaikan, jumlah populasi, jumlah generasi, probabilitas persilangan, probabilitas mutasi dan persentase elitisme. Kemudian algoritma genetik akan menginisialisasi populasi awal dengan membuat individu-individu secara acak. Untuk membuat populasi awal, dilakukan langkah-langkah pseudocode berikut: Mulai Selama jumlah populasi sekarang belum sama dengan jumlah populasi total Lakukan Buat individu baru (nilai kromosom berurut dari 1 sampai dengan jumlah kota – 1)
39 Untuk individu i, selama x=0 sampai dengan panjang (kromosom-1) / 2 lakukan Buat nomor r1 dan r2 secara acak (0 < r1, r2 < 1) posisi1 Í r1 * panjang kromosom posisi2 Í r2 * panjang kromosom Elemen di dalam kromosom ditukar, (elemen di posisi1 ditukar dengan elemen di posisi2) Individu baru ini dimasukkan ke dalam populasi awal Akhir
3.5.1.2 Spesifikasi Proses Perhitungan Fitness dari Populasi Pada proses ini dilakukan perhitungan nilai fitness dari tiap individu di dalam populasi. Individu yang bagus (nilai fitness yang tinggi) adalah individu yang memiliki rute yang terpendek. Semakin besar jarak yang ditempuh pada satu rute, semakin rendah nilai fitness yang akan dimasukkan ke dalam individu. Pseudocode dari proses ini adalah sebagai berikut: Mulai Untuk tiap individu di dalam populasi lakukan Hitung Panjang_Rute_Individu Hitung nilai fitness. Fitness Í
Jumlah _ Kota* C , Panjang _ Rute _ Individu
dimana C merupakan konstan (C = 700) Masukkan nilai fitness dan panjang rute individu ke dalam individu
40 Urutkan populasi mulai dari individu dengan nilai fitness tertinggi ke terendah Jika individu yang terbaik untuk generasi ini lebih baik dari Individu Terbaik, maka Individu Terbaik Í individu terbaik untuk generasi ini Akhir Rumus fitness diatas digunakan untuk menghasilkan jumlah nilai fitness yang konstan dalam setiap generasi. Hal ini dimungkinkan karena program ini membatasi nilai koordinat-koordinat yang akan digunakan untuk membuat TSP. Nilai koordinat yang valid adalah mulai dari (0,0) sampai dengan (480,480). Nilai C sendiri merupakan nilai konstan, yaitu jarak terpanjang yang dapat ditempuh pada dua kota yang bernilai 480 2 + 480 2 ≈ 700 . Dengan demikian nilai fitness maksimal yang bisa diperoleh
adalah Jumlah_Kota*C.
3.5.1.3 Spesifikasi Pemilihan Individu-Individu Elit dari Populasi Proses ini akan memilih individu-individu yang elit untuk dimasukkan ke dalam populasi pada generasi selanjutnya. Cara kerja proses ini dinyatakan dalam pseudocode berikut: Mulai Jumlah_Elit Í persentasi elit * jumlah populasi Jika Jumlah_Elit = 0 dan persentasi elit > 0, maka Jumlah_Elit Í 1 Selama x Í 0 sampai x = Jumlah_Elit lakukan masukkan populasi(x) ke dalam Populasi_Elit Akhir
41 Jika jumlah elit adalah 0 dan persentase elit lebih besar dari 0, maka jumlah elit diset menjadi 1. Hal ini untuk memastikan bahwa terdapat minimal 1 individu elit (nilai persentase elitisme lebih besar dari 0) pada saat elitisme diaktifkan.
3.5.1.4 Spesifikasi Metode Seleksi Individu-individu akan diseleksi untuk dimasukkan ke dalam mating pool, yang dilakukan dengan menggunakan metode seleksi tournament. Metode ini bekerja dengan cara memilih k individu secara acak untuk kemudian mempertandingkan setiap pasangan dua individu yang memiliki probabilitas kemenangan p (sekitar 0.6-0.7) bagi individu yang memiliki nilai fitness yang lebih baik. Kemudian pemenang yang didapat akan ditandingkan lagi, sampai tinggal tersisa satu pemenang yang akan dimasukkan ke dalam mating pool. Pseudocode dari metode seleksi ini adalah sebagai berikut: Mulai Untuk i=0 sampai dengan i=k-1 lakukan r Í nilai acak (0 < r < 1) * jumlah populasi masukkan populasi(r) ke dalam Tournament_Population Untuk i=0 sampai dengan i=√k lakukan Untuk x=0 sampai dengan x=i dimana x=x+2(i+1), lakukan r Í nilai acak (0 < r < 1) Jika fitness Tournament_Population(x) > fitness Tournament_Population(x+2i) maka MAX Í x, MIN Í x+2i, sebaliknya jika tidak MAX Í x+2i, MIN Í x
42 Jika r < p maka Tournament_Population(x) ÍTournament_Population(MAX), sebaliknya jika tidak, maka Tournament_Population(x) Í Tournament_Population(MIN) Masukkan pemenang, yaitu Tournament_Population(0) ke dalam mating pool Akhir
3.5.1.5 Spesifikasi Metode Persilangan Persilangan adalah proses dimana individu-individu di dalam mating pool disilangkan / dikawinkan untuk menghasilkan anak-anak. Pada program ini metode persilangan yang digunakan adalah metode order, yang menyimpan urutan kota secara relatif. Berikut ini adalah cara kerja/pseudocode dari metode ini: Mulai Start Í nilai acak (0 < Start < 1) * panjang kromosom End Í nilai acak (0 < End < 1) * panjang kromosom Jika Start > End maka, nilainya ditukar Untuk i=Start sampai dengan i=End lakukan Kromosom_Anak(i) Í Kromosom_Parent1(i) j Í (End+1) modulus panjang kromosom Untuk i=0 sampai dengan i=(End-Start)+1 lakukan Selama Kromosom_Parent2(j) ada di dalam Kromosom_Anak maka j Í (j + 1) modulus panjang kromosom
43 Kromosom_Anak(i) Í Kromosom_Parent2(j) Buat individu baru dengan mengeset kromosom menjadi Kromosom_Anak Akhir
3.5.1.6 Spesifikasi Metode Mutasi Mutasi adalah metode yang bersifat exploit, yang berusaha untuk mendapatkan hasil yang optimal di daerah yang menjanjikan dengan melakukan perubahan pada elemen-elemen kromosom yang ada. Metode mutasi yang digunakan dalam program adalah metode swap, cara kerja dari metode ini adalah dengan memilih dua elemen di dalam kromosom secara acak, dan posisi diantara dua elemen ini diganti. Efek dari metode ini adalah menyimpan informasi elemen yang berdekatan, walaupun urutannya menjadi lebih berantakan. Pseudocode dari metode ini adalah sebagai berikut: Mulai Start Í nilai acak (0 < Start < 1) * panjang kromosom End Í nilai acak (0 < End < 1) * panjang kromosom Jika Start > End maka, nilainya ditukar Temp Í Kromosom_Anak(Start) Kromosom_Anak(Start) Í Kromosom_Anak(End) Kromosom_Anak(End) Í Temp Akhir
44 3.5.2 Tabu Search 3.5.2.1 Spesifikasi Proses Inisialisasi Inisialisasi merupakan proses pemberian nilai awal untuk tiap parameter yang akan dipakai di dalam tabu search. Nilai-nilai yang akan diinialisasi adalah file TSP yang akan diselesaikan, panjang memori, jumlah pencarian solusi baru, jumlah pembaharuan solusi dan probabilitas pemilihan solusi. Kemudian tabu search akan menginisialisasi sebuah solusi awal dengan membuat solusi (rute) secara acak. Untuk membuat solusi awal, dilakukan langkahlangkah seperti pada pseudocode berikut: Mulai Buat sebuah solusi baru (nilai array berurut dari 1 sampai dengan jumlah kota – 1) Selama x=0 sampai dengan panjang (array-1) / 2 lakukan Buat nomor r1 dan r2 secara acak (0 < r1, r2 < 1) posisi1 Í r1 * panjang array posisi2 Í r2 * panjang array Elemen di dalam array ditukar, (elemen di posisi1 ditukar dengan elemen di posisi2) Solusi Best Í solusi awal Akhir
45 3.5.2.2 Spesifikasi Proses Evaluasi dari Solusi Pada proses ini dilakukan pengevaluasian dari solusi (rute). Kemudian nilai evaluasi akan dimasukkan ke dalam solusi. Mulai Hitung Panjang_Rute_Solusi Masukkan nilai panjang rute solusi ke dalam solusi Akhir
3.5.2.3 Spesifikasi Proses Pencarian Solusi Baru Pada proses ini dilakukan pencarian solusi baru berdasarkan neighborhood pada solusi sebelumnya. Solusi baru Vn yang didapatkan merupakan solusi terbaik dari neighborhood solusi sebelumnya Vc dengan menggunakan algoritma 2-opt. Kemudian solusi baru Vn menggantikan solusi lama Vc dengan probabilitas yang ditentukan oleh user, jika nilai probabilitas adalah 1.0 maka tabu search akan menjadi algoritma yang deterministik. Setelah itu solusi Vc kemudian diperbaharui lagi dengan mencari solusi baru Vn sampai jumlah counter mencapai nilai ITER (jumlah pembaharuan solusi). Solusi yang terbaik saat ini masih bersifat lokal. Kemudian nilai counter_total dinaikkan dan solusi awal diciptakan lagi, diperbaharui dan proses tersebut diulang sampai nilai counter_total menjadi MAXTRIES. Hal ini dilakukan agar solusi yang didapatkan merupakan solusi yang tersebar, sehingga bisa mendapatkan nilai optimal yang global. Setelah semua solusi terbaik yang bersifat lokal terkumpul, maka solusi yang terbaik dari semua solusi lokal adalah solusi terbaik yang bersifat global. Pseudocode dari algoritma ini adalah sebagai berikut:
46 Mulai counter_total Í 0 Selama counter_total < MAX-TRIES Inisialisasi solusi Vc count Í 0 Selama count < ITER Cari solusi terbaik dan valid Vn dari neighborhood Vc Vc Í Vn dengan probabilitas yang ditentukan oleh user Jika Vc lebih baik dari local_best maka local_best Í Vc counter Í counter + 1 counter_total Í counter_total + 1 Jika local_best lebih baik global_best maka global_best Í local_best Akhir
3.5.2.4 Spesifikasi Proses Algoritma 2-opt Algoritma 2-opt digunakan untuk mencari solusi terbaik dengan cara memperbaiki solusi yang ada. Cara kerja algoritma ini sama dengan metode mutasi swap pada algoritma genetik, yaitu dengan memilih 2 elemen untuk kemudian menukar posisinya. Algoritma 2-opt tidak mencari seluruh permutasi dari sebuah solusi melainkan hanya sebagian kecil saja, karena elemen yang diubah hanyalah 2 elemen. Algoritma ini memiliki kompleksitas O(n2). Hal ini didapatkan berdasarkan cara kerja
47 algoritma ini yang melakukan perhitungan sebanyak C (n,2) =
n! kali. (2!*(n − 2)!)
Pseudocode dari algoritma 2-opt ini dinyatakan di bawah ini: Mulai Best Í Vc Selama x=0 sampai dengan x= C (n,2) =
n! (2!*(n − 2)!)
Selama y=jumlah kota sampai dengan y=x lakukan Buat solusi baru Vn Elemen_Solusi_Vn(y)ÍElemen_Solusi_Vc(x) Elemen_Solusi_Vn(x)ÍElemen_Solusi_Vc(y) Jika Vn lebih baik daripada Best, maka BestÍVn Akhir
