8/18/2019 2008-2-00440-MTIF bab 2

1/26

BAB 2

LANDASAN TEORI

 2.1 

Traveling Salesman Problem

2.1.1  Definisi Traveling Salesman Problem 

TSP merupakan suatu permasalahan dimana seorang salesman harus melewati

sejumlah kota tepat satu kali dan kembali ke kota awal, yang perlu dicari adalah rute

terpendek bagi salesman tersebut.

Biasanya permasalahan ini ditampilkan dalam bentuk graph. Pada sebuah

weighted graph, kota direpresentasikan sebagai verteks, dan jalurnya direprentasikan

sebagai edge.  Untuk jarak atau biaya dari suatu node ke node yang lain

direpresentasikan sebagai weight .

Gambar 2.1 - Weighted graph

8/18/2019 2008-2-00440-MTIF bab 2

2/26

  5

2.1.2  Kompleksitas Masalah

Solusi langsung dari TSP adalah dengan menggunakan metode brute force, yaitu

dengan mencoba semua kemungkinan yang ada (permutasi antara tiap kota). Metode ini

akan menghasilkan hasil yang optimal, namun metode ini memiliki kompleksitas yang

sangat tinggi yaitu O(n!). Dimana n adalah jumlah kota yang ingin ditempuh.

2.1.3  Metode Penyelesaian TSP 

Metode penyelesaian TSP dibagi menjadi dua bagian, yaitu metode eksak dan

metode heuritsik. Metode eksak baik digunakan jika jumlah kota sedikit, karena metode

ini bekerja agak lambat. Jika jumlah kota banyak, lebih baik menggunakan metode

heuristik karena metode ini bekerja dengan sangat cepat. Walaupun hasilnya belum

tentu yang optimal, tetapi hasilnya kebanyakan mendekati optimal.

2.2  Algoritma Genetik

Algoritma genetik merupakan algoritma pencarian yang berdasarkan pada cara

kerja seleksi alam dan ilmu genetik (Goldberg, 1989, p1). Algoritma genetik pertama

kali dikembangkan oleh John Holland dari Universitas Michigan pada tahun 1975. John

Holland mengatakan bahwa setiap masalah yang berbentuk adaptasi (alami maupun

 buatan) dapat diformulasikan dalam terminologi genetika. Algoritma genetik adalah

simulasi dari proses evolusi Darwin dan operasi genetika atas kromosom.

Algoritma genetik mengimplementasikan bentuk yang ampuh dari hill climbing 

yang memelihara banyak solusi, membuang solusi yang tidak menjanjikan dan

meningkatkan solusi-solusi yang baik. Gambar 2.2 menunjukkan sejumlah solusi yang

8/18/2019 2008-2-00440-MTIF bab 2

3/26

  6

 bergerak menuju titik-titik yang optimal dalam ruang pencarian. Pada gambar ini axis

horisontal menunjukkan titik-titik yang mungkin menjadi solusi, sementara axis vertical

menunjukkan kualitas dari solusi tersebut. Pada awalnya solusi tersebar pada ruang dari

solusi-solusi yang mungkin. Setelah beberapa generasi, solusi-solusi tersebut cenderung

 bergerak menuju ke area yang memiliki kualitas solusi yang lebih tinggi (Luger, 2002,

 p479). Algoritma genetik tidak secara serta merta langsung membuang solusi yang

 buruk, namun lewat operator genetik, bahkan solusi yang lemah pun bisa terus

memberikan kontribusi terhadap kandidat solusi yang akan datang.

Gambar 2.2 Algoritma genetik divisualisasikan sebagai paralel hill climbing

Pada algoritma genetik, teknik pencarian dilakukan atas sejumlah solusi yang

mungkin yang dikenal dengan istilah populasi. Individu yang terdapat dalam satu

 populasi disebut dengan istilah kromosom. Populasi awal dibangun secara acak,

sedangkan populasi berikutnya merupakan hasil evolusi kromosom-kromosom melalui

iterasi yang disebut dengan istilah generasi. Pada setiap generasi, kromosom akan

melalui proses evaluasi dengan menggunakan alat ukur yang disebut dengan fungsi

8/18/2019 2008-2-00440-MTIF bab 2

4/26

  7

 fitness. Nilai  fitness  dari suatu kromosom akan menunjukkan kualitas kromosom

dalam populasi tersebut. Generasi berikutnya dikenal dengan istilah anak (offspring)

terbentuk dari gabungan dua kromosom generasi sekarang yang bertindak sebagai induk

( parent ) dengan menggunakan operator penyilangan (crossover ). Selain operator

 penyilangan, suatu kromosom dapat juga dimodifikasi dengan menggunakan operator

mutasi. Populasi generasi yang baru dibentuk dengan cara menyeleksi nilai  fitness dari

kromosom induk dan nilai  fitness  dari kromosom anak, serta menjaga agar ukuran

 populasi konstan. Setelah melalui beberapa generasi, maka algoritma ini akan

konvergen ke kromosom terbaik.

Secara umum, cara kerja dari algoritma genetik terdiri dari langkah-langkah

 berikut ini :

1.  Start  

Generate populasi yang terdiri dari n kromosom secara random.

2.  Fitness 

Evaluasi fitness f(x) dari setiap kromosom x dalam populasi.

3.   New population 

Ciptakan populasi baru dengan mengulangi langkah-langkah berikut sampai

 populasi baru lengkap.

a.  Selection 

Pilih dua kromosom parent dari populasi berdasarkan nilai fitness. Semakin baik

nilai fitness, semakin besar kesempatan untuk terpilih menjadi parent .

 b.  Crossover  

Crossover  kedua parent  yang terpilih untuk membentuk populasi baru.

8/18/2019 2008-2-00440-MTIF bab 2

5/26

  8

c.  Mutation 

Mutasi offspring pada tiap locus (posisi pada kromosom).

4.   Replace 

Gunakan populasi baru yang telah terbentuk untuk proses berikutnya.

5.  Test  

Jika kondisi perhentian pada perulangan dipenuhi, proses berhenti dan kembalikan

solusi terbaik pada populasi sekarang.

6.   Loop 

Kembali ke langkah 2.

2.2.1  Representasi Genetik dari Domain Solusi

Kromosom harus dapat merepresentasikan suatu solusi. Menurut Obitko (1998),

metode yang dapat digunakan untuk merepresentasikan kromosom adalah sebagai

 berikut :

1. 

Representasi biner (binary encoding)

Pada representasi biner, setiap kromosom hanya terdiri dari bit 1 dan 0.

Kelemahan dari representasi ini adalah untuk beberapa masalah menjadi tidak

alami dan perbaikan harus dilakukan setelah crossover  atau mutasi. Representasi

 biner ditunjukkan pada Tabel 2.1.

Tabel 2.1 Contoh kromosom dengan representasi biner

Kromosom A 1 0 0 1 1 0 0 1

Kromosom B 0 0 0 1 0 0 0 1

8/18/2019 2008-2-00440-MTIF bab 2

6/26

  9

2.  Representasi permutasi ( permutation encoding)

Pada representasi permutasi, kromosom merupakan string angka yang

merepresentasikan posisi dalam suatu urutan. Metode ini biasanya digunakan

untuk masalah pengurutan tugas seperti Travelling Salesman Problem  (TSP). 

Representasi permutasi ditunjukkan pada Tabel 2.2.

Tabel 2.2 Contoh kromosom dengan representasi permutasi

Kromosom A 8 1 6 7 5 2 3 4

Kromosom B 8 1 2 4 3 5 6 7

3. 

Representasi nilai (value encoding)

Pada representasi nilai, kromosom berisi urutan nilai-nilai. Nilai dapat berupa

angka, huruf, atau string. Metode ini biasanya digunakan untuk masalah khusus,

seperti menemukan bobot untuk neural network . Representasi nilai ditunjukkan

 pada Tabel 2.3.

Tabel 2.3 Contoh kromosom dengan representasi nilai

Kromosom A 1.89 2.34 1.68

Kromosom B A B B A A D O 

4.  Representasi pohon (tree encoding)

Pada representasi pohon, kromosom adalah tree  dari beberapa objek, seperti

 function atau command   dalam bahasa pemrograman. Representasi pohon

ditunjukkan pada Tabel 2.4.

8/18/2019 2008-2-00440-MTIF bab 2

7/26

  10

Tabel 2.4 Contoh kromosom dengan representasi pohon

Kromosom Z

( * ( - ( A B ) ) ( + ( * ( C D ) ) ( / ( E F ) ) ) )

2.2.2 

Inisialisasi

Ukuran populasi bergantung pada sifat dasar dari permasalahan, tetapi biasanya

terdiri dari ratusan hingga ribuan solusi yang mungkin. Setelah ukuran populasi

ditentukan, kemudian harus dilakukan inisialisasi terhadap kromosom yang terdapat

 pada populasi tersebut. Inisialisasi kromosom dilakukan secara acak, namun harus tetap

memperhatikan domain solusi dan kendala permasalahan yang ada.

2.2.3  Fungsi Evaluasi dan Fungsi Fitness 

Fungsi evaluasi digunakan untuk mengevaluasi nilai dari kromosom pada tiap

individu. Sedangkan fungsi  fitness  digunakan untuk mengukur seberapa baik solusi

dalam menyelesaikan TSP.

Jika masalah yang ingin dipecahkan adalah masalah optimisasi, dimana nilai

yang ingin dicari adalah nilai global maksimum, maka fungsi evaluasi dan fungsi fitness 

 berbanding lurus. Namun jika nilai yang ingin dicari adalah nilai global minimum

8/18/2019 2008-2-00440-MTIF bab 2

8/26

  11

(seperti pada TSP), maka fungsi  fitness dan fungsi evaluasi akan berbanding terbalik.

Sebagai contoh:

Mencari nilai global minimum dari fungsi ∑=

5

1

)int(i

i x . Dimana 0 <  xi < 5.12 dan int(x)

adalah pembulatan kebawah.

Fungsi evaluasi untuk fungsi diatas sama dengan fungsi   ∑=

=5

1

)int(i

ieval  xF  . Namun, ada

 banyak cara untuk menghitung fungsi  fitness, salah satu diantaranya )(5.1 evalF  fitnessF   −= .

Dengan demikian, jika x adalah [5, 5, 5, 5, 5], maka 25=evalF  , dan 0004,0= fitnessF   

dan jika x adalah [1, 1, 1, 1, 1], maka 5=evalF  , dan 1317,0= fitnessF  . Dari hasil fungsi

 fitness  diatas maka hasil yang terbaik adalah jika x adalah [1, 1, 1, 1, 1], karena

memiliki nilai fitness yang jauh lebih tinggi.

2.2.4  Seleksi

Seleksi bertujuan untuk memberikan kesempatan reproduksi yang lebih besar

 bagi anggota populasi yang paling fit. Seleksi akan menentukan individu-individu mana

saja yang akan dipilih untuk rekombinasi dan bagaimana anak terbentuk dari individu-

individu terpilih tersebut.

Berbagai metode seleksi dapat digunakan untuk menentukan  fitness  dari tiap

solusi dan memilih solusi yang terbaik. Kebanyakan fungsi dirancang sehingga bagian

kecil dari solusi yang kurang sesuai masih dapat terpilih. Hal ini dapat menjaga

keragaman populasi serta mencegah solusi yang prematur dan seragam.

8/18/2019 2008-2-00440-MTIF bab 2

9/26

  12

Ada beberapa metode seleksi, yaitu roulette-wheel selection, elitist selection, rank

selection, tournament selection, dan lain sebagainya. Salah satu metode seleksi yang

sesuai untuk penyelesaian TSP adalah tournament selection. Metode ini bekerja dengan

cara mengambil kelompok-kelompok individu yang diambil dari populasi, kemudian

setiap individu dalam kelompok saling berkompetisi, dan hanya satu individu dari setiap

kelompok yang akan dipilih untuk reproduksi. Langkah-langkah dari metode

tournament selection, yaitu sebagai berikut:

1.  Pilih k  individu secara acak dari populasi, dimana nilai k = 2 x 

2. 

Hanya terpilih 1 individu pemenang darik   individu yg terpilih. Cara pemilihan

individu ini bervariasi, yang akan penulis gunakan adalah membandingkan setiap

dua individu dengan probabilitas kemenangan p (sekitar 0.6-0.7) bagi individu yang

memiliki nilai  fitness lebih baik. Pemenang akan ditandingkan lagi sampai tinggal

satu pemenang yang akan dimasukkan ke dalam mating pool.

3.  Kembali ke langkah 1, sampai jumlah populasi baru terpenuhi.

Metode tournament  sangat dipengaruhi oleh ukuran dari sample k , semakin kecil

nilai k , semakin tinggi selection pressure-nya, sehingga individu yang memiliki  fitness 

rendah memiliki kemungkinan lebih kecil untuk terseleksi. Sebaliknya jika nilai k  besar,

maka individu yang memiliki fitness kecil memiliki ksempatan untuk terseleksi, namun

menyebabkan kinerja melambat.

2.2.5  Crossover

Crossover   / persilangan adalah proses pertukaran satu atau lebih gen antara

suatu kromosom dengan kromosom lain untuk menghasilkan kromosom anak.

8/18/2019 2008-2-00440-MTIF bab 2

10/26

  13

Kromosom anak yang terbentuk akan mewarisi sebagian sifat kromosom induknya.

Adapun jenis-jenis crossover  adalah sebagai berikut.

1.  One-point crossover  

Pada metode ini, posisi penyilangan k (k=1,2,…,N-1) dengan N adalah panjang

kromosom yang diseleksi secara random. Variabel-variabel ditukar antar kromosom

 pada titik tersebut untuk menghasilkan anak. One-point  crossover  ditunjukkan pada

Gambar 2.3. 

Gambar 2.3 One-point crossover  

Contoh :

Misalkan ada 2 kromosom dengan panjang 12 :

Induk 1  : 0 1 1 1 0 | 0 1 0 1 1 1 0

Induk 2  : 1 1 0 1 0 | 0 0 0 1 1 0 1

Posisi penyilangan yang terpilih : misalkan 5

Setelah penyilangan ,diperoleh kromosom-kromosom baru :

Anak 1  : 0 1 1 1 0 | 0 0 0 1 1 0 1

Anak 2  : 1 1 0 1 0 | 0 1 0 1 1 1 0

2.  Two-point crossover  

Pada metode ini, 2 posisi penyilangan diseleksi secara random, kedua posisi tersebut

8/18/2019 2008-2-00440-MTIF bab 2

11/26

  14

tidak boleh sama dan diurutkan naik. Variabel-variabel ditukar antar kromosom pada titik

tersebut untuk menghasilkan anak. Two-point crossover ditunjukkan pada Gambar 2.4.

Gambar 2.4 Two-point Crossover

3.   Multi-point crossover  

Pada metode ini, m posisi penyilangan k i(k=1,2,…,N-1; i=1,2,…,m) dengan N

adalah panjang kromosom yang diseleksi secara random dan tidak diperbolehkan

ada posisi yang sama serta diurutkan naik. Variabel-variabel ditukar antar

kromosom pada titik tersebut untuk menghasilkan anak.

Misalkan ada 2 kromosom dengan panjang 12 :

Induk 1  : 0 1 1 1 0 0 1 0 1 1 1 0

Induk 2  : 1 1 0 1 0 0 0 0 1 1 0 1

Posisi penyilangan yang terpilih : misalkan (m=3) : 2 6 10

Setelah penyilangan ,diperoleh kromosom-kromosom baru :

Anak 1  : 0 1 | 0 1 0 0 | 1 0 1 1 | 0 1

Anak 2  : 1 1 | 1 1 0 0 | 0 0 1 1 | 1 0

4. Uniform crossover  

Pada metode ini, setiap lokasi memiliki potensi sebagai tempat penyilangan.

Sebuah mask  penyilangan dibuat sepanjang panjang kromosom secara random yang

8/18/2019 2008-2-00440-MTIF bab 2

12/26

  15

menunjukkan bit-bit dalam mask  yang mana induk akan memberikan bit-bit yang

ada kepada anak. Induk mana yang akan menyumbangkan bit ke anak dipilih secara

random dengan probabilitas yang sama. Anak 1 akan dihasilkan dari induk 1  jika bit

mask  bernilai 1, atau sebaliknya, Anak 1 akan dihasilkan dari induk 2  jika bit mask  

 bernilai 0. Sedangkan anak 2 dihasilkan dari kebalikan mask .

Misalkan ada 2 kromosom dengan panjang 12 :

Induk 1  : 0 1 1 1 0 0 1 0 1 1 1 0

Induk 2  : 1 1 0 1 0 0 0 0 1 1 0 1

 Mask  bit

Sampel1  : 1 0 0 1 1 1 0 0 1 1 0 1

Sampel2  : 0 1 1 0 0 0 1 1 0 0 1 0

Setelah penyilangan ,diperoleh kromosom-kromosom baru :

Anak 1  : 0 1 0 1 0 0 0 0 1 1 0 0

Anak 2  : 1 1 1 1 0 0 1 0 1 1 1 1

5.  Permutation crossover

Pada metode ini, kromosom anak diperoleh dengan cara memilih sub-barisan suatu

tour  dari satu induk dengan tetap menjaga urutan dan posisi sejumlah kota yang

mungkin terhadap induk yang lainnya.

Misal :

Induk 1  : ( 1 2 3 | 4 5 6 7 | 8 9 )

Induk 2  : ( 4 5 3 | 1 8 7 6 | 9 2 )

Anak 1  : ( x x x | 1 8 7 6 | x x )

Anak 2  : ( x x x | 4 5 6 7 | x x )

8/18/2019 2008-2-00440-MTIF bab 2

13/26

  16

dari sini diperoleh pemetaan :

1-4, 8-5, 7-6, 6-7.

Kemudian sisa gen di Induk 1 di-copy ke Anak 1 dengan menggunakan

 pemetaan tersebut.

Anak 1  : ( 1-4 2 3 | 1 8 7 6 | 8-5 9 )

Anak 1  : ( 4 2 3 | 1 8 7 6 | 5 9 )

Hal serupa juga dilakukan untuk Anak 2 :

Anak 2  : ( 4-1 5-8 3 | 4 5 6 7 | 9 2 )

Anak 2  : ( 1 8 3 | 4 5 6 7 | 9 2 )

6.  Order crossover  

Pada metode ini, kromosom anak diperoleh dengan cara memilih sub-barisan suatu

tour  dari satu induk, kemudian sisanya disalin dari kromosom induk yang lainnya.

Bila elemen yang akan disalin sudah terdapat pada kromosom anak maka elemen

tersebut tidak disalin, dan dilanjutkan ke elemen berikutnya.

Misal :

Induk 1  : ( 1 2 3 | 4 5 6 7 | 8 9 )

Induk 2  : ( 4 5 3 | 1 8 7 6 | 9 2 )

Anak 1  : ( x x x | 4 5 6 7 | x x )

Anak 2  : ( x x x | 1 8 7 6 | x x )

Kemudian sisa gen di Induk2 di-copy ke Anak 1 mulai dari urutan akhir :

Anak 1  : ( x x x | 4 5 6 7 | 9 2 )

Anak 1  : ( 3 1 8 | 4 5 6 7 | 9 2 )

8/18/2019 2008-2-00440-MTIF bab 2

14/26

  17

Hal serupa juga dilakukan untuk Anak 2 :

Anak 2  : ( x x x | 1 8 7 6 | 9 2 )

Anak 2  : ( 3 4 5 | 1 8 7 6 | 9 2 )

2.2.6  Mutasi 

Mutasi adalah operator genetik yang mengubah satu atau lebih gen dalam suatu

kromosom dari keadaan awalnya. Mutasi berperan untuk menggantikan gen yang hilang

dari populasi akibat proses seleksi yang memungkinkan munculnya kembali gen yang

tidak muncul pada saat inisialisasi populasi. Mutasi merupakan bagian yang penting dari

 pencarian genetik yang dapat mencegah populasi berhenti pada solusi yang optimal

secara lokal.

Mutasi terjadi selama evolusi sesuai dengan peluang mutasi yang didefinisikan.

Sebaiknya peluang mutasi didefenisikan dengan nilai yang cukup rendah, misalnya 0.01,

karena peluang mutasi yang terlalu tinggi mengakibatkan pencarian berubah menjadi

 pencarian primitif secara acak.

Ada beberapa tipe mutasi menurut Fang (1994, p59), yaitu :

1. Mutasi random 

Mutasi random disebut juga mutasi gen. Pada mutasi random, gen yang mengalami

mutasi akan digantikan dengan gen lain dimana gen pengganti tersebut dipilih

secara acak.

2. Mutasi exchange 

Mutasi exchange  disebut juga mutasi swap. Pada mutasi exchange, secara acak

dipilih 2 gen yang akan mengalami mutasi, kemudian posisi kedua gen tersebut

8/18/2019 2008-2-00440-MTIF bab 2

15/26

  18

ditukar.

3. Smart mutation 

Smart mutation  dapat mempercepat evolusi karena mutasi terjadi pada gen yang

mempunyai nilai fitness terbesar atau  penalty  terbesar. Gen tersebut akan

digantikan dengan gen lain secara acak.

2.2.7  Elitisme

Tujuan elitisme adalah untuk menyimpan sedikit individu yang terbaik, agar

hasil di generasi berikutnya tetap bagus, atau bahkan lebih bagus. Individu yang

termasuk dalam golongan elit akan dijamin masuk ke generasi berikutnya tanpa perlu

melakukan persilangan dan mutasi. Elitisme sangatlah membantu meningkatkan hasil

dari algoritma genetik. Hal ini dikarenakan jika generasi berikutnya lebih buruk

daripada generasi sebelumnya, maka hasil yang didapatkan akan menjadi kurang

optimal.

Jumlah individu yang elit tidak boleh terlalu banyak, karena hasil yang dicapai

 juga akan menjadi tidak optimal yang disebabkan oleh kurangnya persaingan antara

individu. Umumnya nilai elitisme diset sekitar 1-2 individu atau 1% dari populasi.

2.2.8 Parameter-parameter Algoritma Genetik

Algoritma genetik dapat memiliki parameter-parameter dalam menjalankan

 prosesnya. Parameter-parameter tersebut akan mempengaruhi kinerja algoritma genetik

dalam proses pencarian solusi terbaik. Parameter-parameter yang dimaksud adalah

sebagai berikut :

8/18/2019 2008-2-00440-MTIF bab 2

16/26

  19

a.  Ukuran populasi dan generasi

Ukuran populasi menentukan jumlah kromosom dalam suatu populasi. Jika jumlah

kromosom sedikit, maka ruang pencarian kecil dan peluang untuk memperoleh solusi

 juga kecil. Sebaliknya, jika jumlah kromosom terlalu banyak, maka ruang pencarian

terlalu besar dan dibutuhkan waktu yang lebih lama untuk memperoleh solusi yang

diinginkan (Obitko, 1998).

Ukuran generasi berperan penting sebagai kondisi perhentian algoritma genetik.

Jumlah generasi haruslah cukup banyak sehingga individu-individu yang dihasilkan

 bagus, dan jangan terlalu berlebihan, karena selain memperlambat kinerja, komputer

akan menghabiskan waktu untuk menghitung jauh lebih lama dengan perubahan yang

sedikit (tidak sebanding dengan cost  untuk menghitung).

 b.  Selection rate

Selection rate menunjukkan jumlah kromosom dalam suatu populasi yang diseleksi.

Selection rate 0% berarti tidak ada kromosom yang diseleksi, sedangkan selection rate 

100% berarti semua kromosom pada populasi tersebut diseleksi. Selection rate  yang

rendah akan mengakibatkan proses pencarian berjalan lambat karena pencarian banyak

 berulang pada kromosom-kromosom yang bukan merupakan solusi. Sebaliknya,

selection rate yang tinggi akan mengakibatkan hilangnya kromosom-kromosom yang

 berpotensi besar menjadi solusi sehingga waktu pencarian akan meningkat.

c.   Mutation rate 

 Mutation rate  menentukan berapa banyak gen dalam kromosom yang akan

mengalami mutasi.  Mutation rate  0% berarti tidak ada gen yang mengalami mutasi,

sedangkan mutation rate  100% berarti semua gen dalam kromosom akan mengalami

8/18/2019 2008-2-00440-MTIF bab 2

17/26

  20

mutasi.  Mutation rate yang terlalu rendah akan mengakibatkan kromosom-kromosom

yang mungkin berpotensi menjadi solusi tidak pernah dicoba dan algoritma genetik

dapat terjebak pada lokal minimum. Sebaliknya, mutation rate yang terlalu tinggi akan

mengakibatkan algoritma genetik cenderung bekerja seperti random search  karena

algoritma tersebut tidak lagi mampu belajar dari sejarah pencariannya.

2.3  Algoritma Tabu Search 

Tabu search merupakan suatu pendekatan meta-heuristik  yang mendasari prosedur

 pencarianheuristic

  lokal yang digunakan untuk mencari kemungkinan ditemukannya

solusi lain di luar tingkat optimalitas lokal atau untuk mencari solusi yang (mendekati)

optimal.  Meta-heuristik   sendiri berarti suatu master   strategi yang mendasari dan

memodifikasi heuristik   lainnya untuk menghasilkan solusi / kesimpulan, selain dari

yang biasanya diterapkan pada penelitian untuk mendapatkan tingkat optimalitas.

(Glover dan Laguna , 1997, p17)

Tabu search  didasarkan pada kesimpulan bahwa penyelesaian masalah, untuk

memenuhi kualitas sebagai metode yang mempunyai kecerdasan, harus menggabungkan

adaptive memory dan responsive exploration. Kemampuan adaptive memory pada Tabu

search  memungkinkan untuk mengimplementasikan prosedur yang mampu untuk

mencari lingkup solusi secara efisien dan ekonomis.

Pentingnya penggunaan responsive exploration  pada Tabu search, baik yang di-

implementasikan secara determinan atau probabilitas, diperoleh dari pengandaian

 bahwa pemilihan strategi yang buruk dapat menghasilkan lebih banyak informasi

daripada sebuah pilihan baik yang diperoleh secara acak. Dalam sistem yang

8/18/2019 2008-2-00440-MTIF bab 2

18/26

  21

menggunakan memori, sebuah pilihan buruk yang diambil berdasarkan strategi dapat

menyediakan kesimpulan yang berguna tentang bagaimana strategi dapat diubah untuk

menjadi lebih baik.

 Responsive exploration menggabungkan prinsip dasar dari pencarian cerdas seperti

selalu berusaha mencari solusi terbaik selama mencari semua kemungkinan yang ada.

Tabu search selalu berusaha mencari cara yang baru dan lebih efisien dalam mengambil

keuntungan dari penggabungan mekanisme adaptive memory  dan mekanisme

responsive exploration.

2.3.1  Cara Kerja Algoritma Tabu Search 

Tabu search merupakan metode yang menggunakan memori untuk mengingat

langkah-langkah yang sudah diambil sebelumnya. Langkah-langkah sebelumnya

kemudian dianggap sebagai hal tabu yang tidak boleh dilakukan pada iterasi berikutnya.

Secara garis besar, tabu search bekerja sebagai berikut:

1. 

Inisialisasi solusi awal Vc secara acak.

2.  Cari solusi baru Vn di dalam neighbourhood  solusi Vc. 

3.  Mengganti Vc dengan Vn jika Vn tidak melanggar daftar tabu.

4.  Memperbaharui daftar tabu.

5.  Kembali ke langkah 2 sampai jumlah iterasi tercapai.

2.3.2  Memori

Memori merupakan ide utama dari algoritma tabu search. Ada beberapa jenis-

 jenis memori yang dapat digunakan dalam tabu search, antara lain recency-based,

8/18/2019 2008-2-00440-MTIF bab 2

19/26

  22

 frequency-based, influence-based   dan quality-based memory. Memori yang akan

digunakan oleh penulis adalah memori recency-based . Memori recency-based  bekerja

dengan cara menandai perubahan paling baru yang terjadi. Contoh berikut akan

memperjelas cara kerja memori ini.

Sebagai contoh, perhatikan masalah traveling salesman dengan menggunakan 6

kota. Solusi awal yang diberikan adalah (1,2,3,4,5,6). Setelah satu iterasi, solusi

 berikutnya menjadi (1,2,6,4,5,3). Dengan demikian memori dalam tabu search  sesuai

 pada gambar 2.5.

Gambar 2.5 Keadaan memori pada solusi awal (kiri) dan solusi baru (kanan)

Dengan keadaan memori yang sekarang maka kota 3 dan kota 6 tidak boleh

ditukar selama 5 iterasi. Angka 5 sendiri merupakan horizon memori yang nilainya

dapat ditentukan sendiri oleh user . Setelah 5 iterasi, kota 3 dan kota 6 dapat ditukar

kembali.

Contoh lain adalah sebagai berikut; pada TSP yang memiliki 6 kota, setelah 20

iterasi memiliki keadaan memori sebagai berikut

1 2 3 4 5 61 0 0 0 0 0 02 0 0 0 0 0 03 0 0 0 0 0 04 0 0 0 0 0 05 0 0 0 0 0 06 0 0 0 0 0 0

1 2 3 4 5 61 0 0 0 0 0 02 0 0 0 0 0 03 0 0 0 0 0 54 0 0 0 0 0 05 0 0 0 0 0 06 0 0 5 0 0 0

8/18/2019 2008-2-00440-MTIF bab 2

20/26

  23

 

Gambar 2.6 Keadaan memori pada solusi awal (kiri) dan solusi baru (kanan)

Pada gambar 2.6 dijelaskan bahwa kota 1 dan 2 tidak dapat ditukar, demikian

 juga untuk kota 2 dan 4, kota 4 dan 3, kota 5 dan 2 dan kota 6 dan 3. Dan ketika solusi

 baru ditemukan, jelaslah solusi baru menukar kota 5 dan kota 6. Hal ini dapat dilihat

dari nilai memori pada slot 5 dan 6, dimana nilai memori adalah 5, bukan 0. Solusi baru

ini juga memungkinkan kota 5 dan kota 2 untuk ditukarkan karena nilai di dalam

memori telah menjadi 0, bukan 1.

2.3.3   Aspiration Criterion 

Cara kerja memori sendiri terkadang terlalu keras. Mungkin saja solusi yang

sangat baik ada di dalam neighborhood  solusi sekarang namun karena isi dari memori

tidak memungkinkan solusi yang baru maka kita baru saja kehilangan solusi yang

sangat baik.

Untuk mengatasi hal ini, aspiration criterion  dapat digunakan. Hal ini mirip

dengan keadaan sehari-hari, dimana jika seseorang melihat kesempatan yang sangat

 baik, terkadang melupakan prinsip-prinsipnya. Jika solusi baru yang tabu merupakan

solusi yang sangatlah baik, maka tidak apa-apa jika kita melanggar prinsip tabu tersebut

dan menggunakan solusi baru yang lebih baik.

1 2 3 4 5 61 0 3 0 0 0 02 3 0 0 4 1 03 0 0 0 2 0 54 0 4 2 0 0 0

5 0 1 0 0 0 06 0 0 5 0 0 0

1 2 3 4 5 61 0 2 0 0 0 02 2 0 0 3 0 03 0 0 0 2 0 54 0 0 0 0 0 4

5 0 3 2 0 0 56 0 0 4 0 5 0

8/18/2019 2008-2-00440-MTIF bab 2

21/26

  24

2.4  Interaksi Manusia dan Komputer

Dalam Interaksi Manusia dan Komputer terdapat aturan mengenai perancangan

sebuah user interface  atau tampilan yang user friendly  (atau mudah digunakan oleh

 pengguna) yaitu Eight Golden Rules of User Interface.

2.4.1 Pengertian Interaksi Manusia dan Komputer

Interaksi Manusia dan Komputer (IMK) atau  Human-Computer Interaction

(HCI)  adalah disiplin ilmu yang berhubungan dengan perancangan, evaluasi, dan

implementasi sistem komputer interaktif untuk digunakan oleh manusia, serta studi

fenomena-fenomena besar yang berhubungan dengannya.

2.4.2  Eight Golden Rules of User Interface

Suatu sistem interaktif yang baik akan menghasilkan suatu rancangan yang baik

 pula, sehingga pemakai dapat menggunakan sistem interaktif tersebut dengan lancar.

Sebaliknya, sistem interaktif yang kurang baik akan menghasilkan rancangan yang

kurang baik pula, sehingga menyebabkan pemakai mendapatkan kesulitan dalam

menggunakannya karena interface yang tidak user friendly.

Untuk membuat suatu interface  dan yang user friendly, maka sebaiknya

menggunakan metode yang terdapat dalam Delapan Aturan Emas ( Eight Golden Rules),

menurut Shneiderman (1998, p74-75), yaitu sebagai berikut:

1.  Berusaha untuk selalu konsisten 

Penggunaan jenis font, warna, simbol, bentuk tombol harus tetaplah sama atau tidak

mengalami perubahan bila masih dalam konteks yang sama di seluruh bagian

8/18/2019 2008-2-00440-MTIF bab 2

22/26

  25

 program.

2.  Memungkinkan frequent users menggunakan shortcut.

Program menyediakan suatu tombol yang berfungsi untuk memasuki bagian yang

dituju secara langsung tanpa harus melalui bagian-bagian yang lainnya.

3.  Memberikan umpan balik yang informatif , sehingga tidak membingungkan

 pemakai.

4.  Merancang dialog yang memberikan penutupan (keadaan akhir), sehingga

 pemakai tahu kapan awal dan akhir dari suatu aksi.

5. 

Memberikanpencegahan kesalahan

dan penanganan kesalahan yang sederhana.

Sistem harus dapat mendeteksi kesalahan dan dapat memberikan jalan keluar untuk

mengatasi kesalahan tersebut.

6.  Memungkinkan pembalikan aksi yang mudah.

Kesalahan yang dapat terjadi dapat dikembalikan pada aksi sebelum kesalahan

terjadi. Dengan adanya rancangan seperti ini kegelisahan dan rasa takut membuat

kesalahan pada pengguna dapat diatasi.

7.  Mendukung pusat kendali internal (internal locus of control).

Memberikan kesan bahwa pengguna mempunyai kuasa penuh atas sistem tersebut.

Pengguna yang berpengalaman menginginkan kuasa penuh terhadap sistem yang

mereka gunakan dan mengharapkan sistem memberikan tanggapan atas aksi yang

dilakukannya.

8.  Mengurangi beban ingatan jangka pendek (short-term memory).

Dengan terbatasnya kemampuan manusia untuk mengingat, tampilan pada sistem

hendaklah mudah untuk diingat dan sederhana.

8/18/2019 2008-2-00440-MTIF bab 2

23/26

  26

2.5  Perangkat lunak

Menurut Pressman (2001, p6), perangkat lunak adalah :

1.  Instruksi – instruksi (program komputer) yang jika dijalankan akan

menyediakan fungsi yang diperlukan.

2.  Struktur data yang memungkinkan program untuk memanipulasi informasi.

3.  Dokumen yang menyatakan operasi dan kegunaan program.

2.5.1  Dasar Perancangan Perangkat Lunak

Menurut Mahyuzir (1991, p78), perancangan merupakan proses penerapan

 bermacam-macam tehnik dan prinsip dengan tujuan untuk mendefinisikan peralatan,

 proses atau system secara rinci. Perancangan dilakukan pada tahap awal pengembangan.

Tujuan perancangan adalah menghasilkan model yang akan dibuat.

Perancangan perangkat lunak mengalami perubahan jika didapatkan metode yang baru,

analisis yang baik dan penyusunan pengertian yang lebih luas.

2.5.2  Fase Pengembangan Perangkat Lunak

Model fase pengembangan perangkat lunak yang digunakan adalah Waterfall

Model. Adapun fase-fase yang ada pada Waterfall model ini antara lain :

1.  Analisis Kebutuhan dan definisi masalah

Pada fase ini, kita menganalis apa yang menjadi kebutuhan dan yang menjadi

tujuan dari membuat perangkat lunak ini.

2.  Merancang Sistem dan perangkat lunak

8/18/2019 2008-2-00440-MTIF bab 2

24/26

  27

Merancang sistem adalah membagi-bagi kebutuhan-kebutuhan tersebut pada

 perangkat keras dan perangkat lunak. Yang kemudian keduanya saling

 bersinkronisasi.

3. 

Implementasi dan unit testing

Pada fase ini, rancangan perangkat lunak direalisasikan menjadi sekumpulan

unit/modul-modul program. Unit testing berguna untuk mengecek apakah suatu unit

tersebut sesuai dengan spesifikasi dan kegunaan yang diharapkan.

4.  Integrasi dan Tes Sistem

Modul-modul program tersebut kemudian diintegrasikan satu sama lain menjadi

satu kesatuan sistem yang utuh dan mengecek system tersebut apakah sesuai

dengan kebutuhan yang diinginkan. Setelah selesai dengan testing program, sistem

tersebut dapat dilepas ke klien.

5.  Penggunaan dan perawatan

Biasanya fase ini adalah yang paling lama. Perawatan perangkat lunak meliputi

 perbaikan kesalahan yang tidak muncul pada tahan-tahap sebelumnya dalam

 pembuatan perangkat lunak, mengembangkan perangkat lunak yang sudah ada

ketika ada kebutuhan yang baru.

8/18/2019 2008-2-00440-MTIF bab 2

25/26

  28

 

Gambar 2.7  Waterfall Model

2.4  Notasi Big O

 Notasi Big O adalah notasi matematika yang digunakan untuk menggambarkan

tingkah laku asimtotik dari fungsi. Dalam dunia ilmu komputer ini berguna untuk

menganalisa kompleksitas dari suatu algoritma. 

Terdapat 2 jenis penggunaan notasi Big O, yaitu :

1.  Infinite asymptotics 

2.  Infinitesimal asymptotics

Perbedaan kedua jenis penggunaan notasi ini hanya pada aplikasi. Sebagai contoh, pada

infinite asymptotics dengan persamaan

T(n) = 2n2 -2n +2

Untuk n yang besar, pertumbuhan T(n) akan sebanding dengan n2  dan dengan

mengabaikan suku yang tidak mendominasi kita, maka kita tuliskan

Merancang Perangkat

Lunak dan Sistem

Integrasi danTestin Sistem

Implementasi danTestin Unit

Penggunaan danPerawatan

Definisi Kebutuhan

8/18/2019 2008-2-00440-MTIF bab 2

26/26

  29

T(n) = O(n2)

Pada infinitesimal asymptotics, Big O digunakan untuk menjelaskan kesalahan dalam

aproksimasi untuk sebuah fungsi matematika, sebagai contoh

Kesalahannya memiliki selisih

Berikut ini adalah daftar kelas fungsi yang umum dijumpai dalam menganalisa

algoritma. Semua ini diandaikan n mendekati tak terhingga. Urutan berdasarkan dari

kinerja yang tercepat ke yang terlambat.

Tabel 2.5 Daftar notasi Big O (Sumber: http://en.wikipedia.org/wiki/Big_Oh)

Notation Name

O(1) ConstantO(log * n)  Iterative logarithmicO(log n)  Logarithmic O([log n]c) PolylogarithmicO(n)  LinearO(n log n)  Linearithmic, loglinear, quasilinear or supralinearO(n2) QuadraticO(nc), c>1 Polynomial (algebraic)O(cn)  Exponential (geometric)O(n!) Factorial (combinatorial)