Algoritma Genetik Dengan Sub Populasi Terurut untuk Desain Penjadwalan Multiprosesor

Algoritma Genetik Dengan Sub Populasi Terurut untuk Desain Penjadwalan Multiprosesor Marisa Widyastuti, Kuspriyanto Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung [email protected] Abstraksi Algoritma genetik dengan sub populasi terurut (Ordered-deme Genetic Algorithm – OGA) adalah algoritma genetik yang berbasis pada algoritma genetik ganda (multiple-deme GA), dimana sebuah populasi global dibagi menjadi beberapa sub-populasi (deme) yang dapat berkembang sendiri-sendiri. OGA mengurutkan sub-populasi dari yang tertinggi sampai terendah serta memigrasikan individu terbaik dan terburuk sekaligus pada saat bersamaan, sehingga meningkatkan kemampuan pencarian menurut kenyataan bahwa pencarian optimum global terjadi secara independen pada setiap sub-populasi untuk daerah solusi yang berbeda. Dengan memperkenalkan metoda operasi mutasi adaptif, kestabilan solusi yang diperoleh pada subpopulasi tinggi dengan kemampuan pencarian sedang pada sub-populasi rendah dapat ditingkatkan pada waktu yang bersamaan. Makalah ini membahas hasil eksperimen pada suatu algoritma penjadwalan berbasis genetik yang dapat meningkatkan kemampuan pencarian untuk menemukan jadwal terbaik secara efisien, sehingga dapat memaksimalkan unjuk kerja suatu sistem mikroprosesor.

Kata Kunci: algoritma genetik, sub populasi terurut, sistem multiprosesor, penjadwalan tugas, pemrosesan paralel. 1. PENDAHULUAN Pada sistem-sistem pemrosesan paralel, seperti sistem multiprosesor, pertimbangan paling mendasar adalah bagaimana memaksimalkan unjuk kerja sistem dengan penjadwalan tugas. Strategi penjadwalan yang baik dapat meningkatkan penggunaan sumber daya dan keluaran sistem secara signifikan. Bila terdapat sekumpulan tugas yang dijalankan secara serial dan paralel, maka tugas-tugas ini harus dijadwalkan secara optimal pada setiap prosesor sehingga waktu eksekusi total tersingkat dapat diperoleh. Masalah penjadwalan yang merupakan salah satu masalah yang menantang dalam komputasi paralel ini diketahui bersifat NP-complete, yaitu semakin banyak tugas yang harus dijadwalkan maka semakin rumit untuk memperoleh jadwal optimal. Algoritma heuristik yang digunakan untuk masalah penjadwalan pada umumnya hanya mencari sebagian saja dari daerah pencarian sehingga tidak memberikan kecepatan yang lebih baik. Karena itu teknik pencarian meta-heuristik seperti algoritma genetik, tabu, dan pencarian koloni semut, banyak digunakan untuk masalah penjadwalan tugas karena diperlukan pencarian yang cepat untuk mendapatkan jadwal yang

mendekati optimal dari semua kemungkinan jadwal yang ada[1]. Menurut penelitian-penelitian yang sudah pernah dilakukan sebelumnya dalam bidang penjadwalan multiprosesor, algoritma genetik terbukti sangat efektif dan dalam banyak kasus biayanya relatif lebih rendah[1,2,5]. Algoritma genetik banyak diaplikasikan dalam kehidupan sehari-hari dimana tugas dengan durasi yang berbeda-beda dijadwalkan pada sekelompok prosesor. Dalam makalah ini dibahas hasil eksperimen pada suatu algoritma penjadwalan berbasis genetik yang dapat meningkatkan kemampuan pencarian untuk menemukan jadwal terbaik secara efisien, sehingga dapat memaksimalkan unjuk kerja suatu sistem multiprosesor.

2. MASALAH PENJADWALAN MIKROPROSESOR Masalah penjadwalan mengasumsikan sejumlah sumber daya untuk melayani sejumlah penguna. Tujuannya adalah mencari aturan untuk mengatur akses sumber daya dan penggunaannya oleh pengguna

e-Indonesia Initiative 2008 (eII2008) Konferensi dan Temu Nasional Teknologi Informasi dan Komunikasi untuk Indonesia 21-23 Mei 2008, Jakarta

yang berbeda untuk mengoptimasi sesuai ukuran unjuk kerja yang diinginkan. Panjang jadwal (schedule length) dan waktu rata-rata (mean-time) yang digunakan oleh sistem adalah contoh dari pengukuran unjuk kerja. Unjuk kerja dan efisiensi adalah dua karakteristik yang harus digunakan untuk mengevaluasi sebuah penjadwalan. Tingkah laku program paralel sering direpresentasikan oleh directed acyclic graph (DAG), yang disebut task graph. Sebuah task graph direpresentasikan sebagai TG = (T,E), dimana T adalah sejumlah tugas dan E:TxT adalah sejumlah edge. Directed edge antara tugas Ti dan Tj terjadi jika terdapat dependensi pada tugas-tugas tersebut, yang berarti tugas Tj tidak dapat dieksekusi sebelum tugas Ti selesai dieksekusi. Task graph seringkali diekspresikan sebagai graph dengan bobot (weighted graph). Bobot dari sebuah node Wn(Ti), adalah waktu eksekusi yang diperkirakan untuk tugas Ti, dimana bobot dari suatu edge, We(Ti,Tj), merepresentasikan biaya komunikasi antara tugas dimana Ti dan Tj dijadwalkan untuk prosesorprosesor yang berbeda. Sebuah jadwal S didefinisikan sebagai sejumlah tuple terbatas (Ti,p,t) yang mengindikasikan tugas Ti diberikan pada prosesor p untuk dieksekusi pada waktu t. anggap Sp(Ti) mewakili prosesor yang terjadwal dan St(Ti) memwakili waktu Ti yang terjadwal. Skema klasifikasi, pada level yang lebih tinggi, membedakan penjadwalan lokal dengan penjadwalan global. Penjadwalan lokal mengatur eksekusi proses pada satu prosesor. Penjadwalan global berkaitan dengan mesin paralel dan terdistribusi dan menentukan prosesor mana yang akan menyelesaikan suatu pekerjaan

dan terdistribusi adalah biaya runtime untuk pendistribusian beban informasi, membuat keputusan penempatan dan menstransfer sebuah pekerjaan ke suatu target host secara terus-menerus selama eksekusi program. Pada penjadwalan statis, keputusan diambil pada saat kompilasi, sebelum eksekusi program dilakukan. Sumber daya yang dibutuhkan oleh proses dan informasi mengenai keadaan sistem telah diketahui. Suatu tugas optimal dapat dibuat menurut kriteria tertentu. Ini merupakan permasalahan NP-complete. Solusi sub-optimal dapat dibagi menjadi dua kategori. Algoritma untuk kategori pertama (approximate) dari kelas ”suboptimal” terdiri dari pencarian pada subbagian dari daerah penyelesaian, dan berhenti ketika sebuah solusi yang baik telah ditemukan. Kategori kedua ditentukan dengan menggunakan metoda heuristik, yang mengasumsikan pengetahuan apriori mengenai proses, komunikasi dan karakteristik sistem.

3. PENJADWALAN DENGAN ALGORITMA GENETIK Untuk memecahkan penjadwalan multiprosesor dengan algoritma genetik, sebuah jadwal harus dienkodekan dalam bentuk susunan bilangan (string). Pada arikel ini, jadwal dienkodekan dalam susunan bilangan integer, T0, T1,..., Tn dimana n adalah jumlah tugas dan Tk mewakili prosesor yang dijadwalkan untuk tugas k. Gambar 3. mengilustrasikan representasi susunan bilangan dari jadwal yang tampak pada gambar 2 Karena skema pengenkodean hanya mengenai pemberian node pada prosesor, uruturutan dari tugas harus ditentukan dalam prosesor.

Level selanjutnya pada hirarki membedakan antara penjadwalan dinamis dengan penjadwalan statis. Pada penjadwalan dinamis, keputusan diambil selama pengeksekusian program. Penjadwalan secara dinamis menyeimbangkan beban kerja setiap terjadi ketidakseimbangan. Pada kasus ini, proses dari penyeimbangan beban dapat dilakukan oleh sebuah prosesor (non-distributed), atau dapat juga didistribusikan secara fisik diantara prosesor-prosesor yang lain (distributed). Pada penjadwalan dinamis global terdistribusi, dibedakan antara penjadwalan kooperatif dan nokooperatif. Penjadwalan kooperatif dimana sebuah prosesor menyeimbangkan beban secara kooperatif dengan prosesor lain. Sedang pada penjadwalan nonkooperatif, sebuah prosesor menyeimbangkan beban hanya berdasarkan informasi lokal yang dimilikinya. Setiap prosesor tidak tergantung pada apa yang dilakukan prosesor lain. Kerugian yang paling utama dari algoritma penyeimbangan beban secara dinamis

Gambar 1. Contoh task graph


Gambar 2. Jadwal optimal untuk tiga prosesor

Gambar 3. Jadwal yang dienkodekan dalam bentuk string Task graph dapat direpresentasikan dalam bentuk tabel seperti bentuk tabel 1.

Tabel 1. Representasi task graph dalam bentuk tabel 0 1 2 3 4 5 0 100 100 100 0 0 0 0 0 0 0 100 0 1 0 0 0 0 100 0 2 0 0 0 0 0 100 3 0 0 0 0 0 100 4 0 0 0 0 0 0 5 Kemudian konsep prioritas dinyatakan dalam istilah height. Konsep ini diambil dari teori graph dan secara rekursif didefinisikan pada Definisi 1. Nilai height dari suatu tugas ditentukan dari nilai maksimum tugas sesudahnya. Dengan menggunakan notasi height, kita dapat mengindetifikasi tugas-tugas mana yang harus didahulukan dan mengukur seberapa jauh suatu node terletak dari root node. Pada definisi, PRED(Ti) adalah sejumlah tugas-tugas sebelum tugas Ti. Karena pengurutan nilai height (height-ordering) dari tugastugas tergantung dari hubungan dari setiap tugas, banyak algoritma penjadwalan heuristik yang menggunakan nilai height untuk mengevaluasi urutan penjadwalan tugas yang valid. Seperti penggunaan metode list-scheduling yang mengurutkan tugas menurut prioritasnya dan mendahulukan tugas dengan prioritas lebih tinggi[5]. Definisi 1

Selama penjadwalan, waktu eksekusi sebuah jadwal (make span) harus dihitung dan setiap nilai kecocokan individu harus dievaluasi. Jadwal yang baik adalah jadwal yang memiliki waktu eksekusi yang singkat. Hasil perhitungan makespan ini dapat digunakan untuk menghitung nilai kecocokan dengan menggunakan fungsi kecocokan. Fungsi kecocokan (fitness function) berguna untuk membedakan kualitas satu jadwal dengan jadwal lainnya. Jadwal yang memiliki fungsi kecocokan tinggi memiliki kualitas yang lebih baik daripada jadwal dengan fungsi kecocokan yang lebih rendah. Fungsi kecocokan yang digunakan adalah Persamaan (1). Fungsi kecocokan didefinisikan waktu eksekusi jadwal yang dihitung nilai relatifnya sehingga algoritma genetik meminimumkan waktu eksekusi dan memaksimumkan fungsi kecocokan. Nilai kecocokan relatif memiliki rentang nilai antara 0 dan 1; suatu jadwal akan semakin baik jika nilai kecocokannya semakin mendekati 1. ⎡ ⎧⎪ ⎛ ⎞ fit ( S ) = MAX ⎢ MAX ⎨St ⎜⎜ Ti ⎟⎟ S p (Ti ) = p∈P ⎪⎩ ⎝ Ti ∈ T ⎠ ⎢⎣

⎫⎪⎤ p ⎬⎥ ⎪⎭⎥⎦

(1)

Nilai kecocokan dapat ditentukan dengan memberikan tugas pada prosesor menurut jadwal S, yang dienkodekan pada setiap individu. Algoritma 1 menunjukkan prosedur untuk mencari waktu pembuatan jadwal. Selama penjadwalan, tugas secara berurutan dijadwalkan menurut nilai height-nya. Untuk menentukan waktu jadwal yang paling awal dari setiap tugas, algoritma mengevaluasi t1 dan t2 sebagai berikut: t1 adalah waktu mulai minimum yang mungkin dari Ti yang ditentukan dari waktu penyelesaian maksimum dari semua tugas sebelum tugas Ti. Ketika menentukan T1, waktu komunikasi antar prosesor harus diperhitungkan ketika Sp(Ti) ≠ Sp(Ti). T2 adalah waktu yang tersedia dari prosesor yang dijadwalkan untuk tugas Ti, misalnya waktu penyelesaian maksimum dari suatu tugas yang telah diberikan sebelumnya pada prosesor. Akhirnya, waktu pembuatan suatu jadwal dapat ditentukan sebagai maksimum dari t1 dan t2 dari semua tugas-tugas yang ada. Algoritma 1: Menghitung makespan m = makespan (task graph TG, jadwal S) for all tasks Ti do determine H (Ti) end for for all tasks Ti, in the increasing order of height for all tasks Tj ∈ PRED (Ti) if (Sp(Ti) ≠ Sp (Tj))


else

tj = St (Tj) + Wn (Tj) +We (i,j)

Individu terbaik

D1

tj = St (Tj) + Wn (Tj)

end if end for t1 = MAX (tj) for all tasks (Tj) scheduled at Sp (Ti) t2 = MAX { St(Tj) + Wn(Tj) } end for St(Tj) = MAX (t1,t2) end for m = MAX (St(Ti) + Wn(Tj) )

D2

D3 Individu terburuk D4

Gambar 5. Ordered Genetic Algorithm (OGA) 4. ORDERED-DEME GENETIC ALGORITHM Tidak seperti pendekatan algoritma genetik subpopuasi ganda yang sebelumnya, Ordered-Deme Genetic Algorithm (OGA) memiliki skema migrasi baru yang terlihat pada gambar 4. Jika skema yang terdahulu hanya memigrasikan individu terbaik pada suatu saat, OGA memigrasikan individu terbaik ke sub-populasi yang lebih tinggi dan individu terburuk ke sub-populasi yang lebih rendah. Skema pengurutan dari OGA memperkenalkan hal-hal berikut. Sementara algoritma genetik sub-populasi ganda tradisional memberikan kesempatan yang sama untuk setiap subpopulasi untuk mencari solusi, OGA tidak. OGA memberikan kesempatan yang lebih tinggi kepada sub-populasi yang lebih tinggi sehingga individuindividu terbaik pada suatu saat akan selalu dapat ditemukan pada sub populasi tertinggi. Karena itu individu-individu yang baik akan berkonsentrasi pada sub-populasi tertinggi dan bersaing dengan individuindividu baik lainnya untuk menghasilkan keturunan yang lebih baik. Sebaliknya, individu-individu yang buruk masih mempunyai kemungkinan untuk mengeksplorasi daerah eksplorasi yang lain dengan berkompetisi dengan individu-individu lain yang relatif inferior. Oleh karena itu, skema pengurutan membantu meningkatkan kemampuan pencarian algoritma genetik karena pada kenyataannya pencarian solusi optimal terjadi pada setiap sub-populasi secara independen pada cakupan nilai kecocokan (fitness range) yang berbeda-beda.

D1

D4

Individu terbaik

D2

D3

Gambar 4. Algoritma sub-populasi ganda tradisional

Skema pengurutan ini juga membantu memperlambat terjadinya konvergensi prematur. Pada algoritma genetik sub-populasi ganda tradisional, migrasi individu terbaik yang dilakukan berulang-ulang menghasilkan penyebaran cepat dari bibit yang baik dari seluruh sub-populasi. Karena itu ketika sebuah individu yang mempunyai nilai kecocokan tinggi di reproduksi pada suatu sub-populasi, ia dapat ditemukan di setiap sub-populasi selama beberapa generasi. Skema ini membuat populasi global cepat terkonvergensi pada solusi terbaik pada suatu saat tertentu, menghasilkan konvergensi prematur. Pada OGA, konvergensi yang cepat ini dapat diperlambat sebagai berikut: karena ada pengurutan sub-populasi, individu yang telah dimigrasi dari sub-populasi atas dapat dimigrasi setelah menjadi individu terburuk pada sub-populasi tersebut. Demikian juga, individu dengan nilai tinggi dari sub-populasi tinggi dapat dimigrasi ke sub-populasi yang lebih rendah setelah sub-populasi tersebut penuh dengan individu-individu yang sama. Karena itu, konvergensi prematur dapat diperlambat dengan kurang dari m kali, dimana m adalah jumlah sub-populasi. Selain itu dengan menggunakan metoda pengurutan sub-populasi, hal yang paling penting dari OGA adalah memberikan laju mutasi yang lebih tinggi pada sub-populasi rendah dan memperlambat laju mutasi pada sub-populasi yang lebih tinggi. Dengan memberikan rate mutasi yang lebih rendah pada subpopulasi tinggi akan mempertinggi kestabilan dari individu-individu yang terkonsentrasi pada subpopulasi tinggi. Metoda mutasi adaptif juga membuat individu-individu buruk pada sub-populasi rendah untuk mencari daerah yang lebih luas dengan memberikan laju mutasi yang lebih tinggi. Definisi tersebut dapat dilihat pada algoritma 2. Algoritma 2 : the ordered genetic algorithm (OGA) g := 0 //g adalah generasi Buat sub-populasi D1(g),D2(g),...,Dm(g), secara acak Evaluasi D1(g), D2(g),…,Dm(g) Urutkan D1(g), D2(g),…,Dm(g) dengan urutan dari besar ke kecil while(g < gmax)


g := g + 1; for all sub-populasi Di //kembangkan setiap sub-populasi Pilih Di(g) dari Di(g-1) //Roulette wheel Lakukan crossover pada Di(g) dengan probabilitas Pc Lakukan mutasi pada Di(g)dengan probabilitas Pm(Di) Evaluasi Di(g) end for //Migrasi dilakukan mulai dari Dm //sampai D2 for all (Dimulai dari Dm sampai D2) Urutkan Di(g) Tukar r individu pada urutan teratas di Di(g) dengan individu pada urutan terbawah dari Di-1(g) end for end while

Proses mutasi pada algoritma genetik dapat dianggap sebagai pengubahan nilai pada string secara acak yang dilakukan sekali-sekali. Untuk penjadwalan multiprosesor, mutasi didefinisikan sebagai penempatan acak dari prosesor yang telah dijadwalkan untuk dipilih secara acak kepada prosesor lain yang telah dipilih secara acak, seperti pada gambar 5. Frekuensi mutasi dapat diatur dengan menggunakan probabilitas mutasi, pm. Jadi probabilitas mutasi dipilih dengan probabilitas yang rendah dibandingkan probabilitas crossover, dan harus ditentukan melalui percobaan. Pada gambar 7 dapat dilihat contoh proses mutasi. Ketika tugas 2 dipilih untuk dimutasi, prosesor yang dijadwalkan untuk task tersebut diubah secara acak dari prosesor 1 menjadi prosesor 2. Posisi Mutasi

P0

0

0

1

1

0

(a) Sebelum mutasi

Pada akhirnya, OGA mengurutkan populasi dari besar ke kecil menurut nilai kecocokan dan diletakkan pada array sub-popolasi D1, D2,...,Dm. Pada setiap evaluasi, setiap sub-populasi berevolusi secara independen. Selama langkah migrasi, OGA menukar r individu terbaik dari setiap populasi Di dengan r yang terburuk dari sub-populasi tetangga diatasnya. OGA mengurutkan setiap sub-populasi sebelum melakukan migrasi, yang terjadi secara berurutan dari Dm ke D2. Sehingga hal ini memungkinkan individu-individu yang dimigrasikan dari sub-populasi dibawahnya untuk dimigrasikan ke sub-populasi diatasnya. Dengan bantuan skema pengurutan, dimungkinkan individu dengan nilai tinggi yang berada di subpopulasi rendah langsung bermigrasi ke sub-populasi tertinggi. Fungsi crossover adalah untuk membuat keturunan (offsprings) baru dengan melakukan kombinasi atau mengatur kembali bagian-bagian dari individu orang tuanya. Frekuensi dilakukannya crossover dikontrol oleh sebuah parameter yang disebut probabilitas crossover, pc. Crossover menentukan posisi crossover secara acak dari 1 sampai n, dan menukar sebagian dari susunan bilangan (substring) posisi tersebut dari satu orangtua ke orangtua lainnya. Prosedur crossover dilustrasikan pada gambar 6. ketika posisi crossover i2 telah dipilih, OGA membuat keturunan baru dengan menukar dua substring yang terdiri dari i3, i4 dan i5.

2

P0

0

0

2

1

0

2

(b) Setelah mutasi

Gambar 7. Proses mutasi

5. HASIL EKSPERIMEN Untuk melihat kinerja dari OGA, pengujian dilakukan dengan menjalankan algoritma dengan variasi parameter algoritma genetik dan dilakukan dengan tiga metoda pencarian yang berbeda. Tiga metoda pencarian yang digunakan dalam pengujian adalah algoritma genetik dengan sub populasi terurut (OGA), algoritma genetik sederhana (SGA)[3] dan metoda pencarian acak. SGA digunakan sebagai pembanding algoritma genetik sejenis, sedang metoda acak sebagai pembanding tambahan. Ketiga metoda pencarian menggunakan data populasi awal yang sama. SGA menggunakan parameter algoritma genetik yang sama dengan OGA. Adapun task graph yang digunakan dapat dilihat pada gambar 8.

Posisi crossover

P0

0

0

1

1

0

2

P0

0

0

1

1

0

2

P0

0

0

1

2

1

1

P1

0

1

1

2

1

1

P1

0

1

1

2

1

1

P1

0

1

1

1

0

2

(a) Parents

(b) Crossover

Gambar 6 Proses crossover

(c) Offsprings

Gambar 8. Task Graph yang digunakan dalam percobaan Tabel 2. Representasi task graph dalam, bentuk tabel


berikut 1 75 0 0 0 0 0

2 50 0 0 0 0 0

3 90 0 0 0 0 0

4 0 30 45 0 0 0

5 0 0 0 80 60 0

Task graph yang umum digunakan untuk kasus penjadwalan multiprosesor memang umumnya memiliki tingkat kompleksitas tinggi, dengan tingkat kepadatan (density) yang lebih tinggi dan jumlah tugas yang lebih banyak. Task graph dalam percobaan ini dipilih sedemikian rupa sehingga cukup menggambarkan pemetaan tugas pada prosesor dan menjelaskan kinerja algoritma genetik dengan baik, tanpa menjadi terlalu rumit. Tahap-tahap pengujian yang dilakukan pada algoritma penjadwalan ini adalah : 1. Pengujian dilakukan pada beberapa set data. 2. Setiap set data memiliki variasi parameter yang berbeda-beda, yang kira-kira dapat mewakili sejumlah kasus yang sering terjadi, sehingga dapat dengan jelas menggambarkan tingkah laku metoda pencarian yang diamati. 3. Untuk setiap set data, dicatat individu dengan nilai kecocokan maksimum yang diperoleh oleh setiap algoritma individu pada setiap generasi kemudian dibuat grafik perbandingan dari ketiga metoda pencarian. Percobaan I Dibawah ini adalah parameter algoritma yang digunakan oleh OGA. Ordered-Deme Genetic Algorithm Program Jumlah individu : 12 Jumlah sub populasi :3 Generasi maksimum :7 Probabilitas crossover : 0.3000 Probabilitas mutasi : 0.0100 Jumlah individu yang bermigrasi : 2 Pada OGA populasi dibagi menjadi tiga sub-populasi yang memiliki nilai probabilitas mutasi berbeda-beda (adaptif). Berikut adalah parameter-parameter yang digunakan untuk SGA. Simple Genetic Algorithm Program Jumlah individu : 12 Generasi maksimum : 7 Probabalitas crossover : 0.3000 Probabilitas mutasi : 0.0100 Pada SGA populasi tidak dibagi-bagi dan tidak juga ada skema pengurutan

Selanjutnya adalah metoda random, yang dilakukan dengan membuat suatu populasi secara acak, kemudian diambil individu yang nilai kecocokannya paling tinggi. Kemudian pada generasi berikutnya dibuat lagi suatu populasi secara acak, diambil individu dengan individu dengan nilai kecocokan tertinggi dan seterusnya. Random Search for Multiprocessor scheduling Jumlah individu : 12 Generasi maksimum : 6 0.96100 Nilai Kecocokan Tertinggi

0 1 2 3 4 5

0 0 0 0 0 0 0

0.96000 0.95900 0.95800

OGA SGA Random

0.95700 0.95600 0.95500 0.95400 0.95300 1

2

3

4

5

6

7

8

Generasi

Gambar 9. Grafik perbandingan OGA, SGA dan random Pada grafik di atas terlihat bahwa OGA memberikan hasil yang terbaik. Pada generasi kedua OGA telah berhasil menemukan jadwal yang jauh lebih baik dari yang dihasilkan algoritma lain. Sehingga generasi terakhir OGA memberikan kurva yang stabil. Hasil yang diperoleh SGA pada percobaan ini kurang baik walaupun tampak meningkat sampai generasi keempat, pada generasi ketujuh hasilnya menurun. Pemilihan parameter sangat berpengaruh pada hasil keluaran SGA yang hanya mengandalkan mekanisme crossover dan mutasi. Berbeda dengan OGA yang mempunyai mekanisme lain seperti pengurutan sub populasi dan migrasi, sehingga hasil yang diperoleh jauh lebih konvergen. Kurva random terlihat turunnaik, dan tidak memberikan alternatif yang diharapkan. Percobaan II Ordered-Deme Genetic Algorithm Program Jumlah individu : 18 Jumlah sub populasi :3 Generasi maksimum : 10 Probabilitas crossover : 0.4000 Probabilitas mutasi : 0.0500 Jumlah individu yang bermigrasi : 2 Simple Genetic Algorithm Program Jumlah individu : 18 Generation maksimum : 10 Probabalitas crossover : 0.4000 Probabilitas mutasi : 0.0500


Random Search for Multiprocessor scheduling Jumlah individu : 18 Generation maksimum : 10

Nilai Kecocokan Tertinggi

0.97200 0.97150

stabil dari awal, dengan nilai yang mendekati angka 1. SGA tampak stabil dan pada generasi ke-10 mulai mendapatkan hasil yang lebih baik, tapi tetap belum sebaik OGA. Kurva random sempat naik dan lebih baik nilainya dari kurva SGA, tapi turun dan kemudian naik lagi lalu menurun pada akhir generasi.

0.97100 0.97050 0.97000

OGA SGA Random

0.96950 0.96900 0.96850 0.96800 0.96750 0.96700 0.96650 1

2

3

4

5

6

7

8

9

10

11

Generasi

Gambar 10.

Grafik perbandingan OGA, SGA dan random

Pada percobaan ini OGA sangat baik, stabil dan dapat mencapai nilai yang jauh lebih tinggi dari yang lain. SGA tampak tidak konvergen dan hal ini tentu dipengaruhi parameter algoritma genetik yang digunakan. Kurva random memberikan hasil yang makin buruk diakhir generasi. Percobaan III Ordered-Deme Genetic Algorithm Program Jumlah individu : 12 Jumlah sub populasi :3 Generasi maksimum : 10 Probabilitas crossover : 0.4000 Probabilitas mutasi : 0.0500 Jumlah individu yang bermigrasi : 2 Simple Genetic Algorithm Program Jumlah individu : 12 Generation maksimum : 10 Probabalitas crossover : 0.4000 Probabilitas mutasi : 0.0500 Random Search for Multiprocessor scheduling Jumlah individu : 12 Generation maksimum : 10

5. ANALISIS Hasil yang diberikan oleh OGA lebih baik dari kedua metoda pencarian lain. Kurva OGA stabil dan mempunyai bentuk hampir sama pada setiap percobaan. SGA tidak sestabil OGA , karena variasi parameter algoritma genetik yang digunakan SGA sangat mempengaruhi kestabilan SGA. Pada umumnya hasil terbaik yang diharapkan diperoleh pada generasi ke-1 sampai ke-3. Hal ini sangat dipengaruhi oleh kombinasi parameter-parameter algoritma genetik yang digunakan serta populasi awal yang diperoleh pada setiap percobaan. Dari hasil penelitian, harga probabilitas crossover yang lebih besar dari 0.4 akan membuat terlalu banyak variasi individu sehingga individu-individu yang baik hilang sehingga butuh lebih banyak generasi untuk memperoleh hasil yang diinginkan. Tetapi nilai crossover yang lebih kecil dari 0,1 akan mengakibatkan kurangnya variasi sehingga memperlambat kekonvergenan hasil yang diperoleh. Demikian pula untuk nilai probabilitasi mutasi lebih besar dari 0.05 atau lebih kecil dari 0.01. memberikan hasil yang kurang baik. Pemilihan nilai probabilitas crossover dan mutasi harus dilakukan dengan sangat teliti karena dapat memberikan perbedaan hasil yang signifikan. Karena ini harus dilakukan percobaan yang sangat banyak dan bervariasi untuk memperoleh kombinasi nilai probabilitas crossover dan mutasi yang terbaik. Pada pengaplikasian nilai probabilitas mutasi adaptif, perlu juga diperhatikan perbedaan skala nilai tersebut pada sub populasi tertinggi dengan sub populasi-sub populasi berikutnya, karena hal ini juga sangat mempengaruhi kestabilan sistem serta waktu yang diperlukan untuk mendapatkan hasil yang diinginkan.

Nilai Kecocokan Tertinggi

0.97150 0.97100 0.97050

6. KESIMPULAN

0.97000 0.96950

OGA SGA Random

0.96900 0.96850 0.96800 0.96750 0.96700 0.96650 1

2

3

4

5

6

7

8

9

10

11

Generasi

Gambar 11.

Grafik perbandingan OGA, SGA dan random

Dari hasil percobaan, dapat disimpulkan: 1. Eksperimen ini berhasil membuktikan bahwa algoritma genetik dengan sub populasi terurut berhasil menemukan jadwal yang umumnya lebih baik secara efisien, sehingga dapat memaksimalkan unjuk kerja suatu sistem multiprosesor. 2. Algoritma genetik dengan sub populasi ganda terurut dan proses migrasi memberikan hasil lebih

Pada percobaan ini OGA memperoleh hasil yang e-Indonesia Initiative 2008 (eII2008) Konferensi dan Temu Nasional Teknologi Informasi dan Komunikasi untuk Indonesia 21-23 Mei 2008, Jakarta

konvergen, sehingga dapat diperoleh jadwaljadwal terbaik dalam waktu relatif singkat. 3. Pemberian nilai probabilitas mutasi adaptif terhadap urutan sub populasi ternyata memberikan hasil yang baik karena sub populasi terendah dengan nilai probabilitas mutasi tertinggi memiliki kesempatan lebih tinggi dibanding sub populasi yang lain untuk menemukan individuindividu baru dengan kualitas yang lebih baik. Populasi terendah ini akan berkembang menjadi populasi yang lebih baik dan akan membantu sub populasi untuk menjadi lebih baik dengan memigrasikan individu-individu terbaiknya ke sub populasi yang lebih baik. 4. Hal-hal yang mempercepat terjadinya konvergensi selain distribusi frekuensi huruf adalah parameter algoritma yang digunakan, jumlah kromosom, serta keberuntungan mendapatkan nilai kecocokan yang tinggi saat pembangkitan acak pertama kali dalam populasi.

DAFTAR REFERENSI [1] Andrew J. Page, Thomas J. Naughton, Dynamic Task Scheduling using Genetic Algorithm for Heterogeneous Distributed Computing. [2] Annie S. Wu, Han Yu, Shiyuan Jin, Kuo-Chi Lin, Guy Schiavone, An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling, Proceeding of the IEEE Transactions on Parallel and Distributed Systems, Vol. 15, No. 9, September 2004. [3] Bong-Joon Jung, Kwan-Il Park, Kyu Ho Park, And Ordered-Deme Genetic Algorithm Scheduling, Proceeding of the IEIDE Transactions on Information System, Vol E83-0 No. 6 pp 1207, June 2000. [4] Goldberg, D.E., Genetic Algorithm in Search, Optimization and Machine Learning, AddisonWesley Publishing Company, 1989. [5] William A. Greene, Dynamic Load-Balancing via a Genetic Algorithm.


Algoritma Genetik Dengan Sub Populasi Terurut untuk Desain Penjadwalan Multiprosesor

Recommend Documents