Algoritma Genetika adalah algoritma yang memanfaatkan proses seleksi alamiah yang dikenal dengan proses evolusi. Dalam proses evolusi, individu secara terus-menerus mengalami perubahan gen untuk menyesuaikan dengan lingkungan hidupnya. “Hanya individu-individu yang kuat yang mampubertahan”. Proses seleksi alamiah ini melibatkan perubahan gen yang terjadi pada individu melaluiproses perkembang- biakan. Algoritma genetika berbeda dengan teknik pencarian yang lain, karena pada algoritma genetika ini langkah pertama dimulai dengan membangkitkan secara random solusi-solusi yang sering dikenal dengan initial population.
Setiap individu didalam populasi dinamakan chromosome, dimana setiap chromosome itu mewakili sebuah solusi untuk masalah yang akan dihadapi. Sebuah chromosome biasanya simbolnya string hal ini diperuntukkan bagi bilangan biner dan untuk floating point yang dipakai adalah bilangan real. Untuk masalah tiga variable maka chromosome akan tersusun atas tiga gen demikian pula kalau permasalahannya melibatkan lima variabel, maka didalam satu chromosome juga akan terdapat lima gen. Chromosome terbentuk setiap generasi dan kemudian dievaluasi menggunakan beberapa ukuran fitness.
Untuk generasi yang baru, chromosome baru terbentuk oleh proses yang dinamakan proses seleksi. Setelah proses seleksi itu berlangsung chromosome yang baru terbentuk itu akan mengalami proses reproduksi dimana didalam proses reproduksi ini chromosome tadi akan diproses dalam dua tahap yaitu crossover dan mutasi. Kadua tahap proses itu akan membuat offspring. Untuk proses crossover , offspring yang terbentuk merupakan penggabungan dari chromosome yang sebelumnya, sedangkan untuk mutasi off spring yang terbentuk merupakan hasil perubahan mutasi dari gen atau mutasi pada bit.
Generasi baru terbentuk oleh seleksi menurut nilai fitness dari keseluruhan chromosome, beberapa parent dan offspring dipilih agar menjaga ukuran populasi tetap. Chromosome yang memiliki nilai fitness yang besar memiliki peluang yang lebih besar untuk terpilih. Setelah beberapa generasi, Algoritma Genetika ini akan mengumpulkan chromosome terbaik,yang membantu untuk mewakili solusi yang optimal untuk masalah itu'
Srtuktur umum pada algoritma genetika mempunyai proses yang berawal dari inisialisasi populasi , evaluasi, seleksi, crossover, mutasi .
Komponen – Komponen Utama:
- Populasi awal adalah proses membangkitkan sejumlah individu secara acak atau melalui prosedur tertentu. Syarat-syarat yang harus dipenuhi untuk menunjukkan suatu solusi harus benar-benar diperhatikan dalam pembangkitan setiap individunya.
- Fitness bertujuan untuk menentukan kelayakan tiap kromosom dalam populasi,sesuai atau tidaknya dengan keadaan yang diharapkan. Contoh fitness, untuk alasan sanitasi, maka dapur tidak boleh bersebelahan dengan kamar mandi, garasi selalu berada disebelah kanan atau kiri rumah, dan lain sebagainya.
- Seleksi individu menyatakan salah satu solusi (penyelesaian) yang mungkin dari permasalahan yang diangkat.
- - Crosss-over adalah proses mengkombinasikan dua individu untuk memperoleh individu-individu baru yang diharapkan mempunyai fitnesslebih baik.
- - Mutasi proses yang bertujuan untuk mengubah salah satu atau lebih bagian dari chromosome
- Populasi baru, dibangkitkan dengan cara membangkitkan semua huruf dalam sejumlah kata (individu) yang dibangkitkan.
Seleksi
Seleksi adalah proses pemilihan calon induk, dalam proses seleksi ini terdapat beberapa metode yang bisa digunakan antara lain: Mesin Roulette (Roulette Wheel), Competition dan Tournament. Dalam contoh ini digunakan Mesin Roullete yang memang metode paling dasar dan model acaknya uniform.
Tiga dasar pokok yang tergabung didalam fase seleksi dalam metode Algoritma
Genetika yaitu:
- Sampling space
- Sampling mechanism
- Selection probability
Sampling Space
Prosedur seleksi yang menghasilkan populasi baru untuk generasi selanjutnya berdasarkan pada baik semua parent atau offspring atau bagian dari mereka.Inilah yang memimpin masalah dari sampling space. Sebuah sampling space dikarakteristikkan oleh dua factor yaitu size (ukuran) dan ingredient (bahan) yang menunjuk pada parent dan offspring. Pop_size menunjuk pada ukuran dari populasi dan off_size menunjuk pada ukuran dari off spring yang dihasilkan pada setiap generasi. Regular sampling space memiliki ukuran dari pop_size dan berisi semua offspring dengan sebagian dari parent. Enlarge sampling space memiliki ukuran dari pop_size+off_size dan berisi semua parent dan offspring.
SamplingMechanim
Sampling mechanism memperhatikan masalah bagaimana memilih chromosome dari Sampling space. Tiga dasar pendekatan yang telah digunakan pada sampling chromosome:
- Stochastic sampling
- Deterministic sampling
- Mixed sampling
a. Stochastic sampling
Ciri-ciri umum pada metode ini yaitu fase seleksi menentukan jumlah dari penggandaan yang akan diterima setiap chromosome berdasarkan pada probabilitas survival. Fase seleksi disusun dari dua bagian:
- Menentukan nilai chromosome yang diharapkan
- Mengkonversi nilai yang diharapkan pada nomor dari off spring
Nilai yang diharapkan dari chromosome adalah nomor real yang mengindikasikan nomor rata-rata dari offspring yang seharusnya diterima sebuah chromosome. Prosedur sampling digunakan untuk mengubah nilai real yang diharapkan pada nomor dari offspring.
Pendekatan ini biasanya memilih pop_size chromosome terbaik dari sampling space. Dari hasil yang ingin dicapai adalah melarang chromosome-chromosome duplikat masuk populasi pada waktu seleksi.
Seleksi Elitist menjamin bahwa chromosometer baik masuk generasi yang baru kalau tidak terpilih melalui proses seleksi yang lain. Modifikasi pada metode ini adalah dengan mengganti sejumlah n chromosome tua yang jelek dengan offspring (dengan jumlah n offspring).
c.Mixed sampling
Pendekatan ini berisi baik random dan ciri-ciri deterministic secara bersama. Contoh dari mixed sampling adalah Tournament Selection. Metode ini secara random memilih sekumpulan chromosome dan mengambil satu terbaik dari kumpulan untuk reproduksi. Jumlah chromosome dalam kumpulan dinamakan Tournament Size. Ukuran tournament umumnya adalah dua, ini yang dinamakan Binary Tournament dan Stochastic Tournament Selection oleh Wetzel, pada metode ini probabilitas seleksi dihitung secara normal dan berturut-turut pasangan dari chromosome-chromosome digambarkan menggunakan Roulette Wheel Selection. Setelah menggambarkan sepasang, chromosome dengan fitness yang tinggi dimasukkan dalam populasi yang baru. Proses ini berlangsung secara kontinu sampai populasi penuh.
SelectionProbabiliy
Bagian ini membicarakan bagaimana probabilitas seleksi untuk setiap chromosome. Dalam prosedur seleksi perbandingan, probabilitas seleksi dari sebuah chromosome sebanding denganf itness value yang dimilikinya. Contoh dalam generasi awal, dimana ada sebuah kecenderungan untuk sebuah super chromosome kecil akan mendominasi proses seleksi. Dalam generasi selanjutnya ketika populasi secara besar berkumpul, kompetisi diantara chromosome kurang kuat dan pencarian random tingkah laku akan muncul. Scaling dan ranking mechanism diharapkan dapat mengurangi masalah ini. Metode scaling membuat peta mentah nilai fungsi obyektif menjadi beberapa nilai real positif, dan probabilitas survival untuk setiap chromosome menurut nilai itu. Metode ranking menganggap nilai actual fungsi obyektif dan menggunakan ranking dari chromosome sebagai pengganti untuk menentukan probabilitas survival.
3.4 Rekombinasi Crossover
Cross-Over (Perkawinan Silang) merupakan proses mengkombinasikan dua individu untuk memperoleh individu-individubaru yang diharapkan mempunyai fitnesslebih baik. Tidak semua pasangan induk mengalami proses cross-over, banyaknya pasangan induk yang mengalami cross-over ditentukan dengan nilai probabilitas cross-over.
Cross-Over menggunakan arithmetic cross-over dengan definisi:
anak[1]=r.induk[1]+(1-r).induk[2]
acak[1]=r.induk[2]+(1-r).induk[1]
Prosedur untuk memilih parent mana yang akan mengalami proses crossover:
• Tentukan probabilitas crossover.
• Bangkitkan bilangan random 0 sampai 1 sebanyak I (jumlah chromosome dalam satu populasi).
• Bandingkan bilangan random itu dengan probabilitas crossover (Pc).
• Parent terpilih bila bilangan r yang ke-i kurang atau sama dengan probabilitas
Crossover (Pc).
• Bila parent yang terpilih jumlahnya hanya satu maka proses ini diulang sampai jumlah parent lebih dari satu.
3.5 MUTASI
Proses mutasi adalah proses yang bertujuan untuk mengubah salah satu atau lebih bagian dari chromosome. Untuk bilangan floating ini memakai Nonuniform Mutation atau yang dikenal sebagai Dynamic Mutation. Mutasi ini didesain untuk dapat mentuning dengan baik dengan tujuan mencapai tingkat ketelitian yang tinggi.
Prosedur untuk menentukan gen mana yang akan dimutasi adalah:
1. Tentukan probabilitas mutasi.
2. Tentukan banyaknya random yang diperoleh dari banyaknya jumlah chromosome dalam satu populasi x banyaknya gen dalam satu chromosome (total_random).
3. Bangkitkan bilangan random antara 0 dan 1 sebanyak total_random.
4. Bandingkan hasil random yang didapat sebanyak total_random dengan probabilitas mutasi.
5. Bilakurang dari probabilitas mutasi (Pm) maka gen tersebut yang akan dipilih untuk dimutasi.
6. Gen yang terpilih kemudian dihitung sehingga dapat diketahui gen tersebut berada pada chromosome nomor berapa dan pada gen yang nomor berapa.
Nonuniform Mutation
Proses mutasinya diberikan contoh parent x ,bila elemen x dari parent x yang
terpilih untuk dimutasi.
BinaryMutation
Mutasi ini memiliki prosedur yang mirip dengan yang digunakan oleh non uniform mutation.
Prosedur untuk pemilihan chromosomenya yaitu:
a. Tentukan probabilitas mutasi.
b.Tentukan banyaknya random yang diperoleh dari banyaknya jumlah chromosome dalam satu populasi x banyaknya jumlah bit dalam satu chromosome (total_random).
c. Bangkitkan bilangan random antara 0 dan 1 sebanyak total_random.
d. Bandingkan hasil random yang sebanyak total_random itu dengan probabilitas mutasi.
e.Bila nilai random itu kurang dari probabilitas mutasi (Pm) maka pilih bit itu untuk dimutasi.
f.Hitung bit yang terpilih itu berada pada chromosome keberapa dan pada posisi bit yang keberapa.
Untuk proses mutasinya, setelah diketahui bit yang akan dimutasi itu berada pada chromosome keberapa dan pada bit yang keberapa maka bila bit itu bernilai ‘0’ maka berubah ke‘1’,sebaliknya bila‘1’maka berubah ke‘0’.
Free DirectionMutation
Mutasi dapat juga menggunakan cara sederhana. Kromosom yang ada dimutasi dengan “arahbebas“. Maksudnya dapat bernilai positif maupun negatif.
www.google.com
www.wikipedia.com
