penerapan algoritma genetika pada penjadwalan mata kuliah
DESCRIPTION
Proposal Tugas Akhir Mery HanitaTRANSCRIPT
PENERAPAN ALGORITMA GENETIKA PADA PENJADWALAN MATA KULIAH
(Studi Kasus: Program Studi Matematika FMIPA Universitas Bengkulu)
PROPOSALTUGAS AKHIR
Oleh
MERY HANITAF1A007050
JURUSAN MATEMATIKAFAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS BENGKULU2011
1
KATA PENGANTAR
Segala puji hanya milik Allah SWT yang telah memahatkan dawai cinta-Nya di
seluruh jagat raya, berdenting menebarkan orkestra kedamaian keseluruh penjuru,
sehingga penulis dapat menyelesaikan penulisan skripsi yang yang berjudul
PENERAPAN ALGORITMA GENETIKA PADA PENJADWALAN MATA
KULIAH (Studi Kasus: Program Studi Matematika FMIPA Universitas
Bengkulu), untuk memenuhi salah satu syarat memperoleh gelar Sarjana Sains Program
Studi Matematika Universitas Bengkulu. Shalawat dan salam disenandungkan untuk
kekasih-Nya Muhammad SAW yang telah memainkan dawai cinya-Nya dan
memperdengarkan kepada seluruh makhluk di alam semesta, sehingga mereka
merasakan sentuhan halus dari simfoni Allah dalam kehidupannya. Skripsi ini di
Penulis menyadari sepenuhnya bahwa dalam melaksanakan penelitian sampai
terwujudnya skripsi ini telah banyak mendapatkan pengetahuan, bimbingan, pengarahan
dan bantuan dari berbagai pihak baik secara langsung maupun tidak langsung, baik
secara moril maupun materil. Untuk itu pada kesempatan ini penulis mengucapkan
terima kasih kepada:
1. Bapak Drs. Rizwar, M.S. selaku Dekan Fakultas Matematika dan Ilmu
Pengetahuan Alam Universitas Bengkulu
2. Bapak Drs. Mudin Simanihuruk, M.Sc, Ph.D selaku Ketua Jurusan
Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas
Bengkulu.
3. Bapak Drs. Fanani Haryo Widodo, M.Sc selaku Dosen Pembimbing
Utama yang telah banyak meluangkan waktu dalam penulisan skripsi ini.
i
4. Ibu Zulfia Memi Mayasari, S.Si, M.Si selaku Dosen Pembimbing
Pendamping yang telah meluangkan waktu dalam memberikan bimbingan,
arahan, motivasi, dan masukan dalam penulisan skripsi ini.
5. Bapak Drs. Syahrul Akbar, M.Pd. dan Bapak Jose Rizal, S.Si, M.Si.
selaku Dosen Penguji yang telah memberikan masukan dan saran dalam
penulisan skripsi ini.
6. Ibu Dra. Baki Swita, M.Sc selaku pembimbing akademik yang selalu
memberikan dukungan dan masukan.
7. Bapak dan Ibu Dosen Jurusan Matematika yang telah memberikan ilmu
pengetahuan kepada penulis.
8. Staf-staf Administrasi di Fakultas Matematika dan Ilmu Pengetahuan Alam.
9. Ayah dan ibu yang selalu mendoakan, memberikan motivasi serta rasa cinta
dan sayang, perhatian dan semua yang terbaik untukku. Adik-adikku (Tia
dan Manda) yang senantiasa memberikanku semangat agar terus berjuang
mencapai yg kuinginkan. Keep Hamasah Bu Guru PAUD dan Pak Guru
BK.
10. Marshmallow (Yati, Febri, Vie, Gusti, Dale’).
11. Anak matematika B angkatan ‘07(Yati, Febri, Nora, Vie, Gusti, Dale’,
Dephe, Hilda, Anton, Aldy, Hendri, Kak Hengki, Mashurdi, Serly, Lundu,
Hengki Primadona, Azhari).
12. Anak OR (Yati, Febri, Nora, Vie, Dephe, Anton, Aldy, Hendri, Lundu,
Hengki Primadona, Azhari, Dona, Dewi, Heni, Clara, Eti, Fitri, Doly, Oon).
13. Rekan-rekan di GSI (eti, rani, pera, mba galih, mba mimi, ayu’ sure).
14. Kak ardi, kak agus, kak ipung, eko.
ii
15. Teman-teman KKN Ujung Karang (Bayu, Ryan, Abang Diko, Nina, Ratna,
Ima).
16. Rekan-rekan Matematika ’07, ’08, ’09, ’10, ’11.
17. Semua pihak yang telah membantu dalam penyelesaian skripsi ini, yang
tidak dapat penulis sebutkan satu persatu.
Semoga Allah memberikan pahala yang berlipat ganda atas segala bantuan dan
kemurahan hati semua pihak yang telah membantu penulis dalam menyelesaikan skripsi
ini. Penulis menyadari bahwa penyajian skripsi ini masih jauh dari sempurna, untuk itu
kritik dan saran yang sifatnya membangun sangat penulis harapkan. Semoga skripsi ini
dapat bermanfaat bagi kita semua sebagai sumbangan ilmu pengetahuan baik dimasa
sekarang maupun dimasa yang akan datang. Aamiin…
Bengkulu, Oktober 2011
Penulis
iii
DAFTAR ISI
Halaman
HALAMAN JUDUL ............................................................................................... i
KATA PENGANTAR.............................................................................................. ii
DAFTAR ISI ............................................................................................................ iv
BAB I PENDAHULUAN
1.1 Latar Belakang ........................................................................................ 1
1.2 Perumusan Masalah ................................................................................ 4
1.3 Batasan Masalah ..................................................................................... 4
1.4 Tujuan Penelitian .................................................................................... 5
1.5 Manfaat Penulisan ................................................................................... 5
1.6 Sistematika Penulisan ............................................................................. 5
BAB II TINJAUAN PUSTAKA
2.1 Permasalahan Optimasi ........................................................................... 7
2.2 Penjadwalan Mata Kuliah ....................................................................... 8
2.3 Algoritma Genetika ................................................................................. 10
2.3.1 Pengertian Algoritma Genetika .................................................... 11
2.3.2 Struktur Umum Algoritma Genetika ............................................ 12
2.3.3 Komponen-komponen Utama Algoritma Genetika ..................... 16
1. Teknik Pengkodean ................................................................. 16
2. Prosedur Inisialisasi ................................................................ 16
3. Fungsi Evaluasi ....................................................................... 16
4. Seleksi ..................................................................................... 17
5. Operator Genetika ................................................................... 18
6. Parameter Kontrol .................................................................. 21
2.4 Penelitian Penjadwalan Mata Kuliah dan Algoritma Genetika
yang Pernah Dilakukan .......................................................................... 22
BAB III METODE PENELITIAN
iv
3.1 Jenis Penelitian ........................................................................................... 24
3.2 Waktu dan Tempat .................................................................................. 24
3.3 Data yang diperlukan .............................................................................. 24
3.4 Teknik Pengumpulan Data ...................................................................... 25
3.5 Analisis Data ........................................................................................... 25
DAFTAR PUSTAKA
v
BAB I
PENDAHULUAN
1.1 Latar Belakang
Salah satu masalah penjadwalan yang umum dijumpai di perguruan tinggi adalah
masalah penjadwalan mata kuliah. Penjadwalan mata kuliah merupakan proses
penyusunan jadwal pelaksanaan yang menginformasikan sejumlah mata kuliah yang
diberikan, dosen yang mengajar, ruang tempat belajar, waktu serta mahasiswa yang
mengambil mata kuliah tersebut. Di setiap semester, beberapa universitas menghadapi
permasalahan yang sama, yaitu bagaimana menjadwalkan mata kuliah dengan kendala
waktu, dosen yang tersedia, kapasitas ruangan yang terbatas, dan mahasiswa yang
mengambil mata kuliah, dimana proses penjadwalan tersebut tetap memperhatikan
sejumlah batasan dan syarat-syarat tertentu.
Untuk menyusun jadwal mata kuliah yang baik kita perlu memperhatikan
berbagai aspek yang mempengaruhi penjadwalan mata kuliah. Dari aspek dosen, kita
perlu memperhatikan kemungkinan dosen yang bersangkutan tidak dapat mengajar
karena kegiatan akademik yang lain, dosen mengajar lebih dari satu mata kuliah pada
hari dan jam yang sama serta dosen sudah memiliki jadwal mengajar di jurusan lain.
Peneliti juga perlu memperhatikan dari aspek mahasiswa ada atau tidaknya jadwal mata
kuliah yang beririsan dengan jadwal kuliah angkatan sebelumnya maupun sesudahnya
sehingga mahasiswa dapat mengambil mata kuliah angkatan sebelumnya maupun
sesudahnya. Selain itu, perlu diperhatikan juga dari aspek ketersediaan ruangan belajar
dan ruang praktikum pada mata kuliah yang berpraktikum agar proses perkuliahan
1
dapat terlaksana. Berdasarkan aspek-aspek di atas, dalam penyusunan jadwal kuliah
terdapat banyak kemungkinan yang dapat dicoba untuk menemukan penjadwalan yang
2
baik. Oleh karena itu dibutuhkan metode optimasi yang dapat diterapkan untuk
mengerjakan penjadwalan mata kuliah.
Masalah optimasi dapat diselesaikan dengan beberapa cara, salah satunya dengan
menggunakan algoritma pencarian heuristik. Untuk kasus yang sederhana digunakan
algoritma pencarian heuristik yang biasa seperti breadth-first search and depth-first
search. Untuk input dan persyaratan yang lebih rumit seperti pada kasus penjadwalan
mata kuliah, algoritma pencarian heuristik sudah tidak dapat digunakan dengan baik
untuk mendapatkan solusi yang diinginkan. Dalam kasus penjadwalan mata kuliah,
diperlukan algoritma yang lebih baik yaitu algoritma yang dapat menyelesaikan
masalah multi-kriteria dan multi-objektif. Salah satu algoritma yang dapat digunakan
adalah algoritma genetika.
Ada tiga keunggulan dari aplikasi algoritma genetika dalam proses optimasi
(Sanjoyo, 2006) yaitu:
a. Algoritma genetika tidak terlalu banyak memerlukan persyaratan matematika dalam
penyelesaian proses optimasi. Algoritma genetika dapat diaplikasikan pada beberapa
jenis fungsi obyektif dengan beberapa fungsi pembatas baik berbentuk linier maupun
non-linier.
b. Operasi evolusi dari algoritma genetika sangat efektif untuk mengobservasi posisi
global secara acak.
c. Algoritma genetika mempunyai fleksibilitas untuk diimplementasikan secara efisien
pada problematika tertentu.
Proses evolusi menjadi ciri spesifik dari algoritma genetika, suatu proses seleksi
alamiah yang berdasarkan prinsip genetika dan pemilihan alami pada individu secara
terus-menerus mengalami perubahan gen untuk menyesuaikan dengan lingkungan
2
hidupnya, sehingga terseleksi individu-individu yang kuat yang mampu bertahan
sebagai hasil optimal (Basuki, 2003; Haupt, 2004). Algoritma genetika dapat digunakan
untuk menyelesaikan permasalahan optimisasi yang rumit (hard optimization problems)
yang tidak dapat diselesaikan dengan teknik optimasi tradisional seperti masalah
penjadwalan, transportasi, permainan komputer, traveling salesman problem (TSP), dan
lain-lain.
Perbedaan algoritma genetika dengan algoritma pencarian lainnya, antara lain
(Goldberg, 1989):
a. Algoritma genetika secara langsung bekerja dengan string yang mempresentasikan
kumpulan parameter.
b. Algoritma genetika menggunakan keputusan probabilistik (non deterministik) dalam
pencarian solusinya.
Ciri-ciri permasalahan yang dapat dikerjakan dengan menggunakan algoritma
genetika adalah (Basuki, 2003):
a. Mempunyai fungsi tujuan optimalisasi non linear dengan banyak kendala yang juga
non linear.
b. Mempunyai kemungkinan solusi yang jumlahnya banyak.
c. Membutuhkan solusi “real-time” dalam arti solusi dapat diperoleh dengan cepat.
d. Mempunyai multi-objektif dan multi-kriteria.
Algoritma genetika merupakan pendekatan komputasional untuk menyelesaikan
masalah yang dimodelkan dengan proses biologi dari evolusi. Diharapkan dengan
digunakannya algoritma genetika akan diperoleh optimasi penjadwalan mata kuliah
dimana terjadi kombinasi terbaik untuk pasangan mata kuliah dan dosen pengajar secara
keseluruhan, serta tidak ada permasalahan jadwal yang beririsan.
3
Berdasarkan uraian di atas, penulis ingin mengambil topik yang berkaitan dengan
penjadwalan mata kuliah dan algoritma genetika dengan judul PENERAPAN
ALGORITMA GENETIKA PADA PENJADWALAN MATA KULIAH (Studi Kasus
Program Studi Matematika FMIPA Universitas Bengkulu).
1.2 Perumusan Masalah
Berdasarkan latar belakang masalah, disusun perumusan permasalahan yaitu
bagaimana menyelesaikan permasalahan penjadwalan mata kuliah dengan algoritma
genetika sehingga diperoleh kombinasi terbaik untuk pasangan mata kuliah dan dosen
pengajar.
1.3 Batasan Masalah
Agar penelitian ini lebih terarah, penelitian dilakukan pada penjadwalan mata
kuliah di Program Studi Matematika FMIPA Universitas Bengkulu pada semester ganjil
Tahun Akademik 2011/2012. Dalam proses penyelesaian masalah penjadwalan mata
kuliah terdapat batasan-batasan yang harus dipenuhi. Batasan-batasan yang harus
dipenuhi tersebut antara lain:
a. Dosen dapat mengajar lebih dari satu mata kuliah dan tidak boleh terjadi irisan pada
jadwal dosen tersebut.
b. Satu mata kuliah dapat diajarkan oleh dua orang dosen atau lebih.
c. Terdapat mata kuliah tertentu yang menggunakan ruang laboratorium yang harus
dijadwalkan pada ruang laboratorium.
d. Hari aktif perkuliahan Senin sampai Jum’at.
e. Untuk semua mata kuliah baik 2 SKS, 3 SKS ataupun 4 SKS dijadwalkan 1 kali
pertemuan dalam seminggu.
4
f. Terdapat 7 kelas yang merupakan kelompok kelas mata kuliah, dimana untuk
semester 1 hanya 1 kelas, semester 3 dan 5 terdapat 2 kelas (A dan B), dan semester
7 terdapat 2 kelas (Matematika dan Statistika).
1.4 Tujuan Penelitian
Tujuan dalam skripsi ini adalah untuk mengetahui penerapan algoritma genetika
pada masalah penjadwalan mata kuliah sehingga diperoleh kombinasi terbaik untuk
pasangan mata kuliah dan dosen pengajar.
1.5 Manfaat Penelitian
Manfaat yang dapat diperoleh dari penelitian ini adalah:
a. Bagi Peneliti, dapat meningkatkan pemahaman tentang penggunaan algoritma
genetika dalam penjadwalan mata kuliah.
b. Bagi Program Studi Matematika, program yang dihasilkan diharapkan dapat
dikembangkan lebih lanjut untuk membantu menyelesaikan masalah penjadwalan
mata kuliah secara komputerisasi.
1.6 Sistematika Penulisan
Adapun sistematika dari penulisan skripsi ini adalah:
BAB I : PENDAHULUAN
Berisi latar belakang, perumusan masalah, batasan masalah, tujuan
penelitian, manfaat penulisan, dan sistematika penulisan.
BAB II : TINJAUAN PUSTAKA
Menjelaskan beberapa teori dan pengertian yang melandasi penelitian
yang berhubungan dengan analisis yang dilakukan.
5
BAB III : METODE PENELITIAN
Menjelaskan sumber data dan metode yang digunakan dalam
menganalisis data.
BAB IV :nHASIL DAN PEMBAHASAN
Menjelaskan hasil dan pembahasan yang dilakukan penulis dalam
penelitian ini.
BAB V : KESIMPULAN
Merupakan bab yang berisi kesimpulan dan saran.
6
BAB II
TINJAUAN PUSTAKA
2.1 Permasalahan Optimasi
Optimasi adalah salah satu disiplin ilmu dalam matematika dengan tujuan
mendapatkan nilai minimum atau maksimum secara sistematis dari suatu fungsi,
peluang, maupun pencarian nilai dalam berbagai kasus. Aplikasi dari teknik optimasi
telah banyak pada berbagai bidang secara cepat. Keberhasilan penerapan teknik
optimasi memerlukan tiga syarat, yaitu: kemampuan membuat model matematika dari
permasalahan yang dihadapi, pengetahuan akan program komputer dan pengetahuan
akan teknik optimasi itu sendiri.
Masalah optimasi dapat dikategorikan ke dalam dua kelas besar, yaitu optimasi
tanpa pembatas (unconstrained optimization) dan optimasi dengan pembatas
(constrained optimization). Optimasi tanpa pembatas merupakan optimasi yang hanya
melibatkan fungsi tujuan, tidak ada pembatas (constraint), sedangkan optimasi dengan
pembatas, selain fungsi tujuan juga mempunyai tambahan pembatas yang membuat
permasalahan lebih rumit. Dalam constrained optimization, dengan adanya pembatas
diperlukan algoritma yang berbeda untuk menyelesaikannya.
Prosedur pemecahan masalah optimasi dilakukan dengan cara memodelkan
persoalannya ke dalam sebuah program matematis dan kemudian memecahkannya
dengan menggunakan teknik-teknik atau metode optimasi seperti program linier,
program nonlinier, program tujuan ganda, dan metode-metode lainnya yang sudah
berkembang saat ini. Dalam penelitian ini akan menggunakan metode algoritma
genetika untuk menyelesaikan persoalan optimasi. Permasalahan optimasi telah banyak
7
diselesaikan dengan menggunakan algoritma genetika, dan hasil yang diperoleh
biasanya lebih baik, walaupun tidak menutup kemungkinan bahwa ada juga hasil akhir
yang kurang begitu memuaskan (Desiani, 2006).
2.2 Penjadwalan Mata Kuliah
Penjadwalan merupakan proses untuk menyusun suatu jadwal atau urutan proses
yang diperlukan dalam sebuah permasalahan. Permasalahan penjadwalan biasanya
berhubungan dengan penjadwalan kelas dalam sekolah atau perkuliahan dan juga dalam
lingkup yang tidak jauh berbeda seperti penjadwalan pelajaran sekolah, penjadwalan
ujian, atau dapat juga penjadwalan karyawan, baik dalam suatu perusahaan ataupun
dalam rumah sakit. Dalam penjadwalan kuliah, yang dibahas adalah tentang pembagian
jadwal untuk tiap mahasiswa pada kuliah tertentu sekaligus dosen pengajarnya. Dalam
penjadwalan pelajaran sekolah yang dibahas adalah tentang pembagian jadwal pelajaran
untuk tiap-tiap kelas yang ada beserta guru pengajar pelajaran tersebut, sedangkan
dalam penjadwalan ujian yang dibahas adalah tentang pengaturan dosen yang
mengawasi ujian dan mahasiswa yang menempati ruang.
Penjadwalan mata kuliah (lecture timetabling) di universitas merupakan suatu
pekerjaan yang tidak mudah. Permasalahan tersebut sering disebut dengan University
Timetabling Problems (UTP). Penjadwalan mata kuliah merupakan proses pengaturan
jadwal dengan memperhatikan dosen, ruang kelas, mata kuliah dan waktu yang
disesuaikan dengan sejumlah batasan tertentu. Pada penjadwalan mata kuliah sejumlah
mata kuliah harus dijadwalkan ke dalam ruang dan slot (pembagian) waktu tertentu
dimana penjadwalan tersebut memperhatikan aturan-aturan dan batasan penjadwalan
yang telah ditentukan. Berikut ini diberikan gambar komponen yang mempengaruhi
penjadwalan mata kuliah:
8
Gambar 2.1. Komponen yang Mempengaruhi Penjadwalan Mata Kuliah
Berdasarkan Gambar 2.1, penjadwalan mata kuliah dipengaruhi oleh beberapa
komponen yang terdiri atas: dosen, ruang kelas, mata kuliah, laboratorium dan waktu
dengan sejumlah batasan-batasan tertentu, dimana batasan-batasan tersebut ada yang
harus dipenuhi atau tidak boleh dilanggar. Batasan tersebut merupakan ukuran kualitas
dari penjadwalan mata kuliah, sehingga suatu jadwal mata kuliah yang optimal dapat
terbentuk.
Terdapat dua batasan dalam penyusunan penjadwalan kuliah yang dikemukakan
oleh Burk dkk (1997), yaitu : hard constraint (harus terpenuhi) dan soft constraint
(diupayakan untuk terpenuhi).
Hard constraints merupakan batas-batas yang harus diterapkan pada penjadwalan
mata kuliah dan harus dipenuhi. Sebuah solusi hanya dapat dikatakan sahih dan valid
9
apabila dalam solusi tersebut sama sekali tidak ada hard constraint yang terlanggar.
Hard constraints yang umum dalam penjadwalan mata kuliah adalah sebagai berikut :
a. Seorang dosen hanya dapat mengajarkan mata kuliah untuk satu lokasi pada waktu
tertentu.
b. Seorang mahasiswa hanya dapat mengikuti kuliah untuk satu lokasi pada waktu
tertentu.
c. Sebuah lokasi (ruangan) hanya dapat digunakan untuk satu mata kuliah pada waktu
tertentu.
d. Mata kuliah dengan bobot 3 SKS dijadwalkan dengan satu kali pertemuan dalam
seminggu.
e. Hari aktif untuk perkuliahan adalah hari Senin sampai dengan Sabtu.
Berbeda dengan hard constraint, soft constraint merupakan kendala yang tidak
selalu dapat terpenuhi dalam proses pembentukan jadwal, akan tetapi meskipun tidak
harus terpenuhi, jadwal yang dihasilkan harus semaksimal mungkin berusaha memenuhi
ketentuan soft constraint. Contoh soft constraints dalam penjadwalan mata kuliah antara
lain :
a. Dosen dapat meminta waktu mengajar tertentu yang diinginkan.
b. Penempatan jadwal untuk waktu yang telah diminta dosen disesuaikan dengan
prioritas dosen.
2.3 Algoritma Genetika
Algoritma genetika pertama kali ditemukan oleh John Holland pada tahun 1975
melalui sebuah penelitian dari Universitas Michigan yang kemudian dikembangkan
oleh muridnya David Goldberg pada tahun 1989. Awalnya tujuan Holland adalah bukan
untuk merancang algoritma yang mampu memecahkan masalah yang spesifik,
10
melainkan hanya untuk mempelajari fenomena adaptasi seperti yang terjadi di alam
sekaligus untuk mengembangkan cara-cara bagaimana mekanisme adaptasi alam dapat
diimpor ke sebuah sistem komputer. John Holland dalam bukunya yang berjudul
Adaptation In Natural And Artificial Systems, menyatakan bahwa setiap masalah yang
berbentuk adaptasi (alami maupun buatan) dapat diformulasikan dalam terminologi
genetika. Untuk memahami algoritma genetika diperlukan 3 tahapan pendalaman yaitu:
aspek filosofis, struktur dan komponen.
2.3.1 Makna Filosofis Algoritma Genetika
Menurut Lawrence (1991), Algoritma Genetika adalah algoritma kecerdasan
buatan tentang teknik pencarian dan optimasi yang berdasarkan pada mekanisme seleksi
atau evolusi yang terjadi di alam. Algoritma genetika merupakan salah satu cabang dari
algoritma evolusi yang digunakan untuk memecahkan masalah optimasi yang kompleks
dan sulit diselesaikan dengan menggunakan metode yang konvensional (tradisional).
Algoritma ini didasarkan pada proses genetika yang ada dalam makhluk hidup; yaitu
perkembangan populasi yang alami, secara lambat laun mengikuti proses seleksi alam
atau Siapa yang kuat, dia yang bertahan (survive). Prinsip pengerjaan algoritma
genetika adalah Survival Of The Fittest (kemampuan kelangsungan hidup) dengan
pemecahan yang berbeda dalam sebuah solusi. Pemecahan terbaik yang diperoleh dari
bentuk baru diharapkan merupakan pemecahan yang terbaik dari populasi, sedangkan
pemecahan yang kurang baik dihilangkan. Survival dalam algoritma genetika
merupakan suatu pewarisan genetik yang dijadikan sebagai model metode pencarian
pada suatu fenomena alam. Dengan meniru teori evolusi, algoritma genetika dapat
digunakan untuk mencari solusi yang tepat pada permasalahan-permasalahan optimasi
dalam dunia nyata baik satu variabel maupun multivariabel seperti pada permasalahan
11
penjadwalan, Travelling Salesman Problem (TSP), perancangan neural networks
(jaringan syaraf tiruan), dan Job Shop Scheduling.
2.3.2 Struktur Umum Algoritma Genetika
Secara garis besar algoritma genetika memiliki banyak kesamaan dengan
mekanisme genetika alami, baik dalam tahapan prosesnya maupun definisi dari istilah-
istilah atau terminologi yang digunakan. Ekuivalensi istilah algoritma genetika dan
genetika alami pada biologi dapat ditunjukkan pada Tabel 2.1.
Tabel 2.1. Perbandingan Istilah pada Genetika Alami dan Algoritma Genetika.
Genetika Alami Algoritma GenetikaKromosom StringGen Fitur, Karakter, atau DetectorAllel Nilai fiturLocus Posisi StringGenotip StrukturFenotip Set parameter, solusi alternatif, struktur yang dikodekan
Secara alamiah semua organisme terdiri dari sel, di dalam setiap sel terdiri dari
sekumpulan kromosom. Kromosom terbentuk dari sekumpulan gen, membuat satu
kesatuan yang tersusun dalam rangkaian linier. Setiap gen mempunyai letak tersendiri
di dalam kromosom, disebut lokus. Gen tersusun dari Deoxyribo Nucleic Acid (DNA)
yang membawa sifat-sifat keturunan. Setiap gen menyandikan protein tertentu suatu
sifat, contoh : gen warna mata binatang dengan posisi lokus 10. Bagian tertentu dari gen
di dalam genome disebut genotip. Beberapa sifat individu yang menunjukkan perbedaan
gen dan berada pada bagian yang berbeda disebut alel.
Algoritma Genetika merepresentasikan individu sebagai sebuah kromosom.
Kromosom ini merupakan suatu solusi yang masih berbentuk simbol. Algoritma ini
menyelesaikan permasalahan dalam pencarian kromosom yang terbaik. Kromosom-
12
kromosom terbaik diperoleh dengan cara populasi awal yang dibangun secara acak dan
populasi berikutnya yang merupakan hasil evolusi kromosom-kromosom melalui proses
iterasi (seleksi, crossover dan mutasi) yang disebut dengan istilah generasi. Pada setiap
generasi, kromosom akan melalui proses evaluasi dengan menggunakan alat ukur yang
disebut dengan fungsi fitness. Nilai fitness dari suatu kromosom akan menunjukkan
kualitas kromosom dalam populasi tersebut. Setelah melalui beberapa generasi, maka
akan diperoleh kromosom terbaik.
Beberapa definisi penting dalam algoritma genetika adalah sebagai berikut:
a. Gen adalah sebuah nilai yang menyatakan satuan dasar yang membentuk suatu arti
tertentu dalam satu kesatuan gen yang dinamakan kromosom. Dalam algoritma
genetika, gen ini dapat berupa nilai biner, float, integer, kombinatorial maupun
karakter.
b. Allel adalah nilai dari gen.
c. Kromosom adalah gabungan gen-gen yang membentuk nilai tertentu.
d. Individu menyatakan satu nilai atau menyatakan salah satu solusi yang mungkin dari
permasalahan yang diangkat.
e. Populasi merupakan sekumpulan individu yang akan diproses bersama dalam satu
siklus proses evolusi.
f. Generasi menyatakan hasil evolusi kromosom-kromosom melalui proses iterasi.
g. Nilai Fitness menyatakan seberapa baik nilai dari suatu individu atau solusi yang
didapatkan.
13
Algoritma genetika secara umum dapat diilustrasikan pada flowchart berikut :
Gambar 2.2 Flowchart Algoritma Genetika
14
Mulai
Tidak
Selesai
Input Data
Pengkodean
Prosedur Inisialisasi
Fitness Terbaik?
Mutasi
Crossover
Kromosom terbaik
ya
Hasil
Evaluasi Fitness
Membangkitkan Populasi Baru
Seleksi
Dari Gambar 2 diatas, struktur umum dari suatu algoritma genetika dapat
didefinisikan dengan langkah-langkah sebagai berikut:
a. Membangkitkan populasi awal
Populasi awal dibangkitkan secara random, dimana populasi tersebut berisi beberapa
kromosom yang telah didefinisikan sehingga didapatkan solusi awal. Populasi itu
sendiri terdiri dari sejumlah kromosom yang merepresentasikan solusi yang
diinginkan.
b. Membentuk generasi baru
Dalam membentuk generasi baru digunakan tiga operator yaitu operator
reproduksi/seleksi, crossover dan mutasi. Proses ini dilakukan 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 denga istilah anak (offspring).
c. Evaluasi solusi
Pada tiap generasi, kromosom akan diukur dengan fungsi 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. Apabila kriteria berhenti belum
terpenuhi maka akan dibentuk lagi generasi baru dengan mengulangi langkah 2.
Beberapa kriteria berhenti yang sering digunakan antara lain:
1. Berhenti pada generasi tertentu.
2. Berhenti setelah beberapa generasi berturut-turut didapatkan nilai fitness tertinggi.
3. Berhenti pada n generasi dimana nilai fitness dari populasi tidak mengalami
perubahan.
15
2.3.3 Komponen-komponen Utama Algoritma Genetika
Ada 6 komponen utama yang terdapat di dalam algoritma genetika,
(Kusumadewi, 2003) yaitu:
1. Teknik Pengkodean
Menurut Desiani (2006), pengkodean adalah suatu teknik untuk menyatakan
populasi awal sebagai calon solusi suatu masalah ke dalam suatu kromosom sebagai
suatu kunci pokok persoalan ketika menggunakan algoritma genetika. Teknik
pengkodean ini meliputi pengkodean gen dan kromosom. Gen merupakan bagian dari
kromosom yang dapat direpresentasikan dalam bentuk string bit, pohon, array bilangan
real, daftar aturan, elemen permutasi, elemen program, atau representasi lain yang dapat
diimplementasikan untuk operator genetika.
2. Prosedur Inisialisasi
Prosedur inisialisasi (membangkitkan populasi awal) adalah membangkitkan
sejumlah individu secara acak atau melalui prosedur tertentu. Ukuran populasi
tergantung pada masalah yang akan dipecahkan dan jenis operator genetika yang akan
diimplementasikan. Setelah ukuran populasi ditentukan, kemudian harus dilakukan
inisialisasi terhadap kromosom yang terdapat pada populasi tersebut. Inisialisasi
kromosom dilakukan secara acak, namun demikian harus tetap memperhatikan domain
solusi dan kendala permasalahan yang ada.
3. Fungsi Evaluasi
Suatu individu dievaluasi berdasarkan suatu fungsi tertentu sebagai ukuran
performansinya. Dalam algoritma genetika, individu yang memiliki nilai fitness tinggi
16
pada kromosomnya yang akan dipertahankan, sedangkan individu yang pada
kromosomnya bernilai fitness rendah akan diganti. Fungsi fitness tergantung pada
permasalahan tertentu dari representasi yang digunakan.
Rumus fitness yang digunakan, (Lee dkk, 2001) adalah sebagai berikut:
(1)
Keterangan : Bn = Bobot pelanggaran
Fn = Banyaknya pelanggaran
n = 1 . . . n
4. Seleksi
Tujuan dari proses seleksi untuk memilih individu-individu yang akan dipilih
untuk proses persilangan dan mutasi, dimana diharapkan diperoleh calon induk yang
baik. Induk yang baik akan menghasilkan keturunan yang baik. Langkah pertama dalam
seleksi yaitu 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. Nilai
fitness inilah yang nantinya akan digunakan pada tahap seleksi berikutnya.
Ada beberapa metode untuk memilih kromosom yang digunakan antara lain :
a. Seleksi roda rolet (roulette wheel selection).
Seleksi roda rolet dilakukan dengan cara menyeleksi parent dengan tujuan untuk
mempertahankan nilai fitness-nya, dimana yang mempunyai kesempatan untuk diseleksi
adalah kromoson yang baik. Pada metode ini dapat dibayangkan seperti sebuah
17
permainan roda (roullette wheel), di mana semua kromosom ditempatkan dalam
populasi, setiap tempat besar sesuai dengan fungsi fitness.
Kromosom dipilih berdasarkan nilai fitness, semakin besar nilai fitness maka
kromosom tersebut mempunyai peluang untuk dipilih beberapa kali. Metode seleksi
roda rolet merupakan metode yang paling sederhana, dan sering juga dikenal dengan
nama stochastic sampling with replacement.
b. Seleksi good fitness
Seleksi menggunakan metode good fitness dilakukan dengan cara setengah dari
jumlah populasi yang memiliki harga fitness yang terendah akan dihilangkan, sehingga
akan hanya selalu tersisa sekelompok solusi yang terbaik yang pernah diperoleh oleh
program. Solusi yang tersisa hasil seleksi ini dikenal dengan nama populasi induk. Agar
jumlah populasi tetap, maka perlu dibangkitkan solusi baru sebanyak setengah dari
jumlah populasi yang ada. Dalam program penyeleksian, cara yang digunakan untuk
membangkitkan solusi baru menggunakan dua cara yaitu reproduksi kromosom baru
dan cara mutasi dari solusi induk. Tujuan pembangkitan solusi baru ini untuk
menemukan alternatif solusi yang lebih baik dari solusi-solusi yang sudah diperoleh.
5. Operator Genetika
Algoritma genetika merupakan proses pencarian yang heuristik dan acak sehingga
penekanan pemilihan operator yang digunakan sangat menentukan keberhasilan
algoritma genetik 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. Ada dua operator genetika yaitu:
a. Persilangan (crossover)
18
Salah satu komponen yang paling penting dalam algoritma genetika adalah
persilangan (crossover). Persilangan merupakan proses pada algoritma genetika yang
bekerja untuk menggabungkan dua kromosom orang tua (parent) menjadi kromosom
baru (offspring) pada suatu waktu. Sebuah kromosom yang mengarah pada solusi yang
baik dapat diperoleh melalui proses crossover pada dua buah kromosom. Tidak semua
kromosom mengalami persilangan. Cara sederhana pada proses persilangan yaitu
dengan memilih suatu titik yang dipisahkan secara random dan kemudian membentuk
offspring dengan cara mengkombinasikan segmen dari satu induk ke sebelah kiri dari
titik yang dipisahkan dengan segmen dari induk yang lain ke sebelah kanan dari titik
yang dipisahkan.
Terdapat beberapa jenis crossover, antara lain :
1. Crossover satu titik
Proses crossover dilakukan dengan memisahkan suatu string menjadi dua bagian,
kemudian salah satu bagian dipertukarkan dengan salah satu bagian dari string yang lain
yang telah dipisahkan. Misalkan ada 2 kromosom dengan panjang 12 :
Induk 1 : 0 1 1 1 0 | 0 1 0 1 1 1 0
Induk 2 : 1 1 0 1 0 | 0 0 0 1 1 0 1
Kromosom yang dipilih: 5
Anak 1 : 0 1 1 1 0 | 0 0 0 1 1 0 1
Anak 2 : 1 1 0 1 0 | 0 1 0 1 1 1 0
2. Crossover banyak titik.
Proses crossover ini dilakukan dengan memisahkan suatu string menjadi
beberapa bagian dan selanjutnya dipertukarkan dengan bagian dari string yang lain yang
telah dipisahkan. Misalkan ada 2 kromosom dengan panjang 12 :
19
Induk 1 : 0 1 | 1 1 0 0 | 1 0 1 1 | 1 0
Induk 2 : 1 1 | 0 1 0 0 | 0 0 1 1 | 0 1
Posisi yang dipilih : kromosom setelah 2, 6 dan 10
Kromosom baru yang terbetuk:
Anak 1 : 0 1 | 0 1 0 0 | 1 0 1 1 | 0 1
Anak 2 : 1 1 | 1 1 0 0 | 0 0 1 1 | 1 0
b. Mutasi (mutation)
Operator berikutnya mutasi (mutation). Proses mutasi merupakan proses untuk
mengubah salah satu atau lebih beberapa gen dari suatu kromosom. Proses ini berperan
untuk menggantikan gen yang hilang dari populasi akibat proses seleksi yang
memungkinkan munculnya kembali gen yang tidak muncul pada inisialisasi populasi.
Beberapa cara operasi mutasi yang diterapkan dalam algoritma genetika menurut jenis
pengkodeannya, antara lain:
1. Mutasi dalam pengkodean biner
Mutasi pada pengkodean biner merupakan operasi yang sangat sederhana. Proses
yang dilakukan adalah menginversi nilai bit pada posisi tertentu yang dipilih secara
acak (atau dengan menggunakan skema tertentu ) pada kromosom.
Contoh mutasi pada pengkodean biner:
Kromosom sebelum mutasi : 1 0 0 1 0 1 1 1
Kromosom sesudah mutasi : 1 0 0 1 0 0 1 1
2. Mutasi dalam pengkodean permutasi
Proses mutasi dalam pengkodean permutasi dilakukan dengan memilih dua posisi
(lokus) dari kromosom dan nilainya saling dipertukarkan.
Contoh mutasi dalam pengkodean permutasi
20
Kromosom sebelum mutasi : 1 2 3 4 6 5 8 7 9
Kromosom sesudah mutasi : 1 2 7 4 6 5 8 3 9
6. Parameter Kontrol
Parameter kontrol genetika diperlukan untuk mengendalikan operator-operator
seleksi. Pemilihan parameter genetika menentukan penampilan kinerja algoritma
genetika dalam memecahkan masalah (Desiani, 2006). Ada dua parameter dasar dari
algoritma genetika, yaitu probabilitas crossover (pc) dan probabilitas mutasi (pm).
a. Probabilitas crossover (Pc)
Probabilitas crossover akan mengendalikan operator crossover dalam setiap
generasi dalam populasi yang mengalami crossover. Semakin besar nilai probabilitas
crossover, akan semakin cepat struktur individu baru terbentuk ke dalam populasi.
Sedangkan apabila nilai probabilitas crossover terlalu besar, individu yang merupakan
kandidat solusi terbaik mungkin akan dapat hilang lebih cepat pada generasi
selanjutnya. Disarankan nilai probabilitas crossover berkisar antara 80 % - 95 %.
b. Probabilitas mutasi ( )
Probabilitas mutasi akan mengendalikan operator mutasi pada setiap generasi
dimana peluang mutasi yang digunakan biasanya lebih kecil daripada peluang
crossover. Pada seleksi alam murni, mutasi jarang sekali muncul. Oleh karena itu,
operator mutasi pada algoritma genetik juga tidak selalu terjadi. Untuk itulah nilai
peluang mutasi dibuat lebih kecil untuk setiap generasi. Disarankan nilai probabilitas
mutasi kecil berkisar antara 0.5 % - 1 %.
Parameter lain yang juga ikut menentukan efisiensi kinerja algoritma genetika
adalah ukuran populasi, yaitu banyaknya kromosom dalam satu populasi. Tidak ada
aturan yang pasti tentang berapa nilai ukuran populasi. Apabila ukuran populasi kecil
21
berarti hanya tersedia sedikit pilihan untuk crossover dan sebagian kecil dari domain
solusi saja yang dieksplorasi untuk setiap generasinya. Sedangkan apabila terlalu besar,
kinerja algoritma genetik akan menurun. Penelitian menunjukan ukuran populasi besar
tidak mempercepat pencarian solusi. Disarankan ukuran populasi berkisar antara 20–30.
2.4 Penelitian Tentang Penjadwalan Mata Kuliah dan Algoritma Genetika yang
Pernah Dilakukan
Beberapa metode optimasi telah banyak diusulkan dalam menyelesaikan masalah
penjadwalan mata kuliah, antara lain dengan metode greedy, algoritma semut, dan
algoritma particle swarm optimization (PSO). Ketiga metode tersebut dibahas oleh
Sugiarti (2009), Fernandez (2005) dan Johan dkk (2006). Menurut Sugiarti (2009)
metode greedy dapat digunakan untuk menyelesaiakan masalah penjadwalan mata
kuliah dimana model yang dikembangkan menggunakan masalah knapsack dan
diselesaikan dengan tiga strategi yaitu: greedy by profit, greedy by weight, dan greedy
by density. Sedangkan menurut Fernandez (2005) masalah aplikasi penjadwalan mata
kuliah dengan algoritma semut bertujuan untuk menyusun jadwal perkuliahan.
Aplikasinya dikembangkan berdasarkan local search dan algoritma semut. Pada proses
iterasinya membutuhkan waktu lama karena parameter yang disusun cukup banyak.
Berbeda dengan Fernandez (2005), menurut Johan dkk (2006) melalui sistem
penjadwalan otomatis dapat menghasilkan jadwal yang sesuai dengan kemampuan
sistem formulasi dan memori yang tersedia.
Algoritma genetika juga telah banyak digunakan dalam menyelesaikan
permasalahan-permasalahan optimasi dalam dunia nyata antara lain: penjadwalan job
shop oleh Afandi (2010), Travelling Salesman Problem (TSP) oleh Fitrah dkk (2006),
dan Shortest Path oleh Koerniamy (2008). Menurut Afandi (2010) algoritma genetika
22
dapat digunakan sebagai salah satu metode alternatif dalam menyelesaikan penjadwalan
job shop karena memiliki kemampuan yang baik dalam membangkitkan solusi heuristik
dari variasi permasalahan yang luas, dimana sifat dari produk penjadwlannya berbaur
dan multi produk dengan meminimalkan total pinalti E/T (earliness/tardiness). Menurut
Fitrah dkk (2006) Travelling Salesman Problem (TSP) dapat diselesaikan dengan
menggunakan algoritma genetika meskipun solusi TSP yang dihasilkan oleh algoritma
ini belum tentu merupakan solusi optimal, namun algoritma gentika akan menghasilkan
solusi yang lebih optimal pada setiap generasinya, hal tersebut terlihat dari nilai fitness
pada tiap generasi. Kelebihan algoritma genetika dibandingkan dengan metode
pencarian konvesional pada TSP, solusi dapat dihasilkan kapanpun karena solusi
dihasilkan pada generasi ke berapapun dan algorima genetika tidak membutuhkan
waktu yang lama karena tidak semua kemungkinan dicoba, tergantung pada kriteria
berakhirnya. Sedangkan menurut Koerniamy (2008) permasalahan Shortest Path dapat
diselesaikan dengan pendekatan algoritma genetika yang dihitung secara manual, tetapi
pada kasus yang lebih besar perhitungan manual akan mengalami kendala, sehingga
dibutuhkan pemrograman untuk membantu menyelesaikannya.
Berdasarkan permasalahan dan metode yang pernah dilakukan pada penelitian
diatas, maka penelitian ini akan mencoba menggabungkan antara permasalahan dan
metode tersebut sehingga diharapkan metode algoritma genetika dapat diterapkan untuk
menyelesaikan permasalahan penjadwalan mata kuliah.
23
BAB III
METODE PENELITIAN
3.1 Jenis Penelitian
Penelitian ini bersifat studi literatur dan kasus. Bahan literatur diperoleh dari studi
pustaka atau jurnal maupun buku teks yang didapat dengan cara akses langsung maupun
akses internet, sedangkan bahan untuk kasus penelitian diperoleh dari data mata kuliah
Semester Ganjil Tahun Akademik 2011/2012 di Program Studi Matematika FMIPA
Universitas Bengkulu.
3.2 Waktu dan Tempat
Penelitian ini dilakukan ± satu semester, bertempat Di Gedung V ruang baca
Program Studi Matematika FMIPA Universitas Bengkulu pada jam kerja.
3.3 Data yang diperlukan
Data yang dipergunakan dalam penelitian ini adalah data sekunder berupa mata
kuliah yang ditawarkan pada Semester Ganjil Tahun Akademik 2011/2012 di Program
Studi Matematika FMIPA Universitas Bengkulu yang terdiri dari :
a. Daftar Mata Kuliah Semester Ganjil Program Studi Matematika FMIPA Tahun
Akademik 2011/2012.
b. Daftar Dosen pengampu mata kuliah.
c. Jadwal Praktikum Semester Ganjil Tahun Akademik 2011/2012 di Program Studi
Matematika FMIPA.
d. Jadwal Kuliah Semester Ganjil Program Studi Matematika Tahun Akademik
20011/2012 untuk Mata Kuliah Wajib di luar Ruang Belajar Matematika.
24
3.4 Teknik Pengumpulan Data
Pengumpulan data dalam penelitian ini dilakukan dengan mengambil data
sekunder yaitu mata kuliah yang ditawarkan pada Semester Ganjil Tahun Akademik
2011/2012 Di Program Studi Matematika FMIPA Universitas Bengkulu, dosen yang
tersedia, jumlah ruang dan daya tampung.
3.5 Analisis Data
Pada penelitian, analisis data ini dimana langkah-langkah yang akan digunakan
adalah sebagai berikut:
a. Input Data
Ada empat kelompok data yang diperlukan pada input data yaitu: ruang belajar
yang digunakan, Tabel SKS dan mata kuliah, Tabel dosen, semester dan kelas.
b. Proses Data Input
Data-data yang telah diperoleh dari input data terlebih dahulu diolah dengan cara
melakukan pengkodean terhadap masing-masing kelompok data.
c. Pembuatan Kromosom dan Populasi
Pembuatan kromosom dan populasi bertujuan untuk memperoleh hasil
penggabungan antara sks dan mata kuliah, dosen pengampu mata kuliah, semester dan
kelas.
d. Evaluasi Fitness
Setiap faktor yang mempengaruhi nilai fitness memberi pengaruh yang berbeda
terhadap nilai fitnessnya, tingkat pengaruh tersebut disebut dengan bobot. Semakin
tinggi harga bobot suatu faktor akan mengurangi nilai fitness dari solusi tersebut.
Faktor-faktor yang mempengaruhi evaluasi fitness terhadap solusi adalah sebagai
berikut:
25
1. Waktu pagi yang kosong. Adakah waktu pagi yang kosong/tidak digunakan
perkuliahan? Untuk meningkatkan produktivitas pemakaian ruangan, maka
dikehendaki agar ruangan dapat segera digunakan semenjak pagi hari.
2. Frekuensi mengajar dosen. Apakah ada dosen yang memiliki frekuensi mengajar
yang tinggi dalam satu hari? Diharapkan agar tugas mengajar dosen dapat
terdistribusi merata di tiap hari kerjanya dengan tujuan agar performansi dosen
sewaktu mengajar dapat tetap terjaga. Dalam penelitian ini didefinisikan bahwa
dosen yang mengajar lebih dari 6 sks tiap harinya telah digolongkan sebagai dosen
yang memiliki frekuensi mengajar yang tinggi.
3. Frekuensi kuliah kelas. Apakah ada kelas yang memiliki frekuensi kuliah yang tinggi
dalam satu hari ? Seperti halnya pada dosen, untuk menjaga performansi belajar
mahasiswa maka diharapkan tidak ada jadwal kuliah yang terlalu padat dalam satu
hari. Kelas yang mendapatkan jadwal kuliah lebih dari 6 sks pada satu hari
didefinisikan sebagai kelas yang memiliki frekuensi kuliah yang tinggi.
Rumus fitness yang digunakan adalah sebagai berikut:
= Bobot waktu pagi yang kosong
= Bobot frekuensi mengajar dosen
= Bobot frekuensi kuliah kelas
= Banyaknya waktu pagi yang kosong
26
= Banyaknya frekuensi jam mengajar yang tinggi dari seorang dosen
= Banyaknya frekuensi jam kuliah yang tinggi dari satu kelas
Nilai bobot setiap faktor pengaruh yang digunakan dalam penelitian ini dapat
dilihat pada Tabel 3.1.
Tabel 31. Nilai Bobot
Waktu pagi yang kosong 33Frekuensi mengajar dosen 33Frekuensi kuliah kelas 33
e. Seleksi
Untuk mendapatkan solusi yang terbaik, harus dilakukan penyeleksian solusi yang
memiliki nilai fitness yang tergolong rendah. Seleksi tersebut menggunakan metode
best fitness. Solusi yang tersisa pada hasil seleksi ini dikenal dengan nama populasi
induk.
f. Membangkitkan Populasi Baru
Populasi baru akan dibangkitkan dengan cara crossover dan mutasi pada populasi
induk yang telah diperoleh dari proses seleksi.
g. Kondisi Selesai
Jika setelah beberapa generasi berturut-turut diperoleh nilai fitness tertinggi dari
populasi maka proses algortitma akan dihentikan, sedangkan jika pada beberapa
generasi berturut-turut nilai fitnessnya belum mencapai kondisi tersebut, maka akan
mengulang kembali proses/iterasi dari langkah keempat yaitu evaluasi fitness terhadap
populasi baru.
27
28