20
BAB 2 TINJAUAN PUSTAKA
2.1. Pengantar Algoritma genetika merupakan algoritma yang lahir dari sebuah inspirasi teori evolusi Darwin yang mengatakan anggota dari spesies yang lemah lambat laun akan mengalami kepunahan sedangkan anggota dari spesies yang kuat akan tetap dapat bertahan hidup dan berkembang biak untuk kelangsungan hidup spesies tersebut. Algoritma genetika merupakan sebuah algoritma pencarian yang berdasarkan mekanisme seleksi alam dan genetika alam (Goldberg, 1989).
2.1.1. Istilah-istilah dasar dalam algoritma genetika Didalam algoritma genetika kita perlu mengetahui beberapa pengertian dari istilahistilah yang digunakan didalam algoritma tersebut, yaitu : 1. Gen (Genotype) adalah variabel dasar yang membentuk suatu kromosom, yang dapat dinyatakan dalam bentuk biner, float, integer dan karakter. 2. Allele adalah nilai dari suatu gen, dapat berbentuk biner, float, integer maupun karakter. 3. Kromosom adalah gabungan dari gen-gen yang membentuk arti tertentu. Dalam algoritma genetika ada beberapa macam bentuk kromosom, yaitu : a. Kromosom Biner : kromosom yang disusun dari gen-gen yang bernilai biner, kromosom ini memiliki tingkat keberhasilan yang tinggi. Kromosom ini baik digunakan untuk permasalahan yang parameter dan range nilainya tertentu. b. Kromosom Float : kromosom yang disusun dari gen-gen yang bernilai pecahan dan yang bernilai bulat. Kromosom ini merupakan model yang memiliki parameter yang banyak dan tingkat keberhasilan dari kromosom ini rendah. c. Kromosom String : kromosom yang disusun dari gen-gen yang bernilai string.
Universitas Sumatera Utara
21
d. Kromosom Kombinatorial : kromosom yang disusun dari gen-gen yang dinilai berdasarkan urutannya. 4. Individu adalah kumpulan dari beberapa kromosom yang membentuk satu kesatuan, individu menyatakan salah satu kemungkinan solusi dari suatu permasalahan. 5. Populasi adalah sekumpulan individu yang akan diproses secara bersama-sama dalam satu siklus proses evolusi. 6. Generasi menyatakan satu kesatuan siklus proses evolusi. 7. Iterasi adalah bilangan yang menunjukkan tingkat generasi dan perulangan. 8. Nilai fitness menyatakan seberapa baik nilai dari suatu individu atau solusi yang dihasilkan, dan nilai inilah yang dijadikan acuan untuk mencari nilai optimal dari suatu permasalahan. 9. Fungsi pinalti : fungsi matematis yang dilibatkan dalam proses pencarian nilai optimum pada masalah optimasi dengan kendala. 10. Probabilitas adalah peluang terjadinya sesuatu.
2.1.2. Siklus algoritma genetika. David Golberg adalah orang yang pertama sekali yang memperkenalkan siklus algoritma genetika, dimana siklus ini dimulai dengan membangkitkan sejumlah individu sebagai populasi awal secara random/acak, populasi awal ini yang nantinya akan disebut dengan populasi orang tua/induk (Parents), kemudian setiap individu dihitung nilai fitnessnya. Proses selanjutnya adalah dengan menyeleksi individu yang memiliki nilai fitness paling baik. Kromosom-kromosom yang terpilih pada proses seleksi akan dilanjutkan ke proses selanjutnya yaitu proses reproduksi yang dikenal dengan
proses crossover, kromosom yang dihasilkan dari proses crossover akan
dilanjutkan ke proses berikutnya yaitu proses mutasi. Pada proses mutasi akan dilakukan penggantian gen yang kurang baik dengan gen yang dianggap baik, kromosom yang dihasilkan dari proses mutasi ini nantinya yang akan menjadi generasi baru (offspring), sehingga terbentuklah sebuah populasi baru. Pada setiap generasi, kromosom akan dievaluasi berdasarkan suatu fungsi evaluasi (Golberg & Richarson, 1997). Populasi baru yang telah dihasilkan akan mengalami siklus yang sama dengan populasi sebelumnya, demikian prosesnya berlangsung secara terus-
Universitas Sumatera Utara
22
menerus hingga generasi ke-n yaitu menghasilkan generasi yang sesuai dengan harapan.
Seleksi Individu
Evaluasi Fitness
Populasi Awal
Reproduksi : Crossover dan Mutasi
Populasi Baru
Gambar 2.1. Siklus Algoritma Genetika oleh David Goldberg (Sutojo T. et al. 2010)
Siklus yang diperkenalkan oleh david Goldberg kemudian diperbaiki oleh Zbigniew Michalewicz yaitu dengan menambah satu proses lagi yaitu proses Elitisme dan membalik proses reproduksi dahulu, kemudian proses seleksi.
Evaluasi Fitness
Populasi Awal
Reproduksi : Crossover dan Mutasi
Seleksi Individu
Populasi Baru
Elitisme
Gambar 2.2. Siklus Algoritma Genetika hasil perbaikan yang diperkenalkan oleh Zbigniew Michalewicz (Sutojo T. et al. 2010)
Universitas Sumatera Utara
23
2.1.3. Struktur umum algoritma genetika. Algoritma genetika memberikan suatu pilihan bagi penentuan nilai parameter dengan meniru cara reproduksi genetika, pembentukan kromosom baru serta seleksi alam seperti yang terjadi pada mahluk hidup. Algoritma genetika secara umum dapat diilustrasikan dalam diagram alir berikut ini :
Start
Representasi kromosom
Inisialisasi populasi
Fungsi objektif
Seleksi
Crossover
Mutasi
Generasi Baru
Tidak Kriteria optimal ? Ya Finish Gambar 2.3. Diagram Alir Algoritma Genetika
Universitas Sumatera Utara
24
Secara umum, Rexhepi et al. (2013) mengemukakan bahwa struktur umum dari suatu algoritma genetika dapat didefenisikan dengan langkah-langkah sebagai berikut: 1. Membangkitkan populasi awal Populasi awal dibangkitkan secara random sehingga didapat solusi awal. Populasi itu sendiri terdiri atas sejumlah kromosom yang merepresentasikan solusi yang diinginkan. 2. Membentuk generasi baru Untuk membentuk generasi baru digunakan operator reproduksi yaitu seleksi, crossover dan mutasi. Proses ini dilakukan secara berulang-ulang sehingga didapatkan jumlah kromosom yang cukup untuk membentuk generasi baru, dimana generasi baru ini merupakan representasi dari solusi baru. Generasi baru ini dikenal dengan istilah anak (offspring). 3. Evaluasi solusi Pada setiap generasi, kromosom akan melalui proses evaluasi
dengan
menggunakan alat ukur yang dinamakan fitness. Nilai fitness suatu kromosom menggambarkan kualitas kromosom dalam populasi tersebut. Proses ini akan mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom dan mengevaluasinya sampai terpenuhi kriteria berhenti. Jika kriteria berhenti belum terpenuhi akan membentuk generasi baru dengan mengulang langkah 2. Beberapa kriteria berhenti yang sering digunakan yaitu berhenti pada generasi tertentu, berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi tidak berubah dan berhenti bila dalam n generasi berikut tidak didapatkan nilai fitness yang lebih tinggi. Goldberg (1989) mengemukakan bahwa algoritma genetika memiliki beberapa karakteristik yang harus diketahui sehingga dapat dibedakan dari prosedur pencarian atau optimasi lainnya, yaitu : 1. Algoritma Genetika bekerja dengan pengkodean dari himpunan solusi permasalahan dengan berdasarkan parameter yang telah ditetapkan dan bukan parameter itu sendiri.
Universitas Sumatera Utara
25
2. Algoritma Genetika melakukan pencarian pada sebuah populasi dari sejumlah individu-individu yang merupakan solusi permasalahan bukan hanya dari sebuah individu. 3. Algoritma Genetika merupakan informasi fungsi obyektif (fitness), sebagai cara untuk mengevaluasi individu yang mempunyai solusi terbaik, bukan turunan dari suatu fungsi. 4. Algoritma Genetika menggunakan aturan-aturan transisi peluang, bukan aturan-aturan deterministik. Menurut Kuhn et al. (2013), variabel dan parameter yang digunakan pada algoritma genetika adalah: 1. Fungsi fitness (fungsi tujuan) yang dimiliki oleh masing-masing individu untuk menentukan tingkat kesesuaian individu tersebut dengan kriteria yang ingin dicapai. 2. Populasi jumlah individu yang dilibatkan pada setiap generasi. 3. Probabilitas terjadinya persilangan (crossover) pada suatu generasi. 4. Probabilitas terjadinya mutasi pada setiap individu. 5. Jumlah generasi yang akan dibentuk yang menentukan lama penerapan dari algoritma genetika.
2.2. Pengkodean dalam Algoritma Genetika Pengkodean merupakan suatu bagian yang paling penting apabila kita menggunakan algoritma genetika. Apapun masalah optimasi yang akan diselesaikan dengan Algoritma Genetika perlu dikodekan kedalam kromosom secara tepat. Hal ini disebabkan dalam proses komputasi yang sebenarnya, kromosom-kromosom itulah yang nantinya akan diproses ke dalam Algoritma Genetika. Pengkodean adalah suatu teknik yang dipakai untuk menyatakan populasi awal sebagai calon solusi suatu masalah kedalam suatu kromosom (Gen dan Cheng, 2000) sebagai suatu kunci utama dari permasalahan ketika menggunakan algoritma genetika. Pembentukan kromoson menghasilkan string yang kemudian disebut kromosom. String terdiri dari sekumpulan bit yang dikenal sebagai gen, jadi satu kromosom terdiri dari beberapa gen. Berdasarkan jenis symbol yang digunakan
Universitas Sumatera Utara
26
sebagai nilai suatu gen atau disebut dengan allele. Adapun metode pengkodean dalam algoritma genetika dapat diklasifikasikan sebagai berikut : pengkodean biner, bilangan rill, bilangan bulat dan struktur data (Gen dan Cheng, 2000). Sedangkan menurut (Kumar, 2012) ada bermacam-macam teknik encoding yang dapat dilakukan dalam algoritma genetika. Beberapa teknik encoding itu antara lain adalah binary encoding, permutation encoding, value encoding serta tree encoding. Menurut Varnamkasthi & Lee (2012), beberapa macam encoding pada algoritma genetika adalah : 1.
Binary Encoding Encoding jenis ini sering digunakan. Kromosom dari binary encoding ini berupa kumpulan dari nilai biner 0 dan 1. Contohnya: Chromosome1 : 0101010100110110 Chromosome2 : 1011011100011110 Dalam Binary Encoding kemungkinkan dihasilkan suatu kromosom yang memiliki nilai allele yang lebih sedikit atau kecil, keuntungan pengkodean biner ini adalah sederhana untuk diciptakan dan mudah dimanipulasi (Davis, 1991). Di pihak lain pengkodean biner ini memiliki kekurangan yaitu tidak dapat digunakan untuk beberapa permasalahan dan terkadang pengkoreksian harus dilakukan setelah proses crossover dan mutasi dilakukan. Salah satu permasalahan yang menggunakan encoding adalah menghitung nilai maksimal dari suatu fungsi.
2.
Permutation Encoding/ pengkodean bilangan Riil Kromosom dari permutation encoding ini berupa kumpulan dari nilai integer yang mewakili suatu posisi dalam sebuah urutan. Biasanya digunakan pada permasalahan TSP, penjadwalan dan masalah optimasi lainnya. Contohnya: Chromosome 1 : 1 2 3 4 5 6 7 8 9 Chromosome 2 : 4 7 1 2 5 9 3 6 0
Universitas Sumatera Utara
27
3.
Value Encoding Kromosom dari value encoding berupa kumpulan dari suatu nilai, yang bisa berupa macam-macam nilai sesuai dengan permasalahan yang dihadapi, seperti bilangan real, char atau objek yang lain. Encoding ini merupakan pilihan yang bagus untuk beberapa permasalahan khusus, biasanya diperlukan metode khusus untuk memproses crossover dan mutasinya sesuai dengan permasalahan yang dihadapi. Contohnya: Chromosome 1 : A B C D E F G Chromosome 2 : H I J K LM N
4.
Tree Encoding Tree Encoding biasanya digunakan pada genetic programming. Kromosom yang digunakan berupa sebuah tree dari beberapa objek, seperti fungsi atau command pada genetic programming.
Pengkodean bilangan riil adalah suatu pengkodean bilangan dalam bentuk riil. Masalah optimalisasi fungsi (Gen & Cheng, 2000) dan optimalisasi kendala (Eshelman & Schaffer, 1993) lebih tepat jika diselesaikan dengan pengkodean bilangan riil karena struktur topologi ruang genotif untuk pengkodean bilangan riil identik dengan ruang fenotifnya, sehingga sangat mudah untuk membentuk operator genetika yang efektif dengan cara menggunakan teknik yang berasal dari metode konvensional.
2.3. Operator dalam Algoritma Genetika Algoritma genetika adalah merupakan suatu proses pencarian yang heuristik dan acak sehingga penekanan pemilihan operator yang digunakan sangat menentukan keberhasilan
algoritma
genetika
dalam
menemukan
solusi
optimum
suatu
masalah yang diberikan. Hal yang harus diperhatikan adalah menghindari terjadinya konvergensi premature, yaitu mencapai solusi optimum yang belum waktunya, dalam arti bahwa solusi yang diperoleh adalah hasil optimum lokal.
Universitas Sumatera Utara
28
Operator genetika yang digunakan setelah proses evaluasi tahap pertama membentuk populasi baru dari generasi sekarang. Operator-operator tersebut adalah operator seleksi, crossover dan mutasi (Malhotra et al. 2011).
2.3.1. Operator Seleksi Seleksi memegang peranan yang sangat penting dalam keberhasilan algoritma genetika yaitu memilih kromosm-kromosom dalam populasi hingga didapatkan kromosom terbaik yang memiliki peluang yang lebih besar untuk dijadikan populasi awal. Seleksi bertujuan memberikan kesempatan reproduksi yang lebih besar bagi anggota populasi yang paling fit. Langkah pertama dalam seleksi ini adalah pencarian nilai fitness. Masing-masing individu dalam suatu wadah seleksi akan menerima probabilitas reproduksi yang tergantung pada nilai objektif dirinya sendiri terhadap nilai objektif dari semua individu dalam wadah seleksi tersebut. Kemampuan algoritma genetika untuk memproduksi kromosom yang lebih baik secara progresif tergantung pada penekanan selektif (selective pressure) yang diterapkan ke populasi. Penekanan selektif dapat diterapkan dalam dua cara. Cara pertama adalah membuat lebih banyak kromosom anak yang dipelihara dalam populasi dan memilih hanya kromosom-kromosom terbaik bagi generasi berikut. Walaupun orang tua dipilih secara acak, metode ini akan terus menghasilkan kromosom yang lebih baik berhubungan dengan penekanan selektif yang diterapkan pada individu anak tersebut. Menurut Sharma et al. (2014), ada beberapa metode untuk memilih kromosom yang sering digunakan antara lain adalah seleksi roda rolet (roulette wheel selection), seleksi ranking (rank selection) dan seleksi turnamen (tournament selection). Dalam penelitian ini, metode yang digunakan adalah seleksi roda rolet (roulette wheel selection), Pada seleksi ini, orang tua dipilih berdasarkan fitness mereka. Semakin baik kualitas suatu kromosom akan lebih besar peluangnya untuk terpilih. Probabilitas suatu individu terpilih untuk proses crossover sebanding dengan fitness-nya. Cara penyeleksian ini merupakan peniruan dari permainan roda rolet.
Universitas Sumatera Utara
29
2.3.2. Operator Crossover Crossover (perkawinan silang) bertujuan menambah keanekaragaman string dalam populasi dengan penyilangan antar string yang diperoleh dari sebelumnya. Beberapa jenis crossover tersebut adalah: 1. Crossover satu titik / one point crossover Pada crossover dilakukan dengan memisahkan suatu string menjadi dua bagian dan selanjutnya salah satu bagian dipertukarkan dengan salah satu bagian dari string yang lain yang telah dipisahkan dengan cara yang sama. Proses yang demikian dinamakan operator crossover satu titik seperti terlihat pada gambar 2.1. Tabel 2.1 Contoh Crossover satu titik Kromosom Orangtua 1
10101010
Kromosom Orangtua 2
11000111
Keturunan
10100111
2. Crossover dua titik/ two point crossover Proses crossover ini dilakukan dengan memilih dua titik crossover. Kromosom keturunan kemudian dibentuk dengan barisan bit dari awal kromosom sampai titik crossover pertama disalin dari orang tua pertama, bagian dari titik crossover pertama dan kedua disalin dari orang tua kedua, kemudian selebihnya disalin dari orangtua pertama lagi seperti terlihat pada gambar 2.2. Tabel 2.2 Contoh Crossover dua titik Kromosom Orangtua 1
10101010
Kromosom Orangtua 2
11000111
Keturunan
10100110
Universitas Sumatera Utara
30
3. Crossover seragam Crossover
seragam
manghasilkan
kromosom
keturunan
dengan
menyalin bit-bit secara acak dari kedua orang tuanya seperti terlihat pada gambar 2.3. Tabel 2.3 Contoh Crossover seragam Kromosom Orangtua 1
10101010
Kromosom Orangtua 2
11000111
Keturunan
11101111
2.3.3. Operator Mutasi Mutasi merupakan operator dalam algoritma genetika yang bertujuan untuk mengubah gen-gen tertentu dari sebuah kromosom. Mutasi merupakan sebuah proses dengan cara
mengubah
nilai
dari
satu
atau
beberapa
gen
dalam
suatu kromosom. Operasi crossover yang dilakukan pada kromosom dengan tujuan untuk memperoleh kromosom-kromosom baru sebagai kandidat solusi pada generasi mendatang dengan fitness yang lebih baik, dan lama-kelamaan menuju solusi optimum yang diinginkan. Akan tetapi, untuk mencapai hal ini, penekanan selektif juga memegang peranan yang penting. Jika dalam proses pemilihan kromosom-kromosom cenderung
pada kromosom
yang memiliki
fitness yang tinggi saja, konvergensi premature, yaitu mencapai solusi yang optimal lokal sangat mudah terjadi. Probabilitas mutasi dari suatu gen biasanya dipilih sangat kecil. Operasi mutasi merupakan operasi yang menyangkut satu kromosom tertentu. Beberapa cara operasi mutasi diterapkan dalam algoritma genetika menurut jenis pengkodean terhadap phenotype, antara lain : 1. Mutasi dalam pengkodean biner Mutasi pada pengkodean biner merupakan operasi yang sangat sederhana. Proses
yang
posisi
tertentu
dilakukan yang
terpilih
adalah
menginversi
secara acak
atau
nilai
bit
pada
menggunakan
skema
Universitas Sumatera Utara
31
tertentu pada kromosom, yang disebut inversi bit seperti terlihat pada tabel 2.4 dibawah ini. Tabel 2.4 Contoh Mutasi dalam pengkodean biner Kromosom sebelum mutasi
10101010
Kromosom setelah mutasi
11101010
2. Mutasi dalam pengkodean permutasi Proses
mutasi
yang
dilakukan
dalam
pengkodean
biner
dengan
mengubah langsung bit-bit pada kromosom tidak dapat dilakukan pada pengkodean
permutasi
diperhatikan.
Salah
karena
satu
cara
konsistensi yang
dapat
urutan
permutasi
dilakukan
adalah
harus dengan
memilih dua posisi (locus) dari kromosom dan kemudian nilainya saling dipertukarkan seperti terlihat pada tabel 2.5 dibawah ini. Tabel 2.5 Contoh Mutasi dalam pengkodean permutasi Kromosom sebelum mutasi
123456789
Kromosom setelah mutasi
153457789
3. Mutasi dalam pengkodean nilai Mutasi pada pengkodean nilai hampir sama dengan yang dilakukan pada pengkodean biner, tetapi yang dilakukan bukan menginversi nilai bit. Penerapannya
bergantung
pada
jenis
nilai
yang
digunakan.
Sebagai
contoh untuk nilai rill, proses mutasi dapat dilakukan seperti yang dilakukan pada pengkodean permutasi, dengan saling mempertukarkan nilai dua gen pada kromosom. Tabel 2.6 Contoh Mutasi dalam pengkodean nilai Kromosom sebelum mutasi
1,43 1,09 4,51 9,11 6,94
Kromosom setelah mutasi
1,43 1,19 4,51 9,11 6,84
Universitas Sumatera Utara
32
4. Mutasi dalam pengkodean pohon Mutasi dalam pengkodean pohon dapat dilakukan antara lain dengan cara mengubah operator (+, -, *, /) atau nilai yang terkandung pada suatu verteks pohon yang dipilih atau dapat juga dilakukan dengan memilih dua
verteks
dari
pohon
dan
saling
mempertukarkan
operator
atau
nilainya.
2.4.
Kontrol Parameter dalam Algoritma Genetika
Kontrol parameter dalam algoritma genetika merupakan salah satu bagian paling penting dalam penerapan algoritma genetika. Parameter ini diperlukan untuk mengendalikan operator-operator dalam algoritma genetika. Pemilihan parameter genetika menentukan penampilan kinerja algoritma genetika dalam memecahkan persoalan. Parameter dalam algoritma
genetika yang disarankan menurut De Jong
(Hopgood, 2001) adalah : 1. Probabilitas penyilangan cukup besar (berkisar 60 % sampai 70 %). 2. Probabilitas Mutasi cukup kecil (sebuah gen untuk sebuah kromosom). 3. Ukuran populasi berkisar antara 50 sampai 500 kromosom.
2.4.1. Probabilitas persilangan (crossover probability) Probabilitas crossover menyatakan seberapa sering proses crossover akan terjadi antara dua kromosom induk/orang tua. Dari hasil penelitian yang telah dilakukan sebelumnya menyatakan bahwa angka probabilitas crossover sebaiknya cukup tinggi, yaitu antara 80 % sampai dengan 95 % untuk memberikan hasil yang baik. Untuk beberapa masalah tertentu probabilitas crossover 60 % memberikan hasil yang lebih baik (Marek, 1998). Probability Crossover dapat digunakan dengan rumus sebagai berikut : Pc = Jumlah % x Banyaknya individu yang ada
Universitas Sumatera Utara
33
2.4.2. Probabilitas mutasi (mutation probability) Probabilitas mutasi menunjukkan seberapa sering gen-gen yang menyusun sebuah kromosom akan dimutasikan. Jika tidak terjadi mutasi atau probabilitas mutasi 0 % maka keturunan yang dihasilkan setelah crossover tidak akan berubah, dan jika terjadi mutasi pada bagian kromosom yang telah dipilih akan mengalami perubahan. Jika probabilitas 100 %, semua kromosom akan dilakukan mutasi dan keseluruhan kromosom akan berubah. Probabilitas dalam mutasi sebaiknya diberi nilai yang kecil. Probabilitas mutasi digunakan untuk mendapatkan rata-rata satu mutasi per kromosom yaitu angka/allele = 1 / (panjang kromosom). Dari hasil yang sudah pernah dicoba para peneliti yang menunjukkan bahwa angka probabilitas terbaik adalah 0,5 % - 1 % hal ini disebabkan oleh karena untuk menjaga perbedaan kromosom dalam populasi agar terhindar dari konvergensi premature. Probability Mutasi dapat digunakan dengan rumus sebagai berikut : Pm = Jumlah % x (Jumlah Individu x Banyaknya gen dalam 1 Individu)
2.4.3. Jumlah individu Jumlah individu yaitu banyaknya jumlah kromosom yang terdapat dalam satu populasi. Jika satu populasi hanya memiliki kromosom dengan junlah yang sedikit menyebabkan algoritma akan memiliki variasi yang akan diberikan pada proses crossover, sebaliknya jika terdapat jumlah kromosom dalam satu populasi yang terlalu banyak maka algoritma genetika akan berjalan lambat untuk menemukan solusi yang diharapkan. Ukuran populasi yang sering digunakan oleh para peneliti sebelumnya antara 20 – 30 kromosom, tetapi ada juga peneliti yang menggunakan 50 - 100 kromosom dengan hasil yang baik. Ukuran populasi yang terbaik adalah tergantung dari pengkodean yang dilakukan yaitu ukuran dari barisan yang dienkodekan.
2.4.4. Jumlah populasi
Universitas Sumatera Utara
34
Jumlah populasi yaitu banyaknya populasi atau banyaknya generasi yang akan dihasilkan yang digunakan sebagai batas akhir dari semua proses dalam algoritma genetika yaitu proses seleksi, proses crossover dan proses mutasi.
2.5.
Greedy Crossover
Metode Greedy Crossover (GX) adalah salah satu metode crossover atau perkawinan silang yang sangat spesifik yang diterapkan pada Algoritma Genetika selain dari metode-metode crossover klasik yang ada pada algoritma genetika tersebut. Metode Greedy Crossover ini pertama kali ditemukan oleh Grefenstette et al. (1985). Metode Greedy Crossover dapat diterapkan apabila semua gen yang terdapat dalam sebuah kromosom tersebut berbeda, dan susunan seluruh gen untuk kedua kromosom harus sama atau identik dan hanya bisa di order pada gen kromosom yang bervariasi, kedua kondisi tersebut selalu benar dan dapat diterapkan berkali-kali. Greedy crossover ini bekerja dengan membuang gen yang tidak sesuai atau tidak memenuhi kondisi yang diinginkan pada kromosom induk pertama / father dan menggantinya dengan gen yang lain pada kromosom induk kedua / mother. Metode Greedy Crossover memiliki prinsip yang sama dengan algoritma Greedy dan sesuai dengan namanya greedy dalam bahasa Indonesia berarti tamak atau rakus dan algoritma ini memiliki prinsip “Take what you can get now” yang berarti “mengambil apa yang bisa anda dapatkan sekarang”. Algoritma greedy adalah algoritma untuk menyelesaikan permasalahan secara bertahap (Brassard G, 1996). Tahap penyelesaiannya adalah: 1. Mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan. 2. Berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global. Sehingga dengan kata lain, dapat disimpulkan bahwa langkah dari algoritma greedy ini adalah mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan, atau dengan prinsip “take what you can get now”, berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global.
Universitas Sumatera Utara
35
Metode Greedy Crossover yang digunakan adalah dengan memilih kromosom pertama sebagai langkah awal dan melihat seluruh gen yang terdapat pada kromosom tersebut dari salah satu orang tua dan membandingkannya dengan orang tua kedua. Jika salah satu gen dalam kromosom orang tua pertama ada yang tidak baik atau tidak memenuhi syarat maka akan dipilih gen pada orang tua kedua. Pertukaran gen ini hanya terjadi pada posisi yang sama dengan gen yang rusak tersebut, proses seperti ini akan dilakukan secara berulang-ulang sampai kondisi berhenti terpenuhi. Prosedur dari greedy crossover ini merupakan prosedur penyesuaian lokal dan perbaikan pada sebuah kromosom . Dalam
pengimplementasiannya
metode greedy crossover menggunakan
beberapa elemen yaitu : 1. Himpunan Kandidat, (C). Himpunan ini berisi elemen-elemen pembentuk solusi 2. Himpunan Solusi, (S). Himpunan ini berisi kandidat yang terpilih sebagai solusi persoalan, atau himpunan bagian dari himpunan kandidat. 3. Fungsi seleksi Fungsi seleksi merupakan fungsi yang ada pada setiap langkah memilih kandidat yang paling memungkinkan guna mencapai solusi optimal. 4. Fungsi Kelayakan (Feasible) Fungsi kelayakan adalah fungsi yang memeriksa apakah suatu kandidat yang telah terpilih dapat memberikan solusi yang layak dan tidak melanggar batasan atau constraints yang ada.
2.6. Optimalisasi Rostering Mata Pelajaran 2.6.1. Pengertian Optimalisasi Optimalisai merupakan suatu upaya sistematis untuk memilih elemen terbaik dari suatu kelompok atau kumpulan yang ada. Optimalisasi didalam konteks matematika dapat dinyatakan sebagai usaha sistematis untuk mencari nilai minimum atau
Universitas Sumatera Utara
36
maksimum dari suatu fungsi. Optimalisasi ini dipakai hampir disemua bidang keilmuan antara lain bidang teknik, ilmu sosial, sains, ekonomi, bisnis maupun dibidang pendidikan. Banyak permasalahan dalam bidang-bidang tersebut yang dapat dinyatakan sebagai permasalahan optimalisassi seperti meminimalkan biaya, mempersingkat waktu, memaksimalkan keuntungan dan kualitas. Optimalisasi merupakan proses dalam mencari nilai yang terbaik berdasarkan fungsi tujuan dengan daerah asal yang telah didefenisikan. Pengertian Optimalisasi menurut Kamus Besar Bahasa Indonesia (Depdikbud, 1995) yaitu optimalisasi berasal dari kata optimal yang berarti terbaik, tertinggi jadi optimalisasi adalah suatu proses meninggikan atau meningkatkan. Optimalisai banyak juga diartikan sebagai ukuran dimana semua kebutuhan dapat dipenuhi dari kegiatan-kegiatan yang dilaksanakan. Berdasarkan uraian diatas optimalisasi dapat diartikan sebagai serangkaian proses secara sistematis yang dilakukan dengan metode yang paling baik dalam suatu pekerjaan dengan harapan dapat meningkatkan kualitas dari pekerjaan tersebut secara efektif dan efisien.
2.6.2. Rostering/Penjadwalan Mata Pelajaran Pembuatan jadwal mata pelajaran merupakan salah satu bagian yang paling penting agar terlaksananya proses belajar mengajar dengan baik, efektif dan efisien pada suatu lembaga pendidikan formal. Penjadwalan adalah kegiatan pengalokasian sumbersumber atau mesin-mesin yang ada untuk menjalankan sekumpulan tugas dalam jangka waktu tertentu (Baker, 1974). Penjadwalan juga didefinisikan sebagai rencana pengaturan urutan kerja serta pengalokasian sumber, baik waktu maupun fasilitas untuk setiap operasi yang harus diselesaikan (Vollman, 1998). Penjadwalan mata pelajaran merupakan proses penyusunan jadwal pelaksanaan yang menginformasikan sejumlah mata pelajaran, guru yang mengajar, ruang, serta waktu kegiatan belajar mengajar. Pada umumnya penyusunan jadwal mata pelajaran dilakukan secara manual, yaitu dengan mencari kolom mana saja yang masih kosong, kemudian menempatkan jadwal pada kolom tersebut. Suatu jadwal di sekolah akan sulit untuk dibuat dengan cara seperti ini jika jumlah kelas dan siswa yang tersedia dalam sekolah tersebut terbatas dan jumlah tenaga pengajar/guru yang tersedia sangat
Universitas Sumatera Utara
37
banyak. Untuk menyusun jadwal mata pelajaran yang baik, pembuat jadwal perlu memperhatikan berbagai aspek yang mempengaruhi jadwal mata pelajaran tersebut. Dari aspek guru, pembuat jadwal perlu memperhatikan kemungkinan guru yang bersangkutan hanya ingin mengajar suatu mata pelajaran pada hari dan jam tertentu. Pembuat jadwal juga harus memperhatikan keterbatasan guru pengajar yang dimiliki oleh sekolah. Pembuat jadwal juga perlu memperhatikan dari aspek mata pelajaran yang diajarkan. Sebagai contoh, mata pelajaran matematika seharusnya diajarkan 4 jam dalam seminggu dengan maskimal 2 jam dalam satu hari. Selain itu, pembuat jadwal juga perlu memperhatikan bahwa jadwal yang dibuat tidak ada bentrokan jam antar pengajar satu dengan pengajar yang lain dalam satu waktu dan kelas tertentu, atau satu pengajar yang berada di lebih dari satu kelas pada satu waktu tertentu. Berdasarkan aspek-aspek di atas, seharusnya jadwal yang disusun dapat menjadi solusi sehingga tidak ada bentrokan jadwal pengajar, mata pelajaran, atau kelas yang terjadi, dan tentunya memenuhi persyaratan kegiatan belajar yang sudah ditentukan. Oleh karena itu dibutuhkan metode optimasi yang dapat diterapkan untuk menyusun jadwal mata pelajaran. Dalam penelitian ini akan dilakukan optimalisai penjadwalan mata pelajaran dengan menggunakan dan menganalisa metode-metode yang heuristik, dimana permasalahan yang akan dijadikan objek penelitian yaitu masalah optimalisasi pada penjadwalan mata pelajaran di SMP Negeri 5 Pematangsiantar, dimana penyusunan jadwal mata pelajaran di sekolah tersebut yang dilakukan setiap memasuki tahun ajaran baru selalu mengalami beberapa kendala terkait dengan pengelolaan penjadwalan yang masih dilakukan secara manual menggunakan program Microsoft Excel, hal tersebut sangat tidak efektif karena prosesnya membutuhkan waktu yang lama dan informasi yang dihasilkan tidak akurat, sehingga banyak para guru yang merasa kecewa atas jadwal mengajar mereka oleh karena banyak terjadi kesalahan didalam jadwal tersebut, seperti seorang guru masuk dikelas yang berbeda pada hari dan jam yang sama, seorang guru masuk di kelas yang sama pada hari yang berbeda. Hal seperti ini selalu terjadi pada saat tahun ajaran atau diawal semester. Peristiwa ini terjadi karena beberapa faktor yaitu banyaknya jumlah tenaga pendidik yang tersedia sementara jumlah ruangan kelas dan peserta didik yang terbatas serta banyaknya
Universitas Sumatera Utara
38
permintaan guru yang tidak bisa masuk untuk mengajar di hari-hari tertentu. Sehingga hal ini sangat menyulitkan bagi pegawai yang bekerja dibagian kurikulum.
2.7. Penelitian Terdahulu Dalam melakukan penelitian, penulis menggunakan beberapa penelitian yang relevan dengan permasalahan yang diteliti yang digunakan sebagai acuan agar penelitian ini berjalan dengan lancar. Algoritma genetika sering terjadi konvergen prematur dalam mencari daerah global optimum (Xinyang, 2011). Algoritma genetika memiliki kelemahan dalam menyelesaikan penjadwalan mata kuliah yaitu sering terjebak pada nilai optimum lokal (Sivanandan, 2008). Ongko (2015) melakukan analisis keterkaitan jumlah gen yang mengalami crossover terhadap kinerja algoritma genetika. Penelitian dilakukan dengan membandingkan whole arithmetic crossover, simple arithmetic dan single arithmatic crossover. Hasil penelitian menunjukkan bahwa semakin banyak gen yang terlibat dalam proses crossover akan meningkatkan kinerja algoritma genetika. hasil lainnya menyatakan bahwa whole arithmetic crossover lebih baik daripada simple arithmetic dan single arithmatic crossover. Ismkhan & Zamanifar (2012) melakukan penelitian dengan dilatarbelakangi bahwa metode greedy crossover klasik lambat dan tidak begitu akurat. Penelitiannya dilakukan dengan pengembangan atas metode greedy crossover untuk meningkatkan kinerja algoritma genetika. Hasil yang diperoleh menunjukkan peningkatan kinerja algoritma
dengan
kompleksitas
waktu
O(n).
Algoritma
greedy
yang
diimplementasikan ke dalam perangkat lunak dapat digunakan untuk menyelesaikan knapsack problem pada dunia transportasi dengan waktu yang lebih cepat dibandingkan dengan menggunakan perhitungan manual dan algoritma brute force (Rachmawati & Candra, 2013). Algoritma greedy adalah salah satu metode yang praktis dalam mencari solusi yang baik pada masalah Traveling Salesman Problem, algoritma ini menghasilkan semua daftar titik dalam grafik dari biaya yang terkecil sampai dengan biaya terbesar (Zoubi & Salam, 2014).
Universitas Sumatera Utara
39
Tabel. 2.7. Penelitian yang relevan No
1.
Nama dan
Metode yang
Tahun Peneliti
Digunakan
Hasil Penelitian
Sallabi dan
Genetic
Mereka
melakukan
El-Haddad
Algorithmn
metode crossover yang disebut dengan
(2009)
hybrid
swapped
inverted
modifikasi
pada
crossover
(SIC),
kemudian melakukan multi mutation operation dan terakhir menambahkan metode partial local mutation operation. Hasil
yang
diperoleh
menunjukkan
peningkatan kinerja algoritma genetika. 2.
3.
Ismkhan
dan Genetic
Zamanifar
Algorithmn
(2012)
and
Penelitiannya pengembangan
dilakukan atas
metode
dengan greedy
Greedy crossover untuk meningkatkan kinerja
Crossover
algoritma genetika pada kasus TSP.
Rachmawati
Greedy
Algoritma
dan
Algorithmn
diimplementasikan ke dalam perangkat
(2013)
Candra,
lunak
greedy
dapat
digunakan
yang
untuk
menyelesaikan knapsack problem pada dunia transportasi dengan waktu yang lebih cepat.
Universitas Sumatera Utara
40
Tabel. 2.7. Penelitian yang relevan (Lanjutan) No
4.
Nama dan
Metode yang
Tahun Peneliti
Digunakan
Zoubi
dan Genetic
Salam (2014)
Hasil Penelitian
Dari hasil penerapannya Algoritma
Algorithmn and GA-Greedy digunakan sangat praktis Greedy
dalam mencari pendekatan dinamis dan
Algorithmn
statis
pada
crossover
dalam
masalah
Traveling
menyelesaikan
Salesman Problem. 5.
Ongko (2015)
Genetic
Penelitian
dilakukan
Algorithmn
membandingkan
whole
dengan arithmetic
crossover, simple arithmetic dan single arithmatic crossover. Hasil penelitian menunjukkan bahwa semakin banyak gen
yang
terlibat
dalam
proses
crossover akan meningkatkan kinerja algoritma
genetika.
hasil
lainnya
menyatakan bahwa whole arithmetic crossover lebih baik daripada simple arithmetic
dan
single
arithmatic
crossover.
6.
Otman
dan Genetic
Jaafar (2011)
Algorithmn
Penelitian
yang
dilakukan
dengan
membandingan enam metode crossover pada
dataset
TSPBERLIN52
yang
menyatakan bahwa metode ordered crossover merupakan metode yang lebih baik dari pada metode crossover klasik.
Universitas Sumatera Utara
