Perbandingan Algoritma Genetika dan Particle Swarm Optimization dalam Optimasi Penjadwalan Mata Kuliah

Disusun Oleh : Yuniar MarbunNIM : 090155201007

Teknik InformatikaFT UMRAH

Latar BelakangPenjadwalan mata kuliah dalam suatu

universitas merupakan hal yang perlu diperhatikan dalam menunjang proses perkuliahan.

Aspek penjadwalan mata kuliah : mata kuliah, dosen pengajar, alokasi waktu dan ketersediaan ruang.

Berbagai Metode Optimasi evolusioner yang dapat digunakan dalam masalah pengoptimasian

Metode yang digunakan adalah Algortima Genetika dan Particle Swarm Optimization

Perumusan Masalah

membandingkan dua algoritma optimasi dalam studi kasus penjadwalan kuliah dan menerapkannya dalam aplikasi penjadwalan mata kuliah.

Tujuan Penelitian

1. Membangun aplikasi penjadwalan dengan metode GA dan PSO

2. Mengetahui algoritma yang lebih optimal digunakan antara GA dan PSO dalam penyusunan jadwal dilihat dari faktor waktu komputasi

Pembatasan Masalah1. Aplikasi yang dibuat adalah aplikasi

berbasis desktop.2. Aplikasi yang dibuat diterapkan untuk

pengolahan mata kuliah di FIKP Universitas Maritim Raja Ali Haji kelas reguler.

3. Aplikasi dibuat untuk mengatur jam mengajar, ruang, dosen pengajar dan mata kuliah.

4. Parameter pengujian dalam pengujian perangkat lunak yaitu jumlah data yang digunakan dan metode yang digunakan.

Manfaat Penelitian

1. Dapat digunakan untuk membantu penjadwalan matakuliah di Universitas Negeri Maritim Raja Ali Haji, khususnya Fakultas Ilmu Kelautan dan Perikanan(FIKP).

2. Sebagai bahan studi perbandingan dan pengembangan lebih lanjut mengenai penelitian dan aplikasi penjadwalan, khususnya yang menggunakan algoritma genetika dan Particle Swarm Optimization.

Kajian LiteraturEmad Elbetagi, Tarek Hegazy dan Donald Grierson(2005)

membandingkan lima algoritma optimasi berbasis evolusi, yaitu Algoritma Genetika, Algoritma Memetika, Particle Swarp Optimization, Koloni Lebah, dan Shuffle Frog Leaping.

Chastine Fatichah, Imam Artha Kusuma, Yudhi Purwananto(2006) membadingkan kinerja algoritma genetika dengan Bivariate Marginal Distribution Algorithm pada kasus Onemax, Fungsi De Jong F2, dan Travelling Salesman Problem.

Komang Setemen (2008) membandingkan kinerja algoritma genetika dan kombinasi antara algoritma genetika dan tabu search dalam optimasi generate penjadwalan mata kuliah.

Metodologi PenelitianAlgoritma GenetikaAlgoritma Genetika adalah adalah algoritma yang digunakan untuk proses pencarian dan optimasi yang didasarkan pada prinsip genetika dan proses seleksi secara alami

Metodologi Penelitianstruktur umum dari suatu algoritma genetika dapat didefiniskan dengan langkah-langkah sebagai berikut:

1. Pembangkitan populasi awal secara acak sehingga didapatkan solusi awal. Populasi itu sendiri terdiri atas sejumlah kromosom yang merepresentasikan solusi yang diinginkan.2. Pembentukan generasi baru. Dalam pembentukan generasi baru diperlukan 3 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.

Metodologi PenelitianParticle Swarm Optimization

Particle Swarm Optimization (PSO) adalah salah satu teknik komputasi evolusioner, yang mana populasi pada PSO didasarkan pada penelusuran algoritma dan diawali dengan suatu populasi yang random yang disebut dengan particle. Setiap partikel dalam PSO juga berhubungan dengan velocity (kecepatan), dimana partikel-partikel tersebut bergerak melalui penelusuran ruang dengan velocity yang dinamis disesuaikan menurut perilaku historisnya. Oleh karena itu partikel-partikel mempunyai kecenderungan untuk bergerak ke area penelusuran yang lebih baik setelah melalui proses penelusuran.

Metodologi PenelitianAdapun prosedur standar untuk menerapkan algoritma PSO adalah sebagai berikut : Inisialisasi populasi dari partikel-partikel dengan posisi dan velocity

secara acak dalam satu ruang dimensi penelusuran.Evaluasi fungsi fitness optimisasi yang diinginkan di dalam variabel d

pada setiap partikel.Membandingkan evaluasi fitness partikel dengan Pbestnya. Jika nilai

yang ada lebih baik dibandingkan nilai Pbestnya, maka Pbest diset sama dengan nilai tersebut dan Pi sama dengan lokasi dengan partikel yang ada Xi dalam ruang dimensional d.

Identifikasi partikel dalam lingkungan dengan hasil terbaik sejauh ini.Update velocity dan posisi partikel.Kembali ke step 2 sampai kriteria terpenuhi, biasanya berhenti pada

nilai fitness yang cukup baik atau sampai pada jumlah maksimum iterasi.

Pembangunan Model Use Case Diagram

Kerangka Pikir Penelitian

Jadwal Penelitian

Daftar Pustaka Ahmad Basuki, 2003. Algoritma Genetika, Suatu Alternatif Penyelesaian Permasalahan Searching,

Optimasi dan Machine Learning. PENS-ITS Surabaya. Chastine Fatichah, Imam Artha Kusuma, Yudhi Purwananto, 2006. Studi Perbandingan Antara

Algoritma Bivariate Marginal Distribution dengan Algoritma Genetika. Jurnal. Jurusan Teknik Informatika, Fakultas Teknologi Informasi Institut Teknologi Sepuluh Nopember Surabaya.

David E.Goldberg, 1989. Genetic Algorithm in Search, Optimization & Machine Learning. Addison- Wesley Publishing Company-Inc.

Debby Paseru, Rila Mandala, Rubby Padang, Lady Ngala, 2007. Sistem Informasi Pengaturan Jadwal Mata Kuliah (Studi Kasus : Universitas Katolik De La Salle Manado). Jurnal, diterbitkan. Jurusan Teknik Informatika ITB, Program Studi Teknik Informatika Unika De La Salle Manado.

Dian Ariani, 2007. Optimasi Penjadwalan Mata Kuliah di Jurusan Teknik Informatika PENS dengan Menggunakan Algoritma Particle Swarm Optimization (PSO). Politeknik Elektronika Negeri Surabaya.

Emad Elbetagi, Tarek Hegazy dan Donald Grierson, 2005. Comparison among five evolutionary-based optimization algorithms. Jurnal terpublikasi. Department of Structural Engineering, Mansoura University, Department of Civil Engineering, University of Waterloo.

Komang Setemen(2008). Implementasi Algoritma Genetika dalam Pengembangan Sistem Aplikasi Penjadwalan Kuliah.Jurnal, diterbitkan. Jurusan Manajemen Informatika Fakutas Teknik dan Kejuruan Universitas Pendidikan Ganesha.

Maickel Tuegeh, Adi Soeprijanto, Mauridhi Hery P, 2009. Optimal Generator Scheduling Based on Particle Swarm Optimization. Jurnal terpublikasi. Jurusan Teknik Elektro UNSRAT Manado, Jurusan Teknik Elektro ITS, Surabaya.

Sri Kusumadewi. Artificial Intelligence. Graha Ilmu, Yogyakarta, 2003.