Algoritma Genetika

Algoritma Genetika

        Evolutionary Algorithm merupakan terminologi umum yang menjadi paying. Bagi empat istilah: algoritma genetika (genetic algorithm), pemrograman genetika (genetic programming), strategi evolusi (evolution strategies), dan pemrograman evolusi (evolutionary programming). Tetapi, jenis evolutionary algorithm yang paling populer dan banyak digunakan adalah algoritma genetika (genetic algorithm).

        Algoritma genetika merupakan evolusi/ perkembangan dunia computer dalam bidang kecerdasan buatan (artificial intelligence). Sebenarnya kemunculan algoritma genetika ini terinspirasi oleh teori evolusi Darwin (walaupun pada kenyatanya teori tersebut terbukti keliru) dan teori-teori dalam ilmu biologi, sehingga banyak istilah dan konsep biologi yang digunakan. Karena itu sesuai dengan namanya, proses-proses yang terjadi dalam algoritma genetika samadengan apa yang terjadi pada evolusi biologi. Algoritma genetika merupakan teknik pencarian nilai optimum secara stochastic berdasarkan mekanisme seleksi alam. Algoritma genetika berbeda dengan teknik konvergensi konvensional yang lebih bersifat deterministik [7]. Metodenya sangat berbeda dengan kebanyakan algoritma optimasi lainnya, yaitu mempunyai ciri-cirinya sebagai berikut:

                 Algoritma genetika merupakan evolusi/ perkembangan dunia computer dalam bidang kecerdasan buatan (artificial intelligence). Sebenarnya kemunculan algoritma genetika ini terinspirasi oleh teori evolusi Darwin (walaupun pada kenyatanya teori tersebut terbukti keliru) dan teori-teori dalam ilmu biologi, sehingga banyak istilah dan konsep biologi yang digunakan. Karena itu sesuai dengan namanya, proses-proses yang terjadi dalam algoritma genetika sama dengan apa yang terjadi pada evolusi biologi. Algoritma genetika merupakan teknik pencarian nilai optimum secara stochastic berdasarkan mekanisme seleksi alam. Algoritma genetika berbeda dengan teknik konvergensi konvensional yang lebih bersifat deterministik.

        Metodenya sangat berbeda dengan kebanyakan algoritma optimasi lainnya, yaitu mempunyai ciri-cirinya sebagai berikut:

a. Menggunakan hasil pengkodean dari parameter, bukan parameter itu sendiri.

b. Bekerja pada populasi bukan pada sesuatu yang unik.

c. Menggunakan nilai satu-satunya pada fungsi dalam prosesnya.Tidak mengunakan

    fungsi luar atau pengetahuan luar lainnya.

d. Menggunakan fungsi transisi probabilitas, bukan sesuatu yang pasti.

Sejarah Singkat Algoritma Genetika

                 Awal sejarah perkembangan dari algoritma genetika (genetic algorithm) dimulai pada tahun 1960. Pada waktu itu, I. Rochenberg dalam bukunya yang berjudul “Evolution Strategies” mengemukakan tentang evolusi computer (computer evolutionary) yang kemudian dikembangkan oleh peneliti lain. Algoritma genetika sendiri pertama kali dikembangkan oleh John Holland pada tahun 1970-an di New York Amerika Serikat yang dikembangkan bersama mahasiswa dan rekan-rekannya. Hal tersebut bisa dibuktikan dengan adanya buku yang dibuat oleh Holland dengan judul “Adaptation in Natural and Artificial System” yang diterbitkan pada tahun 1975.

                 Lalu tujuh belas tahun kemudian, John Koza melakukan penelitian suatu program yang berkembang dengan menggunakan algoritma genetika. Program yang dikenal dengan sebutan metode “Genetic Programming” tersebut dibuat menggunakan LISP (bahasa pemrogramannya dapat dinyatakan dalam bentuk parse tree yaitu objek kerjanya pada algoritma genetika). Sampai sekarang algoritma genetika ini terus digunakan untuk memecahkan permasalahan yang sulit dipecahkan dengan menggunakan algoritma konvensional. 

Aplikasi Algortima Genetika

                 Sejak pertama kali dirintis oleh John Holland pada tahun 1960-an, algoritma genetika telah dipelajari, diteliti, dan diaplikasikan secara luas pada berbagai bidang. Algoritma genetika banyak digunakan pada masalah praktis yang berfokus pada pencarian parameter-parameter optimal. Hal ini membuat banyak orang mengira bahwa algoritma genetika hanya bisa digunakan untuk masalah optimasi. Pada kenyataannya, algoritma juga memiliki performansi yang bagus untuk masalah-masalah selain optimasi . Keuntungan penggunaan algoritma genetika sangat jelas terlihat dari kemudahan implementasi dan kemampuannya untuk menemukan solusi yang bagus (bisa diterima) secara cepat untuk masalah-masalah berdimensi tinggi. Algoritma genetika sangat berguna dan efisien untuk masalah-masalah dengan karakteristik sebagai berikut:

a.   Ruang masalah sangat besar, kompleks, dan sulit dipahami.

b.   Kurang atau bahkan tidak ada pengetahuan yang memadai untuk merepresentasikan          masalah ke dalam ruang pencarian yang lebih sempit.

c.   Tidak tersedianya analisis matematika yang memadai.

d.   Ketika metode-metode konvensional sudah tidak mampu meyelesaikan masalah yang         dihadapi.

e.   Solusi yang diharapkan tidak harus paling optimal, tetapi cukup bagus atau bisa diterima.

f.    Terdapat batasan waktu, misalnya real time system atau sistem waktu nyata.

Read more...

Jaringan Syaraf Tiruan / Artificial Neural Network (ANN)

     Artificial Neural Network (Jaringan Syaraf Tiruan/ANN) adalah sebuah bentuk perhitungan yang meniru bentuk jaringan syaraf padamakhluk hidup. Sama seperti pada jaringan  syaraf  asli,  jaringan  syaraf  tiruan  memiliki  neuron  untuk  memproses input/output.  Karena  itulah,  pada  sebagian  besar  kasus,  ANN merupakan  sistem  yang adaptif, karena struktur  sistemnya dapat berubah seiring dengan berubahnya informasi internal ataupun eksternal yang diproses pada saat  learning phase(tahap pembelajaran).  Pembuatan  sistem ANN dimaksudkan  agar  komputer  dapat  mengenali  suatu  pola, bentuk, atau struktur tertentu karena komputer tidak mempunyai intelegensia, meskipun 8 pada  kenyataannya,  sebuah  komputer  dapat  melakukan  operasi,  misalnya  mengenali wajah manusia, dalam waktu yang jauh lebih singkat daripada manusia.

Hecht-Nielsend (1988)  mendefinisikan  Suatu  neural  network (NN),  adalah  suatu  struktur  pemroses  informasi  yang terdistribusi dan bekerja secara paralel, yang terdiri atas elemen pemroses (yang memiliki  memori lokal  dan  beroperasi  dengan  informasi  lokal)  yang diinterkoneksi  bersama  dengan  alur  sinyal  searah  yang  disebut koneksi.  Setiap elemen pemroses memiliki koneksi keluaran tunggal yang bercabang (fan out) ke sejumlah  koneksi  kolateral  yang  diinginkan  (setiap  koneksi  membawa  sinyal yang  sama  dari  keluaran  elemen  pemroses  tersebut).  Keluaran dari elemen pemroses tersebut dapat merupakan sembarang jenis persamaan matematis yang diinginkan. Seluruh proses yang berlangsung pada setiap elemen pemroses harus benar-benar dilakukan secara lokal, yaitu keluaran hanya bergantung pada nilai masukan pada saat itu yang diperoleh melalui koneksi dan nilai yang tersimpan dalam memori lokal.

a)  Arsitektur Jaringan Syaraf Tiruan

1)   Jaringan syaraf dengan lapisan tunggal (single layer net).

          Jaringan dengan lapisan tunggal hanya memiliki satulapisan dengan bobot-bobot terhubung.  Jaringan  ini  hanya  menerima  input  kemudian  secara  langsung  akan mengolahnya  menjadi  output  tanpa  harus  melalui  lapisan  tersembunyi.  Dengan kata  lain,  ciri-ciri  dari  arsitektur  syaraf  dengan  lapisan  tunggal  adalah  hanya terdiri dari satu lapisan input dan satu lapisan output, tanpa lapisan tersembunyi.

2)   Jaringan syaraf dengan banyak lapisan (multi layer net).

        Jaringan dengan banyak lapisan memiliki satu atau lebih lapisan yang terletak di antara  lapisan  input  dan  lapisan  output  (memiliki  satu  atau  lebih  lapisan tersembunyi).  Umumnya,  ada  lapisan  bobot-bobot  yang terletak  di  antara  2 lapisan  yang  bersebelahan.  Jaringan  dengan  banyak  lapisan  ini  dapat menyelesaikan  permasalahan  yang  lebih  sulit  daripada  jaringan  dengan  lapisan tunggal, tentu saja dengan pembelajaran yang lebih rumit.

3)   Jaringan syaraf dengan lapisan kompetitif (competitive layer)

        Arsitektur  ini  memiliki  bentuk  berbeda  dari  kedua  arsitektur  lainnya,  di  mana antar  neuron  saling  dihubungkan.  Jaringan ini sering disebut feedback loop karena unit output ada yang memberikan informasi terhadap unit masukan.

b)  Algoritma pembelajaran

            Salah  satu  bagian  terpenting  dari  konsep  jaringan  syaraf  tiruan  adalah  proses pembelajaran.  Tujuan  utama  dari  proses  ini  adalah  melakukan  pengaturan terhadap bobot-bobot yang ada pada jaringan syaraf, hingga didapat bobot akhir yang tepat sesuai dengan  pola  data  yang  dilatih.  Selama proses pembelajaran, akan terjadi perbaikan bobot-bobot berdasarkan algoritma tertentu. Nilai bobot akan bertambah jika informasi yang diberikan ke neuron yang bersangkutan tersampaikan. Begitu pula sebaliknya, jika informasi  tidak  disampaikan  oleh  suatu  neuron  ke  neuron  yang  lain,  maka  nilai  bobot yang menghubungkan keduanya akan dikurangi. Pada saat pembelajaran dilakukan pada input yang berbeda, nilai bobot akan diubah secara dinamis hingga mencapai nilai yang cukup seimbang.  Apabila nilai ini telah tercapai, berarti tiap-tiap input telah berhubungan dengan output yang diharapkan. Pada  dasarnya  ada  dua  metode  pembelajaran,  yaitu  metode  pembelajaran  terawasi (supervised  learning)  dan  metode  pembelajaran  yang  tidak  terawasi  (unsupervised learning).

1)  Pembelajaran terawasi (supervised learning)

        Metode pembelajaran pada jaringan syaraf disebut terawasi jika output yang diharapkan telah diketahui sebelumnya. Misalkan jaringan syaraf akan digunakan untuk mengenali pasangan pola, misalkan pada sebuah operasi logika matematika AND. Pada proses pembelajaran, satu pola input akan diberikanke satu neuron pada lapisan input. Pola ini akan dirambatkan ke sepanjang jaringan syaraf hingga sampai ke neuron pada lapisan output. Lapisan output ini akan membangkitkan pola output yang nantinya akan dicocokkan dengan pola output targetnya. Apabila terjadi perbedaan antara pola output hasil pembelajaran dengan pola target, maka akan muncul error. Apabila nilai  errorini masih  cukup  besar,  berarti  perlu  dilakukan  lebih  banyak  pembelajaran  lagi.   Model-model pembelajaran yang menggunakan supervised learning di antaranya adalah Backpropagation, Bidirective Associative Memory (BAM), dan Hopfield.

  

2)  Pembelajaran tak terawasi (unsupervised learning)

        Metode pembelajaran yang tak terawasi tidak memerlukan target output.  Pada 19 metode  ini,  tidak  dapat  ditentukan  hasil  yang  seperti  apakah  yang  diharapkan  selama proses  pembelajaran.  Selama  proses  pembelajaran,  nilai  bobot  disusun  dalam  suatu range  tertentu  tergantung  pada  nilai  input  yang  diberikan.  Tujuan  pembelajaran  ini adalah  mengelompokkan  unit-unit  yang  hampir  sama  dalam  suatu  area  tertentu. Pembelajaran ini biasanya sangat cocok untuk pengelompokan (klasifikasi) pola. Model-model pembelajaran yang menggunakan unsupervised learning di antaranya adalah Adaptive Resonance Theory (ART) dan Competitive.

Beberapa contoh jaringan sederhana AND, OR, dan NOT

a)   Jaringan sederhana AND

Dari  tabel  diatas  terlihat  ada  dua  input  (X1  dan  X2)  dan  satu  output  (Y)  dengan bobot yang sesuai untuk w1 adalah 1 dan w2 adalah 1sehingga diperoleh nilai threshold yang sesuai dengan tabel adalah 2. Arsitektur jaringan sederhana untuk kasus AND sebagai berikut:

b)   Jaringan sederhana OR

Dari  tabel  diatas terdapat 2 input  (X1 dan X2) dan satu output (Y) dengan  bobot yang sesuai untuk w1 adalah 2 dan w2 adalah 2 sehingga X2 diperoleh  nilai threshold yang sesuai dengan table adalah 2. Arsitektur jaringan sederhana untuk kasus OR seperti berikut:

c)   Jaringan sederhana NOT

Dari tabel diatas terlihat ada satu input (X) dan satu output (Y) dengan bobot yang sesuai untuk w adalah -1 sehingga dapat diperoleh nilai threshold yang sesuai dengan tabel adalah 0.5. Arsitektur jaringan sederhananya sebagai berikut:

Read more...