tugas

Tugas 4: Penyelesaian Kasus Travelling Salesman Problem (TSP) Menggunakan Algoritma Genetika

Tugas 4: Penyelesaian Kasus Travelling Salesman Problem (TSP) Menggunakan Algoritma Genetika

Implementasi metode komputasi evolusioner Algoritma Genetika untuk memecahkan permasalahan optimasi kombinatorial NP-Hard: Travelling Salesman Problem (TSP), yakni mencari rute sirkuit terpendek yang mengunjungi setiap kota tepat satu kali dan kembali ke kota asal.

1. Representasi Kromosom dan Operator Genetik TSP

  • Representasi Permutasi: Kromosom direpresentasikan sebagai susunan urutan indeks kota [C1,C2,C3,…,Cn][C_1, C_2, C_3, \dots, C_n].
  • Fungsi Fitness: Berbanding terbalik dengan total jarak tempuh sirkuit tur:
Total Jarak=∑i=1n−1d(Ci,Ci+1)+d(Cn,C1),Fitness=1Total Jarak\text{Total Jarak} = \sum_{i=1}^{n-1} d(C_i, C_{i+1}) + d(C_n, C_1), \quad \text{Fitness} = \frac{1}{\text{Total Jarak}}
  • Order Crossover (OX): Menjaga konsistensi permutasi rute agar tidak terjadi duplikasi kota atau kota yang terlewati saat mewariskan gen dari kedua induk.
  • Swap Mutation & Inversion Mutation: Menukar posisi dua kota secara acak atau membalik urutan sub-rute dengan probabilitas tertentu guna mempertahankan variasi genetik populasi.

2. Berkas Tugas Terlampir

  • Laporan komparasi dan analisis performa: Kelompok3_KK_F.pdf yang memuat formulasi matematika TSP, grafik konvergensi nilai fitness terhadap generasi, dan analisis pengaruh ukuran populasi.
  • Arsip kode sumber lengkap: algoritma-genetika-tsp.zip yang berisi implementasi kode algoritma genetika Python dan dataset koordinat kota pengujian.

Attachments

Back to Academics