Travelling salesman problem menggunakan menggunakan jaringan hopfield

Oleh :
Saptini Kurnia Sari - M0104058 - Fak. MIPA

ABSTRAK. Travelling Salesman Problem (TSP) merupakan permasalahan optimasi yang mempunyai konsep sederhana dan mudah untuk dipahami tetapi memiliki penyelesaian yang sulit. Optimasi yang diinginkan pada TSP adalah menemukan rute perjalanan terpendek. Jika terdapat n kota yang harus dilewati ( 3 n ≥ ) maka ada !/ 2 n npilihan rute yang dapat ditempuh, sehingga semakin banyak jumlah kota semakin sulit untuk menentukan rute dengan jarak minimum. Jaringan Hopfield merupakan model Jaringan Syaraf Tiruan (JST) yang dapat digunakan untuk menyelesaikan permasalahan tersebut. Jaringan Syaraf Tiruan memodifikasi tingkah laku sesuai keadaan lingkungannya dan mengatur dirinya sendiri untuk menghasilkan suatu respon yang konsisten terhadap serangkaian inputan. Proses modifikasi tersebut selesai pada saat mencapai konvergen. Hopfield bekerja dengan meminimalkan fungsi energi dan pada saat konvergen itulah diperoleh energi jaringan yang minimal. Pada saat energi minimal diperoleh pula rute minimum yang merupakan penyelesaian dari TSP. Pemilihan parameter pada fungsi energi sangat penting untuk konvergensi jaringan ke suatu rute TSP dan solusi optimum yang dihasilkan jaringan Hopfield. Dari hasil percobaan menggunakan bahasa pemrograman Delphi 7.0, jaringan dapat konvergen membentuk rute untuk TSP pada kasus 4 kota hingga 10 kota, akan tetapi dilihat dari banyak rute TSP yang dihasilkan, untuk jumlah kota yang lebih besar dari 5 kota, jaringan Hopfield bukan merupakan solusi yang baik untuk permasalahan ini.