Kamis, 15 Mei 2014

Diposkan oleh ayie di 01.21 0 komentar
 Algoritma Genetika

   Algoritma Genetika adalah algoritma pencarian heuristik yang didasarkan atas mekanisme evolusi biologis.
Keberagaman pada evolusi biologis adalah variasi dari kromosom antar individu organisme. Variasi kromsom akan mempengaruhi lajur eproduksi dan tingkat kemampuan oraginisme untuk tetap hidup.
Ada4 kondisi yang sanga tmempengaruhi proses evolusi, yaitu:
1.  Kemampuan organisme untuk melakukan reproduksi
2.  Keberadaan populasi organisme yang bisa melakukan reproduksi
3.  Keberagaman organisme dalam suatu populasi
4.  Perbedaan kemampuan untuk survive

       Algoritma genetika pertamakali diperkenalkan olehJohn Holland dari Universitas Michigan (1975), Setiap masalah yang berbentuk adaptasi dapat diformulasikan dalam terminologi genetika.

Struktur Umum
•Populasi, istilah pada teknik pencarian yang dilakukan sekaligus atas sejumlah solusi yang mungkin
•Kromosom, individu yang terdapat dalam satu populasi dan merupakan suatu solusi yang masih berbentuk simbol.
•Generasi, populasi awal dibangun secara acak sedangkan populasi selanjutnya merupakan hasil evolusi kromosom-kromosom melalui iterasi.

•FungsiFitness, alat ukur yang digunakan untuk proses evaluasi kromosom. Nilai fitness dari suatu kromosom akan menunjukkan kualitas kromosom dalam populasi tersebut.
•Generasi berikutnya dikena ldengan anak(offspring) terbentuk dari gabungan2 kromosom generasi sekarang yang bertindak sebagai induk(parent) dengan menggunakan operator penyilang (crossover).
•Mutasi, operator untuk memodi-fikasi kromosom.


Komponen Utama
•Ada 6 komponen utama algoritma genetika:
1.Teknik Penyandian
-Teknik penyandian meliputi penyandian gen dari kromosom
-Gen merupakan bagian dari kromosom, satu gen biasanya akan mewakili satu variabel
-Gen dapat direpresentasikan dalam bentuk: string bit, pohon, array bilangan real, daftar aturan, elemen permutasi, elemen program dan lain-lain.

−Kromosom dapat direpresentasikan dengan menggunakan:
•String bit: 10011, 11101
•Bilangan Real: 65.65, 562.88
•Elemen Permutasi: E2, E10
•Daftar Aturan: R1, R2, R3
•Elemen Program : pemrograman genetika
•Struktu rlainnya


2.ProsedurInisialisasi
-Ukuran populasi tergantung pada masalah yang akan dipecahkan dan jenis operator genetika yang akan diimplementasikan.

−Setelah ukuran populasi ditentukan, kemudian harus dilakukan inisialisasi terhadap kromosom yang terdapat pada populasi tersebut
−Inisialisasi kromosom dilakukan secara acak, namun demikian harus tetap memperhatikan domain solusi dan kendala permasalahan yang ada
3.Fungsi Evaluasi
Ada2 hal yang harus dilakukan dalam melakukan evaluasi kromosom yaitu: evaluasi fungsi objektif dan konversi fungsi objektif kedalam fungsi fitness

4.Seleksi
-Bertujuan untuk memberikan kesempatan reproduksi yang lebih besar bagi anggota populasi yang paling fit
-Ada beberapa metode seleksi dari induk, antara lain :
•Rank-based fitness assigment
•Roulette wheel selection
•Stochastic universal sampling
•Local selection
•Truncation selection
•Tournament selection

5.Operator Genetika
Ada 2 operator genetika:
a.Operator untuk melakukan rekombinasi, yang terdiri dari:

-Rekombinasi bernilai real
1. Rekombinasi diskrit
2. Rekombinasi intermediate
3. Rekombinasi garis
4. Rekombinasi garisyang diperluas

-Rekombinasi bernilai biner(Crossover)
1. Crossover satu titik
2. Crossover banyak titik
3. Crossover seragam

-Crossover dengan permutasi 
b.Mutasi
-Mutasi bernilai real
-Mutasi bernilai biner
6.Penetuan Parameter 

-Parameter adalah parameter kontrol algoritma genetika, yaitu: ukuran populasi(popsize), peluang crossover (pc) dan peluang mutasi(pm).
-Rekomendasi menentukan nilai parameter :
-Untuk permasalahan yang memiliki kawasan solusi cukup besar, De Jong merekomendasikan nilai parameter :
(popsize; pc; pm) = (50;0,6;0,001)

-Bilarata-rata fitness setiap generasi digunakan sebagai indikator, maka Grefenstette merekomendasikan:
(popsize; pc; pm) =(30;0,95;0,01)

-Bila fitness dari individu terbaik dipantau pada setiap generasi, maka usulannya adalah:
(popsize; pc; pm) = (80;0,45;0,01)

-Ukuran populasi sebaiknya tidak lebih kecil dari30, untuk sembarang jenis permasalahan

Seleksi
•Seleksi akan menentukan individu-individu mana saja yang akan dipilih untuk dilakukan rekombinasi dan bagaimana off-spring terbentuk dari individu-individu terpilih tersebut.
•Langkah pertama: pencarian nilai fitness
•Langkah kedua: Nilai fitness yang diperolah digunakan pada tahap-tahap seleksi selanjutnya

•Ada beberapa definisi yang bias digunakan untuk melakukan perbandingan terhadap beberapa metode yang akan digunakan, antara lain :
-Selective Pressure : probabilitas darii ndividu terbaik yang akan diseleksi dibandingkan dengan rata-rata probabilitas dari semua individu yang diseleksi.
-Bias : perbedaan absolut antara fitness ternormalisasi dari suatu individu dan probabilitas reproduksi yang diharapkan.
-Spread : range nilai kemungkinan untuksejumlah off-spring dari suatu individu
-Loss of diversity: proposi dari individu-individu dalam suatu populasi yang tidak terseleksi selama fase seleksi.
-Selection intensity : nilai fitness rata-rata yang diharapkan dalam suatu populasi setelah dilakukan seleksi (menggunakan distribusi Gauss ternormalisasi).
-Selection variance : variansi yang diharapkan dari distribus ifitness dalam populasi setelah dilakukan seleksi (menggunakan distribus iGauss ternormalisasi).
1.Rank-based Fitness
•Populasi diurutkan menurut nilai objektifnya. Nilai fitness dari tiap-tiap individu hanya tergantung pada posisi individu tersebut dalam urutan, dan tidak dipengaruhi oleh nilai objektifnya.
2.Roulette Wheel Selection
•Istilah lain adalah stochastic sampling with repalcement.
•Individu-individu dipetakan dalam suatu segmen garis secara berurutan sedemikian hingga tiap-tiap segmen individu memiliki ukuran yang sama dengan ukuran fitnessnya
•Sebuah bilangan random di-bangkitkan dan individu yang memiliki segmen dalam kawasan segmen dalam kawasan bilangan random tersebut akan terseleksi. Proses ini berulang hingga didapatkan sejumlah individu yang diharapkan.

3.Stocastic Universal Sampling
•Memiliki nilai bias nol dan penyebaran yang minimum
•Individu-individu dipetakan dalam suatu segmen garis secara berurut sedemikian hingga tiap-tiap segmen individu memiliki ukuran yang sama dengan ukuran fitnessnya seperti halnya pada seleksi rodaroulette. Kemudian diberikan sejumlah pointer sebanyak individu yang ingin diseleksi pada garis tersebut.
•Andaikan N adalah jumlah individu yang akan diseleksi, maka jarak antar pointer adalah1/N, dan posisi pointer pertama diberikan secara acak pada range [1, 1/N]

4.Seleksi Lokal
•Setiap individu yang berada didalam konstrain tertentu disebut dengan nama lingkungan lokal. Interaksi antar individu hanya dilakukan didalam wilayah tersebut. Lingkungan tersebut ditetapkan sebagai struktur dimana populasi tersebut terdistribusi. Lingkungan tersebut juga dapat dipandang sebagai kelompok pasangan-pasangan yang potensial.
•Langkah pertama adalah menyeleksi separuh pertama dari populasi yang berpasangan secara random. Kemudian lingkungan baru tersebut diberikan pada setiap individu yang terseleksi.

•Struktur lingkungan pada seleksi lokal dapat berbentuk:
*Linear : full ring dan half ring
*Dimensi -2:
     -full cross dan half cross
     -full star dan half star

*Dimensi-3 dan struktur yang lebih kompleks yang merupakan kombinasi dari kedua struktur diatas
•Jarak antara individu dengan struktur tersebut akan sangat menentukan ukuran lingkungan. Individu yang terdapat dalam lingkungan dengan ukuran yang lebih kecil, akan lebih terisolasi dibandingkan dengan individu yang terletak pada lingkungan dengan ukuran yang lebih besar.

5.Truncation Selection
•Seleksinya adalah buatan
•Digunakan oleh populasi yang jumlahnya sangat besar
•Individu-individu diurutkan berdasarkan nilai fitnessnya. Hanya individu yang terbaik saja yang akan diseleksi sebagai induk.
•Parameter yang digunakan adalah suatu nilai ambang trunc yang mengindikasikan ukuran populasi yang akan diseleksi sebagai induk yang berkisar antara50% -10%.
•Individu-individu yang ada dibawah nilai ambang ini tidak akan menghasilkan keturunan

6.Tournament Selection
•Ditetapkan suatu nilai tour untuk individu-individu yang dipilih secara random dari suatu populasi.
•Individu-individu yang terbaik dalam kelompok ini akan diseleksi sebagai induk
•Parameter yang digunakan adalah ukuran tour yang bernilai antara2 sampai N (jumlah individu dalam populasi)

Rekombinasi
1.Rekombinasi Diskret
•Menukar nilai variabel antar kromosom induk.
•Misal ada2 individu dengan3 variabel, yaitu:
induk1 :  12    25    5
induk2 :  123  4      34
•Untuk tiap-tiap variabel induk yang menyumbangkan variabelnya keanak yang dipilih secara random dengan probabilitas yang sama.
sample 1 :  2   2   1
sample 2 :  1   2   1

Setelah rekombinasi, kromosom-kromosom baru yang terbentuk:
anak1 :    123   4     5
anak2 :    1       4     5
•Rekombinasi dapat digunakan untuk sembarang variabel (biner, real, atau simbol)
2.Rekombinasi Menengah
•Metode rekombinasi yang hanya dapat digunakan untuk varibel real
•Nilai variebel anak dipilih disekitar dan antara nilai-nilai variabel induk

•Anak dihasilkan menurut aturan sebagai berikut:
anak= induk1 + alpha (induk2 –induk1)
dengan alpha adalah faktor skala yang dipilih secara random pada interval [-d, 1+d], biasanyad=0,25.
•Tiap-tiap variabel pada anak merupakan hasil kombinasi variabel-variabel menuru taturan diatas dengan nilai alpha dipilih ulang untuk tiap variabel.

3.Rekombinasi Garis
•Hampir sama dengan rekombinasi menengah, hanya saja nilai alpha untuk semua variabel sama.
•Misalkan ada2 kromosom dengan 3 variabel:
induk1 :   12     25    5
induk2 :   123   4      34
•Untuk tiap-tiap variabel induk yang menyumbangkan vaiabelnya keanak dipilih secara random dengan  probabilitas yang sama.
sample 1 :   0,5
sample 2 :   0,1
•Setelah rekombinasi kromosom-kromosom baru yang terbentuk
anak1:    67,5     14,5     19,5
anak2:    23,1     22,9     7,9

4.Penyilangan satu titik
•Posisi penyilangan k (k=1,2,…,N-1) denganN = panjang kromosom diseleksi secara random.
•Variabel-variabel ditukar antar kromosom pada titik tersebut untuk menghasilkan anak
•Misalkan ada 2 kromosom dengan panjang12 :
induk 1 : 0 1 1 1 0 | 0 1 0 1 1 1 0
induk 2 : 1 1 0 1 0 | 0 0 0 1 1 0 1
•Posisi menyilang yang terpilih: misalkan5
•Setelah penyilangan, diperoleh kromosom-kromosom baru:
anak 1 : 0 1 1 1 0 | 0 0 0 1 1 0 1
anak 2 : 1 1 0 1 0 | 0 1 0 1 1 1 0

5.Penyilangan banya ktitik
•Pada penyilangan ini, m posisi penyilangan ki(k=1,2,…,N-1,i=1,2,…,m) dengan N = panjang kromosom diseleksi secara random dan tidak diperbolehkan ada posisi yang sama, serta diurutkan naik.
•Variabel-variabel ditukar antar kromosom pada titik tersebut untuk menghasilkan anak.

6.Penyilangan Seragam
•Setiap lokasi memiliki potensi sebagai tempat penyilangan.
•Sebuah mask penyilangan dibuat sepanjang panjang kromosom secara random yang menunjukan bit-bit dalam mask yang mana induk akan mensupply anak dengan bit-bit yang ada.
•Induk yang mana yang akan menyumbangkan bit keanak yang dipilih secara random dengan probabilitas yang sama.

7.Penyilangan dengan permutasi
•Dengan permutasi, kromosom-kromosom anak diperoleh dengan cara memilih sub-barisan sautu tour dari satui nduk dengan tetap menjaga urutan dan posisi sejumlah kotayang mungkin terhadap induk yang lainnya.


Mutasi
•Mutasi Bilanga nReal

-Operator mutasi untuk bilangan real dapa tditetapkan sebagai:
1. Variabel yang dimutasi= variabel±range * delta;
2. Range = 0,5 * domain variabel
3. Delta = Σ(ai* 2-i); ai= 1 dengan probabilitas1/m, selain ituai= 0, denganm = 20

•Mutasi Biner
-Langkah-langkah mutasi:
1.Hitung jumlah gen pada populasi
2.Pilih secara acak gen yang akan dimutasi
3.Tentukan kromosom dari gen yang terpilih untuk dimutasi
4.Ganti nilai gen (0 ke1 atau1 ke0) dari kromosom yang akan dimutasi tersebut

Algoritma Genetika Sederhana
•Langkah-langkah:
1.Generasi= 0
2.Inisialisasi populasi awal, P (generasi), secara acak
3.Evaluas inilai fitness pada setiap individu dalamP (generasi)
4.Kerjakan langkah-langkah berikut hingga generasi mencapai maksimum generasi:


a. generasi= generasi+1
b. Seleksi populasi tersebut untuk mendapatkan kandidat induk, P’(generasi)
c. Lakukan crossover pada P’(generasi)
d. Lakukan mutasi padaP’(generasi)
e. Lakukan evaluasi fitness setiap individu pada P’(generasi
f. Bentuk populasi baru: P(generasi) = {P(generasi-1) yang survive, P’(generasi)

•Metode seleksi rodaroulette
Algoritma seleksi rodaroulette:
1. Hitung total fitness (F)
2. Hitung fitness relatif tiap individu
3. Hitung fitness komulatif
4. Pilih induk yang akan menjadi kandidat untuk dicrossover
•Crossover
Metode yang sering digunakan adalah penyilangan satutitik
•Mutasi
Mutasiyang digunakan adalah mengubah secara acak nilai suatu bit pada posisi tertentu.


 

Kamis, 12 Juli 2012

Tugas Tim

Diposkan oleh ayie di 20.48 0 komentar
Nama : Sri Mulyani
NPM  : 1057201000847
download link Disini

Senin, 11 Juni 2012

Apa itu Interface...?

Diposkan oleh ayie di 04.44 0 komentar
Interface adalah jenis khusus dari blok yang hanya berisi method signature(atau constant
). Interface mendefinisikan sebuah(signature) dari sebuah kumpulan method tanpa tubuh.

Interface mendefinisikan sebuah cara standar dan umum dalam menetapkan sifat-sifat dari
class-class. Mereka menyediakan class-class, tanpa memperhatikan lokasinya dalam hirarki class, untuk mengimplementasikan sifat-sifat yang umum.

Dengan catatan bahwa interface-interface juga menunjukkan polimorfisme, dikarenakan program dapat memanggil method interface dan versi yang tepat dari method yang akan dieksekusi tergantung dari tipe object yang melewati pemanggil method interface.


Kenapa Kita Memakai Interface..?

Kita akan menggunakan interface jika kita ingin class yang tidak berhubungan mengimplementasikan method yang sama. Melalui interface-interface, kita dapat menangkap kemiripan diantara class yang tidak berhubungan tanpa membuatnya seolah - olah class yang berhubungan.

Sabtu, 12 Mei 2012

Apa itu Pemrograman Berorientasi Objek ?

Diposkan oleh ayie di 02.56 0 komentar
Pemrograman berorientasi objek (Inggris: object-oriented programming disingkat OOP) merupakan paradigma pemrograman yang berorientasikan kepada objek. Semua data dan fungsi di dalam paradigma ini dibungkus dalam kelas-kelas atau objek-objek. Bandingkan dengan logika pemrograman terstruktur. Setiap objek dapat menerima pesan, memproses data, dan mengirim pesan ke objek lainnya,
Model data berorientasi objek dikatakan dapat memberi fleksibilitas yang lebih, kemudahan mengubah program, dan digunakan luas dalam teknik piranti lunak skala besar. Lebih jauh lagi, pendukung OOP mengklaim bahwa OOP lebih mudah dipelajari bagi pemula dibanding dengan pendekatan sebelumnya, dan pendekatan OOP lebih mudah dikembangkan dan dirawat.
== Konsep dasar dari Pemrograman Berorientasi Objek Pemrograman orientasi-objek menekankan konsep berikut:

- Kelas — kumpulan atas definisi data dan fungsi-fungsi dalam suatu unit untuk suatu tujuan tertentu. Sebagai contoh 'class of dog' adalah suatu unit yang terdiri atas definisi-definisi data dan fungsi-fungsi yang menunjuk pada berbagai macam perilaku/turunan dari anjing. Sebuah class adalah dasar dari modularitas dan struktur dalam pemrograman berorientasi object. Sebuah class secara tipikal sebaiknya dapat dikenali oleh seorang non-programmer sekalipun terkait dengan domain permasalahan yang ada, dan kode yang terdapat dalam sebuah class sebaiknya (relatif) bersifat mandiri dan independen (sebagaimana kode tersebut digunakan jika tidak menggunakan OOP). Dengan modularitas, struktur dari sebuah program akan terkait dengan aspek-aspek dalam masalah yang akan diselesaikan melalui program tersebut. Cara seperti ini akan menyederhanakan pemetaan dari masalah ke sebuah program ataupun sebaliknya.

- Objek - membungkus data dan fungsi bersama menjadi suatu unit dalam sebuah program komputer; objek merupakan dasar dari modularitas dan struktur dalam sebuah program komputer berorientasi objek.

- Abstraksi - Kemampuan sebuah program untuk melewati aspek informasi yang diproses olehnya, yaitu kemampuan untuk memfokus pada inti. Setiap objek dalam sistem melayani sebagai model dari "pelaku" abstrak yang dapat melakukan kerja, laporan dan perubahan keadaannya, dan berkomunikasi dengan objek lainnya dalam sistem, tanpa mengungkapkan bagaimana kelebihan ini diterapkan. Proses, fungsi atau metode dapat juga dibuat abstrak, dan beberapa teknik digunakan untuk mengembangkan sebuah pengabstrakan.

-Enkapsulasi - Memastikan pengguna sebuah objek tidak dapat mengganti keadaan dalam dari sebuah objek dengan cara yang tidak layak; hanya metode dalam objek tersebut yang diberi izin untuk mengakses keadaannya. Setiap objek mengakses interface yang menyebutkan bagaimana objek lainnya dapat berinteraksi dengannya. Objek lainnya tidak akan mengetahui dan tergantung kepada representasi dalam objek tersebut.

- Polimorfisme melalui pengiriman pesan. Tidak bergantung kepada pemanggilan subrutin, bahasa orientasi objek dapat mengirim pesan; metode tertentu yang berhubungan dengan sebuah pengiriman pesan tergantung kepada objek tertentu di mana pesa tersebut dikirim. Contohnya, bila sebuah burung menerima pesan "gerak cepat", dia akan menggerakan sayapnya dan terbang. Bila seekor singa menerima pesan yang sama, dia akan menggerakkan kakinya dan berlari. Keduanya menjawab sebuah pesan yang sama, namun yang sesuai dengan kemampuan hewan tersebut. Ini disebut polimorfisme karena sebuah variabel tungal dalam program dapat memegang berbagai jenis objek yang berbeda selagi program berjalan, dan teks program yang sama dapat memanggil beberapa metode yang berbeda di saat yang berbeda dalam pemanggilan yang sama. Hal ini berlawanan dengan bahasa fungsional yang mencapai polimorfisme melalui penggunaan fungsi kelas-pertama.

- Dengan menggunakan OOP maka dalam melakukan pemecahan suatu masalah kita tidak melihat bagaimana cara menyelesaikan suatu masalah tersebut (terstruktur) tetapi objek-objek apa yang dapat melakukan pemecahan masalah tersebut. Sebagai contoh anggap kita memiliki sebuah departemen yang memiliki manager, sekretaris, petugas administrasi data dan lainnya. Misal manager tersebut ingin memperoleh data dari bag administrasi maka manager tersebut tidak harus mengambilnya langsung tetapi dapat menyuruh petugas bag administrasi untuk mengambilnya. Pada kasus tersebut seorang manager tidak harus mengetahui bagaimana cara mengambil data tersebut tetapi manager bisa mendapatkan data tersebut melalui objek petugas adminiistrasi. Jadi untuk menyelesaikan suatu masalah dengan kolaborasi antar objek-objek yang ada karena setiap objek memiliki deskripsi tugasnya sendiri. 

                                                                                                                               Sumber : Wikipedia


 

Algoritma Genetika Copyright © 2010 Design by Ipietoon Blogger Template Graphic from Enakei | web hosting