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
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
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
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 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 Kromosom B
10011001 00010001
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 Kromosom B
81675234 81243567
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 Kromosom B
1.89 2.34 1.68 ABBAADO
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.
10 Tabel 2.4 Contoh kromosom dengan representasi pohon Kromosom Z
(*(-(AB))(+(*(CD))(/(EF))))
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
11 (seperti pada TSP), maka fungsi fitness dan fungsi evaluasi akan berbanding terbalik. Sebagai contoh: 5
Mencari nilai global minimum dari fungsi
∑ int( x ) . Dimana 0 < xi < 5.12 dan int(x) i =1
i
adalah pembulatan kebawah. 5
Fungsi evaluasi untuk fungsi diatas sama dengan fungsi Feval = ∑ int( xi ) . Namun, ada i =1
banyak cara untuk menghitung fungsi fitness, salah satu diantaranya F fitness = 1.5 ( − Feval ) . Dengan demikian, jika x adalah [5, 5, 5, 5, 5], maka Feval = 25 , dan F fitness = 0,0004
dan jika x adalah [1, 1, 1, 1, 1], maka Feval = 5 , dan F fitness = 0,1317 . 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 individuindividu 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.
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 = 2x
2.
Hanya terpilih 1 individu pemenang dari k 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.
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 : Induk1 : 0 1 1 1 0 | 0 1 0 1 1 1 0 Induk2 : 1 1 0 1 0 | 0 0 0 1 1 0 1 Posisi penyilangan yang terpilih : misalkan 5 Setelah penyilangan ,diperoleh kromosom-kromosom baru : Anak1 : 0 1 1 1 0 | 0 0 0 1 1 0 1 Anak2 : 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
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 (k=1,2,…,N-1; i=1,2,…,m) dengan N i
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 : Induk1 : 0 1 1 1 0 0 1 0 1 1 1 0 Induk2 : 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 : Anak1 : 0 1 | 0 1 0 0 | 1 0 1 1 | 0 1 Anak2 : 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
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. Anak1 akan dihasilkan dari induk1 jika bit mask bernilai 1, atau sebaliknya, Anak1 akan dihasilkan dari induk2 jika bit mask bernilai 0. Sedangkan anak2 dihasilkan dari kebalikan mask. Misalkan ada 2 kromosom dengan panjang 12 : Induk1 : 0 1 1 1 0 0 1 0 1 1 1 0 Induk2 : 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 : Anak1 : 0 1 0 1 0 0 0 0 1 1 0 0 Anak2 : 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 : Induk1 : ( 1 2 3 | 4 5 6 7 | 8 9 ) Induk2 : ( 4 5 3 | 1 8 7 6 | 9 2 ) Anak1 : ( x x x | 1 8 7 6 | x x ) Anak2 : ( x x x | 4 5 6 7 | x x )
16 dari sini diperoleh pemetaan : 1-4, 8-5, 7-6, 6-7. Kemudian sisa gen di Induk1 di-copy ke Anak1 dengan menggunakan pemetaan tersebut. Anak1 : ( 1-4 2 3 | 1 8 7 6 | 8-5 9 ) Anak1 : ( 4 2 3 | 1 8 7 6 | 5 9 ) Hal serupa juga dilakukan untuk Anak2 : Anak2 : ( 4-1 5-8 3 | 4 5 6 7 | 9 2 ) Anak2 : ( 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 : Induk1 : ( 1 2 3 | 4 5 6 7 | 8 9 ) Induk2 : ( 4 5 3 | 1 8 7 6 | 9 2 ) Anak1 : ( x x x | 4 5 6 7 | x x ) Anak2 : ( x x x | 1 8 7 6 | x x ) Kemudian sisa gen di Induk2 di-copy ke Anak1 mulai dari urutan akhir : Anak1 : ( x x x | 4 5 6 7 | 9 2 ) Anak1 : ( 3 1 8 | 4 5 6 7 | 9 2 )
17 Hal serupa juga dilakukan untuk Anak2 : Anak2 : ( x x x | 1 8 7 6 | 9 2 ) Anak2 : ( 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
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 :
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
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 pencarian heuristic 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 diimplementasikan 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
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 jenisjenis memori yang dapat digunakan dalam tabu search, antara lain recency-based,
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.
1 2 3 4 5 6
1 0 0 0 0 0 0
2 0 0 0 0 0 0
3 0 0 0 0 0 0
4 0 0 0 0 0 0
5 0 0 0 0 0 0
6 0 0 0 0 0 0
1 2 3 4 5 6
1 0 0 0 0 0 0
2 0 0 0 0 0 0
3 0 0 0 0 0 5
4 0 0 0 0 0 0
5 0 0 0 0 0 0
6 0 0 5 0 0 0
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
23
1 2 3 4 5 6
1 0 3 0 0 0 0
2 3 0 0 4 1 0
3 0 0 0 2 0 5
4 0 4 2 0 0 0
5 0 1 0 0 0 0
6 0 0 5 0 0 0
1 2 3 4 5 6
1 0 2 0 0 0 0
2 2 0 0 0 3 0
3 0 0 0 0 2 4
4 0 3 2 0 0 0
5 0 0 0 0 0 5
6 0 0 5 4 5 0
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.
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
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.
Memberikan pencegahan 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.
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
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.
28 Definisi Kebutuhan
Merancang Perangkat Lunak dan Sistem Implementasi dan Testing Unit Integrasi dan Testing Sistem Penggunaan dan Perawatan 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
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 O(1) O(log * n) O(log n) O([log n]c) O(n) O(n log n) O(n2) O(nc), c>1 O(cn) O(n!)
Name Constant Iterative logarithmic Logarithmic Polylogarithmic Linear Linearithmic, loglinear, quasilinear or supralinear Quadratic Polynomial (algebraic) Exponential (geometric) Factorial (combinatorial)
