TEKNIK ELEKTRO UNIVERSITAS ANDALAS: BAB 3

Algoritma Genetik menggunakan sebuah metafora dimana masalah optimasi mengambil alih lingkungan dan solusi yang dianggap layak sebagai individu yang tinggal di lingkungan itu. Bentuk algoritma genetika yang paling sederhana melibatkan tiga jenis operator: seleksi, crossover (titik tunggal), dan mutasi.Seleksi Operator ini memilih kromosom dalam populasi untuk reproduksi. Semakin bugar kromosomnya, semakin sering kemungkinan untuk bereproduksi.Crossover Operator ini secara acak memilih lokus dan menukar urutan sebelum dan sesudah lokus antara dua kromosom untuk menciptakan dua keturunan. Mutasi Operator ini secara acak membalik beberapa bit dalam kromosom.

1. Key Elements [Kembali]

Terdapat dua elemen yang berbeda pada algoritma genetika yaitu individu dan populasi.

2. Individu (Individuals) [Kembali]

Individu adalah solusi tunggal. Individu menggabungkan dua bentuk solusi seperti di bawah ini :
1. Kromosom, yang merupakan informasi 'genetik' mentah (genotipe) yang ditawarkan GA.
2. Fenotipe, yang merupakan ekspresif kromosom dalam hal model.
Individu adalah solusi tunggal. Individu menggabungkan dua bentuk solusi seperti di bawah ini :

Gambar 1 Representasi Genotip dan Fenotip

Gambar 2 Representasi kromosom

Sebuah kromosom terbagi menjadi gen. Setiap faktor dalam rangkaian solusi sesuai dengan gen dalam kromosom. Gambar 1 menunjukkan representasi genotipe. Sebuah kromosom harus mengandung informasi tentang solusi yang diwakilinya. Fungsi morfogenesis menghubungkan setiap genotipe dengan fenotipenya. Ini berarti bahwa setiap kromosom harus mendefinisikan satu solusi unik, namun tidak berarti bahwa setiap solusi dikodekan oleh satu kromosom. Fungsi morfogenesis tidak diperlukan bijektif, dan kadang kala tidak mungkin (terutama dengan representasi biner). Meskipun demikian, fungsi morfogenesis setidaknya harus subjektif. Semua solusi kandidat masalah harus sesuai, setidaknya satu kemungkinan kromosom, untuk memastikan bahwa keseluruhan ruang pencarian dapat dieksplorasi. Bila fungsi morfogenesis yang menghubungkan setiap kromosom dengan satu larutan tidak dapat disuntikkan, seperti contoh kromosom yang berbeda dapat mengkodekan solusi yang sama, maka representasi tersebut dapat dikatakan merosot. Terdapatnya Degenerasi yang sedikit tidak begitu mengkhawatirkan, walaupun ruang dimana algoritma mencari solusi optimal pasti bisa diperbesar. Tapi degenerasi yang terlalu penting bisa menjadi masalah yang lebih serius. Hal ini dapat mempengaruhi perilaku GA, terutama
jika beberapa kromosom dapat mewakili fenotip yang sama, makna setiap gen tentu saja tidak sesuai dengan karakteristik spesifik dari larutan. Ini mungkin menambahkan semacam kebingungan dalam pencarian. Kromosom dikodekan dengan diberikan sedikit senar seperti pada Gambar 2.

3. Gen [Kembali]

Gen adalah "petunjuk" mendasar untuk membangun Algoritma Generik. Gen menggambarkan solusi yang mungkin untuk sebuah masalah, tanpa benar-benar menjadi solusinya. Gen adalah string kecil yang memiliki panjang acak. String bit adalah representasi biner dari jumlah interval dari batas bawah. Gen adalah representasi GA dari satu faktor nilai untuk faktor kontrol, di mana faktor kontrol harus memiliki batas atas dan batas bawah.

Gambar 3 Representasi gen

Rentang ini dapat dibagi menjadi jumlah interval yang dapat diekspresikan dengan string bit gen. String bit panjang 'n' dapat mewakili interval (2n - 1). Ukuran intervalnya adalah (range) / (2n - 1). Dalam kromosom, gen direpresentasikan seperti pada (Gambar 3)

4. Kemampuan [Kembali]

Kemampuan sebuah individu dalam algoritma genetika adalah nilai fungsi objektif untuk fenotipenya. Untuk menghitung kemampuan, kromosom harus diterjemahkan terlebih dahulu dan fungsi objektif harus dievaluasi. Kemampuan tidak hanya menunjukkan seberapa bagus solusinya, tapi juga sesuai dengan seberapa dekat kromosomnya dengan yang optimal.

5. Populasi [Kembali]

Populasi adalah kumpulan individu. Populasi terdiri dari sejumlah individu yang diuji, parameter fenotip yang menentukan individu dan beberapa informasi tentang ruang pencarian. Dua aspek penting populasi yang digunakan dalam Algoritma Genetika adalah:

Generasi penduduk awal.

Ukuran populasi.

Gambar 4 Populasi

Populasi yang menjadi kombinasi dari berbagai kromosom diwakili seperti pada Gambar 4, Jadi populasi di atas terdiri dari empat kromosom.

6. Struktur data [Kembali]

Struktur data utama pada GA adalah kromosom, fenotip, nilai fungsi objektif, dan nilai kemampuan. Hal ini sangat mudah diimplementasikan saat menggunakan paket MATLAB sebagai alat numerik. Seluruh populasi kromosom dapat disimpan dalam satu array mengingat jumlah individu dan panjang representasi genotipe mereka. Demikian pula variabel desain, atau fenotipe yang diperoleh dengan menerapkan beberapa pemetaan dari representasi kromosom ke dalam ruang perancangan dapat disimpan dalam satu array tunggal. Pemetaan yang sebenarnya bergantung pada skema decoding yang digunakan. Nilai fungsi tujuan dapat berupa skalar atau vectorial dan harus sama dengan nilai kesesuaian. Nilai kemampuan berasal dari fungsi objek dengan menggunakan fungsi scaling atau ranking dan dapat disimpan sebagai vektor.

7. Strategi pencarian [Kembali]

Proses pencarian terdiri dari menginisialisasi populasi dan kemudian membiakkan individu baru sampai kondisi terminasi terpenuhi. Ada beberapa tujuan untuk proses pencarian, salah satunya adalah menemukan optima global. Ini tidak akan pernah bisa diyakinkan dengan jenis model yang bekerja dengan GA. Selalu ada kemungkinan bahwa iterasi berikutnya dalam pencarian akan menghasilkan solusi yang lebih baik. Dalam beberapa kasus, proses pencarian bisa berjalan bertahun-tahun dan tidak menghasilkan solusi yang lebih baik daripada yang dilakukan pada iterasi kecil yang pertama. Tujuan lain adalah konvergensi yang lebih cepat. Bila fungsi objektif itu mahal untuk dijalankan, konvergensi yang lebih cepat sangat diharapkan, namun kemungkinan konvergen pada optima lokal, dan mungkin di bawah standar meningkat.

8. Encoding [Kembali]

Encoding adalah proses untuk merepresentasikan gen individu. Prosesnya bisa dilakukan dengan menggunakan bit, angka, pohon, array, daftar atau benda lainnya. Pengkodeannya bergantung pada pemecahan masalah. Sebagai contoh, seseorang dapat mengkodekan bilangan real atau integer secara langsung.

Binary Encoding
Setiap kromosom dikodekan sebagai string biner (bit). Setiap bit dalam string dapat mewakili beberapa karakteristik dari solusi. Setiap string bit jadi solusi namun belum tentu solusi terbaik. Kemungkinan lain adalah bahwa keseluruhan string bisa mewakili sebuah angka. Cara string bit bisa berbeda dari kode ke masalah.

Gambar 5 Binary encoding

Biner encoding memberikan banyak kemungkinan kromosom dengan sejumlah kecil alel (gen yang memiliki lokus(posisi pada kromosom) yang sama). Di sisi lain pengkodean ini tidak alami untuk banyak masalah dan terkadang koreksi harus dilakukan setelah operasi genetik selesai. String kode biner dengan 1s dan 0s banyak digunakan. Panjang tali tergantung pada keakuratannya. Dimana,

Integer diwakili dengan tepat
Jumlah bilangan real yang terbatas dapat diwakili
Jumlah bilangan real terwakili meningkat dengan panjang string

Octal Encoding Encoding ini menggunakan string yang terdiri dari bilangan oktal (0-7).

Gambar 6 Pengkodean Oktal

Hexadecimal Encoding
Encoding ini menggunakan string yang terdiri dari bilangan heksadesimal (0-9, A-F)

Gambar 7 pengkodean heksadesimal

Permutation Encoding ( Pengkodean Bilangan Bulat )
Setiap kromosom adalah serangkaian angka, yang mewakili bilangan secara berurutan. Terkadang koreksi harus dilakukan setelah operasi genetik selesai. Dalam permutasi encoding, setiap kromosom adalah string bilangan bulat / nilai sebenarnya, yang mewakili bilangan secara berurutan.

Gambar 8 Permutasi encoding

Permutasi encoding hanya berguna untuk masalah pemesanan. Koreksi crossover dan mutasi harus dilakukan agar kromosom tetap konsisten (yaitu memiliki urutan sebenarnya di dalamnya).

Value Encoding
Pengkodean nilai sangat bagus untuk beberapa masalah khusus. Di sisi lain, pengkodean ini sering diperlukan untuk mengembangkan beberapa mutasi dan mutasi baru yang spesifik untuk masalah ini.

Gambar 9 Pengkodean nilai

Tree Coding
Encoding ini terutama digunakan untuk mengembangkan ekspresi program untuk pemrograman genetika. Setiap kromosom adalah pohon dari beberapa benda seperti fungsi dan perintah bahasa pemrograman.

9. Breeding [Kembali]

Proses pemuliaan adalah jantung dari algoritma genetika. Dalam proses ini, terjadi proses pencarian untuk menciptakan individu baru. Siklus pemuliaan terdiri dari tiga tahap:

Memilih orang tua
Melintasi orang tua untuk menciptakan individu baru (keturunan atau anak-anak).
Mengganti orang tua dalam populasi dengan populasi baru.

Selection
Seleksi adalah proses memilih dua orang tua dari populasi untuk menyeberang. Setelah memutuskan pengkodean, langkah selanjutnya adalah memutuskan bagaimana melakukan seleksi. Seleksi adalah metode yang secara acak memilih kromosom dari populasi sesuai dengan fungsi evaluasi mereka. Semakin tinggi fungsi kecocokan, semakin besar kemungkinan seseorang harus dipilih. Tekanan seleksi didefinisikan sebagai sejauh mana individu yang lebih baik disukai.
Gambar 10 Proses Seleksi Dasar
Beberapa metode seleksi :

Roulette Wheel Selection

Nilai yang diharapkan dari seorang individu adalah ketangkasan dibagi dengan tingkat populasi yang sebenarnya. Masing-masing individu diberi sepotong roda rolet, ukuran potongannya sebanding dengan kemampuan individu. Roda berputar N kali, di mana N adalah jumlah individu dalam populasi. Pada setiap putaran, individu di bawah penanda roda dipilih berada di kolam orang tua untuk generasi berikutnya. Metode ini diimplementasikan sebagai berikut:

Jumlah total nilai yang diharapkan dari individu dalam populasi yang disebut T.
Ulangi N kali :

Pilih bilangan bulat acak 'r' antara o dan T.
Loop melalui individu dalam populasi, menjumlahkan nilai yang diharapkan, sampai jumlahnya lebih besar dari atau sama dengan 'r'. Individu yang nilai harapannya menempatkan jumlah di atas batas ini adalah yang dipilih.

Roulette wheel selection lebih mudah diimplementasikan tapi ribet. Tingkat evolusi bergantung pada varians dari kesesuaian dalam populasi.

Random Selection

Teknik ini secara acak memilih orang tua dari populasi. Dalam hal terganggunya kode genetik, seleksi acak sedikit lebih mengganggu, rata-rata, dibanding pemilihan roulette wheel.

Rank Selection

Rank Selection memberi peringkat pada populasi dan setiap kromosom menerima ketepatan dari peringkat. Ada beberapa cara untuk melakukan metode ini :

Pilih sepasang individu secara acak. Buat bilangan acak ‘R’ antara 0 dan 1. Jika R = r kemudian menggunakan individu kedua sebagai induknya. Ini diulang untuk memilih orang tua kedua. Nilai r adalah parameter untuk metode ini.
Pilih dua individu secara acak. Individu dengan evaluasi tertinggi menjadi orang tua. Ulangi untuk menemukan orang tua kedua.

Tournament Selection

Individu terbaik dari turnamen adalah yang memiliki ketepatan tertinggi, yang merupakan pemenang Nu. Kompetisi dalam turnamen dan pemenangnya kemudian dimasukkan ke dalam kolam kawin. Kompetisi turnamen diulang sampai kolam kawin untuk menghasilkan keturunan baru diisi. Kolam kawin yang terdiri dari pemenang turnamen memiliki tingkat populasi rata-rata yang lebih tinggi. Kesulitan membedakan memberikan tekanan seleksi, yang mendorong GA untuk meningkatkan kemampuan gen yang berhasil. Metode ini lebih efisien dan menghasilkan solusi optimal.

Boltzmann Selection

Simulasi annealing merupakan metode minimisasi fungsi atau maksimalisasi. Metode ini mensimulasikan proses pendinginan lambat logam cair untuk mencapai nilai fungsi minimum dalam masalah minimisasi. Mengontrol suhu seperti parameter yang diperkenalkan dengan konsep distribusi probabilitas Boltzmann mensimulasikan fenomena pendinginan.

Stochastic Universal Sampling

Stochastic universal sampling memberikan bias nol dan spread minimum. Individu dipetakan ke segmen garis yang berdekatan, sehingga segmen masing-masing sama ukurannya dengan ketepatannya seperti pada pemilihan roulette-wheel. Berikut pointer spasi sama ditempatkan di atas garis, sebanyak ada individu yang akan dipilih. Pertimbangkan NPointer jumlah individu yang akan dipilih, maka jarak antara pointer adalah 1 / N Pointer dan posisi pointer pertama diberikan oleh bilangan acak yang dihasilkan pada kisaran [0,1 / N Pointer].

Gambar 11 contoh Stochastic universal sampling

Crossover ( Recombination )

Crossover adalah proses mengambil dua solusi orang tua dan menghasilkan anak dari mereka. Setelah proses seleksi (reproduksi), populasi diperkaya dengan individu yang lebih baik. Reproduksi membuat klon senar yang bagus tapi tidak menghasilkan yang baru. Operator crossover diaplikasikan ke kolam kawin dengan harapan bisa menciptakan keturunan yang lebih baik. Crossover adalah operator rekombinasi yang berjalan dalam tiga tahap:

Operator reproduksi memilih secara acak sepasang dua senar individu untuk perkawinan.
Sebuah situs silang dipilih secara acak sepanjang panjang string.
Akhirnya, nilai posisi ditukar antara dua senar berikut cross site.

Berbagai teknik crossover dibahas sebagai berikut:

Singel Point Crossover
Algoritma genetika tradisional menggunakan crossover titik tunggal, di mana dua kromosom kawin dipotong satu kali pada titik yang sesuai dan bagian setelah potongan ditukar. Di sini, titik cross-site atau crossover dipilih secara acak sepanjang string yang dikawinkan dan bit di samping cross-site dipertukarkan.

Gambar 12 Titik tunggal Crossover

Two Point Crossover

Dalam crossover dua titik, dua titik crossover dipilih dan isi antara titik-titik ini dipertukarkan antara dua orang tua yang dikawinkan.

Gambar 13 Crossover dua titik

Multi-Point Crossover ( N-point Crossover )

Ada dua cara dalam crossover ini. Salah satunya adalah jumlah cross-sites dan jumlah ganjil lainnya dari cross-site. Dalam kasus bahkan jumlah cross-site, cross-site dipilih secara acak di sekitar lingkaran dan informasi dipertukarkan. Uniform Crossover

Setiap gen pada keturunan diciptakan dengan menyalin gen yang sesuai dari satu atau induk lainnya yang dipilih sesuai dengan masker crossover biner acak yang dihasilkan dengan panjang yang sama seperti kromosom. Dimana ada 1 di topeng crossover, gen disalin dari orang tua pertama, dan di mana ada 0 di topeng, gen tersebut disalin dari orang tua kedua. Masker crossover baru dibuat secara acak untuk masing-masing pasangan orang tua.

Gambar 14 Crossover seragam

Three Parent Crossover

Dalam teknik crossover ini, tiga orang tua dipilih secara acak. Setiap bit orang tua pertama dibandingkan dengan bit induk kedua. Jika keduanya sama, bitnya diambil untuk keturunannya,sedikit dari induk ketiga diambil untuk keturunannya.

Gambar 15 Tiga induk Crossover

Crossover with Reduced Surrogate

Operator pengganti yang berkurang membatasi crossover untuk selalu menghasilkan individu baru sedapat mungkin. Hal ini diimplementasikan dengan membatasi lokasi titik crossover sehingga titik crossover hanya terjadi dimana nilai gen berbeda. Shuffle Crossover
Crossover shuffle ini berhubungan dengan crossover seragam. Posisi crossover tunggal (seperti pada crossover satu titik) dipilih. Tapi sebelum variabel dipertukarkan, keduanya acak pada kedua orang tua. Setelah rekombinasi, variabel pada keturunannya tidak diketahui. Ini menghilangkan bias posisi karena variabel-variabel tersebut secara acak ditugaskan kembali setiap kali crossover dilakukan. Precedence Preservative Crossover ( PPX )
Operator melewati hubungan precedence operasi yang diberikan dalam dua permutasi parental kepada satu keturunan pada tingkat yang sama, sementara tidak ada hubungan preseden baru yang diperkenalkan.PPX diilustrasikan di bawah, untuk masalah yang terdiri dari enam operasi A-F.

Gambar 16 Precedence Preservative Crossover (PPX)

Ordered Crossover

Crossover yang dipesan dua titik berperilaku dengan cara berikut: anak 1 mewarisi bagian kiri dan kanan dari orang tua 1, dan bagian tengahnya ditentukan oleh gen di bagian tengah orang tua 1 sesuai urutan nilai yang muncul pada orang tua. 2. Proses serupa diterapkan untuk menentukan anak 2.

Gambar 17 Memerintahkan crossover

Partially Matched Crossover ( PMX )

Ini dapat dipandang sebagai crossover permutasi yang menjamin bahwa semua posisi ditemukan tepat sekali pada setiap keturunan, yaitu kedua keturunan menerima gen lengkap, diikuti oleh lapisan yang sesuai dengan alel dari orang tua mereka. PMX melanjutkan sebagai berikut:

Dua kromosom sejajar.
Dua lokasi persimpangan dipilih secara seragam secara acak sepanjang senar, untuk menentukan bagian yang sesuai

Crossover Probability

Parameter dasar dalam teknik crossover adalah crossover probability (Pc). Probabilitas crossover adalah parameter untuk menggambarkan seberapa sering crossover akan dilakukan. Jika tidak ada crossover, keturunan adalah salinan orang tua yang tepat. Jika ada crossover, keturunan dibuat dari bagian kromosom kedua orang tua. Jika probabilitas crossover adalah 100%, maka semua keturunan dibuat dengan crossover. Jika 0%, seluruh generasi baru dibuat dari eksemplar kromosom dari populasi lama (tapi ini tidak berarti bahwa generasi baru adalah sama!). Crossover dibuat dengan harapan kromosom baru akan mengandung bagian kromosom lama yang baik dan oleh karena itu kromosom baru akan menjadi lebih baik. Namun, ada baiknya meninggalkan sebagian populasi lama yang bertahan sampai generasi penerus.

Mutation

Mutasi secara tradisional dianggap sebagai operator pencarian sederhana. Jika crossover seharusnya memanfaatkan solusi saat ini untuk menemukan yang terbaik, mutasi seharusnya membantu eksplorasi keseluruhan ruang pencarian. Mutasi dipandang sebagai operator latar belakang untuk menjaga keragaman genetik dalam populasi. Ini memperkenalkan struktur genetik baru dalam populasi dengan memodifikasi secara acak beberapa blok bangunannya. Mutasi membantu melepaskan diri dari jebakan minima lokal dan mempertahankan keragaman dalam populasi.

Flipping

Membalik sedikit melibatkan perubahan 0 sampai 1 dan 1 sampai 0 berdasarkan kromosom mutasi yang dihasilkan.

Gambar 18 Mutasi Flipping

Interchanging

Dua posisi acak dari string dipilih dan bit yang sesuai dengan posisi tersebut dipertukarkan.

Gambar 19 Interchanging

Reversing

Posisi acak dipilih dan bit di sebelah posisi itu terbalik dan kromosom anak diproduksi.

Gambar 20 Reversing

Mutation Probability

Parameter penting dalam teknik mutasi adalah probabilitas mutasi (Pm). Probabilitas mutasi menentukan seberapa sering bagian kromosom akan bermutasi. Jika tidak ada mutasi, keturunan dihasilkan segera setelah crossover (atau langsung disalin) tanpa ada perubahan. Jika mutasi dilakukan, satu atau beberapa bagian kromosom diubah. Jika probabilitas mutasi adalah 100%, seluruh kromosom berubah, jika 0%, tidak ada yang berubah.

Replacement

Penggantian adalah tahap terakhir dari setiap siklus pemuliaan. Dua orang tua diambil dari populasi ukuran tetap, mereka mengembangbiakkan dua anak, namun tidak semua orang dapat kembali ke populasi, jadi dua harus diganti yaitu, sekali dari sumber mata air dihasilkan, sebuah metode harus menentukan anggota populasi saat ini. , jika ada, harus diganti dengan solusi baru. Teknik yang digunakan untuk menentukan individu mana yang tinggal dalam populasi dan yang diganti secara setara dengan pemilihan dalam mempengaruhi konvergensi.

Random Replecement

Anak-anak mengganti dua individu yang dipilih secara acak dalam populasi. Orang tua juga kandidat untuk seleksi. Ini bisa berguna untuk melanjutkan pencarian di populasi kecil, karena individu lemah dapat diperkenalkan ke dalam populasi.

Weak Parent Replacement

Dalam penggantian orang tua yang lemah, orang tua yang lemah digantikan oleh anak yang kuat. Dengan empat individu hanya dua orang tua, orang tua atau anak pertama, kembali ke populasi. Proses ini meningkatkan ketepatan populasi secara keseluruhan bila dipasangkan dengan teknik seleksi yang memilih orang tua yang lemah dan lemah untuk menyeberang, tetapi jika individu lemah dan terdiskriminasi dalam pemilihan, kesempatan tersebut tidak akan pernah bisa menggantikannya.

Both Parents

Kedua pengganti orang tua itu sederhana. Anak menggantikan orang tua. Dalam kasus ini, setiap individu hanya bisa berkembang biak sekali. Akibatnya, populasi dan materi genetik berpindah-pindah namun mengarah pada masalah saat dikombinasikan dengan teknik seleksi yang sangat menguntungkan orang tua: berkembang biak dan kemudian dibuang.

10. Search Terminaton [Kembali]

Berbagai kondisi berhenti tercantum sebagai berikut:

Generasi maksimum - Algoritma genetika berhenti saat jumlah generasi tertentu telah berevolusi.
Waktu yang telah berlalu - Proses genetika akan berakhir ketika waktu yang ditentukan telah berlalu.
Catatan: Jika jumlah maksimum generasi telah tercapai sebelum waktu yang ditentukan telah berlalu, prosesnya akan berakhir.
Tidak ada perubahan dalam kesesuaian - Proses genetik akan berakhir jika tidak ada perubahan pada kemampuan terbaik populasi untuk jumlah generasi tertentu.
Catatan: Jika jumlah generasi maksimum telah tercapai sebelum jumlah generasi yang ditentukan tanpa perubahan telah tercapai, prosesnya akan berakhir.
Stall generation-Algoritma berhenti jika tidak ada perbaikan fungsi objektif untuk urutan generasi berturut-turut generasi Stall.
Stall time limit-Algoritma berhenti jika tidak ada perbaikan fungsi objektif selama selang waktu dalam detik yang sama dengan batas waktu Stall.
Kriteria penghentian atau konvergensi akhirnya menghentikan pencarian. Berikut adalah beberapa metode teknik terminasi.

Best Individual

Kriteria konvergensi individu terbaik menghentikan pencarian setelah tingkat minimum populasi menurun di bawah nilai konvergensi. Hal ini membawa pencarian ke kesimpulan yang lebih cepat yang menjamin setidaknya satu solusi yang baik.

Worst Individual

Individu terburuk menghentikan pencarian ketika individu paling tidak memiliki populasi kurang dari kriteria konvergensi. Ini menjamin seluruh populasi memiliki standar minimum, meskipun individu terbaik mungkin tidak lebih baik daripada yang terburuk. Dalam kasus ini, nilai konvergensi yang ketat mungkin tidak akan pernah terpenuhi, dalam hal mana pencarian akan berakhir setelah batas maksimum terlampaui.

Sum of Fitness

Dalam skema penghentian ini, pencarian dianggap memiliki kepuasan yang terkumpul saat jumlah kekakuan di seluruh populasi kurang dari atau sama dengan nilai konvergensi dalam catatan populasi. Ini menjamin bahwa hampir semua individu dalam populasi akan berada dalam kisaran kecemerlangan tertentu, walaupun lebih baik memasangkan kriteria konvergensi ini dengan penggantian gen yang paling lemah, jika tidak, beberapa individu yang tidak sempurna dalam populasi akan meniup jumlah korban. Ukuran populasi harus dipertimbangkan saat menetapkan nilai konvergensi.

Median Fitness

Di sini setidaknya setengah dari individu akan lebih baik dari atau sama dengan nilai konvergensi, yang harus memberikan solusi yang baik untuk dipilih.

11. Why Do Genetic Algoritmhs Work ? [Kembali]

Template adalah cara yang tepat untuk menggambarkan kesamaan antara Pola dalam kromosom Holland yang menghasilkan sebuah ungkapan yang memprediksi jumlah salinan skema tertentu pada generasi berikutnya setelah menjalani eksploitasi, crossover dan mutasi.

Membangun Blok Hipotesis

Schemata dengan nilai kesesuaian tinggi dan definisi kecil disebut Building Blocks. Algoritma genetika mencari kinerja yang hampir optimal melalui penjajaran skema kinerja rendah, low-order, berperforma tinggi, yang disebut blok bangunan. Hipotesis blok bangunan adalah salah satu kriteria terpenting "bagaimana algoritma genetika". Hipotesis blok bangunan dikatakan oleh buku Goldberg sebagai: "Algoritma genetika mencapai kinerja tinggi melalui penjajaran susunan pendek, rendah, schemata yang sangat baik, atau blok bangunan". Arti "skema sangat baik" tidak sepenuhnya jelas. Interpretasi yang paling jelas adalah bahwa skema sangat sesuai jika ketepatan rata-ratanya jauh lebih tinggi daripada rata-rata ketepatan semua senar di ruang pencarian. Versi hipotesis blok bangunan ini bisa disebut "static building block hypothesis".

Hipotesis Makro-Mutasi

Ini adalah hipotesis alternatif untuk menjelaskan bagaimana kerja GA. Berdasarkan hipotesis ini, fungsi crossover adalah "macromutation". Macromutasi adalah mutasi banyak bit dan bukan hanya 1 atau 2 seperti yang kemungkinan terjadi di bawah mutasi bitwise standar. Operator macrosmutasi yang akan serupa dengan crossover satu titik atau dua titik adalah memilih urutan posisi bersebelahan dan kemudian menggantinya dengan string acak.

Hipotesis Mutasi Adaptif

Sebenarnya, GA hampir selalu berkembang dengan sangat menghargai hasilnya dan dengan sedikit memperhatikan keanggunan, bukti, atau basa-basa matematis lainnya. Namun demikian, beberapa hipotesis telah diajukan untuk menjelaskan hasil yang diperoleh GAs. Hipotesis mutasi adaptif adalah bahwa di mana crossover di GA berfungsi sebagai mekanisme mutasi yang secara otomatis disesuaikan dengan tahap konvergensi populasi.

Teorema Skema

Skema adalah template kemiripan yang menggambarkan subset dari string yang menampilkan kemiripan pada posisi string tertentu. Ini dibentuk oleh alfabet terner {0,1, *}, di mana * hanyalah simbol notasi, yang memungkinkan deskripsi dari semua kemiripan yang mungkin di antara senar dengan panjang dan alfabet tertentu. Secara umum, ada 2 string atau kromosom yang berbeda dengan panjang 1, tapi schemata menampilkan urutan 3.

Alokasi Uji Coba Optimal

Pendekatan sederhana untuk masalah ini adalah memisahkan eksplorasi dari eksploitasi. Lebih khusus lagi, adalah mungkin untuk melakukan percobaan tunggal di awal dan selanjutnya membuat keputusan yang tidak dapat diubah yang bergantung pada hasil percobaan.

Paralelisme Implisit

J. Hollandanalyzedthatin populasi kromosom, skemaGasprocessO (n3) ke dalam setiap generasi. Dia menyebutnya sebagai "Proses paralel implisit"

Teorema No Free Lunch

Pekerjaan No free lunch adalah kerangka kerja yang membahas aspek inti pencarian, dengan fokus pada hubungan antara fungsi kecocokan dan algoritma pencarian yang efektif. Pentingnya hubungan ini ditunjukkan oleh teorema No Free Lunch, yang menyatakan bahwa, keseluruhan masalah rata-rata, semua algoritma pencarian berkinerja sama.

12. Solution Evaluation [Kembali]

Jika suatu solusi diperoleh, maka harus dievaluasi untuk semua berbagai parameter yang dipertimbangkan, yang mencakup kesesuaian, median fitness, individu terbaik, tingkat maksimum dan sebagainya.

13. Search Revinement [Kembali]

Parameter pencarian seperti pemilihan, crossover dan penggantian, yang sangat efektif di awal pencarian, mungkin tidak perlu dilakukan oleh theendestard theend of the search. Selama pencarian awal, sangat diharapkan untuk mendapatkan titik penyebaran yang baik melalui ruang solusi di orderto setidaknya di awal berbagai variasi. Setelah populasi mulai berkumpul di optima, malam hari akan lebih baik untuk melakukan seleksi dan penggantian yang lebih ketat untuk sepenuhnya menutupi wilayah ruang. Sebagai alternatif, pengaturan juga dapat dilakukan dalam domain dan resolusi gen individu. Sejumlah besar dan resolusi kasar di awal pencarian akan membantu menyebarkan titik-titik itu.

14. Kendala [Kembali]

Dalam kasus masalah optimasi yang dibatasi, informasi disediakan untuk variabel yang diperhitungkan. Kendala diklasifikasikan sebagai,

1. Hubungan kesamaan.
2. Hubungan ketidaksetaraan.
Algoritma genetika menghasilkan urutan parameter yang akan diuji dengan menggunakan sistem yang sedang dipertimbangkan, fungsi objektif (untuk dimaksimalkan atau diminimalkan) dan kendala. Saat menjalankan sistem, fungsi objektif dievaluasi dan kendala diperiksa untuk melihat apakah ada pelanggaran. Jika tidak ada pelanggaran, himpunan parameter diberi nilai kesesuaian sesuai dengan evaluasi fungsi objektif. Bila hambatan dilanggar, solusinya tidak memungkinkan dan karenanya tidak memiliki kesesuaian.

15. Fitness Scaling [Kembali]

Penskalaan kebugaran dilakukan untuk menghindari konvergensi prematur dan memperlambat proses penuaan. Berbagai jenis skala ketangkasan adalah:

Penskalaan linier
σ-pemotongan
Hukum daya

Penskalaan linier

Mempertimbangkan,

f-Unscaled raw trance
f'-Kebugaran setelah penskalaan
f’ = af+b

Pemotongan Sigma

Penskalaan linier memberikan kecocokan skala negatif kecuali langkah-langkah khusus diambil seperti yang dijelaskan di atas. Hasil skala negatif pada jalan yang matang karena satu atau dua anggota yang sangat lemah (nilai kesesuaian rendah).
"σ-Truncation" membuang seperti anggota rata-rata. Penskalaan linier kemudian diterapkan ke anggota yang tersisa.

Hukum daya

Dalam penskalaan kuasa hukum, tingkat kecukupan diberikan oleh,

Scaled ﬁtness f’= fK(raw ﬁtness f)
K-masalah dependentconstant. 1.005

16. Contoh Masalah [Kembali]

Memaksimalkan Fungsi

Mempertimbangkan masalah memaksimalkan fungsi,
f(x) =x2
dimana x diijinkan bervariasi antara 0 sampai 31. Langkah-langkah yang terlibat dalam memecahkan masalah ini adalah sebagai berikut:
Langkah 1: Untuk menggunakan pendekatan algoritma genetika, seseorang harus terlebih dahulu memasukkan variabel keputusan 'x' ke dalam string panjang yang tidak terbatas. Menggunakan lima bit (integer biner) unsigned integer, bilangan antara 0 (00000) dan 31 (11111) dapat diperoleh.
Langkah 2: Dapatkan nilai x yang didekode untuk populasi awal yang dihasilkan. Pertimbangkan string 1.

Tabel 1 seleksi

Langkah 3: Hitung kesesuaian fungsi orobjective. Oleh karena itu, cukup mengkuadratkan nilai 'x', karena fungsi yang diberikan adalah f (x) = x2.
Bila, x = 12, nilai fitnessnya adalah,
f(x) = x2 = (12)2 = 144
Langkah 4: Hitung probabilitas pemilihan,
Probi = f(x)ii=1nf(x)i
dimana n - tidak ada populasi f (x) - nilai kesesuaian yang sesuai dengan individu tertentu dalam populasi.
Σf (x) - Penjumlahan semua nilai kesesuaian seluruh populasi.
Langkah 5: Langkah selanjutnya adalah menghitung penghitungan yang diharapkan, yang dihitung sebagai,
Expected count = f(x)i(Avgf(x))i
Dimana (Avgf(x))i = [i=1nf(x)in]
Langkah 6: Sekarang jumlah orang yang tepat yang bisa dihubungi memilih individu, yang akan berpartisipasi dalam siklus waktu yang berbeda dengan menggunakan seleksi Roulette wheel.

Gambar 21 seleksi menggunakan Roulette Wheel

Langkah 7: Sekarang, tulislah kolam kawin berdasarkan hitungan sebenarnya seperti yang ditunjukkan pada Tabel 2.

Tabel 2 Crossover

String penghitungan sebenarnya no 1 adalah 1, maka itu terjadi sekali di kolam kawin. Hitungan sebenarnya dari string no 2 adalah 2, maka terjadi dua kali di kolam kawin. Karena hitungan sebenarnya dari string no 3 adalah 0, itu tidak terjadi pada kolam kawin. Demikian pula, hitungan sebenarnya dari string no 4 menjadi 1, terjadi di dalam kolam kawin. Berdasarkan hal ini, kolam kawin terbentuk.
Langkah 8: Operasi crossover dilakukan pada anak-anak producenew (anak-anak).
Titik crossover ditentukan dan berdasarkan titik crossover, titik tunggal crossoveris dilakukan dan keturunan baru terbentuk. Orang tua,

Keturunannya diproduksi sebagai,

Dengan cara yang sama, crossover dilakukan untuk senar berikutnya.
Langkah 9: Setelah operasi crossover, pegas baru dihasilkan dan nilai 'x' adalah decode dan fi tness dihitung.
Langkah 10: Pada langkah ini, operasi mutasi dilakukan untuk menghasilkan arus keluar baru setelah operasi silang. Tabel 3 menunjukkan keturunan baru setelah mutasi.

Tabel 3 mutasi

Traveling Salesman Problem

Traveling Salesman Problem adalah masalah permutasi dimana tujuannya adalah untuk menemukan jalur terpendek antara kota-kota yang berbeda yang dibutuhkan oleh salesman disebut tur. Dengan kata lain, masalahnya berkaitan dengan menemukan rute yang mencakup semua kota sehingga jarak total yang ditempuh minimal.

Encoding

Semua kota berurutan terhitung mulai dari satu. Jalan-jalan di antara kota-kota tersebut ditentukan dengan membandingkannya dengan catatan waktu yang ada di kota tersebut. Array mewakili urutan di mana kota-kota dilalui.

Gambar 22 kromosom mewakili tur

Crossover

Untuk mengatasi masalah salesman keliling, skema reproduksi crossover sederhana tidak berjalan karena membuat kromosom tidak konsisten, beberapa kota dapat diulang sementara yang lain tidak terjawab. Kelemahan mekanisme crossover sederhana diilustrasikan pada Gambar 23 Seperti dapat dilihat di atas, kota 6 dan 7 hilang pada Anak1 sedangkan kota 2 dan 4 dikunjungi lebih dari satu kali.

Gambar 23 Crossover

Gambar 24 Sebagian cocok crossover

Mutasi

Mutasi memiliki probabilitas tinggi menghasilkan tatanan kota yang tidak layak. Namun, mutasi masih diterapkan dengan memperhitungkan pesanan kota yang tidak layak dalam fungsi evaluasi. Untuk masalah ini, mutasi mengacu pada pertukaran kota secara acak dalam kromosom.

Gambar 25 Mutasi

Fitness Measure

Fungsi penyimpanan mengambil solusi percobaan dan mengembalikan nilai ketahanan. Semakin pendek rute semakin tinggi nilai kesesuaiannya. Dengan menggunakan mekanisme crossover dan inversi yang sebagian cocok, jalur yang tidak layak dihilangkan. Oleh karena itu, kebutuhan untuk menghukum kromosom rendah tidak muncul.

Metode Seleksi

Dengan menggunakan mekanisme seleksi steady state, dua kromosom dari populasi dipilih untuk operasi crossover dan mutasi. Anak keturunan yang diperoleh menggantikan kromosom terkecil pada populasi yang ada. Populasi yang digunakan untuk contoh ini adalah 10.

Hasil

Seperti dapat dilihat pada Tabel 4, kompleksitas pendekatan Algoritma Genetika meningkat secara nominal dengan jumlah kota.

Tabel 4 pendekatan algorima genetika

17. Ringkasan [Kembali]

Bab ini telah meletakkan dasar dasar untuk memahami algoritma genetika, terminologi dan operator mereka. Bab ini telah menyajikan operasi algoritma genetika sederhana yang rinci. Algoritma genetika beroperasi pada populasi string, dengan string dikodekan untuk mewakili kumpulan parameter yang mendasarinya.

=> LinkDownload HTML : Klik Disini

TEKNIK ELEKTRO UNIVERSITAS ANDALAS

MENU

BAB 3

Tidak ada komentar:

Posting Komentar