Traveling Salesperson Problem (TSP) atau Masalah Pedagang Keliling merupakan salah satu masalah optimasi klasik yang paling banyak dipelajari. Inti dari masalah ini adalah menemukan rute terpendek yang mengunjungi setiap kota dalam daftar tepat satu kali dan kembali ke kota asal. Meskipun konsepnya sederhana, menemukan solusi optimal untuk TSP bisa menjadi sangat kompleks, terutama ketika jumlah kota bertambah. Seiring dengan pertumbuhan jumlah kota, jumlah kemungkinan rute tumbuh secara eksponensial, membuat pendekatan coba-coba menjadi tidak praktis.
Dalam menghadapi kompleksitas ini, berbagai algoritma heuristik dan aproksimasi telah dikembangkan. Salah satu pendekatan yang kuat dan populer adalah penggunaan algoritma genetika. Algoritma genetika terinspirasi oleh proses seleksi alam dan genetika biologis, yang menawarkan cara yang efisien untuk menjelajahi ruang solusi yang luas dan menemukan solusi yang mendekati optimal.
Prinsip dasar algoritma genetika melibatkan evolusi populasi solusi potensial dari waktu ke waktu. Untuk TSP, setiap solusi potensial (disebut kromosom atau individu) merepresentasikan urutan kunjungan kota. Misalnya, jika ada 5 kota (A, B, C, D, E), sebuah kromosom bisa berupa urutan [A, C, E, B, D].
Konsep Kunci dalam Algoritma Genetika untuk TSP:
Prosesnya dimulai dengan membuat populasi awal yang terdiri dari banyak rute yang dihasilkan secara acak. Setiap rute ini dievaluasi menggunakan fungsi fitness, yang biasanya adalah kebalikan dari total jarak yang ditempuh oleh rute tersebut. Rute yang lebih pendek (dengan total jarak lebih kecil) akan memiliki nilai fitness yang lebih tinggi.
Selanjutnya, algoritma akan melakukan seleksi. Rute dengan nilai fitness yang lebih tinggi memiliki peluang lebih besar untuk dipilih sebagai "orang tua" untuk menghasilkan generasi berikutnya. Proses seleksi ini meniru "survival of the fittest" di alam.
Setelah orang tua terpilih, mereka akan melalui operasi crossover. Dalam konteks TSP, crossover bisa berarti mengambil sebagian urutan kota dari satu orang tua dan menggabungkannya dengan urutan dari orang tua lain untuk membentuk rute keturunan yang baru. Tujuannya adalah untuk menggabungkan "sifat-sifat baik" (bagian-bagian rute yang pendek) dari kedua orang tua.
Operasi mutasi kemudian diterapkan pada keturunan. Mutasi ini bisa berupa penukaran dua kota secara acak dalam urutan rute. Mutasi sangat penting untuk mencegah algoritma terjebak pada solusi yang optimal secara lokal tetapi bukan optimal global, dan untuk menjaga keragaman dalam populasi.
Proses seleksi, crossover, dan mutasi ini diulang berkali-kali selama beberapa generasi. Setiap generasi diharapkan memiliki populasi rute yang secara keseluruhan lebih baik daripada generasi sebelumnya. Algoritma genetika akan berhenti setelah sejumlah generasi tertentu tercapai, atau ketika solusi yang cukup baik ditemukan (misalnya, ketika tidak ada peningkatan signifikan lagi dalam kualitas solusi).
Salah satu keuntungan utama algoritma genetika adalah kemampuannya untuk menangani masalah TSP dengan jumlah kota yang besar, di mana algoritma eksak menjadi terlalu lambat. Algoritma ini tidak menjamin menemukan solusi yang benar-benar optimal, tetapi ia sangat efektif dalam menemukan solusi yang sangat mendekati optimal dalam waktu yang wajar. Fleksibilitasnya juga memungkinkan penyesuaian parameter (seperti ukuran populasi, laju crossover, dan laju mutasi) untuk mengoptimalkan kinerja pada masalah spesifik.
Oleh karena itu, algoritma genetika adalah alat yang ampuh dalam portofolio penyelesaian masalah optimasi, khususnya untuk tantangan seperti Traveling Salesperson Problem yang banyak ditemui dalam logistik, perencanaan rute, dan penjadwalan.