IMPLEMENTASI TRAVELLING SALESMAN PROBLEM (TSP) MENGGUNAKAN ALGORITMA GENETIK PADA GAME KALPATARU

rd

3 International Conference on e-Learning Bandung, November 23-24, 2011

IMPLEMENTASI TRAVELLING SALESMAN PROBLEM (TSP) MENGGUNAKAN ALGORITMA GENETIK PADA GAME KALPATARU #2

1

Tenia Wahyuningrum*1, Aciek Ida Wuryandari , Agung Harsoyo#3 * AKATEL Sandhy Putra Purwokerto, Jl. DI Panjaitan 128 Purwokerto # Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung Jalan Ganesa No. 10, Bandung 40132, Indonesia

[email protected], [email protected], [email protected]

ABSTRAK Makalah ini membahas tentang analisa pencarian solusi TSP pada penentuan rute pengumpulan sampah pada aplikasi permainan komputer yang disebut “Kalpataru”. Game Kalpataru adalah sebuah game pendidikan pengelolaan dan pemanfaatan sampah bagi komunitas CikapundungNet di Kota Bandung. Persoalan TSP merupakan persoalan optimasi untuk mencari perjalanan terpendek untuk mengambil sampah ke beberapa sumber sampah dan kembali ke Tempat Pembuangan Sementara (TPS) sebagai titik awal keberangkatan. Salah satu algoritma yang muncul untuk menyelesaikan persoalan ini ialah Algoritma Genetika. Dalam makalah ini akan dibahas proses seleksi, crossover dan mutasi dalam menghasilkan rute terbaik. Produk diimplementasikan menggunakan bahasa pemrograman Java. Hasil pengujian rute terbaik yang dilakukan dengan perhitungan manual dan melalui game menunjukkan bahwa algoritma telah berjalan sesuai dengan desain yang diharapkan. Kata kunci : Travelling Salesman Problem, Algoritma Genetika, proses seleksi, crossover, mutasi

1. PENDAHULUAN Game Kalpataru merupakan game yang dibuat untuk memberikan edukasi dan meningkatkan kesadaran masyarakat akan kebersihan lingkungan dan pengelolaan sampah, yang dilakukan melalui sebuah aplikasi simulasi berbentuk permainan maupun game. Game yang dinamakan Kelola samPah Tambah Rupiah (Kalpataru) merupakan game simulasi yang menggambarkan proses pengelolaan sampah, mulai dari pengumpulan sampah, sampai dengan daur ulang sampah. Penyusunan makalah ini bertujuan untuk menentukan rute terbaik pengumpulan dari sumber sampah ke Tempat Pembuangan Sementara (TPS). Dalam penerapan TSP, diperlukan solusi optimal, efektif dan juga efisien untuk mencapai hasil yang diinginkan. Masalah optimasi dalam makalah ini adalah masalah optimasi dalam pengumpulan sampah, dimana akan dicari rute terbaik dalam mengumpulkan sampah dari bakbak sampah warga ke Tempat Pembuangan Sementara (TPS). Beberapa metoda telah dikembangkan untuk memecahkan persoalan ini namun belum

ditemukan algoritma penyelesaian yang optimal. Salah satu algoritma yang muncul untuk menyelesaikan persoalan ini ialah Algoritma Genetika. Algoritma genetika (genetik) merupakan teknik pencarian optimasi yang terinspirasi dari genetika dan seleksi alam (teori evolusi Darwin). Algoritma ini digunakan untuk mendapatkan solusi yang tepat untuk masalah optimasi dari satu variabel atau multi variabel (Gen dan Cheng, 1997). 2. TINJAUAN PUSTAKA Travelling Salesman Problem (TSP) atau Persoalan Perjalanan Pedagang diilhami oleh masalah seorang pedagang yang akan mengunjungi sejumlah kota dengan jarak tertentu menentukan sirkuit terpendek yang harus dilalui oleh seorang pedagang bila pedagang itu berangkat dari sebuah kota asal dan menyinggahi setiap kota tepat satu kali dan kembali lagi ke kota asal keberangkatan. Terapan TSP yang muncul dalam kehidupan sehari-hari antara lain pengumpulan sampah dari beberapa sumber sampah yang terdapat dalam

rd


satu lingkup RW ke TPS. Standar TSP dapat dinyatakan secara matematis sebagai berikut. Metoda yang telah diketahui untuk memecahkan TSP secara optimal, adalah dengan menyebutkan satu persatu setiap kemungkinan tur dan pencarian tur dengan biaya terkecil. Setiap tur yang mungkin adalah permutasi 123…n dengan n merupakan jumlah kota, sehingga jumlah tur adalah n!. Ketika didapatkan nilai tur besar, maka tidak mungkin untuk menemukan biaya untuk setiap tur dengan polynomial waktu. Terdapat banyak motoda yang berbeda untuk optimasi yang digunakan untuk mencoba memecahkan TSP. Homaifar menyatakan satu pendekatan dengan menggunakan optimal solusi pada berbagai aplikasi TSP membutuhkan enumerasi dan evaluasi yang mendalam. Prosedur terdiri dari membangkitkan semua kemungkinan tur dan mengevaluasi jarak tur yang cocok. Tur dengan jarak terpendekmerupakan pilihan yang terbaik dengan jaminan optimal. 2.1 Algoritma Genetik pada TSP Algoritma genetik terinspirasi oleh teori Darwin tentang evolusi. Solusi untuk masalah yang dipecahkan dengan algoritma genetika adalah berevolusi. Algoritma dimulai dengan set solusi (diwakili oleh kromosom ) yang disebut populasi. Solusi dari satu populasi yang diambil dan digunakan untuk membentuk populasi baru. Hal ini didorong oleh harapan, bahwa penduduk baru akan lebih baik dari yang lama. Solusi yang dipilih untuk membentuk solusi baru (anak) yang dipilih sesuai dengan kelayakan yang lebih cocok dan lebih banyak kesempatan untuk bereproduksi. Hal ini diulangi sampai beberapa kondisi mendapatkan hasil yang memuaskan (misalnya jumlah populasi atau peningkatan solusi yang terbaik). 2.2 Operator pada Algoritma Genetik (AG) Setelah populasi awal secara acak dihasilkan, algoritma berkembang melalui tiga operator yaitu seleksi yang setara dengan survival of the fittest, crossover yang merupakan perkawinan antara individu, dan mutasi yang memperkenalkan modifikasi acak.

Operator Seleksi Operator seleksi memberikan pilihan kepada individu yang lebih baik, yang memungkinkan untuk meneruskan gen kepada generasi berikutnya. Kebaikan dari masing-masing individu tergantung pada nilai fitness. Nilai fitness dapat ditentukan oleh fungsi obyektif atau oleh penilaian subyektif. Operator Crossover Faktor utama yang membedakan AG dari teknik optimasi lain adalah operator crossover. Dua individu dipilih dari hasil populasi menggunakan operator seleksi. Crossover memilih gen dari kromosom induk dan menciptakan sebuah keturunan baru. Cara melakukannya adalah dengan memilih secara acak beberapa titik crossover, kemudiannilai dari kedua string dipertukarkan. Dua keturunan baru yang diciptakan dari perkawinan ini dimasukkan ke dalam generasi berikutnya dari populasi. Dengan mengkombinasikan bagian dari individu yang baik, proses ini cenderung untuk menciptakan individu-individu lebih baik. Operator Mutasi Setelah crossover dilakukan, berlangsung proses mutasi. Tujuannya untuk melestarikan keragaman dalam populasi dan menghambat konvergensi prematur. Mutasi menginduksi perjalanan acak melalui ruang pencarian. Mutasi dan seleksi (tanpa crossover) membuat sebuah paralel, noise tolerant, dan algoritma hill climbing. 3. IMPLEMENTASI Teknik best route digunakan untuk menentukan rute terpendek yang harus ditempuh oleh obyek (gerobak) dari TPS dan mengumpulkan sampah dari semua bak sampah selanjutnya kembali ke TPS. Setiap node dinyatakan sebagai simpul graf, sedangkan sisi menyatakan jalan yang menghubungkan antar dua buah node. Bobot pada sisi menyatakan jarak antar dua buah node. Persoalan Perjalanan Pedagang tidak lain adalah menentukan lintasan yang melalui setiap node di dalam graf tepat satu kali, dan kembali ke simpul awal membentuk lintasan tertutup (disebut sirkuit Hamilton). Persoalan TSP pada game ini diselesaikan dengan menggunakan algoritma genetik. Dalam

rd


algoritma genetik, pembentukan generasi baru (anak) dilakukan dengan tiga operasi, yaitu seleksi, crossover dan mutasi, kemudian melakukan evaluasi terhadap setiap populasi dengan menghitung nilai fitness setiap kromosom hingga kriteria berhenti dipenuhi. Bila kriteria berhenti belum terpenuhi, maka akan dibentuk lagi generasi baru dengan mengulangi langkah seleksi, crossover dan mutasi. Beberapa kriteria berhenti yang sering digunakan antara lain berhenti pada generasi tertentu, berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi/terendah, berhenti bila dalam n generasi berikutnya tidak diperoleh nilai fitness yang lebih tinggi/rendah. Pseudocode dari algoritma genetik untuk penentuan rute terbaik.

Class findBestRoute public Gen[] findBestRoute(){ System.out.println("Masuk BestROute");

GA

find

Membangkitkan populasi awal secara random mother = populate(populationSize); child = new Individu[mother.length];

Membentuk generasi baru (anak) dengan menggunakan tiga operasi seleksi, crossover dan mutasi secara berulang-ulang for (Individu individu motherSystem.out.println("Individu :"+individu);}

:

Proses seleksi

mengambil jalur terbaik yang sudah dipilih dari Algoritma A* dan jarak dari masing–masing jalur

for (int jkl = 0; jkl < epoch; jkl++) {mother = competition(mother,3); System.out.println("generasi "+jkl+" : seleksi");

membangkitkan random

for (Individu individu : mother) { System.out.println(individu);}

populasi

awal

membentuk generasi baru (anak) menggunakan tiga operasi seleksi, crossover dan secara berulang-ulang

secara dengan

Proses crossover mutasi

mengevaluasi setiap populasi dengan menghitung nilai fitness setiap individu hingga kriteria berhenti dipenuhi. kriteria berhenti yaitu berhenti pada generasi tertentu

Best route atau rute terbaik dalam persoalan Travelling Salesman Problem adalah rute yang terpendek untuk meminimalkan biaya (cost). Penentuan rute terbaik ditulis dalam classfindBestRoute() menggunakan bahasa pemrograman Java. Inisialisasi public static final int DEFAULT_POPULATION_SIZE = 10; public static final int DEFAULT_CROSSOVER_PROBABILITY= 90; public static final int DEFAULT_MUTATION_PROBABILITY = 10; public static final int DEFAULT_EPOCH= 10;

child = crossover(mother, crossoverProbability); System.out.println("generasi "+jkl+" : Crossover"); for (int i = 0; i < child.length; i++) { System.out.println(child[i].toString())} for (int j = a; j <= b; j++) { result[i].setGen(j, source[i].getGen((a + b) - j));}}} return result; }

Proses mutasi System.out.println("generasi "+jkl+"" : Mutasi); child = mutation(child, mutationProbability); for (int i = 0; i < child.length; i++) {System.out.println(child[i].toString()) ;} mother = child;}

Mengevaluasi setiap populasi dengan menghitung nilai fitness setiap individu hingga kriteria berhenti dipenuhi yaitu berhenti pada generasi ke 199 (nilai epoch). Individu bestIndividu = mother[0]; for(int i=1;i<mother.length;i++){

rd

3 International Conference on e-Learning Bandung, November 23-24, 2011 if(mother[i].getFitness() bestIndividu.getFitness()) bestIndividu = mother[i];} return bestIndividu.getGens();}

>

4. PENGUJIAN

l. node (0,1)=[a, b, c, d, e, f, g, h, i, 1], dengan biaya 615

Langkah-langkah GA dalam penyelesaian TSP dengan perhitungan manual 1.

Populasi dibangkitkan secara random dengan population size 10 yangmenunjukkan terdapat 10 buah populasi dalam satu generasi.

2.

Inisialisasi Inisialisasi dilakukan dengan membentuk generasi baru (anak), misalkan didapatkan 10 individu sebagai berikut.

Individu Individu Individu Individu Individu

[1] [2] [3] [4] [5]

:0 :0 :0 :0 :0

2 1 3 1 3

3 3 2 2 2

1 2 1 3 1


[6] :0 [7] :0 [8] :0 [9] :0 [10]:0

2 1 2 1 2

Gambar 1:Play area4node 3. Gambar 1menunjukkan desain play area dimana terdapat node dan field tempat bak-bak sampah warga. Dalam desain, terdapat 3 bak sampah yang diidentifikasikan dengan nomor 1 sampai 3. Node 0 merupakan Tempat Pembuangan Sementara (TPS). Banyaknya kemungkinan jalur adalah n! /(n-r)! = 4! /(4-2)! = 12. Hasil dari pencarian jalur terpendek menggunakan teknik A* pathfinding yaitu 12 buah jalur terpendek. a. node(3,2)=[o, n, m, l, k, j, 2], dengan biaya 316 b. node(2,3)=[j, k, l, m, n, o, 3], dengan biaya 316 c. node(3,1)=[u, t, f, g, h, i, 1], dengan biaya 373 d. node (1,3)=[i, h, g, f, t, u, 3], dengan biaya 373 e. node (1,2)=[i, h, 2], dengan biaya 139 f. node (2,1)=[h, i, 1], dengan biaya 139 g. node (3,0)=[u, t, f, e, d, c, b, a, 0], dengan biaya 488 h. node (0,3)=[a, b, c, d, e, f, t, u, 3], dengan biaya 488 i. node (2,0)=[h, g, f, e, d, c, b, a, 0], dengan biaya 564 j. node (0,2)=[a, b, c, d, e, f, g, h, 2], dengan biaya 564 k. node (1,0)=[i, h, g, f, e, d, c, b, a, 0], dengan biaya 615

Evaluasi individu Evaluasi individu dilakukan dengan menghitung nilai fitness dari individu yang telah dibangkitkan. Perhitungan nilai fitness dari individu [1] yaitu 0 2 3 1 diperoleh dengan cara menjumlahkan biaya dari node 0 – node 2, node 2 – node 3, node 3 – node 1, dan node 1 – node 0. 𝐹𝑖𝑡𝑛𝑒𝑠𝑠[𝑖] = ∑𝑏𝑖𝑎𝑦𝑎 (𝑛𝑜𝑑𝑒𝑎𝑤𝑎𝑙 − 𝑛𝑜𝑑𝑒𝑎𝑘ℎ𝑖𝑟) ... (1)

𝐹𝑖𝑡𝑛𝑒𝑠𝑠[1,6,8,10] = ∑𝑏𝑖𝑎𝑦𝑎 node0 − 2 , node 2 − 3 , node 3 − 1 , node 1 − 0 = 564 + 316 + 373 + 615 = 1868 𝐹𝑖𝑡𝑛𝑒𝑠𝑠 2 = ∑𝑏𝑖𝑎𝑦𝑎 ((node0 − 1), node(1 − 3), node(3 − 2), node(2 − 0)) = 615 + 373 + 316 + 564 = 1868 𝐹𝑖𝑡𝑛𝑒𝑠𝑠 3,5 = ∑𝑏𝑖𝑎𝑦𝑎 ((node0 − 3), node(3 − 2), node(2 − 1), node(1 − 0)) = 488 + 316 + 139 + 615 = 1558

3 2 3 2 3

1 3 1 3 1

rd

3 International Conference on e-Learning Bandung, November 23-24, 2011 𝐹𝑖𝑡𝑛𝑒𝑠𝑠 4, 7,9 = ∑𝑏𝑖𝑎𝑦𝑎 ((node0 − 1), node(1 − 2), node(2 − 3), node(3 − 0)) = 615 + 139 + 316 + 488 = 1558

4.

Melakukan perulangan sebanyak epoch (di setting sebanyak 200, dan masing-masing operasi sebanyak 10), dan operasi seleksi menggunakan sistem kompetisi. Oleh karena pada persoalan TSP yang diinginkan yaitu individu dengan fitness yang lebih kecil akan mempunyai probabilitas untuk terpilih kembali lebih besar maka digunakan inverse.

yang ditentukan sebesar 90. Dengan operasi crossover, didapatkan individu baru sebagai berikut. Individu Individu Individu Individu Individu

6.

1

Q i = 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 ... (2) Q 1, 2, 6, 8, 10 =

1 = 5,353 1868

1 Q 3, 4, 5, 7, 9 = = 6,418 1558 Total = 58,855

Untuk mencari probabilitas, digunakan rumus sebagai berikut.

Dari nilai P i di atas dapat terlihat bahwa inividu ke 3, 4, 5, 7 dan 9 mempunyai fitness paling kecil mempunyai probabilitas untuk terpilih pada generasi selanjutnya lebih besar dari individu lainnya. 5.

Melakukan operasi crossover, satu bagian individu ditukarkan dengan tetap menjaga urutan node yang bukan bagian dari individu tersebut. Individu yang dijadikan induk dipilih secara acak dan jumlah individu yang di tukarkan dipengaruhi oleh parameter crossover probability (ρc)

2 1 2 2 2

3 3 3 3 3


[6] :0 3 2 1 [7] :0 2 1 3 [8] :0 1 2 3 [9] :0 3 2 1 [10] :0 2 1 3

[1] [2] [3] [4] [5]

:0 :0 :0 :0 :0

1 3 1 1 1

2 1 2 2 3

3 2 3 3 2


[6] :0 3 2 1 [7] :0 2 1 3 [8] :0 1 2 3 [9] :0 1 2 3 [10] :0 2 1 3

Mengevaluasi setiap populasi dengan menghitung nilai fitness setiap individu hingga kriteria berhenti dipenuhi, yaitu pada generasi ke 199. Dari hasil perhitungan didapatkan gen terbaik adalah 0 3 2 1 dengan nilai fitness terkecil, yaitu 1558 dan probabilitas sebesar 6,418.

8.

Rute terbaik diambil dari gen terbaik, gerobak sampah berjalan dari node 0 (TPS) , kemudian node3, node 2, node1, dan kembali lagi ke node 0. Gambar 2 menunjukkan rute terbaik (digambarkan dengan garis kuning) yang akan dilalui oleh obyek.

5,353 = 0,090 58,855

6,418 = 0,109 58,855

1 2 1 1 1

7.

Q i

P 3, 4, 5, 7, 9 =

:0 :0 :0 :0 :0

Melakukan operasi mutasi, jumlah individu yang mengalami mutasi dalam satu populasi ditentukan oleh parameter mutation rate (ρm) yang ditentukan sebesar 10. Proses mutasi dilakukan dengan cara menukar gen yang dipilih secara acak dengan gen sesudahnya. Jika gen tersebut berada di akhir individu, maka ditukar dengan gen yang pertama. Dengan operasi mutasi, didapatkan individu baru sebagai berikut.


P i = 𝑡𝑜𝑡𝑎𝑙 ... (3) P 1, 2, 6, 8, 10 =

[1] [2] [3] [4] [5]

rd


2. Klik sampah pada sumber sampah ke bak sampah, kemudian jalankan gerobak dengan menekan icon gerobak. 3. Hasil menunjukkan gerobak berjalan mulai dari TPS, ke bak sampah no. 3, kemudian bak sampah no. 2, lalu bak sampah no. 1 dan kembali lagi ke TPS.

Gambar 2: Hasil penentuan rute terbaik Tabel1: Pengujian dengan perhitungan manual Node awal 0 3 2 1

Node Jalur Tujuan 3 a, b, c, d, e, f, t, u, 3 2 o, n, m, l, k, j, 2 1 h, i, 1 0 i, h, g, f, e, d c, b, a, 0 Total jarak (∑)

Jarak 488 316 139 615 1558

Langkah-langkah GA dalam penyelesaian TSP dengan menjalankan game Kalpataru 1. Mengatur 3 buah bak sampah sedemikian hingga letaknya sama dengan pengujian secara manual dengan cara menekan tombol beli-beli, kemudian pilih bak sampah. 2. Klik sampah pada sumber sampah ke bak sampah, kemudian jalankan gerobak dengan menekan icon gerobak. 3. Hasil menunjukkan gerobak berjalan mulai dari TPS, ke bak sampah no. 3, kemudian bak sampah no. 2, lalu bak sampah no. 1 dan kembali lagi ke TPS. Langkah-langkah GA dalam penyelesaian TSP dengan menjalankan gameKalpataru 1. Mengatur 3 buah bak sampah sedemikian hingga letaknya sama dengan pengujian secara manual dengan cara menekan tombol beli-beli, kemudian pilih bak sampah.

Gambar 3: Hasil pengujian dengan menjalankan game Kalpataru 5. PENUTUP Penentuan rute terbaik pengumpulan sampah dari TPS ke bak sampah dan kembali ke TPS merupakan persoalan Travelling Salesman Problem dan diselesaikan menggunakan algoritma genetik. Hasil pengujian rute terbaik dengan perhitungan manual dan melalui game didapatkan rute yang sama. Hal ini berarti game telah berjalan sesuai dengan desain yang diharapkan. DAFTAR PUSTAKA Bryant, K. (2000), Genetic Algorithms and the Travelling Salesman Problem, Department of Mathematics, HarveyMudd College. Homaifar, A., Guan, S. And Liepins, Gunar E. (1992), Schema analysis of the travelling salesman problem using genetic algorithms, Complex Systems, 6(2):183-217. Melanie, M. (2005), An introduction to Genetic Algorithms, http://www.doc.ic.ac.uk/~nd/surprise96/jour nal/vol1/hmw/article1.html#selection , 11 Juni 2010, 09.14. WIB. Obitko, M. (1998), Introduction to Genetic Algorithm,Department of Computer Engineering, Faculty of Electrical engineering, Czech Technical

IMPLEMENTASI TRAVELLING SALESMAN PROBLEM (TSP) MENGGUNAKAN ALGORITMA GENETIK PADA GAME KALPATARU

Recommend Documents