BAB 2 TINJAUAN PUSTAKA

BAB 2 TINJAUAN PUSTAKA

2.1. Pengertian Graf Suatu graf G adalah suatu pasangan himpunan (V(G),E(G)), dimana V(G) = { v1, v2,…..vn } adalah himpunan tak kosong berhingga yang terdiri dari titik-titik disebut verteks dan suatu himpunan E(G) = { e1, e2,…..en } dengan garis-garis yang menghubungkan verteks-verteks disebut sisi (Chartrand dan Oellerman, 1993). Penulisan yang tepat untuk menyatakan sisi adalah e=(v1v2) atau e=(v2v1). Jika e=(v1v2) adalah suatu sisi dari graf G, maka dikatakan v1 dan v2 bersisian (adjacent). G :

v1

v2

e1

v6 e7 e5 v5

e4

e2 e6

v4

v3 e3

Gambar 2.1. Graf G

Pada gambar 2.1, G adalah graf dengan : V(G) = { v1, v2,v3,v4,v5,v6, } dan E(G) = { e1,e2,e3,e4,e5,e6,e7,}, dimana e1 = (v1v2), e2 = (v1v3), e3 = (v3v4), e4 = (v4v5), e5 = (v4v6), e6 = (v1v4), dan e7 = (v3v7). Suatu gelang ( loop) pada suatu graf G adalah suatu sisi yang verteks awalnya sama dengan verteks akhir yaitu e=(v1v1). Dua verteks yang dihubungkan lebih dari satu sisi maka disebut sisi paralel. Suatu graf G disebut graf sederhana jika tidak memuat sisi paralel dan gelang.

Universita Sumatera Utara

G:

v1

e1

v3 e6

e4

e2

e5 v2

e3

Gambar 2.2 Graf Tidak Sederhana Graf G pada gambar 2.2, sisi e4 dan e5 merupakan sisi paralel dan sisi e3 merupakan gelang. Banyaknya verteks dari suatu graf G disebut ordo (orde) dengan notasi p dan banyaknya sisi dari suatu graf G disebut ukuran (size) dengan notasi q. Suatu graf G dengan ordo p dan ukuran q dinotasikan (p,q) graf. Suatu graf G, jika v V(G), derajat dari v dinotasikan dengan d(v) yaitu banyaknya sisi yang bertemu di v (Narsingh, 1986). Derajat terkecil dari suatu verteks-verteks di G disebut derajat minimal dengan notasi (G) dan derajat terbesar dari suatu verteks-verteks di G disebut derajat maksimal dengan notasi Δ G . Suatu verteks yang berderajat 0 disebut verteks isolasi dan suatu verteks yang derajat 1 disebut verteks ujung (pendant) serta suatu verteks yang memuat gelang dianggap verteks yang berderajat 2 (Fletcher, 1991). G: u

t

w

y

v

z

x

Gambar 2.3. Graf dengan derajat minimal dan maksimal


Graf G pada gambar 2.3, d(u) = 4, d(v) = 4, d(w) = 3, d(x) = 2, d(y) = 2, d(z) = 1 dan d(t) = 0 maka Δ(G) = 4 dan (G) = 0.

2.1.1. Keterhubungan graf Suatu jalan (walk) dalam suatu graf G adalah barisan berganti-ganti W : v0, e1, v1, e2, v2,

…,

vn-1, en, vn (n ≥0) dari verteks-verteks dan sisi-sisi yang

diawali dan diakhiri dengan verteks-verteks, sehingga ei = vi-1 vi untuk I = 1, 2, …, n. Karena jalan W diawali dengan v0 dan diakhiri dengan vn, dinyatakan sebagai suatu jalan v0 – vn (a v0 – vn walk) (Harary, 1994). Suatu sikel (cycle) adalaj suatu jalan v0, e1, e2, …, vn-1, en, vn dimana n≥3, v0=vn dan n verteks v0,v1…, vn tanpa pengulangan, dinotasikan Cn. suatu sikel disebut genap jika panjangnya genap. Suatu sikel disebut ganjil jika panjangnya ganjil. Graf pada gambar 2.4, memuat C3, C4 dan C5.

c3

c4

c5

Gambar 2.4. Sikel

Suatu graf G sendiri adalah terhubung (connected) jika u terhubungkan ke v untuk setiap pasangan u,v dari verteks-verteks di G.Suatu graf G yang tidak terhubung dikatakan terputus (disconnected).

2.1.2. Subgraf dan graf bipartit Graf G1 disebut subgraf dari G jika V1 adalah himpunan bagian dari V(G) dan E1 adalah himpunan bagian dari E(G) dari G1 sendiri merupakan suatu graf. Graf pada gambar 2.5, G1 dan G2 adalah subgraf di G (Lipschutz, 2002).


G:

G1 : v

w

v

G2 :

w

v

u

u x

y

x

y

x

y

Gambar 2.5. Dua subgragf (G1 dan G2) dari suatu graf G Jika v suatu verteks di G, maka G-v adalah suatu subgraf G yang dihasilkan dengan menghilangkan v dan semua sisi yang bersisian di v. Gambar 2.6 merupakan suatu graf G dengan graf G-v. G-v :

G: x

x

u w

y z

u

y

w

z

v

Gambar 2.6. Graf G-v

Jika e suatu sisi di G, maka G-e adalah suatu subgraf G yang dihasilkan dengan menghilangkan suatu sisi e di G (Liu, 1995). Gambar 2.7 merupakan suatu graf G dengan G-e. G:

G-e e

Gambar 2.7. Graf G-e

Suatu bagian G disebut graf bipartit jika V(G) dapat dipartisi menjadi dua himpunan bagian V1 dan V2 sedemikian sehingga V(G) = V1  V2 yaitu setiap sisi di G terhubungkan dengan suatu verteks di V1 dan V2.


Graf G gambar 2.8(a) adalah graf bipartit karena V(G) dapat dipartisi menjadi dua himpunan bagian V1 = {v1,v6} dan V2 = {v2, v3, v4, v5} dimana setiap sisi di G terhubungkan dengan verteks di V1 dan V2. Setelah digambar ulang, jelas G adalah graf bipartit, seperti pda gambar 2.8(b). G: v1

v2

v1

v6

v3 v4

v5

v6

v4

v2

(a)

v3

v5

(b)

Gambar 2.8. Graf bipartit

Suatu graf tidak trivial G adalah bipartit jika dan hanya jika G tidak memuat sikel ganjil. Suatu graf G disebut graf lengkap jika setiap pasang verteksnya bersisian. Graf lengkap dengan ordo p dinotasikan dengan Kp. Graf pada gambar 2.9 adalah Kp untuk setiap p = 1, 2, 3, 4, 5.

K1

K2

K3

K4

K5

Gambar 2.9. Graf lengkap

2.2. Pewarnaan Graf

Suatu pewarnaan dari graf G adalah proses pemberian warna-warna pada verteks verteks di G, satu warna untuk setiap verteks (Gross & Yellen, 1999). Seharusnya, setiap perwarnaan G, menggunakan x warna, partisi himpunan V(G) verteks ke dalam himpunan x, disebut sebagai kelas warna, sehingga setiap verteks dari kelas


warna tertentu akan mendapatkan warna yang sama (West, 2001). Jika x warna yang digunakan untuk mewarnai (coloring), pewarnaan ini disebut sebagai xcoloring G. Pada masalah pewarnaan graf klasik adalah bahwa kelas warna harus menjadi himpunan independen dan jenis pewarnaan ini disebut sebagai pewarnaan yang tepat, yaitu, pewarnaan yang tepat dari G adalah pemberian warna pada verteks - verteks sedemikian sehingga tidak ada dua verteks yang bersisian (adjacent) di G mempunyai warna yang sama (Wallis, 2000). Jika ada kemungkinan untuk menemukan pewarnaan yang tepat dari graf G, dengan menggunakan x warna, maka G dikatakan x-colorable. Suatu graf adalah xcolorable jika dan hanya jika graf nya adalah x-partite. Khususnya, graf 2colorable adalah graf yang sama dengan graf bipartit (Clark & Holton, 1991). Bilangan kromatik, 𝜒 𝐺 , dari graf G adalah bilangan bulat terkecil x dimana G adalah x-colorable (West, 2001). Ini sama dengan, 𝜒 𝐺 adalah bilangan bulat terkecil x dimana G adalah graf x-partit. Suatu graf G dengan bilangan kromatik x disebut sebagai x-kromatik dan G dikatakan akan 𝜒 𝐺 -colorable, seperi pewarnaan yang optimal disebut 𝜒 𝐺 -coloring G (Chatrand & Oellermann, 1993). Untuk pewarnaan derajat maksimum dengan syarat bahwa untuk setiap kelas warna 𝒞, ∆ 𝒞

≤ 𝑑, dimana 𝑑 ∈ ℕ0 . Suatu x-coloring dari graf G

memenuhi persyaratan disebut sebagai ∆ 𝑑, 𝑥 -coloring di G, yaitu ∆ 𝑑, 𝑥 coloring graf G adalah d-admissible pewarnaan di G yang berkaitan dengan parameter ∆. Suatu graf ∆ 𝑑, 𝑥 -colorable jika ∆ 𝑑, 𝑥 -coloring dari graf yang ada. Bilangan bulat positif terkecil x yang ada ∆ 𝑑, 𝑥 -coloring di G (Untuk beberapa nilai tetap 𝑑 ∈ ℕ0 ) disebut ∆ 𝑑 -chromatic number G, dinotasikan dengan 𝜒𝑑Δ 𝐺 , dan seperti pewarnaan yang optimal disebut 𝜒𝑑Δ -coloring G. Akhirnya, suatu graf G dengan ∆ 𝑑 -chromatic number x disebut sebagai ∆ 𝑑, 𝑥 chromatic,dan graf dikatakan 𝜒𝑑Δ -colorable. Diketahui bahwa perumusan awal oleh Harary( 1985), sifat graf dari pewarnaan derajat maksimum adalah bahwa kelas warna harus 𝐾1,𝑛 -free, dimana 𝑛 = 𝑑 + 1 untuk pilihan tertentu pada perumusan diatas.


2.3. Metode Heuristik Metode Heuristik adalah teknik yang dirancang untuk memecahkan masalah yang mengabaikan apakah solusi dapat dibuktikan benar, tapi yang biasanya menghasilkan solusi yang baik atau memecahkan masalah yang lebih sederhana yang mengandung atau memotong dengan pemecahan masalah yang lebih kompleks. Metode Heuristik ini bertujuan untuk mendapatkan performa komputasi atau penyederhanaan konseptual, berpotensi pada biaya keakuratan atau presisi. Metode heuristik ada dua jenis yakni metode heuristik sederhana dan metaheuristik. Metaheuristik pada sebenarnya adalah metode pendekatan yang didasarkan pada metode heuristik. Sehingga tidak heran bahwa metode heuristik sering kali diintegrasikan di dalam metode metaheuristik. Perbedaan utama dari metode heuristik dan metaheuristik adalah : metode heuristik bersifat problem dependent sedangkan metode metaheuristik bersifat problem independent. Problem dependent artinya bergantung pada permasalahan, jadi metode heuristik itu hanya bisa dipakai untuk jenis permasalahan terntentu. Misalnya, metode nearest neighborhood (NN) termasuk metode heuristik. Metode hanya bisa dipakai pada permasalahan yang mengenal konsep neighborhood (tetangga), misalnya pada pewarnaan graf, Traveling Salesman Problem maupaun Vehicle Routing Problems. Sedangkan problem independent berarti tidak bergantung pada jenis permasalahan. Jadi penerapan metode metaheuristik tidak bergantung pada jenis permasalahan, alias bisa dipakai untuk berbagai jenis permasalahan. Contoh dari metode metaheuristik adalah algoritma genetik (GA), particle swam optimization (PSO), Ant Colony Optimization (ACO).

2.3.1. Tabu Search Tabu search berasal dari Tongan, suatu bahasa Polinesia yang digunakan oleh suku Aborigin pulau Tonga untuk mengindikasikan suatu hal yang tidak boleh "disentuh" karena sakralnya. Menurut kasus Webster, tabu berarti larangan yang


dipaksakan oleh kebudayaan social sebagai suatu tindakan pencegahan atau sesuatu yang dilarang karena berbahaya. Bahaya yang harus dihindari dalam tabu search adalah penjadwalan yang tidak layak, dan terjebak tanpa ada jalan keluar. Dalam konteks lebih luas, larangan perlindungan dapat diganti jika terjadi tuntutan yang mendadak(Glover, 1995). Tabu search adalah sebuah metode optimasi yang berbasis pada local search. Proses pencarian bergerak dari satu solusi ke solusi berikutnya, dengan cara memilih solusi terbaik neighbourhood sekarang (current) yang tidak tergolong solusi terlarang (tabu). Ide dasar dari algoritma tabu search adalah mencegah proses pencarian dari local search agar tidak melakukan pencarian ulang pada ruang solusi yang sudah pernah ditelusuri, dengan memanfaatkan suatu struktur memori yang mencatat sebagian jejak proses pencarian yang telah dilakukan. Struktur memori fundamental dalam tabu search dinamakan tabu list. Tabu list menyimpan atribut dari sebagian move (transisi solusi) yang telah diterapkan pada iterasi-iterasi sebelumnya. Tabu search menggunakan tabu list untuk menolak solusi-solusi yang memenuhi atribut tertentu guna mencegah proses pencarian mengalami cycling pada daerah solusi yang sama, dan menuntun proses pencarian menelusuri daerah solusi yang belum dikunjungi. Tanpa mengunakan strategi ini, local search yang sudah menemukan solusi optimum lokal dapat terjebak pada daerah solusi optimum local tersebut pada iterasi-iterasi berikutnya. List ini mengikuti aturan LIFO dan biasanya sangat pendek (panjangnya biasanya sebesar O( N ), dimana N adalah jumlah total dari operasi). Setiap saat ada langkah itu akan ditempatkan dalam tabu list. Perekaman solusi secara lengkap dalam sebuah forbidden list dan pengecekan apakah sebuah kandidat solusi tercatat dalam list tersebut merupakan cara yang mahal, baik dari sisi kebutuhan memori maupun kebutuhan waktu komputasi. Jadi, tabu list hanya menyimpan langkah transisi (move) yang merupakan lawan satu kebalikan dari langkah yang telah digunakan dalam iterasi sebelumnya untuk bergerak dari satu solusi ke solusi berikutnya. Dengan kata lain tabu list berisi langkah-langkah yang membalikan solusi yang baru ke solusi


yang lama. Pada tiap iterasi, dipilih solusi baru yang merupakan solusi terbaik dalam neighbourhood dan tidak tergolong sebagai tabu. Kualitas solusi baru ini tidak harus lebih baik dari kualitas solusi sekarang. Apabila solusi baru ini memiliki nilai fungsi objektif lebih baik dibandingkan solusi terbaik yang telah dicapai sebelumnya, maka solusi baru ini dicatat sebagai solusi terbaik yang baru. Sebagai tambahan dari tabu list, dikenal adanya kriteria aspirasi, yaitu suatu Penanganan khusus terhadap move yang dinilai dapat menghasilkan solusi yang dinilai dapat menghasilkan solusi yang baik namun move tersebut berstatus tabu. Dalam hal ini, jika move tersebut memenuhi criteria aspirasi yang telah ditetapkan sebelumnya, maka move tersebut dapat digunakan utnuk membentuk solusi berikutnya (status tabunya dibatalkan).

2.3.2. Algoritma Dsatur (Derajat Warna Heuristik) Menurut Brelaz ( 1979) bahwa derajat warna suatu verteks v pada graf G, dinotasikan dengan coldegG(v), yaitu banyaknya verteks-verteks yang berbeda warna yang bersisian, tanpa memperhatikan sudah berapa banyak suatu verteks yang bersisian identik dengan verteks-verteks yang diwarnai. Algoritma derajat warna heuristik, merupakan algoritma greedy, karena hanya jumlah warna yang berbeda pada Neighbourhood N(v) dari verteks v tertentu yang dijelajah, sedangkan masing-masing kelas warna diinduksi derajat dari verteks-verteks yang diwarnai pada N(v) tidak dianggap. Selanjutnya, pada setiap iterasi verteks selanjutnya yang akan diwarnai, dipilih dan diwarnai sesuai yang tampak sebagai verteks yang terbaik dipilih dan diwarnai dengan warna terbaik titik eksekusi algoritma tanpa melihat ke depan untuk memperhatikan apakah bisa atau tidak menjadi pilihan yang baik lebih lanjut pada saat implementasi. Berikut pseudocode algoritma derajat warna heuristik, kita sebut sebagai algoritma 1.


Algoritma 1 dsatur

(Derajat warna heuristik)

input : Suatu graf G dengan order dan suatu nilai d yang mana bilangan kromatik harus ditentukan. output : batas atas x pada ∆ 𝑑, 𝑥 -coloring G 1: L ← 𝑣𝑖 𝑑𝑒𝑔𝐺 𝑣𝑖 = ∆(𝐺) 2: Pilih v ϵ L dan misalkan 𝒞𝑖 ← 𝒞1 ∪ 𝑣 3: 𝑥 ← 1 4: untuk semua i= 2,..., n do 5:

Tentukan 𝑐𝑜𝑙𝑑𝑒𝑔𝐺 𝑣𝑗 ∀𝑗 = 1, … , 𝑛, 𝑣𝑗 ∉ 𝐶𝑘 , 𝑘 = 1, … , 𝑥

6

𝑇 ← 𝑣𝑖 𝑣𝑖 ∉ 𝐶𝑘 , 𝑘 = 1, … , 𝑥 dan 𝑐𝑜𝑙𝑑𝑒𝑔𝐺 𝑣𝑖 ≥ 𝑐𝑜𝑙𝑑𝑒𝑔𝐺 𝑣𝑗 ∀𝑣𝑗 ∉ 𝐶𝑘 , 𝑘 = 1, … , 𝑥

7:

if 𝑇 > 1 then

8: 9: 10: 11:

Tentukan G' sedmikian sehingga 𝑉 𝐺′ = 𝑉 𝐺 ∖ 𝒞1 ∪ 𝒞2 ∪ … ∪ 𝒞𝑥 v ← suatu verteks di T sehingga else

𝑑𝑒𝑔𝐺 ′ 𝑣 ≥ 𝑑𝑒𝑔𝐺 ′ 𝑣𝑗 ∀𝑣𝑗 ϵ T

𝑇 =1

v ← hanya verteks di T

12:

end if

13:

𝐶𝑗 ← 𝐶𝑗 ∪ 𝑣 dimana 𝑗 jumlah warna terkecil sehingga ∆ 𝐶𝑗 ∪ 𝑣

14: 15: 16:

≤𝑑

if j > x maka x = j end if

17: end for 18: return x, 𝑠 = 𝐶1 , … , 𝐶𝑥

Algoritma 1 dimulai dari langkah 1, dengan mendaftarkan semua vaerteksverteks dengan derajat maksimum pada suatu list L, diikuti langkah 2 dengan mewarnai salah satu verteks di L menggunakan warna 1. Parameter x (pada langkah 13 dan 15) terus melacak jumlah warna yang akan digunakan. Pada saat loop spanning langkah 4 hingga 17, setiap n-1 verteks lainnya, akan diwarnai pada gilirannya. Hal ini dapat dicapai dengan terlebih dahulu menentukan derajat warna pada semua verteks-verteks yang belum diwarnai pada langkah 5. Semua verteks-verteks yang belum diwarnai dengan derajat warna maksimum didaftarkan di list T, pada langkah 6. Jika list T memuat hanya satu verteks (langkah 10 dan 11), verteks ini akan diwarnai berikutnya, jika verteks dari T dipilih, menurut pada langkah 7 - 9 algoritma. Pilih suatu verteks dari T, subgraf G' dan G diinduksi. Verteks pada list T dengan derajat terbesar di G' diantara


semua verteks-verteks di T, kemudian dipilih diberikann warna selanjutnya, menurut langkah 9. Jika mengikat masih terjadi, setiap verteks dapat dipilih. Akhirnya, pilihlah verteks v yang diperoleh dengan kemungkinan jumlah warna terkecil, yang dialokasikan pada langkah 13, dan parameter x, diperbaharui pada langkah 15 jika perlu.

2.3.3. Algoritma Pewarnaan Heuristik Tabu Search Hertz dan De Werra (1987) mengimplementasikan teknik tabu search untuk mendapatkan pewarnaan yang tepat pada suatu graf. Ide mereka akan diadaptasi dan di implementasikan pada konteks pewarnaan dalam algoritma pewarnaan heuristik tabu search (Nieuwoudt, 2007). Algoritma pewarnaan heuristik tabu search diberikan dalam pseudo-code berikut, yang kita sebut sebagai algoritma 2, yaitu :

Algoritma 2 Pewarnaan

heuristik tabu search

input : Suatu graf G dengan order n dan suatu nilai d yang mana untuk menentukanΔ(𝑑)-chromatic candidate

number,

tabu

tenure,

t,

size

dari

list, ℓ, dan jumlah maksimum dari iterasi, maxit.

output : Batas atas 𝜒𝑑Δ pada 𝜒𝑑Δ (𝐺) sama artinya Δ 𝑑, 𝜒𝑑Δ -coloringG. 1: x ← (Δ 𝐺 + 1)/(𝑑 + 1) 2: 𝜒𝑑Δ ← -1 3: STOP ← false 4: while not STOP do 5:

itcounter ← 0; EMPTY ← false

6:

Generate random initial coloring𝑠 = 𝒞1 , … , 𝒞𝑥

7:

𝑓 𝑠 ← 𝑚𝑎𝑥1≤𝑗 ≤𝑥 ∆ 𝒞𝑗

8:

𝐴(0) ← 0

9: 𝐴 𝑧 ← 𝑧 − 1 ∀ 𝑧 = 1, … , ∆(𝐺) 10: while (𝑓 𝑠 > 𝑑 and itcounter < 𝑚𝑎𝑥𝑖𝑡 and 11:

count ← 1; NOMORE ← false

12:

while

13:

Pilih suatu verteks 𝑣 ∈ 𝒞𝑖

not EMPTY) do

count < ℓ + 1 𝐚𝐧𝐝 not NOMORE do dengan 𝑑𝑒𝑔 𝒞𝑖 𝑣 = ∆ 𝒞𝑖 untuk sebarang i

dengan kelas warna terbesar di induksi derajat maksimum 14:

pilih suatu warna 𝑗 ≠ 𝑖 untuk sebarang jdengan kelas warna terbesar diinduksi derajat maksimum


15:

𝒞𝑖′ ← 𝒞𝑖 ∖ 𝑣 , 𝒞𝑗′ ← 𝒞𝑗 ∪ 𝑣 , 𝒞𝑘′ ← 𝒞𝑗 ∀ 𝑘 = 1, … , 𝑥, 𝑘 ≠ 𝑖, 𝑗

16:

𝑠 ∗ = 𝒞1′ , … , 𝒞𝑥′

17:

if

𝑣, 𝑗 ∉ 𝑇 𝐨𝐫 𝑓 𝑠 𝐢𝐟 𝑣, 𝑗 ∈ 𝑇 then

18:

𝐿 ← 𝐿 ∪ 𝑠∗

19:

count ← count + 1

20:

end if

21:

if jika semua kemungkinan pada langkah 13 dan 14 telah dipertimbangkan

22: 23:

end if

24:

end while

25:

if𝐿 = ∅then

26: 27:

then

NOMORE ← true

EMPTY ← true else

28:

𝑠 ′ ← suatu kandidat di L sedemikan sehingga 𝑓 𝑠 ′ ≤ 𝑓 𝑠𝑖 ∀ 𝑠𝑖 ∈ 𝐿

29:

if 𝑓 𝑠 ′ ≤ 𝐴𝑓 𝑠 then

30:

← 𝑓 𝑠′ − 1

𝐴𝑓 𝑠

31:

end if

32:

𝑇 ←𝑇∪

33:

if 𝑇 > 𝑡then

34:

𝑣, 𝑖 , where 𝑣 ∈ 𝒞𝑖 di s dan 𝑣 ∉ 𝒞𝑖′ di𝑠 ′

Hapus entri terlama di T

35:

end if

36:

𝑠 ← 𝑠′ ; 𝑓 𝑠 ← 𝑓 𝑠′

37:

itcount ← itcount + 1

38:

end if

39:

end while

40:

if𝑓 𝑠 ≤ 𝑑then

41:

𝜒𝑑Δ ← 𝑥

42:

𝑠𝑑 ← 𝑠

43:

x ← x - 1

44: 45: 46:

else 𝑓 𝑠 ≤ 𝑑 STOP ← true end if

47: end while 48: return 𝜒𝑑Δ , 𝑠𝑑 = 𝒞1 , … , 𝒞𝜒 𝑑Δ

Gagasan utama dari algoritma diatas adalah upaya untuk menentukan suatu Δ 𝑑, 𝑥 −coloring dari suatu graf G dengan menggunakan bilangan tetap x


sebagai warna-warna. Dimulai dari suatu initial random x-coloring G yang paling mungkin, dari suatuΔ 𝑑, 𝑥 −coloring

yang invalid. Strategi ini kemudian

berulang menurunkan x dan mencoba mencari Δ 𝑑, 𝑥 -coloring yang valid pada suatu graf G menggunakan bilangan terkecil sebagai warna, sehingga diperoleh. Dengan demikian batas atas x pada Δ 𝑑 −chromatic number direduksi sampai algoritma menemukan Δ 𝑑, 𝑥 -coloring tidak valid untuk batas atas terkecil. Jika himpunan verteks dipartisi menjadi suatu bilangan tetap c dari himpunan bagian (kelas warna), menghasilkan suatu pewarnaan dengan kelas warna 𝑠 = (𝒞1 , … , 𝒞𝑥 ), tujuannya adalah untuk meminimalkan kelas warna terbesar yang diinduksi derajat maksimum, yaitu untuk minimize 𝑓 𝑠 = max1≤𝑗 ≤𝑥 Δ 𝒞𝑗 . Jelas, bahwa 𝑓 𝑠 ≤ 𝑑, untuk nilai d yang telah ditentukan, dimana Δ 𝑑 −chromatic number dari graf G, harus ditentukan, Δ 𝑑, 𝑥 -coloring yang valid telah diperoleh. Oleh karena itu, ini adalah yang pertama dari tiga stopping kriteria yang diterapkan pada algoritma. Stopping kriteria kedua adalah ketika algoritma melakukan sebelum ditentukan jumlah maksimum dari iterasi, maxit, dimana tidak ada solusi (coloring), s, dimana 𝑓 𝑠 ≤ 𝑑 diperoleh, sehingga Δ 𝑑, 𝑥 −coloring G tidak valid diperoleh. Stopping kriteria yang terakhir adalah ketika tidak ada candidate solution yang dibangkitkan (generated). Pada penerapan tabu search , oleh Hertz dan De Werra (1987) untuk pewarnaan graf yang tepat, setiap candidate solution dibangkitkan dengan cara memilih current solution, s, sebarang verteks v, dengan derajat tak nol dalam hal ini kelas warna khusus diinduksi subgraf, dan kemudian recoloring v dengan warna yang berbeda, dipilih secara acak dari warna - warna lain yang digunakan di s. Agar menjadi benar, sifat deterministik asli dari teknik tabu seach. Setiap candidate solution, s*, pada algoritma 2 di bangkitkan dengan memilih dari current solution, s, suatu kelas warna i, dimana kelas warna diinduksi derajat maksimum untuk s. Verteks v kemudian diwarnakan kemudian diwarnakan dengan warna yang berbeda, j, dari warna - warna lain yang digunakan di s, dimana j adalah warna dengan kelas warna terkecil di induksi derajat maksimum untuk s. Candidate solution dibangkitkan dengan langkah berurutan melalui semua kelas warna dengan kelas warna terbesar diinduksi derajat maksimum


untuk s, semua verteks - verteks v dalam kelas warna dengan kelas warna diinduksi derajat sama dengan kelas warna terbesar diinduksi derajat maksimum dan semua kelas warna dengan kelas warna terkecil diinduksi derajat maksimum digunakan sebagai warna baru untuk v, sampai total dari candidate solution ℓ dibangkitkan dan disimpan di candidate list. Jika semua kemungkinan candidate solution dapat dibangkitkan, seperti dijelaskan diatas, dan jumlah candidate solution adalah lebih kecil dari pada ℓ, maka proses pembangkitan candidate solution diatas diulang untuk suatu verteks u dengan kelas warna diinduksi derajat sama dengan kelas warna terbesar kedua diinduksi derajat maksimum, dimana u juga dalam kelas warna dengan kelas warna diinduksi derajat maksimum sama dengan kelas warna terbesar diinduksi derajat maksimum untuk s. Akhirnya, jika diinginkan, prosedur diatas dapat diulang sekali lagi dimana warna j dengan memilih verteks v yang akan diwarnai, jika sekarang suatu warna dengan kelas warna terkecil kedua diinduksi derajat maksimum untuk s. Jika kekardinalan dari candidate list, adalah masih terkecil daripada ℓ, maka pembangkit dari candidate solution berakhir. Dari candidate list (jika ini tidak kosong), candidate solution, 𝑠 ′ , dengan nilai fungsi objektif terkecil yang dipilih, yang dapat atau tidak dapat sesuai untuk nilai fungsi objektif terkecil, maka didapat current solution s, sebagai solusi selanjutnya untuk bergerak (move). Ini sangat kontras dengan tabu search proper coloring algorithm oleh Hertz dan De Werra (1987) dimana, candidate solution, 𝑠 ′ ,dipilih secara acak diantara candidate solution dengan nilai maksimum untuk 𝑓(𝑠 ′ ), jika suatu hubungan terjadi selama eksekusi pada Δ 𝑑, 𝑥 −coloring heuristic, satu dengan jumlah terkecil dari kelas warna dengan suatu kelas warna diinduksi derajat maksimum lebih besar dari d maka dipilih. Bilamana suatu verteks v di kelas warna 𝒞𝑖 pada current solution, s, bergerak ke kelas warna 𝒞𝑗 pada solusi selanjutnya, 𝑠 ′ ,diantara (v,i) menjadi tabu dan dimasukkan ke dalam tabu list, T. Kemudian, verteks v tidak dapat dikembalikan ke kelas warna 𝒞𝑖 untuk menentukan jumlah iterasi dari algoritma diatas. Jika size dari tabu list T sesudah disisipkan diantara (v,i) kedalam T, adalah lebih besar dari pada tabu tenure, t, entri yang terlama di T dihilangkan. Suatu kriteria aspirasi dari suatu tabu bertransisi sebagai fungsi 𝐴(𝑧) yang


didefinisikan sebagai berikut : Jika suatu tabu diantara (v,i) dimasukkan kedalam solusi yang berdekatan, 𝑠, current solution, s, dan nilai fungsi objektif, 𝑓(𝑠), solusi yang berdekatan 𝑠 lebih besar atau sama dengan nilai fungsi aspirasi, 𝐴 𝑓 𝑠 , nilai fungsi objektif dari current solution, s, maka status tabu dari (v,i) ditolak, dan solusi yang berdekatan 𝑠 dimasukkan ke kandidat list. Pada awalnya kriteria aspirasi, 𝐴(𝑧), untuk setiap nilai z, ditetapkan sebagai 𝑧 − 1.Kemudian, jika suatu solusi 𝑠 ′ memenuhi 𝑓(𝑠 ′ ) ≤ 𝐴 𝑓 𝑠

yang dipilih dari candidate

list, 𝐴 𝑓 𝑠 ditetapkan sebagai 𝑓 𝑠 ′ -1 Berikut rincian bagaimana aspek diatas diimplementasikan pada algoritma, Langkah 1 algoritma, suatu batas atas x pada 𝜒𝑑Δ 𝐺 graf G, diberikan sebagai derajat d. Jika Δ 𝑑, 𝑥 −coloring G layak untuk batas atas ini maka tercapai, sehingga Δ 𝑑, 𝑥 −coloring layak disimpan ( langkah 41 dan 42 pada algoritma) dan batas atas x pada 𝜒𝑑Δ 𝐺 dikurangi dengan 1, pada langkah 43. Iterasi langkah 4-47, dieksekusi menggunakan nilai terbaru dari x. Iterasi ini berlanjut sampai Δ 𝑑, 𝑥 −coloring tidak layak, diperoleh, dimana kasus variabel boolean STOP pada langkah 45, maka ditetapkan benar. Pada point ini ditetapkan batas atas χΔ𝑑 (langkah 41) pada 𝜒𝑑Δ 𝐺 didapat dari algoritma diatas yaitu 𝑥 + 1, dimana x adalah batas atas pertama yang mana Δ 𝑑, 𝑥 −coloring yang valid, diperoleh. Kemungkinan

algoritma

diatas

tidak

menghasilkan

suatu

Δ 𝑑, 𝑥 −coloring G yang layak, untuk batas atas pertama pada 𝜒𝑑Δ 𝐺 menggunakan x = (Δ 𝐺 + 1)/(𝑑 + 1)

warna. Batas atas χΔ𝑑 pada 𝜒𝑑Δ 𝐺

ditetapkan tak layak dengan nilai−1 pada langkah 2. Jika pada akhir eksekusi algoritma, nilai χΔ𝑑 diberikan −1 , ini jelas bahwa algoritma tidak dapat menetukan solusi yang layak untuk masalah Δ 𝑑, 𝑥 −coloring. Untuk suatu nilai x dengan batas atas di χΔ𝑑 , pewarnaan awal pada verteks - verteks didapat pada langkah 6 algoritma, dimana nilai fungsi objectif untuk pewarnaan ditentukan pada langkah 7. Pencarian untuk suatu Δ 𝑑, 𝑥 −coloring yang layak di G di jalankan pada langkah 10 - 39. Suatu candidate list dari size ℓ dibangkitkan pada langkah (12 - 24). Pada langkah 28, solusi selanjutnya dipilih


dari candidate list asal saja bahwa candidate list tidak kosong (langkah 27), dan kriteria aspirasi di perbaharui pada langkah 30, jika perlu. Akhirnya, tabu list di perbaharui pada langkah (32 - 35). Jika candidate list kosong (langkah 25) maka variabel boolean EMPTY pada langkah 26 ditetapkan benar dan pencarian untuk suatu Δ 𝑑, 𝑥 −coloring G yang layak, berakhir.

2.4. Riset Terkait A Hertz et, al. (1987) dalam jurnalnya menyatakan dimana teknik tabu search digunakan untuk menuju nilai minimum fungsi. Suatu tabu list yang gerakannya diperbaharui selama iterasi untuk menghindari perputaran dan terjebak dalam minimum lokal. Teknik tersebut disesuaikan dengan masalah pewarnaan graf. Chams

et,

al.

(1987)

dalam

jurnalnya

bereksperimen

dengan

mengkombinasikan dua algoritma yaitu algoritma dsatur dan algoritma RLF (Recursive Largest First) yang digunakan dalam dua tahap pada graf yang sama. Raphael Dorne et, al. (1998) dalam jurnalnya menyatakan dimana tabu search disajikan untuk tiga masalah pewarnaan, yaitu pewarnaan graf, tpewarnaan

dan

himpunan

t-pewarnaan.

Algoritma

tabu

search

disini

mengintegrasikan fitur penting seperti solusi regenerasi dan tabu tenure dinamis. Galinier et, al. (2008) dalam jurnalnya mengadaptasi metode AMA (Adapted Memory Algorithm) untuk masalah pewarnaan graf yang dinamakan metode AMACOL. Kemudian hasil pewarnaan graf yang didapat dengan metode AMACOL dibandingkan dengan algoritma GLS (Genetic Local Search). Jan Olav Hajduk (2010) dalam tesisnya membahas dan menganalisa tabu tenure pada algoritma tabu search untuk masalah pewarnaan graf.

2.5. Kontribusi Riset Penulis berharap penelitian ini dapat digunakan sebagai wawasan pengetahuan dan pembanding tentang pewarnaan graf dan metode heuristik

serta dapat

diaplikasikan dalam kehidupan nyata.


BAB 2 TINJAUAN PUSTAKA

Recommend Documents