| dc.description.abstract | Travelling Salesman Problem (TSP) adalah suatu pencarian rute perjalanan n
kota dengan biaya termurah dengan mengunjungi semua kota hanya satu kali. Biaya
dapat diasumsikan sebagai jarak, waktu, bahan bakar, dan sebagainya. Berdasarkan
biaya, permasalahan TSP dapat dibagi menjadi dua, yaitu TSP-simetris dan TSPasimetris.
Pada TSP-simetris, biaya dari kota 1 ke kota 2 adalah sama dengan biaya
dari kota 2 ke kota 1. Sedangkan pada TSP-asimetris, biaya dari kota 1 ke kota 2
tidak sama dengan biaya dari kota 2 ke kota 1.
Algoritma Genetik Commonality merupakan suatu pengembangan dari
algoritma Genetika. Jika dalam algoritma genetika baku, proses reproduksi dilakukan
melalui operator tukar silang dan mutasi. Setiap kromosom dievaluasi dengan
menggunakan fungsi fitness. Sedangkan pada algoritma genetik commonality, operasi
tukar silang didefinisikan kembali dalam dua tahap (Chen & Stephen, 1999) : 1)
memelihara common schema maksimal dari dua induk, dan 2) melengkapi solusi
dengan construction heuristic. Karena keturunan yang dihasilkan akan lebih baik
dibandingkan dengan kedua induknya, maka evolusi akan terjadi tanpa menyatakan
seleksi alam secara eksplisit. Dengan kata lain, evolusi terjadi tanpa melibatkan
fungsi fitness.
Penelitian dilakukan dengan beberapa langkah. Langkah pertama
membangkitkan populasi awal (rute awal) menggunakan construction heuristic
dengan metode AI (Arbitrary Insertion). Langkah kedua melakukan reproduksi solusi
baru dengan operasi tukar silang. Langkah ketiga membentuk populasi baru
(kumpulan rute). Berdasarkan penelitian yang telah dilakukan, didapatkan hasil bahwa jarak
perjalanan terpendeknya sepanjang 1007 km dengan rute 1-13-24-7-20-23-22-19-1621-25-4-11-9-15-18-14-2-17-8-10-12-5-3-6
dan diperoleh kesimpulan dapat
dihasilkan jarak yang sama dengan rute yang berbeda disebabkan adanya proses
penyisipan kota-kota yang tidak terdapat pada Graf Partial Order menggunakan
metode AI. | en_US |
