Perbandingan Masalah Optimasi TSP dengan Menggunakan Algoritma Ant Colony dan Jaringan Hopfield

Perbandingan Masalah Optimasi TSP dengan Menggunakan Algoritma Ant Colony dan Jaringan Hopfield 1

Yuliani, 2Moh.Isa Irawan, dan 3Mardlijah

1, 2, 3

Jurusan Matematika, Institut Teknologi Sepuluh November Kampus ITS, Surabaya 60111 – Indonesia Email: [email protected], [email protected].

Abstrak. Travelling Salesman Problem (TSP) adalah suatu problem yang dialami oleh seorang sales yang ingin memulai perjalanannya dari satu kota menuju kota tertentu dengan hanya dapat melalui kota lainnya sekali dan ia menginginkan dalam perjalanannya, ongkos dan waktu yang dikeluarkan dapat seoptimum dan seminimal mungkin. Algoritma Ant colony dan jaringan Hopfield merupakan metode optimasi yang dapat menyelesaikan berbagai macam masalah, sehingga dalam penelitian ini diujicobakan kedua metode optimasi tersebut untuk menyelesaikan masalah TSP. Penyelesaian masalah TSP ini menghasilkan path terpendek dari masing – masing algoritma yang digunakan. Dalam pencarian path terpendek tidak dapat dikatakan secara langsung algoritma mana yang paling optimum untuk keseluruhan kasus, karena selalu tergantung dari setiap kondisi permasalahan yang ada, dan kondisi yang paling mempengaruhi adalah banyaknya titik. Dalam penelitian ini juga dilakukan perbandingan path terpendek antara algoritma Ant colony dan jaringan Hopfield. Hasil yang diharapkan penyelesaian masalah optimasi TSP dengan menggunakan algoritma Ant Colony itu lebih baik daripada jaringan Hopfield. Kata kunci: Algoritma ant colony, Jaringan Hopfield

Seminar Nasional Matematika IV Institut Teknologi Sepuluh November, Indonesia, 13 Desember 2008

Perbandingan Masalah Optimasi TSP dengan Menggunakan Algoritma Ant Colony dan Jaringan Hopfield 1

Yuliani, 2Moh.Isa Irawan, dan 3Mardlijah

1, 2, 3

Jurusan Matematika, Institut Teknologi Sepuluh November Kampus ITS, Surabaya 60111 – Indonesia

Email: [email protected], [email protected], [email protected]

Abstrak. Travelling Salesman Problem (TSP) adalah suatu problem yang dialami oleh seorang sales yang ingin memulai perjalanannya dari satu kota menuju kota tertentu dengan hanya dapat melalui kota lainnya sekali dan ia menginginkan dalam perjalanannya, ongkos dan waktu yang dikeluarkan dapat seoptimum dan seminimal mungkin. Algoritma Ant colony dan jaringan Hopfield merupakan metode optimasi yang dapat menyelesaikan berbagai macam masalah, sehingga dalam penelitian ini diujicobakan kedua metode optimasi tersebut untuk menyelesaikan masalah TSP. Penyelesaian masalah TSP ini menghasilkan path terpendek dari masing – masing algoritma yang digunakan. Dalam pencarian path terpendek tidak dapat dikatakan secara langsung algoritma mana yang paling optimum untuk keseluruhan kasus, karena selalu tergantung dari setiap kondisi permasalahan yang ada, dan kondisi yang paling mempengaruhi adalah banyaknya titik. Dalam penelitian ini juga dilakukan perbandingan path terpendek antara algoritma Ant colony dan jaringan Hopfield. Hasil yang diharapkan penyelesaian masalah optimasi TSP dengan menggunakan algoritma Ant colony itu lebih baik daripada jaringan Hopfield. Kata kunci: Algoritma ant colony, Jaringan Hopfield

1. Pendahuluan Setiap hari seseorang pasti melakukan suatu perjalanan, baik itu perjalanan dari rumah ke kantor ataupun dari rumah ke kampus. Dan mungkin juga perjalanan ke beberapa kota. Dalam melakukan perjalanan ke beberapa kota, sering seseorang menginginkan path terpendek dan biaya yang minimal. Masalah ini sering disebut dengan Travelling Salesman Problem (TSP). Travelling Salesman Problem (TSP) adalah suatu problem yang dialami oleh seorang sales yang ingin memulai perjalanannya dari satu kota menuju kota tertentu dengan hanya dapat melalui kota lainnya sekali dan ia menginginkan dalam perjalanannya, ongkos dan waktu yang dikeluarkan dapat seoptimum dan seminimal mungkin. Dengan persoalan yang dideskripsikan sebagai berikut: Diberikan n buah kota serta diketahui jarak antara setiap kota satu sama lain. Carilah perjalanan terpendek yang dimulai dari sebuah kota dan melalui setiap kota lainnya hanya sekali dan kembali lagi ke kota asal keberangkatannya. Pada penelitian sebelumnya, Helvig dkk (2007) mengenalkan moving-target travelling salesman problem dimana target dapat bergerak dengan kecepatan konstan. Pada awal tahun 1990 ditemukan oleh Dorigo pendekatan heuristik dalam menyelesaikan Travelling Salesman Problem dengan menggunakan algoritma Ant colony. Algoritma Ant colony yang ditemukan dari perilaku semut dalam pencarian makanan dan secara tidak langsung komunikasi mereka melalui pheromone. Algoritma Ant colony telah diaplikasikan pada beberapa masalah antara lain job scheduling, routing optimization dalam jaringan komunikasi data, dan jaringan telepon. Kemudian pada tahun 1982 dikembangkan oleh John Hopfield suatu metode optimasi dari jaringan syaraf tiruan yang kemudian dikenal dengan jaringan Hopfield. Jaringan Hopfield merupakan salah satu metode optimasi untuk pencarian nilai minimum dari fungsi obyektif. Algoritma Ant colony dan jaringan Hopfield merupakan metode optimasi yang dapat menyelesaikan berbagai macam masalah, sehingga dalam penelitian ini diujicobakan kedua metode optimasi tersebut untuk menyelesaikan masalah TSP. Penyelesaian masalah TSP ini menghasilkan path terpendek dari masing – masing algoritma yang digunakan. Dalam lingkup pencarian path terpendek ini tidak dapat dikatakan secara langsung algoritma mana yang paling optimum untuk keseluruhan kasus, karena belum tentu suatu algoritma yang memiliki optimasi yang tinggi untuk suatu kasus memiliki optimasi yang

tinggi pula untuk kasus yang lain. Optimasi yang mencakup efisiensi waktu proses kerja algoritma, waktu tempuh yang diperlukan untuk mencapai tujuan akhir dan jarak tempuh yang paling pendek ini selalu tergantung dari setiap kondisi permasalahan yang ada. Dan kondisi yang paling mempengaruhi adalah banyaknya titik (titik yang dalam hal ini mewakili kota). Dalam penelitian ini juga dilakukan perbandingan antara algoritma Ant colony dan jaringan Hopfield.

2. Kajian pustaka Dalam bab ini akan dikemukakan beberapa teori-teori yang dipandang mendukung TSP (Traveling Salesman Problem) untuk mengoptimasi rute perjalanan sales dengan path terpendek. 2.1 Optimasi Definisi Optimasi Optimasi adalah suatu proses untuk mencapai solusi yang terbaik atau optimal dalam suatu masalah (nilai efektif yang dapat dicapai). Dalam disiplin matematika optimasi merujuk pada studi permasalahan yang mencoba untuk mencari nilai minimal atau maksimal dari suatu fungsi tertentu. Untuk dapat mencapai nilai optimal baik minimal atau maksimal tersebut, secara sistematis dilakukan pemilihan nilai variabel yang akan memberikan solusi optimal (Clapham, 1996). Beberapa Persoalan Optimasi Persoalan yang berkaitan dengan optimasi sangat kompleks dalam kehidupan sehari – hari. Nilai optimal yang didapat dalam optimasi dapat berupa besaran panjang, waktu, jarak, dan lain – lain (Wardy, 2008). Berikut ini adalah beberapa persoalan yang memerlukan optimasi: 1. Menentukan lintasan terpendek dari suatu tempat ke tempat yang lain. 2. Menentukan jumlah pekerja seminimal mungkin untuk melakukan suatu proses produksi agar pengeluaran biaya pekerja dapat diminimalkan dan hasil produksi tetap maksimal. 3. Mengatur jalur kendaraan umum agar semua lokasi dapat dijangkau. 4. Mengatur routing jaringan kabel telepon agar biaya pemasangan kabel tidak terlalu besar dan penggunaannya tidak boros. Selain beberapa contoh diatas, masih banyak persoalan lainnya yang terdapat dalam kehidupan sehari – hari. 2.2 Graph Graph (G) adalah himpunan pasangan terurut (V, E), dimana V adalah himpunan vertex/titik dan E adalah himpunan edge/rusuk. Sebuah graph ditulis sebagai pasangan order (v, e) atau lengkapnya G = (v, e), dimana diasumsikan v ∈ V dan E merupakan himpunan edge – edge e = (vi ,vj) dimana e ∈ E (Wibisono, 2004). Graph terbagi menjadi beberapa macam diantaranya adalah sebagai berikut (Siang, 2004): a. Graph berarah (Directed Graph) adalah graph yang setiap edgenya mempunyai arah dengan memenuhi persyaratan (vi ,vj) ≠ (vj ,vi) dimana (vi ,vj) ∈ E. b. Graph tidak berarah (Undirected Graph) adalah graph yang setiap edgenya tidak mempunyai arah dengan memenuhi persyaratan (vi ,vj) = (vj ,vi) dimana (vi ,vj) ∈ E. c. Graph berbobot (Weighted Graph) adalah graph yang setiap edgenya mempunyai bobot sebesar w. 2.3 Algoritma Ant Colony Pada awal tahun 1990, sebuah algoritma bernama Ant system dicetuskan sebagai pendekatan heuristik baru untuk pencarian solusi dari kombinasi masalah optimasi (Dorigo, 1999). Algoritma ini dikembangkan berdasarkan hasil pengamatan tingkah laku semut dalam mencari makanan. Semut – semut secara berkelompok mencari jalur terpendek dari sarang ke sumber makanan ataupun sebaliknya. Pada saat semut – semut berjalan, mereka menyimpan suatu zat pheromone di sepanjang jalan yang dilaluinya. Pheromone adalah zat kimia yang berasal dari kelenjar endokrin dan digunakan oleh makhluk hidup untuk mengenali sesama jenis, individu lain, kelompok, dan untuk membantu proses reproduksi. Berbeda dengan hormon, pheromone menyebar keluar tubuh dan hanya dapat mempengaruhi dan dikenali oleh individu lain yang sejenis (satu spesies). Semut – semut dapat mencium pheromone yang ditinggalkan untuk menentukan langkah selanjutnya, mereka akan memilih pheromone dengan konsentrasi kuat. Jalur dengan pheromone konsentrasi kuat menandakan telah dilalui oleh banyak semut, yang akhirnya merupakan rute terpendek (Zha, 2007).

(1) Semua semut berada di sarang, tidak ada pheromone ditanah

(2) Proses mencari makanan mulai dengan probabilitas 50% semut akan memilih jalur terpendek (ditandai dengan bulatan) dan 50% semut akan memilih jalur yang panjang (ditandai dengan persegi)

(3) Semut – semut yang mengambil jalan terpendek lebih dulu sampai, karena itu probabilitas mengambil jalur yang sama saat kembali lebih besar.

(4) Jejak pheromone yang ada di jalur pendek (dalam probabilitas) memberikan aroma lebih tajam, sehingga probabilitas memilih jalur ini lebih besar. Dan dengan adanya penguapan pada jalur panjang, seluruh koloni (dalam probabilitas) akan memilih jalur pendek. Gambar 1. Diagram yang menunjukkan kemampuan semut dalam mencari jalur terpendek. Antara sarang semut dan sumber makanan terdapat dua jalur dengan panjang yang berbeda. Pada grafik keempat, jejak pheromone ditunjukkan oleh garis putus – putus yang ketebalannya menunjukkan kekuatan jejak. (Blum, 2005).

Dari gambar di atas, terlihat bahwa jalur yang lebih pendek akan memiliki kemungkinan lebih besar untuk dipilih oleh semut berikutnya. Hal ini disebabkan oleh jarak yang ditempuh sangat pendek sehingga waktu perpindahan menjadi lebih singkat. Ketika semut lain masih menyusuri jalur yang lebih panjang, semut yang memilih jalur pendek dapat memulai rute pulang yang sama, dan memperkuat intensitas pheromone pada jalur tersebut. Karena intensitas pheromone yang lebih kuat, maka probabilitas jalur pendek untuk dilewati oleh semut berikutnya lebih besar dibandingkan dengan probabilitas jalur panjang. Algoritma ant colony atau siklus semut untuk penyelesaian masalah Traveling Salesman Problem (Kusumadewi, 2005), diberikan sebagai berikut:

Langkah 1: a. Inisialisasi nilai parameter-parameter algoritma. 1. Intensitas jejak semut antar kota dan perubahannya (τ i j )

b.

2. 3. 4.

Banyak kota (N) termasuk x dan y (koordinat) atau dij (jarak antar kota) Q adalah tetapan siklus semut. Parameter pengendali intensitas jejak semut (α )

5.

Parameter pengendali visibilitas ( β )

6.

Visibilitas antar kota (η ij ) =

7. 8.

Banyak semut (m) Koefisien penguapan jejak semut ( ρ )

9.

Jumlah siklus maksimum (NCmax) bersifat tetap selama algoritma dijalankan, sedangkan

1 dij

τi j

akan selalu diperbaharui harganya pada setiap siklus algoritma mulai dari siklus pertama (NC = 1) sampai tercapai jumlah siklus maksimum (NC = NCmax) atau sampai terjadi konvergensi. Inisialisasi kota pertama setiap semut. Inisialisasi τ i j dengan bilangan yang cukup kecil, kemudian m semut ditempatkan pada kota

pertama tertentu secara acak. Langkah 2: Pengisian kota pertama ke dalam tabu list. Langkah 3: Penyusunan rute kunjungan setiap semut ke setiap kota. Untuk menentukan kota tujuan digunakan persamaan probabilitas kota untuk dikunjungi sebagai berikut:

p (t ) = k ij

[τ ij (t )]α [ηij ]β

∑

k ' ∈ { N −Tabuk }

[τ ik ' (t )]α [ηik ' ]β

untuk j ∈ {N − Tabuk } (1)

dan pijk = 0, untuk j lainnya dengan i sebagai indeks kota asal dan j sebagai indeks kota tujuan. Probabilitas ke kota yang akan dituju berikutnya (pij), disini diperoleh dari persamaan (1) kemudian dibangkitkan bilangan random (r) antara 0 sampai 1. Kota ke-k akan terpilih jika r lebih kecil dari nilai probabilitasnya. Langkah 4: a. Perhitungan panjang rute setiap semut. Perhitungan panjang rute tertutup (length closed tour) atau Lk setiap semut dilakukan setelah satu siklus diselesaikan oleh semua semut. Perhitungan dilakukan berdasarkan tabuk masing-masing dengan persamaan berikut:

Lk = dtabuk ( N ), tabuk (1) +

N −1

∑d s =1

tabuk ( s ), tabuk ( s +1)

(2)

Dengan dij adalah jarak antara kota i ke kota j yang dihitung berdasarkan persamaan:

di j = ( xi − x j ) 2 + ( yi − y j ) 2 b.

c.

(3)

Pencarian rute terpendek. Setelah Lk setiap semut dihitung, akan didapat harga minimal panjang rute tertutup setiap siklus atau LminNC dan harga minimal panjang rute tertutup secara keseluruhan atau Lmin. Perhitungan perubahan harga intensitas jejak kaki semut antar kota.

Persamaan perubahan ini dihitung dengan rumus: m

∆τ i j =

∑ ∆τ

Dengan

∆ τ ikj adalah perubahan harga intensitas jejak kaki semut antar kota setiap semut yang

k =1

k ij

(4)

dihitung berdasarkan persamaan

Q Lk untuk (i, j) ∈ kota asal dan kota tujuan dalam tabuk. ∆ τ ikj =

(5)

∆ τ ikj = 0 , untuk (i, j) lainnya

(6)

Langkah 5: a. Perhitungan harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya. Harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya dihitung dengan persamaan:

τ i j = ρτ i j + ∆ τ i j

(7)

b.

Atur ulang harga perubahan intensitas jejak kaki semut antar kota. Untuk siklus selanjutnya perubahan harga intensitas jejak semut antar kota perlu diatur kembali agar memiliki nilai sama dengan nol. Langkah 6: Pengosongan tabu list, dan ulangi langkah 2 jika diperlukan atau belum terjadi konvergensi. Algoritma diulang lagi dari langkah 2 dengan harga parameter intensitas jejak kaki semut antar kota yang sudah diperbaharui. 2.4 Algoritma Neural Network Hopfield Algoritma Neural Network Hopfield pertama kali dikenalkan oleh John Hopfield dari California Institute of Technology pada tahun 1982. John Hopfield merancang sebuah jaringan syaraf tiruan yang kemudian dikenal dengan nama jaringan Hopfield. Dalam jaringan Hopfield semua neuron berhubungan penuh. Neuron yang satu mengeluarkan output dan kemudian menjadi input untuk semua neuron yang lain. Proses penerimaan sinyal antara neuron ini secara feedback tertutup terus menerus sampai dicapai kondisi stabil (Dayhoff, 1990). Koneksi antara unit adalah bidirectional, sedemikian sehingga matriks bobot adalah symmetric; yaitu, koneksi dari unit ui ke unit uj (dengan bobot wij) adalah sama halnya dengan koneksi dari uj ke ui (dengan bobot wij).

Gambar 2. Layout dari JST Hopfield Hopfield-Tank menyatakan energi fungsi untuk masalah TSP adalah:

A B C⎡ ⎤ E = ∑∑∑ v x ,i v x , j + ∑∑∑ v x ,i v y .i + ⎢ N − ∑∑ v x.i ⎥ 2 x i j ≠i 2 i x y≠ x 2⎣ x i ⎦ D + ∑∑∑ d x , y v x ,i v y ,i +1 + v y ,i −1 2 x y≠x i

(

)

dimana: A, B, C, D = konstanta yang harus ditentukan tergantung jumlah kota

2

(8)

Sinyal outputnya diberikan dengan menerapkan fungsi sigmoid (dengan range antara 0 dan 1), yang mana Hopfield dan Tank menyatakan sebagai:

v = g (u ) = 0.5[1 + tanh (α u )] i

i

(9)

i

dimana:

α = learning rate yang telah ditentukan Algoritma Prosedur dasar untuk memecahkan masalah traveling salesman menggunakan jaringan Hopfield diuraikan sebagai berikut. Step 0 Initialisasi aktivasi pada semua unit Step 1

Initialisasi ∆t untuk nilai kecil jika kondisi belum terpenuhi, lanjutkan Step 2-6 Step 2 Lakukan langkah 3-5 sebanyak n2 kali (n adalah banyaknya kota) Step 3 memilih suatu unit secara random Step 4 Mengubah aktivitas pada unit terpilih:

u x ,i (baru ) = u x ,i (lama ) + ∆t[ −u x ,i (lama ) − A∑ v x , j j ≠i

− ∑ v y ,i + C{N − ∑∑ v x , j } − D ∑ d x , y (v y ,i +1 + v y ,i _ 1 ) y≠ x

x

y≠ x

j

Step 5 Aplikasikan fungsi output

vx ,i = 0,5 ⎡⎣1 + tanh(α u x , i ) ⎤⎦ Step 6 Cek pemberhentian kondisi Dari formula diatas dilakukan perhitungan terhadap nilai fungsi energi E hingga didapatkan nilai E yang minimum. Apabila telah didapatkan nilai fungsi energi yang minimum, diharapkan hasil dari proses algoritma ini memberikan hasil berupa path terpendek.

3. Hasil dan pembahasan 3.1 Algoritma Ant Colony Secara matematis path terpendek dengan menggunakan algoritma Ant colony adalah sebagai berikut: Diberikan sebuah graph G (V, E), misalkan sejumlah semut pada node i pada waktu t, dan m merupakan jumlah total semut dimana tiap – tiap semut merupakan agen sederhana dengan karakteristik sebagai berikut: a. Memilih node tujuan dengan suatu probabilitas. b. Tidak melewati node yang telah dilewati (yang dikontrol oleh tabu list) c. Meninggalkan substansi yang disebut pheromone pada setiap jalur yang dikunjungi. Dengan tujuan memenuhi batasan dimana semut mengunjungi semua node yang berbeda, masing – masing semut dihubungkan dengan sebuah struktur data bernama tabu list. Tabu list berfungsi menyimpan semua node yang sudah dikunjungi sampai waktu tertentu, dan melarang semut untuk mengunjunginya lagi sebelum n iterasi (satu tour) diselesaikan. Ketika tour telah diselesaikan, tabu list digunakan untuk menghitung hasil semut saat itu, yaitu jarak dari jalur yang telah dilalui semut. Tabu list lalu dikosongkan dan semut bebas untuk memilih jalur yang lain. Untuk penyelesaian permasalahan TSP ini diambil 5, 10 dan 15 kota sebagai penyelesaian optimasi TSP dengan menggunakan algoritma Ant colony. Hasil perhitungan tersebut dapat dilihat sebagai berikut: Tabel 1. TSP untuk 5 kota

Koordinat kota X Y 50 46 36 33 54 43 53 46 39 40

m

α

β

ρ

Q

Banyaknya iterasi

Waktu iterasi (detik)

10

0,1

0,9

0,5

1

100

0,6870

Gambar 1. Path terpendek untuk 5 kota. Panjang jalur terpendek: 26.308 Jalur Terpendek: C1 - D1 - A1 - E1 - B1 Tabel 2. TSP untuk 10 kota

Koordinat kota X Y 14 42 70 65 88 33 62 18 64 76 23 35 45 67 44 30 23 52 67 56

m

α

β

ρ

Q

Banyaknya iterasi

Waktu iterasi (detik)

10

0,1

0,9

0,5

1

100

0,8590

Gambar .2. Path terpendek untuk 10 kota Panjang jalur terpendek: 180.864 Jalur Terpendek: A1 - F1 - I1 - G1 - E1 - B1 J1 - C1 - D1 - H1

Gambar 3. Path terpendek untuk 15 kota Panjang jalur terpendek: 345.737 Jalur Terpendek: H1 - E1 - I1 - F1 - O1 - D1 - L1 - G1 - N1 - J1 - K1 - M1 - B1 - C1 - A1 Waktu iterasi : 2,5310

3.2 Jaringan Hopfield Pada kasus traveling salesman problem dengan menggunakan jaringan syaraf tiruan Hopfield dilakukan dengan merepresentasikan n neuron jaringan menjadi n kemungkinan urutan posisi yang dilalui pada sebuah kota. Untuk n kota maka dibutuhkan n node. Sebagai contoh terdapat 4 kota, maka empat node yang berisi: 0 0 1 0 menunjukkan sebuah kota yang mempunyai urutan ketiga untuk dikunjungi. Untuk menentukan apakah sebuah rute merupakan path terpendek pada jaringan Hopfield ini digunakan sebuah fungsi energi pada persamaan (8), dimana jika nilai energi yang dihasilkan kecil, menunjukkan bahwa rute tersebut merupakan path yang terpendek. Setelah didapatkan path terpendek, kemudian hasil yang dperoleh dibandingkan dengan algoritma Ant colony. Tetapi untuk kasus penyelesaian TSP dengan menggunakan jaringan Hopfield pada saat makalah ini dikumpulkan, peneliti masih melakukan percobaan sehingga belum dapat menampilkan hasil yang diperoleh.

4. Kesimpulan Algoritma Ant colony merupakan pendekatan heuristik baru untuk pencarian solusi dari kombinasi masalah optimasi. Algoritma ini dikembangkan berdasarkan hasil pengamatan tingkah laku semut dalam mencari makanan. Semut – semut secara berkelompok mencari jalur terpendek dari sarang ke sumber makanan ataupun sebaliknya. Pada saat semut – semut berjalan, mereka menyimpan suatu zat pheromone di sepanjang jalan yang dilaluinya. Jalur dengan pheromone konsentrasi kuat menandakan telah dilalui oleh banyak semut, yang akhirnya merupakan rute terpendek. Penyelesaian masalah TSP menggunakan algoritma Ant colony untuk 5 kota diperoleh dengan waktu 0.6870, 10 kota dengan waktu 0.8590 dan untuk 15 kota dengan waktu 2,5310. Jaringan syaraf tiruan Hopfield terdiri dari n2 neuron, dimana jumlah baris sebanyak n dan jumlah kolom sebanyak n. Semua neuron berhubungan penuh. Neuron yang satu mengeluarkan output dan kemudian menjadi input untuk semua neuron yang lain. Untuk menentukan apakah sebuah rute merupakan path terpendek pada jaringan Hopfield ini digunakan sebuah fungsi energi, dimana jika nilai energi yang dihasilkan kecil, menunjukkan bahwa rute tersebut merupakan path yang terpendek.

Daftar Pustaka Blum C, (2005), “Ant Colony Optimization: Introduction and Recent Trends”, Journal Physics of Life Reviews, volume 2, 353 – 373. Clapham C, (1996), “Concise Dictionary of Mathematics”, Second Edition, Oxford University Press, New York. Dorigo, M and Di Caro G, (1999), “Ant Colony Optimization: A New Meta-Heuristic”, IIEC Transactions on Evolutionary Computation, 1470 – 1477. Dayhoff J, (1990), “Neural Network Architectures (An Introduction)”, Van Nostrand Reinhold, New York. Fausett, Laurene, (1994), “Fundamental Of Neural Networks Architectures, Algorithms, and Applications”, ed. Don Fowley, Prentice Hall, London. Helvig, C.S, Robins Gabriel, dan Zelikovsky Alex, (2003), “The Moving-target Traveling Salesman Problem”, Journal of Algorithms, 153 – 174. Kusumadewi, S., & Purnomo, H. (2005), “Penyelesaian Masalah Optimasi dengan Teknik – Teknik Heuristik”, Edisi Pertama, Graha Ilmu, Yogyakarta. Siang JJ, (2004), “Matematika Diskrit dan Aplikasinya pada Ilmu Komputer”, Edisi Pertama, Andi Yogyakarta, Yogyakarta. Wibisono S, (2004), “Matematika Diskrit”, Edisi Pertama, Graha Ilmu, Yogyakarta. Wardy. S.I, “Penggunaan Graf dalam Algoritma Semut untuk Melakukan Optimisasi”, http://www.google.org /enrepaper/ download pada tanggal 15 Agustus 2008. Zha, Xuan.F, (2007), Artificial Intelligence and Integrated Intelligent Information Systems Emerging Technologies and Applications, Idea Group Publishing, Lon