Source Code Algoritma Genetika TSP Codeigniter

Landasan Teori

Traveling Salesman Problem (TSP)

Traveling Salesman Problem (TSP) adalah permasalahan yang sudah cukup tua di dunia optimasi. Pada permasalahan ini, ada sebuah kota awal dan sejumlah n kota untuk dikunjungi. Seorang salesman dituntut memulai perjalanan dari kota awal ke seluruh kota yang harus dikunjungi tepat satu kali. Tujuan utamanya adalah mencari rute dengan total jarak atau biaya minimum yang mengunjungi setiap lokasi tepat satu kali dan biasanya kembali ke titik awal.

Langkah-langkah Traveling Salesman Problem

1. Menentukan daftar lokasi yang harus dikunjungi.
2. Membentuk matriks jarak atau biaya antarlokasi.
3. Menentukan kota awal jika diperlukan.
4. Mencari urutan kunjungan yang memenuhi setiap kota tepat satu kali.
5. Menghitung total jarak atau biaya rute.
6. Memilih rute dengan nilai objektif terbaik.

Algoritma Genetika

Algoritma Genetika dikembangkan pertama kali oleh John Holand dari New York, Amarika Serikat yang dipublikasikan dalam bukunya yang berjudul “Adaption in Natural and Artificial Systems” tahun 1975. Algoritma Genetika merupakan Teknik untuk menemukan solusi optimal dari permasalahan yang mempunyai banyak solusi. Teknik ini akan melakukan pencarian dari beberapa solusi yang diperoleh sampai mendapatkan solusi terbaik sesuai dengan kriteria yang telah ditentukan atau yang disebut sebagai fungsi fitness. Algoritma ini masuk dalam kelompok algoritma evolusioner dengan menggunakan pendekatan evolusi Darwin di bidang Biologi seperti pewarisan sifat, seleksi alam, mutasi gen dan kombinasi (crossover). Karena merupakan Teknik pencarian optimal dalam bidang ilmu komputer, maka algoritma ini juga termasuk dalam kelompok algoritma metaheuristik.

Langkah-langkah Algoritma Genetika

1. Menentukan representasi kromosom dan populasi awal.
2. Menentukan fungsi fitness.
3. Melakukan seleksi individu.
4. Melakukan crossover.
5. Melakukan mutasi.
6. Membentuk populasi baru.
7. Mengulangi proses hingga kriteria berhenti terpenuhi.