DETAIL KOLEKSI

Perbandingan genetic algorithm dan ant colony system dalam menyelesaikan travelling salesman problem


Oleh : Nur Trismi Auliah A.

Info Katalog

Penerbit : FTI - Usakti

Kota Terbit : Jakarta

Tahun Terbit : 2012

Pembimbing 1 : Djasli Djamarus

Subyek : Comparison of genetic algorithm;Ant colony system

Kata Kunci : travelling salesman problem, genetic algorithm, ant colony system.


File Repositori
No. Nama File Ukuran (KB) Status
1. 2012_TA_IF_06407044_1_Halaman-Judul.pdf 2272.53
2. 2012_TA_IF_06407044_8_Daftar-Pustaka.pdf 624.84
3. 2012_TA_IF_06407044_9_Lampiran.pdf 1835.68

P Pokok permasalahan dari Traveling Salesman Problem (TSP) adalah menentukan rute terpendek dari perjalanan seorang salesman yang harus mengunjungi sejumlah kota dengan syarat semua kota yang ada harus dikunjungi tepat satu kali dan perjalanan diakhiri dengan kembali ke kota semula. TSP merupakan salah satu masalah optimasi yang membutuhkan waktu yang sangat lama apabila diselesaikan dengan algoritme eksak. Oleh karena itu, digunakanlah metode pendekatan (heuristic) seperti Genetic Algorithm dan Ant Colony System untuk mencari solusi TSP. Genetic Algorithm merupakan teknik pencarian dan optimasi yang terinspirasi oleh proses seleksi alam dalam suatu populasi. Algoritme ini bermula dari himpunan solusi yang dihasilkan secara acak yang disebut sebagai populasi. Setiap individu dalam populasi tersebut disebut kromosom yang merupakan representasi dari solusi. Algoritme Genetika terdiri dari tiga operasi, yaitu operasi reproduksi, operasi crossover (persilangan) dan operasi mutasi. Algoritme Ant Colony System merupakan salah satu algoritme yang terinspirasi dari perilaku semut dan dapat diterapkan untuk menyelesaikan TSP. Secara alamiah sekumpulan semut mampu menemukan rute terpendek dalam perjalanan dari sarang ke tempat- empat sumber makanan. Koloni semut dapat menemukan rute terpendek antara sarang dan sumber makanan berdasarkan jejak zat pheromone yang ditinggalkan. Dalam ACS terdapat tiga aturan yang harus diterapkan yaitu aturan state transition, local updating dan global updating. Dalam tugas akhir ini, telah dibuat sem= software yang dapat digunakan untuk membandingkan hasil dan waktu eksekusi dari Genetic Algorithm dan Ant Colony System dalam menyelesaikan TSP. Software ini dikembangkan dengan menggunakan bahasa pemrograman Java yang berorientasi objek. Uji coba dilakukan dengan mencari solusi dari beberapa kasus TSP dengan jumlah titik n=20 sampai n=115. Hasil mendekati optimal diperoleh dengan melakukan beberapa kali percobaan untuk setiap kasus. Selanjutnya hasil perhitungan dan waktu eksekusi untuk setiap kasus dan setiap algoritme dibandingkan. Dan hasil uji coba tersebut, terlihat bahwa algoritme ACS memiliki performa yang lebih baik dalam menentukan solusi TSP dibandingkan dengan algoritme Genetika.

T The main idea of the Traveling Salesman Problem (TSP) is determine the shortest route of the journey of a salesman who must visit a number of cities and the requirement is all existing city must be visited exactly once and the ends of the trip is back to the first city. TSP is one of the optimization problem that requires a very long time if solved with exact algorithms. Therefore, the approximation method is used such as Genetic Algorithm and Ant Colony System to find a solution of TSP. Genetic Algorithm is a search and optimization techniques inspired by the process of natural selection in a population. This algorithm starts from the set of randomly generated solutions called population. Each individual in the population are called chromosomes, which is a representation of the solution. Genetic algorithm consists of three operations, namely reproduction operation, crossover operation and mutation operations. Ant Colony System algorithm is one of the algorithms are inspired by ant behavior and can be applied to solve the TSP. Naturally, colony of the ants are able to find the shortest route on the way from nest to food source. Colony of ants can find shortest route between the nest and food sources based on the pheromone trail left by the substance. In ACS there are three flees that must be applied, namely state transition rule, local updating and global u#dating. In this fmal project, has made software that can be used to compare results and execution time of the Genetic Algorithm and Ant Colony System to solve TSP. This software is developed using Java programming language that is object oriented. A trial was made by finding the solution of some cases of the TSP by the number of city n=20 to n=115. The optimal results obtained by performing the experiment several times for each case. Furthermore, the results of calculation and execution time for each case and each algorithm were compared. From the results of these experiments, shows that the ACS algorithm has better performance in determining a solution of TSP compared with Genetic Algorithm.

Bagaimana Anda menilai Koleksi ini ?