Library Automation and Digital Archive
LONTAR
Fakultas Ilmu Komputer
Universitas Indonesia

Pencarian Sederhana

Find Similar Add to Favorite

Call Number T-0045
Collection Type Tesis
Title Pemecahan TSP (Traveling salesperson problem) dengan jaringan neural hopfield
Author Peter Rhatodirdjo Angka;
Publisher Jakarta: Pascasarjana MTI UI, 1994
Subject Traveling-salesman problem
Location FASILKOM-UI;
Lokasi : Perpustakaan Fakultas Ilmu Komputer
Nomor Panggil ID Koleksi Status
T-0045 95/7162 TERSEDIA
Tidak ada review pada koleksi ini: 8268
Travelling Salesperson Problem (TSP) merupakan masalah optimasi kombinatorial klasik. Semua algoritma konvesional yang dikenal saat ini untuk pemecahan TSP, membutuhkan usaha komputasi yang meningkatkan secara eksponensial terhadap jumlah kota. Dalam tulisan ini dibahas jaringan neural Hopfield dengan maukan kontinyu sebagai alternatif pemecahan TSP. Jaringan neural ini memecahkan TSP dengan kompleksitas komputasi sebanding dengan polinomial pangkat 4 dari jumlah kota. Komputasi jaringan neural ini efektif, karena adanya tanggapan analog non-linear dari neuron dan konektifitas yang besar diantara neuron. Metode ini hanya memberikan penyelesaian minimum lokal, yang diharapkan mendekati minimum global. Implementasi jaringan neural ini disimulasikan pada komputer sekuensial. Komputer yang digunakan berupa workstation SUN SPARC 1+ berbasis UNIX dengan kapasitas memori 8 mb. Kinerja metode jaringan neural Hopfield dievaluasi berdasarkan jarak tour dan waktu yang dibutuhkan. Kemudian hasilnya dibandingkan dengan penyelesaian optimal yang diperoleh dengan algoritme konvesional least cost Branch and Bound (LCBB). Dari hasil eksekusi program pada workstation SUN SPARC 1+ berbasis UNIX untuk jumlah kota 15 s/d 22 buah diperoleh jarak tour rata-rata dengan metode jaringan neural berkisar antara 1.63 s/d 2,06 kali jarak tour dengan algoritme LCBB. Waktu rata-rata yang dibutuhkan jaringan neural (Jumlah kota 15 s/d 22 buah) sebesar 4/10 sampai dengan 4x10 kali waktu yang dibutuhkan algoritme LCBB. Pada jumlah kota 5 s/d 14 buah, hasil dari jaringan neural kurang bagus dibandingkan dengan hasil dari algoritme LCBB. Jarak tour rata-rata dengan jaringan neural Hopfield berkisar antara 1.01 s/d 1.45 kali jarak tour dengan algoritme LCBB, tetapi waktu yan dibutuhkan jaringan neural Hopfield sebesar 1 s/d 10 kali waktu yang dibutuhkan algoritme LCBB.