ANALISIS DAN IMPLEMENTASI PENJADWALAN DENGAN MENGGUNAKAN PENGEMBANGAN MODEL CROSSOVER DALAM ALGORITMA GENETIKA

Jurnal Elektronik Ilmu Komputer - Universitas Udayana

JELIKU Vol 1 No. 2 Nopember 2012

ANALISIS DAN IMPLEMENTASI PENJADWALAN DENGAN MENGGUNAKAN PENGEMBANGAN MODEL CROSSOVER DALAM ALGORITMA GENETIKA

Made Darma Yunantara, I Gede Santi Astawa, Ngr. Agus Sanjaya ER Program Studi Teknik Informatika, Jurusan Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Udayana. Email: ABSTRAK Optimasi penjadwalan dapat dilakukan dengan berbagai metode salah satunya algoritma genetika. Pada algoritma genetika dilakukan beberapa tahap dalam melakukan optimasi penjadwalan yaitu seleksi, crossover dan mutasi. Pada metode crossover kromosom penjadwalan akan diacak dan ditukarkan dengan kromosom yang lainya. Pada penelitian ini, dilakukan pengembangan terhadap metode crossover yang diambil dari metode crossover yang biasa dilakukan di algoritma genetika. dimana pada metode crossover pada umumnya memungkinkan terjadinya kerusakan pada kromosom. Terdapat 2 metode yang dikembangkan, pertama dengan memotong gen hanya pada gen yang mengalami bentrok, dan yang kedua merandom gen yang akan dipotong. Gen dipotong secara utuh tidak memotong ditengah gen, sehingga tidak merusak gen. Analisis terhadap hasil uji coba menunjukan bahwa pengembangan metode crossover dapat diimplementasikan pada kasus penjadwalan dan terlihat bahwa metode yang memotong gen hanya pada gen yang bentrok lebih cepat mencapai nilai terbaik atau mendekati 1 daripada metode yang hanya merandom gen saja. Dari nilai akhir juga terlihat bahwa metode yang memotong gen pada gen yang bentrok memiliki nilai akhir lebih baik. Selain itu kedua metode ini mampu meminimalisir kerusakan pada kromosom hasil dari crossover. Kata Kunci : penjadwalan, pengembangan crossover, algoritma genetik

ABSTRACT Much digital image has been used in various aspects. Almost all digital images need a wide enough space, meaning that a wide enough space is needed; however, the images kept in the database are limited.One of the solutions to overcoming the problems mentioned above is compressing the image prior to storage. Then they are reconstructed again in such a way that they look like original (decompressed) again. One of the lossless compressions available now still uses arithmetic coding algorithms. From the results of implementation and examination of the performance of arithmetic coding algorithms on images with the same resolution but with the same number of different colors, it can be concluded that the more colors an image had, the smaller the compression ratio would be. It was proved that the result of examination based on 1 to 10 colors, there was a decrease in regard to compression ratio from 77.9% to 48.9%. However, in the examination of image compression using the same number of colors but different resolution, it was found that the compression ratio was 59.2%. This indicated that the resolution with different images but the same colors did not highly affect the compression ratio. The value of PSNR for arithmetic coding algorithm was infinite, proving that arithmetic coding algorithm was the lossless compression algorithm, in which the image produced by the 14



compression was successfully reconstructed again exactly the same as the original image. In addition, the compression and decompression time increased following the increase in number of colors, resolution and the size of color file in which the average speed of 10 test images having different colors was 1089.48 ms and decompression was 1036.41 ms. Keywords: Digital Image, Compression, Arithmetic Coding, Lossless

1. PENDAHULUAN Umumnya penyusunan jadwal mata kuliah dilakukan secara manual, yaitu dengan pencarian blok-blok atau kolomkolom mana saja yang masih kosong, kemudian menempatkan jadwal pada blok atau kolom tersebut. Jadwal yang dihasilkan dengan cara seperti ini cenderung menghasilkan jadwal yang menumpuk dan tingkat keakuratannya tidak bisa dijamin. Jadwal yang baik semestinya dapat mengakomodasi semua syarat yang telah ditentukan. Sebagai contoh adalah seorang dosen hanya bisa mengajar pada waktu dan jam tertentu. Dengan syarat ini seharusnya jadwal yang disusun menyediakan sejumlah solusi sehingga kelas yang diajarkan oleh dosen tersebut tidak bentrok dengan dosen yang lainnya. Dengan kemajuan ilmu pengetahuan dalam bidang komputer, masalah penjadwalan di atas dapat dibuat secara otomatis sehingga dapat memberikan solusi optimal sesuai dengan batasan dan syarat yang sudah ditentukan. Sejumlah metode dari berbagai disiplin ilmu telah diusulkan, seperti antara lain algoritma semut atau Ant Colony Optimization (ACO) dengan pendekatan Max Min Ant System (MMAS), Taboo Search, teknik pewarnaan graf (Coloring Graph) dan lainya (ihsan, 2006) Pada penelitian sebelumnya yang dilakukan di universitas udayana, dilakukan optimasi penjadwalan dengan algoritma genetika, dimana penelitian tersebut menghasilkan dan memperlihatkan bahwa algoritma genetika dapat digunakan dalam pembuatan jadwal optimal dengan tidak adanya bentrok antar jadwal kuliah, waktu dan ruangan(suarma,2011) Namun pada penelitian sebelumnya terlihat bahwa terkadang ada jadwal yang tidak sesuai antara mata kuliah dengan dosen pengajar. Penelitian ini akan mencari

bentuk dari penjadwalan dengan menganalisis dan membandingkan metode pengembangan crossover dan mutasi dalam algoritma genetika dengan metode konvensional yang ada. dari hasil penelitian ini akan mencari metode crossover mana yang lebih baik digunakan untuk mendapatkan jadwal yang sesuai tersebut. Metode yang lebih baik akan terlihat dari nilai fitness yang dihasilkan. 2. MATERI 2.1 Algoritma Genetika Evolutionary Algorithm merupakan terminologi umum yang menjadi induk bagi empat istilah : algoritma genetika (genetic algorithm), pemrograman genetika (genetic programming), strategi evolusi (evolution strategies), dan pemrograman evolusi (evolutionary programming). Tetapi, jenis evolutionary algorithm yang paling populer dan banyak digunakan adalah algoritma genetika (genetic algorithm). Algoritma genetika merupakan evolusi/ perkembangan dunia computer dalam bidang kecerdasan buatan (artificial intelligence). Sebenarnya kemunculan algoritma genetika ini terinspirasi oleh teori evolusi Darwin (walaupun pada kenyatanya teori tersebut terbukti keliru) dan teori-teori dalam ilmu biologi, sehingga banyak istilah dan konsep biologi yang digunakan. Karena itu sesuai dengan namanya, proses-proses yang terjadi dalam algoritma genetika sama dengan apa yang terjadi pada evolusi biologi. Algoritma genetika merupakan teknik pencarian nilai optimum secara stochastic berdasarkan mekanisme seleksi alam. Algoritma genetika berbeda dengan teknik konvergensi konvensional yang lebih bersifat deterministic . Metodenya sangat berbeda dengan kebanyakan algoritma optimasi

15


lainnya, yaitu mempunyai ciri-cirinya sebagai berikut : a. Menggunakan hasil pengkodean dari parameter, bukan parameter itu sendiri. b. Bekerja pada populasi bukan pada sesuatu yang unik. Menggunakan nilai satu-satunya pada fungsi dalam prosesnya. c. mengunakan fungsi luar atau pengetahuan luar lainnya. d. Menggunakan fungsi transisi probabilitas, bukan sesuatu yang pasti.


kesatuan gen kromosom.

yang

dinamakan

2.2 Proses Algoritma Genetika Algoritma genetika adalah algoritma pencarian hasil yang terbaik, yang didasarkan pada perkawinan dan seleksi gen secara alami. Kombinasi perkawinan ini dilakukan dengan proses acak (random). Dimana struktur gen hasil proses perkawinan ini, akan menghasilkan gen inovatif untuk diseleksi. Dalam setiap generasi, ciptaan buatan yang baru (hasil perkawinan), diperoleh dari bit-bit dan bagian-bagian gen induk yang terbaik. Diharapkan dengan mengambil dari gen induk yang terbaik ini diperoleh gen akan yang lebih baik lagi. Meskipun pada kenyataannya tidak selalu tercipta gen anak yang lebih baik dari induknya. Ada kemungkinan lebih baik, sama baiknya, atau bahkan mungkin lebih buruk. Tujuan dari algoritma genetika ini adalah menghasilkan populasi yang terbaik dari populasi awal. Sedangkan keuntungan dari algoritma genetika adalah sifat metoda pencariannya yang lebih optimal, tanpa terlalu memperbesar ruang pencarian. Dalam menyusun suatu algoritma genetika menjadi program, maka diperlukan beberapa tahapan proses, yaitu proses pembuatan generasi awal, proses genetika, proses seleksi, dan pengulangan proses sebelumnya Pada algoritma genetika ini terdapat beberapa definisi penting yang harus dipahami sebelumnya, yaitu : a) Gen Gen merupakan nilai yang menyatakan satuan dasar yang membentuk suatu arti tertentu dalam satu

Gambar 2.1 Proses Algoritma Genetika b) Kromosom / Individu Kromosom merupakan gabungan dari gen-gen yang membentuk nilai tertentu dan menyatakan solusi yang mungkin dari suatu permasalahan. c) Populasi Populasi merupakan sekumpulan individu yang akan diproses bersama dalam satu satuan siklus evolusi. d) Fitness Fitness menyatakan seberapa baik nilai dari suatu individu yang didapatkan. e) Seleksi Seleksi merupakan proses untuk mendapatkan calon induk yang baik. f) Crossover Crossover merupakan proses pertukaran atau kawin silang gen-gen dari dua induk tertentu. g) Mutasi 16


Mutasi merupakan proses pergantian salah satu gen yang terpilih dengan nilai tertentu. h) Generasi Generasi merupakan urutan iterasi dimana beberapa kromosom bergabung. i) Offspring Offspring merupakan kromosom baru yang dihasilkan.


dalam mengikuti mata kuliah pertama tidak mengganggu proses belajar pada mata kuliah selanjutnya. d. Frekuensi belajar mahasiswa. Seperti halnya pada dosen, untuk menjaga performansi belajar mahasiswa e. Frekuensi mengajar dosen. Diinginkan agar tugas mengajar dosen dapat terdistribusi merata di tiap hari kerjanya 3.2. Implementasi dan Analisis Algoritma

3. METODE PENELITIAN 3.1 Variabel penelitian

Analisa yang dilakukan pada tahapan ini adalah mengetahui keoptimalan kromosom melalui beberapa metode dalam algoritma genetika. Dalam algoritma genetika terdapat beberapa metode crossover yang juga akan menghasilkan nilai fitness yang berbeda pula. Adapun tahapan penelitian yang akan dilakukan: 1. Menentukan jumlah kromosom yang digunakan dalam 1 generasi dan jumlah maksimum generasi yang digunakan. Dalam penelitian ini menggunakan 12 kromosom yang akan dilakukan crossover dan menggunakan 100 maksimum generasi, jadi generasi akan berhenti setelah generasi ke 100 walaupun nilai fitness belum mencapai 1. Mata kuliah yang digunakan untuk satu kromosom terdiri dari 33 mata kuliah yang ditawarkan. 2. menginisialisasikan faktor pembentuk kromosom dan mensimulasikan kromosom yang ada dalam sebuah jadwal yang dibuat dalam 1 minggu. Terdapat 4 faktor yang membentuk kromosom, yang pertama adalah mata kuliah, dosen, semester, dan sks dari mata kuliah, inisialisasi gen pembentuk kromosom dapat dilihat pada table 3.1

Variabel yang digunakan dalam penelitian ini adalah keoptimalan dari kromosom yang ada yang bisa dilihat dari nilai fitness dan waktu komputasi dari algoritma. Faktor utama pembentuk kromosom dari penelitian ini adalah: a. Mata kuliah yang ditawarkan di masing-masing semester b. Dosen-dosen yang tersedia c. Jumlah SKS setiap matakuliah yang ditawarkan d. Jumlah jam yang ditempuh setiap matakuliah e. Ruang dan waktu yang tersedia Sedangkan faktor-faktor pengaruh yang mempengaruhi nilai fitness dari penelitian ini adalah: a. Adanya mahasiswa yang mengambil dua mata kuliah pada waktu yang bersamaan b. Adanya dosen yang mengajar dua matakuliah pada waktu yang bersamaan c. Kedekatan antar mata kuliah. Mahasiswa memiliki waktu istirahat antar dua mata kuliah yang ada dalam satu hari sehingga kelelahan mahasiswa SMSTR SKS MATA KULIAH kode 1 3 aljabar linier elementer 000001 1 3 logika pemrograman 000010 1 2 ISBD 000011 1 3 Sistem digital 000100 1 3 kalkulus 000101 1 2 pancasila 000110 1 3 PTI 000111 1 2 bhs inggris 001000

17

DOSEN srinadi Dwidasmara ISBD agus mul Asih Pancasila widhi agussan

kode 00001 00010 00011 00100 00101 00110 00111 01000

Gen 001000000100001 001000001000010 000100001100011 001000010000100 001000010100101 000100011000110 001000011100111 000100100001000


3 3 3 3 3 3 3 5 5 5 5

2 3 3 3 3 3 3 3 2 3 3

5 5 5 5 5 5 5 5 5 7 7 7

3 3 3 3 3 3 3 3 3 2 2 3

7 7

3 3

agama rekayasa perangkat lunak basis data probabilitas terapan algoritma dan struktur data sistem operasi proram linier riset operasi Kewarganegaraan pemrograman web pemodelan matematika pengantar kecerdasan buatan teori bahasa dan otomata jaringan komputer lanjut keamanan jaringan pemodelan dan simulasi basis data terdistribusi citra digital pengenalan pola data warehouse Manejemen Kewirausahaan ADBO sistem pendukung keputusan sistem temu kembali

001001 001010 001011 001100 001110 001111 010000 010001 010010 010011 010100

agama gung de herry Srinadi widiartha Anom santi astawa santi astawa Mku Ibmahendra p.eka

01001 01010 01011 00001 01101 01110 01111 01111 10010 10011 10100

010100100101001 011000101001010 011000101101011 011000110000001 011000111001101 011000111101110 011001000001111 101001000101111 100101001010010 101001001110011 101001010010100

010101 010110 011000 011001 011010 011011 011100 011101 011110 011111 100000 100001

LGAstuti Anom cok rai widhi Cahya Ibmahendra Gede agus mul agusSan cok rai Ketut gus de

10101 01110 10101 00111 11010 10110 10111 00100 01000 10101 11000 00010

101001010110101 101001011001110 101001100010101 101001100100111 101001101011010 101001101110110 101001110010111 101001110100100 101001111001000 110101111110101 110110000011000 111010000100010

100011 100100

agusSan 01000 111010001101000 agusSan 01000 111010010001000 c. Setelah terpilih gen yang akan dilakukan crossover, cari pasangan kromosom dari parent yang lainya d. Lakukan crossover sesuai dengan pasanganya e. Penempatan gen crossover dilakukan secara random terlihat

3. Generate kromosom yang telah terbentuk menjadi beberapa jadwal dengan mengambil gen dan diurutkan dalam kolom – kolom waktu dan ruang 4. lakukan crossover dengan parent yang telah dipilih, crossover akan dilakukan dengan beberapa metode yang berbeda. Crossover A a. pilih gen yang memiliki nilai bentrok b. dari gen yang dipilih tadi, lakukan random sehingga hanya beberapa gen dengan nilai bentrok saja yang dipilih.

Parent 1


seperti gambar 3.2. Dimana pada gambar dibawah adalah sebagian kecil dari sebuah kromosom untuk mensimulasikan teknik crossover Parent 2

111010001101000

101001010110101

101001100010101

101001111001000

101001111001000

101001000101111

111010001101000

101001010110101

18



011000101001010

000100100001000

101001000101111

000100100001000

….

….

….

….

anak 1

anak 2

111010001101000

101001111001000

101001100010101

101001010110101

101001010110101

101001000101111 000100100001000

111010001101000

011000101001010

101001000101111

101001111001000 000100100001000

….

….

….

….

Gambar 3.2 contoh crossover A d. Penempatan

gen crossover dilakukan secara random seperti

Crossover B a. Pilih gen dengan cara random b. Setelah gen terpilih, cari gen pasanganya pada parent yang lainya c. Lakukan crossover dengan pasanganya

Parent 1

pada gambar 3.3. Dimana pada gambar dibawah adalah sebagian kecil dari sebuah kromosom untuk mensimulasikan teknik crossover Parent 2

111010001101000

101001010110101

101001100010101

101001111001000

101001111001000

111010001101000

011000101001010

101001000101111 000100100001000

101001000101111

101001010110101 000100100001000

….

….

….

….

anak 1

anak 2

111010001101000

101001111001000

101001100010101

101001010110101

101001010110101

111010001101000

011000101001010

101001000101111 000100100001000

101001000101111

101001111001000 000100100001000

….

….

….

….

Gambar 3.3 contoh crossover B

a = Adanya kelas yang mengambil dua mata kuliah pada waktu yang bersamaan b= Adanya dosen yang mengajar dua matakuliah pada waktu yang bersamaan c = Kedekatan antar mata kuliah d = Frekuensi belajar mahasiswa e = Frekuensi mengajar dosen

5. setelah mendapat populasi baru, hitung nilai fitness dengan menggunakan rumus nilai fitness 3.1

(3.1)

dimana masing-masing faktor memiliki bobot 2, bobot ini bisa

Keterangan:

19


disesuaikan dengan kemauan user nantinya. Dengan melihat nilai fitness bisa dilihat kromosom mana yang berada dalam kondisi paling fit. Semakin sedikit terjadinya bentrok maka akan semakin besar nilai fitness yang dihasilkan 6. lakukan seleksi terhadap semua individu yang ada dengan cara melihat nilai fitness yang dihasilkan. Hanya kromosom dengan fitness terbaik yang akan digunakan kembali 7. lakukan crossover dan seleksi secara berulang hingga individu berada pada fitness terbaik atau sudah mencapai maksimum populasi yang ditetapkan. 3.3 Flowchart Penelitian MULAI

menginisialisasikan faktor pembentuk kromosom

Generate jadwal simulasi

Crossover

TIDAK

Hitung nilai fitness Lakukan seleksi


4. HASIL DAN PEMBAHASAN Dari setiap generasi didapat beberapa individu dengan nilai fitnessnya, dan setiap generasi memiliki individu terbaik dengan nilai fitness yang besar, mendekati nilai 1. Generasi akan berhenti apabila didapatkan individu yang sempurna atau individu dengan nilai fitness sama dengan 1, jika tidak setelah beberapa kali generasi akan diambil individu dengan nilai terkecil pada generasi terakhir, berikut adalah nilai fitness yang terbentuk Dari grafik 4.1 s/d 4.5 menunjukan bahwa seiring generasi bertambah maka nilai fitness individu akan semakin baik. Dari dua tipe crossover yang dipakai terlihat bahwa crossover type A menghasilkan nilai fitness yang lebih baik dibanding dengan type B. Ini disebabkan dari type A yang melakukan crossover menggunakan gen yang bermasalah, sehingga gen yang bermasalah dalam sebuah individu akan langsung ditukarkan dengan gen dari individu lain sehingga tingkat gen yang bermasalah akan cepat berkurang dan akan menaikan nilai dari fitness. Bila pada tipe B gen yang bermasalah tidak langsung dilakukan persilangan tetapi mengambil gen secara random sehingga gen bermasalah kemungkinan masih berada dalam individu tersebut, sehingga nilai fitness pada tipe B akan meningkat tidak secepat pada metode pertama

Nilai fitness = 1 atau maks. generasi YA

Penjadwalan

SELESAI

20



TIPE B TIPE A

Grafik 4.1 Hasil Nilai Fitness Terbaik Percobaan Pertama

FITNESS

TIPE B TIPE A

GENERASI

Grafik 4.2 Hasil Nilai Fitness Terbaik Percobaan Kedua

FITNESS

TIPE B TIPE A

GENERASI

Grafik 4.3 Hasil Nilai Fitness Terbaik Percobaan Ketiga

21



FITNESS

TIPE B TIPE A

GENERASI

Grafik 4.4 Hasil Nilai Fitness Terbaik Percobaan Keempat

FITNESS

TIPE B TIPE A

GENERASI Grafik 4.5 Hasil Nilai Fitness Terbaik Percobaan Kelima

22


KESIMPULAN


penjadwalan kegiatan belajar mengajar”, Jurnal Teknik Informatika ITB, Bandung. Puspitasari, .B. 2008 . “Penggunaan tabu search dalam penjadwalan kuliah dan ujian di perguruan tinggi(skripsi)” Yogyakarta. Universitas Islam Indonesia Prssman, Roger S. 2005. “software engineering A practitioner’s approach sixth edition”. Mc Graw Hill. New York Satemen, .K, Mauridhi,.HP. 2008. “Kombinasi algoritma genetika dan tabu search dalam pembuatan table mata kuliah”. Seminar of intelegent technology an its application, Surabaya. Suarma. 2011 “perancangan dan imlementasi algoritma genetika dalam penjadwalan mata kulaih (skripsi)” Denpasar. Universitas Udayana

Berdasarkan uji coba yang dilakukan, maka kesimpulan yang dapat diambil dari penelitian ini adalah : 1. Penggunaan Algoritma Genetika dengan menggunakan pengembangan metode crossover bisa diimpleentasikan pada kasus pengaturan jadwal. Pengembangan metode crossover memiliki keunggulan tidak dihasilkanya kromosom rusak atau kromosom yang tidak memiliki nilai 2. Dua metode pengembangan metode crossover menghasilkan nilai fitness yang berbeda, dimana metode A memiliki nilai fitness yang lebih kecil dibanding metode B, ini menunjukan metode A memiliki kromosom yang lebih baik dibanding metode B karena kromosom yang bentrok lebih sedikit DAFTAR PUSTAKA

Buliali, . JL, Herumurti,.D, Wiriapraja, .G. 2008. “Penjadwalan mata kuliah dngan menggunakan algoritma genetika dan constraint satisfaction”. Jurnal Teknik Industri, Surabaya. Fernandes, .A, Handoyo, E, Somantri,.M. 2008 . “Pembangunan aplikasi penyusunan mata kuliah dengan algoritma semut”.Jurnal Teknik Elektro: Semarang. Hermann, .J , Lee ,. CY. 1995 . “solving a class scheduling problem with genetic algorith” ORSA Journal on computing.Florida. Ihsan. 2008. “penjadwalan mata kuliah menggunakan algoritma genetika(skripsi)”Yogyakarta. Institut Teknologi Bandung Mustafa, .H ., 2000 . “Teknik Sampling”, ANDI Jogjakarta, Jogjakarta Nugraha, .I. 2008, “Aplikasi algoritma genetic untuk optimasi 23

ANALISIS DAN IMPLEMENTASI PENJADWALAN DENGAN MENGGUNAKAN PENGEMBANGAN MODEL CROSSOVER DALAM ALGORITMA GENETIKA

Recommend Documents