Metode Hill ClimbingPenyusun:

Denny Agustiawan

B. Pendakian Bukit (Hill Climbing)

Metode ini hampir sama dengan metode pembangkitan & pengujian,hanya saja proses pengujian

dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat

tergantung padafeedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan

menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya

yang mungkin.

B.L. Simple Hill Climbing

Algoritma:

1. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika

tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

2. Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator

baru yang akan diaplikasikan pada keadaan sekarang:

(a) Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan

keadaan yang baru.

(b) Evaluasi keadaan baru tersebut.

(i) Jika keadaan baru merupakan tujuan, keluar.

(ii) Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan

keadaan baru tersebut menjadi keadaan sekarang.

(iii) Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.

Pada simple hill climbing ini, ada 3 masalah yang mungkin, yaitu:

o Algoritma akan berhenti kalau mencapai nilai optimum lokal.

o Urutan penggunaan operator akan sangat berprngaruh pada penemuan solusi.

. Tidak diijinkan untuk melihat satupun langkah sebelumnya.

Contoh 2.4: Traveling Salesman Problem dengan eimple hill climbing.

Disini ruang keadaan berisi semua kemungkinan lintasan yang mungkin. Operator digunakan

untuk menukar posisi kota-kota yang bersebelahan. Fungsi heuristik yang digunakan adalah

panjang

lintasan yang terjadi.

Operator yang akan kita gunakan, adalah menukar urutan posisi 2 kota dalam suatu lintasan.

Apabila ada n kota, dan kita ingin mencari kombinasi lintasan dengan menukar posisi urutan 2

kota,

maka kita akan mendapatkan sebanyak : n!

2t(n-2)l

Sehingga kalau ada 4 kota, kita bisa memperoleh :

kombinasi.

Keenam kombinasi ini akan kita pakai semuanya sebagai operator,

yaitu:

* Tukar 1, 2 (menukar urutan posisi kota ke-1 dengan kota ke-2).

* Tukar 2, 3 (menukar urutan posisi kota ke-2 dengan kota ke-3).

* Tukar 3, 4 (menukar urutan posisi kota ke-3 dengan kota ke-4).

* Tukar 4, 1 (menukar urutan posisi kota ke-4 dengan kota ke-1).

* Tukar 2, 4 (menukar urutan posisi kota ke-2 dengan kota ke-4).

* Tukar 1, 3 (menukar urutan posisi kota ke-1 dengan kota ke-3).

Pada Gambar 2.22 terlihat bahwa, pada keadaan awal, lintasan terpilih adalah ABCD (=19). Pada

level pertama, hill climbing akan mengunjungi BACD (=17) yang ternyata memiliki nilai

heuristic lebih kecil dibandingkan dengan ABCD (17<19), sehingga BACD menjadi pilihan

selanjutnya dengan operator terpakai Tukar1,2. Pada level kedua, hill climbing akan mengunjung

ABCD. Karena operator Tukar 1, 2 sudah digunakan oleh BACD, maka dipilih node yang lain

yaitu BCAD (=15). Karena nilai heuristik BCAD lebih kecil dibanding dengan BACD (15<17),

maka node BCAD akan menjadi pilihan selanjutnya dengan operator Tukar2,3. Kemudian hill

climbing akan mengunjungi CBAD (=20). Karena nilai heuristik CBAD lebih besar jika

dibanding dengan BCAD (20>17), maka dipilih node lain. Pencarian menuju ke node BACD,

karena operator Tukar2,3 sudah pernah digunakan oleh BCAD, maka dipilih node lain.

Kunjungan berikutnya ke node BCDA (=18). Niiai inipun masih lebih besar dari niiai heuristic

BCAD, sehingga dipilih node lain. Node vang dikunjungi berikutnya adalah DCAB (=19). Nilai

heuristic DCAB ternyata juga lebih besar dibanding dengan BCAD, sehingga pencarian

dilarrjutkan di node lainnya lagi, yaitu BDAC (=14). Nilai heuristik ini sudah lebih kecil

daripada nilai heuristik node BCAD (14<15), maka sekarang node ini yang akan diekplorasi.

Pencarian pertama ditemukan node DBAC (=21), yang lebih besar daripada nilai BDAC. Nilai

heuristik yang lebih kecil diperoleh pada node BDCA (=13). Sehingga node BDCA ini akan

diekplorasi. Pencarian pertama sudah mendapatkan node dengan nilai heuristik yang kebih kecil,

yaitu DBCA (=12). Sehingga node ini diekplorasi juga. Dari hasil ekplorasi dengan pemakaian

semua operator, ternyata sudah tidak ada node yang memiliki nilai heuristik yang lebih kecil

disbanding dengan nilai heuristik DBCA, sehingga sebenarnya node DBCA (=12) inilah lintasan

terpendek yang kita cari (SOLUSI). Misalkan kita tidak menggunakan semua operator,

melainkan kita

hanya menggunakan 4 operator pertama saja, yaitu :

* Tukar 1,2 (menukar urutan posisi kota ke'1 dengan kota ke'2).

* Tukar 2, 3 (menukar urutan posisi kota ke-2 dengan kota ke'3).

* Tukar 3,4 (menukar urutan posisi kota ke-3 dengan kota ke'4).

* Tukar 4, 1 (menukar urutan posisi kota ke-4 dengan kota ke'l).

maka pencarian dengan simple hill climbing ini dapat dilihat pada Gambar 2.23. Lintasan

terpendek yang diperoleh adalah B-C-A-D yaitu sebesar 15. Disini kita akan terjebak pada nilai

minimum local yang disebabkan oleh kurangnya operator yang kita gunakan. Kita tidak dapat

memperoleh nilai minimum globalnya yaitu sebesar 12.

B.2. SteepesLAscent Hill Climbing

Steepest-ascenhti II climbing sebenarnyah ampir sama dengan sirnple hitt ctimbing, hanya saja

gerakan pencarian tidak dimulai dari posisi paling kiri. Gerakan selanjutnya dicari berdasarkan

nilai heuristic terbaik. Dalam hal ini urutan penggunaan operator tidak menentukan penemuan

solusi.

Algoritma:

1. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika

tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.

2. Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberikan perubahan pada keadaan

sekarang.

a. Tentukan succ sebagai nilai heuristik terbaik dari successor-successor.

b. Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang:

i. Gunakan operator tersebut dan bentuk keadaan baru.

ii. Evaluasi keadaan baru tersebut. Jika merupakan tujuan,keluar. Jika bukan, bandingkan nilai

heuristiknya dengan succ. Jika lebih baik, jadikan nilai heuristic keadaan baru tersebut sebagai

succ. Namun jika tidak lebih baik, nilai succ tidak berubah.

c. Jika succ lebih baik daripada nilai heuristik keadaan sekarang, ubah node suCC menjadi

keadaan sekarang.

Pada steepest-ascent hill climbing ini, ada 3 masalah yang mungkin,

yaitu:

- Local optimum: keadaan semua tetangga lebih buruk atau sama dengan keadaan dirinya.

- Plateou: keadaan semua tetangga sama dengan keadaan dirinya.

- Ridgez local optimum yang lebih disebabkan karena ketidakmampuan untuk menggunakan 2

operator sekaligus.

Pada Gamb at 2.24, terlihat bahwa, keaclaan awal, iintasan terpiiih adalah ABCD (19). Pada

level pertama, hili climbing akan rnemiiih nilai heuristik terbaik dari keenam succesor yang ada,

yaitu: BACD(17), ACBD(12), ABDC(I8), DBCA(12), ADCB (18) atau CBAD(20). Tentu saja

yang terpilih adalah ACBD, karena memiliki nilai heuristik paling kecil (=12;. Dari ACBD ini

akan dipilih nilai heuristik terbaik dari succesornya yaitu: CABD(15), ABCD(19), ACDB(13),

DCBA(19), ADBC(16) atau BCAD(15). Ternyata dari keenam successor tersebut memiliki nilai

heuristik yang lebih besar disbanding dengan ACBD. Sehingga tidak akan ada perubahan nilai

keadaan (tetap ACBD). Hasil yang diperoleh, lintasannya adalah ACBD (12).

Contoh 2.6:8-puzzle dengan steepest a,scent hill climbing.

Pada permainan 8-puzzle, keadaan awal dan tujuan adalah sebagai

berikut:

Operator yang digunakan untuk menggerakkan dari satu keadaan ke

keadaan berikutnya adalah:

* Ubin kosongkekanan

* Ubin kosong ke kiri

* Ubin kosong ke atas

* Ubin kosong ke bawah

Dengan menggunakan bentuk pohon untuk merepresentasikan ruang keadaan, gunakanlah

metode Stepest Ascent Hill Climblng untuk mencari langkah-langkah yang harus ditempuh dari

keadaan awal sampai mendapatkan tujuan. Fungsi heuristik yang digunakan adalah jumlah ubin

yang menempati posisi yang benar.

Pada Gambar 2.26 terlihat bahwa semula ada 3 operator yang bias digunakan, yaitu ubin kosong

digeser ke kanan, kiri dan bawah. Masing-rnasing kondisi hasil dari implementasi operator

memberikan nilai heuristik 4, 6, dan 5. Nilai heuristik terbesar adalah 6, sehingga kondisi kedua

yang dipilih. Pada tahap kedua, operator yang bias digunakan hanya 2, yaitu ubin kosong digeser

ke kanan dan ke bawah. masing-masing dengan nilai heuristik 5 dan 7. Nilai heuristic yang

dihasilkan adalah 7, dan kondisi ini dipilih. Pada tahap ketiga, ada 3 operator yang digunakan,

yaibu ubin kosong digeser ke atas, kanan, dan bawah. Masing-masing kondisi memiliki nilai

heuristik 6, 8, dan 6. Karena nilai 8 merupakan solusi, maka pencarian telah berakhir.

C. Pencarian Terbaik Pertama (Best-First Search)

Metode best-first search ini merupakan kombinasi dari rnetode depth first search dan metode

breadth-first search dengan mengambil kelebihan dari kedua metode tersebut. Apabila pada

pencarian dengan metode hill climbing tidak diperbolehkan untuk kembali ke node pada level

yang lebih rendah meskipun node pada level yang lebih rendah tersebut memiliki nilai heuristik

yang lebih baik, lain halnya dengan metode best-first search ini. Pada metode best-iirst search,

pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata

node pacia lebih yang lebih tinggi ternyata memiliki nilai heuristik yang lebih buruk.

C.1. OR Graph

Pada metode depth-first search mampu menernukan solusi tanpa harus mengeksplorasi semua

cabang dalam level yang sama. Pada metode breadth-first search juga cukup bagus, karena

mampu mengantisipasi adanya lintasan yang mengalami jalan buntu. Kombinasi kedua metode

ini sangat dimungkinkan, dirnana pencarian dilakukan dengan hanya melihat satu lintasan,

namun dernikian masih memungkinkan untuk berpindah ke lintasan lain apabila lintasan lain

tersebut lebih menjanjikan untuk mendapatkan solusi. Untuk mengimplementasikan metode ini

dengan mengunakan graph keadaan, dibutuhkan 2 antrian yang herisi node-node, yaitu:

- OPEN, yang berisi node-node yang sudah dibangkitkan, sudah memiliki fungsi heuristik

namun belum diuji. Umumnya berupa antrian berprioritas yang berisi elemen-elemen dengan

nilai heuristik tertinggi.

- CLOSED berisi node-node yang sudah diuji. Disamping 2 antrian tersebut, kita juga harus

memiliki fungsi heuristik yang akan mengestimasi seberapa baik dibangkitkannya setiap node.

Fungsi f(n) merupakan pendekatan dari fungsi f(n) yang merupakan fungsi evaluasi yang

sebenarnya terhadap node n.Biasanya fungsi f(n) merupakan kombinasi dari 2 komponen, yaitu

g(n) dan h'(n). Fungsi g(n) merupakan biaya yang dikeluarkan dari keadaan awal sampai ke node

n. Nilai yang diperoleh g(n) bukan merupakan hasil estimasi, namun merupakan nilai eksak yang

diperoleh dengan cara menjumlahkan total biaya yang telah dikeluarkan dari keadaan awal

sampai ke node n. Apabila ada beberapa lintasan dari keadaan awal ke node g tersebut, maka kita

ambil lintasan terbaiknya. Fungsi h'(n) merupakan estimasi tambahan biaya yang harus

dikeluarkan dari node n sampai mendapatkan tujuan.

Algoritma:

1. Tempatkan node awal A pada antrian OPEN.

2. Kerjakan langkah-langkah berikut hingga tujuan ditemukan atau antrian OPEN sudah kosong:

a. Ambil node terbaik dari OPEN:

b. Bangkitkan semua successornya;

c. Untuk tiap-tiap successor kerjakan:

I Jika node tersebut belum pernah dibangkitkan sebelumnva. evaluasi node tersebut dan

masukkan ke OPEN

ii. Jika node tersebut sudah pernah dibangkitkan sebelumnya,ubah parent jika hntasan baru lebih

menjanjikan.Hapus node tersebut dari antrian OPEN.

Gambar 2..27 rnenunjukkan metode pencarian terbaik pertama. Diasurnsiknn bahwa node

dengan nilai yang lebih besar, memiliki nilai evaluasi yang lebh baik. Pada saat keadaan awal,

antrian berisi

A. Pengujian dilakukan pada level pertama, node D merniliki nilai terbaik, sehingga menempati

antrian pertama, disusul dengan C dan

B. Node D memiiiki cabang E dan F yang masing-rnasing bernilai 2 dan 4. Dengan demikian C

merupakan pilihan terbaik dengan menempati antrian pertama. Demikian seterusnya.

C.2. Algoritma A*

Algoritma A* merupakan perbaikan dari metode best-first search dengan memodifikasi fungsi

heuristiknya. A* akan meminimumkan total biaya lintasan. Pada kondisi yang tepat, A* akan

memberikan solusi yang terbaik dalam waktu yang optimal. Fungsi f sebagai estimasi fungsi

evaluasi terhadap node n, dapatdituliskan:

f(n)=g(n)+h'(n)

dengan:

f(n) = fungsi evaluasi

g(n) = biaya yang sudah dikeluarkan dari keadaan awal sampai keadaan n.

h'(n) = estimasi biaya untuk sampai pada suatu tujuan mulai dari n.

Dengan demikian dapat dikatakan bahwa:

o Apabila h' = h, berarti proses pelacakan sudah sampai pada suatu tujuan.

o Apabila g = h' = 0, maka dikendalikan oleh apapun. f random, artinya sistem tidak dapat r

Apabila g=k (konstanta biasanya menggunakan breadth first search.

Pada Algoritma A*, juga dibutuhkan 2 antrian, yaitu:

- OPEN,yang berisi node.node yang sudah dibangkitkan, sudah memiliki fungsi heuristik

namun belum diuji.

- CLOSED berisi node-node yang sudah diuji

Sebelum kita menuju ke algoritma A* lebih lanjut, akan dibahasterlebih dahulu tentang

algoritma A.

Algoritma A:

1. Set: OPEN={S}, dan CLOSED=0, dengan S adalah node yang dipilih sebagai keadaan awal.

2. Kerjakan jika OPEN belum kosong:

a.Cari node n dari OPEN dimana nilai f(n) minimal.Kemudian tempatkan n Pada CLOSED.

b. Jika n adalah node tujuan, keluar. SUKSES.

c. Ekspan node n keanak-anaknya.

d. Kerjakan untuk setiap anak n, yaitu n':

i. Jika n belum ada di OPEN atau CLOSED, maka:

1. Masukkan n ke OPEN' Kemudian set backpointerdari n ke n.

2. Hitung:

a. h(n);

b. g(n) = g(n)+c(n,n); dengan c(n,n) adalah biaya dari n ke n', dan

c. f(n) = g(n)+h(n).

ii. Jika n'telah ada di OPEN atau CLOSED dan jika g(n) lebih kecil (untuk versi n'yang

baru), maka:

1. Buang versi lama n'.

2. Ambil n'di OPEN, dan set backpointer dari n' ke n.

Algoritma A* sebenarnya merupakan pengembangan dari algoritma A, dengan batasan bahwa

h(n) < h*(n), dengan:

o h(n) = biaya yang sebenarnya dari biaya minimal lintasan dari n ke sembarang tujuan.

o g(n) = biaya yang sebenarnya dari biaya minimal lintasan dari S ke n.

o f(n) = h(n) + g(n); adalah biaya ysng sebenarnya dari biaya minimum solusi lintasan dari S ke

sembarang tujuan yang melalui n.

Nilai h dapat diterima jika h'(n) s h(n). Pencarian dengan algoritma A* ini akan lebih sempurna

jika faktor percabangannya terbatas, dan untuk setiap operator memiliki biaya yang bernilai

positif (total

jumlah node dengan h'(.) < h(tujuan) terbatas.

Contoh 2.7:

Misalkan kita memiliki ruang pencarian seperti terlihat pada Gambar 2.28. Node M merupakan

keadaan awal, dan node T merupakan tujuannya. Biaya edge yang menghubungkan node M

dengan node A

adalah biaya yang dikeluarkan dari untuk bergerak dari kota M ke kota A. Nilai g diperoleh

berdasarkan biaya edge minimal. Sedangkan nilai h' di node A merupakan nilai perkiraan

(estimasi) terhadap

biaya yang harus diperlukan dari node A untuk sampai ke tujuan (nilai ini tidak menjamin

keberadaan solusi, hanya perkiraan saja). h'(n) bernilai co jika sudah jelas tidak ada hubungan

antara node n

dengan node tujuan (alan buntu). Kita bisa merunut nilai untuk setiap node seperti terlihat pada

Tabel 2.6.

Pada Tabel 2.6 tersebut dapat dilihat bahwa, karena h(n) < h(n) untuk setiap n, maka nilai h dapat

diterima.

Apabila kita menggunakan fungsi evaluasi: f(n) = h'(n), maka solusi yang didapat adalah lintasan

terpendek: M-C-H-T dengan biaya sebesar 7. Alur penelusuran dapat dilihat pada Tabel 2.7.

Apabila masalah ini kita selesaikan dengan menggunakan Algoritma A*, dengan fungsi evaluasi:

f(n) = g(n) + h'(n), maka solusi yang didapat adalah lintasan terpendek: M-C-H-T dengan biaya

sebesar 7. Alur penelusuran dapat dilihat pada Tabel 2.8.

Dengan menggunakan Algoritma A* ini, nilai h' dari pelacakan yang terjadi mungkin di bawah

dari perkiraan (underestimate) atau bias jadi di atas dari perkiraan (overestirnate) terhadap nilai

h.

Gambar 2.29 menunjukkan nilai h' yang underestimote terhadap h. Misalkan biaya untuk tiap

edge=l (g=1), masing-masing node B, C, dan D memiliki nilai estimasi h' sama dengan 3, 4, dan

5, maka akan

dipilih jalur dengan biaya terendah yaitu ke node B dengan biaya 4 (3+1). Kemudian node B

dieksplorasi. Andaikan node B hanya memiliki 1 cabang, yaitu E dengan h' = 3 juga, maka biaya

yang akan

dikeluarkan dari A sampai E menjadi 5 (3+2). Bila E dieksplore dan hanya dirniliki satu cabang

yaitu F dengan h' = 3 juga, maka biaya yang dikeluarkan dari A sampai E menjadi 6 (3+3).

Keadaan ini jauh lebih buruk dibandingkan jika arah pelacakan sebelumnya dari A ke C.

Gambar 2.30 menunjukkan nilai h'yang overestimate terhadap h.Misalkan biaya untuk tiap

edge=l (g=1), masing-masing node B, C, dan D memiliki nilai estimasi h'sama dengan 3, 4, dan

5, maka akan dipilih jalur dengan biaya terendah yaitu ke node B dengan biaya 4 (3+1).

Kemudian node B diekspansi. Andaikan node B hanya memiliki 1 cabang, yaitu E dengan h'= 2,

maka biaya yang akan dikeluarkan dari A sampai E menjadi 4 (2+2) juga. Bila E diekspansi dan

hanya dimiliki satu cabang yaitu F dengan h' = 1, maka biaya yang dikeluarkan dari A sampai E

menjadi 4 (1+3) juga. Bila F diekspansi dan hanya dimiliki satu cabang yaitu G dengan h' = 0,

maka biaya yang dikeluarkan dari A sampai G menjadi 4 (O+4) juga. Diperoleh nilai estimasi

yang selalu konstan yaitu 4. Jika fungsi heuristik h'dapat diterima, maka dapat dikatakan bahwa

algoritma ini optimal (memiliki lintasan terpendek). Disini, tidak

akan pernah terjadi overestimate dari suatu keadaan ke tujuan. D. Simulated Annealing Ide dasar

simulated annealing terbentuk dari pemrosesan logam Annealing (memanaskan kemudian

mendinginkan) dalam pemrosesan logam ini adalah suatu proses bagaimana membuat bentuk

cair berangsur-angsur menjadi bentuk yang lebih padat seiring dengan penurunan temperatur.

Simulated anneoling biasanya digunakan untuk penyelesaian masalah yang mana perubahan

keadaan dari suatu kondisi ke kondisi yang lainnya membutuhkan ruang yang sangat luas,

misalkan perubahan gerakan dengan menggunakan permutasi pada masalah Tlavelling Salesman

Problem. Pada eimulated annealing, ada 3 parameter yang sangat menentukan, yaitu: tetangga,

gain, temperatur, pembangkitan bilangan random. Tetangga akan sangat berperan dalam

membentuk perubahan

pada solusi sekarang. Pembangkitan bilangan random akan berimplikasi adanya probabilitas.

Algoritma

1. Evaluasi keadaan awal. Jika keadaan awal merupakan tujuan, maka pencarian berhasil dan

KELUAR. Jika tidak demikian, lanjutkan dengan menetapkan keadaan awal sebagai kondisi

sekarang.

2. Inisialisasi BEST_SO_FAR untuk keadaan sekarang.

3. Inisialisasi T sesuai dengan annealing schedule.

4. Kerjakan hingga solusi ditemukan atau sudah tidak ada operator baru lagi akan diaplikasikan

ke kondisi sekarang.

a. Gunakan operator yang belum pernah digunakan tersebut untuk menghasilkan kondisi baru.

b. Evaluasi kondisi yang baru dengan menghitung:

AE = nilai sekarang - nilai keadaan baru.

i. Jika kondisi baru merupakan tujuan, maka pencarian berhasil dan KELUAR.

ii. Jika bukan tujuan, namun memiliki nilai yang lebih baik daripada kondisi sekarang,

maka tetapkan kondisi baru sebagai kondisi sekarang. Demikian pula tetapkan

BEST_SO_FAR untuk kondisi yang baru tadi.

iii. Jika nilai kondisi baru tidak lebih baik dari kondisi sekarang, maka tetapkan kondisi

baru sebagai kondisi sekarang dengan probabilitas:

p’= e-AE/T

Langkah ini biasanya dikerjakan dengan membangkitkan suatu bilangan random r pada range [0

1]. Jika r < p', maka perubahan kondisi baru menjadi kondisi sekarang diperbolehkan. Namun

jika tidak demikian, maka tidak akan dikerjakan apapun.

c. Perbaiki T sesuai dengan annealing scheduling.

5. BEST-SO_FAR adalah jawaban yang dimaksudkan.

Dari algoritma tersebut, sebenarnya secara umum ada 3 hal yang perlu disoroti pada simulated

annealing, yaitu:

a. Nilai awal untuk temperatur (T0).

Nilai T0 biasanya ditetapkan cukup besar (tidak mendekati nol), karena jika T mendekati 0 maka

gerakan simulated annealing akan sama dengan hill climbing.

b. Kriteria yang digunakan untuk memutuskan apakah temperature sistem seharusnya dikurangi.

c. Berapa besarnya pengurangan temperatur dalam setiap waktu.

Contoh 2.8: masalah TSP

Ada beberapa hal yang periu diperhatikan clalann menyelesaikan permasalahan TSP dengan

simulated anneulirug. Sebagai catatan, perlu diketahui bahwa masalah TSP yang diherikan pada

contoh ini sedikit berbeda dengan TSP sebelurnnya. Pada TSP ini kota asal dan tujuannya adalah

sama.

o Operator

Ada beberapao perator yang bisa digrrniika-n.L lerikut ini adalali salah satu contoh operator

untuk menentukan jalur.Misalkan jumlah kota yang akan dikunjungi adalah NC.

* Kota-kota disimpan pada larik L.

* Kita bangkitkan 2 bilangan random antan'a 1 sampai NC, rnisalkan kedua bilangan itu adalah

Nl dan N2 dengan N1 < N2.

* Depan = L(1) sampai L(N1-1).

* Tengah = L(N1) sampai L(N2).

* Belakang = L(N2+1) sampai L(NC).

* Kita bangkitkan bilangan random r, apabiia r < 0,5; maka:

o DepanBaru = Depan.

c TengahBaru = Tengah dengan urutan dibalik.

o BelakangBaru = Belakang.

o Lbaru = [DepanBaru TengahBaru BelakangBaru]

* Jika r > 0,5; maka kerjakan:

o Sementara = [Depan Belakangl, misalkan memiliki M elemen.

o Bangkitkan bilangan random r dengan nilai antara 1

.. sampai M.

o DepanBaru = Sementara(1:r).

o TengahBaru = Tengah.

o BelakangBaru = Sementara(r+L:M).

o Lbaru - [DepanBaru TengahBaru BelakangBaru]

Contoh:

Misalkan jalur yang ada adalah:

L=( 4 3 6 9 11 2 5 1 7 8 12 10) --) NC=12

Kita bangkitkan bilangan random, misal: N1=4 dan N2=10' Maka

kita bisa dapatkan:

o Depan

. Tengah

. Belakang

Kita bangkitkan bitangan random r, apabila r < 0,5; maka:

. DepanBaru = [4 3 6].

. TengahBaru = [8 7 1 5 2 11 9 ] .

o BelakangBaru = [12 10].

. Lbaru = [4 3 6 8 7 1 5 2 11 9 12 10]

Jika r > 0,5; maka kerjakan:

. Sementara = [4 3 6 12 10], M=5.

. Bangkitkan bilangan random r, misal r=2.r DepanBaru = [4 3].

. TengahBaru = [9 11 2 5 1 7 8].

. BelakangBaru = [6 12 10].

. Lbaru = [ 4 3 9 11 2 5 1 7 8 6 12 10 ]

Apabila data diberikan dalam bentuk koordinat kota ke-i (xi,yi), dengan jumlah kota NC, maka

pseudocode dapat diberikan sebagai

berikut.

c, Pseudocode

Function Pj gJalur(L): real;

1. Panjang= 0;

2. For i=1 to (NC-l) do

3. Panjang = Panjang + sqrt((xi*r - xi)2 + (yi*r - yi)2);

4. PjgJalur = Paniang;

Function JalurBaru(L): arrayNC;

1. Bangkitkan 2 bilangan random N1 dan N2 antara 1 sampai

NC dengan N1< N2

2. Depan = Ul) sarnpd UN1-1);

3. Tengah = UN1) sampd L(Nz);

4. Belakang = UN2+1) sampai UNC);

5. Bangkitkan bilangan random r.

6. If r < 0,5 then

7. DepanBaru = Depan.

8. TengahBaru(1..NT) = Tengah(NT..l.); dengan NT=N2-N1+1.

9. BelakangBaru = Belakang.

10. Lbaru = [DepanBaru TengahBaru BelakangBaru]

11. else

12. Sementara = [Depan Belakang]; dengan M elemen.

13. Bangkitkan bilangan random r dengan nilai antara 1 sampai M.

14. DepanBaru = Sementara(1..r).

15. TengahBaru = Tengah.

16. BelakangBaru = Sementara(r+1..M).

17. Lbaru - [DepanBaru TengahBaru BelakangBaru]

18. JalurBaru = LBaru

Procedure SimulatedAnneal (T:real; L:arrayNC; NC:integer; var

Lbaru:arrayNC; var sukses:integer);

1. Maxlterasi = 100*NC;

2. MaxSukses = 10xNC:

3. Sukses = 0;

4. Lbaru = L;

5. MinPjgJalul = PjgJalur(L);

6. For i=1 to Maxlterasi do

7 Jalur = JalurBaru(L);

8 P;g = PjgJalur(Jalur);

9 Bangkitkan bilangan random r.

10 If r < e{Pje-MinggJalwthVern Lbaru=Jalur;

11 If Jalur < MinPjgJalur then

12 MinPjgJalur = Pjg;

13 Sukses = Sukses +1;

14 If Sukses = MaxSukses then BREAK:

Misalkan kita ingin mensimulasikan algoritma ini untuk 15 kota, dengan temperatur awal sebesar

50 dan pendinginan sebesar 10% (pengurangan temperatur), maka penyelesaian TSP adalah:

Program TSP-SA;

1. NC = 15;

2. XC -) bangkitkan bilangan random sebanyak NC'

3. YC -) bangkitkan bilangan random sebanyak NC.

4. T= 50;

5. Sukses = 1;

6. L -) t1 23 4 ... L l l ;

7. While sukses > 0 do

8. SimulatedAnneal(T, L, NC, Lbaru,Sukses);

9. T = 0,9*T;

Misalkan ke-15 kota tersebut memiliki koordinat seperti terlihat pada

Tabel2.9

Jalur terpendek L-O-N-K-D-F-I-A-M-E-H-B-C-GJ, dengan panjang jalur sebesar 3,7384.

sedangkan Gambar 2.31 menunjukkan jalur terpendek yang diperoleh secara grafis

.

2.3 REDUKSI MASALAH

Pada algoritma-algoritma terdahulu, kita mencari solusi menggunakan pohon OR, dimana

lintasan dari awal sampai tujuan tidak terletak pada satu cabang. Apabila lintasan dari keadaan

awal sampai tujuan dapat terletak pada satu cabang, maka kita akan dapat menemukan tujuan

lebih cepat.

2.3.1 Graph AND-OR

Algoritma Graph AND-OR ini pada dasarnya sama dengan Best-First Search, dengan

mempertimbangkan adanya arc AND. Pada Gambar 2.32 terlihat bahwa untuk mendapatkan TV

orang bisa dengan cara singkat yaitu mencuri atau dengan membeli TV asal orang tersebut punya

uang.

Untuk mendeskripsikan algoritma Graph AND-OR kita menggunakan

nilai F_UTILITY, yaitu biaya solusi.

Algoritma:

1. Inisialisasi graph ke node awal.

2. Kerjakan langkah-Iangkah di bawah ini hingga node awal

SOLVED atau sampai biayanya lebih tinggi dari F_UTILITY:

(a) Telusuri graph, mualai dari node awal dan ikuti jalur terbaik.Akumulasikan kumpulan node

yang ada pada lintasantersebut dan belum pernah diekspansi atau diberi label SOLVED.

(b) Ambil satu node dan ekspansi node tersebut. Jika tidak ada successor, maka set F_UTILITY

sebagai nilai dari node tersebut. Bila tidak demikian, tambahkan successor-successor dari node

tersebut ke graph dan hitung nilai setiap f (hanya gunakan h' dan abaikan g). Jika f = 0, tandai

node tersebut dengan SOLVED.

(c) Ubah f harapan dari node baru yang diekspansi. Kirimkan perubahan ini secara backward

sepanjang graph. Jika node berisi suatu arc suatu successor yang semua descendant-nya berlabel

SOLVED maka tandai node itu dengan SOLVED.Pada Gambar 2.33, pada langkah -1 semula

hanya ada satu node yaitu

A. Node A diekspansi hasilnya adalah node B, C, dan D. Node D memiliki

biaya yang lebih rendah (6) jika dibandingkan dengan B dan C

(d). Pada langkah-2 node D terpilih untuk diekspansi, menjadi E dan F dengan biaya estimasi

sebesar 10. Sehingga kita harus memperbaiki nilai f dari D menjadi 10" Kembali ke level

sebelumnya, node B dan C memiliki biaya yang lebih rendah daripada D (9 < 10). Pada langkah-

3, kita menelusuri arc dari node A, ke B dan C bersamasama. Jika B dieksplore terlebih dahulu,

maka akan menurunkan node G dan H. Kita perbaiki nilai f dari B menjadi 6 (nilai G=6 lebih

baik daripada H=8), sehingga biaya AND-arc B-C menjadi L2 (6+4+2). Dengan demikian nilai

node D kembali menjadi lebih baik (10 < 12). Sehingga ekspansi dilakukan kembali terhadap D.

Demikian seterusnya.

2.3.2 NgoritmaAO*

Algoritma AO* menggunakan struktur Graph. Tiap-tiap node pada graph tersebut akan memiliki

nilai h'yang merupakan biaya estimasi jalur dari node itu sendiri sampai suatu solusi.

Algoritma

1. Diketahui GRAPH yang hanya berisi node awal (sebut saja node

INIT). Hitung h(INIT).

2. Kerjakan langkah-Iangkah di bawah ini hingga INI bertanda - SOLVED atau samoai nilai

h'(INIT) menjadi lebih besar daripada FLITILITY:

(a) Ekspand INIT dan ambil salah satu node yang belum pernah diekspand (sebut NODE).

(b) Bangkitkan successor-successor NODE. Jika tida memiliki successor maka set FUTIILITY

dengan nilai h'(NODE). Jika ada successor, maka untuk setiap successor (sebut sebagai SUCC)

yang bukan merupakan ancestor dari NODE, kerjakan:

i. Tambahkan SUCC ke graph.

ii. Jika SUCC adalah terminal node, tandai dengan SOLVED dan set nilai h'-nya sama dengan 0.

iii. Jika SUCC bukan terminal node, hitung nilai h'.

(c) Kirimkan informasi baru tersebut ke graph, dengan cara: tetapkan S adalah node yang

ditandai dengan SOLVED atau node yang nilai h'-nya baru saja diperbaiki, dan sampaikan nilai

ini ke parent-nya. Inisialisasi S = NODE. Kerjakan IangkahJangkah berikut ini hingga S kosong:

i. Jika mungkin, seleksi dari S suatu node yang tidak memiliki descendant dalam GRAPH yang

terjadi pada S. Jika tidak ada, seleksi sebarang node dari S (sebut: CURRENT) dan hapus dari S.

ii. Hitung biaya tiap-tiap arc yang muncul dari CURRENT. Biaya tiap-tiap arc ini sama dengan

jumlah h'untuk tiap-tiap node pada akhir arc ditambah dengan biaya arc itu sendiri. Set

h'(CURRENT) dengan biaya minimum yang baru saja dihitung dari stiap arc yang muncul tadi.

iii. Tandai jalur terbaik yang keluar dari CURRENT dengan menandai arc yang memiliki biaya

minimum.

iv. Tandai CURRENT dengan SOLVED jika semua node yang dihubungkan dengannya hingga

arc yang baru saja ditandai tadi telah ditandai dengan SOLVED.

v. Jika CURRENT telah ditandai dengan SOLVED atau jika biaya CURRENT telah berubah,

maka status baru ini harus disampaikan ke GRAPH. Kemudian tambahkan semua ancestor dari

CURRENT ke S.

Sebagai contoh, pada Gambar 2.34 Jelas bahwa jalur melalui C selalu lebih baik daripada

melalui B. Tetapi jika biaya node E muncul, dan pengaruh perubahan yang diberikan ke node B

tidak sebesar pengaruhnya terhadap node C, maka jalur melalui B bisa jadi lebih baik. Sebagai

contoh, hasil expand node E, misalkan 10, maka biaya node C menjadi 11 (10+1), dengan

demikian biaya node A apabila memilih jalur lewat C adalah 12 (11+1). Tentu saja akan lebih

baik memilih jalur melalui node B (11). Tapi tidak demikian halnya apabila kemudian node D

diekspan. Bisa jadi jalur dengan melalui node B akan lebih buruk lagi ketimbang jalur dengan

melalui node C.