PENYELESAIAN MASALAH PENUGASAN DENGAN ALGORITMA GENETIKA TEKNIK CYCLE CROSSOVER. Ir. Samuel Lukas, M.Tech*, Dr(Eng). Pujianto Yugopuspito, M.Sc", dan Hadiyanto Asali*"
Abstract Assignment problem is one of the fundamental combinatorial optimization problems. Many algorithms can solve the assignment problem, however it is not easy to solve the problem that has many agents or tasks. Genetic algorithm is applied to find approximate solutions of such problems. Genetic algorithm uses the basic principles of evolutionary biology to computer science. Many applications of the genetic algorithms are implemented as a computer simulation. This paper discusses how to solve assignment problem by applying the technique of cycle crossover in crossover section and random mutation in mutation section. Various percentages of crossover and mutation operators are experimented to find out the best result.
1. PENDAHULUAN Masalah penugasan adalah masalah optimasi dari penjadwalan sumberdaya dan aktifitas yang berprinsip pada penugasan satu ke satu. Sama halnya dengan masalah penjadwalan maka masalah penugasan adalah bagaimana mengatur penugasan terhadap satu agent sedemikian rupa sehingga tercapai optimal. Masalah penugasan ini sering kali ditemukan dalam kehidupan. Sebagai contoh, penghitung biaya minimum pengerjaan yang dibutuhkan dalam memproduksi beberapa jenis barang oleh sejumlah mesin produksi, apabila semua kemungkinan biaya produksi dari setiap mesin untuk setiap barang yang berbeda diketahui dan satu barang terselesaikan hanya oleh satu pengerjaan mesin, merupakan salah satu masalah penugasan. Masalah penugasan sebenarnya tidak hanya terbatas untuk mencari biaya minimum saja, tetapi dalam penerapannya masalah penugasan ini dapat juga digunakan untuk kasus maksimum. Misalnya dalam mencari keuntungan penjualan maksimum bermacam produk oleh banyak penjual. Dalam masalah ini, setiap penjual harus memasarkan produk tersebut, dimana kemampuan seorang penjual dalam menjual suatu produk adalah bervariasi. Seorang penjual akan memperoleh lebih banyak keuntungan untuk suatu macam produk, sedangkan penjual yang lain temyata memperoleh lebih banyak keuntungan untuk produk yang lain. Dengan demikian perlu dilakukan penentuan pasangan penjual dan produk yang tepat, agar diperoleh keuntungan yang paling banyak. Ini adalah contoh penerapan kasus masalah penugasan untuk mencari keuntungan maksimum.
* Dosen Tetap Jurusan Teknik Informatika, FIK-UPH ** Dosen Tetap Jurusan Teknik Informatika, FIK-UPH *** Alumnus Jurusan Teknik Informatika, FIK-UPH Penyelesaian Masalah Penugasan...(S. Lukas, P.Yugopuspito, H.Asali)
87
2.
MASALAH PENUGASAN
Masalah penugasan adalah bagian dari masalah optimasi. Secara matematis, masalah penugasan n sumberdaya atau n aktifitas dapat diformulasikan sebagai berikut:
R = {(a,b) \aeA,b(E B;(a,b) e AxB) X = {(a„b,) | (a„b,) e R,at * aj,bj * btJ = l,2,...,n,y = 1,2,..., n) Sol = Optimum(Jit(X)) R adalah relasi dari A yang merupakan himpunan sumberdaya yang dapat mengerjakan satu aktifitas ke himpunan B yang adalah himpunan aktifitas itu sendiri. X adalah fungsi satu-satu dari A ke B. Jelaslah bahwa banyaknya himpunan bagian dari X adalah n\. Sehingga solusi penugasan adalah mencan X yang merupakan urutan penugasan sedemikian rupa sehingga didapat Sol yang optimum atas fungsi fit(X). Fit(X) adalah fungsi biaya dari penugasan itu sendiri. Untuk makalah ini maka optimum yang dicari adalah optimum minimum. Banyaknya kemungkinan penjadwalan yang dapat dibuat adalah sebesar n\, dimana n adalah jumlah sumberdaya atau aktifitas. Untuk menyelesaikan masalah penugasan, telah dikembangkan beberapa algoritma, diantaranya adalah metode Hongaria oleh Branson tahun 1982, algoritma simulated anneling oleh Kapsalis, Smith, dan Rayward-Smith tahun 1994, tabu search oleh Boyce, Dimitripoulus, dan Taylor tahun 1995 dan algoritma genetika. 3. ALGORITMA GENETIKA DAN MASALAH PENUGASAN Algoritma genetika dikembangkan pertama kali oleh John Holland dari Universitas Michigan (1975). la mengatakan bahwa algoritma genetika dapat mensimulasikan proses evolusi Darwin dan operasi genetika atas kromosom. Beberapa terminologi penting pada algoritma genetika adalah populasi, kromosom, offspring, generasi, crossover, dan mutasi. Populasi adalah himpunan dari kromosom dari suatu permasalahan yang ada. Sedangkan kromosom adalah salah satu kemungkinan jawab tetapi masih dalam bentuk suatu simbol. Offspring adalah anak dari hasil penggabungan 2 buah kromosom sebagai induk dengan mengunakan operator crossover atau penyilangan. Generasi adalah suatu populasi yang dihasilkan dari hasil perubahan seluruh kromosom dari populasi sebelumnya, setelah melalui suatu proses penseleksian yang dinamakan fitness. Populasi awal dibangkitkan secara acak. Populasi berikutnya adalah hasil evaluasi seluruh kromosom dalam populasi. Setelah melalui proses offspring, fitness dan mutasi maka diupayakan ukuran populasi tetap dan konvergen pada kromosom terbaik. Kromosom biasanya ditampilkan dalam bentuk string sederhana. Panjangnya string suatu kromosom / banyaknya gen dalam suatu kromosom tergantung dari teknik penyandian yang digunakan untuk memecahkan persoalannya. Untuk makalah ini kromosom x disandikan sebagai string yang panjangnya L dimana L adalah minimum dari jumlah sumberdaya dengan jumlah aktifitas yang ada, L = min(Js,JA) Aplikasi kromosom x pada masalah penugasan diatas adalah salah satu fungsi satusatu dari A ke B. Salah satu kromosom untuk 9 sumber daya adalah <6 5 7 9 3 2 1 4 8>, yang artinya sumber daya pertama mengerjakan aktifitas 6, sumber daya ke dua mengerjakan aktifitas ke 5 dst hingga sumber daya ke 9 mengerjakan aktifitas 8. 88 Jurnal llmiah llmu Komputer, Vol. 3 No. 2 Mei 2005: 87-95
Proses penyeleksian kromosom mana yang akan bertahan hidup pada generasi berikutnya sangat dipengaruhi oleh fungsi fitness sistem yang dikembangkan. Fungsi fitness berfungsi untuk melakukan evaluasi setiap kromosom dalam suatu populasi. Fungsi fitness dapat dipakai untuk pengurutan kromosom dari kromosom terbaik hingga kromosom yang terburuk. Maka dengan adanya nilai fitness ini dapat ditentukan apakah suatu kromosom akan tetap bertahan atau tidak. Penentuan fungsi fitness dari suatu kromosom x, fit(x), sangat tergantung pada permasalahan yang ada. Biasanya nilai fungsi fitness lebih besar dari 0 dan kurang dari 1, 0 < fitness < 1 Pada makalah ini, fungsi fitness ini adalah fungsi biaya penugasan. Biaya penugasan oleh sumberdaya a, untuk mengerjakan aktifitas 6, dinotasikan dengan f(aj,bj). Sehinga fungsi fitness didefinisikan sebagai:
fl/aya(*) = £ / » , ) '"' r.. , _ I Biaya(x)
dimana Biayc^x) adalah penugasan kromosom ke x
total
seluruh
biaya
Dari rumus fungsi fitness tersebut dapat dilihat bahwa semakin besar total biaya penugasan maka nilai fifnessnya akan semakin kecil. Sebaliknya jika total biaya penugasan semakin kecil, maka nilai fifness-nya akan semakin besar. Untuk masalah optimasi mencari biaya minimum, maka nilai fitness terbaik adalah nilai fitness yang terbesar. 3.1
Cycle Crossover
Crossover adalah salah satu operator genetika yang digunakan untuk melakukan persilangan secara bervariasi dari suatu kromosom pada satu generasi ke generasi selanjutnya. Crossover dapat dilakukan dengan banyak cara, namun dalam simulasi ini hanya digunakan cycle crossover . Cycle Crossover (CX) ini ditemukan oleh Oliver. Langkah - langkah untuk melakukan metode cycle crossover ini yaitu : • Tentukan induk 1 dan induk 2. Indukl :<1 2 3 4 5 6 7 8 9> Induk 2 : <6 5 7 9 3 2 1 4 8> • Temukan putaran yang terbentuk dari gen pada induk 1 ke gen induk 2 ke gen induk 1 lagi dan seterusya hingga terbentuk perputaran (cycle). Dari dua kromosom diatas didapat urutan putarannya 1->6->2->5->3->7-> 1 • Setelah diperoleh putaran dari kedua induk ini, maka langkah berikutnya adalah untuk membentuk anaknya yaitu dengan mempertahankan gen yang mengalami perputaran. Anak 1 : < 1 2 3 x 5 6 7 x x > Anak 2 : < 6 5 7 x 3 2 1 x x > • Kemudian untuk melengkapi bagian yang kosong dari anak 1, maka diambil dari gen yang bersesuaian letak dari induk 2, demikian pula untuk anak 2 akan mengambil dari gen yang bersesuaian induk 1. Dengan demikian anaknya adalah: Anak 1 : <1 2 3 9 5 6 7 4 8> Anak 2 : <6 5 7 4 3 2 1 8 9> Penyelesaian Masalah Penugasan...(S. Lukas, P.Yugopuspito, H.Asali)
89
3.2
Mutasi
Mutasi merupakan salah satu operator genetika yang digunakan untuk memelihara perbedaan genetika satu generasi dengan generasi selanjutnya. Mutasi dapat dilakukan dengan metode reciprocal exchange, yakni tahapan pembentukan kromosom populasi selanjutnya dengan menggantikan dua gen secara acak pada suatu kromosom. Contoh dari operator mutasi ini ialah : Sebelum mutasi: < 1 2 3 4 5 6 7 8 9 > Setelah mutasi : < 1 2 3 8 5 6 7 4 9 > Dari contoh tersebut, dapat dilihat bahwa gen 4 dan gen 8 saling berganti posisi setelah mengalami mutasi, dimana gen 4 dan gen 8 ini dipilih secara acak. 3.3
Langkah Simulasi Penyelesaikan Masalah Penugasan
Masalah penugasan dengan sumber daya yang berjumlah banyak sulit dipecahkan secara manual. Oleh karena itu, pemecahan masalah penugasan digunakan algoritma genetika. Pemecahan masalah penugasan dengan algoritma genetika dilakukan dengan urutan langkah sebagai berikut: 1. Membangun suatu generasi awal 2. Menentukan fitness dan melakukan crossover 3. Melakukan mutasi 4 Membentuk generasi baru 5. Jika belum dicapai generasi akhir, maka langkah kedua hingga selesai diulangi. 4.
IMPLEMENTASI DAN PENELITIAN
Simulasi ini dirancang untuk membuktikan bahwa masalah penugasan dapat diselesaikan dengan pendekatan algoritma genetika. Deskripsi simulasi yang dibangun yaitu : • Dibangun dengan bahas pemrograman Visual Basic 6.0 • Banyak sumberdaya dan aktifitas adalah N, dimana N ^ 500. • Banyak kromosom per generasi adalah /, dimana / £ 1500 • Besarnya persentase terjadinya crossover adalah C dan besarnya persentase terjadinya mutasi adalah M , dimana M dan C bernilai 0, 0.1,0.2,0.3,0.4, ... , 1. • Banyaknya generasi adalah G, dimana G < 1000 generasi. • Input biaya random adalah bernilai 10 sampai dengan 99 Sistem penyeleksian kromosom yang digunakan adalah sistem rank atau pengurutan kromosom berdasarkan nilai fffnessnya. Rancangan tampilan simulasi diperlihatkan pada Gambar 1. Sistem akan dilakukan dua pengujian yang masing-masing bertujuan untuk menguji apakah simulasi telah berjalan baik dengan jumlah sumberdaya yang relatif besar dan apakah sistem cukup layak untuk dipakai dengan melakukan perbandingan hasilnya dengan hasil penyelesaian teknik konvensional masalah penugasan yaitu metode Hongaria.
90 Jurnal llmiah llmu Komputer, Vol. 3 No. 2 Mei 2005: 87-95
Menu Jumlah Me srn
Banyak Individu per Generasi
|~
Input Random
Tabel untuk Input Data
Persentase Crossover
Persentase Mutasi
Generasi ke . Susunan kromosom senap mdividu, rolai fitness dan total biayanya 99xxxxxxxxxxxxxxxxxx
xx = fitness (Totalbiaya = ..)
Gambar 1 Rancangan Tampilan Simulasi
4.1
Percobaan Pertama
Untuk percobaan simulasi ini dilakukan langkah - langkah berikut: • Data percobaan simulasi adalah untuk sumberdaya dan aktifitas berukuran NxN, N= {100, 200, 300, 400, 500} Data N akan disimpan dalam file input. • Untuk setiap nilai N akan dilakukan percobaan : o Jumlah kromosom dalam satu generasi adalah / {500,750,1000,1250,1500} o Banyaknya generasi adalah G yaitu 1000 o Persentasi crossover adalah C,C = {0.1,0.2,0.3,....0.9} o Persentasi mutasi adalah M, M = {0.1,0.2,0.3,...,0.9} Pertama - tama dilakukan perhitungan untuk A/=100, /=500, C=0.1, dicari M terbaik yang menghasilkan solusi optimum dan didapat M = 0.6. Kemudian dicari C terbaik dan didapat C = 0,7 dengan total biaya sebesar 5052. Dilakukan hal yang sama untuk kombinasi lainnya dan hasil terbaiknya ditabulasikan pada Tabel 1. Dari Tabel 1 terlihat bahwa untuk N yang sama maka total biaya relatif sama meskipun besarnya jumlah kromosom dalam satu generasi berbeda dan parameter genetiknya juga berbeda. Ini berarti bahwa sistem telah bekerja sebagaimana mestinya. 4.2
Percobaan Kedua
Percobaan kedua ini dilakukan dengan tujuan untuk membandingkan hasil yang diperoleh dari perhitungan algoritma genetika dengan hasil yang diperoleh dari perhitungan manual dengan menggunakan metode Hongaria. Hasil perhitungan simulasi diharapkan akan memberikan solusi yang sama dengan atau mendekati hasil perhitungan metode Hongaria. Sistem diuji dengan menggunakan 10 Penyelesaian Masalah Penugasan...(S. Lukas, P.Yugopuspito, H.Asali)
91
sumberdaya dan fungsi biayanya disimpan dalam suatu file input. Parameter jumlah kromosom dalam satu generasi adalah 1000 dan banyaknya generasi juga 1000. Sedangkan parameter crossover dan mutasi dibuat variabel mulai dari 0,1 s/d 0,9 Tabel 1. Hasil Percobaan Keseluruhan
Total Total I C M N C M Biaya Biaya 400 100 500 0.6 500 5052 21182 0.5 0.9 0.7 400 100 750 0.8 0.6 750 21001 0.1 4989 0.9 0.3 400 1000 0.1 100 1000 4767 0.1 21086 0.8 400 0.7 100 1250 0.6 0.6 1250 20920 0.8 4970 400 1500 0.6 100 1500 4717 0 1 0.2/0.5 20338 0.5 500 500 0.1 200 500 9789 0.7 0.8 27308 0.9 500 750 200 750 0.7 26785 0.1 0.5 9836 0.6 500 200 1000 0.4 0.4 1000 26586 0.8 0.3 9928 200 1250 500 1250 0.1 9803 0.9 0.7 25909 0.2 500 1500 06 200 1500 0.6 25165 0.9 9806 0.8 07 300 500 15670 0.9 0.1 300 750 15982 0.3 300 1000 15831 0.8 0.5 300 1250 15232 0.6 0.7 0.4 300 1500 15232 0.4 Tabel 2 memperlihatkan fungsi biaya pada masing-masing hubungan sumberdaya dengan aktifitasnya. Terlihat bahwa sumberdaya 3 jika mengerjakan aktifitas 5 memerlukan biaya 69 sedangkan sumberdaya 5 mengerjakan aktifitas 3 adalah 93. Tabel 3 memperlihatkan hasil percobaan yang dilakukan.
N
I
Tabel 2. Fungsi Biaya untuk Percobaan Kedua
1 1 61 2 36 3 56 4 66 5 93 6 50 7 74 8 69 9 95 10 60
2 36 46 92 92 44 23 17 97 89 15
3 30 71 35 86 93 35 87 72 33 40
4 5 63 73 92 23 89 69 60 21 98 50 21 21 43 13 56 36 12 76 14 56
6 71 20 63 83 16 95 40 66 54 82
7 95 97 23 28 42 70 74 38 75 59
8 9 95 37 21 69 80 68 59 29 57 68 84 61 30 51 27 91 99 13 47 69
10 19 52 76 64 37 22 48 23 36 84
Jika perhitungan dilakukan secara manual dengan mengikuti metode Hongaria akan memberikan total biaya minimum 219, dengan kromosom solusi 3 1 7 5 6 1 0 2 8 9 4. Hasil perhitungan memperlihatkan hasil yang sama apabila dilakukan dengan algoritma genetika. Hal ini memperlihatkan bahwa sistem telah bekerja dengan sempurna.
92
Jurnal llmiah llmu Komputer, Vol. 3 No. 2 Mei 2005: 87-95
5.
PEMBAHASAN
Secara matematis dapat dihitung akan ada 3.628.800 atau 10! kemungkinan kombinasi yang dapat dibentuk dari 10 sumberdaya. Pada awalnya, sistem hanya membangkitkan secara acak 1.000 kemungkinan jawab pada generasi awal sesuai dengan banyaknya kromosom dalam satu generasi. Sistem melakukan perubahan kromosom setelah melakukan crossover dan mutasi sebanyak 1000 kali sesuai dengan banyaknya generasi. Sehingga apabila setiap kromosom dalam satu generasi unik dan generasi berikutnya juga unik tidak hanya terhadap generasinya tetapi secara keseluruhan maka dapat dipastikan bahwa hanya terbangkitkan sebanyak 1.000.000 kombinasi kromosom. Hal ini tidaklah mungkin karena nilai C tidak 1 yang berarti ada kromosom yang tinggal tetap pada generasi berikutnya. Jadi jumlah seluruh kromosom yang dibangkitkan pastilah kurang dari 1.000.000 kromosom akan tetapi jawab optimum sudah dapat dihasilkan. Hal ini memperlihatkan bahwa algoritma genetik dapat dipakai untuk pemecahan masalah penugasan dengan baik. Tabel 3. Hasil Percobaan kedua
c
M
Kromosom Solusi
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
0.1 0.1 0.1 0.1 0.1 01 0.1 0.1 0.1
9 1 7 8 6 3 5 1042 9 8 3 7 6 5 2 1041 21376108594 38756421091 3 1 7 9 6 5 2 1048 10179635842 3 8 7 1 6 5 2 1094 31756102894 3 1756102894
Total Biaya 269 270 266 245 254 225 244 219 219
C
M
Kromosom Solusi
09 0.9 0.9 0.9 0.9 09 0.9 0.9 0.9
01 02 03 0.4 0.5 0.6 0.7 08 09
31756 102894 10175642893 38716251094 3 1 7 5 6 10 2 8 9 4 3 8 1 7 6 2 5 10 9 4 3 1756281094 3 1756 102894 31756 102894 31756 102894
Total Biaya 219 233 242 219 237 229 219 219 219
Gambar 2 memperlihatkan pengaruh parameter crossover pada algoritma genetik. Terlihat dengan parameter mutasi yang relatif kecil 10% yang berarti hanya 10% dari kromosom yang akan terjadi mutasi maka dibutuhkan parameter crossover yang relatif besar untuk mencapai titik optimumnya. Gambar 3 memperlihatkan pengaruh parameter mutasi pada algoritma genetika. Terlihat dengan parameter crossover yang relatif besar 90% ( yang berarti akan terjadi penyilangan 90% dari kromosom ) maka perubahan parameter kurang berkorelasi langsung untuk pencapai titik optimum. Akan tetapi terlihat bahwa total biaya bergerak fluktuatif.
Penyelesaian Masalah Penugasan...(S. Lukas, P.Yugopuspito, H.Asali)
93
Perbandingan Hasil Algoritma Genetika dengan Metoda Hongaria untuk persentasi Mutasi 10%
.
240
+
230 233 210
zed Q5
oh
Persentasi Crossover
Metoda Algoritma Genetika
Metoda Hongarian
Gambar 2. Pengaruh Parameter Crossover Pada Algoritma Genetika Perbandingan Hasil algoritma Genetika dengan etoda Hongarian Untuk Persentasi Crossover 90%
-•>— Metoda Algoritma Genetika
Metoda Hongarian
Gambar 3. Pengaruh Parameter Mutasi pada Algoritma Genetika
6.
KESIMPULAN
Dari hasil penelitian ini dapat disimpulkan : 1. Masalah penugasan dapat dipecahkan oleh algoritma genetika dengan baik. 2. Untuk memperoleh suatu hasil yang optimum dari masalah penugasan dengan ukuran N yang besar, diperlukan jumlah kromosom per generasi yang besar, dan juga diperlukan jumlah generasi yang lebih banyak. 3. Hasil perhitungan dengan algoritma genetika dapat memberikan hasil perhitungan yang optimal. Akan tetapi untuk nilai N yang besar, solusi yang diperoleh adalah solusi yang diharapkan mendekati solusi sebenamya. 4. Nilai persentase crossover yang besar akan memberikan kemungkinan jawab yang lebih bervariasi untuk mencapai hasil optimal. Sedangkan nilai persentase mutasi memberikan hasil solusi pemecahan masalah yang lebih tak terduga.
94 Jurnal llmiah llmu Komputer, Vol. 3 No. 2 Mei 2005: 87-95
DAFTAR PUSTAKA [Zuk 2004] Zukhri, Zainudin. Penyelesaian Masalah Penugasan dengan Algoritma Genetika. SNATI. Yogyakarta , 19 Juni 2004. Internet: [1] [2] [3] [4]
Obitko, Marek. 1998. Genetic Algorithms, http://cs.felk.cvut.cz/~xobitko/ ga/main.html. 20 September 2004. Wikipedia. Genetic Algorithm. http://en.wikipedia.org/wiki/Genetic_ algorithm. 21 September 2004. Wikipedia. Assignment Problem. http://en.wikipedia.org/wiki/Assignment_ problem 21 September 2004. Kendall, Graham.(2004). Artificial Intelligence Methods Genetic Algorithms. www.cs.nott.ac.uk/~gxk/courses/ g5baim/004qa/powerpoint/ ga.ppt 14 September 2004.
Penyelesaian Masalah Penugasan...(S. Lukas, P.Yugopuspito, H.Asali)
95
