Jurnal Computech & Bisnis (e-Journal)
Vol 3, No 1 (2009): Jurnal Computech & Bisnis

STUDI KOMPARATIF ALGORITMA ANT DAN ALGORITMA GENETIK PADA TRAVELLING SALESMAN PROBLEM

Bambang Siswoyo (Unknown)
Andrianto . (Unknown)



Article Info

Publish Date
12 Feb 2015

Abstract

Travelling Salesman Problem ( TSP ) is a problem in which a trader must make a circuit or a route through several cities, where each city is visited only once and to minimize the total distance traveled . The limit is that every city that passed only once visited, and the merchant must return to the city of origin at the end of his journey . The program searches the shortest distance made, based on two algorithms namely genetic algorithms and Ant Colony System ( ACS ) . Genetic algorithm is an algorithm that works based on the mechanism of natural selection and natural genetics. The main idea behind this algorithm is to choose the best individuals from a population of individuals and between individuals recombination to generate new individuals are expected to be better than the previous individual. Ant Colony System is an algorithm that uses the workings of the ant colony to solve TSP problem. At ACS, there are a set of ants working together to determine the best solution TSP, ants working together through indirect communication using pheromone trail deposited on the sides of the graph TSP. From the difference of this approach, will be studied and compared the ability of each approach in solving the TSP . Keywords: Traveling Salesman Problem , Genetic Algorithms , Ant Colony System  Abstrak Travelling Salesman Problem (TSP) yaitu sebuah masalah dimana seorang pedagang harus membuat suatu sirkuit atau rute melalui beberapa kota, dimana setiap kota hanya dikunjungi sekali dan dengan meminimalkan total jarak yang dilalui. Batasannya adalah bahwa setiap kota yang dilalui hanya sekali dikunjungi,  dan pedagang tersebut harus kembali ke kota asal pada akhir perjalanannya. Program pencarian jarak terpendek yang dibuat, didasarkan pada dua algoritma yaitu algoritma genetik dan algoritma Ant Colony System (ACS). Algoritma genetik adalah algoritma yang bekerja berdasarkan mekanisme seleksi alam dan genetika alam. Ide utama dibalik algoritma ini adalah memilih individu-individu terbaik dari sebuah populasi individu dan melakukan rekombinasi antar individu untuk membangkitkan individu baru yang diharapkan lebih baik dari individu sebelumnya. Ant Colony System adalah algoritma yang menggunakan cara kerja koloni semut untuk memecahkan masalah TSP. Pada ACS ini terdapat sekumpulan semut yang bekerja sama untuk menentukan solusi TSP yang paling baik, semut-semut bekerja sama melalui  komunikasi tidak langsung dengan menggunakan jejak pheromone yang disimpan pada sisi-sisi dari graph TSP. Dari perbedaan pendekatan ini, akan dipelajari dan diperbandingkan kemampuan masing-masing pendekatan dalam menyelesaikan TSP. Kata kunci: Travelling Salesman Problem, Algoritma Genetik, Ant Colony System 

Copyrights © 2015






Journal Info

Abbrev

jcb

Publisher

Subject

Computer Science & IT Control & Systems Engineering Economics, Econometrics & Finance Education Library & Information Science

Description

The scope of this journal covering the field Computer, Technology and Business. Topic related to these fields can be information systems, informatics, product based knowledge, computer science, knowledge management, business and management, business IT, IT Governance, communication and marketing, ...