Seminar Nasional Sistem dan Informatika 2007; Bali, 16 November 2007
SNSI07-048
PENYELESAIAN SHORTEST PATH PROBLEM DENGAN JARINGAN SARAF TIRUAN HOPFIELD Nur Hasanah1) Istikhomah2) Taufiq Hidayat3) Sri Kusumadewi4) Jurusan Teknik Informatika, Fakultas Teknologi Industri, Universitas Islam Indonesia Fakultas Teknologi Industri, Jurusan Teknik Informatika - Universitas Islam Indonesia
[email protected])
[email protected])
[email protected])
[email protected]) ABSTRACT The shortest path problem (SPP) is one of many optimization problems. The purpose of SPP is to get a route from the source city to the destination city by visiting other cities. In SPP, not every city should be visited and every city is visited only once. The goal is to find path that minimize the total distance of a route. In this paper, a recurrent neural network for solving the SPP is presented. This kind of neural networks can be used to solve this optimization problem by choosing an appropriate architecture to find the optimal solution. The Hopfield-type neural network is a very efficient tool for solving such problems. Keywords: Shortest Path Problem (SPP), Neural Network, Hopfield Neural Network, Optimization.
1.
Latar Belakang
Shortest Path Problem (SPP) adalah masalah optimasi kombinasional untuk mencari rute minimum yang diperlukan untuk mencapai kota tujuan dari kota asal berdasarkan beberapa jalur alternatif yang tersedia. Setiap tempat tidak selalu mempunyai jalur yang terhubung dengan kota-kota lainnya. Berbagai macam algoritma telah diuji untuk menyelesaikan masalah ini. Jaringan saraf tiruan merupakan salah satu alternatif untuk menyelesaikan masalah optimasi. JST Hopfield pertama kali digunakan oleh Hopfield dan Tank untuk memecahkan Travelling Salesman Problem (TSP). Sejak itu banyak peneliti berusaha untuk mengaplikasikan JST Hopfield untuk memecahkan masalah optimasi lainnya.
2.
Tujuan Penelitian
Tujuan dari penelitian ini adalah: 1. Untuk mengaplikasikan JST Hopfield ke dalam sebuah kasus optimasi. 2. Untuk menemukan sebuah solusi baru dalam menentukan jalur terpendek menggunakan algoritma JST Hopfield. 3. Untuk menganalisa kinerja JST Hopfield dalam memecahkan SPP.
3.
Rumusan Masalah
Rumusan masalah dari penelitian ini adalah bagaimana membuat desain JST Hopfield dan mengimplementasikannya ke dalam kasus SPP agar didapatkan hasil yang optimal.
4.
Landasan Teori
4.1 Jaringan Syaraf Tiruan Hopfield Jaringan syaraf merupakan salah satu representasi buatan dari otak manusia yang selalu mencoba untuk mensimulasikan proses pembelajaran pada otak manusia. Seperti halnya otak manusia, jaringan syaraf juga terdiri dari beberapa neuron yang mentransformasikan informasi yang diterima melalui sambungan keluarnya menuju ke neuron-neuron yang lain dengan nama bobot. Fungsi aktivasi, merupakan penggambaran hubungan tingkat aktivasi internal. bobot Input dari neuronneuron lain
∑
Fungsi aktivasi
bobot Output
Output ke neuronneuron lain
Gambar 1. Struktur Neuron Jaringan Syaraf. Algoritma Hopfield neural network pertama kali dikenalkan oleh John Hopfield dari California Institute of Technology pada tahun 1982. John Hopfield merancang sebuah jaringan saraf tiruan yang kemudian dikenal dengan nama jaringan Hopfield. Pada jaringan Hopfield, semua neuron saling berhubungan penuh. Neuron yang satu mengeluarkan output dan kemudian menjadi input bagi semua neuron yang lain. Proses pengiriman dan penerimaan sinyal antar neuron ini secara feedback tertutup terus menerus sampai dicapai kondisi stabil (Kristanto 2004). Penggunaan JST Hopfiled untuk memecahkan masalah optimasi pertama dilakukan oleh Hopfield dan Tank untuk memecahkan Travelling Salesman Problem.
276
Seminar Nasional Sistem dan Informatika 2007; Bali, 16 November 2007
SNSI07-048
Sirkuit jaringan Hopfield dapat dilihat pada Gambar 2. Desain sirkuit ini diadaptasi dari komponen-komponen dasar jaringan saraf biologis. Setiap neuron dimodelkan sebagai sebuah amplifier dengan fungsi aktivasi sigmoid dengan input U i dan output Vi dari neuron ke-i. Output dari Vi merupakan bilangan 0 atau 1.
Gambar 2. Jaringan Saraf Tiruan Hopfield Fungsi sigmoid: Vi = g i (U i ) =
1 1+ e
(1)
− λi U i
Setiap neuron menerima input/impuls dari neuron-neuron lainnya. Hubungan ini biasanya disebut dengan koneksi sinapsis dan dideskripsikan melalui matrik T = [Tij ] . Dalam jaringan, matrik T disebut juga dengan matrik hubungan.
Setiap neuron juga menerima bias yang disebut I i . Rumus perubahan U i dari jaringan Hopfield adalah sebagai berikut: dU i dt
N
= ∑ TijV j −
Ui
j =1
+ I i (2)
τ
Dimana τ adalah konstanta dari waktu sirkuit. Dari kedua persamaan di atas didapatkan pula fungsi energi: E=−
1
N
N
N
∑∑ T VV − ∑ I V 2 ij
i =1
i
j
j =1
i
i
(3)
i =1
Berdasarkan rumus energi (3), rumus perubahan neuron ke ith dirumuskan sebagai berikut: dU i dt
=−
Ui
τ
−
∂E ∂Vi
(4)
4.2 Shortest Path Problem dengan Jaringan Syaraf Tiruan Hopfield Pada kasus Shortest Path Problem, tujuannya adalah menemukan rute yang terpendek antara node source s, ke node destination d, di jaringan yang ada. Jaringan didefinisikan sebagai sebuah graf berarah G = (N, A), dengan N adalah banyaknya node dan A adalah banyaknya sisi (arc) atau dalam kasus ini adalah jalan (path). Adapun Cij , adalah nilai
yang menunjukkan besarnya jarak, panjang, atau waktu transit dari node i ke node j. Rute terpendek dapat dirumuskan dengan graf Psd, yang berisi urutan node-node yang menghubungkan s ke d: Psd = (s, i, j, k, ..., r, d)
(5) 277
Seminar Nasional Sistem dan Informatika 2007; Bali, 16 November 2007
SNSI07-048
Panjang dari jalur terpendeknya adalah Lsd = Csi + Cij + C jk + ... + Crd . Inti permasalahannya adalah mencari rute Lsd dengan panjang minimum. Pada kasus shortest path, node-node disediakan dalam bentuk matrik n x n. Dengan semua elemen diagonal dihilangkan, karena tidak dibutuhkan. Setiap elemen merepresentasikan neuron dengan indikator (i, j), dimana i menyatakan kolom dan j menyatakan nomor dari node. Jadi, sebuah jaringan memerlukan n (n - 1) neuron, dan neuron dengan letak (i, j) menggambarkan output Vij , dengan ketentuan sebagai berikut:
1 Vij = 0
Bila jalur dari node i ke node j ada dalam rute terpendek
(6)
Sebaliknya
Dan juga ditentukan ρ ij sebagai berikut:
1
Bila tidak ada jalur dari node i ke node j
0
Sebaliknya
ρ ij =
(7)
Selain Vij dan ρ ij , diperlukan juga Cij , yaitu besarnya jarak dari node i ke node j dan harus bernilai positif. Untuk jalur yang tidak ada, maka besarnya jarak akan dianggap sebagai nol, dan jalur ini akan tereliminasi dari solusi. Untuk menentukan apakah sebuah rute merupakan rute terpendek pada jaringan Hopfield ini digunakan sebuah fungsi energi (3) yang telah dimodifikasi, dimana hasil akan diperoleh bila energi yang dihasilkan minimum. Berikut adalah rumus fungsi energinya:
E=
µ1 2
µ2
n
∑∑ C i =1
ij
⋅V + ij
2
j =1
n
n
i =1
j =1
∑∑ ρ
j ≠i
+
µ4 2
n
n
i =1
j =1
ij
⋅V + ij
j ≠i
∑∑ (V ⋅ (1 − V ) )¬ + ij
ij
µ5 2
j ≠i
n
µ3 2
∑ ∑V − ∑V n
n
n
i =1
j =1
j =1
j ≠i
j≠i
ij
ij
−γ
i
2
(8)
n
∑∑ (1 − V ) ds
i =1
j =1 j ≠i
Koefisien Cij merupakan besar jarak dari kota i ke kota j dan Vij menggambarkan koneksi antara kota i dan kota j, dimana Vij akan bernilai 0 jika kedua kota tersebut tidak terkoneksi atau berhubungan dan akan bernilai 1 jika terkoneksi. Konstanta µ1 digunakan untuk meminimalkan total jarak; konstanta µ 2 digunakan untuk mencegah jalur yang tidak ada agar tidak ikut dalam rute; konstanta µ 3 bernilai 0 untuk setiap node (jumlah jalur yang masuk sama dengan jumlah jalur yang keluar); konstanta µ 4 digunakan agar jaringan dapat meraih kondisi konvergen; konstanta µ 5 bernilai nol di saat output. Vij adalah sama dengan 1, untuk memastikan shortest path yang ada menpunyai sumber dan tujuan yang sesuai. Berdasarkan persamaan (1), (2), dan (4) maka didapatkan rumus perubahan U ij : dU ij dt
dU ij dt
=−
=−
U ij
τ U ij
τ
n
+
n
∑ ∑T
ij , kl
.Vkl + I ij (9a)
k =1 l =1 l≠k
−
Vij = g ij (U ij ) =
∂E
(9b)
∂Vij 1 1+ e
− λij U ij
(10a)
278
Seminar Nasional Sistem dan Informatika 2007; Bali, 16 November 2007
∀(i , j ) ∈ Nx N / i ≠ j.
SNSI07-048
(10b)
Dengan mensubstitusikan (9) di (10b), persamaan untuk perubahan jaringan saraf menjadi: dU ij
=−
dt
U ij
τ
−
µ1 2
Cij (1 − δ id .δ js ) −
+ µ 3∑ (V jk − Vkj ) − k =1 k≠ j
µ4 2
(1 − 2Vij ) +
µ2 2
µ5 2
n
ρ ij (1 − δ id .δ js ) − µ 3∑ (Vik − Vki ) k =1 k ≠i
δ id δ js
(11)
∀(i,j) ∈ Nx N / i ≠ j.
Dimana δ merupakan delta Kronecker dimana:
1 0
δ ab =
Bila a = b
(12)
Sebaliknya
Dengan membandingkan persamaan (10a) dan (12), maka kekuatan koneksi dan bias ditetapkan sebagai berikut: Tij , kl = µ 4δ ik δ jl − µ 3δ ik − µ 3δ jl + µ 3δ li + µ 3δ jk (13) I ij = −
µ1 2
Cij (1 − δ id .δ js ) −
µ2 2
ρ ij (1 − δ id .δ js ) −
µ4 2
+
µ5 2
δ id .δ js
µ5 − µ 4 jika (i , j ) = ( d , s ) 2 2 = − µ1 C − µ 2 ρ − µ 4 sebaliknya ij 2 ij 2 ∀(i ≠ j ), ∀(k ≠ j ). 5.
Metode Penelitian
5.1 Perancangan Jaringan Hopfield Misalkan akan dibuat sebuah jaringan Hopfield yang mempresentasikan jaringan kota di pulau Jawa. Node-node dalam jaringan mempresentasikan kota-kota. Sedangkan arc mempresentasikan jalur dari satu kota ke kota lainnya.
Gambar 3. Jaringan Kota di Pulau Jawa
Pada Gambar 3 dapat dilihat bahwa jaringan tersebut mempunyai 11 node dengan 16 jalur. Tiap-tiap jalur mempunyai nilai jarak sendiri. Keterangan nodenya adalah sebagai berikut:
279
Seminar Nasional Sistem dan Informatika 2007; Bali, 16 November 2007
SNSI07-048
Tabel 1. Daftar Kota yang Saling Terhubung
NODE A B C D E F G H I J K
NAMA KOTA Jakarta Bogor Bandung Cirebon Semarang Magelang Purworejo Sleman Yogyakarta Malang Surabaya
5.2 Studi Kasus Misalkan akan dicari rute terpendek dari kota Jakarta (A) ke kota Yogyakarta (I) dari jaringan Hopfield pada gambar 3. Didapatkan matrik C, yang elemen-elemennya mempresentasikan besarnya jarak dari satu kota ke kota lainnya. Diasumsikan bahwa matrik jalur ini bersifat simetris dengan Cij = C ji , dimana terdapat jalur dengan dua arah antara satu
kota ke kota lainnya. C=
50 0 50 0 200 100 0 100 0 0 0 0 0 0 0 0 0 0 0 0 0 0
200 100 0
100 0 100
300 0 0
0 0 0
0 0 450
0 0 0
0 0 0
0 0 0
100 0 0 450 0 0
0 300 0 0 0 0
300 0 250 0 0 0
0 250 0 55 25 0
0 0 55 0 11 23
0 0 25 11 0 14
0 0 0 23 14 0
0 0 0 0 0 200
0 0
0 0
0 400
0 0
0 0
0 0
200 0
0 78
0 400 0 0 0 0 78 0 0 0 0
Didapat juga matrik ρ , yang elemen-elemennya mempresentasikan ada tidaknya sebuah jalur dari satu kota ke kota lainnya.
ρ =
1 0 0
0 1 0
0 0 1
0 1 0
0 1 1
1 1 1
1 1 0
1 1 1
1 1 1
1 1 1
0 1 1
1 1 1
0 1 1
1 0 1
0 1 0
1 0 1
1 1 0
1 1 0
1 1 1
1 1 1
1 1 1 1
1 1 1 1
0 1 1 1
1 1 1 1
1 1 1 1
0 0 1 1
1 0 0 1
0 1 0 1
0 0 1 0
1 1 0 1
1
1
1
1
0
1
1
1
1
0
1 0 1 1 1 1 0 1
1 1 1
Setelah dikomputasi, maka hasil dari energi yang didapatkan dapat dilihat pada grafik di bawah ini:
280
Seminar Nasional Sistem dan Informatika 2007; Bali, 16 November 2007
SNSI07-048
Gambar 4. Energi Jaringan Kota di Pulau Jawa Pada Grafik 1, dapat dilihat bahwa nilai dari energi pada jaringan kota akan mencapai kondisi konvergen, dimana di saat itulah rute terpendek didapatkan.
Gambar 5. Rute Terpendek pada Jaringan Kota di Pulau Jawa
Rute terpendek dari kota Jakarta ke kota Yogyakarta yang didapatkan adalah: Jakarta – Bandung – Purworejo – Yogyakarta.
6.
Kesimpulan 1. 2.
Pemanfaatan teknologi informasi pada pencarian rute terpendek diyakini menghasilkan suatu keluaran yang akurat dan tepat, untuk pilihan transportasi seseorang. Jaringan saraf tiruan Hopfield dapat digunakan untuk memecahkan masalah rute terpendek dengan memberikan solusi optimum yang tepat. Setelah dicoba beberapa kali percobaan kombinasi jalur pada jaringan, terbukti JST Hopfield dapat memberikan jalur terpendek bahkan dengan jumlah node yang banyak.
Daftar Pustaka [1] Ahn, C.W., Ramakrishna, R.S., Kang, C.G., and Choi, I.C. (2001). Shortest Path Routing Algorithm Using Hopfield Neural Networks. IEEE Electronics Letter on 13th September 2006 vol. 37, no. 19. pp. 1176-1178. [2] Ali, M.K.M., and Kamoun, F. (1993). Neural Networks for Shortest Path Computation and routing in Computer Networks. IEEE Transactions on Neural Networks, vol. 4, no. 6 November 1993, pp. 941-947. [3] Kojic, N., Reljin, I., and Reljin, B. (2006). Neural Networks for Optimization of Routing in Communication Networks. Elec.Energ. vol. 19, no. 2 August 2006, pp. 317-329. [4] Kristanto, A. (2004). Jaringan Syaraf Tiruan.Yogyakarta : GavaMedia. [5] Kronecker Delta Function, http://en.wikipedia/wiki/kronecker_delta.html, diakses 15 Juli 2007.
281
