BAB II TINJAUAN PUSTAKA
2.1. Timetable Scheduling Timetablemenurut
Wren
(1996)
adalah
kejadian
tertentu
yang
membutuhkan tempat yang tidak secara langsung mengutarakan alokasi dari sumber, contohnya adalah timetable bus atau kereta api yang menunjukkan kapan kereta api atau bus berangkat dan rute perjalanan kereta api atau bus tersebut, tetapi tidak menunjukkan alokasi kendaraan maupun supir. Proses pengalokasian inilah yang dinamakan scheduling atau timetable scheduling. Timetable schedulingatau penjadwalan tersebut kemudian didefinisikan oleh Chu dan Fang (1999) sebagai perencanaan berbasis waktu dan combinational optimization yang diselesaikan dengan kerjasama antara pencarian dan heuristik, yang biasanya mengarah pada solusi yang memuaskan tetapi suboptimal.Terdapat banyak jenis problem penjadwalan dalam kehidupan sehari-hari, seperti ujian, perkuliahan, dan jadwal transportasi. Kemudian timetablescheduling didefinisikan kembali oleh Qarouni-Fard et al. (2007) sebagai pengalokasian satu set event ke dalam sejumlah ruangan dan timeslot dimana sejumlah batasan (constraints) harus dipenuhi. Banyak jenis problem penjadwalan yang ada dalam kehidupan sehari-hari, contohnya adalah penjadwalan matakuliah, ujian dan transportasi.Problem penjadwalan yang paling umum adalah University Course Timetabling Problem (UCTP) dan Exam Timetabling Problem (ETP).
7
8
Menurut Ho et al. (2008), problem penjadwalan biasanya berhadapan dengan bagaimana mendistribusikan resourcesecara efektif. Resourceini biasanya bersifat terbatas dan tidak ada dua pekerjaan (tasks) yang menggunakan resource yang sama dalam waktu yang sama. Dalam timetable scheduling,events harus diatur ke dalam waktu tertentu (timeslot) untuk memenuhi constraints yang ada.Burke et al. (1997) membagi constraint yang menjadi pertimbangan menjadi dua jenis, yaitu Hard Constraints yaitu batasan yang harus dipenuhi dalam timetable agar dapat digunakan (layak) dan Soft Constraints yaitubatasan yang diinginkan tapi tidak benar-benar diperlukan.
2.2. Sejarah Timetable Scheduling Timetableschedulingyang sebelumnya masih dilakukan secara manual, yaitu dengan menggunakan tenaga dan pikiran manusia, mulai berubah kearah penggunaan komputer.Perubahan ini dimulai ketika D. de Werra pada tahun 1985mulai memperkenalkan tentang timetabling, dalam penelitiannya tersebut de Werra masih menggunakan teknik graph dan networks.Walaupun pada akhirnya penelitian tersebut dapat menyelesaikan permasalahan examtimetabling problem maupun course timetabling problem dalam transaksi dengan skala kecil namun memiliki permasalahan dalam transaksi skala besar (Lai et al., 2006). Karena perkembangan transaksi timetablingyang terus meningkat menjadi skala
yang
besar,
penelitian-penelitianpada
timetablingini
jugaterusmeningkat.Penelitian timetabling tersebut sudah dikembangkan mulai
9
dengan menggunakan interaksi manusia dan komputer sampai ke metode ArtificialIntelligencedan Computational Intelligence. Bhaduri (2009), mencatat beberapa penelitian yang telah dilakukan dalam bidang
timetabling
OperationResearch,
dengan
menggunakan
ArtificialIntelligence
dan
metode
dalam
bidang
ComputationalIntelligencedan
metode-metode tersebut dapat dibagi menjadi empat kategori yaitu: 1. Sequential Methods Sequential Methods memperlakukan timetabling problem sebagai graph problem.Para peneliti mengatur events dengan menggunakan domain-spesific heuristics dan memasukkan events secara berurutan dalam slot waktu yang valid sedemikian rupa, sehingga tidak ada contraints yang dilanggar pada setiap slot waktu. Lai et al. (2006) mencatat bahwa de Werra pada tahun 1992 dan 1997 menunjukkan bagaimana mengurangi course timetabling problem ke dalam graphcoloringproblem. Dengan menerapkan coloring technology, problem tersebut dapat dirumuskan sebagai jaringan arcs dan node, kemudian solusi dapat diperoleh dengan menemukan satu set warna di mana tidak ada dua node yang berdekatan atau edges memiliki warna yang sama. 2. Cluster Methods Problem dibagi menjadi beberapa set events. Setiap set didefinisikan sehingga memenuhi segala hard constraints. Kemudian set tersebut diatur ke dalam timeslot nyata untuk memenuhi soft constraints.
10
Lai et al. (2006) juga mencatat beberapa penelitian yang menggunakan Cluster Methods dilakukan oleh Ferland& Roy pada tahun 1985 yang memformulasikan timetabling problem sebagai assignment problem dan menyelesaikan problem tersebut melalui pengurangan quadratic assignment problem. Kemudian penelitian dengan menggunakan cluster methods tersebut dilanjutkan
kembali
oleh
Tripathy
pada
tahun1992
dengan
menggunakan metode Lagrangian Relaxation, dalam pendekatan ini, sejumlah variable dikurangi dengan menggunakan grouping. Sejumlah constraints dikurangi dengan menggantinya dengan sejumlah relaxed contraints,
kemudian
solusi
yang
layak
didapatkan
dengan
menggunakan metode heuristic. 3. Constraint Based Methods Timetabling problem dimodelkan sebagai satu set variabel (events) yang resource (lecturer atau rooms) harus ditugaskan dalam rangka memenuhi sejumlah constraints. Lai et al. (2006) mencatat bahwa Monfroglio et al. pada tahun 1988 menggunakan sistem yang berbasiskan prolog yang menggunakan backtracking untuk menemukan timetable yang layak dengan cara men-decomposes dan mengklasifikasi constraints sehubungan dengan message passing dan constraints ordering untuk meminimalkan backtracking dan memaksimalkan parallelism. Kemudian Deris et al. pada tahun 2000 mengusulkan Constraint-based Reasoning Algorithm dan diimplementasikan dengan pendekatan
11
Object-Oriented, lalu pada tahun 2003 Valouxis dan Housos mengusulkan penggunaan Operation Research models dan metode Local Search untuk membantu constraint programming dengan meminimalkan wilayah pencarian solusi. 4. Metaheuristic Methods Metaheuristic Methods diimplementasikan dalam timetabling problem dengan memulai beberapa solusi awal, kemudian menggunakan metode pencarian untuk menghindari local optima.Metaheuristic ini juga mencakup beberapa pendekatan heuristic yang diinspirasikan dari alam, dan mengaplikasikan proses nature-like untuk mendapatkan solusi atau populasi dari solusi. Lai et al. (2006) mencatat beberapa jenis Metaheuristic Methods yang pernah digunakan dalam penelitian timetabling adalah Genetic Algorithm yang dilakukan oleh Colorni dan Maniezzo pada tahun 1990. Kemudian pada tahun 1992, Moscato dan Norman menggunakan Memetic Algorithm yang digunakan untuk meningkatkan kemampuan Genetic Algorithm dengan menggabungkan local neighborhood search, yang digunakan untuk mengeksplorasi neighborhood solusi yang didapatkan dari Genetic Algorithm dan menavigasi pencarian menuju local optima untuk setiap solusi. Beberapa penelitian yang menggunakan pendekatan heuristic yang nature-like dalam timetable scheduling adalah metode Tabu Search juga kemudian digunakan oleh Hertz pada tahun 1991 yang
12
menggunakan grouping untuk problem optimization dan pada tahun 1992, Hertz menggunakan metode ini untuk masalah lectures yang lebih kompleks (Lai et al. 2006). Penelitian yang lain adalah penggunaan Particle Swarm Optimization yang dilakukan oleh Chu et al. pada tahun 2006 yang digunakan untuk membuat schedule exam timetables, penelitian ini mengukur kualitas dari examination timetable dan waktu yang dibutuhkan untuk menghasilkan timetable tersebut.Selain Particle Swarm Optimization, penelitian lain yang menggunakan nature-like algorithm adalah penggunaan Harmony Search yang dilakukan oleh Al-betar et al. pada tahun 2008 dan 2009. Harmony Search yang diperkenalkan oleh Geem et al. pada 2001 yang diinspirasikan dari fenomena natural dari perilaku pemusik ketika mereka memainkan alat music bersama-sama untuk mendapatkan fantastic harmony.Pada penelitian tersebut, Harmony Search untuk university course timetabling dan berhasil menemukan near optimal solution.
2.3. Metode Timetable Scheduling Banyak metode yang sudah digunakan untuk menyelesaikan permasalahan timetable scheduling dan beberapa di antaranya terdapat pada kelompok metaheuristic algorithm. Metaheuristic algorithm adalah suatu metode komputasi yang mengoptimalkan suatu problem dengan cara meningkatkan kandidat solusi secara interaktif dengan ukuran kualitas tertentu.
13
Biasaanya Metaaheuristics algorithm digunakan d untuk com mbinational optimization o n di mana solusi optiimal dicari dalam sebbuah discreete searchi sesuai denngan perkem space.Tetap s mbangan tekknologi infoormasi dan kebutuhan Algorithm ini mulai timetable t sccheduling yang y semakiin pesat, Metaheuristic M dikembangk d kan untuk mengatasi m tim metabling problem.Klas p sifikasi darii algoritma Metaheuristi M ics dapat dillihat pada gaambar berikuut ini:
Gambar 2.1.
Klasiffikasi Metahheuristics Alggorithm (Dréo &Candann, 2011)
Dari sekian bannyak algorittma yang teermasuk daari jenis ini, beberapa algoritma a y yang sering digunakan untuk menyelesaikan timetablingg problem adalah: a
14
2.3.1. Genetic Algorithm (GA) Dalam penelitiannya,Fang (1992) mendefinisikan Genetic Algorithm sebagai kelompok methods yang menyelesaikan problems menggunakan algoritma yang diinspirasikan oleh proses evolusi Darwinian. Dalam GA, kemampuan dari satu set kandidat solusi sebuah problem (chromosomes) dievaluasi dan diurutkan, kemudian kandidat solusi baru diciptakan dengan menggunakan kandidat terbaik sebagai “parents” dan mengaplikasikan mutasi dan crossover (mengkombinasikan bits dari dua parents untuk menghasilkan satu atau lebih child)operators. Set dari kandidat baru ini kemudian dievaluasi, dan cycle ini terus berlanjut sampai solusi yang memadai ditemukan. Menurut Fang (1992), Outline dari tradisional Genetic Algorithm, adalah sebagai berikut: 1. Inisialisasi dan Encode sebuah random populasi dari chromosomes. 2. Decode dan evaluasi setiap chromosomefitness dalam sebuah populasi. 3. Reproduce sebuah generasi baru dengan memilih chromosome sebagai parents sesuai dengan fitness value untuk menghasilkan children (chromosome) baru. 4. Melakukan crossover, inversion dan mutation untuk chromosome baru agar menghasilkan chromosome baru yang berbeda. 5. Ulangi langkah 2-4 sampai ditemukan fitness value atau fitness function yang paling optimal. Penjelasan mengenai crossover, inversion dan mutation menurut Fang (1992), adalah sebagai berikut:
15
1. Crossover Proses crossover adalah proses menghasilkan rekombinasi string bit (gene) melalui pertukaran sebagian gene antara 2 chromosomeparents. a. One-point Crossover Crossover yang dilakukan dengan membagi chromosome menjadi 2 bagian, dimana bagian sebelum crossover point (letak pembagian chromosome yang dilakukan secara random) dibiarkan tidak berubah, dan bagian setelah crossover point ditukar antara 2 parents. b. Two-point Crossover Crossover jenis ini sama dengan one-point crossover tetapi dalam two-point crossoverdipilih 2 buah crossover point dan yang ditukar adalah gene yang ada di antara 2 buah crossover point tersebut. Proses ini dapat menghasilkan performance yang baik karena kadang kala bagian head dan tail dari chromosome tetap dibutuhkan. c. N-point Crossover Proses crossover yang dilakukan sama dengan yang dilakukan pada one-point dan two point crossover tetapi dalam N-point crossover dipilih beberapa crossover point yang dipilih untuk menentukan tempat untuk dilakukan crossover dan bit antara crossover
point
ganjil
dan
genap
yang
dilakukan
crossoversedangkan bit antara crossover point genap dan ganjil tidak berubah.
16
d. Uniform Crossover Untuk uniform crossover dilakukan proses sebagai berikut: a) Random nomor untuk mengetahui berapa posisi yang harus dilakukan crossover (menentukan berapa banyak crossover point). b) Random nomor untuk menentukan crossover point mana yang akan di jadikan patokan untuk melakukan crossover contoh P1,P2, P3 … Pn. c) Untuk setiap Pi, lakukan crossover untuk Pith dari parent dengan Pith parent yang lain, dan hasilkan 2 children baru. 2. Inversion Invesion adalah suatu proses penukaran gene seperti melakukan reordering. Inversion ini membutuhkan sebuah chromosome dan dua buah inversion point yang menentukan bagian dari chromosome (gene) manakah yang akan dilakukan reordering. Bagian antara 2 inversion point ini akan dilakukan perputaran gene. Dari beberapa penelitian, dibuktikan bahwa inversion ini tidak menghasilkan hasil yang baik dalam percobaan Genetic Algorithm. 3. Mutation Mutation adalah suatu proses untuk mengubah satu atau beberapa gene dalam sebuah chromosome menjadi sebuah gene baru berdasarkan encoding yang dilakukan sebelumnya. Proses mutation ini digunakan untuk menghasilkan suatu gene baru yang diharapkan menghasilkan suatu gene yang tidak terjangkau sebelumnya. Misalnya saja, pada
17
gene chromosome induk tidak ditemukan angka 15, maka ketika proses mutation ini selesai diharapkan gene yang dihasilkan adalah angka 15.
2.3.2. Simulated Annealing (SA) Simulated Annealing adalah sebuah algoritma generic probabilistic metaheuristic untuk mengatasi permasalahan global optimization dalam menempatkan sebuah perkiraan yang baik untuk global optimum dari fungsi yang diberikan dalam search space yang besar.Biasanya algoritma ini digunakan ketika search space yang digunakan adalah discrete, misalnya Traveling Salesman Problem. Algoritma ini diinspirasikan dari kata annealing dari metallurgy (pengetahuan mengenai logam), sebuah teknik yang meliputi penggunaan heating (pemanasan) dan pengaturan cooling (pendinginan) dari sebuah material untuk meningkatkan size kristal dari material tersebut dan mengurangi cacatnya. Menurut Moscato (1989), Simulated Annealing adalah sebuah teknik untuk global optimization yang diambil dari Statistical Mechanics. Metode ini telah dibuktikan cocok untuk banyak jenis permasalahan contohnya min cut partitioning problem, global wiring, least square fitting of many unknows, image analysis, dan banyak lagi. Simulated Annealing menurut Duong et al. (2004) adalah teknik global stochastic optimization yang banyak digunakan untuk menyelesaikan banyak tipe dari permasalahan optimisasi combinatorial.Simulated Annealing adalah sebuah variant dari local search yang memperbolehkan langkah uphill untuk diterima dalam sebuah kejadian yang dikendalikan.
18
Algoritma SA yang tipikal menerima solusi baru jika cost solusi baru tersebut lebih rendah dari cost solusi sekarang, tetapi kadang-kadang terdapat kemungkinan solusi baru ini dapat diterima walaupun costnya lebih besar. Dengan kriteria tersebut ini memungkinkan untuk mendaki keluar dari local optima. Basic pseudocode dari Simulated Annealing yang terdapat pada penelitian Duong et al. (2004) untuk menyelesaikan permasalahan university exam timetabling adalah sebagai berikut: Pilih sebuah solusi awal S0 Pilih sebuah temperatur awal t0> 0 Pilih temperature reduction function α Repeat Repeat Secara acak pilih s ∈N(s0) /* merupakan neighbor solution dari S0 d = f(s) – f(s0);
/* hitung perubahan dalam cost function*/
ifd < 0 then s0 = s else generate random x ∈[0,1];
/* x adalah angka acak
number in range 0 to 1 */ ifx < exp(-d/t) then s0 = s endif endif untiliteration_count = nrep; t = α(t) untilstopping condition = true./* s0adalah perkiraan dari solusi optimal */
19
Dalam mendisain sebuah algoritma simulated annealing yang bagus diperlukan beberapa komponen yaitu: 1. Neighborhood Structure Dalam mengaplikasikan SA, diperlukan neighborhood structure yang menunjukkan bahwa untuk setiap solusi diperlukan sebuah set neighborhood solution. Ini adalah komponen kunci dari metode simulated annealing untuk kasus apapun. Dalam penelitian Duong et al. (2004) neighborhood yang digunakan adalah salah satu variant dari Kempe chains neighborhood yang dikonstuksikan
dengan
simpel.Kemudiancurrent
menggunakan solution
dicek
prosedur dan
perulangan
diperbaiki
yang
sedangkan
neighbor dari current solution dipilih secara acak. 2. Cost Function Cost function ini dibuat untuk menghitung besarnya cost dari current solution, solusi baru dan neighborhood solution, agar terjadi perubahan antara current solution, solusi baru dan neighborhood solution. Cost function ini dibuat berbeda-beda tergantung permasalahan yang dihadapi.Untuk kasus permasalahan exam timetabling, cost function dibuat untuk mencerminkan pengaruh dari soft constarints, perbedaan time distance antara dua exam untuk siswa yang sama juga menjadi salah satu factor penting. Semakin dekat waktunya maka semakin besar penalty yang diberikan, penalty diberikan dengan menggunakan metode yang diajukan oleh Burke et al.
20
Dalam penelitian Duong et al. (2004), dalam menghitung delta evaluation menggunakan delta evaluationdimana perbedaan cost antara current solution dan neighborhood solutiondievaluasi. Selama neighbor solution adalah sebuah timetable yang dihasilkan dari pertukaran antara dua exam sessions dalam current timetable, maka perbedaan cost antara current timetable dan neighbor timetable dapat dihitung secara cepat. 3. Cooling Schedule Cooling schedule adalah suatu perlakuan dalam mengontrol parameter, temperatur awal dan proses pengaturan temperatur dalam proses pendinginan. Dalam proses cooling schedule, dilakukan beberapa kali perulangan (nrep) untuk mengubah temperatur (t) berdasarkan perkalian dengan reduction function (α).
2.3.3. Tabu Search (TS) Menurut Glover (1989), Tabu Search adalah sebuah strategi untuk menyelesaikan combinatorial optimization problems yang aplikasinya mulai dari graph theory dan matroid settings ke general pure dan mixed integer programming problems. Tabu Search ini adalah sebuah prosedue adaptive dengan kemampuan untuk mempergunakan metode lain seperti linear programming algorithms untuk langsung mengatasi permasalahan dari keterbatasan dalam local optimality. Kemudian dalam penelitiannya, Chu dan Fang (1999) menyimpulkan bahwa Tabu Search sebagai suatu heuristic search method yang memiliki
21
keuntungan karena memiliki internal memory.Keuntungan ini memungkinkan Tabu Search untuk mencegah pencarian ke area yang sudah di kunjungi sebelumnya. Pendekatan ini memiliki dua mekaniskme dasar, yaitu tabu restrictions dan aspiration criteria.Selain itu, lebih mudah juga untuk keluar dari local optimum dan mendapatkan global optimum atau near global optimum dalam waktu yang singkat. Langkah-langkah simple tabu search adalah 1. Pilih x awal dimana
dan biarkan x* := x. Atur counteriterasi k = 0,
dan mulai dengan T yang kosong. 2. Jika S(x) – T adalah kosong, lanjutkan ke Langkah 4. Selain itu, set k := k + 1 dan pilih
:
, jika
. 3. Biarkan x := sk(x). Jika
, dimana x* denotes adalah solusi
terbaik yang sudah ditemukan, biarkan x* := x. 4. Jika angka yang dipilih untuk iterasi melampaui baik dalam total atau ketika x* terakhir ditingkatkan, atau jika s(x) – T = Ø atau sampai pada langkah ini melalui langkah 2, maka hentikan proses. Selain itu, update T (seperti yang sudah diberikan sebelumnya) dan kembali ke langkah 2.
22
2.3.4. Memetic Algorithm (MA) Memetic Algorithm pertama kali diperkenalkan oleh Moscato (1989), dimana Moscato memperkenalkan algoritma ini mirip dengan Genetic Algorithm yang digabungkan dengan prosedur individual learning yang dapat menghasilkan perbaikan local. Memetic algorithm menangkap beberapa bagian teori seperti Darwinian evolution dan antara memes dan domain spesifik tertentu (local search) heuristic dan kemudian dirender kedalam sebuah metodologi yang menyeimbangkan antara permasalahan secara general maupun secara spesifik. Memetic algorithm sekarang ini banyak dikenal dengan berbagai sebutan nama yaitu Hybrid Evolutionary Algorithms, Baldwinian Evolutionary Algorithms, Lamarckian Evolutionary Algorithms, Cultural Algorithms atau Genetic Local Search. Kemudian menurut Hung et al. (2005), Memetic Algorithm yang diperkenalkan oleh Moscato dan Norman pada tahun 1992 adalah sebuah variant yang dikembangkan dari Genetic Algortihm. Memetic Algorithm mengambil konsep evolusi sama seperti pada Genetic Algortihm, tetapi Genetic Algortihm menggunakan konsep biological evolution sedangkan memetic algorithm menggunakan konsep cultural evolution atau idea evolution. Dalam evolusi ide, sebuah ide dapat berkembang tidak hanya berdasarkan rekombinasi dari yang lainnya, tetapi berdasarkan adaptasi dari dirinya sendiri.Meme,
sebuah
unit
informasi
dalam
memetic
algorithm
dapat
dikembangkan oleh individual yang memegang informasi tersebut sebelum didistribusikan.
23
Meme berbeda dengan gene, karena gene diturunkan antara individual, sedangkan meme didapatkan berdasarkan adaptasi setiap individual dimana gene yang diturunkan tidak berubah.Jadi basic Memetic Algorithm ini adalah sebuah Evolution Algorithm yang digabungkan dengan beberapa teknik local search. Dalam penelitiannya, Hung et al. (2005), menyelesaikan permasalahan examination timetabling dengan menggunakan teknik local search hill-climbing dan hanya menggunakan mutation sebagai evolutionary operators dalam Genetic Algorithm. Outline dari Memetic Algorithm yang disimpulkan oleh Hung et al. adalah sebagai berikut: Repeat Ambil setiap individual setiap perulangan: Pilih mutation method (Light atau Heavy Mutation) Aplikasikan mutation method untuk individual yang dipilih Aplikasikan hill-climbing pada individual baru Masukkan individual tersebut ke dalam populasi Pilih setengah dari populasi, untuk mengurangi populasi menjadi ukuran awal Untilkondisi berhenti terpenuhi
2.3.5. Ant Colony Optimization (ACO) Menurut Engelbrecht (2007, p360), Ant Colony Optimization adalah sebuah algoritma yang dikembangkan oleh Marco Dorigo pada tahun 1992 yang digunakan untuk mencari optimal path dalam sebuah graph, dengan menggunakan tingkah laku dari semut mencari path antara colony-nya dengan sumber makanan. Di kehidupan alam, semut berkeliling secara acak untuk mencari makanan, ketika menemukan makanan, semut mengeluarkan pheromone untuk membantu
24
semut yang lain mengikuti path yang ditemukan, pencarian kemudian dilakukan tidak secara acak, tetapi menggunakan path tersebut. Denganmengeluarkan pheromone, semut yang mengikuti jalur tersebut memperkuat jalur, jika menemukan makanan. Tetapi jalur pheromone tidak dapat berlangsung lama, dan kehilangan kemampuan untuk menarik perhatian seiring dengan waktu ketika semut mengikuti path dan kembali ke koloni.Oleh karena itu, semut mencari path yang lebih pendek, agar kepekatan pheromone semakin tinggi dan membentuk path baru yang lebih baik.Pembentukan path baru yang lebih baik tersebut dapat dilihat pada contoh dalam gambar di bawah ini:
Gambar 2.2.
Pemilihan Shortest Path (Engelbercht, 2007)
Pemudaran pheromone ini juga membantu semut untuk menghindari konvergensi pada local optima, jika tidak ada pemudaran, maka path yang dipilih oleh semut pertama akan terus digunakan dan akan membatasi pencarian solusi terbaik. Dengan menggunakan tingkah laku ini, ant colony optimization menggunakannya untuk membuat “simulated ants” untuk bergerak di dalam graph
25
untuk merepresentasikan penyelesaian masalah dan menemukan shortest path yang digunakan menjadi solusi penyelesaian. Dalam perkembangannya, ACO banyak digunakan untuk menyelesaikan permasalahan scheduling. Misalnya pada tahun 2005, Ghoseiri & Morshedsolouk menggunakan Ant Colony System (ACS) untuk menyelesaikan permasalahan trainscheduling
dengan
menyelesaikan
permasalahan
tersebut
sebagai
permasalahan Traveling Salesman Problem (TSP) dimana kota dalam TSP merepresentasikan kereta dan menghasilkan suatu algoritma baru yang dinamakan ACS-TS, sebuah model matematika untuk menyelesaikan permasalahan train scheduling. Kemudian permasalahan
pada
Post
tahun
Enrolment
2007, Course
Nothegger
et.
Timetabling
al. untuk
menyelesaikan International
Timetabling Competition dengan menggunakan ACO. Antsdigunakan untuk mengalokasikan events ke dalam ruangan dan timeslot berdasarkan dua jenis pheromone
yang
merepresentasikan
probabilitas
untuk
mengalokasikan event i ke dalam slot j dan ruang k berurutan. Algoritma Ant Colony Optimization yang digunakan sekarang ini, adalah sebagai berikut: Inisialisasiτij(0) dengan angka random; Inisialisasit = 0; Simpannk antspada node awal; repeat foreach ant k = 1, . . . , nk do //Buat path xk(t); xk(t) = ; repeat Pilih node selanjutnya dengan probability:
26
Add link (i, j) ke path xk(t); Untilnode akhir tercapai; Remove all loops darixk(t); Hitung panjang dari pathf(xk(t)); end foreach link (i, j) of the graph do //pemudaran pheromone; Reduce pheromone, τij(t), dengan perhitungan:
end foreach ant k = 1, . . . , nk do foreach link (i, j) of xk(t) do Δτk = 1 f(xk(t)) ; Update τij dengan perhitungan:
end end t = t + 1; untilkondisi berhenti terpenuhi; Return path xk(t) dengan nilaif(xk(t)) terkecilsebagai solusi;
2.3.6. Particle Swarm Optimization (PSO) Menurut Engelbrecht (2007,p289) algoritma Particle Swarm Optimization (PSO) adalah algoritma yang berdasarkan interaksi sosial dari sekumpulan burung.Konsep awal dari algoritma ini adalah untuk mensimulasikan pergerakan yang tidak terprediksi dari sekumpulan burung dan bertujuan untuk mengetahui pola pergerakan burung yang dapat berubah secara tiba – tiba dan membuat formasi yang optimal.
27
Menurut Chu et al. (2006), PSO yang pertama kali diperkenalkan oleh Dr. Eberhart dan Dr. Kennedy pada tahun 1995 adalah sebuah teknik populationbased evolutionary computation alternatif yang diinspirasikan dari perilaku sosial dari kelompok burung dan ikan. PSO sebenarnya memiliki kesamaan dengan evolutionary computation teknik seperti GA, tetapi tidak seperti GA, PSO tidak punya evolutionoperatorsseperti crossover dan mutasi. PSO mencoba untuk mensimulasikan perilaku sosial dengan membuat populasi dari solusi yang potensial (particles)sama seperti burung dalam kawanannya. PSO diinisialisasikan menjadi sekelompok random particles kemudian optima dicari dengan meng-update generasi.Semua particles mempunya fitness value yang dievaluasi oleh fitness function untuk dioptimasikan, setiap particle mempunyai velocities yang mengatur arah dari setiap particle.Setiap particle diupdate dengan dua value terbaik dalam setiap iterasi.Value pertama adalah posisi terbaik sebelumnya dari particle ke-k pada iterasi ke-i
. Sedangkan value yang
lain dilacak dengan Particle Swarm Optimizer yang didapatkan oleh setiap particle dalam sebuah populasi. Populasi terbaik ini adalah global best dari semua particle Gi dari iterasi pertama sampai dengan iterasi ke-i.Setiap particle ini equivalent dengan kandidat solusi dalam sebuah problem.Particle akan bergerak sesuai dengan velocity yang diatur, berdasarkan dengan pengalaman dari particle tersebut dan oleh companion. Dan sebagai hasilnya, PSO biasanya mendapatkan nearly best solution dalam evolusi yang lebih sedikit dibandingkan dengan metode yang lain. Langkah-langkah original dari PSO yang digambarkan oleh Chu et al. (2006) adalah sebagai berikut:
28
1. Banyak particle yang akan digunakan untuk menyelesaikan problem ditentukan. Setiap particle mempunyai posisi, velocity dan solusi terbaik.
2. Proses dari pengubahan velocity dapat dilihat berdasarkan perhitungan: .
.
.
3. Pergerakan particle dapat dilihat berdasarkan perhitungan: ,
0,1, … ,
1,
Dimana:
M adalah particle size
(Vmax adalah maximum velocity) Sedangkan r1 dan r2 adalah random variable contohnya 0
,
1
4. Jika solusi yang didapatkan lebih baik dari Gi, maka Giakan diganti dengan solusi tersebut untuk menciptakan Gi+1. Jika tidak lebih baik, maka tidak ada perubahan untuk solusi global best. 5. Ulangi langkah 1 sampai 4, sampai kondisi berhenti terpenuhi. Menurut Engelbrecht (2007,p298) ada 2 aspek penting dalam memilih kondisi berhenti yaitu : •
Kondisi berhenti tidak menyebabkan PSO konvergen premature dimana solusi tidak optimal yang akan didapat
29
•
Kondisi berhenti harus melindungi dari kondisi oversampling pada nilainya. Jika kondisi berhenti memerlukan perhitungan yang terus menerus maka kerumitan dari proses pencarian akan meningkat
Beberapa kondisi berhenti yang dapat dipakai dalam Particle Swarm Optimization menurut Engelbrecht (2007,p298) adalah: •
Berhenti ketika jumlah iterasi telah mencapai jumlah iterasi maksimum yang diperbolehkan
•
Berhenti ketika solusi yang dapat diterima telah ditemukan
•
Berhenti ketika tidak ada perkembangan setelah beberapa iterasi
2.3.7. Harmony Search (HS) Harmony Search adalahsebuah metaheuristic algorithm yang dikemukakan oleh Geem et al. (2001), algoritma ini dikonseptualisasikan menggunakan proses musical untuk mencari perfect state of harmony. Para pemusik mencari harmony yang tepat yang ditentukan berdasarkan aesthetic standard, sama seperti proses optimasi yang mencari global solution seperti yang ditentukan berdasarkan objective function. Pitch dari setiap instrument music menentukan aesthetic quality dari masing-masing instrument, sama seperti objective functionvalue ditentukan melalui suatu set value yang diatur ke dalam decision variable masing-masing. Algoritma Harmony Search ini diturunkan berdasarkan kinerja proses alami yang terjadi ketika seorang musisi mencari harmony yang lebih baik, seperti ketika improvisasi music Jazz.
30
Dalam improvisasi musik, masing-masing musisi membunyikan sebuah nada dalam tingkat nada yang mungkin dihasilkan, nada-nada tersebut membuat sebuah vektor harmoni. Jika semua nada menghasilkan harmoni yang bagus, maka pengalaman membuat harmoni tersebut akan tersimpan di ingatan para musisi, sehingga kemungkinan untuk membuat harmoni bagus lainnya akan meningkat. Hal ini diadaptasi dalam teknik optimalisasi, dengan masing-masing variabel keputusan memilih nilai awal (initial value) dalam batasan yang mungkin membentuk sebuah vektor solusi. Jika masing-masing variabel keputusan membentuk harmoni yang baik, pengalaman tersebut akan disimpan dalam variabel memori, yang nantinya akan memperbesar kemungkinan untuk mendapatkan vektor solusi yang lebih baik (Geem et al., 2005). Ada beberapa strategi yang bisa digunakan untuk mendapatkan harmonisasi yang baik. Pada pertunjukan musik yang dilakukan oleh para musisi jazz, biasanya mereka memiliki tiga pilihan untuk melakukan improvisasi: 1. Memainkan
nada
yang
sering
dimainkan,
yang
merupakan
karakteristik dari bagian musik tersebut. Dalam musik, nada ini dikenal dengan sebutan nada dasar. Pada dasarnya semua musisi mengerti nada dasar tersebut dan dapat memainkan nada tersebut dengan sendirinya, dengan kata lain nada-nada dasar ini sudah tersimpan dalam memori mereka. 2. Memainkan nada yang serupa dengan nada dasar. Biasanya musisi memperkaya musik dengan menaikkan atau menurunkan nada dasar sesuai dengan eksplorasi mereka. Hal ini akan menyebabkan permainan musik serupa dengan variasi nada yang berbeda.
31
3. Memainkan nada sembarang, yang memberikan musisi kebebasan untuk berimprovisasi. Dengan cara seperti ini, ada kemungkinan not yang dihasilkan sedikit atau tidak memiliki hubungan dengan lagu yang ditampilkan. Hal ini membutuhkan bakat dan imajinasi dari musisi, yang membuatnya menjelajahi dunia musik dan memberikan nuansa baru pada musik dengan tema-tema segar dan baru. Dari tiga pilihan berimprovisasi di atas, memberikan para peneliti strategi untuk mendapatkan harmonisasi yang baik. Hal ini diadaptasi, sehingga setiap variabel keputusan dalam mengambil sebuah nilai dalam algoritma harmony search harus berpedoman pada tiga aturan ini (Geem et al., 2005): 1. Mengambil nilai yang sudah terdapat pada memori harmoni, biasanya didefinisikan sebagai memory considerations. 2. Mengambil nilai yang berdekatan dari satu nilai pada memori harmoni, biasanya didefinisikan sebagai pitch adjustments. 3. Mengambil nilai acak dari rentang nilai yang mungkin, biasanya didefinisikan sebagai randomization. Tiga aturan ini nantinya akan dibutuhkan dalam menyusun algoritma harmony search yang diwakilkan oleh beberapa parameter.Secara umum parameter-parameter ini akan sangat mempengaruhi kinerja dari harmony searchdalam mendapatkan solusi yang optimal. Berikut adalah parameter yang digunakan secara umum dalam harmony search(Geem et al., 2005): 1. HMS (Harmony Memory Size), adalah jumlah dari kumpulan harmoni memori, bisa disebut sebagai jumlah populasi.
32
2. HMCR (Harmony Memory Consideration Rate), adalah probabilitas dari harmoni memori untuk digunakan kembali sebagai hasil dari vektor solusi. Parameter ini memiliki rentang nilai dari 0 sampai dengan 0,99. Parameter ini tidak menggunakan nilai 1, untuk mencegah terjadinya stagnansi nilai (range nilai tidak berubah dan perbaikan minimal). 3. PAR (Pitch Adjustment Rate), adalah parameter yang mempunyai peran signifikan dalam menentukan jumlah nilai yang harus diubah, disesuaikan, atau ditukar dengan nilai yang lain. Parameter ini memiliki rentang nilai dari nol sampai dengan satu. 4. NI (Number of Improvisations), adalah parameter yang digunakan sebagai kriteria pemberhenti perulangan, biasanya berupa jumlah iterasi untuk mendapatkan nilai yang optimal. Langkah-langkah yang digunakan dalam melakukan algoritma harmony searchadalah (Geem et al., 2005): 1. Inisialisasi Harmony Search Algorithm (HSA) dan parameterparameter permasalahan optimasi. 2. Inisialisasi Harmony Memory (HM). 3. Improvisasi sebuah harmoni baru. 4. Memperbarui Harmony Memory (HM). 5. Melakukan pengecekan kondisi berhenti. Dalam langkah (1), perlu diperhatikan fungsi objektif yang akan digunakan untuk menghitung nilai perbaikan dari HM. Fungsi objektif bisa dispesifikasikan sebagai berikut:
33
|
|
atau
Keterangan: a.
, fungsi objektif. 1…
b.
, himpunan dari setiap variabel keputusan
c.
, himpunan dari rentang nilai yang mungkin untuk setiap variabel 1 ,
keputusan, dengan,
2 ,…,
untuk
.
.
d.
adalah jumlah variabel keputusan.
e.
adalah jumlah rentang nilai yang mungkin untuk setiap variabel keputusan. Dalam langkah (2), HM adalah vektor solusi dengan banyak sejumlah
HMS.Pada langkah ini solusi-solusi yang dibentuk merupakan nilai random. Bentuk HM bila digambarkan dalam Matriks bisa berbentuk seperti:
. Untuk setiap objektifnya
.
. 1…
dengan
.
, perlu ditentukan nilai fungsi
, agar bisa diketahui mana himpunan yang memiliki nilai terbaik
dan nilai terburuk. Dalam prosesnya, himpunan dengan nilai terbaik akan menjadi solusi yang dipakai, sedangkan himpunan dengan nilai terburuk akan tereliminasi dan digantikan dengan yang himpunan dengan nilai yang lebih baik selama perulangan berlangsung. Dalam langkah (3), HSA akan secara otomatis membuat vektor solusi yang baru,
,
,
,…,
, berdasarkan pada tiga
34
operator: (a) memory consideration, (b) random consideration, dan (c) pitch adjustment. a.
Memory Consideration Pada operator ini, pencarian variabel keputusan akan berdasarkan pada memori yang tersimpan sebelumnya di posisi yang sama dengan kemungkinan pemilihan operator ini sebesar parameter HMCR, dengan kemungkinan 0
1 .
Bila operator ini dilaksanakan, maka untuk mendapatkan variabel keputusan ,
,
yang
baru
,…,
akan
b.
dari
himpunan
yang disimpan dalam HM. Untuk mendapatkan
variabel keputusan selanjutnya ,
himpunan
dipilih
berlaku
juga
,
,
,
,…,
untuk
maka akan dipilih dari yang disimpan dalam HM. Hal ini
variabel-variabel
keputusan
yang
lain
… .
Random Consideration Operator ini akan terlaksanakan dengan kemungkinan 1
,
yang merupakan alternatif apabila operator memory consideration tidak digunakan dalam mencari vektor solusi. Bila operator ini dilaksanakan, maka untuk mendapatkan variabel keputusan yang baru adalah nilai yang termasuk dalam
. Jadi
operator ini akan mengambil calon vektor solusi dari semua variabel keputusan yang terdapat pada HM. c.
Pitch Adjustment
35
Operator ini akan terlaksana dengan sebuah prasyarat, terlaksananya operator memory consideration. Operator ini akan melakukan improvisasi nilai dari variabel keputusan secara lokal. Operator ini memiliki kemungkinan terjadi
.
Bila operator ini dilaksanakan, dengan varibel keputusan dengan
adalah posisi elemen / nilai pada ,
dengan
adalah
, maka
neighborhood
index,
… , 2, 1, 0, 1, 2, … . Operator ini akan mengambil calon vektor solusi dari vektor neighborhood yang mungkin. Dalam
langkah ,
,
(4), ,…,
jika
hasil
vektor
harmoni
, memiliki nilai fungsi objektif yang lebih
baik dari vektor harmoni dengan nilai fungsi objektif terburuk di HM, maka vektor harmoni yang baru akan dimasukkan ke dalam HM, sedangkan vektor harmoni dengan nilai fungsi objektif terburuk di HM akan dike luarkan. Dalam langkah (5), akan dilakukan pengecekan sampai kondisi berhenti dari algoritma harmony searchterpenuhi. Biasanya kondisi berhenti dari algoritma adalah nilai dari parameter NI (jumlah maksimal dari perbaikan harmoni).Bila kondisi berhenti salah, maka ulangi langkah (3) dan langkah (4).
