ii
ANALISIS METODE SELEKSI RANK-BASED FITNESS ASSIGMENT DAN ONE POINT CROSSOVER PADA PENJADWALAN MATAKULIAH
TESIS Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh ijazah Magister Teknik Informatika
FITRI RIZANI 117038039
PROGRAM MAGISTER (S2) TEKNIK INFORMATIKA FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2013
ii Universitas Sumatera Utara
iii
PERSETUJUAN
Judul
: Analisis Metode Seleksi Rank-Based Fitness Assigment Dan One Point Crossover Pada Penjadwalan Matakuliah
Katagori
: Tesis
Nama
: Fitri Rizani
Nomor Induk Mahasiswa
: 117038039
Program Studi
: Teknik Informatika
Fakultas INFORMASI
:
ILMU
KOMPUTER
DAN
TEKNOLOGI
UNIVERSITAS SUMATERA UTARA
Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Dr. Erna Budhiarti Nababan, M. IT Zarlis
Prof.
Dr.
Muhammad
Diketahui/disetujui oleh Program Studi Magister (S2) Tehnik Informatika Ketua,
Prof. Dr. Muhammad Zarlis NIP. 195707011986011003
iii Universitas Sumatera Utara
iv
PERNYATAAN ORISINALITAS
ANALISIS METODE SELEKSI RANK-BASED FITNESS ASSIGMENTDAN ONE POINT CROSSOVER PADA PENJADWALAN MATA KULIAH
TESIS
Saya mengakui bahwa tesis ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan masing – masing telah disebutkan sumbernya.
Medan, 13 Februari 2014
Fitri Rizani 117038039
iv Universitas Sumatera Utara
v
PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS
Sebagai Sivitas akademika Universitas Sumatera Utara, saya bertanda tangan dibawah ini: Nama
: Fitri Rizani
NIM
: 117038039
Program Studi
: Teknik Informatika
Jenis Karya Ilmiah
: Tesis
Demi pengembangan ilmu pengetahuan, menyetujui untuk memberikan kepada Universitas Sumatera Utara Hak Bebas Royalti Non-Eksklusif (Non-Exclusive Royalty Free Right) atas tesis saya yang berjudul: ANALISIS METODE RANK-BASED FITNESS ASSIGMENT DAN ONE POINT CROSSOVER PADA PENJADWALAN MATAKULIAH
Dengan Hak Bebas Royalti Non-Eksklusif ini, Universitas Sumatera Utara berhak menyimpan, mengalih media, memformat, mengelola dalam bentuk database, merawat dan mempublikasikan tesis saya tanpa meminta izin dari saya selama tetap mencamtumkan nama saya sebagai penulis dan sebagai pemegang atau sebagai pemilik hak cipta. Demikian pernyataan ini dibuat dengan sebenarnya. Medan, 13 Februari 2014
Fitri Rizani
NIM: 1170380239
v Universitas Sumatera Utara
vi
Telah diuji pada Tanggal : 13 Februari 2014
PANITIA PENGUJI TESIS Ketua
: Prof. Dr. Muhammad Zarlis
Anggota
: 1. Dr. Erna Budhiarti Nababan, M.IT 2. Prof. Dr. Herman Mawengkang 3. Prof. Dr. Tulus 4. Dr. Marwan Ramli, M.Si
vi Universitas Sumatera Utara
vii
RIWAYAT HIDUP
DATA PRIBADI Nama Lengkap
: Fitri Rizani, S. Kom
Tempat dan Tanggal Lahir
: Pante Lhong, 19 November 1987
Alamat Rumah
: Matangglumpangdua, Mns.Dayah
E_Mail
:
[email protected]
Instansi Tempat Bekerja
: Universitas Al-Muslim
Alamat Kantor
: Jl. Tengku Abdurrahman No. 37 Matangglumpangdua, Bireuen 24261, Provinsi Aceh
DATA PENDIDIKAN SD
: SD Negeri Meunasah Dayah, Bireuen
TAMAT: 1999
SLTP : SMP Negeri2 Peusangan, Bireuen
TAMAT: 2002
SLTA : SMA Negeri 2 Peusangan, Bireuen
TAMAT: 2005
S1
: STMIK Bina Bangsa Lhokseumawe
TAMAT: 2010
S2
: Teknik Informatika Fasilkom-TI USU
TAMAT: 2014
vii Universitas Sumatera Utara
viii
KATA PENGANTAR
Assalamu’alaikum Warahmatullahi Wabarakatu Segala puji bagi Allah Swt, dengan namaNya langit ditinggikan dan bumi dihamparkan. Begitu besar kebesaran Allah yang telah memberikan dua nikmat yang cukup besar kepada kita, yaitu nikmat iman dan nikmat islam. Sehingga dengan kedua nikmat tersebut yang telah diberikan kepada kita, berarti telah diberikan hidayah dan petunjuk oleh Allah. Shalawat beriring salam, kita sanjungkan kepada junjungan alam Nabi Muhammad Saw. Karna Nabi Muhahammad adalah utusan Allah yang terakhir yang diutuskan Allah diakhir zaman untuk menyeru kepada seluruh manusia agar beriman dan bertakwa kepada Allah. Selanjutnya kata penghormatan yang utama kepada Bapak Rektor Universitas Sumatera Utara, Prof. Dr. dr. Syahril Pasaribu, DTM&H, M.Sc (CTM), Sp.A(K) atas kesempatan yang telah diberikan kepada penulis untuk menyelesaikan Studi Program Magister (S2) Teknik Informatika. Kepada ketua Program Studi Magister (S2) Teknik Informatika Fakultas Ilmu Komputer dan Teknologi Informasi (Fasilkom) Prof. Dr. Muhammad Zarlis dan Sekretaris Program Studi Magister (S2) Teknik Informatika M. Andri Budiman, S.T, M.Comp, M.E.M, beserta seluruh Staff Pengajar pada Program Studi Magister (S2) Teknik Informatika pada Fakultas Ilmu Komputer dan Teknologi Informasi (Fasilkom) Universitas Sumatera Utara, yang selama ini telah banyak memberikan ilmu dan membimbing penulis sehingga penulis dapat meyelesaikan studi tepat waktu. Terimakasih yang tak terhingga dan
penghargaan setinggi – tingginya saya
ucapkan kepada Prof. Dr. Muhammad Zarlis sebagai pembimbing utama dan kepada Dr. Erna Budhiarti Nababn, M. IT Sebagai pembimbing Anggota, yang selama ini telah membimbing penulis dalam menyelesaikan tesis dari awal sampai akhir dengan penuh kesabaran, memotifasi serta mengarahkan penulis untuk menyelesaikan tesis dengan baik.Terimakasih yang tak terhingga saya ucapkan kepada pembanding, Prof. Dr. Herman Mawengkang, Prof. Dr. Tulus dan Dr. Marwan Ramli, M. Si yang selama ini juga dalam penyelesaian tesis, telah banyak memberikan masukan, arahan – arahan yang sangat baik untuk kesempurnaan tesis penulis. Dan selanjutnya kepada viii Universitas Sumatera Utara
ix
pada staff Fasilkom yang selama ini sangat membantu penyelesaian tesis dari pada penulis,
berupa pelayanan akademik yang cukup baik dalam mendukung
perlengkapan setiap tesis penulis. Sehingga dengan kebaikan tersebut yang diberikan mendapat balasan yang lebih baik dari Allah Swt. Terimaksih kepada ibunda tercinta ismail dan kepada Ummi tercinta nuraini, yang selama ini telah mendidik adinda dan membimbing adinda semenjak kecil sampai dewasa. Sehingga dengan motivasi, nasehat selalu kepada adinda semenjak menimba ilmu di Fasilkom pada Program studi Magister (S2) Teknik Informatika sampai menyelesaikan Tesis, semua itu tidak akan pernah adinda selesaikan dengan baik dan waktu yang tepat, melainkan dengan doa dari ayahanda dan ummi tercinta serta dengan izin dari Allah yang Maha Kuasa. Semua ini adinda lakukan untuk menjadi yang terbaik dan bisa membanggakan ayah dan ummi serta menjadi pendidik yang bisa memberikan ilmu kepada yang membutuhkan, Dan juga kepada saudara ayah handa dan saudara ummi yang selama ini juga memberikan motivasi serta dukungan kepada adinda dalam menyelesaikan Tesis. selanjutnya kepada kawan – kawan di Fakultas Ilmu Komputer (Fikom) Universitas Almuslim yang juga selalu memberikan dukungan dan semangat. Semoga kebaikan dari kawan – kawan semua, diberikan balasan yang lebih baik dari Allah Swt. Medan, 06 Febuari 2014 Penulis,
Fitri rizani
ix Universitas Sumatera Utara
x
ABSTRAK
Proses perkuliahan di Universitas Al-Muslim Fakultas Ilmu Komputer setiap awal semester dilakukan roster mata kuliah. Jadwal matakuliah terdiri dari empat komponen penyusun dasar, yakni: dosen, matakuliah, waktu dan ruang. Penjadwalan mata kuliah dikatakan optimal jika semua aturan terhadap komponen penyusun jadwal tersebut dapat terpenuhi.Namun untuk untuk menyusun jadwal mata kuliah yang optimal cenderung memakai waktu yang lama.Hal ini disebabkan penyusun jadwal harus lah memperhatikan semua faktor penyusun dasar jadwal tersebut, apakah telah memenuhi peraturan yang telah ditetapkan ataukah belum.Untuk itu diperlukan suatu sistem yang mampu membantu menyusun jadwal mata kuliah yang optimal secara cepat dan akurat. Salah satu algoritma yang bisa dipakai untuk membangun sistem penjadwalan secara otomatis adalah algoritma genetika. Algoritma Genetika adalah suatu algoritma pencarian yang berbasis pada mekanisme seleksi alam, perkawinan silang dan genetika. Proses seleksi pada algoritma genetika memiliki banyak metode. Metode Rank Based Fitness Assigment dan One Point Crossover untuk melihat kinerja algoritma genetika dalam mendapatkan penjadwalan mata kuliah yang baik. Penggunaan metode Rank Based Fitness Assigment dan One Point Crossover dapat menghasilkan jadwal matakuliah dan praktikum yang optimal. Nilai populasi, nilai probabilitas crossover dan nilai probabilitas mutasi sangat mempengaruhi lamanya waktu dalam mendapatkan solusi optimal. Lamanya proses pencarian solusi berbanding lurus dengan jumlah kromosom (dalam hal ini adalah data pengampu dan matakuliah). Serta berbanding terbalik dengan jumlah ruang dan waktu. Semakin banyak kromosom (data pengampu) maka waktu yang dibutuhkan untuk mencapai olusi semakin lama. Semakin banyak ruang dan waktu yang tersedia maka waktu yang dibutuhkan untuk mencapai solusi semakin cepat. Kata Kunci: Rank Based Fitness Assigment, One Point Crossover, kromosom dan mutasi.
x Universitas Sumatera Utara
xi
THE SELECTION METHOD ANALYSIS RANK-BASED FITNESS ASSIGMENT AND ONE POIN CROSSOVER IN THE LECTURE SCHEDULE
ABSTRACT
The lecture process in Al-Muslim University exactly for computer science faculty, have the lecture schedule in the begining semester the lecture schedule consisted of four basic components arrangement they are: lecture, subjects, time and class. Subject scheduling is called optimal if the rules of its components are approves but to composelecturing schedule optimally will spend a longer time. It is caured the schedule arrangement noticing all of arranging of its based factors had approved the role of it schedule of not. So that the system is needed which helps to arrange the lecturing schedule optimally, fluency and accuracy. One of algorithm that can be, used to build scheduling system automatic is genetic algorithm. Genetic algorithm is searching which is gasicallyreturn to natural selection. Hybridization and genetic selection process in genetic algorithm has many methods. Rank-based fitness assigment and one point crossover method is used to see the work genetic algorithm in getting the lecture scheduling perfectly. The use of rank-based fitness assigment andone point crossover produces the lecture schedule in optimal practice population score. Crossover probably score and mutasion score influence the length of time in getting the optimal solusion the length of process for a solusion is compared with the amount of chromosom (in lecturing capability) and also ratios to the amount of rooms and timing. The amount of cromosom (able data) so the time is required to reach the solution is more longer. More available rooms and time so the requirement of time to reach the solution is faster. Keywords:Rank-Based Fitness Cromosom.
Assigment,
One
Point
Crossover,
Mutasion,
xi Universitas Sumatera Utara
xii
DAFTAR ISI KATA PENGANTAR .................................................................................................. i ABSTRAKS ................................................................Error! Bookmark not defined. ABSTRACT ................................................................Error! Bookmark not defined. DAFTAR ISI .............................................................................................................. xii DAFTAR TABEL ..................................................................................................... xiv DAFTAR GAMBAR ................................................................................................. xv BAB I PENDAHULUAN ............................................................................................ 1 1.1 Latar Belakang Masalah............................................................................. 1 1.2 Rumusan Masalah ...................................................................................... 3 1.3 Tujuan Penelitian ....................................................................................... 3 1.4 Batasan dan Ruang Lingkup Penelitian ..................................................... 3 BAB II LANDASAN TEORI ...................................................................................... 6 2.1 Penjadwalan ............................................................................................... 6 2.2 Algoritma Genetika .................................................................................... 6 2.2.1 Deskripsi Umum Algoritma Genetika .............................................. 7 2.2.2 Terminologi Algoritma Genetika ...................................................... 8 2.2.3 Struktur Umum Algoritma Genetika................................................. 9 2.2.4 Komponen-komponen Utama Algoritma Genetika ........................ 10 2.3 Kelebihan dan Kekurangan Algoritma GenetikaError! Bookmark not defined. 2.4 Simulasi Sederhana Permasalahan Algoritma Genetika .......................... 20 2.5 Pengertian Visual Basic .net .................................................................... 23 2.5.1 Lingkup Kerja pada Visual Basic .NET.......................................... 24 2.6 Riset Terkait ............................................................................................. 24 2.7 Perbedaan dengan Riset yang Lain .......................................................... 25 2.8 Kontribusi Riset ....................................................................................... 25 BAB III METODOLOGI PENELITIAN .................................................................. 26 3.1 Pendahuluan ............................................................................................. 26 3.2 Data yang digunakan ................................................................................ 26 3.3 Algoritma Genetika Pada Pejadwalan Matakuliah .................................. 28 3.3.1 Dasar Algoritma Genetika .............................................................. 30 3.3.2 Teknik Penyandian Genetika .......................................................... 31 3.3.3 Populasi Awal ................................................................................. 37 3.3.4 Seleksi ............................................................................................. 39 3.3.5 Crossover ........................................................................................ 44 3.3.6 Mutasi.............................................................................................. 47 BAB IV HASIL DAN PEMBAHASAN ................................................................... 26 4.1 Hasil ......................................................................................................... 26 4.1.1 Tampilan Utama Program Penjadwalan ......................................... 26 4.1.2 Tampilan Form Dosen .................................................................... 27 4.1.3 Tampilan Form Matakuliah ............................................................ 28 4.1.4 Tampilan Form Pengampu .............................................................. 29 4.1.5 Tampilan Form Hari-Jam ................................................................ 30 4.1.6 Tampilan Form Ruang .................................................................... 32 4.1.7 Tampilan Form Proses Genetika ..................................................... 33 4.1.8 Tampilan Grafik Fitnes ................................................................... 34 xii Universitas Sumatera Utara
xiii
4.1.9 Tampilan Grafik Rata-rata Fitnes ................................................... 34 4.2 Percobaan ................................................................................................. 35 BAB V KESIMPULAN DAN SARAN ................................................................... 39 5.1 Kesimpulan .............................................................................................. 39 5.2 Saran......................................................................................................... 39 DAFTAR PUSTAKA ................................................................................................ 41
xiii Universitas Sumatera Utara
xiv
DAFTAR TABEL Tabel 2.1 Tabel 2.2 Tabel 2.3 Tabel 2.4 Tabel 2.5 Tabel 2.6 Tabel 2.7 Tabel 3.1 Tabel 3.2 Tabel 3.3 Tabel 3.4 Tabel 3.5 Tabel 3.6 Tabel 3.7 Tabel 3.8 Tabel 3.9 Tabel 3.10 Tabel 3.11 Tabel 3.12
Istilah Ilmu Genetik dan Algoritma Genetika ............................................ 7 Populasi Kromosom pada Generasi 0 ...................................................... 21 Total Populasi Kromosom pada Generasi 0 ............................................. 21 Populasi Baru Kromosom pada Generasi 0 ............................................. 22 Populasi Kromosom pada Generasi 1 ...................................................... 22 Total Populasi Kromosom pada Generasi 1 ............................................. 23 Populasi Baru Kromosom pada Generasi 1 ............................................. 23 Data input ................................................................................................. 27 Daftar jam kuliah reguler ......................................................................... 28 Tabel Kode Data Pengampun................................................................... 33 Tabel kode data Jam ................................................................................. 35 Tabel kode data hari ................................................................................. 35 Tabel Kode Data Ruang ........................................................................... 35 Tabel Populasi awal ................................................................................. 37 tabel Populasi Induk 1 .............................................................................. 40 Tabel Aturan Hard Constraint ................................................................. 42 Tabel Perhitungan Hard Constraint ......................................................... 43 Tabel Fitness Masing-masing Individu .................................................... 43 Tabel nilai fitness masing-masing individu dirangking dari nilai fitness terendah ke tertinggi ................................................................................. 44 Tabel 3.13 Tabel Individu Terpilih ............................................................................ 44 Tabel 3.14 Tabel Crosover ......................................................................................... 45 Tabel 3.15 Tabel Hasil Mutasi ................................................................................... 48 Tabel 4.1 Hasil percobaan ........................................................................................ 38
xiv Universitas Sumatera Utara
xv
DAFTAR GAMBAR Gambar 2.1 Contoh Struktur Data Algoritma Genetika ............................................. 10 Gambar 2.2 Roulette Wheel Selection ........................................................................ 13 Gambar 2.3 Rank-Based Fitness Assignment ............................................................ 14 Gambar 2.4 One Point Crossover............................................................................... 16 Gambar 2.5 Two Point Crossover .............................................................................. 17 Gambar 2.6 Partially Matched Crossover .................................................................. 18 Gambar 2.7 Order-Based Mutation ............................................................................ 19 Gambar 3.1 Metode Penelitian ................................................................................... 28 Gambar 3.2 Flowchart Penjadwalan Algoritma Genetika .......................................... 31 Gambar 3.3 Teknik penyandian.................................................................................. 32 Gambar 3.4 Ilustrasi penyandian genetika pada penjadwalan matakuliah ................. 36 Gambar 4.1 Tampilan program utama ........................................................................ 26 Gambar 4.2 Form dosen ............................................................................................. 27 Gambar 4.3 Form matakuliah ..................................................................................... 28 Gambar 4.4 Tampilan Form Pengampu ..................................................................... 29 Gambar 4.5 Tampilan Form Hari-Jam ....................................................................... 30 Gambar 4.6 Tampilan Form Ruang ............................................................................ 32 Gambar 4.7 Tampilan Form Proses Genetika ............................................................ 33 Gambar 4.8 Tampilan Grafik Fitnes ........................................................................... 34 Gambar 4.9 Tampilan Grafik Rata-rata Fitnes ........................................................... 34 Gambar 4.10 Grafik fitness dengan probabilitas crossover 0,7 dan mutasi 0,4, populasi 10............................................................................................. 35 Gambar 4.11 Grafik rata-rata fitness dengan probabilitas crossover 0,7 dan mutasi 0,4, populasi 10 ...................................................................................... 35 Gambar 4.12 Hasil Solusi Matakuliah dengan probabilitas crossover 0,7 dan mutasi 0,4, populasi 10 ...................................................................................... 36 Gambar 4.13 Grafik fitness .......................................................................................... 36 Gambar 4.14 Grafik rata-rata fitness dengan probabilitas crossover 0,8 dan mutasi 0,5, populasi 20 ...................................................................................... 36 Gambar 4.15 Hasil Solusi Matakuliah dengan probabilitas crossover 0,8 dan mutasi 0,5, populasi 20 ...................................................................................... 37 Gambar 4.16 Grafik fitness dengan probabilitas crossover 0,9 dan mutasi 0,3, populasi 30............................................................................................. 37 Gambar 4.17 Grafik rata-rata fitness dengan probabilitas crossover 0,9 dan mutasi 0,3, populasi 30 ...................................................................................... 37 Gambar 4.18 Hasil Solusi Matakuliah dengan probabilitas crossover 0,9 dan mutasi 0,3, populasi 30 ...................................................................................... 38
xv Universitas Sumatera Utara
