APLIKASI ANT COLONY SYSTEM UNTUK TRAVELLING SALESMAN PROBLEM
HAVEA PERTIWI

Informasi Umum

Kode

112050118

Klasifikasi

005.36 - Program for Personal Computer, Information System

Jenis

Karya Ilmiah - Skripsi (S1) - Reference

Subjek

Application Programs

Dilihat

48 kali

Informasi Lainnya

Abstraksi

Travelling Salesman Problem (TSP) adalah suatu permasalahan klasik mengenai pencarian rute yang optimal untuk sejumlah n kota, dengan aturan bahwa setiap kota harus dikunjungi tepat satu kali kecuali kota awal. Optimalisasi yang dimaksud disini yaitu dilihat dari sisi jarak.<br> Banyak alternatif-alternatif rute yang mungkin yaitu berjumlah permutatif terhadap N diperoleh dari persamaan (N-1)!/2. Misalnya jumlah kota yang akan didatangi sejumlah 15 kota (N=15) maka akan didapatkan rute alternatif sekitar 653.837.184.000 rute. Untuk N=70 maka rute alternatif yang akan diseleksi sekitar 8.556*1097 rute. Hal ini berarti bahwa untuk N besar, ukuran masalah juga membesar secara supereksponensial.<br> Banyak metode heuristik yang dapat digunakan untuk menyelesaikan permasalahan TSP, salah satunya yaitu Ant Colony System (ACS). ACS merupakan bagian dari Ant Colony Optimization, yaitu algoritma yang terinspirasi dari tingkah laku semut di dunia nyata pada saat proses pencarian makan.<br> Dalam proses perhitungannya, ACS terdiri dari tiga fase utama yaitu fase inisialisai, pembentukkan tur, dan fase update global. Pada saat proses pemilihan ruas yang dilaluinya semut sangat dipengaruhi oleh intensitas pheromone dan juga oleh jarak antar ruas. Dimana pheromone tersebut digunakan sebagai alat komunikasi secara tidak langsung. Semakin tinggi intensitas pheromone pada ruas tersebut maka semakin besar probabilitas ruas tersebut untuk dilewati atau dipilih.<br> Karena metode ACS merupakan metode heuristik, maka tidak ada jaminan bahwa solusi yang dihasilkan benar-benar optimal. Namun metode ini banyak dipilih karena waktu dan biaya yang relatif lebih rendah dibandingkan dengan metode yang bukan heuristik.<br> Untuk hasil dari penyelesaian dengan menggunakan metode Ant Colony System juga akan dibandingkan dengan hasil dari metode-metode yaitu Simulated Annealing, Teori Nearest Neighbour by 2-Opt dan Teori Interaksi Gani.<br> ant colony, ACS, TSP

Koleksi & Sirkulasi

Tersedia 1 dari total 1 Koleksi

Pengarang

Penerbit

Sirkulasi

Download / Flippingbook