Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Algoritma Genetika

No description
by

Ferry Sandi Cristian

on 9 June 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Algoritma Genetika

Algoritma genetika adalah algoritma komputasi yang diinspirasi teori evolusi yang kemudian diadopsi menjadi algoritma komputasi untuk mencari solusi suatu permasalahan dengan cara yang lebih “alamiah” yaitu siapa yang kuat dia yang bertahan. Salah satu aplikasi algoritma genetika adalah pada permasalahan optimasi kombinasi, yaitu mendapatkan suatu nilai solusi optimal terhadap suatu permasalahan yang mempunyai banyak kemungkinan solusi. Dalam tulisan ini akan dibahas teori dasar algoritma genetika.
Pengertian Algoritma Genetika
Algoritma Genetika
Genotype(Gen)
:Sebuah nilai yang menyatakan satuan dasar yang membentuk suatu arti tertentu dalam satu kesatuan gen yang dinamakan kromosom. dalam algoritma genetika, gen ini bisa berupa nilai biner, float, integer maupun karakter, atau kombinatorial.
Allele
:nilai dari gen.
Kromosom
:Gabungan gen-gen yang membentuk nilai tertentu.
Individu
:menyatakan satu nilai atau keadaan yang menyatakan salah satu solusi yang mungkin dari permasalahan yang diangkat.
populasi
:merupakan sekumpulan individu yang akan diproses bersama dalam satu siklus proses evolusi.
Generasi
:menyatakan satu siklus proses evolusi atau ssatu iterasi di dalam algoritma genetika.

Pendefinisian Individu
Nilai Fitness adalah nilai yang menyatakan baik tidaknya suatu individu(Solusi). Nilai fitness ini yang dijadikan acuan dalam mencapai nilai optimal dalam algoritma genetika. Algoritma genetika bertujuan mencari individu dengan nilai fitness yang paling tinggi. nilai fitness yang tinggi berarti solusi yang terbaik.
Nilai Fitness
adalah proses membangkitkan sejumlah individu secara acak atau melalui prosedur tertentu. ukuran untuk populasi tergantung pada masalah yang akan diselesaikan dan jenis operator genetika yang akan di implementasikan. setelah ukuran populasi ditentukan, baru kemudian dilakukan pembangkitan populasi awal. dimana syarat-syarat yang harus dipenuhi untuk menunjukan suatu solusi harus benar-benar diperhatikan dalam pembangkitan setiap individunya.
1.Membangkitkan populasi awal
Algoritma Genetika di temukan oleh John Holland
Illustrasi Representasi Penyelesaian Permasalahan dalam Algoritma Genetika
Evaluasi Fitness
Seleksi Individu
Reproduksi Crossover dan Mutasi Gen
Populasi Baru
Populasi Awal
Siklus Algoritma Genetika
inti dari cara ini adalah melibatkan pembangkitan bilangan random untuk nilai setiap gen sesuai dengan representasi kromosom yang digunakan.


1.1.Random Generator
Cara ini adalah dengan memasukan nilai tertentu ke dalam gen dari populasi awal yang dibentuk.
1.2.Pendekatan Tertentu
Salah satu cara permutasi gen dalam pembangkitan populasi awal adalah penggunaan Josephus dalam permasalahan kombinatorial seperti TSP. Misalkan ada kota dari 1 sampai 9. permutasi titik awal adalah 6 dan selang adalah 5. Maka lintasan berangkat dari kota 6, selang 5 kota dari kota 6 adalah kota 2 (dengan asumsi kota 1-9 membentuk circular list). kota 2 dihapus dari list. selang 5 kemudian adalah kota 7. proses ini di ulang hingga ada satu lintasan dalam list. Hasil permutasi ini adalah 2-7-3-8-4-9-5-1-6
1.3.Permutasi Gen
Adapun beberapa komponen utama Algoritma Genetika
ada 5, antara lain:
2.Teknik Pengkodean
Teknik pengkodean adalah bagaimana mengkodekan gen dari kromosom, dimana gen merupakan bagian dari kromosom. satu gen biasanya akan mewakili satu variable, dimana gen dapat di presentasikan dalam bentuk : bit, bilangan real, daftar aturan, elemen permutasi atau representasi lainnya yang dapat di implementasikan untuk operator genetika.
Seleksi digunakan untuk memilih individu-individu mana saja yang akan dipilih untuk proses kawin silang dan mutasi. Seleksi ini yang di gunakan untuk mendapatkan induk yang baik. "induk yang baik akan menghasilkan keturunan yang baik". semakin tinggi nilai fitness suatu individu semakin besar kemungkinannya untuk terpilih.
3.Seleksi
3.1. Metode Seleksi Mesin Roulette
Metode seleksi dengan mesin roulette ini merupakan metode yang paling sederhana dan sering dikenal dengan nama stochastic sampling with replacement. Cara kerjanya sebagai berikut:
1.Di hitung nilai fitness masing-masing individu(f1, dimana i adalah individu ke-1 s/d ke-n).
2.Di hitung total fitness semua individu.
3.Dihitung probabilitas masing-masing individu.
4.Dari probabilitas tersebut, dihitung jatah masing-masing individu pada angka 1-100
5.Dibangkitkan bilangan random antara 1-100
6.Dari bilangan random yang dihasilkan, ditentukan individu mana yang terpilih dalam proses seleksi
3.2.Seleksi dengan Turnamen
Pada metode seleksi dengan turname, 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
4.Pindah Silang(Crossover)
kawin silang (Crossover) adalah operator dari algoritma genetika yang melibatkan dua induk untuk membentuk kromosom baru.prinsip pindah silang ini adalah melakukan operasi(pertukaran,aritmatika) pada gen-gen yang bersesuaian dari dua induk untuk menghasilkan individu baru.
5.Mutasi
Mutasi gen berperan untuk menggantikan gen yang hilang dari populasi akibat proses seleksi yang memungkinkan munculnya kembali gen yang tidak muncul pada inisialisasi populasi.

kromosom anak dimutasi dengan menambahkan nilai random yang sangat kecil, dengan probabilitas yang rendah.
Diagram Alur Mutasi
Individu
Individu dilambangkan oleh sebuah nilai fitness yang nantinya akan digunakan untuk mencari solusi terbaik.

pertahanan yang tinggi dari individu memberikan kesempatan untuk melakukan reproduksi melalui perkawinan silang dengan individu yang lain dalam populasi tersebut. populasi baru yang di hasilkan dinamakan keturunan, yang nantinya membawa beberapa sifat dari induknya. sedangkan populasi yang tidak terseleksi dalam reproduksi akan mati dengan sendirinya. dengan cara ini beberapa generasi dengan karakteristik yang bagus akan bermunculan dalam populasi tersebut. Untuk melakukan hal di atas ada beberapa operasi yang harus dilakukan, antara lain:
Operasi Evolusi yang melibatkan proses Seleksi
Operasi Genetik yang melibatkan proses kawin silang dan mutasi
Ada beberapa hal yang harus dilakukan dalam algoritma genetika, antara lain:


1.Mendefinisikan individu, dimana individu menyatakan salah satu solusi yang mungkin dari permasalahan yang diangkat.
2.Mendefinisikan nilai fitness, yang merupakan ukuran baik-tidaknya sebuah individu/solusi yang di dapat.
3.Menentukan proses pembangkitan populasi awal.
4.Menentukan proses seleksi yang akan digunakan.
5.Menentukan proses perkawinan silang dan mutasi gen yang akan di gunakan.
Full transcript