APLIKASI ALGORITMA GENETIKA DALAM INFORMATION RETRIEVAL

APLIKASI ALGORITMA GENETIKA DALAM INFORMATION RETRIEVAL

Penerjemah: https://komarudintasdik.wordpress.com

Judul asli: Applied Genetic Algorithms in Information Retrieval

Bangorn Klabbankoh

Identitas pengarang

Abstrak: Artikel ini mempresentsikan online information retrieval menggunakan algoritma genetika untuk meningkatkan efisiensi information retrieval. Dalam model ruang vektor, information retrieval didasarkan pada ukuran kesamaan di antara query dan dokumen. Dokumen-dokumen dengan kesamaan tinggi dengan query dianggap lebih relevan untuk query tersebut dan harus dilakukan retrieval terdahulu. Dalam algoritma genetika, tiap query direpresentasikan dengan chromosome. Chromoseme-chromosome ini melakukan feed ke dalam proses operator genetika: selection, crossover, dan mutation hingga kami memperoleh query chromosome optimal untuk document retrieval. Hasil pengujian kami menunjukkan bahwa information retrieval dengan 0.8 probabilitas crossover dan 0.01 probabilitas mutation memberikan precision tertingi sementara 0.8 probabilitas crossover dan 0.3 probabilitas mutation memberikan recall tertinggi. Barakallahu li wa lakum….

  1. Pendahuluan

Algoritma genetika (GA) merupakan metode pencarian probabilistik yang telah dikembangkan oleh John Holland tahun 1975. [1][2] GA telah mengaplikasikan seleksi alami dan genetika alami dalam kecerdasan  buatan untuk menemukan solusi optimal secara global untuk masalah optimalisasi dari solusi yang mungkin terjadi.

Sekarang, GA telah diaplikasikan untuk berbagai domain, mencakup daftar perjalanan, penjadwalan, kontrol robot, verifikasi tanda tangan, pengolahan gambar, pengemasan, routing, sistem kontrol pipeline, pembelajaran mesin, dan information retrieval [3][5].

  1. Prinsip-Prinsip Algoritma Genetika

2.1  Prinsip-Prinsip Dasar

GA dikelompokkan menjadi 5 komponen dasar seperti berikut:

1)      Representasi chromosome untuk solusi yang mungkin diambil untuk masalah optimalisasi.

2)      Populasi awal solusi yang mungkin diambil.

3)      Fungsi fitness yang mengevaluasi tiap solusi.

4)      Operator genetika yang menghasilkan populasi baru dari populasi yang ada.

5)      Parameter kontrol seperti ukuran populasi, probabilitas operator genetika, jumlah generation, dll.

2.2  Proses Algoritma Genetika

GA merupakan metode iteratif yang melakukan maintain populasi ukuran konstan dari solusi-solusi yang mungkin diambil. Selama tiap langkah iterasi, disebut generation, fitness populasi terbaru dievaluasi, dan populasi diseleksi berdasarkan nila-nilai fitness. Fitness chromosome yang lebih tinggi dipilih untuk reproduksi di bawah tindakan crossover dan mutation untuk membentuk populasi baru. Fitness chromosome yang lebih rendah dieliminasi. Populasi baru ini dievaluasi, diseleksi dan di-feed ke dalam proses operator genetika lagi hingga kami memperoleh solusi optimal (lihat gambar 1)

  1. Online Information Retrieval menggunakan Algoritma Genetika

3.1  Representasi Chromosome

Online information retrieval menggunakan algoritma genetika didasarkan pada model ruang vektor. Di dalam model ini, dokumen dan query direpresentasikan dengan vektor. Dokumen tertentu direpresentasikan dengan vektor terms dan query tertentu direpresentasikan dengan vektor query terms.

Lihat Gambar 1 Proses Algoritma Genetika!

–          Menghasilkan populasi awal

–          Menaksir populasi awal

–          Memilih populasi

–          Crossover populasi baru

–          Mutasi populasi baru

–          Menaksir populasi baru

–          Pencarian berakhir?

–          Berhenti

Vektor dokumen (Doc) dengan n keywords dan vektor query dengan m query term dapat direpresentasikan sebagai berikut:

Doc = (term1,term2,term3….termn)

Query = (qterm1, qterm2, qterm3,…..qtermm)

Kami menggunakan vektor term biner, sehingga tiap termi (atau qtermi) bisa 0 atau 1. Termi di-set ke nol ketika termi tidak ada dalam dokumen dan di-set ke satu  ketika termi ada dalam dokumen.

Contohnya, user memasukkan sebuah query ke dalam sistem kami yang mampu melakukan retrieval 5 dokumen. Dokumen-dokumen ini adalah

Doc1 = {Relational Databases, Query, Data Retrieval, Computer Networks, DBMS}

Doc2 = {Artificial Intelligence, Internet, Indexing, Natural Language Processing}

Doc3 = {Databases, Expert System, Information Retrieval System, Multimedia}

Doc4 = {Fuzzy Logic, Neural Network, Computer Networks}

Doc5 = {Object-Oriented, DBMS, Query, Indexing}

Semua kunci dokumen ini disusun dalam urutan ascending seperti

Artificial Intelligence, Computer Networks, Data Retrieval, Databases, DBMS, Expert

System, Fuzzy Logic, Indexing, Information Retrieval System, Internet, Multimedia, Natural

Language Processing, Neural Network, Object-Oriented, Query, Relational Databases

Encode dalam representasi chromosome seperti

Doc1 = 0 1 1 0 1 0 0 0 0 0 0 0 0 0 1 1

Doc2 = 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0

Doc3 = 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0

Doc4 = 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0

Doc5 = 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0

Chromosome-chromosome ini disebut populasi awal yang melakukan feed ke dalam proses operator genetika. Panjang chromosome tergantung jumlah keyword dokumen yang mengalami retrieval dari user query. Dari contoh kami penjang masing-masing chromosome adalah 16 bit.

3.2  Evaluasi Fitness

Fungsi fitness merupakan ukuran performa atau fungsi reward yang mengevaluasi sebagus apa tiap solusi yang diambil. Masalah information retrieval adalah bagaimana melakukan retrieval dokumen yang dibutuhkan user. Terlihat bahwa kami dapat menggunakan fungsi fitness pada tabel 1 untuk menghitung jarang antara dokumen dan query. Dari tabel 1, ada 2 jenis fungsi fitness: vektor weighted term dan vektor term biner.

Kami mendefinisikan X = (x1 , x2 , x3 ,….., xn) , | X | = jumlah term yang terjadi dalam X , | X ÇY | = jumlah term yang terjadi dalam X dan Y [6]

Tabel 1 Fungsi Fitness

Hasil dari fungsi-fungsi fitness ini adalah interval 0 sampai 1. Dengan 1.0 berarti dokumen dan query adalah kesamaan (sameness). Nilai-nilai mendekati 1.0 berarti dokumen dan query lebih relevan dan nilai-nilai mendekati 0.0 berarti dokumen dan query kurang relevan. Nilai-nilai yang menilai dari fungsi-fungsi fitness disebut “fitness”.

3.3  Selection

Setelah kami mengevaluasi fitness populasi, langkah selanjutnya adalah seleksi chromosome. Seleksi menggunakan prinsip-prinsip ‘survival of the fittest”. Fitness chromosome yang cukup dipilih untuk reproduksi. Chromosome lemah atau fitness chromosome rendah dapat dipilih sebagian atau seluruhnya.

3.4  Crossover

Crossover adalah operator genetika yang menggabungkan dua chromosome bersama untuk menghasilkan keturunan baru. Crossocver hanya terjadi dengan suatu probabilitas (probabilitas crossover). Chromosome tidak ditujukan untuk crossover remain unmodified. Intuisi di balik crossover merupakan eksplorasi solusi baru dan eksploitasi solusi lama. GA membangun solusi yang lebih baik dengan menggabungkan karakteristik bagus chromosome bersama-sama. Fitness chromosome yang lebih tinggi memiliki peluang lebih besar untuk dipilih daripada yang lebih rendah, sehingga solusi yang baik selalu aktif untuk generation selanjutnya.

Teknik crossover mencakup satu point crossover, dua point crossover dan multiple point crossover. Jika struktur itu direpresentasikan sebagai binary strings, crossover dapat diimplementasikan dengan menggunakan sebua point secara acak, yang disebut crossover point, dan mempertukarkan segemen-segmen tersebut ke kanan point ini. Contohnya, dua chromosome adalah crossover di antara posisi 5 dan 11.

1 0 1 1 1 1 1 1 0 0 1 1 1 0 1

1 0 0 1 1 0 0 1 1 1 1 0 0 0 0

Crossover hasil menghasilkan dua chromosome baru.

1 0 1 1 1 0 0 1 1 1 1 1 1 0 1

1 0 0 1 1 1 1 1 0 0 1 0 0 0 0

3.5  Mutation

Mutation melibatkan modifikasi nilai-nilai tiap gene sebuah solusi dengan suatu probibilitas (probabilitas mutasi). Berdasarkan perubahan nilai-nilai bit dari chromosome, memberikan breeds yang berbeda. Chromosome bisa lebih baik atau lebih jelek daripada chromosome lama. Jika chromosome itu lebih jelek daripada chromosome lama, akan diseleksi pada tahap seleksi. Tujuan mutation adalah me-restore dan mengeksplorasi varietas data yang hilang. Contohnya: secara acak memutasikan chromosome pada posisi 10.

1 0 1 1 1 1 1 1 0 0 1 1 1 0 1

Hasil 1 0 1 1 1 1 1 1 0 1 1 1 1 0 1

3.6  Proses Sistem Kami

  1. User memasukkan query ke dalam sistem kami
  2. Mencocokkan keyword dari user query dengan daftar keyword
  3. Populasi mem-feed ke dalam proses operator genetika seperti selection, crossover, dan mutation.
  4. Lakukan langkah 4 ingga generation maksimal diperoleh. Kami akan mendapatkan query chromosome yang optimal untuk document retrieval.
  5. Lakukan decode query chromosome yang optimal untuk query dan me-retrieve document dari basis data.
  1. Eksperimen

4.1  Formulasi Kasus Tes

Tes eksperimen ini untuk 21 query dengan 3 fungsi fitness yang berbeda: jaccard coefficient (F1), cosine coefficient (F2) dan dice coefficient (F3). Tes fungsi fitness tertentu dengan sekelompok parameter: probabilitas crossover (Pc = 0.8), dan probabilitas mutation (Pm=0.01, 0.10, 0.30) untuk membandingkan efisiensi sistem retrieval. Efisiensi information retrieval mengukuru dari recall sampai precision.

Recall didefinisikan sebagai proporsi dokumen relevan yang di-retriev (lihat persama 1) [4][6]

Recall=jumlah dokumen yang di-retrieve dan relevan                       (1)

Total relevan dalam koleksi

Precision didefinisikan sebagai proporsi dokumen yang di-retrive itu relevan. (lihat persamaan 2) [4][6]

Precision=jumlah dokumen yang di-retrieve dan relevan

Total yang di-retrieve

Basis data yang diuji terdiri atas 343 dokumen yang diambil dari proyek mahasiswa Fakultas Teknologi Informasi, King Mongkut’s Institute of Technology Ladkrabang

Tabel 2 Information Retrieval oleh 3 Fungsi Fitness dengan PC=0.8 dan PM=0.01

4.2  Hasil Eksperimen

Pengujian awal menunjukkan bahwa

  1. Eksperimen dari pengujian 3 fungsi fitness menunjukkan bahwa query-query yang optimal dari fungsi-fungsi fitness ini semuanya adalah query yang sama tapi ada nilai fitness yang berbeda (F1, F2, dan F3) seperti tampak pada Tabel 2. Dari tabel 2, RetRel didefinisikan sebagai jumlah dokumen relevan yang di-retrieve dan RetNRel didefinisikan sebagai jumlah yang di-retrieve tapi bukan dokumen yang relevan.
  1. Information retrieval dengan Pc=0.8 dan Pm=0.01 menghasilkan precision tertinggi 0.746 sementara information retrieval dengan Pm=0.10 menghasilkan precision sedang 0.560 dan information retrieval dengan Pm=0.10 menghasilkan recall terendah 0.786 seperti pad Gambar 2.
  1. Kesimpulan

Dari eksperimen awal menunjukkan bahwa precision dan recall adalah invert. Untuk menggunakan parameter mana tergantung pada kepatutan bahwa untuk apa user melakukan retrieve. Pada kasus dokumen precision tinggi lebih disukai, parameter tersebut akan menjadi probabilitas crossover tinggi dan probabilitas mutation rendah. Sedangkan dalam kasus dokumen yang lebih relevan (recall tinggi) lebih disukai, parameter tersebut akan menjadi probabilitas mutation tinggi dan probabilitas crossover rendah. Dari eksperimen awal menunjukkan bahwa kami dapat menggunakan GA dalam information retrieval. Kajian yang berkelanjutan adalah pengujian dengan basis data yang lebih besar dan merepresentasikan dokumen yang sudah di-retrieve             dengan sederetan nilai-nilai fitness yang merepresentasikan keinginan user. Barakallahu li wa lakum……

Referensi

One response to “APLIKASI ALGORITMA GENETIKA DALAM INFORMATION RETRIEVAL

  1. Great information! Very useful and impressive,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s