optimasi-penjadwalan-kegiatan-belajar-mengajar.docx

8/18/2019 optimasi-penjadwalan-kegiatan-belajar-mengajar.docx

1/12

ALGORITMA GENETIKA UNTUK

OPTIMASI PENJADWALAN KEGIATAN PERKULIAHAN

DI STMIK DENPASAR

Ni Wayan Sumartini Saraswati ST., MT.

Ni Ma! Mi"a Prayant#i S.K$m

A%STRA&T

Scheduling lectures activities at STMIK Denpasar involve limited space and time capacity so the

optimization of scheduling is needed to produce a schedule of courses that meet the needs. In this

study we developed a system of scheduling lectures at STMIK Denpasar with Genetic Algorithm

method. rom the e!perimental results o"tained optimal scheduling in which all of the

scheduling parameters are met with the crossover pro"a"ility # $.%& mutation pro"a"ility # $.$'

and population size # %$$.

K!yw$rs' Scheduling& Genetic Algorithms& (ptimization.

(. PENDAHULUAN

)enyusunan *adwal dengan +omponen penyusun yang +omple+s dan +apasitas yang

ter"atas adalah se"uah permasalahan yang umumnya a+an rumit *i+a di+er*a+an dengan proses

manual. )en*adwalan +egiatan per+uliahan di STMIK Denpasar meli"at+an +apasitas ruang dan

wa+tu yang ter"atas sehingga optimasi pen*adwalan sangat diperlu+an untu+ menghasil+an

*adwal per+uliahan yang mampu memenuhi +e"utuhan.

Algoritma geneti+a "iasanya diguna+an untu+ menyelesai+an masalah +om"inatrional

dan ,)-complete yang tergolong sulit. Diharap+an dengan diguna+annya algoritma geneti+a

a+an diperoleh optimasi pen*adwalan yaitu +ondisi dimana ter*adi +om"inasi ter"ai+ untu+

pasangan mata +uliah& dosen penga*ar& ruang dan wa+tu& dimana tida+ ada permasalahan

"entro+an *adwal "ai+ dari sisi mata+uliah& ruang dan wa+tu maupun dosen dan wa+tu.

). KAJIAN PUSTAKA

Algoritma geneti+a merupa+an algoritma pencarian yang menerap+an proses sele+si alam

dan evolusi yang di+emu+a+an oleh harles Darwin. Algoritma geneti+a pertama +ali


2/12

diper+enal+an oleh /ohn 0olland 123456 dari 7niversitas Michigan. /ohn 0olland menyata+an

"ahwa setiap masalah yang "er"entu+ adaptasi 1alami maupun "uatan6 dapat diformulasi+an

+edalam terminologi geneti+a.

Sifat algoritma geneti+a adalah mencari +emung+inan-+emung+inan dari +andidat solusi

untu+ mendapat+an yang optimal untu+ penyelesaian masalah. 8uang ca+upan dari semua solusi

yang laya+ 1 feasible6& yaitu o"*e+-o"*e+ diantara solusi yang sesuai& dinama+an ruang pencarian

1 search space6. Tiap titi+ dalam ruang pencarian mempresentasi+an satu solusi yang laya+. Tiap

solusi yang laya+ dapat ditandai dengan nilai fitness-nya "agi masalah.

Algoritma geneti+a "e+er*a dari populasi yang merupa+an himpunan solusi yang

dihasil+an secara aca+. Setiap anggota himpunan yang merepresentasi+an satu solusi masalah

dinama+an +romosom. Kromosom dalam suatu populasi "erevolusi dalam iterasi yang

dinama+an generasi& tiap +romosom dievaluasi "erdasar+an fungsi evaluasi 1 fitness function6.

)ada algoritma geneti+a& fitness "iasanya dapat "erupa fungsi o"*e+tif dari masalah yang a+an

dioptimalisasi.

Kromosom-+romosom disele+si menurut nilai fitness masing-masing. Kromosom yang

+uat mempunyai +emung+inan tinggi untu+ "ertahan hidup pada generasi "eri+utnya& tetapi tida+

menutup +emung+inan *uga "agi +romosom lemah untu+ tetap "ertahan hidup. )roses sele+si

terse"ut +emudian ditentu+an +romosom-+romosom "aru 1offspring 6 melalui crossover dan

mutasi dari +romosom terpilih 1 parents6. Dari dua proses terse"ut& ma+a ter"entu+ suatu generasi

"aru yang a+an diulangi terus hingga mencapai suatu +onvergensi& yaitu se"anya+ generasi yang

diingin+an.

*. PERAN&ANGAN SISTEM

'.2 Data )enawaran )er+uliahan


3/12

Data perco"aan diam"il dari penawaran per+uliahan dalam satu semester di STMIK

Denpasar& seperti ditun*u++an oleh ta"el '.2

Ta+!" *.(

Data P!nawaran aa STMIK D!nasar

i

d Kode mk

Sk

s

ke

Id

dos

en

1 MPK-5101 1 14

2 MPK-5101 2 14

3 MPK-5102 1 13

4 MPK-5102 2 13

5 MPK-5103 1 17

6 MPK-5103 2 17

7 MKK-5104 1 8

8 MKK-5104 2 89 MKK-5104 3 8

10 MKK-5105 1 4

11 MKK-5105 2 4

12 MKK-5105 3 4

13 MKK-5106 1 6

14 MKK-5106 2 6

1

5 MKK-5106 3 616 MKK-5107 1 9

17 MKK-5107 2 9

18 MKK-5107 3 919 MKK-5301 1 4

20 MKK-5301 2 4

21 MKK-5301 3 4

22 MKB-5302 1 15

23 MKB-5302 2 15

24 MKB-5302 3 15

25 MKK-5303 1 10

2 MKK-5303 2 10


4/12

627 MKB-5304 1 128 MKB-5304 2 1

2

9 MKB-5304 3 130 MKB-5305 1 731 MKB-5305 2 732 MKB-5305 3 733 MKB-5306 1 11

34 MKB-5306 2 1135 MBK-5306 3 11

36 MKB-5307 1 537 MKB-5307 2 538 MKB-5307 3 5

39 MKB-5501 1 240 MKB-5501 2 241 MKB-5501 3 24



52 MKB-5506 2 10


5/12

53 MKB-5506 3 1054 MPB-5507 1 155 MPB-5508 1 10

56 MKB-5701 1 1257 MKB-5701 2 1258 MKB-5702 1 8

59 MKB-5702 2 860 MKB-5702 3 861 MKB-5703 1 26

2 MKB-5703 2 263 MKB-5703 3 2


69 MKB-57-5 3 1670 MKB-5706 1 671 MKB-5706 2 672 MKB-5706 3 673 MKB-5707 1 1674 MKB-5707 2 167

5 MKB-5707 3 1676 MKB-5108 1 4

77 MKB-5108 2 478 MKB-5108 3 4


6/12

/umlah record penawaran ini merupa+an pan*ang +romosom dan mewa+ili *umlah item yang

harus di*adwal+an.

'.9 8epresentasi KromosomSe"uah allele di"entu+ dengan ' +omponen penyusun yaitu id& ruang dan wa+tu seperti

ditun*u++an oleh ta"el '.9

Ta+!" *.)

R!r!s!ntasi Kr$m$s$m

Id 8uan

g

:a+tu I

d

8uan

g

:a+tu I

d

8uan

g

:a+tu I

d

8uan

g

:a+tu ;

2 2..% 2..'$ 9 2..% 2..'$ ' 2..% 2..'$ < 2..% 2..'$ ;

)ada ta"el '.9 +omponen allele id mewa+ili informasi mata +uliah& dosen pengampu dan

=s+s +e> sesuai dengan ta"el penawaran& lihat ta"el '.2. Sedang+an ruang merupa+an ruang yang

ditentu+an untu+ mata +uliah terse"ut "erdasar+an id ruang pada ta"el ruang dimana isinya

adalah nilai integer antara 2 sampai dengan %. 7ntu+ +omponen allele wa+tu merupa+an id

wa+tu sesuai dengan id wa+tu pada ta"el wa+tu dimana satu record mewa+ili wa+tu tempuh

per+uliahan dalam 2 s+s. /umlah record wa+tu dalam ta"el wa+tu adalah '$ record sehingga isi

+omponen allele wa+tu adalah integer antara 2 sampai dengan '$.

'.' ,ilai FitnessDalam penelitian ini +omponen yang men*adi parameter *adwal antara lain tida+ adanya

ta"ra+an ruang-wa+tu yaitu suatu +eadaaan dimana se"uah satuan per+uliahan di*adwal+an pada

ruang yang sama pada slot wa+tu yang sama 126& tida+ adanya ta"ra+an dosen-wa+tu yaitu suatu

+eadaan dimana seorang dosen di*adwal+an pada wa+tu yang sama untu+ mata +uliah yang

"er"eda 196& solidnya satuan wa+tu pen*adwalan pada se"uah mata +uliah dalam arti se"uah mata

+uliah di*adwal+an pada hari yang sama dan *am yang "erurutan 1'6& solidnya ruangan pada satu


7/12

+egiatan per+uliahan yang "erarti se"uah +egiatan per+uliahan yang le"ih dari satu s+s

menempati ruang yang sama untu+ masing-masing s+snya 1


8/12

Metode sele+si dila+u+an dengan metode roulette wheel dimana +romosom dengan

fungsi fitness ter"esar memili+i peluang terpilih yang le"ih "esar. 0al ini dila+u+an dengan

memilih se"uah nilai aca+ yang "erada diantara $ sampai dengan *umlah fitness semua

+romosom dalam populasi& +emudian dicari +romosom dimana posisi nilai terse"ut "erada.

Kawin silang dila+u+an untu+ satu titi+ dimana pro"a"ilitas ter*adi ditentu+an oleh pro"a"ilitas

crossover yang "isa ditentu+an saat runtime. Keti+a ter*adi +awin silang dila+u+an pula mutasi

dengan +emung+inan se"esar pro"a"ilitas mutasi yang *uga ditentu+an saat runtime.

/. HASIL DAN PEM%AHASAN

Dalam tulisan ini hanya ditun*u++an "e"erapa form utama yang memegang peranan

penting dalam penyusunan *adwal mengguna+an algoritma geneti+a& seperti ditun*u++an oleh

gam"ar


9/12

se"agai pem"entu+an populasi awal. )roses Algoritma Geneti+a +emudian diapli+asi+an

terhadap populasi awal hingga "erhenti dan didapat+an hasil pen*adwalan masih dalam "entu+

+romosom. 0asil pen*adwalan dalam "entu+ +romosom terse"ut diter*emah+an dalam "entu+

laporan pen*adwalan seperti ditun*u++an oleh gam"ar


10/12

0asil ter"ai+ ditun*u++an oleh perco"aan +e 22 dengan nilai fitness # 2 dimana semua parameter

pen*adwalan yang "ai+ terpenuhi.

2. SIMPULAN DAN SARAN

Metode Algoritma Geneti+a dapat diguna+an untu+ menghasil+an *adwal per+uliahan

yang optimal pada STIMIK Denpasar dimana semua parameter pen*adwalan terpenuhi.

,( 7)S?@?7M GA S?S7DA0 GA IT,?SS

@8: @D: TS: TS8 @8: @D: TS: TS8

1 100 23 0 82 36 0 0 3 30'055555

556

2 150 14 6 79 37 3 4 1 2

0'052631

579

3 200 23 2 69 38 0 0 6 390'023809

524

4 250 13 2 82 34 0 0 2 50'047619

048

5 300 25 2 77 34 0 2 3 40'043478

261

6 350 1 8 71 36 0 4 1 3 0'0625

7 400 21 4 77 34 0 0 3 30'055555

556

8 450 22 5 73 39 0 0 0 3

0'111111

111

9 500 19 6 78 36 0 0 5 50'033333

333

10 550 15 0 72 42 0 4 1 40'052631

579

11

60

0 18 5 72 38 0 0 0 0 1

12 650 15 0 71 38 0 0 1 70'046666

667

13 700 14 6 77 37 0 0 1 30'083333

333

14 750 23 4 67 42 0 0 1 3

0'083333

333

15 800 20 2 74 38 0 4 5 30'035714

286

16 850 20 5 70 43 0 0 1 50'055555

556

17 900 15 0 72 42 0 0 1 50'055555

556

18 950 22 2 72 33 0 0 1 30'083333

33319 100

017 4 74 37 0 2 4 3 0'043478

261


11/12

)arameter Algoritma Geneti+a ter"ai+ yang diperoleh dari perco"aan ini adalah B pro"a"ilitas

crossover # $&% & pro"a"ilitas mutasi # $&$' dan u+uran populasi # %$$.Dalam perancangan pen*adwalan per+uliahan ini "elum dimasu++an parameter +esediaan

wa+tu menga*ar dosen& dimana pada +enyataannya sering +ali dosen telah memili+i *adwal yang

padat untu+ menga*ar pada perguruan tinggi yang lain sehingga +ita tida+ "e"as menentu+an

wa+tu menga*ar untu+ dosen "ersang+utan. 7ntu+ penelitian selan*utnya dapat dimasu++an

parameter +esediaan wa+tu menga*ar dosen dalam proses pem"uatan *adwal.

Dalam penelitian ini item *adwal yang diwa+ili oleh satu allele di"entu+ per-s+s mata

+uliah. Dimung+in+an dalam penelitian selan*utnya di"entu+ item *adwal yang mewa+ili se"uah

mata +uliah yang utuh tanpa terpecah per-s+s.

DA0TAR PUSTAKA

A"dul Kadir& Konsep dan Tuntunan Praktis Basis Data& Cogya+artaB Andi& 9$$$.

A"dul Kadir& Dasar plikasi Database !"#$% Delphi& Cogya+arta B Andi& 9$$%.

Achmad @asu+i& lgoritma &enetika& Sura"ayaB )olite+ni+ ?le+troni+a ,egeri Sura"aya&

)?,S-TIK. 9$$'& Tanggal a+ses % *anuari 9$2$.

Anita Desiani Muhammad Arhami& Konsep Kecerdasan Buatan& Cogya+arta B Andi

(ffset&9$$%.

Ivan ,ugraha& plikasi lgoritma &enetika 'ntuk (ptimasi Penjadwalan Kegiatan Belajar

!engajar & Institut Te+nologi @andung. Tanggal a+ses Desem"er 9$$3.

Muhammad Aria& plikasi lgoritma &enetika 'ntuk (ptimasi Penjadwalan !ata Kuliah)

7niversitas Komputer Indonesia. Tanggal A+ses % /anuari 9$2$.

,ovandry :idyastuti& Asti+a 8atnawati& 8ahma ,ur ahyani& (ptimasi Penjadwalan Kegiatan

Belajar !engajar Dengan lgoritma &enetika& Sura+arta B 7niversitas Se"elas Maret&

9$$E. Tanggal A+ses Desem"er 9$$3.

)0K TIK K2& *andout !ata Kuliah rtificial +ntelligence& MalangB 7niversitas :idyagama

Malang& 9$$E. Tanggal a+ses /anuari 9$2$.

Son Kuswadi& Kendali Cerdas Teori dan plikasi Praktisn"a& Cogya+arta B Andi (ffset& 9$$4.


12/12

Sumartini& ,. :.& Penjadwalan Pendaratan Pesawat Terbang #ecara ,eal Time !enggunakan

lgoritma &enetika& /urnal STIK(M 9$$3.

optimasi-penjadwalan-kegiatan-belajar-mengajar.docx

Documents