PENERAPAN ALGORITMA GENETIKA PADA TRAVELLING SALESMAN PROBLEM

Dalam dunia yang serba praktis, diperlukan suatu algoritma cepat untuk mencari suatu solusi yang mendekati solusi optimal, tetapi tidak memerlukan waktu yang lama. Algoritma genetika adalah salah satu algoritma alternatif yang dapat digunakan sebab prosesnya cepat dan memberikan hasil yang diinginkan. Selain itu, algoritma genetika juga mampu memberikan suatu solusi pada waktu kapanpun.

Bagaimana algoritma genetika dapat menyelesaikan TSP yaitu solusi direpresentasikan ke dalam suatu kromosom yang berisi dari nomor urut kota-kota selain kota asal. Masing-masing nomor urut tidak boleh muncul lebih dari satu kali di dalam kromosom sehingga satu kromosom merepresentasikan satu rute perjalanan (satu solusi) yang valid.

Bentuk representasi dari persoalan yang akan digunakan

Berikut contoh persoalan yang diselesaikan dengan menggunakan algoritma genetika.!

Terdapat 5 buah kota yang akan dilalui oleh seorang pedangang keliling, misalnya Kota A,B,C,D,E. Perjalanan dimulai dari kota A dan berakhir di kota A. Jarak antar kota diperlihatkan pada graf di bawah ini:

TRAVELLING SALESMAN PROBLEM

Masalah klasik yang dikenal sebagai Traveling Salesman Problem (TSP) menjadi pokok bahasan menantang yang dikaji secara intensif selama beberapa dasawarsa terakhir di bidang operational research, logistik dan sistem rantai pasok (supply chain systems), transportasi maupun theoretical computer science.

Sejarah TSP bisa ditelusur dari Euler yang mempelajari Knight Tour’s Problem (1759), Kirkman yang mempelajari grafik polihedron (1856) maupun Hamilton yang membuat game Icosian (1856) yang bertujuan mencari jalur sirkuit berbasis grafik polihedron yang memenuhi kondisi tertentu [2]. Istilah TSP sendiri diperkirakan berasal dari buku yang diterbitkan oleh seorang veteran salesman sekitar tahun 1930an di Jerman, meski dalam buku ini masalah TSP lebih dibahas dari aspek bisnis dan belum diformulasikan secara matematis.

ALGORITMA GENETIKA

Apa itu Algoritma Genetika.?

Algoritma genetik adalah teknik pencarian yang di dalam ilmu komputer untuk menemukan penyelesaian perkiraan untuk optimisasi dan masalah pencarian. Algoritma genetik adalah kelas khusus dari algoritma evolusioner dengan menggunakan teknik yang terinspirasi oleh biologi evolusioner seperti warisan, mutasi, seleksi alam dan rekombinasi (atau crossover)

Algoritma Genetik pertama kali dikembangkan oleh John Holland pada tahun 1970-an di New York, Amerika Serikat. Dia beserta murid-murid dan teman kerjanya menghasilkan buku berjudul "Adaption in Natural and Artificial Systems" pada tahun 1975.

Algoritma Genetik khususnya diterapkan sebagai simulasi komputer dimana sebuah populasi representasi abstrak (disebut kromosom) dari solusi-solusi calon (disebut individual) pada sebuah masalah optimisasi akan berkembang menjadi solusi-solusi yang lebih baik. Secara tradisional, solusi-solusi dilambangkan dalam biner sebagai string '0' dan '1', walaupun dimungkinkan juga penggunaan penyandian (encoding) yang berbeda. Evolusi dimulai dari sebuah populasi individual acak yang lengkap dan terjadi dalam generasi-generasi. Dalam tiap generasi, kemampuan keseluruhan populasi dievaluasi, kemudian multiple individuals dipilih dari populasi sekarang (current) tersebut secara stochastic (berdasarkan kemampuan mereka), lalu dimodifikasi (melalui mutasi atau rekombinasi) menjadi bentuk populasi baru yang menjadi populasi sekarang (current) pada iterasi berikutnya dari algoritma.