[Programming] [Algoritma] Genetic Algorithm

[hatRed]

permulaan ini dulu deh

A genetic algorithm (GA) is a search technique used in computing to find exact or approximate solutions to optimization and search problems. Genetic algorithms are categorized as global search heuristics. Genetic algorithms are a particular class of evolutionary algorithms (also known as evolutionary computation) that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover (also called recombination).

[johan3000]

bro hatRed,

GA utk memecahin masalah timetabling dan scheduling...
bisa beri contoh kedua hal yg mungkin dipergunakan sehari-hari ?

trims!

[hatRed]

pernah liat2 waktu masih cari2 tentang GA, diaplikasian untuk pemecahan solusi pemasangan pipa..

untuk timetabling/schedulling contoh yg diaplikasikan adalah penjadwalan dosen,ruang,dan waktu.

sorrry threadnya kagak keurus

oh yah, tambahan aja, dulu waktu buat untuk skripsi, aye implementasikan dalam penyusunan huruf ke kata... dari pengenalan huruf

[johan3000]

bro hatRed,

ceritain lebih ditail lagi dunng tentang skipsi anda....

implementasi peyusunan huruf ke kata..... apa tuh manfaat yg dpt diambil dari skripsi tsb?

thanks ya!

[hatRed]

cuman implementasiin doank sih

jadi inspirasinya dari OCR (Optical character Recognition)

karena pengenalan OCR hanya sebatas huruf saja dan juga adanya tingkat error (khsuusnya utk gambar yg kurang jelas/tulisan yg jelek )

maka itu aye ada ide buat lebih lanjut ke "pengenalan kata" <--- gak tau dah namanya apa aye namain aja gitu , sempet berantem sama dosen buat nentuin judul skripsi ^_^

nah misal dari Kata yg seharusnya adalah "Dhamma" dengan OCR maka dikenal menjadi "Dhamma" <--- artinya 100% berhasil

nah kalo misal tulisan jelek misalnya eh dikenal "Dhomma" <--- 5/6*100% = 83% tepat

sebelumnya aye jelasin dulu, aplikasinya ada dua tingkat gitu
1. tingkat satu : pengenalan huruf (OCR)
2. tingkat dua : pengenalan kata (OWR ngarang )


nah, dalam pengenalan huruf (OCR) tingkat pertama itu menggunakan pemetaan bit, jadi dalam tulisan huruf dibuat grid yg dimana titik hitam divalue 1 dan titik putih (tidak kena coretan) divalue 0

nanti dikalkukasi dan dibandingkan/dipetakan dengan database sebelonnya yg diinput duluan (database huruf)

nah kan ketauan persentasenya, diambil ajah yg persentasenya/kecocokannya paling gede

dan seterusnya utk huruf2 berikutnya

tapi karena dalam GA itu harus ada populasi awal maka aye ambil per huruf misal 5 besar atau 3 besar ( nah yg analisa adalah diambil berapa populasinya untuk optimal, jd di skripsi itu aye uji beberapa nilai, gak hanya nilai populasi aja sih ada beberapa parameter GA jg yg diuji)

gituh

nah dari populasi huruf2 tersebut kan jadi modal awal buat GA nya

 

[hatRed]

kembali ke contoh "Dhamma" diatas

disitu ada 6 huruf, misal dalam OCR hasil dari populasi adalah

Kiri ke kanan = nilai cocok besar ke kecil

huruf 1 : D, O, a, Q, U
huruf 2 : h, h, N, N, N
huruf 3 : O, a, o, q, o
huruf 4 : m, M, m, M, M
huruf 5 : m, M, N, N, N
huruf 6 : a, a, o, o, o

nah intinya GA kan nyari solusi optimal dan kalo diambil dari OCR aja kan kenanya "Dhomma"

nah abis itu sama deh dengan pengenalan huruf , yaitu disamain dengan database huruf kata .

dicari persentase ketepatannya yaitu 83% itu berarti belum tepat..

jadi diacak2 (mutasi, crossover, de el el) lagi sama GA, terus tiap generasi di cek nilai persentasenya setiap individu ketemu 100% gak...

nah yg ketemu 100% baru deh ketemu (sukses)

misal ketemu2 pas di

D urutan 1
h urutan 1
a urutan 2
m urutan 3
m urutan 1
a  urutan 2

gitu deh

[johan3000]

nah, dalam pengenalan huruf (OCR) tingkat pertama itu menggunakan pemetaan bit, jadi dalam tulisan huruf dibuat grid yg dimana titik hitam divalue 1 dan titik putih (tidak kena coretan) divalue 0

dilapangan...

tulisan bisa tebal tipis,
tegak maupun miring,
besar maupun kecil

Nah... bagaimana kesulitan 3 hal tsb diatasin ?

(tanya2 cuma asah otak aja lho bro....
  semoga pertanyaan begini gak membosankan)

trims sebelumnya... 

[hatRed]

nah, om johan lihat deh untuk huruf ke 2 yaitu yg seharusnya huruf "h"

itu ternyata dalam lima besar ada dua huruf "h" dan 3 huruf "N"

itu maksudnya bukan item yg sama, yaitu item2 yg berbeda pola bitnya (dari gaya penulisan)

atau dalam kata lain misal

"h" yg pertama huruf "h" dalam Arial
"h" yg kedua huruf "h" dalam Times New Roman

gituh

ga pa pa , seneng kok aye ditanyain, abis pas sidang dosennya kurang nanya sampe aye ajuin lagi "ada pertanyaan lagi gak"

[hatRed]

Algoritma genetika pertama kali diperkenalkan dan dipelajari oleh John Holland dan para muridnya pada tahun 1975 di Michigan. Dia beserta murid-murid dan teman kerjanya menghasilkan buku berjudul "Adaption in Natural and Artificial Systems".  Algoritma ini merupakan algoritma pencarian yang berdasarkan mekanisme seleksi alam dan genetik alami yang menunjukkan pencarian yang paralel, acak, dan global untuk menemukan solusi yang optimal menggunakan komputasi yang sederhana.
Algoritma genetika merupakan teknik komputasi yang berevolusi, salah satunya adalah program yang dapat digunakan untuk tujuan tertentu menggunakan algoritma genetika disebut pemrograman genetika yang dikembangkan oleh John R. Koza pada tahun 1992.
Secara sederhana algoritma umum dari algoritma genetik ini dapat dirumuskan menjadi beberapa langkah, yaitu :
1.   Membentuk suatu populasi individual secara acak
2.   Mengevaluasi kecocokan setiap individual keadaan dengan hasil yang diinginkan
3.   Memilih individual dengan kecocokan yang tertinggi
4.   Bereproduksi, mengadakan persilangan antar individual terpilih diselingi mutasi
5.   Mengulangi langkah 2 - 4 sampai ditemukan individual dengan hasil yang diinginkan
Untuk penggambarannya dapat dilihat pada gambar 2. Dalam algoritma genetika terdapat beberapa istilah seperti istilah dalam genetika seperti kromosom, gen, allele dan sebagainya. Dalam biologi genetik, kromosom terdiri dari susunan gen-gen. Tiap gen mempunyai nilai atau sifat tertentu yang disebut allele, sedangkan posisi gen dalam kromosom disebut locus. Selanjutnya satu atau beberapa kromosom bergabung membentuk paket genetik yang disebut sebagai genotif. Interaksi genotif ini dengan lingkungannya disebut fenotif. Pada algoritma genetik, kromosom bersesuaian dengan string yang dibentuk dari beberapa karakter. Setiap karakter ini mempunyai posisi (locus) dan mengandung nilai tertentu (allele ). Satu atau beberapa string akan bergabung membentuk struktur (genotif), dan bila struktur tersebut didekodekan akan diperoleh satu titik yang merupakan salah satu alternatif solusi (fenotif).
 

Walau dalam pengaplikasiannya suatu string lebih baik bernilai antara 0 atau 1 tetapi dapat pula berisi karakter. Dalam pencarian solusi, algoritma genetik mempunyai beberapa parameter yaitu fungsi fitness atau fungsi objektif, dimana fungsi fitness ini digunakan untuk mendapatkan nilai fitness dari kromosom yang akan menetukan apakah kromosom digunakan untuk operator selanjutnya yaitu operator mutasi, inversi, penghapusan, persilangan, atau reproduksi. Walau demikian pada dasarnya operator genetik dapat terdiri dari reproduksi, mutasi dan penyilangan saja.

K.1   Persilangan
   Setelah diperoleh nilai fitnes dari tiap string maka dapat dilakukan operasi penyilangan, penyilangan dapat dilakukan dengan mengambil dua gen induk untuk membuat satu atau lebih gen pewaris (offspring). Salah satu bentuk sederhana adalah dengan mengambil secara acak urutan locus dari kromosom lalu urutan locus yang diambil sampai terakhir ditukar ke dalam gen induk yang lain sesuai dengan locus yang diambil. Untuk penggambarannya dapat dilihat gambar 3.
Kromosom 1   11011 | 00100110110
Kromosom 2   11011 | 11000011110
Offspring 1   11011 | 11000011110
Offspring 2   11011 | 00100110110
 






Gambar 3. Penyilangan sederhana

K.2   Mutasi
   Mutasi adalah perubahan secara acak nilai dari kromosom. Suatu kromosom yang kurang fitnes dipilih lalu diubah salah satu nilainya secara acak untuk mendapatkan nilai kromosom baru. Penggambaran dari mutasi dapat dilihat pada gambar 4.
Original offspring 1   1101111000011110
Original offspring 2   1101100100110110
Mutated offspring 1   1100111000011110
Mutated offspring 2   1101101100110110

Gambar 4. Mutasi sederhana

K.3   Reproduksi
   Operator reproduksi menyalin kromosom yang nilai fitnesnya tinggi yang akan digunakan kembali untuk generasi berikutnya dari suatu populasi, sehingga kromosom yang nilai fitnesnya tinggi mempunyai kesempatan lebih besar untuk bertahan.

K.4   Parameter genetika
   Algoritma genetika mempunyai dua parameter dasar yaitu parameter kemungkinan mutasi dan kemungkinan penyilangan. Kemungkinan penyilangan dapat lebih besar, dan biasanya yang disilangkan adalah kromosom yang baik dengan yang baik atau yang baik dengan yang buruk atau yang buruk dengan yang buruk, bahkan bisa saja suatu kromosom disilangkan dengan dirinya sendiri. Penyilangan dilakukan agar mendapatkan turunan yang diharapkan lebih baik dari induknya. Kemungkinan mutasi atau seberapa sering mutasi dilakukan tergantung kasusnya.
   Selain itu ada juga beberapa parameter yaitu, parameter jumlah populasi awal dimana menentukan jumlah kromosom yang dibangkitkan untuk seleksi, lalu parameter generasi maksimal dimana digunakan sebagai parameter berhenti yang menentukan sampai generasi keberapa suatu algoritma genetika akan berjalan.

[johan3000]

nah, om johan lihat deh untuk huruf ke 2 yaitu yg seharusnya huruf "h"

itu ternyata dalam lima besar ada dua huruf "h" dan 3 huruf "N"

itu maksudnya bukan item yg sama, yaitu item2 yg berbeda pola bitnya (dari gaya penulisan)

atau dalam kata lain misal

"h" yg pertama huruf "h" dalam Arial
"h" yg kedua huruf "h" dalam Times New Roman

gituh

ga pa pa , seneng kok aye ditanyain, abis pas sidang dosennya kurang nanya sampe aye ajuin lagi "ada pertanyaan lagi gak"

Dosennya kurang tanya paling dia gak baca skripsi anda (googling dulu),... nah begitu elu maju.. trus mau tanya apa lagi ?...

kalau utk mengenailin satu huruf saja...
adakah cara2 mengajarkan program tsb utk pintar menebak HURUF saja gak?

Apakah algorihmanya supaya program bisa dgn BIJAKSANA mengenal sebuah huruf?
(tentu dgn asumsi : huruf bisa agak besar/kecil, tulisan bisa tebal/tipis, posisi bisa miring sekian derajat)....

asah otak lagi bro..........

[hatRed]

pake vektor