tips dan trik algoritma genetika

Download Tips dan Trik Algoritma Genetika

Post on 27-Nov-2015

28 views

Category:

Documents

3 download

Embed Size (px)

DESCRIPTION

Cara mudah mengaplikasikan algoritma genetika untuk berbagai jenis permasalahan, seperti optimasi, searching, prediksi

TRANSCRIPT

  • Tip & Trik: Algoritma GenetikaTip & Trik: Algoritma Genetika

    Achmad BasukiPoliteknik Elektronika Negeri Surabaya

    PENS-ITS 2006

  • Computer Vision and Pattern Recognition Research GroupPENS ITS, Surabaya 2006

    Dibalik Model Adopsi Alamiah dalamAlgoritma Genetika

    Bagaimana membuat model adopsialamiah di dalam algoritma

    genetika untuk menyelesaikanbeberapa permasalahan

    searching, optimasi dan machine learning?

  • Computer Vision and Pattern Recognition Research GroupPENS ITS, Surabaya 2006

    Beberapa ImplementasiAlgoritma Genetika

    Nilai Maksimum Fungsi Dengan BanyakVariabel Bebas

    Optimasi Pada Unit Commitment Menentukan Model Antenna Array

    Optimal Time Series Forecasting

  • Computer Vision and Pattern Recognition Research GroupPENS ITS, Surabaya 2006

    Nilai Maksimum Fungsi DenganBanyak Variabel Bebas

    Nilai Maksimal Fungsi F(x1, x2, x3, , xn)Mendapatkan nilai maksimal fungsi F(x) dengan satu variabel bebas bisadigunakan cara grafik atau numerik, bagaimana bila harus mencari nilai maksimalfungsi dengan n buah variabel bebas (n>1).

    Contoh grafik dari fungsidengan 2 variabel bebasf(x,y)

  • Computer Vision and Pattern Recognition Research GroupPENS ITS, Surabaya 2006

    Model Adopsi AlamiahMenggunakan Kromosom Biner

    Definisi Individu: Bila ditentukan bahwasetiap variabel menggunakan M bit dan adaN buah variabel, maka jumlah gen dalamkromosom adalah MxN bit. Untuk itudiperlukan proses decoding(next) yang dapatmenterjemahkan nilai-nilai bit ini menjadinilai-nilai float.

    Definisi Fitness: Karena tujuannya adalahmencari nilai maksimal fungsiF(x1,x2,x3,,xn) maka nilai fitnessnyaadalah nilai fungsi itu sendiri.

  • Computer Vision and Pattern Recognition Research GroupPENS ITS, Surabaya 2006

    Fungsi Decoding N Variabel

    ( ) agenabx += 12)8:1(

    81

    function bilDecimal=decoding(bilBiner,aMin,aMax)nBaris=size(bilBiner,1);nKolom=size(bilBiner,2);for i=1:nBaris

    z=0;for j=1:nKolom

    z=z+bilBiner(i,j)*2^(nKolom-j);endbilDecimal(i)=(aMax-aMin)*z/(2^nKolom-1)+aMin;

    end

    function bilDecimal=decoding(bilBiner,aMin,aMax)nBaris=size(bilBiner,1);nKolom=size(bilBiner,2);for i=1:nBaris

    z=0;for j=1:nKolom

    z=z+bilBiner(i,j)*2^(nKolom-j);endbilDecimal(i)=(aMax-aMin)*z/(2^nKolom-1)+aMin;

    end

    1 1 0 1 0 0 1 0 0 1 0 1 1 1 0 0 Susunan 16 genx1 x2

    Batas: a xi b

    ( ) agenabx += 12)16:9(

    82

  • Computer Vision and Pattern Recognition Research GroupPENS ITS, Surabaya 2006

    Proses Algoritma GenetikaNilai Maksimum Fungsi F(x1,x2,..,xn)

    Pembangkitan populasi awal dapat dilakukandengan membangkitkan array biner 2 Dimensi dengan ukuran NpopNkrom(Npop=jumlah populasi, dan Nkrom=jumlahkromosom)

    Proses Seleksi menggunakan Roulette Wheel

    Proses Cross-Over menggunakan Cross Over Biner dengan probabilitas cross-over antara 80% sampai dengan 100%

    Proses Mutasi menggunakan mutasi binerdengan probabilitas 1% sampai dengan 20%

    Offspring dengan rank (elistism).

  • Computer Vision and Pattern Recognition Research GroupPENS ITS, Surabaya 2006

    Model Adopsi AlamiahMenggunakan Kromosom Float

    Definisi Individu: Karena yang dicariadalah nilai x1,x2,x3,,xn makakromosom dibentuk dari x1,2,x3,,xn

    Definisi Fitness: Karena tujuannyaadalah mencari nilai maksimal fungsiF(x1,x2,x3,,xn) maka nilai fitnessnyaadalah nilai fungsi itu sendiri.

  • Computer Vision and Pattern Recognition Research GroupPENS ITS, Surabaya 2006

    Proses Algoritma GenetikaNilai Maksimum Fungsi F(x1,x2,..,xn)

    Pembangkitan populasi awal dapat dilakukandengan membangkitkan array float 2 Dimensi dengan ukuran NpopNkrom, dimana Nkrom=jumlah variabel bebas

    Proses Seleksi menggunakan Roulette Wheel

    Proses Cross-Over menggunakan Cross Over Biner atau Aritmatik denganprobabilitas cross-over antara 80% sampaidengan 100%

    Proses Mutasi menggunakan mutasi geserdengan probabilitas 1% sampai dengan 20%

    Offspring dengan rank (elistism).

  • Computer Vision and Pattern Recognition Research GroupPENS ITS, Surabaya 2006

    Unit Commitment

    Permasalahan Unit Commitment SederhanaDaerah Jawa dan Bali mempunyai 148 pembangkit listrik mulai PLTU, PLTD, PLTG dan PLTA. Masing-masing pembangkit mempunyai kapasitas maksimum dayayang bisa dibangkitkan, biaya startup, biaya satuan pembangkitan daya per KWH dan biaya akibat losses. Untuk memenuhi permintaan daya listrik tertentu padawaktu tertentu dengan kondisi awal pembangkit sudah diketahui, pembangkit manasaj yang harus digunakan untuk memenuhi kebutuhan listrik dengan biaya minimal.

    No Jenis Kapasitas B. Start B. Satuan Losses

    1 PLTG 6000 400 0.15 0.2

    2 PLTD 1000 100 0.18 0.1

    3 PLTA 2000 250 0.10 0.3

    4 PLTU 5000 300 0.16 0.2

  • Computer Vision and Pattern Recognition Research GroupPENS ITS, Surabaya 2006

    Model Adopsi AlamiahMenggunakan Kromosom Float

    Definisi Individu: Permasalahan unit commitment ini bertujuanmencari pembangkit mana yang harus dipakai, dan berapadaya yang harus disediakan oleh pembangkit-pembangkittersebut dengan perubahan permintaan daya yang berubahsetiap periode sehingga individu dapat dinyatakan dalamkumpulan daya yang dibangkitkan oleh setiap pembangkit.

    Definisi Fitness: Nilai optimal adalah biaya minimal, dimanaperhitungan biaya dapat dilakukan dengan:

    Biaya = S(01) + B*(Pi++)S(01) : Biaya startup bila pembangkit asalnya off menjadi

    onB: Biaya satuan per-daya pembangkitanPi: jumlah daya yang dibangkitkan oleh pembangkit ke-I: prosentase daya cadangan yang harus disediakan: prosentase losses

  • Computer Vision and Pattern Recognition Research GroupPENS ITS, Surabaya 2006

    Proses Algoritma GenetikaUnit Commitment

    Inisialisasi keadaan awal sebelum proses yang berupa daya yang dibangkitkan setiap pembangkit(nilai 0 berarti pembangkit tidak aktif)

    Pembangkitan populasi awal dilakukan denganpembangkitan acak dengan memperhatikan keadaanawal dengan meminalkan pengaktifan pembangkityang sedang tidak aktif

    Seleksi dilakukan dengan roulette wheel. Proses Cross-Over menggunakan Cross Over

    Aritmatika dengan probabilitas cross-over sekitar80%-100%

    Proses Mutasi menggunakan Mutasi Random atauMutasi Geser dengan probabilitas sekitar 1%-20%

    Offspring dengan rank (elistism).

  • Computer Vision and Pattern Recognition Research GroupPENS ITS, Surabaya 2006

    Menentukan Model Antenna Array Optimal

    Jumlah elemen array (N) Jarak setiap elemen array (d) Frekwensi pakai (f) Setiap elemen array mempunyai nilai amplitudo daya (An) dan

    phase daya (Dn) yang disuplai.

    Elemen array

    dParameter di dalam model antenna array linier

    Permasalahan: Bagaimana mengatur amplitudo daya dan phase padasetiap elemen, agar hasil pola radiasi antenna dapat memiliki level side lobe yang kecil, sehingga pancaran pada main lobe menjadi lebih jauhdan luas.

  • Computer Vision and Pattern Recognition Research GroupPENS ITS, Surabaya 2006

    Pola Radiasi Antenna Array

    =

    +=N

    n

    Dfjndn

    nneAP1

    )(

    Elemen array

    dPola radiasi bila amplitudo dan phase daya (Ai,Di) pada setiap elemen sama, atau yang dinamakan dengan antenna array uniform adalah sebagai berikut (Pola radiasi akanberubah ketika Ai dan Di diganti dan tidak uniform.

    Level side lobe

  • Computer Vision and Pattern Recognition Research GroupPENS ITS, Surabaya 2006

    Model Adopsi AlamiahMenggunakan Kromosom Float

    Definisi Individu: Dengan asumsi yang diatur adalah amplitudo padasetiap elemen An dan phase dianggap nol maka kromosom berupa N gen float dengan nilai antara -1 sampai dengan 1.

    Definisi Fitness: Nilai optimal dari model antenna array linier ini adalahmodel yang dapat meminimalkan side lobe level. Level side lobe bisadiperoleh dari Max(P setelah P=0 pertama). Sehingga fitnessnyaadalah invers dari level side lobenya.

    Area Pencarian

    Level Side Lobe

  • Computer Vision and Pattern Recognition Research GroupPENS ITS, Surabaya 2006

    Proses Algoritma GenetikaModel Antenna Array Optimal

    Pembangkitan populasi awal dapat dilakukan denganmembangkitkan array float 2 Dimensi denganukuran NpopNkrom, dimana Nkrom=N (jumlahelemen)

    Proses Seleksi menggunakan Roulette Wheel Proses Cross-Over menggunakan Cross Over Biner

    atau Aritmatik dengan probabilitas cross-over antara 80% sampai dengan 100%

    Proses Mutasi menggunakan mutasi geser denganprobabilitas 1% sampai dengan 20%

    Offspring dengan rank (elistism).

    Optimasi dilakukan pada pengaturan amplitudo dan phase dianggap tetap.

  • Computer Vision and Pattern Recognition Research GroupPENS ITS, Surabaya 2006

    Time Series Forecasting

    Time series forecasting secara sederhana dapatdikatakan sebagai teknik peramalan data berdasarkan data-data pada periode sebelumnya.

    Time series forecasting dapat dirumuskan dengan:

    Keberhasilan peramalan di dalam time series forecasting sangat ditentukan oleh nilai ai danjumlah periode data yang digunakan (n). Algoritmagenetika dapat digunakan untuk mengoptimasi ai.

    01

    1 axaxn

    iiin +=

    =+

    xi adalah data pada periode ke iai adalah bobot pengaruh dari periode ke Iao adalah error perkiraan

  • Computer Vision and Pattern Recognition Research GroupPENS ITS, Surabaya 2006

    Model Adopsi AlamiahTime Series Forecasting

    Definisi Individu: Karena nilai ai (i=0,1,2,n) yang dicari untuk dapat menghasilkan nilai peramalanyang baik, maka kromosom dibentuk dari n+1 genfloat (-~ s/d +~)

    Definisi Fitness: Nilai optimal adalah nilai minimal hasil peramal