tugas akhir biro jodoh 11 jan 2011
TRANSCRIPT
A. Permasalahan Terdapat sebuah agen biro jodoh yang menangani wanita maupun pria yang mempunyai kesulitan dalam mencari pasangan hidupnya. Setiap client mempunyai atribut diri seperti warna kulit, tingkat penghasilan, jumlah saudara, dll. Selain atribut diri, client juga memiliki kriteria pasangan. Contoh : Tabel 1 Tabel atribut dan kriteria Nama Kriteria Kriteria yg diinginkan Andi Kulit putih Kulit coklat Penghasilan Penghasilan 10jt/bulan 10jt/bulan Saudara = 4 Saudara = 5 Maria Kulit kuning Kulit coklat langsat muda Penghasilan Penghasilan 7jt/bulan 10jt/bulan Saudara=2 Saudara = 1 Dari tabel 1, dapat dilihat masingmasing client mempunyai atribut dan kriteria untuk mendapatkan pasangannya. Biro jodoh perlu menempatkan pasangan client yang mempunyai atribut sifat dan kriteria yang sama dalam satu meja.
dalam satu meja dengan ketentuan bahwa pasangan-pasangan tersebut mempunyai atribut sifat dan kriteria pasangan yang hampir sama. Oleh karena itu, dibutuhkan suatu metode penempatan pasangan menggunakan algoritma evolusi. B. Batasan Masalah Batasan masalah dari permasalahan biro jodoh adalah : 1. Masing-masing client memiliki atribut sifat dan kriteria calon pasangan yang diinginkan. 2. Kriteria sudah ditentukan, tidak dapat ditambah sendiri. 3. Setiap klien memiliki prioritas criteria yang mana terdapat minimal 2 kriteria yang cocok. C. Penyelesaian Genetika Dengan Algoritma
a. Struktur Data Struktur data yang digunakan untuk atribut dan criteria adalah menggunakan linked list, yang nantinya akan direpresentasikan dalam bilangan biner. Tabel.2 Tabel Daftar Atribut dan Kriteria No Nama Kriteria Atribute 1 Warna kulit Putih Sawo matang Hitam 2 Umur 20-25 26-30 31-40 3 Pekerjaan Pegawai Wiraswasta Lain - lain 4 Penghasilan 5.000.000 5 Tinggi badan 150cm 70kg Olahraga Seni Lain - lain Single Duda/Janda Duda/Janda Beranak
perbulan Tinggi badan Berat badan Hobi Status 100cm150cm 40kg70kg Seni Duda/Ja nda Beranak Hitam 20-25 Lain lain 5.000. ilan 00000 perbulan 5.000.0 00 Tinggi >150cm >150cm badan Berat 70kg badan Hobi Seni Lain lain Status Single Single 2 Anis Warna Putih Sawo kulit matang Umur 31-40 31-40 Pekerjaa Wirasw Pegawai n asta Penghas >5.000. 1.000.0 ilan 000 00-
Warna kulit Umur Pekerjaa n Penghas ilan perbulan Tinggi badan Berat badan Hobi Status
Putih 20-25 Wirasw asta >5.000. 000 >150cm
4
Bett y
Warna kulit Umur Pekerjaa n Penghas ilan perbulan Tinggi badan Berat badan Hobi
40kg70kg Lain - Olahrag lain a Single Duda/Ja nda Beranak Putih Hitam 20-25 Wirasw asta >5.000. 000 20-25 Wirasw asta 1.000.0 005.000.0 00 >150cm 40kg70kg Seni Single Putih 31-40 Wirasw asta
>150cm 70kg badan Hobi Lain lain Status Duda/Ja nda Beranak
>5.000. 000
>150cm >70kg Olahrag a Duda/Ja nda Beranak 3 Gani sh
badan Berat badan Hobi Status Warna kulit Umur Pekerjaa n Penghas ilan perbulan Tinggi badan Berat badan Hobi Status Warna kulit Umur Pekerjaa n Penghas ilan perbulan Tinggi badan Berat badan Hobi Status
40kg70kg Seni Single Putih 20-25 Wirasw asta 1.000.0 005.000.0 00 100cm150cm 70kg Lain lain Duda/Ja nda Sawo matang 20-25 Pegawai 150cm
Warna kulit Umur Pekerjaa n Penghas ilan perbulan
Lain lain Duda/Ja Duda/Ja nda nda Beranak Beranak Hitam Sawo matang 31-40 26-30 Pegawai Lain lain >5.000. 150cm >70kg Olahrag a Single
100cm150cm 40kg70kg Seni Single
=Dengan, = Nilai probabilitas rata rata kedua belah pihak P1 = Probabilitas Pihak 1 P2 = Probabilitas Pihak 2 Untuk menghitung probabilitas semua kromosom dalam satu individu, digunakan rumus :
Untuk permulaan dibangkitkan individu secara random sebanyak 3 buah dalam sebuah populasi. individu ini berisi pasangan nama pria dan wanita yang masing masing membawa atribut yang merupakan pasangan kromosom dan kemudian akan dihitungan kecocokan dari kedua belah pihak tersebut. Dan untuk melihat prosentase kecocokan dilakukan dengan mentabelkan attribute yang dibawa wanita dengan attribute yang diinginkan si pria, begitu pula sebaliknya. Setiap pasangan atribut tersebut memiliki 24 kolom yang menyatakan jumlah attribute yang mungkin(ada 8 jenis attribute dengan 3 buah attribute untuk masing masing jenisnya). Jika bernilai 1, maka attribute tersebut dimiliki oleh pria/wanita yang dimaksud, dan untuk sebaliknya maka akan dinilai dengan 0. Kemudian akan dihitung probabilitas kecocokannya dengan menjumlahkan pasangan nilai 1 yang terjadi dikali dengan 3 dan dibagi jumlah dari jumlah attribute yg mungkin.
Ptotal=
Dengan, Pfinal = probabilitas semua kromosom dalam satu individu N = jumlah kromosom P = Probabilitas masing masing individu Individu 1 = 1 4 2 1 3 5 4 3 5 2
Untuk kromosomnya : 1 1 1 2 0 0 3 0 0 4 1 0 5 0 1 6 0 0
P=Dengan, P= Probabilitas Kecocokan Pasangan n = jumlah atribut yang mungkin x = gen yang bernilai 1 y = jumlah attribute per jenis attribute Setelah itu barulah menghitung rata rata probabilitas kedua belah pihak dengan cara:
Bet ty Alf ath Alf ath Bet ty 7 0 0
0 0
0 0
1 1
1 1
0 0
0 0
8 1 0
9 0 1
10 0 0
11 0 0
12 1 1
0 0 13 0 0 0 0 19 1 1 0 0
1 1 14 0 0 0 0 20 0 0 0 1 1 0 1 2 1 0
0 0 15 1 1 1 1 21 0 0 1 0 3 0 0
0 0 16 1 1 0 0 22 1 1 0 1 4 0 1
1 1 17 0 0 0 1 23 0 0 1 0 5 1 0
0 0 18 0 0 1 0 24 0 0 0 0 6 0 0
0 0 19 0 0
0 0 20 1 0
1 1 21 0 1
0 0 22 1 1
1 0 23 0 0
0 1 24 0 0
0 0
1 0 1 0 0 2 1 1
0 1 3 0 0
1 1 4 0 1
0 0 5 0 0
0 0 6 1 0
Yu ni Ga nis h Ga nis h Yu ni 7 1 0 0 0 13 0 0 0 0 19 0 0 0
1
0
0
1
0
0
Din da Mi ko
1
0
0
0
0
1
Mi ko Din da 7 1 0
0 1
1 0
0 0
1 0
0 0
0 1
8 0 0 1 1 14 1 1 1 0 20 0 1 0
9 0 1 0 0 15 0 0 0 1 21 1 0 1
10 0 1 0 0 16 0 1 1 0 22 0 1 1
11 1 0 1 0 17 0 0 0 0 23 0 0 0
12 0 0 0 1 18 1 0 0 1 24 1 0 0
8 0 1
9 0 0
10 0 0
11 1 1
12 0 0
1 1 13 0 0
0 0 14 0 1
0 0 15 1 0
0 0 16 1 1
0 0 17 0 0
1 1 18 0 0
1
0 1 2 0
0 3 1
0 4 1
0 5 0
1 6 0 Ani s Ma rla n Ma rla n Ani s 7 0 0 1 1 13 0 0 0 0 19 0 0 1 0 1 1 0 2 0 1 3 0 0 4 0 0 5 0 1 6 1 0
Ra hm a Ha ri
0
0
0
1
1
0
0 0 0 1 0 0 1
Ha ri Ra hm a 7 0 0
1 1
0 0
0 0
0 1
1 0
0 0
0
1
0
0
0
1
8 1 0 0 0 14 1 1 0 0 20 1 1 0 1
9 0 1 0 0 15 0 0 1 1 21 0 0 0 0
10 0 1 0 0 16 0 0 0 0 22 1 1 1 1
11 0 0 0 1 17 1 1 0 1 23 0 0 0 0
12 1 0 1 0 18 0 0 1 0 24 0 0 0 0
8 0 1
9 1 0
10 1 0
11 0 1
12 0 0
0 0 13 0 0
0 1 14 1 1
1 0 15 0 0
1 0 16 1 1
0 0 17 0 0
0 1 18 0 0
0 0 19 0 0
0 0 20 0 0
1 1 21 1 1
0 0 22 1 0
1 1 23 0 0
0 0 24 0 1
Individu 2 = 1 1 1 0 2 5 2 1 3 2 3 0 4 0 4 4 5 1 5 3 6 0
0 1
1 0
0 0
0 0
0 0
1 1
Din da
Alf ath Alf ath Din da 7 1 0 1 1 13 0 0 0 019 0 1 0 0
1
0
0
1
0
0
0 13 0 0 0 0 19 0 0 0 1
1 14 1 1 0 0 20 0 0 1 0
0 15 0 0 1 1 21 1 1 0 0
0 16 0 1 0 0 22 0 1 1 0
0 17 0 0 1 0 23 0 0 0 0
1 18 1 0 0 1 24 1 0 0 1
0 1
0 0
1 0
1 0
0 0
0 1
8 0 1 0 0 14 0 0 0 020 1 0 0 0
9 0 0 0 0 15 1 1 1 121 0 0 1 1
10 0 0 0 0 16 1 1 0 022 1 1 0 1
11 1 0 1 0 17 0 0 0 023 0 0 1 0
12 0 1 0 1 18 0 0 1 124 0 0 0 0
Ani s Ga nis h Ga nis h Ani s 7 0 0 0 1 13 0 0 0 0
1 1 0
2 0 1
3 0 0
4 0 1
5 0 0
6 1 0
1
0
0
1
0
0
0
1
0
0
0
1
Yu ni Mi ko Mi ko Yu ni 7 1 0 1
1 0 1
2 1 0
3 0 0
4 0 1
5 0 0
6 1 0
8 1 0 1 0 14 1 1 1 0
9 0 1 0 0 15 0 0 0 1
10 0 1 0 0 16 0 1 1 0
11 0 0 1 1 17 1 0 0 1
12 1 0 0 0 18 0 0 0 0
0 1
1 0
0 0
1 0
0 0
0 1
8 0 1 0
9 0 0 0
10 0 0 0
11 1 1 0
12 0 0 1
19 0 0 0 0
20 1 1 0 1
21 0 0 1 0
22 0 1 1 1
23 0 0 0 0
24 1 0 0 0
hm a Ma rla n Ma rla n Ra hm a 7 0 0 1 0
0
1
0
0
1
0
0
0
1
0
0
1
Bet ty Ha ri Ha ri Bet ty 7 0 0 0 0 13 0 0 0 0 19 1 0 0 0
1 1 0
2 0 0
3 0 1
4 1 1
5 0 0
6 0 0
1
0
0
1
0
0
1 0
0 0
0 1
0 1
1 0
0 0
8 0 0 0 1 14 1 1 0 0 20 0 1 0 0
9 1 1 0 0 15 0 0 1 1 21 1 0 0 0
10 1 1 0 0 16 1 0 0 0 22 1 1 1 0
11 0 0 0 0 17 0 1 0 1 23 0 0 0 0
12 0 0 1 1 18 0 0 1 0 24 0 0 0 1
8 1 1 0 1 14 0 1 0 0 20 0 0 1 1
9 0 0 1 0 15 1 0 1 1 21 0 1 0 0
10 0 0 1 0 16 1 1 0 0 22 1 0 0 1
11 0 1 0 1 17 0 0 1 1 23 0 0 0 0
12 1 0 0 0 18 0 0 0 0 24 0 1 1 0
13 0 0 0 0 19 0 0 1 1
Individu 3 = 1 5 1 0 2 2 2 1 3 0 3 1 4 0 4 3 5 0 5 4 6 1
Ra
1 0
2 0
3 1
4 1
5 0
6 0
Yu ni
Alf ath Alf ath Yu ni 7 1 0 1 0 13 0 0 0 0 19 0 1 0 1
1
0
0
1
0
0
0 1 1 13 0 0 0 0 19 0 0 0 0
1 0 0 14 1 1 0 0 20 1 0 1 1
0 0 0 15 0 0 1 1 21 0 1 0 0
0 0 0 16 0 1 0 0 22 0 1 1 1
1 0 1 17 1 0 1 1 23 0 0 0 0
0 1 0 18 0 0 0 0 24 1 0 0 0
0 1
0 0
1 0
1 0
0 0
0 1
8 0 1 0 1 14 1 0 0 0 20 0 0 0 0
9 0 0 0 0 15 0 1 1 1 21 1 0 1 0
10 0 0 0 0 16 0 1 0 0 22 0 1 0 0
11 1 0 1 0 17 0 0 0 0 23 0 0 0 0
12 0 1 0 1 18 1 0 1 1 24 1 0 1 1
Din da Ga nis h Ga nis h Din da 7 1 0 0 1 13 0
1 0 0
2 1 1
3 0 0
4 0 1
5 1 0
6 0 0
1
0
0
1
0
0
Ani s Mi ko Mi ko Ani s 7 0
1 1 1
2 0 0
3 0 0
4 0 1
5 0 0
6 1 0
1
0
0
0
0
1
0 0
1 1
0 0
1 0
0 0
0 1
8 0 0 1 0 14 0
9 0 1 0 0 15 1
10 0 1 0 0 16 1
11 1 0 1 0 17 0
12 0 0 0 1 18 0
8 1
9 0
10 0
11 0
12 1
0 0 0 19 0 0 0 0
1 1 0 20 1 1 0 0
0 0 1 21 0 0 1 1
1 1 0 22 1 1 1 1
0 0 0 23 0 0 0 0
0 0 1 24 0 0 0 0
0 0 1
0 1 0
1 0 0
0 0 0
0 0 0
1 1 1
Bet ty Ma rla n Ma rla n Bet ty 7 0 0 1 0 13 0 0 0 0 19 1 0 1 0
1 1 0
2 0 1
3 0 0
4 1 0
5 0 1
6 0 0
0
0
1
0
0
1
Ra hm a Ha ri Ha ri Ra hm a 7 0 0 0 0 13 0 0 0 0 19 0
1 0
2 0
3 1
4 1
5 0
6 0
0
0
1
1
0
0
0
0
1
1
0
0 8 1 0 0 1 14 0 1 0 0 20 0 1 0 1 9 0 1 0 0 15 1 0 1 1 21 0 0 0 0 10 0 1 0 0 16 1 0 0 0 22 1 1 1 1 11 0 0 0 1 17 0 1 0 0 23 0 0 0 0 12 1 0 1 0 18 0 0 1 1 24 0 0 0 0
1 1
0 0
0 0
0 1
1 0
0 0
8 0 1 0 1 14 1 1 0 0 20 0
9 1 0 1 0 15 0 0 1 1 21 1
10 1 0 1 0 16 1 1 0 0 22 1
11 0 1 0 0 17 0 0 1 1 23 0
12 0 0 0 1 18 0 0 0 0 24 0
b. Perhitungan nilai Penalty y Individu 1 :
== (0.13 + 0.13)/2 = 0.13
Kromosom 1 =
P1== (6*3)/24 = 0.75 Kromosom 4 :
P1== (5*3)/24 = 0.63
P2== (5*3)/24 = 0.63 Dari P1 dan P2 itu lalu akan dihitung nilai rata2 P dengan rumus :
P2== (4*3)/24 = 0.50
== (0.75+ 0.63)/2 = 0.69
== (0.63+ 0.50)/3 = 0.56
Kromosom 2 =
P1== (3*3)/24 = 0.38
Kromosom 5 :
P1== (4*3)/24 = 0.50
P2== (4*3)/24 = 0.50
P2== (4*3)/24 = 0.50
== (0.38 + 0.50)/2 = 0.44%
== (0.50+ 0.50)/3 = 0.50 Untuk Probabilitas total dari individu 1 :
Kromosom 3 :
P1== (1*3)/24 = 0.13
Ptotal=
P2== (1*3)/24 = 0.13
=0.69+0.44+0.13+0.56+0.50 5 = 0.46
y
Individu 2 :
== (3*3)/24 = 0.38 = (0.13+ 0.13)/2 = 0.25
Kromosom 1 =
P1= P2== (4*3)/24 = 0.50
Kromosom 4 :
P1== (3*3)/24 = 0.38
Dari P1 dan P2 itu lalu akan dihitung nilai rata2 P dengan rumus :
P2== (3*3)/24 = 0.38
== 0.38 + 0.50 = 0.44
== (0.38 + 0.38)/2 = 0.38
Kromosom 2 =
P1== (3*3)/24 = 0.38 Kromosom 5 :
P1== (4*3)/24 = 0.50
P2== (2*3)/24 = 0.25
P2== (3*3)/24 = 0.38
== 0.38 + 0.25 = 0.31
== (0.50+ 0.38)/2 = 0.44 Untuk Probabilitas total dari individu 1 :
Kromosom 3 :
P1== (2*3)/24 = 0.25
Ptotal=
P2== (2*3)/24 = 0.25
=0.44+0.31+0.25+0.38+0.44 5 = 0.28
y
Individu 3 :
== (0*3)/24 = 0.00 = (0.50 + 0.38)/2 = 0.44
Kromosom 1 =
P1= P2== (3*3)/24 = 0.38
Kromosom 4 :
P1== (5*3)/24 = 0.63
Dari P1 dan P2 itu lalu akan dihitung nilai rata2 P dengan rumus :
P2== (4*3)/24 = 0.50
== (0.00 + 0.38)/2 = 0.19
== (0.63 + 0.50)/2 = 0.56
Kromosom 2 =
P1== (3*3)/24 = 0.38 Kromosom 5 :
P1== (1*3)/24 = 0.13
P2== (6*3)/24 = 0.75
P2== (4*3)/24 = 0.50
== (0.38 + 0.75)/2 = 0.56
== (0.13+ 0.50)/2 = 0.31
Kromosom 3 :
P1== (4*3)/24 = 0.50
Untuk Probabilitas total dari individu 1 :
P2== (3*3)/24 = 0.38
Ptotal=
=0.19+0.56+0.44+0.56+0.31 5 = 0.41
c. Perhitungan Fitness Nilai fitness yang semakin kecil menunjukan individu yang semakin baik. Nilai fitness dihitung berdasarkan :
F=
Didapatkan secara random n = 3 dan r = 2 Individu I : Individu awal : 1 2 3 4 5 4 1 5 3 2 Indivitu akhir : 1 2 3 4 5 4 1 2 3 5 Individu 3 : 1 2 5 2 Individu akhir : 1 2 5 1
Jadi, Nilai Fitness individu 1 :
F=
=
= 0.69
3 1 3 2
4 3 4 3
5 4 5 4
Nilai Fitness individu 2 :
F=
=
= 0.78f. Metode Mutasi Mutasi dilakukan jika salah satu atau lebih kromosom yang dimiliki individu bernilai kurang dari sama dengan 0.25%. Metode nya dengan inverse mutation. Algortimanya dengan membangkitkan bilangan random dengan rumus :
Nilai Fitness individu 3 :
F=
=
= 0.70
d. Metode Seleksi Metode seleksi yang digunakan pada permasalahan ini adalah metode seleksi turnamen (tournament Selection) dimana akan diambil 2 individu terbaik yang akan dilakukan operasi crossover. Dengan membandingkan nilai fitness dari 3 individu tersebut, maka didapat individu1 dan 3 yang akan dijadikan induk pada generasi selanjutnya. e. metode Crossever metode crossover yang digunakan adalah metode one point cut crossover. Dimana algoritma nya adalah sebagai berikut : Inisalisasi n R