Mata kuliah JST menjadikan ide ini muncul untuk garap penelitian sebagai aplikasi perkuliahan JST TE/ TI'2002 “PENENTUAN JALUR TERPENDEK PADA KASUS TRAVELLING SALESMAN PROBLEM DENGAN ALGORITMA SELF ORGANIZING MAP“
A. RENCANA JUDUL
“PENENTUAN JALUR TERPENDEK PADA KASUS TRAVELLING SALESMAN PROBLEM DENGAN ALGORITMA SELF ORGANIZING MAP“
B. BIDANG ILMU
Matematika, Jaringan Syaraf Tiruan, Komputer.
C. PENDAHULUAN
1. Jalur Terpendek ( SHORTEST PATH )
Andaikan diberikan sebuah graph G dalam tiap garis (x,y) dihubungkan dengan titik a (x,y) mewakili panjang dari garis. Dalam beberapa hal, panjang sebenarnya mewakili biaya atau beberapa nilai lainnya. Panjang dari lintasan adalah menentukan panjang jumlah dari masing-masing garis yang terdiri dari lintasan. Untuk 2 verteks s dan t dalam G, ada beberapa lintasan dari s ke t . Masalah lintasan terpendek meliputi pencarian lintasan dari s ke t yang mempunyai lintasan terpendek dan biaya termurah.
a. Defenisi Jalur Terpendek
Jalur terpendek (Shortest Path) antara dua verteks dari s ke t dalam jaringan adalah lintasan graph berarah sederhana dari s ke t dengan sifat dimana tidak ada lintasan lain yang memiliki nilai terendah. Pada persoalan ini akan terdorong untuk menyelesaikan suatu persoalan untuk menentukan jalur terpendek dan biaya termurah dalam suatu jaringan dengan mengimplementasikannya ke dalam kasus travelling salesman problem yang merupakan salah satu persoalan dalam Jaringan Syaraf Tiruan.
Setiap path dalam digraph mempunyai nilai yang dihubungkan dengan nilai path tersebut, yang nilainya adalah jumlah dari nilai edge path tersebut. Dari ukuran dasar ini dapat dirumuskan masalah seperti “ mencari lintasan terpendek antara dua vertek dan meminimumkan biaya”.
Banyak bidang penerapan mensyaratkan untuk menentukan lintasan terpendek berarah dari asal ke tujuan di dalam suatu distribusi aliran berarah. Algoritma yang diberikan dapat dimodifikasi dengan mudah untuk menghadapi lintasan berarah pada setiap iterasinya.
Suatu versi yang lebih umum dari masalah lintasan terpendek adalah menentukan lintasan terpendek dari sembarang verteks menuju ke setiap verteks lainnya. Pilihan lain adalah membuang kendala tak negatif bagi “jarak”. Suatu kendala lain dapat juga diberlakukan dalam
suatu masalah lintasan terpendek.
Definisi 1.1. Lintasan terpendek antara dua verteks dari s ke t dalam jaringan adalah lintasan graph berarah sederhana dari s ke t dengan sifat dimana tidak ada lintasan lain yang memiliki nilai terendah.
Pada gambar 1.1. dapat dilihat bahwa setiap edge terletak pada path-path dari titik 1 ke titik 5. Edge merepresentasikan saluran dengan kapasitas tertentu (contohnya, air) dapat dialirkan melalui saluran. Sedangkan verteks merepresentasikan persimpangan saluran. Air mengalir melalui verteks pada vertex yang dilalui
Lintasan terpendek dari verteks pada graph di atas adalah P = {1 – 4, 4 – 5} dengan kapasitas 4.
2. Travelling Salesman Problem
Permasalahan TSP (Traveling Salesman Problem ) adalah permasalahan dimana seorang salesman harus mengunjungi semua kota dimana tiap kota hanya dikunjungi sekali, dan dia harus mulai dari dan kembali ke kota asal. Tujuannya adalah menentukan rute dengan jarak total atau biaya yang paling minimum. Permasalahan TSP merupakan permasalahan yang memang mudah untuk diselesaikan dengan algoritma Brute Force, tetapi hal itu hanya dapat dilakukan dengan jumlah kota atau simpul yang tidak banyak. Kompleksitas algoritma untuk permasalahan TSP dengan algoritma Brute Force adalah O(n!) dengan catatan n adalah jumlah kota atau simpul dan setiap kota atau simpul terhubung dengan semua kota atau simpul lainnya. Dengan jumlah sebanyak 20 kota, maka banyak sirkuit Hamilton yang mungkin adalah sebanyak 6 x 1016.
12.1. Pendahuluan
Selain masalah sarana transportasi, efisiensi pengiriman surat atau barang ditentukan pula oleh lintasan yang diambil untuk mengirimkan surat atau barang tersebut. Oleh karena itu solusi optimal dari permasalahan TSP ini, akan sangat membantu perusahaan pegiriman surat atau barang untuk mengefisienkan proses pengiriman barang, baik dari segi waktu maupun dana.
Hingga kini kompleksitas algoritma permasalahan TSP masih tidak dapat diketahui pasti, bahkan setelah 50 tahun lebih pencarian. Hal tersebut menjadikan TSP menjadi salah satu permasalahan yang hingga kini belum terselesaikan dalam banyak permasalahan optimasi matematis.
12.2 Sejarah Permasalahan TSP
Permasalahan matematika tentang Traveling Salesman Problem dikemukakan pada tahun 1800 oleh matematikawan Irlandia William Rowan Hamilton1 dan matematikawan Inggris Thomas Penyngton2. Gambar dibawah ini adalah foto dari permainan Icosian Hamilton yang membutuhkan pemain untuk menyelesaikan perjalanan dari 20 titik menggunakan hanya jalur-jalur tertentu.
Diskusi mengenai awal studi dari Hamilton dan Kirkman dapat ditemukan di Graph Theory 1736-19363 oleh N. L. Biggs, E. K. LLoyd, dan R. J. Wilson, Clarendon Press, Oxford, 1976. Bentuk umum dari TSP pertama dipelajari oleh para matematikawan mulai tahun 1930. Diawali oleh Karl Menger4 di Vienna dan Harvard. Setelah itu permasalahan TSP dipublikasikan oleh Hassler Whitney5 dan Merrill Flood6 di Princeton. Penelitian secara detail dari hubungan antara Menger dan Whitney, dan perkembangan TSP sebagai sebuah topik studi dapat ditemukan di makalah Alexander Schrijver’s7 “On the history of combinatorial optimization (till 1960)”8.
3. Algoritma Self Organizing Map
3.1 Pendahuluan
Jaringan saraf tiruan Self Organizing Maps (SOM) atau disebut juga dengan jaringan Kohonen telah banyak dimanfaatkan untuk pengenalan pola baik berupa citra, suara, dan lain-lain [1,2]. Jaringan SOM sering pula digunakan untuk ekstraksi ciri (feature) pada proses awal pengenalan pola. Ia mampu mereduksi dimensi input pola ke jumlah yang lebih sedikit sehingga pemrosesan komputer menjadi lebih hemat.
Dalam paper ini akan dicoba memanfaatkan jaringan saraf tiruan SOM/Kohonen untuk pengenalan citra dengan kehadiran noise dan juga pergeseran serta pengecilan bentuk. Jaringan dilatih untuk mengenali pola sebanyak lima belas macam yang meliputi tiga bentuk (kubus, tabung, dan kerucut) dengan masing-masing lima posisi berbeda. Jaringan dilatih terus menerus sampai diperoleh error tertentu. Pada proyek ini diteliti pula struktur dan parameter jaringan SOM yang optimal untuk kebutuhan pengenalan citra ini. Dengan didapatnya struktur yang optimal, maka diharapkan jaringan akan cepat belajar dan dapat mengenali citra dengan error yang minimum. Pada proses percobaan didapat beberapa parameter yang optimal yaitu jumlah Kohonen map, nilai neighborhood, dan alpha/learning rate adalah 90, 10, 0.9. Jaringan diuji untuk mengenali citra dengan deformasi, yaitu pemberian variasi noise pada input citra. Juga diuji seberapa jauh jaringan dapat menangani pergeseran bentuk. Untuk pengenalan citra bernoise dengan memakai bobot-bobot optimal maka jaringan Kohonen ini mempunyai tingkat keberhasilan sekitar 98 % untuk semua level noise.
3.2 Deskripsi Sistem
Jaringan SOM/Kohonen yang digunakan di sini digambarkan pada gambar 1. Dimensi input citra yang digunakan di sini adalah 10 x 10 pixel. Node input dihubungakan dengan node output dengan koneksi bobot, yang mana bobot ini selalu diperbaiki pada proses iterasi pelatihan jaringan.
Prinsip kerja dari algoritma SOM adalah pengurangan node-node tetangganya (neighbor), sehingga pada akhirnya hanya ada satu node output yang terpilih (winner node). Pertama kali yang dilakukan adalah melakukan inisialisasi bobot untuk tiap-tiap node dengan nilai random. Setelah diberikan bobot random, maka jaringan diberi input sejumlah dimensi node/neuron input (10x10). Setelah input diterima jaringan, maka jaringan mulai melakukan perhitungan jarak vektor yang didapatkan dengan menjumlah selisih/jarak antara vektor input dengan vektor bobot. Secara matematis dirumuskan
Setelah diketahui tiap-tiap jarak antara node output dengan input maka dilakukan perhitungan jumlah jarak selisih minimum. Dimana node yang terpilih (winner) berjarak minimum diberi tanda khusus, yaitu diberikan angka satu dan node yang lain nol. Tahap akhir algoritma ini adalah melakukan perubahan bobot pada node output yang terpilih beserta tetangga sekitarnya (misal node terpilih adalah node ke-20 dan jumlah neighborhood=5, maka bobot pada node ke-15 sampai ke-25 akan diubah), yang dirumuskan sebagai berikut:
a(t) merupakan alpha/ learning rate yaitu faktor pengali pada perubahan bobot yang berubah terhadap perubahan error. Perubahan alpha ini sesuai dengan banyaknya input yang masuk. Faktor pengali alpha/learning rate ini akan selalu berkurang bila tidak ada perubahan error.
Pada metode ini hasil pengenalan pola/citra ada pada bobot-bobot yang terdapat pada node winner output. Dibandingkan dengan bobot-bobot yang lain, bobot pada winner output ini paling
mendekati dengan pola yang dilatihkan pada jaringan. Pada proses pelatihan bobot pada winner output beserta dengan tetangganya selalu diupdate, dilakukan iterasi terus menerus sampai mencapai error yang diinginkan. Jikalau belum mencapai error tertentu maka proses kembali pada penginputan citra untuk dilatih kembali.
Dalam perubahan bobot ini hal yang paling menentukan adalah alpha/learning rate a(t). Faktor pengali ini menentukan kecepatan belajar jaringan dan diset dengan nilai antara nol sampai satu. Untuk faktor pengali yang cukup besar akan didapatkan hasil belajar yang cepat, tetapi dengan pemetaan yang kasar. Dan untuk faktor pengali yang kecil akan didapatkan pemetaan yang bagus
dengan waktu belajar yang lebih lama. Bobot yang didapatkan bukan hanya didasarkan pada besarnya vektor tapi arah vektor itu sendiri.
Inisialisasi bobot dilakukan dengan cara memberikan bobot random antara -1 sampai 1. Jika hal ini dilakukan maka vector bobot akan benar-benar menyebar dengan random. Konsekuesi dari penyebaran yang random memungkinkan jaringan tidak dapat belajar secara konvergen dan akhirnya jaringan akan memiliki orientasi yang sangat berbeda dengan orientasi awal. Karena kesalahan orientasi ini akan dapat menyebabkan jaringan tidak terlatih dan pada akhirnya menghasilkan sedikit node yang dapat membedakan input.
Salah satu metode untuk mencegah terjadinya nonkonvergen adalah menginisialisasi bobot awal dengan pola-pola yang sangat mirip dengan pola-pola yang akan dilatihkan (input pattern). Dengan cara ini maka jaringan akan dapat belajar secara perlahan mengikuti perubahan input yang ada, yang pada akhirnya didapatkan bentuk pemetaan yang sesuai dengan yang diperlukan
oleh jaringan untuk pengenalan pola. Pada algoritma Kohonen didapatkan node output yang saling berhubungan antara satu node dengan node yang lain, dari hubungan ini maka node yang satu akan mempengaruhi node-node yang lain. Sebelum diberikan input maka daerah keputusan
memiliki area yang sangat lebar. Setelah melewati tahapan pelatihan maka luas area dari vektor keputusan akan semakin kecil.
3.3 Algoritma Self Organizing Map
Algoritma SOM adalah sbb.
1. Inisialisasi random reference vector untuk tiap neuron. Misalnya struktur yang dipakai adalah two-dimensional array SOM, diatur pada array n x n. Tiap vektor berdimensi d, sama dengan dimensi data.
2. Untuk tiap input vector training data x, tentukan best-matching neuron. Yaitu neuron yang memiliki jarak terdekat dengan input vector x, diukur memakai Euclidean distance. Neuron ini disebut winner.
3. Update-lah reference vector dari winner neuron ini dan neighboring neuron. Neighboring neuron ini didefinisikan sebagai neuron yang topographically berada pada posisi yang dekat dengan winner neuron di array n x n. Misalnya pada gambar di bawah (klik-lah untuk memperbesar), jika neuron yang berwarna merah adalah winner neuron untuk suatu input vector, maka neighboring neuron untuk winner neuron ini adalah mereka yang terletak di dalam lingkaran area, yang didefinisikan dengan Nc(t1), Nc(t2), … dst. Nc(t1) adalah batas area pada iterasi ke-1, Nc(t2) adalah batas area pada iterasi ke-2, dst. Radius area semakin lama semakin menyempit, misalnya sebagaimana didefinisikan oleh persamaan (3). Reference vector diupdate berdasarkan persamaan (1), sedangkan neuron yang secara topografi terletak jauh dari winner neuron tidak diupdate (persamaan (2) ). Persamaan (3) mendefinisikan learning rate yang dipakai studi saya.
Step ke-3 ini yang membedakan SOM dengan algoritma vector quantization yang lain, karena proses mapping dilakukan secara terurut (ordered mapping) dan merefleksikan distribusi vektor x. Konsekuensinya data yang dipetakan pada suatu neuron S, akan memiliki kemiripan karakteristik dengan data yang dipetakan ke neuron yang secara topografi terletak didekat neuron
S. Dengan kata lain, data yang pada ruang vektor dimensi tinggi terletak berdekatan, akan dipetakan ke neuron pada twodimensional-array yang berdekatan juga.
D. PERUMUSAN MASALAH
1. Analisa Jaringan Syaraf Tiruan untuk menyelesaikan permasalahan Travelling Salesman Problem yang dipergunakan untuk penentuan jalur terpendek.
2. Melakukan analisa pada traveling salesman problem dengan mencari jalur terpendek untuk 25 titik.
E. TINJAUAN PUSTAKA
Jaringan Syaraf Tiruan yang selanjutnya dikenal dengan nama JST merupakan cabang ilmu multidisiplin yang relative masih baru. Pada dasarnya JST mencoba meniru cara kerja otak makhluk hidup. Salah satu struktur yang ingin ditiru adalah bentuk neuron-nya (Sel Syaraf).
Sel Syaraf (neuron) dalam banyak hal sama dengan sel-sel tubuh yang lain, hanya bedanya sel neuron tidak dapat berkembang biak. Faktor kecerdasan dari syaraf tidak ditentukan di dalam sel tetapi terletak pada bentuk dan topologi jaringannya.
Jaringan syaraf tiruan didefenisikan sebagai system pemrosesan informasi yang mempunyai karakteristik menyerupai jaringan syaraf manusia. Jaringan syaraf tiruan tercipta sebagai suatu generalisasi model matematis dari pemahaman manusia (human cognition) yang didasarkan atas asumsi sebagai berikut:
1. Pemrosesan informasi terjadi pada elemen sederhana yang disebut neuron.
2. Isyarat mengalir diantara sel syaraf (neuron) melalui suatu sambungan penghubung.
3. Setiap sambungan penghubung memiliki bobot yang bersesuaian. Bobot ini akan digunakan untuk mengandakan/mengalikan isyarat yang dikirim melaluinya.
4. Setiap sel syaraf akan menerapkan fungsi aktivasi terhadap isyarat hasil penjumlahan berbobot yang masuk kepadanya untuk menentukan isyarat keluarannya.
Sistem jaringan syaraf tiruan disebut juga brain metaphor, computional neuroscience atau parallel distributed processing serta connection. Jaringan syaraf tiruan tersusun dari sejumlah besar elemen yang melakukan kegiatan analog dengan fungsi-fungsi biologis neuron yang paling elementer. Elemen – elemen ini terorganisasi sebagaimana layaknya anatomi otak, walaupun tidak persis. Jaringan syaraf tiruan dapat belajar dari pengalaman, melakukan generalisasi atas contoh–contoh yang diperoleh dan mengabtarksi karakteristik essensial input bahkan untuk data yang tidak relevan.
Jaringan syaraf tiruan memiliki sejumlah besar kelebihan dibandingkan dengan metode perhitungan lainnya, yaitu:
1. Kemampuan mengakusisi pengetahuan walaupun dalam kondisi ada gangguan dan ketidakpastian. Hal ini karena jaringan syaraf tiruan mampu melakukan generalisasi, abtraksi, dan ekstraksi terhadap property statistic dari data.
2. Kemampuan merepresentasikan pengetahuan secara fleksibel. Jaringan syaraf tiruan dapat menciptakan sendiri representasi melalui pengaturan diri sendiri atau kemampuan belajar (Self Organizing).
3. Kemampuan untuk memberikan toleransi atas suatu distorsi (error/fault), dimana gangguan kecil pada data dapat dianggap hanya sebagai noise (guncanngan) belaka.
4. Kemampuan memproses pengetahuan secara efisien karena memakai system parallel, sehingga waktu yang diperlukan untuk mengoperasikan menjadi lebih singkat.
Dengan tingkat kemampuan yang sangat baik, beberapa aplikasi jaringan syaraf tiruan sangat cocok untuk diterapkan pada:
1. Klasifkasi, memilih suatu input data kedalam satu katagori tertentu yang diterapkan
2. Asosiasi, mengambarkan suatu objek secara keseluruhan hanya dengan sebuah bagian dari objek lain.
3. Self Organizing, kemampuan untuk mengelola data-data input tanpa harus memiliki data sebagai target.
4. Optimasi, menemukan suatu jawaban atau solusi yang paling baik sehingga seringkali dengan meminimalisasikan suatu fungsi biaya (optimizer).
Karakteristik jaringan syaraf tiruan ditentukan oleh:
1. Pola hubungan antar neuron (disebut dengan arsitektur jaringan)
2. Metode penentuan bobot-bobot sambungan (disebut dengan pelatihan atau proses belajar jaringan)
3. Fungsi aktivasi.
F. TUJUAN PENELITIAN
Tujuan penulisan tugas akhir adalah:
1. Menganalisa kasus traveling salesman problem (tsp) dengan menggunakan algoritma self organizing map untuk mendapatkan jalur terpendek atau sikular.
2. Hasil simulasi dari arsitektur yang dipilih memiliki kemampuan belajar yang cepat dan akurat.
G. KONTRIBUSI PENELITIAN
Dengan mengimplementasikan arsitektur jaringan Self Oragnizing Map pada Travelling Salesman Problem dapat bermanfaat dalam pengembangan Artificial Neural Network lebih lanjut dengan penerapan komputerisasi dalam bidang simulasi pengenalan lainnya.
H. METODE PENELITIAN
Metode penelitan dalam tulisan ini adalah :
1. Pembahasan mengenai Shortest Path, Travelling Salesman Problem dan Algoritma Self-Organizing.
2. Menerjemahkan permasalahan Travelling Salesman Problem dengan algoritma Self-Organizing Map ke model matematis dan komputerisasi.
3. Menganalisa algoritma Self-Organizing Map dalam kajian kasus Travelling Salesman Problem.
DAFTAR PUSTAKA
1. Andri Kristanto, 2004, Jaringan Saraf Tiruan (Konsep Dasar, Algoritma dan Aplikasinya ), Gava Media Yogyakarta.
2. Arief Hermawan, 2006, Jaringan Syaraf Tiruan Teori dan Aplikasi, Penerbit ANDI Yogyakarta.
3. Diyah Puspitaningrum , 2006 , Pengan Jaringan Syaraf Tiruan, Penerbit ANDI Yogyakarta.
4. Jong Jek Siang, Drs, M.Sc, 2005, Jaringan Syaraf Tiruan & Pemrogramannya Menggunakan Matlab, Penerbit ANDI Yogyakarta.
5. Sri Kusumadewi, 2004, Membangun Jaringan Syaraf Tiruan Menggunkan MATLAB & EXCEL LINK, Penerbit GRAHA ILMU Yogyakarta.
---- Semoga Bermanfaat Bagi Civitas Teknik Informatika ----
--- Khususnya Yang Memilih Mata Kuliah Pilihan JST ---
Salam Kekuatan Berawal Dari Hati bayoete.blogspot.com
