Combinatorial Problem

• Masalah : Menemukan suatu objek kombinatorik seperti permutasi, kombinasi atau subset yang memenuhi batasan tertentu dan memiliki properti yang diinginkan.
• Problem yang paling sulit : Sejumlah objek kombinatorik tertentu tumbuh dengan cepat seiring peningkatan ukuran masalah
•  Tidak diketahui algoritma eksak untuk menyelesaikan masalah tersebut.
• Salah satu contohnya TSP dan GCP.

Travelling Salesman Problem (TSP)

    TSP adalah problem untuk mengoptimasi dan menemukan perjalanan (tour) yang paling terpendek. Secara ringkas, berikut adalah karakteristik dari permasalahan TSP:

1.           Harus mengunjungi setiap kota tepat satu kali, tidak boleh kurang ataupun lebih.
2.           Semua kota harus dikunjungi dalam satu kali perjalanan (tour).
3.           Dimulai dan diakhiri pada kota yang sama.

       Kelebihan TSP : dapat dilakukan secara sederhana dengan beberapa metode algoritma.    

       Kekurangan TSP : salah satu contoh permasalahan kombinatorial dengan kemungkinan penyelesaian yang sangat banyak. 
      Implementasi TSP Pada Kota :

      TSP Dengan 3 Kota.

        TSP dengan 3 kota (1, 2, 3) hanya mempunyai satu kemungkinan seperti gambar dibawah ini :

                                  TSP dengan 3 kota tidak perlu diselesaikan menggunakan komputer.

      TSP Dengan 4 Kota.

      Graf di atas memiliki 4!/2(4) = 3 sirkuit Hamilton Misalkan simpul a adalah kota tempat dimulainya  perjalanan (starting city). Enumerasikan semua sirkuit hamilton sebagai berikut :

I₁ = (a, b, c, d, a) atau (a, d, c, b, a)  ==> panjang = 10 + 12 + 8 + 15 = 45

I₂ = (a, c, d, b, a) atau (a, b, d, c, a)  ==> panjang = 12 + 5 + 9 + 15 = 41

I₃ = (a, c, b, d, a) atau (a, d, b, c, a)  ==> panjang  = 10 + 5 + 9 + 8 = 32

        

      Jadi, sirkuit Hamilton terpendek adalah I₃ = (a, c, b, d, a) atau (a, d, b, c, a)dengan panjang sirkuit = 10 + 5 + 9 + 8 = 32.    

      TSP Dengan 5 Kota.

    Graf di atas memiliki 5!/2(5) = 12 sirkuit Hamilton Misalkan simpul a adalah kota tempat dimulainya perjalanan (starting city). Enumerasikan semua sirkuit hamilton sebagai berikut :

I    1 = (1, 2, 3, 4, 5,1) atau (1, 5, 4, 3, 2,1) 

I    2 = (1,2,5,4,3,1) atau (1,3,4,5,2,1)

I    3 = (1,2,3,5,4,1) atau (1,4,5,3,2,1 )

:
:

:

I    12 =………………………………………

    TSP dengan 5 kota mulai perlu diselesaikan menggunakan komputer. Teknik yang dipakai bisa berupa mencoba semua kemungkinan dan dibandingkan jaraknya untuk memperoleh jarak paling pendek. 

.     TSP Dengan N Kota.

      TSP dengan n kota (1, 2, 3, 4, 5,…, n) mempunyai n ! / 2n kemungkinan.

     TSP dengan 15 kota mempunyai 15 ! / (15) atau 4,3589 x 10¹⁰ kemungkinan. Metode pencarian satu-satu memerlukan waktu yang sangat lama.

    TSP dengan 20 kota mempunyai 19 ! / 2 atau 6,08 x 10¹⁶ kemungkinan, suatu jumlah yang sangat besar. Dengan menganggap bahwa komputer mampu menyelesaikan 1 Giga (10⁹) proses per-detik maka untuk mencari semua solusi diperlukan 6,08 x 10⁷ detik atau 1,69 x 10⁴ jam atau 704 hari. Waktu yang sangat lama.

      Konsep dan Implementasi Beberapa Algoritma Terhadap TSP

•      Algoritma Greedy

     Algoritma greedy merupakan sebuah algoritma yang dapat menentukan sebuah jalur terpendek antara node-node yang akan digunakan dengan mengambil secara terus menerus dan menambahkannya ke dalam jalur yang akna dilewati.

      Algoritma greedy dalam menyelesaikan masalah dengan langkah per langkah “bertahap”
Dengan definisi, Pada setiap langkah algoritma greedy :

1.      mengambil pilihan yang terbaik yang
2.      Dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi kedepan(prinsip“take what you can get now!”) 
3.       Berharap bahwa dengan memilih optimum Local pada setiap langkah akan berakhir dengan optimum global.

      Algoritma greedy merupakan salah satu dari sekian banyak algoritma yang sering di pakai dalam implementasi sebuah system atau program yang menyangkut mengenai pencarian “optimasi”.

1.      

•      Algoritma Genetika

    Konsep algoritma genetika sendiri adalah algoritma pencarian heuristik yang didasarkan pada mekanisme evolusi biologis. Keberagaman pada evolusi biologis adalah variasi dari kromosom dalam individu organisme. Variasi kromosom ini akan mempengaruhi laju reproduksi dan tingkat kemampuan organisme untuk tetap hidup.Pada dasarnya ada 4 kondisi yang mempengaruhi proses evaluasi, yaitu :

1.  Kemampuan organisme untuk melakukan reproduksi.
2.  Keberadaan populasi organisme yang bisa melakukan reproduksi.
3.  Keberagaman organisme dalam suatu populasi.
4.  Perbedaan kekuatan dan kemampuan organisme untuk bertahan hidup.

Adapun langkah-langkah dari algoritma genetika adalah sebagai berikut :

1. Langkah pertama adalah melakukan penentuan nilai awal (inisialisasi). Bagian ini merupakan pemberian input yang dilakukan oleh pengguna.
2. Proses berikutnya adalah proses pembentukan populasi awal. Proses ini berfungsi untuk membentuk populasi generasi pertama.
3. Selanjutnya adalah proses seleksi, dimana setelah terbentuk populasi awal, maka hasil populasi awal itu akan diseleksi.
4. Setelah melakukan proses seleksi, maka hasil dari proses tersebut akan digunakan dalam proses crossover.
5. Sebelum melakukan proses crossover dilakukan pengundian dengan bilangan random untuk setiap kromosom, apakah kromosom tersebut terjadi crossover atau tidak.
6. Jika dari proses pengundian menunjukkan bahwa terjadi crossover maka akan dibuat bilangan random lain untuk menentukan dimana crossover akan terjadi.
7. Setelah proses crossover dijalankan selalu dilakukan pengecekan apakah kromosom yang terkena crossover tersebut merupakan kromosom yang valid, dalam arti kromosom hasil crossover tersebut membentuk suatu rute.
8. Jika terjadi pengulangan individu dalam kromosom, maka dilakukan proses normalisasi untuk membuat kromosom tersebut menjadi valid.
9. Pada saat penyalinan kromosom dilakukan, kromosom tersebut dapat mengalami mutasi, yaitu perubahan isi kromosom, dimana isi dari kromosom tersebut digantikan dengan suatu nilai yang dipilih secara acak dari titik-titik yang ada.
10. Setelah proses mutasi, maka akan dilakukan lagi proses seleksi dan dilakukan pengecekan apakah proses keseluruhan telah selesai atau belum. 

Algoritma	Greedy	Genetika
Kelebihan	-          Waktu komputasi yang dibutuhkan dalam menyelesaikan kasus TSP lebih cepat.       -          Lebih sesuai untuk kasus yang membutuhkan solusi hampiran.	-          Waktu komputasi yang dibutuhkan cenderung stabil.       -          Mampu memberikan jarak terpendek meski dengan jumlah kota yang besar, bila dibandingkan dengan algoritma yang lain.
Kekurangan	Hasil yang didapatkan tidak selalu optimal. Hal ini karena algoritma greedy masih terjebak dalam optimum lokal.	Sangat bergantung pada pemilihan parameter input, yaitu ukuran populasi, besar maksimum generasi, ukuran peluang crossover, dan ukuran peluang mutation.

     Kesimpulan : 

1.      Travelling salesman problem adalah suatu permasalahan dalam menentukan sirkuit terpendek dari suatu simpul ke seluruh simpul lain tepat satu kali dan kembali ke simpul asal.
2.       Algoritma exhaustive, yaitu dengan mencari semua kombinasi yang mungkin terjadi, kemudian memilih kombinasi perjalanan dengan jarak terdekat, algoritma ini mempunyai kompleksitas n!/2n.
3.    Belum ada algoritma yang dapat menyelesaikan masalah  traveling salesman problem dengan  polynomial worst-case time complexity .Ini artinya untuk jumlah simpul yang banyak, penyelesaian traveling salesman problem adalah tidak praktis.

            GCP (Ground Control point)

           Titik kontrol lapangan (GCP) adalah suatu titik-titik yang letaknya pada suatu posisi piksel suatu citra yang koordinat petanya (referensinya) diketahui. GCP terdiri atas sepasang koordinat x dan y, yang terdiri atas koordinat sumber dan koordinat referensi. Koordinat-koordinat tersebut tidak dibatasi oleh adanya koordinat peta. Secara teoretis, jumlah minimum GCP yang harus dibuat adalah: 

J    jumlah minimum GCP = (t+1) (t+2)/2 dimana t = orde .

             Lokasi ideal saat pengambilan GCP adalah perempatan jalan, sudut jalan, perpotongan jalan pedestrian, kawasan yang memiliki warna menyolok, persimpangan rel dengan jalan dan benda/ monumen/ bangunan yang mudah diidentifikasi atau dikenal. Perlu dihindari pohon, bangunan, dan tiang listrik selain sulit diidentifikasi, karena kesamaannya yang tinggi.

     Daftar Pustaka :
           https://profhadibanoe.wordpress.com/2012/01/13/solusi-tsp-dengan-algoritma-generate-test/
           http://livooz.blogspot.co.id/2013/04/travelling-salesman-problem-tsp.html
h         https://awhasyim.wordpress.com/2009/05/10/85/
           http://herilovemetallica.blogspot.com/2010/04/algorima-greedy-dan-pembahasan-lengkap.html