BAB 2 LANDASAN TEORI

8

BAB 2

LANDASAN TEORI

Pada bab ini akan dibahas beberapa konsep dasar dan beberapa definisi yang akan digunakan sebagai landasan berpikir dalam melakukan penelitian ini sehingga mempermudah penulis untuk menyampaikan pembahasan yang akan dijelaskan pada bab selanjutnya. Konsep dasar ini berkaitan dengan permasalahan yang akan dibahas dalam penelitian ini, yaitu traveling salesman problem, graph, metode simulasi, algoritma Metropolis, simulasi annealing dan hubungan antara traveling salesman problem dengan simulasi annealing yang nantinya akan digunakan dalam bab pembahasan.

2.1

Traveling salesman problem

Traveling salesman problem memiliki sejarah panjang. Dicetuskan pertama kali oleh Euler pada awal tahun 1759, walaupun dengan nama yang berbeda, yang tertarik untuk menyelesaikan permasalahan “knight’s tour”. Solusi yang tepat akhirnya diperoleh ketika pion kuda melewati tiap-tiap rute yang memungkinkan dari 64 kotak pada papan catur tepat satu kali dalam perjalanannya. Yang artinya setelah pion kuda tersebut melewati seluruh kemungkinan rute akhirnya dia menemukan solusi yang tepat.

Kemudian sekitar tahun 1800 diperkenalkan kembali oleh matematikawan Irlandia bernama William Rowan Hamilton dan matematikawan Inggris bernama Thomas Penyngton yang berupa suatu permainan bernama Icosian Hamilton yang mengharuskan pemain untuk menyelesaikan perjalanan dari 20 titik dengan

Universitas Sumatera Utara

9

menggunakan hanya jalur-jalur tertentu. Oleh karena itu traveling salesman problem sangat erat hubungannya dengan cycle hamilton di mana dideskripsikan sebagai lintasan seorang salesman yang harus mengunjungi sebanyak n kota.

Misalkan

adalah jarak perjalanan dari kota i ke kota j dan salesman

ingin melakukan perjalanan dengan biaya total yang minimum, yang mana biaya total adalah jumlah masing-masing biaya tiap edge atau jalur perjalanannya (Vasudev, 2006, hal : 88). Sehingga traveling salesman problem didefinisikan sebagai suatu permasalahan optimasi yang bertujuan untuk mendapatkan rute terpendek (minimum) dari beberapa tempat atau kota yang harus dilalui seorang salesman tepat satu kali ia hingga kembali ke tempat awal keberangkatannya.

Jadi, secara sederhana traveling salesman problem merupakan permasalahan seorang salesman yang harus melakukan kunjungan tepat satu kali pada semua kota dalam sebuah lintasan sebelum dia kembali ke titik awal keberangkatannya.

Definisi 2.1.1 Andaikan khususnya jika perjalanan dan

dinotasikan sebagai kota-kota yang telah dikunjungi,

, maka kota

adalah kota ke i yang telah dikunjungi selama

merupakan matriks jarak yang mana anggota-anggota

dinotasikan sebagai jarak antara kota i dan kota j. Permasalahannya adalah menemukan rute terpendek untuk melewati seluruh kota tepat satu kali. Sehingga secara matematis traveling salesman problem didefinisikan sebagai :

Minimum

dengan kendala


10

Model dari permasalahan traveling salesman problem dapat digambarkan sebagai graph lengkap dengan n verteks. Bentuk traveling salesman problem dengan graph didefinisikan sebagai berikut. adalah

, di mana

dinotasikan dengan

lengkap yang sering .

adalah fungsi dari verteks , dan G memiliki rute perjalanan dengan biaya sebanyak k.

Definisi. 2.1.2 Suatu graph

dikatakan lengkap apabila graph sederhana

dengan n verteks dan setiap verteks pada G terhubung dengan verteks lainnya tepat satu edge.. Dengan catatan bahwa

memiliki tepat

edge dan

lintasan (Vasudev, 2006, hal : 20).

Contoh. 2.1 : Berikut diberikan gambaran traveling salesman problem dengan menggunakan graph lengkap dari lintasan hamilton. Andaikan suatu

graph

lengkap

adalah

dengan

dan maka

bentuk

graph

tersebut adalah :

Gambar 2.1 Graph lengkap dengan 6 verteks dan 15 edge


11

Namun, traveling salesman problem juga dapat dideskripsikan kedalam bentuk graph tidak lengkap seperti contoh berikut.

Contoh 2.2 : Diberikan suatu

dengan 5 verteks dan 8 edge

Gambar 2.2 Graph tidak lengkap dengan 5 verteks dan 8 edge

Tiap verteks pada suatu graph merupakan representasi dari kota-kota yang harus dikunjungi oleh seorang salesman, sedangkan edge yang menghubungkan antar verteks merupakan representasi dari nilai jarak antar kedua kota. Dalam graph, traveling salesman problem direpresentasikan sebagai graph berbobot.

Definisi. 2.1.3

Andaikan

suatu fungsi berbobot maka

adalah suatu graph dan

adalah disebut graph

bersama dengan fungsi

berbobot.

Definisi. 2.1.4 berbobot dan

Andaikan

dengan

adalah suatu graph

terhubung dengan T adalah spanning tree pada

maka

adalah jumlah bobot tiap edge pada T.


12

Ada dua metode yang sering digunakan dalam menyelesaikan traveling salesman problem, yaitu :

a.

Metode Optimal Metode ini menghasilkan nilai yang optimal dengan menemukan secara pasti nilai minimum dari traveling salesman problem. Biasanya metode optimal ini digunakan untuk menyelesaikan permasalahan yang ruang lingkupnya masih kecil. Namun, dibutuhkan waktu yang cukup lama jika lingkup permasalahan sudah memasuki skala besar yaitu jumlah kota yang harus dilalui sangat banyak. Metode optimal itu meliputi complete enumeration, branch and bound, cutting plane dan dynamic programming.

Contoh. 2.2 : Diberikan suatu graph dari perjalanan seorang salesman. `

Gambar 2.3 Graph lengkap dengan 5 verteks.

Andaikan seorang salesman ingin mengunjungi 5 kota, misalkan kota A, B, C, D dan E. Tabel 2.1 Jarak antar Kota Kota

A

B

C

D

E

A

0

100

250

400

180

B

100

0

160

100

120

C

250

160

0

240

450

D

400

100

240

0

380

E

180

120

450

380

0


13

Dengan menggunakan enumerasi lengkap tentukan rute yang harus ia lewati berdasarkan graph tersebut diatas dengan asumsi bahwa seluruh edge memiliki hambatan yang sama dan memulai perjalanan dari titik mana saja sehingga ia mampu menyelesaikan seluruh perjalanan dengan bobot tempuh yang minimum!

Penyelesaian :

Permasalahan diatas akan diselesaikan dengan metode enumerasi lengkap yang akan menjabarkan seluruh kemungkinan yang terdapat dalam graph, setelah itu akan dibandingkan lintasan mana yang paling minimum.

Untuk menyelesaikan permasalahan ini, kita misalkan dia memulai keberangkatan dari titik A. Secara manual dapat diselesaikan dengan memeriksa semua jalur yang memungkinkan untuk ia melewati empat kota lainnya dan akhirnya kembali ke kota awal yaitu A.

Sesuai dengan definisi sebelumnya bahwa permasalahan tersebut memiliki sebanyak

lintasan yang termasuk dalam ruang solusi. Ini berarti ada 24

lintasan yang dianggap sebagai rute alternatif. Namun, oleh karena terdapat rute yang dilalui memiliki bobot yang sama ketika rute tersebut dilewati secara berlawanan arah, maka ada

lintasan sehingga ada 12 lintasan yang menjadi

kemungkinan solusi permasalahan tersebut. Bobot total dihitung dengan cara menjumlahkan bobot tiap edge pada masing-masing lintasan.

Dari tabel jarak tersebut diperoleh bobot dari masing-masing edge adalah sebagai berikut.


14

Berikut ini adalah tabel rute-rute dari lintasan hamilton yang mungkin dari graph lengkap diatas dan total bobot yang akan ditempuh untuk masing-masing lintasan.

Tabel 2.2 Lintasan dari sirkuit hamilton. Rute alternatif

Bobot total 1060 1490 1070 1280 1310 1090 1070 1310 890 1320 1290 1100

Bobot minimum

890

Dari perhitungan diatas diperoleh rute yang harus dilalui olehnya agar bobot tempuh minimum adalah

dengan total bobot yaitu

890. Cara ini memang sangat ampuh karena didapat hasil yang benar-benar optimal yaitu diperolehnya rute dengan bobot tempuh yang paling minimum. Namun, hal itu hanya berlaku jika jumlah kota masih sedikit. Ketika permasalahan

diperbesar

maka

akan

menjadi

sangat

merepotkan

dan

menghabiskan waktu yang sangat banyak jika kendala yang berupa jumlah kota yang harus dikunjungi itu sangat banyak.


15

b. Metode Aproksimasi Metode aproksimasi atau sering disebut juga dengan metode heuristik menghasilkan penyelesaian yang hanya mendekati nilai yang optimal. Metode aproksimasi ini meliputi tabu search, local search, algoritma acak, simulasi annealing, algoritma greedy, ant colony dan neural network.

Contoh. 2.3 : Diberikan suatu graph dengan bobot yang sama dari contoh sebelumnya (Gambar 2.3). Dengan menggunakan algoritma greedy tentukan rute yang harus ia lewati berdasarkan graph tersebut (dengan asumsi yang sama seperti pada contoh kasus sebelumnya) sehingga ia mampu menyelesaikan seluruh perjalanan dengan bobot tempuh yang minimum!

Penyelesaian :

Diketahui

suatu

dengan

dan dengan bobot masing-masing edge

yaitu :

Sebelumnya akan dijelaskan mengenai algoritma greedy. Secara sederhana algoritma greedy merupakan algoritma untuk mencari solusi optimal dengan cara memulai lintasan dengan titik-titik yang memiliki edge yang paling minimum. Dan untuk menentukan titik yang akan dipilih selanjutnya adalah dengan memilih titik yang belum dilewati dan memiliki jarak yang paling minimum pula.

Andaikan

adalah graph berbobot dan n adalah jumlah verteks dengan

adalah edge dari verteks

ke verteks

maka

adalah bobot dari

edge tersebut.


16

Sehingga permasalahan menjadi

Langkah-langkah penyelesaian dengan algoritma greedy :

Langkah 1. Pilih titik awal Pilih titik awal keberangkatan

yang memiliki bobot paling minimum.

Bobot antar edge setelah diurutkan dari yang paling kecil hingga yang ke besar adalah

Berarti kita bisa memulai perjalanan dari titik A, B, atau D. Misalkan kita mulai dari titik B.

Langkah 2. Misalkan

maka

pilih begitu seterusnya hingga seluruh kota terlewati. Titik

selanjutnya dipilih dengan cara memilih kota yang belum pernah

dilewati dengan bobot yang paling minimum.

Berikut akan ditunjukkan juga ilustrasi berupa graph dengan lintasan yang terpilih dari permasalahan sehingga mempermudah untuk melihat tiap iterasi dari pemilihan tiap urutan verteks yang akan ditetapkan menjadi rute atau lintasan yang paling minimum.

Iterasi Pertama Oleh karena

, maka titik selanjutnya adalah sehingga


17

Pilih

Ada dua titik yang bernilai minimum yaitu BA dan BD, maka pilih salah satu titik. Misalkan A menjadi titik yang terpilih untuk dipakai berikutnya maka ulangi langkah sama seperti langkah sebelumnya. Gambar berikut menunjukkan titik yang terpilih dengan garis yang dipertebal adalah rute yang dilalui.

`

Gambar 2.4 Graph dengan edge yang terpilih setelah iterasi pertama

Iterasi Kedua Oleh karena


Pilih

Karena titik AE bernilai minimum, maka titik E terpilih menjadi titik solusi untuk mendapatkan titik berikutnya.

`

Gambar 2.5 Graph dengan edge yang terpilih setelah iterasi kedua


18

Iterasi Ketiga Oleh karena


Pilih

Karena titik ED bernilai minimum, maka titik D terpilih menjadi titik solusi untuk mendapatkan titik berikutnya.

`

Gambar 2.6 Graph dengan edge yang terpilih setelah iterasi ketiga

Iterasi Keempat Oleh karena


.

Dan karena hanya tinggal titik C yang belum dilalui maka titik C menjadi titik yang terpilih untuk kemudian kembali ke titik B (titik awal keberangkatan).

Gambar 2.7 Graph dengan edge yang terpilih setelah iterasi keempat


19

Maka iterasi dihentikan karena telah melewati seluruh titik dengan urutan dengan total bobot

dan

bentuk lintasan sebagai berikut.

`

Gambar 2.8 Solusi optimal

Terdapat perbedaan hasil yang cukup besar antara penyelesaian dengan metode enumerasi lengkap dan algoritma greedy meskipun permasalahannya sama dan masih dalam lingkup yang kecil yakni jumlah verteks dan edge yang tidak terlalu banyak. Hal itu dapat dilihat dari hasil yang diperoleh dengan cara enumerasi lengkap yaitu sebesar 890 sedangkan dengan menggunakan algoritma greedy diperoleh bobot sebesar 1060.

2.2

Algoritma Metropolis

Pada tahun 1953 Metropolis, Rosenbluth dan Teller memperkenalkan suatu metode dan algoritma yang sederhana untuk menyimulasikan perubahan benda dari yang bertemperatur sangat tinggi ke dalam “thermal equilibrium” dengan menampilkan langkah per langkah dari simulasi tersebut pada temperatur T (Aarts et al, 1989, hal : 14).

Mereka menyatakan permasalahan dengan menyimulasikan reaksi partikel dari suatu sistem fisis berdasarkan mekanika statistika. Mekanika statistika adalah aplikasi dari teori probabilitas yang menerapkan fungsi matematika untuk menangani permasalahan dalam jumlah populasi yang besar kedalam bentuk matematika. Metode dasar dari permasalahan ini dinyatakan sebagai probabilitas menemukan sistem fisis


20

didalam state dengan energi E yang sesuai dengan fungsi Gibs-Boltzmann yaitu dimana

adalah temperatur dan

Untuk setiap temperatur

adalah konstanta Boltzmann.

fungsi tersebut menurun secara monoton pada

energi E, sehingga state yang berada pada sistem fisis tampak lebih seperti menurunkan energi state dari tingginya energi state sebelumnya. Efek dari temperatur adalah ketika nilai

kecil probabilitas untuk energi state yang rendah adalah lebih

besar daripada energi state yang tinggi. Dengan kata lain, jika nilai temperatur besar, maka perbedaan antara dua probabilitas itu sangat kecil dan sistem menjadi lebih sama persis dalam kondisi state apapun.

Definisi 2.2.1 Diberikan state awal i dengan energi

, maka state selanjutnya j

dihasilkan dengan mengaplikasikan suatu mekanisme acak yang mana mengubah state awal menjadi state selanjutnya dengan tindakan yang kecil, sebagai contoh adalah pertukaran partikel-partikelnya. Energi dari state selanjutnya adalah perubahan energi yaitu

. Jika

, lebih kecil dari 0, maka state j diterima sebagai state

yang akan dipakai selanjutnya. Dan jika perubahan energi tersebut lebih besar atau sama dengani 0 maka state j diterima sebagai state berikutnya jika memenuhi syarat probabilitas berikut.

di mana T dinotasikan sebagai temperatur pada ruang panas dan

adalah konstanta

Boltzmann. Aturan penerimaan diatas disebut dengan kriteria Metropolis dan algoritmanya disebut dengan algoritma Metropolis.

Berikut adalah algoritma Metropolis untuk permasalahan minimasi. Mulai Ambil S sebagai solusi current. Ambil

sebagai solusi terpilih dengan distribusi seragam secara acak

dari tetangga S Jika

maka perbaharui


21

yang lain dengan probabilitas perbaharui selain itu tinggalkan S yang tidak berubah akhiri.

Kriteria

Metropolis

diaplikasikan

ke

simulasi

annealing

untuk

membangkitkan atau mendapatkan suatu barisan solusi dari permasalahan optimasi kombinatorial. Dengan menerapkan algoritma Metropolis ke simulasi annealing maka pada simulasi annealing akan terlihat sebagai suatu iterasi untuk mengevaluasi seluruh perubahan fungsi objektif dan nilai penurunan suhu.

2.3

Simulasi Annealing

Sebelum membahas tentang simulasi annealing, akan dijelaskan terlebih dahulu konsep dasar mengenai teori simulasi. Pengertian umum simulasi adalah suatu metodologi untuk melaksanakan percobaan dengan menggunakan model atau algoritma dari suatu sistem nyata. Konsep dasarnya adalah menggunakan beberapa perangkat untuk meniru sistem nyata guna mempelajari dan memahami sifat-sifat, perangai atau tingkah laku dan karakteristik operasinya. Simulasi juga merupakan alat percobaan untuk mengetahui data sampel serta taksiran statistik dari suatu model atau algoritma. Oleh karena itu, simulasi sangat berkaitan dengan percobaan untuk menaksir karakteristik dari sistem nyata tersebut dengan tujuan untuk merancang, menyusun dan mengembangkan sistem atau mengubahnya.

Simulasi yang baik membutuhkan perencanaan dan organisir yang bagus, namun bentuk simulasi tersebut tidak selalu tetap dan selamanya akan terus berubahubah sesuai dengan permasalahan dan kendala yang muncul. Pada umumnya terdapat lima langkah utama yang diperlukan dalam menggunakan simulasi sebagai metode penyelesaian suatu permasalahan, yaitu :


22

1. Tentukan sistem atau persoalan yang ingin disimulasikan. 2. Kembangkan model atau algoritma simulasi yang ingin digunakan. 3. Menguji model atau algoritma tersebut dan bandingkan karakteristiknya dengan karakteristik sistem nyata yang diadopsi, kemudian berlakukan model simulasinya. 4. Rancang percobaan-percobaan simulasi. 5. Jalankan simulasi dan analisis outputnya.

Pada awal tahun 1980 Kirkpatrick, Gellat dan Vecchi (1982; 1983) dan secara terpisah Cerny (1985) memperkenalkan konsep simulasi annealing untuk menyelesaikan permasalahan optimasi kombinatorial.

Definisi

2.3.1

Permasalahan

optimasi

kombinatorial

adalah

permasalahan

minimum dan maksimum yang dirincikan dengan himpunan beserta beberapa kendala didalamnya.

Penyelesaian suatu permasalahan optimasi kombinatorial bertujuan untuk menemukan solusi terbaik atau solusi optimal serta dapat dihitung yang nilainya terbatas ataupun tidak dari solusi-solusi alternatif yang ada.

Definisi

2.3.2.

Suatu

contoh

diformulasikan sebagai pasangan

permasalahan

optimasi

kombinatorial

dapat

, di mana ruang solusi S sebagai himpunan

terbatas dari seluruh kemungkinan solusi dan fungsi biaya f merupakan pemetaan yang didefinisikan sebagai berikut.

Dalam kasus minimum, permasalahannya adalah menemukan solusi

yang

harus memenuhi untuk semua

Sedangkan dalam kasus maksimum,

harus memenuhi kondisi


23

untuk semua

yang mana =

adalah global optimal solusi, baik itu minimum maupun maksimum, merupakan nilai optimal dan

adalah himpunan dari seluruh solusi

optimal.

Penyelesaian suatu permasalahan optimasi dengan menggunakan simulasi annealing terinspirasi dari proses fisika yakni pendinginan bahan logam yang disebut dengan annealing. Dalam proses pendinginan suatu benda, annealing diketahui sebagai proses penurunan suhu secara bertahap untuk mendapatkan tingkat energi yang rendah pada benda (dalam hal ini adalah logam) pada suhu ruang tertentu. Proses tersebut terdiri atas dua langkah (Kirkpatrick et al, 1982; 1983) sebagai berikut.

1. Menaikkan temperature ruang panas hingga mencapai nilai maksimum pada tiap-tiap lelehan benda tersebut. 2. Menurunkan temperatur secara perlahan hingga partikel-partikel benda tersebut menyusun diri mereka sendiri dalam bentuk yang stabil hingga akhirnya menjadi benda padat, yang dalam bentuk cair partikel-partikel benda tersebut mampu menyusun diri mereka sendiri secara acak.

Berikut adalah tabel dari analogi antara annealing dalam permasalahan proses pendinginan logam dan annealing dalam permasalahan optimasi.

Tabel 2.3 Analogi proses annealing Proses Annealing pada Logam

Permasalahan Optimasi

State

Solusi layak

Energi

Fungsi evaluasi

Keadaan stabil

Solusi optimal

Rapid quenching

Local search

Suhu

Parameter kontrol T

Pendinginan bertahap

Simulasi annealing


24

Dari tabel diatas diperoleh gambaran analogi antara permasalahan optimasi kombinatorial dan simulasi annealing yaitu sebagai berikut : 1. Solusi-solusi dari permasalahan optimasi kombinatorial (dalam hal ini adalah traveling salesman problem) ekuivalen terhadap state dari sistem annealing. 2. Total biaya atau bobot dari solusi-solusi tersebut ekuivalen terhadap energi state.

Simulasi annealing pada traveling salesman problem memiliki beberapa pertanyaan dasar yang harus diselesaikan dalam bentuk algoritma yaitu :

1. Apa solusinya? 2. Apa titik tetangga dari solusinya? 3. Berapa total biaya dari solusi tersebut? 4. Bagaimana cara menentukan solusi awalnya?

Berdasarkan analogi antara annealing dalam permasalahan proses pendinginan logam dan annealing dalam permasalahan optimasi ada beberapa pertanyaan tambahan untuk menentukan algoritma yang cocok dalam permasalahan yaitu sebagai berikut.

1. Bagaimana menentukan temperatur awal T? 2. Bagaimana menentukan rasio penurunan pendinginan

pada cooling

scheduling? 3. Bagaimana menentukan keadaan akhirnya? 4. Bagaimana menentukan kriteria penghentian iterasinya?

Dari beberapa pertanyaan tersebut, aplikasi dari analogi algoritma simulasi annealing harus memenuhi tiga rincian berikut.

1. Representasi dari permasalahan Representasi dari permasalahan mengandung representasi ruang solusi dan fungsi nilai. Fungsi nilai harus ditetapkan sebagai nilai efektif dari solusi yang berkaitan dengan objektif optimasi.


25

2. Mekanisme transisi Membangkitkan trail untuk mengubah solusi awal menjadi solusi berikutnya memiliki tiga langkah. Pertama, solusi awal yang baru dibangkitkan dari salah satu solusi current dengan menerapkan mekanisme pembangkitan. Kedua, perubahan nilai diantara dua solusi dihitung dan yang ketiga, tentukan keputusan diterima atau tidaknya solusi yang baru dan mengganti solusi current dengan solusi terbaru jika solusi yang baru tersebut diterima.

Evaluasi trail merupakan bagian yang menghabiskan waktu yang cukup banyak dalam algoritma simulasi annealing dan harus dilakukan dengan waktu yang seefisien mungkin. Mekanisme pembangkitan biasanya memilih solusi baru yang terkandung dalam salah satu solusi current dengan penyusunan ulang sederhana. Keputusan untuk menerima solusi baru tersebut berdasarkan atas kriteria penerimaan yaitu kriteria Metropolis berikut.

di mana c adalah parameter kontrol yaitu Boltzmann dan

adalah temperatur serta

dengan

adalah konstanta

adalah perubahan biaya antara

solusi baru dan solusi current dalam kasus permasalahan minimasi. Dalam mekanisme transisi terdapat proses modifikasi, langkah acak atau perubahan apa yang harus dilakukan terhadap elemen-elemen konfigurasi untuk menghasilkan konfigurasi berikutnya serta fungsi evaluasi atau fungsi objektif yang dapat menyatakan baik-buruknya suatu solusi terhadap permasalahan.

3. Jadwal pendinginan atau cooling schedule. Simulasi annealing bekerja dengan menjalankan algoritma Metropolis yang secara perlahan menurunkan nilai

hingga akhir proses penurunan.

yang

diperbaharui tersebut disebut sebagai jadwal pendinginan atau cooling


26

schedule. Secara resmi, cooling schedule adalah suatu fungsi

dari

yang merupakan bilangan real positif dalam iterasi dari algoritma Metropolis dan digunakan temperatur

sebagai definisi dari

probabilitas.

Dari rincian diatas diperoleh hal-hal penting yang harus diperhatikan dalam pelaksanaan proses simulasi annealing yaitu sebagai berikut.

1. Inisialisasi solusi awal yang dipilih secara acak. Memilih solusi awal secara acak sebagai posisi awal iterasi dalam proses simulasi.

2. Temperatur awal Temperatur awal harus memiliki nilai yang cukup besar agar mampu terhindar dari bad local optima. Biasanya nilai temperatur awal ini ditetapkan sebesar dua kali panjang suatu jalur yang telah dipilih secara acak.

3. Mekanisme pertukaran. Tentukan operator yang dibutuhkan untuk menentukan pertukaran solusi yang dianggap sebagai iterasi.

4. Fungsi objektif permasalahan Mengevaluasi setiap fungsi energi yang berubah karena proses iterasi dari mekanisme pertukaran.

5. Cooling schedule Fungsi cooling schedule yang umum digunakan adalah

di mana dengan range

adalah rasio pendinginan untuk menurunkan temperatur . Hasil yang bagus akan diperoleh jika

berada pada

(Chibante, 2010).


27

6. Kriteria penghentian proses simulasi. Ada beberapa metode yang biasa digunakan untuk mengontrol penghentian algoritma (Chibante, 2010), yaitu dilihat dari : a. Maksimum jumlah iterasi b. Nilai minimum temperatur c. Nilai minimum fungsi objektif d. Nilai minimum dari tingkat penerimaan.

Sebagian besar penerapan simulasi annealing mengikuti algoritma dari barisan sederhana berikut (Michalewicz et al, 2000, hal : 122).

Langkah 1 : pilih Langkah 2 :

secara acak.

Ambil titik

dari tetangga pada

jika

lebih baik daripada maka pilih selain itu pilih

dengan probabilitas

ulangi langkah ini hingga

Langkah 3 :

kali.

tetapkan jika maka ulangi langkah 2 selain itu pergi ke langkah 1

dimana

adalah temperatur awal,

pendinginan dan

adalah jumlah iterasi,

adalah rasio

adalah temperatur setelah membeku.

Walaupun algoritma simulasi annealing secara konsep terlihat sederhana yaitu membangkitkan parameter optimal seperti temperatur awal, annealing schedule, parameter fungsi penerimaan dan hal lainnya yang diperlukan bukan berarti ia mudah dilaksanakan secara langsung. Pengaturan parameter untuk simulasi annealing adalah tidak bebas dan cara terbaik untuk mencapainya adalah dengan melalui trial dan


28

error. Selain itu banyak penelitian telah menunjukkan bahwa menentukan algoritma simulasi annealing sangat sensitif terhadap parameter dan pelaksanaannya sangat tergantung pada penyusunan parameternya (Chibante et al, 2010, hal : 218).

Berikut ini adalah flowchart dari algoritma simulasi annealing (Chibante, 2010). Parameter Awal

N

Penelusuran dihentikan?

Bangkitkan Solusi Baru

Evaluasi Solusi

Y

Output

Diterima? N

Stop Y

Turunkan Temperatur

Update state terbaru

Ubah Temperatur

N

Y

Gambar 2.9 Flowchart untuk Algoritma Simulasi Annealing


29

2.4 Simulasi Annealing dan Traveling salesman problem.

Traveling salesman problem dikenal sebagai suatu permasalahan optimasi yang bersifat klasik dan non-deterministic polynomial-time complete yang berarti tidak ada penyelesaian yang paling optimal selain harus mencoba seluruh kemungkinan penyelesaian yang ada. Permasalahan ini melibatkan seorang salesman yang harus melakukan kunjungan sekali pada semua kota dalam sebuah lintasan sebelum dia kembali ke titik awal keberangkatannya.

Berawal dari sinilah dikembangkan metode-metode pemecahan permasalahan traveling salesman yang diharapkan dapat memberikan pemecahan yang optimal, salah satunya adalah metode simulasi annealing. Simulasi annealing adalah suatu metode derivative free optimization yang digunakan pada permasalahan optimasi dalam bentuk kontinu maupun diskrit (kombinatorial). Keunggulan dari metode simulasi annealing adalah kemampuan untuk menghindari bad local optima berdasarkan aturan penerimaan terhadap calon solusi berikutnya.

Annealing adalah proses metalurgi yaitu memanaskan suatu benda padat (biasanya logam) hingga cair kemudian mendinginkannya secara perlahan hingga ia kembali padat. Atom-atom penyusun benda tersebut memiliki energi dengan temperatur yang sangat tinggi. Hal ini mengakibatkan atom-atom benda tersebut memiliki kebebasan untuk menyusun diri mereka sendiri. Pada saat temperatur berkurang maka energi atom-atom tersebut juga menurun hingga akhirnya kondisi energi minimum tercapai. Dalam permasalahan optimasi, simulasi annealing dianalogikan sebagai proses annealing tersebut.

Dalam mengadopsi simulasi annealing pada traveling salesman problem, Kirkpatrick (1982; 1983) dan Cerny (1985) menyarankan untuk menggunakan aturan perpindahan 2-opt ketika memilih titik yang bertetanggaan dengannya. Cerny (1985) juga menjelaskan langkah sederhana dalam perubahan posisi antar kota tetapi bagian dalam diantara kota tersebut tidak berubah. Namun dalam bukti nyatanya pendekatan ini tidak efektif.


30

Kirkpatrick, dkk (1982; 1983) menggunakan suatu algoritma untuk menyelesaikan permasalahan dalam skala besar (sekitar 6000 kota) tetapi mereka tidak menyediakan informasi yang lengkap tentang kualitas dari solusi yang ditemukan, sehingga nilai dan simulasi annealing pada traveling salesman problem tidak pernah jelas secara numerik.


BAB 2 LANDASAN TEORI

Recommend Documents