ALGORITMA GENETIKA
Algoritma Genetika menggunakan metafora tempat masalah optimasi terjadi lingkungan dan solusi yang layak dianggap sebagai individu yang hidup di dalamnya lingkungan Hidup. Dalam algoritma genetika, individu adalah digit biner atau beberapa lainnya set simbol yang diambil dari himpunan terbatas. Karena memori komputer terdiri dari array bit, apa saja dapat disimpan di komputer dan juga dapat dikodekan oleh string bit cukup panjang.
3.2 ELEMEN KUNCI
Dua elemen berbeda dalam GA adalah individu dan populasi. Seorang individu adalah solusi tunggal sementara populasi adalah sekumpulan individu yang saat ini terlibat dalam proses pencarian.
3.3 INDIVIDUAL
Seorang individu adalah solusi tunggal. Masing-masing kelompok menyatukan dua bentuk solusi
seperti yang diberikan di bawah ini:
1. Kromosom, yang merupakan informasi mentah 'genetik' (genotipe) yang dimiliki GA
penawaran.
2. Fenotip, yang merupakan ekspresi kromosom dalam istilah
model.
Sebuah kromosom dibagi lagi menjadi gen. Gen adalah representasi GA dari a faktor tunggal untuk faktor kontrol. Setiap faktor dalam set larutan sesuai dengan gen dalam kromosom. Gambar 3.1 menunjukkan representasi genotipe.
3.4 GEN
Gen adalah "instruksi" dasar untuk membangun Algoritma Generik. Sebuah kromosom adalah urutan gen. Gen dapat menggambarkan solusi yang mungkin untuk suatu masalah, tanpa benar-benar menjadi solusinya.
Kesesuaian seorang individu dalam suatu algoritma genetika adalah nilai dari suatu tujuan berfungsi untuk fenotipenya. Untuk menghitung kebugaran, kromosom harus menjadi yang pertama diterjemahkan dan fungsi tujuan harus dievaluasi. Kebugaran tidak hanya menunjukkan seberapa baik solusinya, tetapi juga sesuai dengan seberapa dekat kromosom yang optimal.
3.6 POPULASI
Populasi adalah kumpulan individu. Suatu populasi terdiri dari sejumlah individu
sedang diuji, parameter fenotip menentukan individu dan beberapa
informasi tentang ruang pencarian. Dua aspek penting dari populasi yang digunakan di
Algoritma Genetika adalah:
1. The initial population generation.
2. The population size.
3.7 STRUKTUR DATA
Struktur data utama dalam GA adalah kromosom, fenotip, fungsi objektif nilai dan nilai kebugaran. Ini sangat mudah diimplementasikan saat menggunakan Paket MATLAB sebagai alat numerik. Seluruh populasi kromosom bisa disimpan dalam satu array mengingat jumlah individu dan panjangnya representasi genotipe.
3.8 STRATEGI PENCARIAN
Proses pencarian terdiri dari menginisialisasi populasi dan kemudian berkembang biak baru individu sampai kondisi pemutusan terpenuhi. Ada beberapa tujuan untuk proses pencarian, salah satunya adalah mencari global optima.
3.9 PENGKODEAN
Pengkodean adalah proses mewakili gen individu. Prosesnya bisa dilakukan menggunakan bit, angka, pohon, array, daftar atau objek lainnya. Pengkodean tergantung terutama pada pemecahan masalah. Misalnya, seseorang dapat menyandikan secara langsung nyata atau angka integer.
3.9.1 Pengkodean Biner
Cara pengkodean yang paling umum adalah string biner, yang akan direpresentasikan seperti pada Gambar. 3.5 Setiap kromosom mengkodekan string biner (bit). Setiap bit dalam string dapat mewakili beberapa karakteristik solusinya. Oleh karena itu setiap bit string adalah solusi tetapi belum tentu solusi terbaik.
3.9.2 Pengkodean Oktal
3.9.3 Pengkodean Heksadesimal
3.9.4 Pengkodean Permutasi
Pengkodean permutasi hanya berguna untuk masalah pemesanan. Bahkan untuk masalah ini untuk beberapa jenis crossover dan koreksi mutasi harus dibuat untuk pergi kromosom yang konsisten (mis., memiliki urutan nyata di dalamnya).
3.9.5 Pengkodean Nilai
Setiap kromosom adalah serangkaian nilai dan nilainya bisa apa saja yang terhubung untuk masalah ini. Pengkodean ini menghasilkan hasil terbaik untuk beberapa masalah khusus. Di di sisi lain, seringkali perlu untuk mengembangkan operator genetik baru khusus untuk masalah.
3.9.6 Pengkodean Pohon
Pengkodean ini terutama digunakan untuk mengembangkan ekspresi program untuk pemrograman genetik. Setiap kromosom adalah pohon dari beberapa objek seperti fungsi dan perintah dari bahasa pemrograman.
3.10 Breeding
Proses breeding adalah jantung dari algoritma genetika,Ia adalah sebuah prses untuk membuat individual baru. Proses breeding sendiri terdiri atas 3 step yakni:
a. Pemilihan Induk/seleksi
b. Persilangan induk untuk membuat individual baru (anak)
c. Pergantian/regenerasi individu.
a. SELEKSI
Proses seleksi ialah pemilihan 2 induk dari seluruh populasi untuk dilakukan persilangan, kegunaan seleksi alah untuk memilih individual hasil persilangan yang lebih baik , kromoson dipilih dari populasi untuk kemudian di seleksi
adapun proses seleksi dapa dilihat dari bagan berikut:
laju konvergensi algoritma genetika ditentukan oleh magnitudp/besaran tekannan seleksi, yang berbanding lurus dengan tingkat ketinggian konvergensi .
b. CrossOver
Crossover adalah proses mengambil dua solusi induk dan menghasilkan dari mereka Seorang anak. Setelah proses seleksi (reproduksi), populasi diperkaya dengan individu yang lebih baik.
Mutasi mencegah algoritma terperangkap dalam minimum lokal. Mutasi memainkan peran memulihkan kehilangan materi genetik dan juga untuk informasi genetik yang mengganggu secara acak. Itu adalah polis asuransi terhadap kehilangan materi genetik yang tidak dapat dipulihkan.
d. Replacement
Penggantian adalah tahap terakhir dari setiap siklus pemuliaan. Dua orang tua diambil dari
populasi ukuran tetap, mereka membiakkan dua anak, tetapi tidak semua empat dapat kembali ke populasi, sehingga dua harus diganti yaitu, setelah mata air diproduksi, metode
harus menentukan anggota populasi mana yang saat ini, jika ada, yang seharusnya
digantikan oleh solusi baru.
3.11 Search Termination
singkatnya proses penghentian adalah sebagai berikut:
- Maximum generation Algoritma genetik berhenti ketka nomor yang ditentukan berhasil berevolusi.
- Elapsed time, proses genetika akqan berhenti ketika ketika waktu spesifik telah berlalu
- No change in fitness, Proses genetika akan berakhir ketika tidak ada perubahan terhadap ketahanan terbaik di populasi dalam beberapa generasi spesifik.
- Stall generations, algoritma berhenti ketika tidak ada perbaikan terhadap funsgi objektif dalam satu generasi
- Stall time limit,algoritma berhenti ketika tidak ada perbaikan dalam funsgi objektif dalam rentang waktu tertentu.
3.12 Kenapa algoritma genetika bisa bekerja?
ada beberapa hypotesis kenapa algoritma genetika bisa bekerja, Heuristic dari algoritma genetika bekerja sesuai dengan teorema Holland , sebuah skema yang didefinisikan sebagai template untuk mendeskripsikan subset kromosom dengan seksi yang sama, skema itu tersendiri terdiri atas bit 0 dan 1 dan meta-karakter. yang dimana ia cocok untuk mengenali kesamaan dalam sebuah pola.
Rumus daeri skema holland tersendiri adalah.
= number of strings belonging to schema 
at generation 
,
=observed average fitness of schema Selain itu di dalam algoritma genetika juga dikenal hipotesis blok pembangun/ building block hypothesis dimana ia tediri atas:
deskripsi heuristik yang melakukan adaptasi dengan mengidentifikasi dan mengkombinasikan blok penyusun hypotesis dimana ia melakukannya dengan implisit danefisien dalam building block.
3.13 Solution evaluation.
parameter setelah pencarian, atau mungkin beberapa faktor sederhana diabaikan. Jadi sekali jika suatu solusi diperoleh, itu harus dievaluasi untuk semua itu berbagai parameter yangdipertimbangkan, yang meliputi kebugaran, kebugaran rata-rata, individu terbaik, kebugaran maksimum dan sebagainya.
3.14 Search Refinement / penyempurnaan pencarian.
Parameter pencarian seperti pemilihan, crossover dan penggantian, yang sangat efektif pada tahap awal pencarian, mungkin tidak selalu menjadi yang terbaik menjelang akhir pencarian. Selama pencarian awal diinginkan untuk mendapatkan penyebaran poin yang baik ruang solusi untuk menemukan setidaknya awal dari berbagai optima. Sekali populasi mulai berkumpul pada optima it malam lebih baik untuk melakukan seleksi yang lebih ketat dan penggantian untuk sepenuhnya menutupi wilayah ruang.
3.15 Constraints/Batasan
Jika algoritma genetik yang ditangani hanya terdiri dari fungsi objektif dan tidak ada informasi tentang spesifikasi variabel, maka itu disebut masalah optimisasi tidak dibatasi. Pertimbangkan, masalah optimasi formulir yang tidak dibatasi,
Dalam kasus masalah optimasi yang terbatas, informasi disediakan untuk variabel yang dipertimbangkan. Kendala diklasifikasikan sebagai.
1. Equality relations.
2. Inequality relations
3.16 Fitness Scaling
Penskalaan fitness dilakukan untuk menghindari konvergensi dini dan lambat
finishing. Berbagai jenis penskalaan fitness adalah:
a. Linear Scaling
f ’ = af + b
Agar anggota rata-rata mendapatkan seleksi, rata-rata kebugaran setelah penskalaan harus sama dengan rata-rata kebugaran sebelum penskalaan
fav’ = fav
Agar tidak memungkinkan dominasi oleh individu super, jumlah salinan yang diberikan kepada mereka dikendalikan dengan mengambil,
f ’ max = C ∗ fav’
sehingga:
b. Sigma truncation
Skala linear memberikan kebugaran skala negatif kecuali langkah-langkah khusus diambil seperti yang dijelaskan di atas. Hasil kebugaran berskala negatif pada lari yang matang karena satu atau dua
anggota yang sangat lemah (nilai kebugaran rendah).
"Σ – Pemotongan" membuang anggota yang rata-rata seperti itu. Skala linear kemudian
berlaku untuk anggota yang tersisa.
f” = f − (fav-Cσ) if RHS > 0 = 0, otherwise
Setelah penskalaan linier ini diterapkan tanpa bahaya kebugaran negatif.
f’ = af” + b
c.Power Law Scaling
Dalam power law scaling, kebugaran skala diberikan oleh
Scaled fitness f’ = f k(raw fitness f)
Jika algoritma genetik yang ditangani hanya terdiri dari fungsi objektif dan tidak ada informasi tentang spesifikasi variabel, maka itu disebut masalah optimisasi tidak dibatasi. Pertimbangkan, masalah optimasi formulir yang tidak dibatasi,
Minimize f(x) = x2
Dalam kasus masalah optimasi yang terbatas, informasi disediakan untuk variabel yang dipertimbangkan. Kendala diklasifikasikan sebagai.
1. Equality relations.
2. Inequality relations
3.16 Fitness Scaling
Penskalaan fitness dilakukan untuk menghindari konvergensi dini dan lambat
finishing. Berbagai jenis penskalaan fitness adalah:
a. Linear Scaling
f ’ = af + b
Agar anggota rata-rata mendapatkan seleksi, rata-rata kebugaran setelah penskalaan harus sama dengan rata-rata kebugaran sebelum penskalaan
fav’ = fav
Agar tidak memungkinkan dominasi oleh individu super, jumlah salinan yang diberikan kepada mereka dikendalikan dengan mengambil,
f ’ max = C ∗ fav’
sehingga:
b. Sigma truncation
Skala linear memberikan kebugaran skala negatif kecuali langkah-langkah khusus diambil seperti yang dijelaskan di atas. Hasil kebugaran berskala negatif pada lari yang matang karena satu atau dua
anggota yang sangat lemah (nilai kebugaran rendah).
"Σ – Pemotongan" membuang anggota yang rata-rata seperti itu. Skala linear kemudian
berlaku untuk anggota yang tersisa.
f” = f − (fav-Cσ) if RHS > 0 = 0, otherwise
Setelah penskalaan linier ini diterapkan tanpa bahaya kebugaran negatif.
f’ = af” + b
c.Power Law Scaling
Dalam power law scaling, kebugaran skala diberikan oleh
Scaled fitness f’ = f k(raw fitness f)
Tidak ada komentar:
Posting Komentar