TSP Algorithm

Travelling Salesman Problem (TSP)

with Genetic Algorithm

Oleh Aila Gema Safitri NIM : 23213314 UAS Sistem Intelijen

Latar Belakang � Pekerjaan seorang sales yang harus melakukan

perjalanan dari satu tempat/kota ke tempat/kota lain. Bayangkan, dalam sehari, jika sales tersebut harus mengunjungi 20 tempat/kota. Berapa banyak waktu, tenaga, dan biaya yang dihabiskan? Untuk itu, sebelum melakukan perjalanan, sebaiknya dilakukan analisa rute mana yang lebih singkat untuk ditempuh.

� Jika hanya 3 kota, maka kemungkinan yg ada hanya 6 rute.Namun, bagaimana jika ada 20 kota? Berapa banyak kemungkinan rute yang harus ia tempuh? 20! ??

� Untuk itu, algoritma genetika dapat dijadikan solusi untuk mencari kemungkinan jarak rute yang relatif singkat.

Titik-titik koordinat kota yang harus dikunjungi (ada 20 kota)

Flowchart Algoritma Genetika Representasi Kromosom

Membangkitkan Populasi Awal

Hitung Fitness

Seleksi

Perkawinan Silang

Mutasi

Individu Baru

Optimal ? Tidak

Solusi Optimal Ya

Representasi Kromosom • Kromosom terdiri dari beberapa gen.

• Pada TSP, gen adalah sebuah kota. Jadi, kumpulan dari kota-kota yang akan dilalui akan membentuk sebuah rute. 1 rute mewakili 1 kromosom.

• Pada kasus 20 kota, kromosom dinyatakan dalam 21 gen, dikarenakan index awal = index akhir. Sebagai contoh, jika 1 rute hanya menempuh 5 kota maka rute nya : B-A-D-C-E-B ( ada 6 gen dalam 1 rute)

Membangkitkan Populasi Awal

Membangkitkan sejumlah kromosom, misalkan satu populasi terdiri dari 120 kromosom ( 5!), maka dibangkitkan 120 kromosom dengan 6 gen yang dibangkitkan secara acak.

Proses ini ada pada kelas Populasi.java

public Populasi(int

populationSize, boolean

initialise) {

rutes = new

Rute[populationSize];

if (initialise) {

for (int i = 0; i <

populationSize(); i++)

{

Rute newRute = new Rute();

newRute.generateIndividual();

saveRute(i, newRute);

}

}

Hitung Fitness • Nilai fitness adalah tingkat ketahanan sebuah

kromosom. Semakin tinggi fitness, semakin baik kromosom tersebut.

• Pada TSP, utk mencari nilai fitnes, dihitung berdasarkan bobot jarak dalam sebuah rute. Dengan fungsi fitness = 1 / (total jarak sebuah rute)

• Dimana jarak antar kota diperoleh dari menghitung jarak dari satu kota ke kota lain dengan rumus persamaan garis. Lihat kelas Kota.java

• Total jarak rute dihitung berdasarkan jumlah jarak antar kota dalam satu rute. Lihat kelas Rute.java

• Semakin kecil total jarak rute, maka nilai fitness semakin besar. Sehingga, nanti akan dipilih, nilai fitness yang besar (mendekati ideal).

• Hitung nilai fitness ada di kelas Rute.java

Seleksi Kromosom tahap 1

� Seleksi nilai fitness untuk memilih kromosom kandidat yang akan di cross over.

� Lihat di kelas Populasi.java dimana ada fungsi getFittest untuk mencari kromosom-kromosom dengan nilai fitness yang mendekati ideal.

Seleksi Kromosom Tahap 2 • Setelah terpilih kelompok kromosom dengan nilai

fitness yang mendekati ideal, maka dilakukan seleksi berikutnya terhadap kromosom-kromosom tersebut.

• Seleksi dilakukan menggunakan method Tournament Selection.

• Yaitu diambil sekelompok kromosom secara random, lalu dipilih satu kromosom yang memiliki nilai fitness tertinggi untuk menjadi orang tua. Hal ini dilakukan berulang-ulang hingga ditemukan jumlah orang tua yang diinginkan

• Proses tournament selection dapat dilihat di kelas GA.java.

Perkawinan Silang (Cross Over) � Cross-Over (Perkawinan Silang) dilakukan dengan metode Two

Point Crossover, dengan menentukan 2 posisi awal dan akhir gen pada individu yang akan dikawinkan secara acak. Kemudian dilakukan penukaran nilai gen induk 1 dan induk 2 dari posisi awal sampai dengan posisi akhir untuk diperoleh anak 1 dan anak 2.

� Parent 1 � Child � Parent 2

� Proses cross over dapat dilihat di kelas GA.java

B C D A E B

C B D A E C

C A B D E C

Mutasi

� Mutasi dilakukan dengan cara swap mutation yakni menggeser gen didalam kromosom child secara random, menggunakan parameter mutation rate.

� Mutasi sebaiknya jangan terlalu sering dilakukan, karena kromosom child yang dihasilkan akan sangat berbeda dengan parent. Mutasi dilakukan agar terjadi variasi keturunan, dengan tujuan mencari kualitas yang lebih baik dari parent.

� Child sebelum mutasi � Child setelah mutasi

� Proses mutasi ada di kelas GA.java dengan menggunakan

fungsi mutate.

C B D A E C

C E D A B C

Membentuk Individu Baru

� Anak hasil perkawinan silang dan mutasi menjadi generasi baru untuk dilakukan proses regenerasi

� Proses membentuk individu baru dapat dilihat di method evolvePopulasi di kelas GA.java

� Untuk iterasi generasi berikutnya, dilakukan looping populasi baru untuk mencari parent berikutnya. Looping berdasarkan hasil seleksi individu terbaik (nilai fitness terbesar) yang dipertahankan lewat proses elitism.

� Elitism semacam parameter untuk menyimpan individu terbaik (dipertahankan), untuk kemudian menjadi nilai pembanding di proses iterasi berikutnya.

� Iterasi terus dilakukan sampai didapat child yang dianggap paling mendekati kondisi ideal.

Contoh Hasil Algoritma Genetika Untuk 5 Kota didapat rute terbaik yaitu B-A-D-C-E-B

Contoh Hasil Algoritma Genetika

Untuk 20 Kota didapat rute terbaik :