PENENTUAN MATCHING MAKSIMUM PADA GRAPH BIPARTISI BERBOBOT DENGAN MENGGUNAKAN ALGORITMA GENETIKA , , Universitas Negeri Malang E-mail:
[email protected] ABSTRAK: Matching berguna untuk menyelesaikan masalah kehidupan dengan mencari nilai yang paling optimal. Algoritma yang digunakan untuk menyelesaikan permasalahan tersebut yaitu algoritma genetika. Pembahasan ini mendiskripsikan tentang penerapaan algoritma genetika pada pencarian matching maksimum. Dengan mengkodekan permasalahan yaitu dengan mengasumsikan solusi dari matching yang diwakili oleh satu set parameter. Parameter ini disebut dengan gen, yang berisi nilai atau bobot yang bersatu membentuk kromosom. Beberapa kromosom berkumpul membentuk populasi. Panjang kromosom n, dengan n merupakan banyaknya titik pada himpunan A yang merupakan bagian dari graph bipartisi yang berpasangan dengan posisi gen dari 1 sampai m yang merupakan banyaknya titik pada himpunan B. Algoritma genetika merupakan algoritma yang dapat diterapkan dalam segala permasalahan optimasi dengan memiliki banyak pilihan solusi. Namun di samping kelebihan tersebut algoritma genetika memiliki kelemahan, yaitu membutuhkan waktu yang lama dalam proses pencarian solusi tersebut. Kata Kunci: matching, matching maksimum, algoritma genetika
Dalam kehidupan sehari-hari tidak terlepas dari adanya suatu permasalahan. Seiring dengan perkembangan jaman permasalahan yang timbul semakin hari akan semakin beragam, sehingga dibutuhkan suatu metode yang semakin berkembang pula untuk mencari solusi dari masalah kehidupan tersebut. Pada kasus ini ilmu matematika sangat berperan penting bahkan menjadi suatu kebutuhan dalam pencarian solusi yang optimal. Salah satu cabang ilmu matematika adalah teori graph. Dengan teori graph suatu masalah dapat dimodelkan dengan diagram dan lambang atau simbol, sehingga dalam pemahamannya lebih mudah dan praktis, begitu juga dalam penyelesaiannya. Penentuan model yang digunakan dalam masalah ini adalah matching. Matching merupakan salah satu pembahasan dalam teori graph yang mempunyai ketentuan berpasangan tepat satu-satu. Matching berguna untuk menyelesaikan masalah kehidupan dengan mencari nilai yang paling optimal diantaranya dalam penjodohan pada biro jodoh dan pemasangan karyawan dengan posisi kerja. Kelebihan algoritma genetika dibandingkan dengan algoritma yang lainnya yaitu, memiliki pilihan solusi yang banyak dan cara kerjanya lebih teliti untuk mencari solusi penyelesaiannya. Oleh karena itu peneliti ingin mengkaji tentang algoritma genetika secara mendalam. Sehingga diharapkan dapat menambah ilmu pengetahuan tentang penerapan algoritma genetika dalam matching. Dalam tulisan ini istilah dan definisi graph merujuk pada Rosen, 2000. Istilah dan definisi dari matching merujuk pada Aldous, 2004. 1. Anisak Heritin adalah mahasiswa jurusan Matematika FMIPA Universitas Negeri Malang 2. Purwanto adalah dosen jurusan Matematika FMIPA Universitas Negeri Malang 3. Mohamad Yasin adalah dosen jurusan Matematika FMIPA Universitas Negeri Malang
PEMBAHASAN Algoritma Genetika untuk Pencarian Matching Maksimum Misalkan P(generasi) adalah populasi dari satu generasi, maka secara sederhana algoritma genetika terdiri dari langkah-langkah (Kusumadewi, 2003): 1. Generasi = 0 (generasi awal). 2. Inisialisasi populasi awal, P(generasi), secara acak. 3. Evaluasi nilai fitness pada setiap individu dalam P(generasi). 4. Kerjakan langkah-langkah berikut hingga generasi mencapai maksimum generasi: a) Generasi = generasi + 1 (tambah generasi). b) Seleksi populasi tersebut untuk mendapatkan kandidat induk, P’(generasi). c) Lakukan crossover pada P’(generasi). d) Lakukan mutasi pada P’(generasi). e) Lakukan evaluasi fitness setiap individu pada P’(generasi). f) Bentuk populasi baru: P(generasi) = {P(generasi – 1) yang survive, P’(generasi)}. Sebelum algoritma genetika dapat dijalankan, maka suatu kode yang sesuai untuk persoalan harus dirancang. Untuk ini maka titik solusi dalam ruang permasalahan dikodekan dalam bentuk kromosom/string yang terdiri atas komponen genetik terkecil yaitu gen. Urutan dari proses algoritma genetika adalah: a. Pengkodean. Pada algoritma ini dalam mengasumsikan suatu solusi untuk suatu persoalan dimungkinkan dengan diwakili oleh satu set parameter. Parameter-parameter ini dinamakan gen, berisi nilai/allele yang bersatu membentuk kromosom. Selanjutnya beberapa kromosom yang sejenis berkumpul membentuk populasi. Dari suatu populasi inilah algoritma genetika memulai untuk melakukan pencarian. Bentuk populasi yang menyatakan kumpulan kromosom pada permasalahan ini adalah suatu kromosom yang berisi informasi tentang urutan kecocokan antar titik pada matching. Panjang kromosom n, dengan n merupakan banyaknya titik pada himpunan A yang merupakan bagian dari graph bipartisi yang berpasangan dengan posisi gen dari 1 sampai m yang merupakan banyaknya titik pada himpunan B. Representasi dari kromosom tersebut dapat dilihat pada gambar berikut: Kromosom
...
Gen
...
b. Inisialisasi populasi. Inisialisasi ini dilakukan secara random dan hanya satu kali saja sewaktu pertama kali algoritma dijalankan. Inisialisasi ini menghasilkan populasi dengan jumlah kromosom yang sesuai dengan yang diharapkan.
Teknik yang digunakan adalah permutasi gen. dalam permutasi gen, setiap gen merupakan suatu string dari nomor-nomor seperti di bawah ini (Turangga, 2012): Kromosom Gen
3 1
4 2
1 3
2 4
5 5
Pada gambar di atas menerangkan kasus matching 5 titik pada himpunan A dan 5 titik pada himpunan B. Di mana nomor pada gen menunjukkan urutan posisi pada kromosom. Dengan kunci-kunci tersebut dapat dikatakan bahwa nomor 3 pada himpunan A cocok dengan nomor 1 pada himpunan B, nomor 4 pada himpunan A cocok dengan nomor 2 pada himpunan B dan seterusnya. Dengan demikian, diperoleh bentuk kromosom sebagai berikut: 3 4 1 2 5 c. Evaluasi fitness. Ini adalah proses menghitung nilai fitness dari masing-masing kromosom yang ada. Dalam masalah matching ini fungsi fitness melibatkan beberapa faktor yang dapat mempengaruhi terbentuknya nilai fitness. Misalnya dalam masalah penugasan tentor pada LBB (Lembaga Bimbingan Belajar), maka fungsi fitnessnya melibatkan faktor-faktor seperti bidang ilmu/jurusan, indeks prestasi dan gelar yang telah diperoleh. Kemampuan tentor merupakan bobot sisi yang menghubungkan tentor ( = 1,2,3, … , ) dengan mata pelajaran ( = 1,2,3, … , ). Bentuk tabel bobot = [ ], dengan = ( , ) dan model graph sebagai berikut:
Fungsi fitness yang digunakan untuk mengevaluasi suatu kromosom dalam penelitian ini adalah: = + + +⋯ d. Seleksi. Melalui proses ini maka lahirlah generasi baru dimana kromosom diperoleh dari kromosom sebelumnya. Seleksi yang akan digunakan yaitu seleksi berdasarkan roda Roulette. Dibangun permainan roulette sebagai berikut (Desiani, 2007) : 1. Hitung harga fitness "#( $ ) untuk masing-masing kromosom $ (% = 1 … , &'&( )* ) 2. Cari total fitness dari populasi =
,-,_( )*
+
$/
"#(
$)
3. Hitung probabilitas suatu seleksi &$ untuk masing-masing kromosom 1, … &'&( )* )
$ (%
=
&$ = "#( $ )/ 4. Hitung probabilitas komulatif 1$ untuk masing-masing kromosom. $ (% = 1, … &'&( )* ) 1$ = ∑$/ 3 Proses seleki berdasarkan perputaran rode roulette pop_size kali. Pada masing-masing waktu diseleksi kromosom tunggal untuk populasi baru dengan cara berikut: a) Pembangkitan bilangan acak r dari range [0 1] sebanyak pop_size. b) Jika 4 < 1$ , pilih kromosom pertama ( $ ). Untuk yang lain, seleksi kromosom ke-i $ (2 ≤ % ≤ &'&_ 7 ), seperti 1$8 < 4 ≤ 1$ e. Crossover Proses ini akan menghasilkan keturunan yang berbeda dengan induknya. Untuk proses ini dilakukan dengan mengambil induk secara berpasangan dan akan menghasilkan keturunan dengan jumlah yang sama dengan induknya. Prosedur untuk pemilihan induk mana yang akan mengalami proses crossover: • Tentukan probabilitas crossover. • Bangkitkan bilangan random 0 sampai 1 sebanyak i (jumlah kromosom dalam satu populasi). • Bandingkan bilangan random itu dengan probabilitas crossover (Pc). • Induk terpilih bila bilangan r yang ke-i kurang atau sama dengan probabilitas crossover (Pc). • Bila induk yang terpilih jumlahnya hanya satu maka proses ini diulang sampai jumlah induknya lebih dari satu. Teknik crossover yang akan digunakan yaitu teknik position based crossover. • Pilih sekumpulan posisi gen dari salah satu orang tua secara acak. • Menghasilkan sebuah kromosom anak dengan menyalin posisi gen dari salah satu induk tersebut ke dalam posisi gen yang bersesuaian pada kromosom anak. • Menghapus gen yang telah terpilih pada induk kedua. Kemudian urutkan gen yang dihasilkan. • Tempatkan gen tersebut pada posisi yang masih kosong di kromosom anak, dari kiri ke kanan. f. Mutasi. Pada proses ini juga akan menghasilkan keturunan di mana jumlahnya tergantung pada banyaknya bilangan random yang kurang dari probabilitas mutasi (Pm). Prosedur untuk menentukan kromosom mana yang akan dimutasi adalah (Yuliagandi, 2010): 1. Masukkan Pm (Probabilitas Mutasi). 2. Menentukan banyaknya kromosom yang akan melakukan mutasi: Pm * pop_size * panjang kromosom. 3. Bangkitkan bilangan random antara 1 sampai jumlah gen tersebut (pop_size * panjang kromosom) sebanyak jumlah kromosom yang mengalami mutasi (Pm * pop_size * panjang kromosom). 4. Menentukan posisi gen yang akan dimutasi yaitu dengan cara:
• • • •
Memilih kromosom. Kromosom dipilih dengan cara membagi bilangan acak hasil dari langkah 3 dengan panjang kromosom Memilih posisi gen. Untuk memilih posisi gen yang akan dimutasi dengan cara menghitung bilangan acak yang diperoleh dari langkah 3 kemudian dimodulasikan dengan panjang kromosom. Karena pada permasalahan ini akan digunakan metode invertion mutation, maka bangkitkan bilangan acak antara 1 sampai panjang kromosom untuk mendapatkan posisi gen yang kedua. Balik posisi gen yang ada di antara 2 posisi gen yang terpilih dari kromosom tersebut untuk menghasilan kromosom anak.
g. Evaluasi. Proses ini dilakukan kembali untuk menghitung nilai fitness dari masingmasing kromosom. h. Kriteria terminasi. Kriteria teriminasi merupakan kondisi di mana iterasi dalam algoritma genetika dihentikan. Dalam penilitian ini yang menjadi kriteria berhenti yaitu max_gen. Artinya, pada saat maksimum generasi yang telah ditentukan proses pencarian algoritma genetika harus dihentikan. i. Lakukan pengulangan kembali ke langkah d, bila kriteria berhenti sudah dicapai, maka algoritma genetika sudah selesai. Untuk mempermudah dalam pencarian matching maksimum dengan menggunakan algoritma genetika maka dibuat program dengan menggunakan Borland Delphi, berikut adalah gambar flowchart: Mulai
Populasi Awal
Mutasi
Evaluasi
Crossover Seleksi Generasi = max_gen ?
Tidak
Ya Hasil
Selesai Flowchart Algoritma Genetika untuk Matching
Uji Coba Program Akan dilakukan uji coba terhadap program yang telah dibuat. Terdapat suatu permasalahan dengan banyaknya titik di himpunan A adalah 3 dan banyaknya titik di himpunan B adalah 7, dengan tabel bobot sebagai berikut:
Dengan model graph sebagai berikut:
Diselesaikan dengan menggunakan algoritma genetka dengan ketentuan nilai Pc adalah 0.03, Pm adalah 0.8, banyak populasi adalah 20 dan banyak generasi 30. Sehingga diperoleh hasil penyelesaian seperti di bawah ini:
Dengan model graph sebagai berikut:
Dari gambar di atas terlihat bahwa solusi dari permasalahan matching tersebut adalah: A1 diisi oleh B4 dengan nilai 4, A2 diisi oleh B3 dengan nilai 6 dan A3 diisi oleh B7 dengan nilai 5, sehingga diperoleh total bobot adalah 15. PENUTUP Kesimpulan 1. Untuk menerapkan algoritma genetika dalam mencari penyelesaian matching maksimum, yaitu dengan mengasumsikan solusi dari matching yang diwakili oleh satu set parameter. 2. Algoritma genetika dapat diterapkan dalam kehidupan sehari-hari, seperti penyelesaian masalah pencocokan pelamar dengan jabatan, permasalahan pada biro jodoh, pencocokan tentor dengan mata pelajaran, dll. 3. Perbandingan hasil uji coba dengan menggunakan program Borland Delphi yaitu sama dengan hasil yang diperoleh dari penyelesaian dengan algoritma genetika secara manual. Selain itu program dari algoritma genetika juga telah diuji coba pada graph bipartisi dengan banyak titik. Di samping itu algoritma genetika juga memiliki kelemahan, yaitu memerlukan waktu yang lebih lama dalam proses pencariannya. 4. Perbandingan hasil dengan permasalahan dari Abrori, 2012; Andrieanto, 2007 dan Fatmawati, 2006 menghasilkan solusi yang sama. Saran 1. Saran yang dapat diberikan dalam penerapan algoritma genetika pada matching maksimum, yaitu sebaiknya dalam penulisan permasalahan ini lebih diperdalam dengan membandingkan dari setiap metode dalam crossover, sehingga dapat diketahui metode crossover yang paling baik untuk menemukan solusi yang paling optimal. 2. Dalam pembahasan ini memiliki ketentuan banyaknya titik di himpunan A harus lebih dari atau sama dengan banyaknya titik di himpunan B, sehingga perlu untuk membahas permasalahan ini dengan ketentuan banyak titik di himpunan A lebih dari banyak titik di himpunan B.
Daftar Rujukan Abrori, M & Wahyuningsih, R. 2012. Penentuan Matching Maksimum Pada Graf Bipartit Berbobot Menggunakan Metode Hungarian. Jurnal Ilmiah Teknik Industri, 11(1): 9-21. Aldous, Joan M. & Wilson, Robin J. 2004. Graph and Application An Introductory Approach. London: Springer. Andrieanto, Lutfi Nova. 2007. Pencarian Perfect Matching Optimal Dalam Masalah Penugasan Dengan Menggunakan Algoritma Khun Munkres.Skripsi tidak diterbitkan. Malang: FMIPA Universitas Negeri Malang. Desiani, Anita & Muhammad, Arhami. 2007. Konsep Kecerdasan Buatan. Yogyakarta: Andi Publisher. Fatmawati, Mutia. 2006. Algoritma Matching Maksimum Pada Graph Bipartisi.Skripsi tidak diterbitkan. Malang: FMIPA Universitas Negeri Malang. Kusumadewi, Sri. 2003. Artificial Intelligence. Yogyakarta: Graha Ilmu Rosen, H. Kenneth. 2000. Handbook of Discreate and Combinatorial Mathematics. Florida: CRC Press LLC. Turangga, Surya. 2012. Penyelesaian Travelling Salesman Problem With Time Windows (TSPTW) Dengan Algoritma Genetika. Skripsi tidak diterbitkan. Malang: FMIPA Universitas Negeri Malang. Yuliagandi, Devi. 2010. Implementasi Algoritma Genetika Hibrid (First Improvement Seacrh) Pada Travelling Salesman Problem.Skripsi tidak diterbitkan. Malang: FMIPA Universitas Negeri Malang.
