BAB I PENDAHULUAN
1.1 Latar Belakang Pada awal diciptakan, komputer hanya difungsikan sebagai alat hitung saja. Namun seiring dengan perkembangan zaman, maka peran komputer semakin mendominasi kehidupan. Lebih dari itu, komputer diharapkan dapat digunakan untuk mengerjakan segala sesuatu yang bisa dikerjakan oleh manusia baik dalam bidang pendidikan, kesehatan, industri, dan kehidupan sehari-hari sehingga peran komputer dan manusia akan saling melengkapi. Beberapa hal yang menjadi kekurangan manusia diharapkan dapat digantikan oleh komputer. Begitu juga dengan komputer yang tak akan berguna tanpa sentuhan manusia. Dalam dunia komputer dan informatika adanya suatu ilmu dengan ide-ide untuk dapat membuat komputer menjadi lebih cerdas, ilmu tersebut dinamakan kecerdasan buatan (Artificial Intelligence). Pengertian dari Artificial Intelligence ini sendiri adalah bagian dari ilmu komputer yang mempelajari bagaimana membuat mesin (komputer) dapat melakukan pekerjaan seperti dan sebaik yang dilakukan oleh manusia bahkan bisa lebih baik daripada yang dilakukan manusia, dengan mengimplementasikannya dalam sebuah program. Dalam Artificial Intelligence adanya istilah soft computing yaitu inovasi baru dalam membangun sistem cerdas dimana sistem ini memiliki keahlian seperti manusia pada domain tertentu, mampu beradaptasi dan belajar agar dapat bekerja lebih baik jika terjadi perubahan lingkungan. Untuk mengoperasikan soft computing perlu diketahui metodologi-metodologinya dimana salah satunya adalah Evolutionary Computing (optimasi) yang menggunakan Algoritma Genetika. Jadi dengan kata lain dapat dikatakan bahwa Algoritma Genetika merupakan evolusi/perkembangan dunia komputer dalam bidang kecerdasan buatan (Artificial Intelligence).
Universitas Sumatera Utara
Algoritma Genetika terinspirasi dari teori evolusi Darwin yang menyatakan bahwa kelangsungan hidup suatu makhluk dipengaruhi aturan bahwa yang kuat adalah yang menang. Algoritma Genetika merupakan algoritma pencarian hasil terbaik yang berdasarkan atas perkawinan dan seleksi gen secara alami. Untuk lebih memahami tentang Algoritma Genetika, terlebih dahulu harus memahami konsep genetika (rekayasa genetika). Pengertian dari rekayasa genetika adalah penerapan genetika untuk kepentingan manusia, kegiatannya melalui seleksi dalam populasi, penerapan mutasi buatan dan perkawinan silang antara individu yang satu dengan yang lainnya untuk menghasilkan individu baru. Algoritma Genetika menggunakan istilah gen dalam menyimpan informasi, dimana gen merupakan struktur paling sederhana pada Algoritma Genetika. Solusi optimal direpresentasikan sebagai untaian gen yang disimpan dalam stukutur data yaitu kromosom. Kromosom merupakan material yang membawa bahan terwariskan dari gen. Proses pencarian solusi dilakukan dengan cara melakukan operasi terhadap kromosom yaitu rekombinasi kromosom yang dilakukan dengan persilangan dan mutasi dengan tujuan untuk memperoleh kromosom anak. Hal ini juga telah menjelaskan tentang konsep genetika. Algoritma Genetika pertama kali dikembagkan oleh John Holland dari Michigan University pada tahun 1975 dengan tujuan untuk meneliti proses adaptasi dari sistem alam serta mendesain perangkat lunak yang memiliki kecerdasan buatan dengan mencontoh mekanisme sistem alam. Algoritma Genetika banyak digunakan untuk proses optimasi. Salah satu masalah optimasi yang dapat diselesaikan dengan Algoritma Genetika adalah Travelling Salesman Problem atau lebih dikenal dengan TSP. Travelling Salesman Problem (TSP) adalah suatu kondisi dimana seorang salesman keliling yang harus mengunjungi n kota dengan aturan bahwa ia harus mengunjungi setiap kota hanya sebanyak satu kali, meminimalisasi total jarak perjalanannya dan pada akhirnya ia harus kembali ke kota asalnya. Salah satu masalah yang berhubungan dengan TSP adalah menentukan jalur yang terpendek dari rute beberapa kota. (sirkular : kota tujuan sama dengan kota asal). Problema Travelling Salesman Problem (TSP) berkembang terus secara nyata, dengan pencarian hasilnya diselesaikan dengan menggunakan Algoritma Genetika. Dari
Universitas Sumatera Utara
latar belakang inilah penulis memilih judul “Implementasi Algoritma Genetika untuk Travelling Salesman Problem ( TSP )”.
1.2 Perumusan Masalah Permasalahan yang dibahas dalam tugas akhir ini adalah penerapan Algoritma Genetika untuk menyelesaikan masalah Travelling Salesman Problem yaitu mencari jalur terpendek dari beberapa kota dengan hasil yang akurat dan menghasilkan rute terbaik yang optimal.
1.3 Batasan Masalah Agar permasalahan tidak menyimpang dari masalah yang dibahas, maka dalam pembahasan masalah terdapat batasan-batasan sebagai berikut : 1. Diasumsikan bahwa setiap kota yang terhubung selalu ada jalur yang menghubungkan antara satu kota dengan kota yang lainnya. 2. Kasus yang diambil adalah kota di Provinsi Jawa Barat dengan jumlah titik yang digunakan sebanyak 15 buah, dimana masing-masing titik mewakili kota yaitu Bekasi, Karawang, Indramayu, Purwakarta, Subang, Bogor, Cirebon, Cianjur, Sumedang, Sukabumi, Bandung, Kuningan, Garut, Tasikmalaya, Ciamis. 3. Jarak antar kota dihitung dengan bentuk euclidean 4. Parameter yang digunakan adalah ukuran populasi, peluang crossover, peluang mutasi, maksimum generasi dan panjang kromosom (jumlah gen).
1.4 Tujuan Penelitian Tujuan dari tugas akhir ini adalah mengimplementasikan Algoritma Genetika dalam masalah Travelling Salesman Problem dimana dalam hal ini masalah yang behubungan dengan TSP adalah mencari jalur terpendek dari beberapa jalur yang ada terhadap 15
Universitas Sumatera Utara
titik kota pada peta Jawa Barat yang diketahui koordinatnya dengan menggunakan Matlab 6.1.
1.5 Tinjauan Pustaka Dalam melakukan penelitian ini, penulis menggunakan beberapa pustaka sebagai referensi pendukung teori. Beberapa sumber pustaka yang diperkenalkan akan digunakan untuk membantu penulis menyelesaikan permasalahan dalam penelitian ini. Sumber pustaka yang digunakan adalah : Rachmayadi (2008) dalam jurnalnya yang berjudul Pencarian Solusi TSP (Travelling Salesman Problem) Menggunakan Algoritma Genetika, menguraikan mengenai struktur umum dari algoritma genetika adalah sebagai berikut : 1. Memilih populasi awal 2. Menghitung nilai fitness dari setiap individu 3. Repeat 3.1. Memilih indvidu-individu yang terbaik berdasarkan fungsi fitness untuk dilakukan reproduksi. 3.2. Menghasilkan generasi baru melalui reproduksi disertai operasi genetik berupa persilangan dan mutasi. 3.3. Menghitung nilai fitness generasi baru. 3.4. Mengganti individu-individu yang memiliki nilai fitness yang paling rendah dengan generasi baru yang nilai fitnessnya lebih baik. 4. Until terminasi. (terminasi dilakukan jika ditemukan solusi optimal, tidak ditemukan solusi yang lebih baik, atau waktu yang dialokasikan telah digunakan sepenuhnya).
Dalam Algorima Genetika adanya istilah populasi, individu, gen, kromosom, allela, locus, fitness, perkawinan silang, mutasi, generasi, seleksi, dan offspring (anak). Menurut Hendarto (2007) pengertian Populasi adalah sejumlah solusi yang mungkin. Populasi awal dibangun secara acak, sedangkan populasi berikutnya merupakan hasil
Universitas Sumatera Utara
evolusi kromosom-kromosom melalui iterasi yang disebut dengan generasi. Individu adalah kumpulan gen dalam sistem Algoritma Genetika bisa dikatakan sama dengan kromosom. Gen adalah substansi hereditas yang terletak di dalam kromosom. Generasi adalah iterasi yang dilakukan untuk menentukan populasi berikutnya. Kromosom adalah individu yang terdapat dalam satu populasi. Kromosom ini merupakan solusi yang masih berbentuk simbol. Allela merupakan nilai yang berada dalam gen. sedangkan Locus adalah letak suatu gen berada dalam suatu kromosom. Offsprings adalah anak (generasi berikutnya) yang terbentuk dari gabungan 2 kromosom. Generasi sekarang yang bertindak sebagai induk (parent) dengan menggunakan operator penyilangan (crossover) maupun operator mutasi. Suyanto (2005) dalam bukunya yang berjudul Algoritma Genetika dalam MATLAB menjelaskan tentang fungsi fitness. Suatu individu dievaluasi berdasarkan suatu fungsi tertentu sebagai ukuran performasinya. Di dalam evolusi alam, individu yang bernilai fitness tinggi yang akan bertahan hidup. Sedangkan individu yang bernilai fitness rendah akan mati. Kusumadewi (2003) dalam bukunya yang berjudul Artificial Intelligence (Teknik dan Aplikasinya) menjelaskan tentang perkawinan silang (crossover) yang dilakukan atas 2 kromosom untuk menghasilkan kromosom anak (offspring). Kromosom anak yang terbentuk akan mewarisi sebagian sifat kromosom induknya. Proses perkawinan silang ini bertujuan untuk menambah keanekaragaman kromosom digenerasi berikutnya berdasarkan kromosom dari generasi saat ini. Kusumadewi dan Purnomo (2005) dalam bukunya yang berjudul Penyelesaian Masalah Optimasi dengan Teknik-teknik Heuristik menjelaskan tentang mutasi menciptakan individu baru dengan melakukan modifikasi satu atau lebih gen dalam individu yang sama. Mutasi berfungsi untuk menggantikan gen yang hilang dari populasi selama proses seleksi serta menyediakan gen yang tidak ada dalam populasi awal. Mutasi dapat dilakukan dari semua gen yang ada dengan probabilitas mutasi tertentu. Jika bilangan random yang dibangkitkan kurang dari probabilitas mutasi yang ditentukan maka ubah gen tersebut menjadi nilai kebalikannya. Penjelasan tentang seleksi akan menentukan individu-individu mana saja yang akan dipilih untuk dilakukan rekombinasi dan bagaimana offspring terbentuk dari individu-
Universitas Sumatera Utara
individu terpilih tersebut. Langkah yang dilakukan adalah pencarian nilai fitness. Masing-masing individu dalam suatu wadah seleksi akan menerima probabilitas reproduksi yang tergantung pada nilai objektif dirinya sendiri terhadap nilai objektif dari semua individu dalam wadah seleksi tersebut. Nilai fitness inilah yang nantinya akan digunakan pada tahap-tahap berikutnya. Menurut Fitrah, Zaky dan Fitrasani (2006), Persoalan pedagang keliling (Travelling Salesman Problem/TSP) merupakan salah satu persoalan optimasi kombinatorial, jika diberikan sejumlah kota (atau tempat) dan biaya perjalanan dari satu kota ke kota lain. Deskripsi persoalannya adalah bagaimana menemukan rute perjalanan paling murah dari suatu kota dan mengunjungi semua kota lainnya, masing masing kota hanya dikunjungi satu kali, dan harus kembali ke kota asal keberangkatan. Kombinasi dari semua rute perjalanan yang ada adalah faktorial dari jumlah kota. Biaya perjalanan bisa berupa jarak, waktu, bahan bakar, kenyamanan, dan sebagainya. Travelling Salesman Problem (TSP) dapat direpresentasikan dalam bentuk graph, dengan memisalkan kota sebagai verteks dan jalur penghubung antar kota dengan edge. Siang (2002) dalam bukunya yang berjudul Matematika Diskrit dan Aplikasinya dalam ilmu komputer menyatakan tentang sirkuit hamilton. Suatu graph terhubung G disebut sirkuit hamilton bila ada sirkuit yang mengunjungi setiap titiknya tepat 1 kali (kecuali titik awal yang sama denga titik akhirnya). Pencarian sirkuit hamilton dapat memecahkan problema kasus Travelling Salesman Problem.
1.6 Kontribusi Penelitian Selain menambah pemahaman dan pengetahuan penulis mengenai Algoritma Genetika dalam menyelesaikan Travelling Salesman Problem, dengan mengadakan penulisan ini penulis juga dapat menjadikannya sebagai sarana untuk mengaplikasikan materi-materi yang telah didapat dibangku kuliah. Penulis juga berharap dapat menambah referensi dan wawasan bagi pembaca maupun programmer untuk menggunakan Algoritma Genetika sebagai algoritma yang tepat untuk menyelesaikan problema TSP.
Universitas Sumatera Utara
1.7 Metodologi Penelitian Metode yang digunakan pada penelitian ini merupakan metode pengumpulan data dan bersifat literatur pada teori-teori dari Algoritma Genetika dan Travelling Salesman Problem sebagai studi kasusnya. Langkah pertama yang dilakukan yaitu menjelaskan tentang Travelling Salesman Problem, Algoritma Genetika dan Sirkuit Hamilton. Langkah selanjutnya adalah menjelaskan penggunaan dan pengembangan Algoritma Genetika dalam menentukan jalur terpendek pada masalah Travelling Salesman Problem dengan terlebih dahulu menentukan parameternya. Mengerjakannya secara bertahap
dengan
Algoritma
Genetika
dimulai
dari
pengkodean
kromosom,
menginisialisasi populasinya, menentukan nilai fitness, melakukan proses seleksi, crossover dan mutasi. Selanjutnya mengimplementasikannya dengan menggunakan Matlab 6.1.
Universitas Sumatera Utara
