Traveling Salesperson Problem

Traveling Salesman Problem atau Traveling Salesperson Problem(TSP) adalah permasalahan komputasi combinatorial optimization yang berfokus pada optimalisasi dari kumpulan objek yang mempunyai batasan. Namun, kompleksitas dari komputasi masalah ini mempunyai tingkatan NP-hardness (non-deterministic polynomial-time hardness). TSP bisa dibentuk dengan model graf, dimana kota-kota bisa disebut dengan simpul kemudian jarak antara kota bisa disebut sisi sehingga jarak total jalur dapat diartikan bobot sisi.

Pada dasarnya TSP mempunyai tujuan untuk mencari solusi paling minimum dari total panjang jarak jalur suatu kota sampai n-kota dengan tepat satu kali kunjungan pada setiap kota yang dilewati. Hal ini bisa menjadi rumit seiring dengan banyak kota yang akan dikunjungi, karena diharuskan untuk menghitung jarak total kumpulan kota dari kombinasi urutan kota tersebut yang kemudian memilih jarak yang paling pendek.

Salah satu solusi komputasi adalah dengan mencoba untuk mencari nilai permutasi dari banyak kota sehingga membentuk urutan kombinasi kota yang kemudian dilihat satu satu mana jarak yang paling murah dalam model graf.

Genetic Algorithm

Algoritma genetika adalah teknik pencarian heuristik dalam ilmu komputasi untuk menemukan penyelesaian perkiraan optimasi dari suatu permasalahan pencarian. Algoritma genetika mempunyai dasar mekanisme dari teorema evolusi Darwinian yang mempunyai konsep evolusi biologis, yakni sebuah konsep dimana setiap generasi yang terbentuk dapat berkembang dan berevolusi menjadi generasi yang lebih baik kedepannya.

Proses perkembangan dan evolusi ini terjadi berdasarkan faktor kondisi yang mendukung seperti seleksi alam, pewarisan sifat atau gen yang bervariasi sehingga meningkatkan kemampuan untuk berkompetisi, bertahan hidup dan reproduksi. Setiap keturunan yang dihasilkan akan mewariskan sifat dari induknya untuk terus berevolusi dan berkembang. Hal ini akan terus terjadi dan berulang.

Keturunan memainkan peran penting untuk keberlangsungan dari sifat atau gen yang dimiliki generasi sebelumnya. Jika mampu bertahan cukup lama dari kondisi yang diberikan maka sifat mereka akan dipasangkan dengan yang lain untuk membuat generasi berikutnya.

Variasi harus ada dalam setiap generasi untuk menunjang perubahan yang terjadi pada generasi berikutnya. Sebagai contoh, jika pada sebuah populasi kupu-kupu yang mana setiap kupu-kupu yang ada mempunyai warna, ukuran, lebar sayap semuanya sama. Tanpa adanya variasi dari sifat-sifatnya, anak yang dihasilkan dari reproduksi mereka akan identik dengan induknya. Kombinasi yang terjadi akan selalu ada dalam bentuk yang sama sehingga tidak menghasilkan evolusi.

Sebuah mekanisme seleksi diperlukan untuk memangkas sifat atau gen yang tidak diperlukan lagi dari sebuah populasi. Hal ini ditujukan untuk memilih mana anggota populasi yang mempunyai kesempatan untuk menjadi induk dan menurunkan informasi sifatnya dengan yang tidak bisa sama sekali.

Namun konsep keturunan yang baik bukan hanya berarti lebih cepat, lebih besar atau lebih kuat. Faktor alam untuk seleksi menyesuaikan kecocokan (fitness) yang diperlukan dengan kondisi itu sendiri. Proses ini semua akan dilakukan secara berulang ulang membuat keturunan yang baru sampai mendapatkan hasil yang paling optimal.