SKRIPSI Jurusan Matematika - Fakultas MIPA UM, 2013

Ukuran Huruf:  Kecil  Sedang  Besar

Penentuan Matching Maksimum pada Graph Bipartisi Berbobot dengan Menggunakan Algoritma Genetika

ANISAK HERITIN

Abstrak


ABSTRAK

 

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. Algoritma yang dapat 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.

Dalam skripsi ini juga dibahas contoh kasus dari pencocokan calon pegawai dengan jabatannya yang diambil dari Abrori dan Wahyuningsih yang berjudul “Penentuan Matching Maksimum Pada Graf Bipartit Berbobot Menggunakan Metode Hungarian”.

Untuk mempermudah dalam mencari solusi permasalahan matching maksimum pada graph bipartisi berbobot dengan menggunakan algoritma genetika maka dibuat software algoritma genetika dengan menggunakan program Borland Delphi. Dalam pembahasan ini telah dibandingkan antara penyelesaian algoritma khun munkres dan algoritma matching maksimum dengan algoritma genetika. Selain itu juga diuji coba pada graph bipartisi dengan banyak titik.