Sukses Beralgoritma

SUKSES BERALGORITMA

SRY WAHYUNI

Sukses beralgoritma 2012

i

KATA PENGANTAR

Puji dan syukur penulis panjatkan ke kehadirat Tuhan Yang Maha Kuasa, karena atas

berkat dan rahmat-Nyalah sehingga penulis dapat menyelesaikan penulisan buku ini

dengan judul “Sukses Beralgoritma”.

Buku ini merupakan pengalaman yang sangat berharga, meskipun dalam

penyusunannya menemui banyak hambatan dan masih terdapat banyak kekurangan di

dalamnya. Kritik dan saran sangat diharapkan untuk kesempurnaan buku ini.

Dengan segala kerendahan dan ketulusan hati penulis ucapkan terima kasih yang

begitu besar kepada Tuhan Yesus Kristus yang telah membimbing dan menyertai

penulis untuk tetap sabar dan setia dalam penulisan buku ini bahkan selama

perkuliahan. Tak lupa juga trima kasih yang sebesar-besarnya kepada semua pihak

khususnya dosen yang senantiasa mendukung penulis selama proses perkuliahan.

Dalam kesempatan ini pula penulis menyampaikan rasa syukur dan terima kasih

atas segala bantuan, kerja sama dan dukungan selama ini sehingga penulis dapat

mencapai kesuksesan menyelesaikan penyusunan buku ini.

Penulis menyadari bahwa buku ini masih jauh dari kesempurnaan sehingga saran

dan masukan yang sifatnya membangun dari semua pihak sangat saya hargai. Akhir kata

penulis menaruh harapan besar semoga buku ini dapat memberikan manfaat bagi

semua pihak.

Makassar, Oktober 2012

Penulis


ii

DAFTAR ISI

KATA PENGANTAR…………………………………………………. i

DAFTAR ISI ...................................................................................... ii

TENTANG PENULIS...................................................................... iii

BAB I PENGANTAR ALGORITMA

A. DEFINISI ALGORITMA .................................................. 2

B. DESAIN ALGORITMA .................................................... 2

C. ANALISIS ALGORITMA…………………….…………... 4

BAB II PERANCANGAN ALGORITMA

A. MASALAH PENCARIAN DATA.................................. 6

B. PENCARIAN BISEKSI (BAGI-DUA).......................... 8

C. BINARY SEARCH TREE (BST)………….................... 12

BAB III ALGORITMA MERGE SORT

A. MERGE SORT................................................................... 16

B. RECURRENCE ................................................................ 22

BAB IV STRATEGI ALGORITMA (I)

A. METODE GREEDY ........................................................ 28

B. DYNAMIC PROGRAMMING …................................... 30

BAB V STRATEGI ALGORITMA (II)

A. ALGORITMA METAHEURISTIK................................ 38

B. ALGORITMA GENETIKA……..…................................. 39

C. JARINGAN SYARAF TIRUAN………………………… 53

DAFTAR PUSTAKA………………............................................... 59


iii

TENTANG PENULIS

Sry Wahyuni lahir di Makale, 22 Januari 1993. Putri ketiga

pasangan Eliusat Loly – Orpha Saranga’ ini tengah menempuh

pendidikan di Universitas Hasanuddin, Prodi statistika, Jurusan

Matematika, Fakultas MIPA. Alumni SMAN 1 Makale ini memulai

pendidikannya di Unhas semenjak tahun 2011. Kini ia berada di

tahun kedua (semester 3). Dengan memiliki visi-misi dan konsentrasi

hidup yaitu “hidup sukses” , ia menulis buku ini dengan judul “sukses

beralgoritma”. Harapan agar setiap orang mendapatkan terobosan

pemahaman yang sangat bermakna ketika setiap orang membaca

buku ini. Ini adalah buku pertama yang ia tulis disertakan harapan

agar boleh menginspirasi setiap orang yang ingin belajar algoritma.

Sry Wahyuni terlahir dari keluarga sederhana dan bahagia.

Dengan kasih sayang orang tua yang membesarkannya, ia sekarang

tumbuh menjadi seorang mahasiswa yang diharapkan dapat

mengharumkan nama keluarga tercinta. Gadis periang ini juga

diberkahi kasih sayang dari dua pria penyayang di sisinya. Sebut saja Ellya dan Melky,

dua orang kakak yang juga turut mengambil bagian dalam perjalanan kehidupannya

menuju kedewasaan , kebahagiaan dan kesuksesan. Akhir kata, penulis mengungkapkan

kebahagian atas segala pengalaman yang ia rasakan selama penulisan buku ini.

Selamat membaca.

Yeshua Hamasiah Bless.

Cheers


1

BAB 1

PENGANTAR ALGORITMA


2

A. DEFINISI ALGORITMA

Prosedur komputasional yang terdefinisi dengan baik yang membutuhkan nilai

(atau himpunan nilai) sebagai input dan menghasilkan nilai (atau himpunan nilai)

sebagai output

Alat bantu (tools) menyelesaikan masalah komputasional yang terdefinisi dengan

baik (well-defined computational problem)

Metode penyelesaian yang logis dan ‘wajib’ benar (correctness) sesuai keinginan

masalah (desired solution)

B. DESAIN ALGORITMA

– Pseudocode: Kode untuk memudahkan pemahaman algoritma yang dapat

ditransformasi kedalam berbagai Bahasa Pemrograman.

– Kompleksitas algoritma: Analisis kebutuhan dari algoritma, khususnya waktu

komputasi dan kapasitas memory.

– Strategi algoritma: Perancangan kadang membutuhkan strategi perancangan

algoritma tertentu. Dalam kuliah ini: Greedy algorithm, divide-and-conquer,

dynamic programming dan strategi-strategi algoritma meta-heuristik untuk

masalah optimisasi.

Ketentuan pseucode:

• Indent menyatakan struktur blok.

• Statemen perulangan dikonstruksi dengan while, for dan repeat.

• Statemen penyeleksian kondisi/syarat dikonstruksi dengan if, then dan else.

• Simbol “” menyatakan komentar untuk statemen baris-baris berikutnya.

• Penugasan berganda (multiple assignment) i j e menyatakan

penugasan/pemberian nilai e kedalam i dan j; pernyataan ini ekivalen dengan i

j lalu diikuti j e.

Alogritma Insertion-Sort

Insertion-Sort(A)

<> perulangan untuk patokan

1. for to

2. key

3. <> Sisip A[j] ke dalam barisan terurut A[1..j-1]

4.

5. while ⋀

6.

7.

8.


3

Contoh kasus pengurutan data:

Barisan bilangan A (31,41,26,35). Urutkan data dari terkecil ke terbesar!

Untuk j = 2 to 4

(j=2) -> key=A[2]=41

i=2-1=1

ketika ( i=1 > 0 A[2] > key=41)

T F

A[2]=key

(j=3) -> key=A[3]=26

i=3-1=2

ketika ( i=2 > 0 A[2] > key=26)

T T

26

A[3]=A[2]

i=2-1=1

ketika ( i=1 > 0 A[1] > key=26)

T T

A[2]=A[1]

26

(j=4) -> key=A[4]=35

i=4-1=3

ketika ( i=3 > 0 A[3] > key=35)

T T

35

A[4]=A[3]

i=3-1=2

ketika ( i=2 > 0 A[2] > key=35)

T F

31 41 26 35

31 41 41 35

31 31 41 35

26 31 41 41

26 31 35 41


4

A[3]=key

i=2-1=1

ketika ( i=1 > 0 A[1] > key=35)

T F

A[3]=key

(j=5) -> key=A[5]

(proses berhenti karena tidak ada A[5])

C. ANALISIS ALOGRITMA

• Kasus Terbaik

Suatu alogritma dikatakan kasus terbaik pada saat statementnya atau

pernyataannnya terpenuhi dan t = 1. Laju komputasinya dalam fungsi linier.

∑

• Kasus Terburuk

Suatu alogritma dikatakan kasus terburuk pada saat statementnya atau

pernyataannnya tidak terpenuhi dan t = 0. Laju komputasinya dalam fungsi

kuadratik.

∑ (

)

(

)

26 31 35 41


5

BAB 2

PERANCANGAN ALGORITMA


6

A. MASALAH PENCARIAN DATA

Searching problem

Input : Barisan n bilangan asli (a1, a2, …, an) dalam larik A dan sebuah bilangan

key yang ingin dicari.

Output : Lokasi key dalam A. Jika key tidak ditemukan dalam A, tambahkan key

sebagai unsur terakhir.

Contoh:

Input barisan bilangan: A = (31, 41, 59, 26, 41, 58) dan key = 26.

Algoritma pencarian (searching algorithm), output menghasilkan posisi key adalah 4.

Pencarian Linier

Linear-Search(A, key)

cost times

1 ada False c1 1

2 for i 1 to

length[A]

c2 n + 1

3 if A[i] = key then c3 n

4 posisi i c4

n

i it1

5 ada True c5

n

i it1

6 if not(ada) then c6 1

7 posisi length[A] +

1

c7 s

8 A[posisi] data C8 S

)32(22)(1

stnnTn

i

i

ada False

Pernyataan ini ditentukan di awal, yakni merupakan penentu pada kondisi awal.

Bagian ini di proses sebanyak 1 kali. Karena hanya satu kali ditentukan pada bagian

awal.

for i 1 to length[A]

Di sini length[A]=n.

Pada bagian ini, akan diproses sebanyak n+1, karena data yang ada sebanyak n, dan 1

untuk mengecek kembali, apakah i yang selanjutnya masih memenuhi length [A],

dengan kata lain bahwa sudah tidak ada unsur setelah n.

if A[i] = key then

Waktu komputasinya sebanyak n. Karena ada n data yang akan di uji apakah nilainya

sama dengan key.


7

posisi i

Waktu komputasinya adalah

n

i it1 . dimana nilai t sangat tergantung pada n (jumlah

/ panjang data) yang terkesekusi. Apabila i=1 maka , jika i = 2 maka dan

seterusnya sampai banyaknya data.

ada True

Untuk pernyataan di atas terlihat bahwa tereksekusi sebanyak ∑ dimana nilai t

juga tergantung pada n yang tereksekusi dan bernilai benar.

if not(ada) then

Pernyataan di atas akan tereksekusi sebanyak 1 kali, karena merupakan kondisi

awal juga, ketika key tidak ditemukan pada barisan data yang tersedia.

posisi length[A] + 1

Pernyataan di atas akan tereksekusi sebanyak s kali. Dalam hal ini, s adalah sebuah

variabel bebas. Pernyataan ini akan dieksekusi apabila key yang dicari tidak

ditemukan dalam barisan bilangan. Namun jika key ada, maka pernyataan ini akan

dilangkahi.

A[posisi] data

Pernyataan di atas juga akan tereksekusi sebanyak s kali. Pernyataan ini merupakan

lanjutan dari pernyataan di atasnya. Jika pernyataan di atas tereksekusi sebanyak s

kali maka pernyataan ini juga akan turut tereksekusi.

KASUS TERBAIK DAN KASUS TERBURUK

a) Kasus Terburuk: Semua unsur dalam larik A sama dengan key. (Dalam hal ini,

ntn

i i 1 dan s = 0)

Untuk kasus terburuk terjadi ketika .

Contohnya:

Diberikan data 23,23,23,23 dengan Key=23

Setiap unsur akan mengeksekusi setiap pernyataan berulang-ulang sebanyak n.

34)32(22)(1

nstnnTn

i

i

b) Kasus Terbaik: Tidak terdapat satu pun unsur dalam larik A sama dengan key.

(Dalam hal ini, 01

n

i it dan s = 1)

Dalam hal ini, semua data akan dieksekusi sebanyak satu kali. Namun key yang dicari

tidak ditemukan dalam barisan data. Misalnya A = 23, 45, 67, 87 dan key = 90 maka

sintaks-sintaks akan di proses hingga terakhir.

52)32(22)(1

nstnnTn

i

i


8

CONTOH

A = (31, 41, 59, 26, 41, 58) , Key = 26

URAIAN PSEUCODE:

ada False

for i 1 to length[A]

karena length [A]=6, maka akan menjadi for i=1 to 6

for i 1 to 6

if A[i] = key

if 31 = key (FALSE)

then

Karena pernyataan if 31 = Key bernilai “FALSE” maka eksekusi dilanjutkan

for i 2 to 6

if A[i] = key

if 41 = key (FALSE)

then

Karena pernyataan if 41 = Key bernilai “FALSE” maka eksekusi dilanjutkan.

for i 3 to 6

if A[i] = key

if 59 = key (FALSE)

then

Karena pernyataan if 59 = Key bernilai “FALSE” maka eksekusi dilanjutkan

for i 4 to 6

if A[i] = key

if 26 = key (TRUE)

then

posisi 4

ada True

Karena pernyataan if 26 = Key bernilai “TRUE” maka eksekusi dihentikan pada posisi

A[4], Sehingga output akan menghasilkan posisi key adalah 4.

B. PENCARIAN BISEKSI (BAGI-DUA)

Metode pencarian bagidua atau pencarian biner (binary search). Metode ini

digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Prinsip metode ini

adalah membagi dua data. Kemudian data dicari secara bersamaan dari dua sisi, yakni


9

dari depan dan belakang. Hal ini dimaksudkan agar waktu komputasi lebih cepat dan

efisien.

Bisection-Search(A, key) cost

times

1 ada False c1 1

2 for i 1 to length[A]

/2

c2 ½ n + 1

3 if A[i] = key then c3 ½ n

4 posisi i c4

2

1

n

i it

5 ada True c5

2

1

n

i it

6 if A[n – i + 1] = key

then

c6 ½ n

7 posisi n – i + 1 c7

2

1

n

i ip

8 ada True c8

2

1

n

i ip

9 if not(ada) then c9 1

10 posisi length[A] + 1 c10 s

11 A[posisi] data c11 s

)32(22)( 22

1123

sptnnTnn

i ii i

ada False

Pernyataan ini ditentukan di awal, yakni merupakan penentu pada kondisi awal.

Bagian ini di proses sebanyak 1 kali. Karena hanya satu kali ditentukan pada bagian

awal.

for i 1 to length[A] /2

Pernyataan ini akan tereksekusi sebanyak 1/2 n+1. Maksudnya adalah tereksekusi

sebanyak n ½ (Jumlah/panjang data dibagi dua), dibagi dua agar dalam satu waktu

bisa dilakukan dua perintah sekaligus yaitu dari unsur paling depan dan belakang,

sedangkan + 1 untuk mengecek kembali bahwa ⁄ adalah unsur terakhir dari

deret tersebut (tidak ada unsur lain lagi). Digunakan tanda ( ) pada for i 1 to

length[A] /2 artinya dilakukan pembulatan ke atas.

if A[i] = key then

Pernyataan ini akan tereksekusi sebanyak ⁄ , maksudnya adalah tereksekusi

sebanyak ⁄ (jumlah data/panjang data dibagi dua), dibagi dua agar dalam satu

waktu dapat dikerjakan dua perintah sekaligus. Dalam hal ini pernyataan di atas

merupakan perintah eksekusi unsur pada bagian depan.


10

posisi i

Pada pernyataan di atas terlihat bahwa tereksekusi sebanyak ∑ dimana nilai t

sangat tergantung pada ⁄ (jumlah / panjang data dibagi dua) yang tereksekusi.

Dalam hal ini bukan nilai n pada awal melainkan n yang tereksekusi, misalnya dari

panjang ⁄ = 3 namun yang hanya terkeksekusi adalah ⁄ =2 maka running

timenya dapat di tulis ∑

ada True

Pernyataan ini akan tereksekusi sebanyak ∑ dimana nilai t juga tergantung

pada ⁄ yang tereksekusi dan bernilai benar, misalnya pada barisan 25,25,25,31

dan key=25 maka ada True akan tereksekusi sebanyak ∑

if A[n – i + 1] = key then

Pernyataan ini akan tereksekusi sebanyak ⁄ , maksudnya adalah tereksekusi

sebanyak ⁄ (jumlah data/panjang data dibagi dua), dibagi dua agar dalam satu

waktu dapat dikerjakan dua perintah sekaligus. Dalam hal ini pernyataan di atas

merupakan perintah eksekusi unsur pada bagian belakang.

posisi n – i + 1

Pernyataan ini akan tereksekusi sebanyak ∑ dimana nilai t sangat tergantung

pada ⁄ (jumlah / panjang data dibagi dua) yang terkesekusi.

Dalam hal ini bukan nilai ⁄ pada awal melainkan ⁄ yang tereksekusi,

misalnya dari panjang ⁄ = 3 hanya terkeksekusi ⁄ maka running

timenya dapat di tulis ∑ .

ada True

Pernyataan ini akan tereksekusi sebanyak ∑ dimana nilai t juga tergantung

pada ⁄ yang tereksekusi dan bernilai benar, misalnya pada barisan 21,21,21,31

dan key=21 maka ada True akan tereksekusi sebanyak ∑ , karena

pada saat ⁄ ⁄ =2 bernilai benar (ada True).

if not(ada) then

Pernyataan ini akan tereksekusi sebanyak 1 kali, karena merupakan kondisi awal

juga, ketika key tidak ditemukan pada barisan yang tersedia.

posisi length[A] + 1

Pernyataan ini akan tereksekusi sebanyak s, dalam hal ini tergantung pada

pernyataan di atas, jika pernyataan tersebut terpenuhi maka akan di eksekusi

sebanyak s.

A[posisi] data

Pernyataan ini akan tereksekusi sebanyak s, dalam hal ini jika pernyataan 9

terpenuhi makan pernyataan di atas juga dapat terpenuhi sehingga akan dieksekusi

sebanyak s.


11

CONTOH:

A= (31, 41, 59, 26, 41, 58) dan key = 26

URAIAN PSEUCODE:

ada False

for i 1 to length[A]/2

karena length [A]=6, maka akan menjadi for i=1 to 3

for i 1 to 3

(dari depan)

if A[1] = key then

if 31 = key then (FALSE)

(dari belakang)

if A[6] = key then


Karena pernyataan masih bernilai salah (ada False) maka eksekusi dilanjutkan.

for i 2 to 3

(depan)

if A[2] = key then


(belakang)

if A[5] = key then


Karena pernyataan masih bernilai salah (ada False) maka eksekusi dilanjutkan.

for i 3 to 3

(depan)

if A[3] = key then


(belakang)

if A[4] = key then

if 26 = key then (TRUE)

posisi 4

ada True


12

Karena pernyataan bernilai benar (ada True) maka eksekusi dihentikan pada posisi

A[4], sehingga output menghasilkan posisi Key adalah 4.

Kasus Terbaik Dan Kasus Terburuk

Kasus Terburuk: Semua unsur dalam larik A sama dengan key. (Dalam hal ini,

2121

22 , n

i in

i i

nn

pt dan s = 0)

Untuk kasus terburuk terjadi ketika

Kasus ini terjadi bila nilai dari larik A itu sama semua dengan key yang ditentukan.

Misalnya A = 36, 36, 36, 36 dan key = 36.

Maka setiap unsur

akan mengeksekusi semua unsur ini secara berulang sebanyak

.

3)32(22)(27

1123 22

nsptnnTnn

i ii i

Kasus Terbaik: Terdapat tepat satu unsur dalam larik A sama dengan key. (Dalam

hal ini, 1atau 1 22

11

nn

i ii i pt dan s = 0)

untuk kasus terbaik terjadi ketika

contoh kasus:

Diberikan barisan bilangan 21,31,41,51,61,71 dengan key = 61

Untuk unsur yang tidak sama dengan key yaitu i = 1 dan 3 (A[1],A[3],A[4],A[6] ) tidak

perlu mengeksekusi pernyataan. Namun langsung saja pada pernyataan, kecuali

untuk i = 2 (A[2],A[5]. Maka deperoleh sehingga disebut

sebagai kasus terbaik.

5)32(22)(23

1123 22

nsptnnTnn

i ii i

Dengan metode ini (bagi-dua) maka membuat waktu komputasi (running time)

pencarian data menjadi lebih cepat. Namun pengembangan alamiah hanya

mengurangi ½ + ¼ + 1/8 + 1/16 dari jumlah data n.

C. BINARY SEARCH TREE (BST)

• Struktur Data: Prosedur penyimpanan data dalam bentuk tertentu sedemikian

sehingga operasi dasar pada algoritma menjadi lebih efisien atau optimal.

• Pohon biner adalah pohon yang setiap simpulnya memiliki anak paling banyak

berjumlah 2. Anak-anak tersebut dibedakan antara anak kiri (left child) dan anak

kanan (right child). Karena ada perbedaan urutan anak, maka pohon biner adalah

pohon terurut. Pohon biner merupakan jenis pohon yang paling populer karena

sering dimanfaatkan. Pohon biner memang memiliki banya aplikasi, misalnya dalam

sorting atau untuk menghitung hasil evaluasi suatu ekspresi aritmatika.


13

• Metode Binary searh tree lebih memudahkan kita dalam masalah pencarian data,

dengan cara yang mudah yaitu bagi unsur ke dalam dua sisi, sisi kiri untuk unsur

yang lebih kecil sedangkan sisi kanan untuk unsur yang lebih besar.

Contoh kasus:

Diberikan barisan bilangan 36, 34, 35, 32, 38, 37, 39 dengan Key =37, tunjukan

dengan metode Binary Search Tree!

1. Di sini yang menjadi patokan adalah 36.

2. Masukkan angka yang lebih kecil untuk sisi kiri, dan angka yang lebih besar untuk

sisi kanan.

Mulailah melakukan pencarian data, mulai dari atas. Jika bilangan yang dicari lebih

kecil, maka cari ke arah (cabang) bagian kiri. Namun jika bilangan yang dicari lebih

besar, maka carilah ke arah kanan. Begitu selanjutnya sampai diperoleh key yang

dicari.

Diperoleh

Langkah 1: Karena key(37)>36, maka kita cari ke arah kanan

Langkah 2: Karena key(37)<38 maka kita cari ke arah kiri.

36

3

4

37

3

8

3

5 39 32

36

3

4

37

3

8

3

5 39 32


14

36

3

4

37

3

8

3

5 39 32


15

BAB 3

ALGORITMA MERGE SORT


16

A. MERGE SORT

Merge sort merupakan algoritma pengurutan dalam ilmu komputer yang

dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang

tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya

yang terlalu besar. Algoritma ini ditemukan oleh John von Neumann pada tahun 1945.

(id.wikipedia.org)

Divide, conquer, dan combine

Algoritma pengurutan data merge sort dilakukan dengan menggunakan cara

divide and conquer yaitu dengan memecah kemudian menyelesaikan setiap bagian

kemudian menggabungkannya kembali. Pertama data dipecah menjadi 2 bagian

dimana bagian pertama merupakan setengah (jika data genap) atau setengah minus

satu (jika data ganjil) dari seluruh data, kemudian dilakukan pemecahan kembali untuk

masing-masing blok sampai hanya terdiri dari satu data tiap blok. Setelah itu

digabungkan kembali dengan membandingkan pada blok yang sama apakah data

pertama lebih besar daripada data ke-tengah+1, jika ya maka data ke-tengah+1

dipindah sebagai data pertama, kemudian data ke-pertama sampai ke-tengah digeser

menjadi data ke-dua sampai ke-tengah+1, demikian seterusnya sampai menjadi satu

blok utuh seperti awalnya. Sehingga metode merge sort merupakan metode yang

membutuhkan fungsi rekursi untuk penyelesaiannya.

Algoritma Merge Sort ialah algoritma pengurutan yang berdasarkan pada strategi

divide and conquer.

Algoritma Merge Sort dilakukan dengan memenuhi kondisi sebagai berikut :

1.Untuk kasus n=1, maka table a sudah terurut sendirinya (langkah solve)

2. Untuk kasus n>1, maka :

a. DIVIDE: bagi table a menjadi dua bagian, bagian kiri dan bagian kanan, masing-

masing bagian berukuran n/2 elemen.

b. CONQUER: secara rekursif, terapkan algoritma D-and-C pada masing-masing

bagian.

c. MERGE: gabung hasil pengurutan kedua bagian sehingga diperoleh table a yang

terurut.

Dengan menerapkan kedua aturan diatas secara terus menerus maka nantinya akan

didapatkan list yang terurut. Pseudo Code untuk algoritma MergeSort adalah sebagai

berikut:


17

Untuk menyederhanakan perhitungan kompleksitas waktu MergeSort, kita membuat

asumsi ukuran tabel adalah perpangkatan dari 2, yaitu n= dengan k adalah bilangan

bulat positif . Kompleksitas waktu dihitung dari jumlah perbandingan dengan elemen-

elemen tabel.

T(n) = jumlah perbandingan pada pengurutan dua buah subtabel + jumlah perbandingan

pada prosedur Merge.

Kompleksitas prosedur Merge adalah t(n) = cn = O(n), sehingga kompleksitas algoritma

Merge Sort menjadi (dalam bentuk relasi rekurens):

{

( )

dalam hal ini,a dan c adalah konstanta.

Penyelesaian persamaan rekurens:

T(n) =T(n/2)+cn

= 2(2T(n/4) + cn/2) + cn

= 4T(n/4) + 2cn

= 4(2T(n/8) + cn/4) + 2 cn

= ...

= 2k T(n/2k)+kcn

Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah

permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah

untuk diselesaikan. Langkah-langkah umum algoritma Divide and Conquer :

Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan

dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir

sama ).

Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara

rekursif ).

Combine : Menggabungkan solusi masing-masing upa-masalah sehingga membentuk

solusi masalah semula.

Merge sort pseucode

Merge-Sort(A, p, r):

if p < r then

q¬(p+r)/2

Merge-Sort(A, p, q)

Merge-Sort(A, q+1, r)

Merge(A, p, q, r)


18

if p < r then

Bagian ini di proses sebanyak O(1).

q¬(p+r)/2

Pernyataan ini akan dieksekusi sebanyak n/2. Karena data dibagi dua.

Merge-Sort(A, p, q)

Merge-Sort(A, q+1, r)

Pernyataan ini waktu komputasinya adalah T(n/2). Pada bagian ini merupakan proses

divide yaitu data dipecah (dibagi-bagi) hingga potongan terkecil.

Merge(A, p, q, r)

Pernyataan ini waktu komputasinya adalah O(n). Bagian ini merupakan proses combine,

yaitu data digabungkan kembali.

Contoh kasus:

Penyelesaian dengan dengan Divide and Conquer.

Misalkan tabel A berisi elemen-elemen sebagai berikut:

A= 4 12 23 9 21 1 35 2 24

Algoritma MinMaks:

1. Untuk kasus n = 1 atau n = 2,

SOLVE: Jika n = 1, maka min = maks = An. Jika n = 2, maka bandingkan kedua elemen

untuk menentukan min dan maks.

2. Untuk kasus n > 2,

a. DIVIDE: Bagi dua tabel A secara rekursif menjadi dua bagian yang berukuran sama,

yaitu bagian kiri dan bagian kanan.


19

b. CONQUER: Terapkan algoritma Divide and Conquer untuk masing-masing bagian,

dalam hal ini min dan maks dari tabel bagian kiri dinyatakan dalam peubah min1

dan maks1, dan min dan maks dari tabel bagian kanan dinyatakan dalam peubah

min2 dan maks2.

c. COMBINE: Bandingkan min1 dengan min2 untuk menentukan min tabel A.

Bandingkan maks1 dengan maks2 untuk menentukan maks tabel A.

Tinjau kembali soal di atas

DIVIDE dan CONQUER: Bagi tabel menjadi dua bagian sampai berukuran 1 atau 2

elemen:

4 12 23 9 21 1 35 2 24

4 12 23 9 21 1 35 2 24

4 12 23 9 21 1 35 2 24

SOLVE dan COMBINE: Tentukan min dan maks masing-masing bagian tabel, lalu gabung:

4 12 23 9 21 1 35 2 24

min=4 min=9 min=1 min=35 min=2

maks=12 maks=23 maks=21 maks=35 maks=24

4 12 23 9 21 1 35 2 24

min = 4 min = 1 min = 2

maks=23 maks = 21 maks=35

4 12 23 9 21 1 35 2 24

min = 4 min = 1

maks = 23 maks = 35

4 12 23 9 21 1 35 2 24

min = 1

maks = 35

Jadi, nilai minimum tabel = 1 dan nilai maksimum = 35.

Merge Sort : contoh lain

Pertama, data dibagi 2 bagian, selanjutnya tiap bagian dibagi lagi menjadi dua bagian,

demikian selanjutnya hingga data tidak dapat dibagi lagi. Tahap ini merupakan divide.


20

Setelah dibagi hingga potongan terkecil, data tesebut diurutkan kembali.

Setelah data diurutkan kembali, maka tahap terakhir adalah data tersebut

disatukan/dikombain.

Implementasi Merge Sort :

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

void printv(char* in, int *v, int n) {


21

printf("%s", in);

int i = 0;

for (; i < n; ++i)

printf("%d ", v[i]);

printf("\n");

}

void merge(int *v, int p, int q, int r) {

int i = p;

int j = q + 1;

int *tmp = (int*)malloc((r - p + 1) * sizeof(int));

int k = 0;

while ((i <= q) && (j <= r)) {

if (v[i] < v[j])

tmp[k++] = v[i++];

else

tmp[k++] = v[j++];

}

while (i <= q)

tmp[k++] = v[i++];

while (j <= r)

tmp[k++] = v[j++];

memcpy(v + p, tmp, (r - p + 1) * sizeof(int));

free(tmp);

}

void mergeS(int *v, int p, int r) {

if (p < r) {

int q = (p + r) / 2;

mergeS(v, p, q);

mergeS(v, q + 1, r);

merge(v, p, q, r);

}

}

int main(int argc, char *argv[]) {

int n = 10;


22

int v[] = {9, 8, 7, 6, 5, 5, 4, 3, 2, 1};

printv("V: ", v, n);

mergeS(v, 0, n - 1);

printv("V: ", v, n);

return 0;

}

Output:

B. RECURRENCE

Recurrence adalah fungsi yang memanggil dirinya sendiri. Rekurensi adalah suatu

persamaan atau pertidaksamaan yang menguraikan fungsi dalam suku-suku nilai input

yang lebih kecil.

Pada bagian ini ada tiga metode untuk menyelesaikan rekurensi, yaitu untuk

mendapatkan batas asymptotic "" atau ""O pada solusi. Ketiga metode adalah

metode iterasi, substitusi, metode master.

Menyelesaikan fungsi recurrence, terdapat 3 metode, yakni:

1. Metode substitusi

o Pertama-tama dibuat suatu “guess” dari bentuk solusinya.

o Gunakan induksi matematika untuk membuktikan bahwa guess itu benar.

o Metode ini dapat digunakan untuk menentukan baik batas atas maupun batas

bawah suatu rekurensi.

Contoh:

Tentukan batas atas dari T(n) = 2(T(n/2)) + n

Jawab:

Pertama, dibuat “guess” dari solusinya adalah T(n) = O(n lg n)

Kedua, dibuktikan dengan induksi matematis bahwa solusi di atas benar, yaitu

dibuktikan bahwa T(n) c (nlgn)

o Basis untuk n = 2, T(2) = 2(T(2/2))+ 2 = 4 c (2lg2), dengan c 2

o Anggap solusi diatas berlaku untuk n/2, yaitu T(n/2) c (n/2) lg (n/2)

o Dibuktikan bahwa solusi diatas berlaku untuk n.

o Substitusikan pertidaksamaan T(n/2) c (n/2) lg (n/2) ke rekurensi,

diperoleh:

T(n) 2 (c (n/2) lg (n/2)) + n


23

cn lg (n/2) + n

cn lg (n) – cn lg 2 + n

= cn lg n – cn + n

cn lg n, untuk c 1 (terbukti)

Jadi batas atas dari rekurensi diatas adalah T(n) = O (n lg n). Pada “guess” kadang-

kadang solusinya bisa dengan manipulasi aljabar, karena belum pernah diketahui solusi

yang mirip.

Contoh:

T(n) = 2 T(n) + lg n

Jawab:

Misalkan m = lg n n = 2m

n = n1/2 = (2m)1/2 = 2m/2

T(2m) = 2 T(2m/2) + m

Misalkan lagi S(m) = T(2m), sehingga rekurensinya menjadi S(m) = 2 S(m/2) + m,

Yang mirip dengan T(n) = T(n/2) + n

Jadi solusinya serupa yaitu: S(m) = O(m lg m).

Dengan mengubah kembali dari S(m) ke T(n) diperoleh:

T(n) = T(2m) = S(m) = O(m lg m)

= O(lg n (lg lg n))

2. Metode iterasi (pohon rekursif)

Metode iterasi mengkonversi rekurensi ke dalam jumlahan dan kemudian

berdasarkan cara untuk bounding summations untuk menyelesaikan rekurensi.

Prinsip dari metode iterasi adalah menjabarkan rekurensi sebagai suatu bentuk

penjumlahan yang hanya bergantung pada n dan syarat awal.

Contoh:

T(n) = c + T(n/2);

Ganti n dengan n/2 diperoleh: T(n/2) = c + T(n/4) dan T(n/4) = c + T(n/8).

Kemudian masukkan ke formula diperoleh:

T(n) = c + T(n/2)

= c + c + T(n/4) = c + c + T(n/8)

Jika misalkan n = 16, formula di atas dapat dinyatakan:

T(16) = c+T(16/2) = c+c+T(16/4) = c+c+c+T(16/8)

= c+c+c+c+T(16/16) = c.4 + T(1).

Jadi formula di atas misalkan diasumsikan n = 2k

T(n) = c+c+....+c+T(1) = c lg(n) + T(1)

))(lg( n


24

Contoh pohon rekursif:

Tn = n + T(n)

T(n) = n+2T(n/2)= n log2n, nilai n = (n/2)

n

n

n

--

nk

n log 2 n

3. Metode master

Metode master melengkapi batas-batas untuk rekurensi dari bentuk

)()/()( nfbnaTnT , dengan 1,1 ba , dan )(nf fungsi yang diketahui; ini

perlu diketahui/dipahami dan dihafal, karena sekali anda melakukan ini penentuan

batas asimtotis untuk rekurensi sederhana akan mudah.

Rumus untuk menyelesaikan rekurensi berbentuk:

Andaikan )()( nfb

naTnT

Di mana, a ≥ 1, b > 1, and f(n) > 0

Case 1: if f(n) = O(nlogba -) for some > 0, then:

T(n) = (nlogba)

Case 2: if f(n) = (nlogba), then: T(n) = ( nlogba lgn)

Case 3: if f(n) = (nlogba+ε) for some > 0, and if af(n/b) ≤ cf(n) for some c < 1 and all

sufficiently large n, then:

T(n) = (f(n))

n

n/2

n/4

n/2

n/4 n/4 n/4


25

Contoh:

1.

2.

3.

4.

2

3

log 1

log 9

2

( ) ( / 2) 1

1, 2; 1

also ( ) 1, ( ) (1)

( ) (lg )

(

Case 2:

Cas

) 9 ( / 3)

9, 3;

( ) , ( ) ( ) with 1

( )e 1:

T n T n

a b n

f n f n

T n n

T n T n n

a b

f n n f n O n

T n n

4

4

2

log 3 0.793

log 3

log 2 1

( ) 3 ( / 4) lg

3, 4;

( ) lg , ( ) ( ) with 0.2

Regularity condition

( / ) 3( / 4) l

Case

g( / 4) (3 / 4) lg ( ) for 3 / 4

( ) ( lg )

( ) 2 ( / 2) lg

2, 2;

3:

T n T n n n

a b n n

f n n n f n n

af n b n n n n cf n c

T n n n

T n T n n n

a b n n

f

1

1

( ) lg , ( ) ( ) with ?

also l

neither Case 3 nor Case 2!

g / lg

n n n f n n

n n n n


26


27

BAB 4

STRATEGI ALGORITMA (I)

METODE GREEDY & DYNAMIC PROGRAMMING


28

Ada banyak macam strategi algoritma yang biasanya digunakan. Khusus pada bab ini,

strategi algoritma yang akan dibahas adalah metode greedy dan dynamic programming.

A. Metode Greedy

Prinsip metode greedy ini adalah: “take what you can get now!”.

Algoritma greedy membentuk solusi langkah per langkah (step by step). Pada setiap

langkah, terdapat banyak pilihan yang perlu dieksplorasi. Oleh karena itu, pada setiap

langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Pada setiap

langkah, kita membuat pilihan optimum lokal (local optimum) dengan harapan

bahwa langkah sisanya mengarah ke solusi optimum global (global optimum).

Algoritma greedy adalah algoritma yang memecahkan masalah langkah per langkah.

Pada setiap langkah:

o Mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa

memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”)

o Berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir

dengan optimum global.

Skema umum dari algoritma greedy disusun oleh elemen-elemen sebagai berikut :

1. Himpunan kandidat

Himpunan ini berisi elemen-elemen pembentuk solusi.

2. Himpunan solusi

Himpunan ini berisi bagian dari himpunan kandidat yang terpilih sebagai solusi

persoalan.

3. Fungsi seleksi

Fungsi ini adalah fungsi yang pada setiap langkah memilih solusi yang paling

memungkinkan mencapai solusi optimal.

4. Fungsi kelayakan

Fungsi ini memasukkan kandidat-kandidat yang layak dari himpunan kandidat ke

himpunan solusi.

5. Fungsi obyektif

Yaitu fungsi yang memaksimumkan atau meminimumkan nilai solusi

Contoh kasus:

Tinjau masalah penukaran uang

Langkah strategi metode greedy:

Pada setiap langkah, pilihlah koin dengan nilai terbesar dari himpunan koin yang

tersisa.

Misal: diberikan jumlah uang A = $ 32, koin yang tersedia: $1, $5, $10, dan $25

Langkah 1 :pilih 1 buah koin $25 (Total = 25)

1 koin uang $20= $20


29

Sisa = $7

Langkah 2 :pilih 1 buah koin $5 (Total = 25 + 5 = 30)

1 koin uang $5= $5

Sisa = $2

Langkah 3 :pilih 2 buah koin $1 (Total = 25+5+1+1= 32)

2 koin uang $1= $2

Sisa = 0

Solusi: Jumlah koin minimum = $4 (solusi optimal!)

Catatan:

Algoritma greedy tidak beroperasi secara menyeluruh terhadap semua alternatif

solusi yang ada (sebagaimana pada metode exhaustive search).

Terdapat beberapa fungsi SELEKSI yang berbeda, sehingga kita harus memilih fungsi

yang tepat jika kita ingin algoritma menghasilkan solusi optiamal.

Kesimpulan:

Jadi, pada sebagian masalah, metode greedy tidak selalu berhasil memberikan solusi

yang optimal.

Kelebihan dan kelemahan metode greedy:

Kelebihan:

Kompleksitas ruangnya rendah. Memori yang dibutuhkan tidak besar, karena

langkah sebelumnya tidak disimpan. Kita terus memperhatikan langkah di depan

saja. Sehingga sangat kecil kemungkinan mengalami masalah ketersediaan memori.

Mudah diimplementasikan, algoritma greedy sangat mudah untuk

diimplementasikan pada persoalan-persoalan yang ada.

Kompleksitas waktunya rendah, sehingga jarang mengalami masalah dalam

lamanya waktu pencarian langkah.

Kelemahan:

Hasilnya belum tentu optimal.

Hanya mencari solusi terbaik saat itu, padahal nelum tentu terbaik untuk langkah

berikutnya.


30

B. Dynamic Programming

Dynamic programming problems adalah masalah multi tahap(multistage) dimana

keputusan dibuat secara berurutan (in sequence).

Pemrograman dinamis (dynamic programming) adalah metode pemecahan masalah

dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan

(stage) sedemikian rupa sehingga solusi dari permasalahan ini dapat dipandang dari

serangkaian keputusan-keputusan kecil yang saling berkaitan satu dengan yang lain.

Penyelesaian persoalan dengan pemrograman dinamis ini akan menghasilkan

sejumlah berhingga pilihan yang mungkin dipilih, lalu solusi pada setiap tahap-tahap

yang dibangun dari solusi pada tahap sebelumnya, dan dengan metode ini kita

menggunakan persyaratan optimasi dan kendala untuk membatasi sejumlah pilihan

yang harus dipertimbangkan pada suatu tahap.

Karakteristik Persoalan yang dimiliki oleh Program Dinamis:

o Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada setiap tahap hanya

dapat diambil satu keputusan.

o Masing-masing tahap terdiri dari sejumlah status (state) yang berhubungan dengan

tahap tersebut. Secara umum, status merupakan bermacam kemungkinan masukan

yang ada pada tahap tersebut. Jumlahnya bisa berhingga atau tak berhingga.

o Hasil dari keputusan yang diambil pada setiap tahap ditransformasikan dari status

yang bersangkutan ke status berikutnya pada tahap berikutnya.

o Ongkos (cost) pada suatu tahap meningkat secara teratur (steadily) dengan

bertambahnya jumlah tahapan.

o Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap yang sudah berjalan

dan ongkos pada tahap tersebut.

o Keputusan terbaik pada suatu tahap bersifat independen terhadap keputusan yang

dilakukan pada tahap sebelumnya.

o Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap

status pada tahap k memberikan keputusan terbaik untuk setiap status pada tahap k +

1.

o Prinsip optimalitas berlaku pada persoalan tersebut.

Langkah-langkah Pengembangan Algoritma Program Dinamis sebagai berikut :

a) Karakteristikkan struktur solusi optimal.

b) Definisikan secara rekursif nilai solusi optimal.

c) Hitung nilai solusi optimal secara maju atau mundur.

d) Konstruksi solusi optimal.

Contoh kasus:

Joe tinggal di new York dan akan pergi ke LA. Dia berencana menginap di rumah

temannya dalam perjalanan tersebut. Joe punya teman di Columbus, Nashville,

Louisville, Kansas, Omaha, Dallas, San Antonio, dan Denver. Joe tahu setelah satu hari


31

perjalanan dia akan mencapai Columbus, Nashville atau Louisville. Setelah perjalanan 2

hari akan mencapai Kansas, Omaha, atau Dallas. Setelah 3 hari perjalanan akan mencapai

Denver atau San Antonio. Setelah 4 hari akan mencapai LA. Untuk meminimalkan jarak,

kemana Joe harus menginap setiap malam dalam perjalanannya ?

Stage 3:

Kansas = {New York, Columbus} cost Kansas=1230

Omaha= {New York, Columbus} cost Omaha=1340

Dallas={New York, Nashville} cost Dallas= 1560

Stage 4:

Denver={ New York, Columbus, Kansas} cost Denver=1840

San Antonio={ New York, Nashville, Dallas} cost San Antonio=1830

Stage 5:

LA={ New York, Columbus, Kansas, Denver } cost LA=2870

Jadi jarak optimal yang diperoleh adalah 2870

Kelebihan dan kelemahan metode dynamic programming:

Kelebihan:

mengoptimalkan penyelesaian suatu masalah tertentu yang diuraikan menjadi sub-

sub masalah yang lebih kecil yang terkait satu sama lain dengan tetap memperhatikan

kondisi dan batasan permasalahan tersebut.

Proses pemecahan suatu masalah yang kompleks menjadi sub-sub masalah yang lebih

kecil membuat sumber permasalahan dalam rangkaian proses masalah tersebut

menjadi lebih jelas untuk diketahui.

Pendekatan dynamic programming dapat diaplikasikan untuk berbagai macam

masalah pemrograman matematik, karena dynamic programming cenderung lebih

fleksibel daripada teknik optimasi lain.


32

Prosedur perhitungan dynamic programming juga memperkenankan bentuk analisis

sensitivitas terdapat pada setiap variabel status (state) maupun pada variabel yang

ada di masing-masing tahap keputusan (stage).

Dynamic programming dapat menyesuaikan sistematika perhitungannya menurut

ukuran masalah yang tidak selalu tetap dengan tetap melakukan perhitungan satu per

satu secara lengkap dan menyeluruh.

Kelemahan:

Penggunaan dynamic programming jika tidak dilakukan secara tepat, akan

mengakibatkan ketidakefisienan biaya maupun waktu. Karena dalam menggunakan

dynamic programming diperlukan keahlian, pengetahuan, dan seni untuk

merumuskan suatu masalah yang kompleks, terutama yang berkaitan dengan

penetapan fungsi transformasi dari permasalahan tersebut.

Contoh Kasus:

Diberikan sebuah kotak berukuran 15cmx35cm.

35

15

Jenis kotak, ada 4 buah yang akan disusun ke dalam kotak tersebut:

6 cm

Kotak 3

Kotak

1

Kotak2

Kotak4


33

Penyelesaian dengan metode greedy:

Kotak 4 dan kotak 1 tersebut disusun seperti di bawah ini:

Sehingga diperoleh luas yang dianggap bisa menempati kotak tersebut dengan luas

yang optimum.

4 2 4

4

10

Kotak yang telah disusun tersebut dimasukkan ke dalam kota besar yang berukuran

15x35 cm. jumlah kotak yang dimasukkan adalah sebanyak 9 buah, sehingga diperoleh

sbb:

10 10 10

Tempat yang kosong masih dapat diisi dengan kotak berukuran 4x2 cm.. jumlah

kotak yang dimasukkan adalah sebanyak 14 buah. Sehingga diperoleh:

35

Dapat dihitung luas dari sisa kotak yang tidak terisi adalah: 35 + 9 + 12 =56

1

3


34

Penyelesaian dengan dynamic programming:

Pada metode ini, kotak yang akan diisi dibagi 2 bagian. Sehingga kita akan mengisi kotak

tersebut dengan 2 step. Hasilnya menjadi seperti di bawah ini:

8cm

7cm

35 cm

Kemudian dari 4 kotak yang ada dibentuklah susunan kotak yang sesuai sehingga dapat

dimasukkan ke dalam kota utama di atas. Berikut adalah kotak yang sesuai dengan kotak

utama (kotak ini dibentuk dari kotak 1 dan kotak 2):

STEP 1: Kotak tersebut kemudian diisi ke dalam kotak utama bagian (I)

STEP 2: Selanjutnya kita akan mengisi kotak bagian (II). Kembali kita meninjau kotak

yang telah disusun, ternyata masih biasa digunakan untuk mengisi kotak bagian (II) ini.

Sehingga diperoleh:

8cm

7cm

3cm

I

II


35

Selanjutnya kita meninjau kembali tempat yang masi belum terisi, ternyanya masih ada

kotak yang dapat diisi ke dalam, yakni kotak berukuran 4x2 cm. Setelah diisi, kita

memperoleh hasil sebagai berikut:

Sisa kotak yang kosong adalah= 4+9=13

Kesimpulan:

Jika kita membandingkan metode greedy dengan metode dynamic programming,

maka yang mendapatkan sisa kotak yang paling minimum adalah metode dynamic

programming. Jadi metode yang paling optimal adalah dynamic programming.

Prinsip Optimalitas

• Pada program dinamis, rangkaian keputusan yang optimal dibuat

dengan menggunakan Prinsip Optimalitas.

• Prinsip Optimalitas: jika solusi total optimal, maka bagian solusi

sampai tahap ke-k juga optimal.

• Prinsip optimalitas berarti bahwa jika kita bekerja dari tahap k ke

tahap k + 1, kita dapat menggunakan hasil optimal dari tahap k tanpa

harus kembali ke tahap awal.

• ongkos pada tahap k +1 = (ongkos yang dihasilkan pada tahap k ) +

(ongkos dari tahap k ke tahap k + 1)

• Dengan prinsip optimalitas ini dijamin bahwa pengambilan keputusan

pada suatu tahap adalah keputusan yang benar untuk tahap-tahap

selanjutnya.

• Pada metode greedy hanya satu rangkaian keputusan yang pernah

dihasilkan, sedangkan pada metode program dinamis lebih dari satu

rangkaian keputusan. Hanya rangkaian keputusan yang memenuhi

prinsip optimalitas yang akan dihasilkan.


36


37

BAB 5

STRATEGI ALGORITMA (II)


38

A. Algoritma Metaheuristik

Heuristik berasal dari kata Yunani Heuriskein yang berarti seni

untuk menemukan strategi dalam menyelesaikan persoalan sedangkan meta

berarti metodologi tingkat tinggi atau lanjut (Talbi, 2009). Di dalam ilmu

komputer, metode heuristik merupakan suatu teknik untuk penyelesaian

permasalahan yang tidak menekankan pada pembuktian apakah solusi yang

didapatkan adalah benar (pembuktian apakah suatu solusi adalah benar

merupakan fokus dari metode penyelesaian analitik), tetapi lebih menekankan

pada performa komputasi dan kesederhanaan. Metode heuristik merupakan

suatu metode penyelesaian yang menggunakan konsep pendekatan

Menurut Talbi (2009), metaheuristik dapat didefinisikan sebagai metode

lanjut (advanced) berbasis heuristic untuk menyelesaikan persoalan optimisasi

secara efisien. Metaheuristik didefinisikan sebagai metode optimisasi yang

dilakukan dengan memperbaiki kandidat penyelesaian secara iteratif sesuai

dengan fungsi objektifnya. Metode ini mampu menghasilkan penyelesaian yang

baik dalam waktu yang cepat (acceptable), tetapi tidak menjamin bahwa penyelesaian

yang dihasilkan merupakan penyelesaian terbaik (optimal). Metode

metaheuristik banyak dipakai dalam optimisasi stokastik (optimisasi stokastim

merupakan optimisasi yang memiliki derajat ketidakpastian atau random).

Metaheuristik dapat menggunakan domain pengetahuan khusus dalam bentuk

heuristik yang dikendalikan dengan strategi tingkat lanjuti) Metaheuristik dapat

menggunakan pengalaman yang didapat selama proses pencarian untuk menuntun

proses pencarian. Dalam menentukan apakah metaheuristik adalah metode yang

sesuai untuk menyelesaikan suatu permasalahan, ada beberapa hal yang perlu

diperhatikan misalnya kompleksitas permasalahan, ukuran input, struktur input

dan waktu yang diperlukan untuk menyelesaikan masalah tersebut. Secara umum

metehauristik dipakai untuk masalah-masalah yang komplek dan tidak bisa

diselesaikan dengan mudah secara analitikal/eksak. Tidaklah terlalu bermanfaat

menggunakan metaheuristik untuk persoalan yang dengan mudah dan cepat dapat

diselesaikan secara eksak (penyelesaian eksak merupakan penyelesaian terbaik,

tetapi seringkali metode ini tidak dapat diterapkan pada permasalahan optimisasi,

sehingga dipakailah metode pendekatan). Metaheuristik pada sebenarnya adalah

metode pendekatan yang didasarkan pada metode heuristik. Sehingga tidak heran

bahwa metode heuristik sering kali diintegrasikan didalam metodeme taheuristik.

Perbedaan utaman dari metode heuristik dan metaheuristik adalah: metode

heuristik bersifat problem dependent sedangkan metode metaheuristik bersifat

problem independent.


39

B. Algoritma Genetika

Algoritma genetika adalah algoritma komputasi yang diinspirasi teori evolusi

yang kemudian diadopsi menjadi algoritma komputasi untuk mencari solusi

suatu permasalahan dengan cara yang lebih “alamiah”. Salah satu aplikasi

algoritma genetika adalah pada permasalahan optimasi kombinasi, yaitu

mendapatkan suatu nilai solusi optimal terhadap suatu permasalahan yang

mempunyai banyak kemungkinan solusi. Dalam tulisan ini akan dibahas teori

dasar algoritma genetika beserta contoh aplikasinya dalam menyelesaikan suatu

permasalahan optimasi kombinasi sederhana.

Algoritma genetika adalah algoritma heuristik adaptif (metaheuristik) yang

memiliki dasar pemikiran atau gagasan evolusioner untuk proses seleksi alami dan

genetika. Konsep dasar dari algoritma genetika dirancang untuk menirukan proses di

dalam sistem alami yang penting bagi evolusi makhluk hidup untuk dapat terus

bertahan hidup, yang secara rinci teori ini dicetuskan oleh Charles Darwin yaitu

“Survival of the Fittest”. Dengan menirukan teori dari Charles Darwin, algoritma

genetika dapat digunakan, untuk mencari solusi dari segala macam permasalahan

dalam ilmu pengetahuan seperti dalam mencari solusi penjadwalan job shop.

Pelopor pertama penggunaan metode algoritma genetika adalah John Holland

pada tahun 60-an. Algoritma genetika menggunakan analogi seleksi alam yang

bekerja dari suatu populasi yang terdiri dari berbagai individu (gen), yang

masing-masing individu mempresentasikan suatu solusi yang mungkin muncul dari

persoalan yang dihadapi. Dalam hal ini, individu yang terpilih dilambangkan

dengan sebuah nilai fitness yang digunakan untuk mencari solusi terbaik dari

persoalan yang ada.

Teori Dasar Algoritma Genetika

Algoritma genetika yang dikembangkan oleh Goldberg adalah algoritma

komputasi yang diinspirasi teori evolusi Darwin yang menyatakan bahwa

kelangsungan hidup suatu makhluk dipengaruhi aturan “yang kuat adalah yang

menang”. Darwin juga menyatakan bahwa kelangsungan hidup suatu makhluk dapat

dipertahankan melalui proses reproduksi, crossover, dan mutasi. Konsep dalam

teori evolusi Darwin tersebut kemudian diadopsi menjadi algoritma komputasi

untuk mencari solusi suatu permasalahan dengan cara yang lebih “alamiah”.

Sebuah solusi yang dibangkitkan dalam algoritma genetika disebut sebagai

chromosome, sedangkan kumpulan chromosome-chromosome tersebut disebut

sebagai populasi. Sebuah chromosome dibentuk dari komponen-komponen

penyusun yang disebut sebagai gen dan nilainya dapat berupa bilangan numerik,

biner, simbol ataupun karakter tergantung dari permasalahan yang ingin


40

diselesaikan. Chromosome-chromosome tersebut akan berevolusi secara

berkelanjutan yang disebut dengan generasi. Dalam tiap generasi chromosome-

chromosome tersebut dievaluasi tingkat keberhasilan nilai solusinya terhadap

masalah yang ingin diselesaikan (fungsi_objektif) menggunakan ukuran yang

disebut dengan fitness. Untuk memilih chromosome yang tetap dipertahankan

untuk generasi selanjutnya dilakukan proses yang disebut dengan seleksi. Proses

seleksi chromosome menggunakan konsep aturan evolusi Darwin yang telah

disebutkan sebelumnya yaitu chromosome yang mempunyai nilai fitness tinggi akan

memiliki peluang lebih besar untuk terpilih lagi pada generasi selanjutnya.

Chromosome-chromosome baru yang disebut dengan offspring, dibentuk

dengan cara melakukan perkawinan antar chromosome-chromosome dalam satu

generasi yang disebut sebagai proses crossover. Jumlah chromosome dalam

populasi yang mengalami crossover ditetukan oleh paramater yang disebut dengan

crossover_rate. Mekanisme perubahan susunan unsur penyusun mahkluk hidup

akibat adanya faktor alam yang disebut dengan mutasi direpresentasikan sebagai

proses berubahnya satu atau lebih nilai gen dalam chromosome dengan suatu nilai

acak. Jumlah gen dalam populasi yang mengalami mutasi ditentukan oleh parameter

yang dinamakan mutation_rate. Setelah beberapa generasi akan dihasilkan

chromosome-chromosome yang nilai gen-gennya konvergen ke suatu nilai tertentu

yang merupakan solusi terbaik yang dihasilkan oleh algoritma genetika terhadap

permasalahan yang ingin diselesaikan.

Prosedure Algoritma Genetika

Algoritma genetik yang umum menyaratkan dua hal untuk didefinisikan: (1)

representasi genetik dari penyelesaian, (2) fungsi kemampuan untuk

mengevaluasinya.

Representasi baku adalah sebuah larik bit-bit. Larik jenis dan struktur lain dapat

digunakan dengan cara yang sama. Hal utama yang membuat representasi genetik

ini menjadi tepat adalah bahwa bagian-bagiannya mudah diatur karena ukurannya

yang tetap, yang memudahkan operasi persilangan sederhana. Representasi panjang

variabel juga digunakan, tetapi implementasi persilangan lebih kompleks dalam

kasus ini. Representasi seperti pohon diselidiki dalam pemrograman genetik dan

representasi bentuk bebas diselidiki di dalam HBGA.

Fungsi kemampuan didefinisikan di atas representasi genetik dan mengukur

kualitas penyelesaian yang diwakili. Fungsi kemampuan selalu tergantung pada

masalah. Sebagai contoh, jika pada ransel kita ingin memaksimalkan jumlah benda

(obyek) yang dapat kita masukkan ke dalamnya pada beberapa kapasitas yang

tetap. Representasi penyelesaian mungkin berbentuk larik bits, dimana tiap bit

mewakili obyek yang berbeda, dan nilai bit (0 atau 1) menggambarkan apakah

obyek tersebut ada di dalam ransel atau tidak. Tidak setiap representasi seperti ini


41

valid, karena ukuran obyek dapat melebihi kapasitas ransel. Kemampuan

penyelesaian adalah jumlah nilai dari semua obyek di dalam ransel jika representasi

itu valid, atau jika tidak 0. Dalam beberapa masalah, susah atau bahkan tidak

mungkin untuk mendefinisikan lambang kemampuan, maka pada kasus ini

digunakan IGA.

Sekali kita mendefinisikan representasi genetik dan fungsi kemampuan,

algoritma genetik akan memproses inisialisasi populasi penyelesaian secara acak,

dan memperbaikinya melalui aplikasi pengulangan dengan aplikasi operator-

operator mutasi, persilangan, dan seleksi.

Secara sederhana, algoritma umum dari algoritma genetik ini dapat dirumuskan

menjadi beberapa langkah, yaitu:

1. Membentuk suatu populasi individual dengan keadaan acak

2. Mengevaluasi kecocokan setiap individual keadaan dengan hasil yang diinginkan

3. Memilih individual dengan kecocokan yang tertinggi

4. Bereproduksi, mengadakan persilangan antar individual terpilih diselingi mutasi

5. Mengulangi langkah 2 - 4 sampai ditemukan individual dengan hasil yang

diinginkan.

Pada umumnya suatu penerapan algoritma genetika secara generasional sederhana

terdiri dari 3 bagian, yaitu:

1. Memilih populasi awal (inisial populasi)

2. Evaluasi nilai fitness dari setiap individu didalam populasi

3. Ulangi sampai proses berhenti (nilai fitness terbaik terpenuhi)

a) Pilih individu terbaik berdasar ranking untuk reproduksi

b) Bentuk generasi baru melalui pindah silang dan mutasi untuk

menghasilkan keturunan baru (child)

c) Evaluasi nilai fitness keturunan yang dihasilkan

Jika diilustrasikan, maka proses algoritma genetika yang dilakukan dapat terlihat seperti gambar berikut:

http://id.wikipedia.org/wiki/Mutasi

http://id.wikipedia.org/w/index.php?title=Persilangan&action=edit&redlink=1

http://id.wikipedia.org/w/index.php?title=Seleksi&action=edit&redlink=1


42

Definisi Individu

Individu menyatakan solusi yaitu nilai x. Nilai x sebagai individu dinyatakan dalam

nilai biner. Individu dinyatakan dalam 8 gen biner dengan batas 0 sampai dengan 1

yang berarti sat bit setara dengan 2-8

Sebagai contoh:

10001001 = (128+8+1)/256 = 0.5352

01010010 = (2+16+64)/256 = 0.3203

Fungsi Fitness

Fungsi fitness dinyatakan sebagai fungsi f(x), karena yang dicari adalah nilai

maksimum.

Membangkitkan Populasi Awal

Membangkitkan sejumlah individu, misalkan satu populasi terdiri dari 8 individu,

maka dibangkitkan 8 individu dengan 8 gen biner yang dibangkitkan secara acak.

Seleksi

Seleksi roulette whell untuk memilih induk dilakukan dengan menggunakan

prosentasi fitness setiap individu, dimana setiap individu mendapatkan luas bagian

sesuai dengan prosentase nilai fitnessnya.


43

Hitung Total Fitness

Menghitung prosentase fitness dan penentuan bidang

Aplikasi Algoritma Genetika

Berikut adalah contoh aplikasi algoritma genetika yang digunakan untuk

menyelesaikan masalah kombinasi. Misalkan ada persamaan a+2b+3c+4d = 30, kita

mencari nilai a, b, c, dan d yang memenuhi persamaan diatas. Kita mencoba

menggunakan algoritma genetika untuk menyelesaikan permasalahan diatas.

Diagram alir dari algoritma genetika untuk menyelesaikan permasalahan diatas dapat

dilihat pada Gambar 1.


44

Penjelasan mengenai langkah-langkah penyelesaian permasalahan diatas

menggunakan algoritma genetika adalah sebagai berikut:


45

1. Pembentukan chromosome

Karena yang dicari adalah nilai a, b, c, d maka variabel a, b, c, d dijadikan sebagai

gen-gen pembentuk chromosome. Batasan nilai variabel a adalah bilangan integer

0 sampai 30. Sedangkan batasan nilai variabel b, c, dan d adalah bilangan integer 0

sampai 10.

2. Inisialisasi

Proses inisialisasi dilakukan dengan cara memberikan nilai awal gen-gen dengan

nilai acak sesuai batasan yang telah ditentukan.

Misalkan kita tentukan jumlah populasi adalah 6, maka:

Chromosome[1] = [a;b;c;d] = [12;05;03;08]

Chromosome[2] = [a;b;c;d] = [02;01;08;03]

Chromosome[3] = [a;b;c;d] = [10;04;03;04]

Chromosome[4] = [a;b;c;d] = [20;01;10;06]

Chromosome[5] = [a;b;c;d] = [01;04;03;09]

Chromosome[6] = [a;b;c;d] = [20;05;07;01]

3. Evaluasi Chromosome

Permasalahan yang ingin diselesaikan adalah nilai variabel a, b, c, dan d yang

memenuhi persamaan a+2b+3c+4d = 30, maka fungsi_objektif yang dapat

digunakan untuk mendapatkan solusi adalah fungsi_objektif(chromosome) = |

(a+2b+3c+4d) – 30 |

Kita hitung fungsi_objektif dari chromosome yang telah dibangkitkan:

fungsi_objektif(chromosome[1]) = Abs(( 12 + 2*5 + 3*3 + 4*8 ) - 30)

= Abs((12 + 10 + 9 + 32 ) - 30)

= Abs(63 - 30)

= 33


= Abs(( 2 + 2 + 24 + 12 ) - 30)

= Abs(40 - 30)

= 10


= Abs(( 10 + 8 + 9 + 16 ) - 30)

= Abs(43 - 30)

= 13


= Abs(( 20 + 2 + 30 + 24 ) - 30)

= Abs(76 - 30)

= 46


= Abs(( 1 + 8 + 9 + 36 ) - 30)

= Abs(54 - 30)


46

= 24


= Abs(( 20 + 10 + 21 + 4) - 30)

= Abs(55 - 30)

= 25

Rata-rata dari fungsi objektif adalah:

rata-rata = (33+10+13+46+24+25)/6

= 151 / 6

= 25.167

4. Seleksi Chromosome

Proses seleksi dilakukan dengan cara membuat chromosome yang mempunyai

fungsi_objektif kecil mempunyai kemungkinan terpilih yang besar atau

mempunyai nilai probabilitas yang tinggi. Untuk itu dapat digunakan fungsi fitness

= (1/(1+fungsi_objektif)), fungsi_objektif perlu ditambah 1 untuk menghindari

kesalahan program yang diakibatkan pembagian oleh 0.

fitness[1] = 1 / (fungsi_objektif[1]+1)

= 1 / 34

= 0.0294


= 1 / 11

= 0.0909


= 1 / 14

= 0.0714


= 1 / 47

= 0.0212


= 1 / 25

= 0.0400


= 1 / 26

= 0.0385

total_fitness = 0.0294 + 0.0909 + 0.0714 + 0.0212 + 0.04 + 0.0385

= 0.2914

Rumus untuk mencari probabilitas: P[i] = fitness[i] / total_fitness

P[1] = 0.0294 / 0.2914 = 0.1009

P[2] = 0. 0909 / 0.2914 = 0.3119


47

P[3] = 0. 0714 / 0.2914 = 0.2450

P[4] = 0. 0212 / 0.2914 = 0.0728

P[5] = 0.04 / 0.2914 = 0.1373

P[6] = 0.0385 / 0.2914 = 0.1321

Dari probabilitas diatas dapat kita lihat kalau chromosome ke 2 yang mempunyai

fitness paling besar maka chromosome tersebut mempunyai probabilitas untuk

terpilih pada generasi selanjutnya lebih besar dari chromosome lainnya. Untuk

proses seleksi kita gunakan roulete wheel, untuk itu kita harus mencari dahulu nilai

kumulatif probabilitasnya:

C[1] = 0.1009

C[2] = 0.1009+ 0.3119 = 0.4128

C[3] = 0.1009+ 0.3119 + 0.2450 = 0.6578

C[4] = 0.1009+ 0.3119 + 0.2450 + 0.0728 = 0.7306

C[5] = 0.1009+ 0.3119 + 0.2450 + 0.0728 + 0.1373 = 0.8679

C[6] = 0.1009+ 0.3119 + 0.2450 + 0.0728 + 0.1373 + 0.1321= 1

Setelah dihitung cumulative probabilitasnya maka proses seleksi menggunakan

roulete-wheel dapat dilakukan. Prosesnya adalah dengan membangkitkan

bilangan acak R dalam range 0-1.

Jika R[k] < C[1] maka pilih chromosome 1 sebagai induk, selain itu pilih

chromosome ke-k sebagai induk dengan syarat C[k-1] < R < C[k]. Kita putar roulete

wheel sebanyak jumlah populasi yaitu 6 kali (bangkitkan bilangan acak R) dan

pada tiap putaran, kita pilih satu chromosome untuk populasi baru. Misal:

R[1] = 0.201

R[2] = 0.284

R[3] = 0.009

R[4] = 0.822

R[5] = 0.398

R[6] = 0.501

Angka acak pertama R[1] adalah lebih besar dari C[1] dan lebih kecil daripada C[2]

maka pilih chromosome[2] sebagai chromosome pada populasi baru, dari bilangan

acak yang telah dibangkitkan diatas maka populasi chromosome baru hasil proses

seleksi adalah:

chromosome[1] = chromosome[2]






Chromosome baru hasil proses seleksi:


48

chromosome[1] = [02;01;08;03]

chromosome[2] = [02;01;08;03]

chromosome[3] = [12;05;03;08]

chromosome[4] = [01;04;03;09]

chromosome[5] = [02;01;08;03]

chromosome[6] = [10;04;03;04]

5. Crossover

Setelah proses seleksi maka proses selanjutnya adalah proses crossover. Metode

yang digunakan salah satunya adalah one-cut point, yaitu memilih secara acak satu

posisi dalam chromosome induk kemudian saling menukar gen. Chromosome yang

dijadikan induk dipilih secara acak dan jumlah chromosome yang mengalami

crossover dipengaruhi oleh parameter crossover_rate ( ρc ).

Pseudo-code untuk proses crossover adalah sebagai berikut:

begin

k← 0;

while(k<populasi) do

R[k] ← random(0-1);

if (R[k] < ρc ) then

select Chromosome[k] as parent;

end;

k = k + 1;

end;

end;

Misal kita tentukan crossover probability adalah sebesar 25%, maka diharapkan

dalam satu generasi ada 50% Chromosome (3 chromosome) dari satu generasi

mengalami proses crossover. Prosesnya adalah sebagai berikut:

Pertama kita bangkitkan bilangan acak R sebanyak jumlah populasi

R[1] = 0.191

R[2] = 0.259

R[3] = 0.760

R[4] = 0.006

R[5] = 0.159

R[6] = 0.340

Maka Chromosome ke k akan dipilih sebagai induk jika R[k] < ρc, dari bilangan

acak R diatas maka yang dijadikan induk adalah chromosome[1],

chromosome[4] dan chromosome[5].

Setelah melakukan pemilihan induk proses selanjutnya adalah menentukan posisi

crossover. Ini dilakukan dengan cara membangkitkan bilangan acak dengan


49

batasan 1 sampai (panjang chromosome-1), dalam kasus ini bilangan acak yang

dibangkitkan adalah 1 – 3. Misalkan didapatkan posisi crossover adalah 1 maka

chromosome induk akan dipotong mulai gen ke 1 kemudian potongan gen

tersebut saling ditukarkan antar induk.

chromosome[1] >< chromosome[4]



Posisi cut-point crossover dipilih menggunakan bilangan acak 1-3 sebanyak jumlah

crossover yang terjadi, misal

C[1] = 1

C[2] = 1

C[3] = 2

offspring[1] = chromosome[1] >< chromosome[4]

= [02;01;08;03] >< [01;04;03;09]

= [02;04;03;09]

offspring[4] = Chromosome[4] >< Chromosome[5]

= [01;04;03;09] >< [02;01;08;03]

= [01;01;08;03]

offspring[5] = Chromosome[5] >< Chromosome[1]

= [02;01;08;03] >< [02;01;08;03]

= [02;01;08;03]

Dengan demikian populasi Chromosome setelah mengalami proses crossover

menjadi:

chromosome[1] = [02;04;03;09]

chromosome[2] = [02;01;08;03]

chromosome[3] = [12;05;03;08]

chromosome[4] = [01;01;08;03]

chromosome[5] = [02;01;08;03]

chromosome[6] = [10;04;03;04]

6. Mutasi

Jumlah chromosome yang mengalami mutasi dalam satu populasi ditentukan oleh

parameter mutation_rate. Proses mutasi dilakukan dengan cara mengganti satu

gen yang terpilih secara acak dengan suatu nilai baru yang didapat secara acak.

Prosesnya adalah sebagai berikut. Pertama kita hitung dahulu panjang total gen

yang ada dalam satu populasi. Dalam kasus ini panjang total gen adalah total_gen

= (jumlah gen dalam chromosome) * jumlah populasi

= 4 * 6

= 24


50

Untuk memilih posisi gen yang mengalami mutasi dilakukan dengan cara

membangkitkan bilangan integer acak antara 1 sampai total_gen, yaitu 1 sampai

24. Jika bilangan acak yang kita bangkitkan lebih kecil daripada variabel

mutation_rate (ρm) maka pilih posisi tersebut sebagai sub-chromosome yang

mengalami mutasi. Misal ρm kita tentukan 10% maka diharapkan ada 10% dari

total_gen yang mengalami populasi:

jumlah mutasi = 0.1 * 24

= 2.4

= 2

Misalkan setelah kita bangkitkan bilangan acak terpilih posisi gen 12 dan 18 yang

mengalami mutasi. Dengan demikian yang akan mengalami mutasi adalah

chromosome ke-3 gen nomor 4 dan Chromosome ke-5 gen nomor 2. Maka nilai

gen pada posisi tersebut kita ganti dengan bilangan acak 0-30.

Misalkan bilangan acak yang terbangkitkan adalah 2 dan 5. Maka populasi

chromosome setelah mengalami proses mutasi adalah:

chromosome[1] = [02;04;03;09]

chromosome[2] = [02;01;08;03]

chromosome[3] = [12;05;03;02]

chromosome[4] = [01;01;08;03]

chromosome[5] = [02;05;08;03]

chromosome[6] = [10;04;03;04]

Setelah proses mutasi maka kita telah menyelesaikan satu iterasi dalam algoritma

genetika atau disebut dengan satu generasi. Maka fungsi_objective setelah satu

generasi adalah:

chromosome[1] = [02;04;03;09]

fungsi_objektif[1] = Abs(( 2 + 2*4 + 3*3 + 4*9 ) - 30)

= Abs(( 2 + 8 + 9 + 36 ) - 30)

= Abs( 55 - 30)

= 25

chromosome[2] = [02;01;08;03]


= Abs(( 2 + 2 + 24 + 12 ) - 30)

= Abs(40 - 30)

= 10

chromosome[3] = [12;05;03;02]


= Abs(( 12 + 10 + 9 + 8 ) - 30)


51

= Abs(39 - 30)

= 9

chromosome[4] = [01;01;08;03]


= Abs(( 1 + 2 + 24 + 12 ) - 30)

= Abs(39 - 30)

= 9

chromosome[5] = [02;05;08;03]


= Abs(( 2 + 10 + 24 + 12 ) - 30)

= Abs(48 - 30)

= 18

chromosome[6] = [10;04;03;04]


= Abs(( 10 + 8 + 9 + 16 ) - 30)

= Abs(43 - 30)

= 13

Rata-rata fungsi objektif setelah satu generasi adalah:

rata-rata = ( 25 + 10 + 9 + 9 + 18 + 13) / 6

= 84 / 6

= 14.0

Dapat dilihat dari hasil perhitungan fungsi objektif diatas bahwa setelah satu

generasi, nilai hasil rata-rata fungsi_objektif lebih menurun dibandingkan hasil

fungsi_objektif pada saat sebelum mengalami seleksi, crossover dan mutasi. Hal ini

menunjukkan bahwa chromosome atau solusi yang dihasilkan setelah satu

generasi lebih baik dibandingkan generasi sebelumnya. Maka pada generasi

selanjutnya chromosome-chromosome yang baru adalah:

chromosome[1] = [02;04;03;09]

chromosome[2] = [02;01;08;03]

chromosome[3] = [12;05;03;02]

chromosome[4] = [01;01;08;03]

chromosome[5] = [02;05;08;03]

chromosome[6] = [10;04;03;04]


52

Chromosome-chromosome ini akan mengalami proses yang sama seperti generasi

sebelumnya yaitu proses evaluasi, seleksi, crossover dan mutasi yang kemudian

akan menghasilkan chromosome-chromosome baru untuk generasi yang

selanjutnya. Proses ini akan berulang sampai sejumlah generasi yang telah

ditetapkan sebelumnya.

Setelah 50 generasi didapatkan chromosome yang terbaik adalah:

Chromosome = [07;05;03;01]

Jika didekode maka:

a=7 ; b=5 ; c=3 ; d=1

Jika dihitung terhadap persamaan f = a+2b+3c+4d:

7 + (2*5) + (3*3) + (4*1) = 30

Penyilangan atau Crossover

Sebuah kromosom yang mengarah pada solusi yang bagus bisa diperoleh dari proses

memindah-silangkan dua buah kromosom. Penyilangan dua buah kromosom dimaksud

un-tuk menghasilkan kromosom anak atau “offspring”. Kromosom anak yang terbentuk

akan mewarisi sebagian sifat kromosom induknya. Pada crossover ada satu parameter

yang sangat penting yaitu peluang crossover “pc”.

Contoh Proses Penyilangan.

Jika solusi yang dicari adalah X1 = 0 dan X2 = 0, maka kromosom Anak 1 memiliki nilai

finess tinggi dan menuju pada solusi yang dicari

Mutasi

Pada mutasi ada satu parameter penting yaitu peluang (probabilitas) mutasi atau

“pmut” yang menunjukkan prosentase jumlah total gen pada populasi yang akan


53

mengalami mutasi. Untuk semua gen yang ada, jika bilangan ran-dom yang dibangkitkan

kurang dari probabilitas mutasi “pmut” yang ditentukan, maka ubah gen tersebut

menjadi nilai kebalikannya. Biasanya “pmut” diset sebagai 1/n, “n” adalah jumlah gen

dalam kromosom. Dengan “pmut” sebesar ini berarti mutasi hanya terjadi pada 1 gen

saja.

Contoh Proses Mutasi.

Bilangan random yang dihasilkan lebih kecil dari probabilitas mutasi pmu terjadi pada

gen g10 sehingga gen g10 berubah dari 1 menjadi 0

Membentuk Individu Baru

Anak hasil perkawinan silang dan mutasi menjadi generasi baru untuk dilakukan proses

regenerasi . Pada generasi berikutnya, individu terbaik (nilai fitness terbesar) dapat

dipertahankan dengan proses elitism

C. Jaringan Syaraf Tiruan

Berawal dari sistem mesin Von Neumann, sistem komputer pada saat ini telah

berkembang pesat. Jaringan syaraf tiruan (JST) terjemahan dari Artificial Neural

Network, merupakan suatu model dari sistem syaraf biologis yang disederhanakan

sebagai suatu alternatif sistem komputasi. (Penelitian Jaringan Syaraf Tiruan,1993).

Meskipun kecepatan proses yang telah dicapai komputer dewasa ini lebih cepat jika


54

dibandingkan dengan proses yang dilakukan otak manusia, komputer masih belum

bisa menandingi universilitas kemampuan pada otak manusia.

Struktur sel syaraf biologis

Sel syaraf biologis atau disebut juga Neuron memiliki tiga komponen penyusun yang

saling bekerja sama untuk mengolah sinyal-sinyal informasi. Tiga komponen tersebut

adalah dendirt, soma atau badan sel dan axon seperti tampak pada gambar 1.

Dendrit merupakan serabut saraf yang bercabang-cabang pendek dan berjumlah lebih

dari satu ini bertugas menerima sinyal dari neuron lain. Sinyal listrik ini dilewatkan

melalui celah sinapsis (sianapsis gap) yang pada perjalanan biologisnya terjadi proses

kimiawi dengan penskalaan frekuensi sinyal, pada jaringan syaraf tiruan proses ini

disebut pembentukan bobot. Sinyal yang diterima diolah oleh soma dan kemudian

dijumlahkan.

Gambar 1. Struktur Sel Syaraf Biologis

Untuk mengirimkan informasi ke sel lain, sinyal dilewatkan melalui axon yang

merupakan serabut syaraf tunggal dan pada ujungnya bercabang-cabang.

Selanjutnya sinyal akan melalui celah sinapsis dan disampaikan ke soma lain oleh

dendrit neuron tersebut. Sehingga dengan terintegrasi dan terkoneksinya neuron

satu dengan yang lain akan dapat melaksanakan aktifitas secara teratur sesuai

kebutuhan.

Struktur jaringan saraf tiruan

JST disusun oleh elemen – elemen pemroses yang berada pada lapisan-lapisan yang

berhubungan dan diberi bobot. Dengan serangkaian inputan diluar sistem yang

diberikan kepadanya jaringan ini dapat memodifikasi bobot yang akan

dihasilkannya, sehingga akan menghasilkan output yang konsisten sesuai dengan

input yang diberian kepadanya. Setiap elemen pemroses melaksanakan operasi

matematika yang sudah ditentukan dan menghasilkan (hanya) sebuah harga


55

keluaran dari satu ataupun banyak masukan. Struktur jaringan akan ditunjukkan

seperti pada gambar berikut ini :

Gambar 2. Model tiruan neuron

Sebuah pemodelan neuron memiliki masukan Xp sebanyak p, yang berasal dari sel

lain atau dari inputan luar (bukan dari neuron). Selanjutnya setiap inputan diberi

pembobot Wkp. Masing – masing inputan Xp akan dikalikan dengan pembobot Wk

yang berkesesuaian. Untuk semua hasil perkalian akan dijumlahkan sebagaimana

pada persamaan dibawah ini :

(1)

dan hasil persamaan tersebut akan menjadi masukan bagi fungsi aktivasi untuk

mendapatkan tingkat derajat sinyal keluaran pada neuron, dimana terdapat

bermacam-macam jenis fungsi aktivasi. Untuk jenis fungsi sigmoid dapat

dideskripsikan dengan persamaan :

(2)

dengan grafik yang ditunjukkan sebagai berikut :

Gambar 3. Grafik fungsi sigmoid

Pada umumnya sinyal fungsi aktivasi yang dikeluarkan tiap neuron berbeda, hal ini

dikarenakan berbedanya nilai bobot yang diterima tiap neuron berbeda.

http://creasoft.files.wordpress.com/2008/04/nn3.jpg

http://creasoft.files.wordpress.com/2008/04/nn4.jpg


56

Pemodelan jaringan pada syaraf tiruan sering dikategorikan menjadi tiga yaitu :

Single layer, multi layer dan competitve layer. Namun pada pembahasan kali ini hanya

akan dibahas single layer dan multi layer, karena mengingat kaidah pelatihannya

menggunakan algoritma backpropagation. Secara umum , tiap unit pada lapisan

(Layer) yang sama atau dapat kita sebut neuron mempunyai tingkah laku yang sama

untuk pemrosesan sinyal data. Hanya hal terpenting yang perlu diperhatikan adalah

penentuan penggunaan jenis fungsi aktifasi pada masing-masing unit pada lapisan

tersebut dan pola koneksi pembobot antar lapisan. Namun biasanya unit pada lapisan

yang sama mempunyai jenis fungsi aktifasi yang sama dan pola koneksi pembobot

yang sama pula.

Untuk pemilihan jumlah layer bukan berarti pemilihan layer untuk neuron, namun

pemilihan layer untuk penghubung jalur pembobot antar neuron. Jadi variabel

terpenting untuk pengenalan pola adalah pembobotnya.

Faktor Keberhasilan Jaringan Syaraf Tiruan

Jaringan Syaraf Tiruan mengalami “booming” dan diminati beberapa tahun

terakhir ini, dan sangat sukses digunakan untuk memecahkan berbagai masaalah

dalam berbagai disiplin ilmu seperti : bidang finansial, kedokteran, teknik, geologi

dan fisika. Lebih jauh lagi, bahwa sesuatu masaalah dengan menggunakan

Jaringan Syaraf Tiruan dapat diprediksi, dikelompokkan dan dikontrol.

Ada beberapa faktor yang mendukung keberhasilan tersebut antara lain :

Handal. Jaringan Syaraf Tiruan adalah teknik pemodelan yang sangat

memuaskan yang dapat membuat model suatu fungsi yang sangat kompleks.

Khususnya Jaringan Syaraf Tiruan nonlinear. Sejak beberapa tahun, model

linear umumnya digunakan dimana model linear dikenal dengan strategi

optimasi. Jaringan Syaraf Tiruan juga menggunakan model nonlinear dengan

berbagai variabel.

Mudah digunakan. Jaringan Syaraf Tiruan dipelajari dengan contoh.

Pengguna Jaringan Syaraf Tiruan mengumpulkan data dan melakukan

pembelajaran algoritma untuk mempelajari secara otomatis struktur data,

sehingga pengguna tidak memerlukan pengetahuan khusus mengenai bagaimana

memilih dan mempersiapkan data, bagaimana memilih Jaringan Syaraf Tiruan

yang tepat, bagaimana membaca hasil, tingkatan pengetahuan yang diperlukan

untuk keberhasilan Menggunakan Jaringan Syaraf Tiruan tidak lebih dari

pemecahan masalah yang menggunakan metode statistik nonlinear yang telah

dikenal.

Aplikasi Jaringan Syaraf Tiruan


57

Jaringan Syaraf Tiruan mampu menggambarkan setiap situasi adanya sebuah

hubungan antara variabel predictor (independents, inputs) dan variabel predicted

(dependents, outputs), ketika hubungan tersebut sangat kompleks dan tidak

mudah untuk menjelaskan kedalam istilah yang umum dari “correlations” atau

“differences between groups”.

Kegunaan

Jaringan saraf tiruan pada umumnya digunakan untuk tugas atau pekerjaan yang

kurang praktis jika dikerjakan secara manual.

Kegunaan Dalam Kehidupan Nyata

Perkiraan Fungsi, atau Analisis Regresi, termasuk prediksi time series dan

modeling.

Klasifikasi, termasuk pengenalan pola dan pengenalan urutan, serta pengambil

keputusan dalam pengurutan.

Pengolahan data, termasuk penyaringan, pengelompokan, dan kompresi.

Robotik

Kesimpulan

Jaringan Syaraf Tiruan mulai dilirik banyak kalangan karena mempunyai banyak

kelebihan dibandingkan system konvensional. Jaringan Syaraf Tiruan mewakili

pikiran manusia untuk mendekatkan diri dengan komputer, maksudnya Jaringan

Syaraf Tiruan dirancang agar komputer dapat bekerja seperti/layaknya otak

manusia. Berikut ini beberapa keunggulan dari Jaringan Syaraf Tiruan adalah :

Adaptive learning: Suatu kemampuan untuk melakukan suatu kegiatan

yang didasarkan atas data yang diberikan pada saat pembelajaran atau

dari pengalaman sebelumnya.

Self-Organisation: Dapat membuat organisasi sendiri atau me-

representasikan informasi yang didapat pada saat pembelajaran.

Real Time Operation: Dapat menghasilkan perhitungan parallel dan

dengan device hardware yang khusus yang dibuat akan memberikan

keuntungan dengan adanya kemampuan tersebut.

Fault Tolerance melalui Redundant Information Coding: Kerusakan pada

bagian tertentu dari jaringan akan mengakibatkan penurunan

kemampuan.

Beberapa jaringan mempunyai kemampuan untuk menahan kerusakan

besar pada jaringan.

Kelebihan Jaringan Syaraf Tiruan terletak pada kemampuan belajar yang

dimilikinya. Dengan kemampuan tersebut pengguna tidak perlu

merumuskan kaidah atau fungsinya. Jaringan Syaraf Tiruan akan


58

belajar mencari sendiri kaidah atau fungsi tersebut. Dengan demikian

Jaringan Syaraf Tiruan mampu digunakan untuk menyelesaikan masalah

yang rumit dan atau masalah yang terdapat kaidah atau fungsi yang tidak

diketahui.

Kemampuan Jaringan Syaraf Tiruan dalam menyelesaikan masalah yang

rumit telah dibuktikan dalam berbagai macam penelitian.


59

DAFTAR PUSTAKA

Ilmukomputer.com

http://id.wikipedia.org

http://eprints.undip.ac.id/2226/1/1_Sarwadi_-_Anjar_Krismi.pdf

Membangun Jaringan Syaraf Tiruan, Sri Kusumadewi, 2004, Graha Ilmu,

Yogyakarta

Neural Network by Nikolay Nikolaef

http://homepages.gold .ac.uk/nikolaef/cis311.html.course_outline_for_fall_2004

http://id.wikipedia.org/

http://eprints.undip.ac.id/2226/1/1_Sarwadi_-_Anjar_Krismi.pdf

http://homepages.gold/

Sukses Beralgoritma

Documents