Pada bab sebelumnya sudah dibahas mengenai operasi genetik sederhana; reproduksi, persilangan dan mutasi. Pada bab ini kita akan membahas mengenai proses lebih lanjut yang mana dapat mengembangkan algoritma genetika sederhana. Operasi tingkat rendah seperti dominance, inversion, recording, deletion, segregation, dan diploidy akan dibahas dalam bab ini. Operasi tingkat rendah seperti Niche dan speciation juga akan dibahas.
4.2 Diploid, Dominansi, dan Penundaan [Kembali]
4.2 Diploid, Dominansi, dan Penundaan [Kembali]
Pada saat sekarang, kita hanya tahu mengenai genotipe tersimpel yaitu haploid atau kromosom tunggal. Namun, alam juga mengkonstruksi genotipe yang lebih kompleks yang sering disebut dengan diploid atau kromosom ganda. Dalam diploid, sebuah genotipe membawa 2 atau lebih pasangan kromosom yang membawa masing-masing informasi untuk fungsi yang sama. Huruf besar dianggap alel dominan dan huruf kecil dianggap alel alternatif.
Masing-masing allel merepresentasikan bentuk gen, seperti Q artinya gen rambut pirang dan q artinya rambut hitam. Ini dapat memicu permasalahan pada gen haploid. Ada kemungkinan fenotip tidak memiliki rambut pirang dan hitam secara bersamaan.
Untuk mencegah hal tersebut, maka ada proses eliminasi yang disebut dengan dominansi. Dalam proses ini, alel dominan akan mengeleminasi alel alternatif sehingga menghasilkan fenotipe yang baru.
Seperti pada gambar, gen dominan akan mendominasi gen resesif dan gen resesif hanya akan muncul jika tidak ada gen dominan dalam 2 kromosom.
Dominansi dan diploid dapat diimplementasikan dalam algoritma genetika. Kita anggap:
- 0 sebagai kode gen nol
- 1 sebagai kode gen resesif dari 1
- 2 sebagai kode gen dominan dari 1
maka jika dimasukkan dalam tabel :
Algoritma genetika multiploid menggabungkan beberapa kandidat untuk setiap gen dalam genotipe tunggal, dan menggunakan beberapa bentuk mekanisme dominasi untuk menentukan pilihan masing-masing gen yang aktif dalam fenotipe. Seperti contoh berikut, sebuah genotipe multiploid mengandung p kromosom, masing-masing panjang L, dan topeng yang menentukan kromosom p memiliki gen dominan pada posisi tertentu di kromosom.
Nilai alel pada lokus i dalam topeng menandakan bahwa gen in di kromosom dengan indeks a menjadi gen of dari fenotipe. Panjang topeng bisa lebih pendek dari panjang kromosom.
Inversi adalah penataan kembali operator genetik. Algoritma genetika sederhana menggunakan pemilihan stokastik, crossover 1 titik, dan mutasi untuk meningkatkan jumlah blok bangunan dalam populasi dan menggabungkannya kembali untuk blok bangunan yang lebih baik.
Operator inversi adalah mekanisme alami utama untuk mengulangi sebuah masalah. Dalam operator inversi, dua titik dipilih sepanjang panjang kromosom, kromosom dipotong pada titik-titik tersebut dan titik akhir potongan bagian, dibalik (diganti, ditukar).
ketika ada operasi inversi, stringnya menjadi:
Jadi dalam titik-titik inversi yang ditentukan, peralihan antara kromosom terjadi. Operator inversi juga dapat digunakan untuk representasi diperpanjang seperti yang diberikan oleh,
Bagian-bagian yang diinversikan diambil secara random, maka hasilnya:
Algoritma dasar untuk inversi dapat dibuat seperti ini:
Dengan demikian indeks diperlukan untuk setiap lokus untuk mempertahankan makna lokus independen posisinya pada kromosom. Pembalikan berlebihan dengan operator seperti UX (Uniform Crossover), yang tidak memiliki bias posisional.
Fitur inversi dan cross-over digabungkan bersama untuk menghasilkan satu operator tunggal, yang mengarah pada pengembangan operator pemesanan ulang lainnya. Bentuk-bentuknya adalah:
1. Partially Matched Crossover (PMX)
2. Order Crossover (OX)
3. Cycle Crossover (CX)
4.4.1 Partially Matched Crossover (PMX)
Dalam Crossover Sebagian Cocok, dua string sejajar, dan dua titik crossover dipilih secara acak seragam sepanjang string. Dua titik crossover memberikan pemilihan yang sesuai, yang digunakan untuk mempengaruhi operasi pertukaran posisi melalui posisi-posisi.
Jika dimisalkan 2 kondisi :
Dua crossoverpoint dipilih secara acak, dan PMX melanjutkan dengan pertukaran posisi. Di antara titik-titik silang, gen ditukarkan yaitu, 3 dan 2, 6 dan 7, 5 dan 9 tempat pertukaran. Ini dengan memetakan induk B ke parent A. Sekarang memetakan parent A ke parent B, 7 dan 6, 9 dan 5, 2 dan 3 tempat pertukaran. Jadi :
Yang mana masing-masing keturunan mengandung bagian informasi dari masing-masing orangtua.
4.4.2 Order Crossover (OX)
OX memulai proses crossover sama dengan PMX. Namun OX menerapkan gerakan geser untuk mengisi meninggalkan lubang dengan memindahkan posisi yang dipetakan.
contoh :
Saat memetakan parent B dengan A, kromosom 3,5,6 kita ubah menjadi holes
Lubang-lubang ini sekarang diisi dengan gerakan geser yang dimulai dengan yang kedua
titik crossover.
Lubang-lubang tersebut kemudian diisi dengan bagian yang cocok diambil dari induk A. Dengan demikian melakukan operasi ini, keturunan yang diproduksi menggunakan perintah crossover adalah seperti yang diberikan di bawah.
4.4.3 Cycle Crossover (CX)
Cycle Crossover berbeda dari PMX dan OX. Siklus melakukan rekombinasi
di bawah batasan bahwa setiap gen berasal dari orang tua atau yang lain.
4.5. Niche and Speciation [Kembali]
Masalah abadi dengan Genetic Algorithm adalah konvergensi prematur, yaitu genotipe yang tidak optimal mengambil alih populasi yang menghasilkan setiap individu menjadi identik atau sangat mirip, konsekuensinya adalah populasi yang tidak mengandung keragaman genetik yang cukup untuk berevolusi lebih lanjut. Cukup meningkatkan ukuran populasi mungkin tidak cukup untuk menghindari masalah, sementara setiap peningkatan ukuran populasi akan dikenakan biaya dua kali lipat dari kedua perhitungan ekstra waktu dan lebih banyak generasi untuk berkumpul pada solusi optimal. Genetic Algorithm lalu, menghadapi masalah yang sulit. Bagaimana populasi bisa didorong
untuk mencari solusi sementara tetap mempertahankan keberagaman? Jelas, itu operator, yang menyebabkan konvergensi, yaitu crossover dan reproduksi, harus diubah entah bagaimana.
Masalah lain yang sering digunakan sebagai kritik terhadap Algoritma Genetika adalah waktunya terlibat dalam mendapatkan solusi. Tidak seperti metode deterministik lainnya seperti Neural Jaringan, pendakian bukit, metode berbasis aturan, dll., Algoritma Genetika mengandung suatu tingkat keacakan yang besar dan tidak ada jaminan untuk berkumpul pada solusi dalam suatu
waktu tetap. Bukan hal yang luar biasa untuk sebagian besar berjalan tidak menemukan yang optimal
larutan. Untungnya, karena sifatnya, Algoritma Genetika secara inheren sejajar, yaitu individu dapat dievaluasi secara paralel karena kinerja mereka jarang, jika ada, mempengaruhi dari individu lain. Fase reproduksi, bagaimanapun, yang biasanya melibatkan seksual gratis untuk semua, selama mana orang-orang dari populasi panah tentang dalam hiruk-pikuk gila berlomba-lomba satu sama lain dalam upaya untuk kawin sesering mungkin, merupakan hambatan serius dalam Algoritma Genetika tradisional. Kebugaran setiap individu harus diketahui, dan, meskipun sangat besar dan tidak diragukan lagi semangat sabar hadir dalam populasi, hanya satu reproduksi / crossover mungkin berlangsung pada suatu waktu. Suatu metode yang bisa menghindari kemacetan semacam ini akan meminjamkan itu sendiri sangat baik untuk implementasi pada mesin paralel, dan karenanya mempercepat seluruh proses.
4.5.1 Niche dan Spesiasi dalam Masalah Multimodal
Misalkan fungsi kebugaran multimodal yaitu beberapa puncak GA akan cenderung menyatu ke salah satu puncak, terutama jika salah satu puncak lebih pas daripada yang lain. Mungkin, seseorang suka mengidentifikasi puncak konvergensi ke beberapa puncak secara bersamaan. Sebuah 'ceruk' dapat dianggap sebagai salah satu puncak dan 'spesies' adalah koleksi anggota populasi sangat cocok untuk niche tertentu. Kami mungkin menginginkan GA untuk menciptakan subpopulasi yang stabil (spesies) yang cocok ke ceruk pasar. Pertimbangkan contoh mesin slot dua-tangan, jika satu orang bermain mesin slot dua-bersenjata, ia akan mencoba setiap lengan untuk sementara waktu untuk melihat yang memiliki hasil lebih besar dan kemudian memainkan lengan itu untuk sisa waktu. Dalam hal ini, dimungkinkan untuk memperoleh rumus untuk berapa banyak yang harus dimainkan di setiap lengan sebelum memilih lengan mana yang akan dimainkan sisa waktu untuk hasil keseluruhan optimal. Sekarang anggaplah bahwa sekelompok orang semuanya memainkan mesin slot dua-bersenjata yang sama dan kelompok yang memainkan lengan, orang harus berbagi kemenangan mereka dan juga untuk lengan juga. Para pemain diperbolehkan untuk berpindah grup untuk meningkatkan bagian mereka. Jika M orang bermain total,
Hal yang serupa dengan ini dapat diterapkan di GA selama ‘crowding’ dan ‘sharing’ teknik seperti yang dibahas di bawah ini. Algoritma Genetika menggunakan panmictic diterapkan ke fungsi multimodal menghadapi dua masalah utama, yang pertama adalah bahwa mendistribusikan individu secara merata di semua puncak dalam solusi:
Setiap puncak dalam lanskap solusi dapat dilihat sebagai lingkungan yang terpisah ceruk. Penerapan suatu algoritma genetika yang sukses untuk masalah seperti ini harus menghasilkan beberapa individu yang tersebar di setiap ceruk lingkungan. Cara apa yang lebih baik untuk melakukan ini selain untuk mengizinkan evolusi beberapa spesies dalam lingkungan, masing-masing mengkhususkan diri dalam ceruk khusus sendiri? Menggunakan ceruk dan spesies dalam aplikasi seperti ini dapat meminjamkan yang lebih biologis artinya bagi spesies kata. Masalah kedua sekarang muncul sebagai orang tua yang berbeda spesies, yaitu dari ceruk lingkungan yang berbeda cenderung menghasilkan anak-anak yang tidak layak, jadi orang tua yang menempati ceruk yang berbeda harus berkecil hati untuk kawin.
4.5.1.1 Crowding
Masalah pertama diatasi oleh [DeJong 75] untuk mencegah satu genotipe dari mendominasi suatu populasi. Dengan memastikan bahwa individu yang baru lahir akan menggantikannya bahwa itu adalah sekutu genotip yang mirip dengannya, Crowding berusaha mempertahankan populasi yang seimbang. Mekanisme penggantian ini cukup sederhana: satu memilih CF secara acak individu dan, melalui perhitungan jarak hamming, memutuskan yang cocok korban.
Keuntungan Crowding adalah bagaimana beberapa individu harus diperiksa kapan memilih korban, karena CF biasanya 2 atau 3. Penggantian orang yang sama ini bertindak untuk mencegah satu genotipe mengambil alih populasi sepenuhnya, memungkinkan relung lainnya yang mungkin kurang cocok untuk terbentuk dalam populasi utama. Gagak tidak secara eksplisit menciptakan ceruk, juga tidak membuat konsentrasi upaya untuk mendorong mereka, tetapi memungkinkan mereka untuk terbentuk.
4.5.1.2 Sharing
Suatu pendekatan yang agak berbeda diadopsi dalam skema Berbagi, dalam individu-individu itu dalam suatu populasi yang menggunakan Berbagi menghadapi sumber daya terbatas sebagaimana yang mereka perjuangkan kebugaran. Untuk membuat hidup lebih sulit bagi mereka, individu dari lingkungan ceruk yang sama, dalam hal ini sekutu genotip serupa, lebih cenderung mencari tempat yang sama untuk sumber daya, sehingga memiliki waktu yang lebih sulit daripada individu yang unik. Dalam cara yang mirip dengan Crowding, dominasi populasi oleh genotipe tunggal tidak dianjurkan oleh hukuman individu yang terlalu mirip dengan orang besar bagian dari populasi.
Sharing, bagaimanapun, tidak sesederhana untuk menghitung sebagai Crowding, dan itu sangat spesifik-masalah seperti yang harus diketahui sebelumnya berapa banyak puncak yang ada di dalam lanskap solusi. Berbagi memang mendorong pembentukan ceruk dan, untuk mencegah prospek buruk individu dari berbagai ceruk,
Jika dimisalkan 2 kondisi :
Dua crossoverpoint dipilih secara acak, dan PMX melanjutkan dengan pertukaran posisi. Di antara titik-titik silang, gen ditukarkan yaitu, 3 dan 2, 6 dan 7, 5 dan 9 tempat pertukaran. Ini dengan memetakan induk B ke parent A. Sekarang memetakan parent A ke parent B, 7 dan 6, 9 dan 5, 2 dan 3 tempat pertukaran. Jadi :
Yang mana masing-masing keturunan mengandung bagian informasi dari masing-masing orangtua.
4.4.2 Order Crossover (OX)
Masalah abadi dengan Genetic Algorithm adalah konvergensi prematur, yaitu genotipe yang tidak optimal mengambil alih populasi yang menghasilkan setiap individu menjadi identik atau sangat mirip, konsekuensinya adalah populasi yang tidak mengandung keragaman genetik yang cukup untuk berevolusi lebih lanjut. Cukup meningkatkan ukuran populasi mungkin tidak cukup untuk menghindari masalah, sementara setiap peningkatan ukuran populasi akan dikenakan biaya dua kali lipat dari kedua perhitungan ekstra waktu dan lebih banyak generasi untuk berkumpul pada solusi optimal. Genetic Algorithm lalu, menghadapi masalah yang sulit. Bagaimana populasi bisa didorong
untuk mencari solusi sementara tetap mempertahankan keberagaman? Jelas, itu operator, yang menyebabkan konvergensi, yaitu crossover dan reproduksi, harus diubah entah bagaimana.
Masalah lain yang sering digunakan sebagai kritik terhadap Algoritma Genetika adalah waktunya terlibat dalam mendapatkan solusi. Tidak seperti metode deterministik lainnya seperti Neural Jaringan, pendakian bukit, metode berbasis aturan, dll., Algoritma Genetika mengandung suatu tingkat keacakan yang besar dan tidak ada jaminan untuk berkumpul pada solusi dalam suatu
waktu tetap. Bukan hal yang luar biasa untuk sebagian besar berjalan tidak menemukan yang optimal
larutan. Untungnya, karena sifatnya, Algoritma Genetika secara inheren sejajar, yaitu individu dapat dievaluasi secara paralel karena kinerja mereka jarang, jika ada, mempengaruhi dari individu lain. Fase reproduksi, bagaimanapun, yang biasanya melibatkan seksual gratis untuk semua, selama mana orang-orang dari populasi panah tentang dalam hiruk-pikuk gila berlomba-lomba satu sama lain dalam upaya untuk kawin sesering mungkin, merupakan hambatan serius dalam Algoritma Genetika tradisional. Kebugaran setiap individu harus diketahui, dan, meskipun sangat besar dan tidak diragukan lagi semangat sabar hadir dalam populasi, hanya satu reproduksi / crossover mungkin berlangsung pada suatu waktu. Suatu metode yang bisa menghindari kemacetan semacam ini akan meminjamkan itu sendiri sangat baik untuk implementasi pada mesin paralel, dan karenanya mempercepat seluruh proses.
4.5.1 Niche dan Spesiasi dalam Masalah Multimodal
Misalkan fungsi kebugaran multimodal yaitu beberapa puncak GA akan cenderung menyatu ke salah satu puncak, terutama jika salah satu puncak lebih pas daripada yang lain. Mungkin, seseorang suka mengidentifikasi puncak konvergensi ke beberapa puncak secara bersamaan. Sebuah 'ceruk' dapat dianggap sebagai salah satu puncak dan 'spesies' adalah koleksi anggota populasi sangat cocok untuk niche tertentu. Kami mungkin menginginkan GA untuk menciptakan subpopulasi yang stabil (spesies) yang cocok ke ceruk pasar. Pertimbangkan contoh mesin slot dua-tangan, jika satu orang bermain mesin slot dua-bersenjata, ia akan mencoba setiap lengan untuk sementara waktu untuk melihat yang memiliki hasil lebih besar dan kemudian memainkan lengan itu untuk sisa waktu. Dalam hal ini, dimungkinkan untuk memperoleh rumus untuk berapa banyak yang harus dimainkan di setiap lengan sebelum memilih lengan mana yang akan dimainkan sisa waktu untuk hasil keseluruhan optimal. Sekarang anggaplah bahwa sekelompok orang semuanya memainkan mesin slot dua-bersenjata yang sama dan kelompok yang memainkan lengan, orang harus berbagi kemenangan mereka dan juga untuk lengan juga. Para pemain diperbolehkan untuk berpindah grup untuk meningkatkan bagian mereka. Jika M orang bermain total,
Hal yang serupa dengan ini dapat diterapkan di GA selama ‘crowding’ dan ‘sharing’ teknik seperti yang dibahas di bawah ini. Algoritma Genetika menggunakan panmictic diterapkan ke fungsi multimodal menghadapi dua masalah utama, yang pertama adalah bahwa mendistribusikan individu secara merata di semua puncak dalam solusi:
Setiap puncak dalam lanskap solusi dapat dilihat sebagai lingkungan yang terpisah ceruk. Penerapan suatu algoritma genetika yang sukses untuk masalah seperti ini harus menghasilkan beberapa individu yang tersebar di setiap ceruk lingkungan. Cara apa yang lebih baik untuk melakukan ini selain untuk mengizinkan evolusi beberapa spesies dalam lingkungan, masing-masing mengkhususkan diri dalam ceruk khusus sendiri? Menggunakan ceruk dan spesies dalam aplikasi seperti ini dapat meminjamkan yang lebih biologis artinya bagi spesies kata. Masalah kedua sekarang muncul sebagai orang tua yang berbeda spesies, yaitu dari ceruk lingkungan yang berbeda cenderung menghasilkan anak-anak yang tidak layak, jadi orang tua yang menempati ceruk yang berbeda harus berkecil hati untuk kawin.
4.5.1.1 Crowding
Masalah pertama diatasi oleh [DeJong 75] untuk mencegah satu genotipe dari mendominasi suatu populasi. Dengan memastikan bahwa individu yang baru lahir akan menggantikannya bahwa itu adalah sekutu genotip yang mirip dengannya, Crowding berusaha mempertahankan populasi yang seimbang. Mekanisme penggantian ini cukup sederhana: satu memilih CF secara acak individu dan, melalui perhitungan jarak hamming, memutuskan yang cocok korban.
Keuntungan Crowding adalah bagaimana beberapa individu harus diperiksa kapan memilih korban, karena CF biasanya 2 atau 3. Penggantian orang yang sama ini bertindak untuk mencegah satu genotipe mengambil alih populasi sepenuhnya, memungkinkan relung lainnya yang mungkin kurang cocok untuk terbentuk dalam populasi utama. Gagak tidak secara eksplisit menciptakan ceruk, juga tidak membuat konsentrasi upaya untuk mendorong mereka, tetapi memungkinkan mereka untuk terbentuk.
4.5.1.2 Sharing
Suatu pendekatan yang agak berbeda diadopsi dalam skema Berbagi, dalam individu-individu itu dalam suatu populasi yang menggunakan Berbagi menghadapi sumber daya terbatas sebagaimana yang mereka perjuangkan kebugaran. Untuk membuat hidup lebih sulit bagi mereka, individu dari lingkungan ceruk yang sama, dalam hal ini sekutu genotip serupa, lebih cenderung mencari tempat yang sama untuk sumber daya, sehingga memiliki waktu yang lebih sulit daripada individu yang unik. Dalam cara yang mirip dengan Crowding, dominasi populasi oleh genotipe tunggal tidak dianjurkan oleh hukuman individu yang terlalu mirip dengan orang besar bagian dari populasi.
Sharing, bagaimanapun, tidak sesederhana untuk menghitung sebagai Crowding, dan itu sangat spesifik-masalah seperti yang harus diketahui sebelumnya berapa banyak puncak yang ada di dalam lanskap solusi. Berbagi memang mendorong pembentukan ceruk dan, untuk mencegah prospek buruk individu dari berbagai ceruk,
4.5.2 Niche and Speciation in Unimodal Problems
Penggunaan ceruk dalam masalah multimodal adalah pemetaan yang sangat sederhana, dengan evolusi dari spesies yang berbeda untuk setiap puncak di lanskap solusi. Pemetaan itu tidak begitu mudah dalam masalah unimodal yang biasanya hanya berisi satu puncak, atau pada paling tidak mengandung satu puncak lebih tinggi dari yang lain.
Semua pendekatan untuk masalah unimodal, melibatkan niching, berusaha untuk mempertahankan populasi yang seimbang, baik melalui perkawinan terbatas untuk mencegah perkawinan yang tidak pantas atau melalui metode penggantian yang menghambat pengambilalihan populasi dengan genotipe tunggal.
4.5.2.1 Pencegahan Incest
Ketika populasi berevolusi, individu-individu menjadi lebih dan lebih mirip, sehingga itu menjadi lebih sulit untuk menemukan orang tua yang cocok. Untuk menghindari situasi di mana ada tidak ada orang tua seperti itu dalam suatu populasi, ada perbedaan ambang batas yang ditetapkan, yang bisa rileks jika ada kesulitan dalam memilih orang tua. Diasumsikan kesulitan itu akan muncul jika tidak ada perubahan dalam populasi orang tua, dan, sebagai pencegahan inses digunakan dengan elitisme, yaitu daftar orang tua yang dipertahankan hanya dapat dilakukan oleh individu masukkan jika kebugaran mereka cukup tinggi, itu adalah masalah sepele untuk melacak perubahan apa pun.
Sekali lagi, spesies yang berbeda tidak secara eksplisit dibuat, dan tidak dijamin untuk muncul, tetapi jika mereka melakukannya, pencegahan Incest mendorong perkawinan antar spesies, sebagai lanskap kebugaran dalam fungsi cenderung unimodal.
Untuk program:
SET THRESHOLD
REPEAT
FOR EACH INDIVIDUAL DO
TEST INDIVIDUAL
ENTER PARENT POPULATION
IF NO-NEW-PARENTS THEN LOWER THRESHOLD
FOR EACH INDIVIDUAL DO
REPEAT
SELECT PARENTS
UNTIL DIFFERENT ( )
UNTIL END-CRITERION REACHED OR THRESHOLD=0
4.5.2.2 The Pygmy Algorithm
Algoritma Pygmy biasanya digunakan pada masalah dengan dua atau lebih persyaratan, misalnya evolusi solusi yang perlu efisien dan singkat. Relung-relung digunakan dengan memiliki dua fungsi kebugaran yang terpisah, sehingga menciptakan dua spesies. Individu dari masing-masing spesies kemudian dipandang sebagai jenis kelamin berbeda, dan ketika orang tua dipilih untuk menciptakan individu baru, seseorang ditarik dari setiap spesies dengan tujuan setiap orang tua menggunakan tekanan dari kebugarannya fungsi.
Biasanya, ada satu fungsi kebugaran utama, katakanlah efisiensi, dan persyaratan sekunder seperti singkatnya. Individu yang sangat efisien kemudian akan memasuki yang pertama niche, sementara individu yang tidak cocok dengan niche ini menjalani kebugaran kedua tes, yang hanya fungsi kebugaran asli mereka dimodifikasi untuk menyertakan sekunder kebutuhan. Orang-orang ini kemudian mencoba untuk bergabung dengan ceruk kedua, dan kegagalan untuk mencapai hasil ini dalam kematian dini bagi individu yang bersangkutan.
REPEAT
FOR EACH INDIVIDUAL DO
TEST INDIVIDUAL WITH MAIN FITNESS FUNCTION
ENTER PARENT POPULATION #1
IF UNSUCCESSFUL
TEST INDIVIDUALWITH SECONDARY FITNESS FUNCTION
ENTER PARENT POPULATION #2
FOR EACH INDIVIDUAL DO
SELECT PARENT FROM POPULATION #1
SELECT PARENT FROM POPULATION #2
CREATE NEW INDIVIDUAL
UNTIL END-CRITERION REACHED
4.5.3 Kawin Terbatas
Tujuan perkawinan terbatas adalah untuk mendorong spesiasi, dan mengurangi produksi dari lethals. Yang mematikan adalah anak dari orang tua dari dua ceruk berbeda. Meskipun setiap orang tua mungkin sangat cocok, kombinasi kromosom mereka mungkin sangat tinggi tidak layak jika jatuh di lembah antara dua maxima. Alam menghindari formasi dari letal dengan mencegah perkawinan antara spesies yang berbeda, menggunakan berbagai teknik. (Sebenarnya, ini adalah definisi biologis utama dari suatu spesies - satu set individu yang dapat berkembang biak bersama untuk menghasilkan keturunan yang layak.)
Filosofi umum perkawinan terbatas membuat asumsi bahwa jika dua orang tua yang sama (yaitu, dari ceruk yang sama) dikawinkan, maka keturunannya akan menjadi serupa. Namun, ini sangat tergantung pada skema pengkodean-khususnya keberadaan blok bangunan, dan epistasis yang rendah. Di bawah crossover konvensional dan operator mutasi, dua orang tua dengan genotipe serupa akan selalu menghasilkan keturunan dengan genotipe serupa.
4.6 Few Micro-operators [Kembali]
Biasanya, ada satu fungsi kebugaran utama, katakanlah efisiensi, dan persyaratan sekunder seperti singkatnya. Individu yang sangat efisien kemudian akan memasuki yang pertama niche, sementara individu yang tidak cocok dengan niche ini menjalani kebugaran kedua tes, yang hanya fungsi kebugaran asli mereka dimodifikasi untuk menyertakan sekunder kebutuhan. Orang-orang ini kemudian mencoba untuk bergabung dengan ceruk kedua, dan kegagalan untuk mencapai hasil ini dalam kematian dini bagi individu yang bersangkutan.
REPEAT
FOR EACH INDIVIDUAL DO
TEST INDIVIDUAL WITH MAIN FITNESS FUNCTION
ENTER PARENT POPULATION #1
IF UNSUCCESSFUL
TEST INDIVIDUALWITH SECONDARY FITNESS FUNCTION
ENTER PARENT POPULATION #2
FOR EACH INDIVIDUAL DO
SELECT PARENT FROM POPULATION #1
SELECT PARENT FROM POPULATION #2
CREATE NEW INDIVIDUAL
UNTIL END-CRITERION REACHED
4.5.3 Kawin Terbatas
Tujuan perkawinan terbatas adalah untuk mendorong spesiasi, dan mengurangi produksi dari lethals. Yang mematikan adalah anak dari orang tua dari dua ceruk berbeda. Meskipun setiap orang tua mungkin sangat cocok, kombinasi kromosom mereka mungkin sangat tinggi tidak layak jika jatuh di lembah antara dua maxima. Alam menghindari formasi dari letal dengan mencegah perkawinan antara spesies yang berbeda, menggunakan berbagai teknik. (Sebenarnya, ini adalah definisi biologis utama dari suatu spesies - satu set individu yang dapat berkembang biak bersama untuk menghasilkan keturunan yang layak.)
Filosofi umum perkawinan terbatas membuat asumsi bahwa jika dua orang tua yang sama (yaitu, dari ceruk yang sama) dikawinkan, maka keturunannya akan menjadi serupa. Namun, ini sangat tergantung pada skema pengkodean-khususnya keberadaan blok bangunan, dan epistasis yang rendah. Di bawah crossover konvensional dan operator mutasi, dua orang tua dengan genotipe serupa akan selalu menghasilkan keturunan dengan genotipe serupa.
4.6 Few Micro-operators [Kembali]
4.6.1 Segregation and Translocation
Berdasarkan proses pembentukan gamet ketika ada lebih dari satu kromosom pasangan dalam genotip.Crossover terjadi seperti yang dibahas dalam bab sebelumnya dan kapan untuk membentuk gamet, kami secara acak memilih salah satu dari masing-masing kromosom haploid. Ini proses pemilihan acak disebut sebagai segregasi yang mengganggu setiap penautan, yang mungkin ada di antara gen pada kromosom yang berbeda. Ditemukan bahwa segregasi mengeksploitasi organisasi yang tepat dari kromosom dan penting untuk dicatat itu bagaimana kromosom menjadi terorganisir dengan cara yang tepat. Untuk ini tujuan, operator translokasi digunakan. Operator translokasi dapat dipertimbangkan sebagai operator crossover interchromosomal. Operator ini dapat diimplementasikan oleh menghubungkan alel dengan nama gen mereka, sehingga seseorang dapat mengidentifikasi tujuan mereka artinya ketika mereka dikocok dari kromosom ke kromosom oleh translokasi operator.
4.6.2 Duplication and Deletion
Ada juga sepasang operator tingkat rendah untuk melakukan pencarian algoritma genetika. Duplikasi intrachromosom dilakukan dengan menduplikasi gen tertentu dan menempatkan bersama dengan leluhurnya pada kromosom. Penghapusan berfungsi dengan menghapus gen a duplikat dari kromosom. Tingkat mutasi dapat dikendalikan secara efektif oleh operator ini. Ketika tingkat mutasi tetap konstan dan intrachromosomal duplikasi menyebabkan salinan ‘k’ dari gen tertentu, maka kemungkinan mutasi yang efektif untuk gen ini dikalikan dengan ‘k’. Di sisi lain, ketika penghapusan terjadi, tingkat mutasi efektif menurun.
4.6.3 Sexual Determination
Awalnya dalam skema perkawinan, kami mengizinkan setiap individu untuk kawin dengan siapa pun lainnya, dan produk genetik yang dihasilkan dibagi sehingga mereka telah memastikan genotipe a yang layak. Penentuan jenis kelamin ditangani secara berbeda pada spesies yang berbeda, tetapi contoh manusia cukup untuk memahami penentuan seksual. Jenis kelamin ditentukan pada manusia oleh salah satu dari 23 pasang kromosom manusia. Betina memiliki dua kromosom X dan X yang sama dan laki-laki memiliki dua kromosom X dan Y yang berbeda. Selama proses gametogenesis, laki-laki membentuk sperma (yang membawa baik X atau Y kromosom) dan betina memiliki telur (yang hanya membawa kromosom X). Pada pemupukan, kromosom X yang dihasilkan oleh wanita dikombinasikan dengan X atau Y-kromosom diproduksi oleh wanita. Demikianlah metode penentuan jenis kelamin pada manusia sederhana. Menerapkan strategi yang sama untuk penentuan jenis kelamin dalam pencarian GA. Pembentukan perbedaan jenis kelamin secara efektif membagi spesies menjadi dua atau lebih kelompok. Hal ini memungkinkan pria dan wanita untuk mengkhususkan, dengan demikian melampirkan jangkauan perilaku yang diperlukan untuk bertahan hidup secara lebih luas daripada dengan satu pesaing populasi. Penelitian di bawah penentuan jenis kelamin dan perbedaan untuk buatan pencarian algoritma genetika masih berlangsung.
4.7 Non-binary Representation [Kembali]
Sebuah kromosom adalah rangkaian simbol, dan, secara tradisional, simbol-simbol ini telah ada digit biner, sehingga setiap simbol memiliki kardinalitas 2. Huruf kardinalitas lebih tinggi telah digunakan dalam beberapa penelitian, dan beberapa percaya bahwa mereka memiliki kelebihan. Goldberg berpendapat bahwa secara teoritis, representasi biner memberikan jumlah terbesar schemata, dan karenanya memberikan tingkat tertinggi paralelisme implisit. Tapi Antonisse menafsirkan schemata berbeda, dan menyimpulkan bahwa, sebaliknya, kardinalitas tinggi abjad berisi lebih banyak schemata daripada yang biner.
Goldberg kini telah mengembangkan teori, yang menjelaskan mengapa representasi kardinalitas tinggi dapat berkinerja baik. Teorinya tentang abjad virtual mengatakan bahwa setiap simbol menyatu dalam beberapa generasi pertama, hanya menyisakan sejumlah kecil kemungkinan nilai-nilai. Dengan cara ini, setiap simbol secara efektif hanya memiliki kardinalitas rendah. Empiris studi dari huruf kardinalitas tinggi biasanya menggunakan kromosom di mana masing-masing simbol mewakili integer, atau angka floating-point. Sebagaimana Davis tunjukkan, masalah parameter sering numerik, jadi mewakili mereka secara langsung sebagai angka, bukan dari bit-string, tampak jelas, dan mungkin memiliki kelebihan. Satu keuntungannya adalah kita dapat lebih mudah mendefinisikan operator crossover dan mutasi yang berarti dan spesifik.
Masalah optimasi multi-tujuan telah menerima penelitian bentuk minat sejakawal 1960-an. Dalam masalah optimasi multi-tujuan, beberapa fungsi obyektifperlu dioptimalkan secara bersamaan. Dalam kasus berbagai tujuan, memang adabelum tentu ada solusi yang terbaik sehubungan dengan semua tujuan karenadiferensiasi antara tujuan. Suatu solusi mungkin yang terbaik dalam satu tujuan tetapi yang terburuk di tempat lain. Oleh karena itu, biasanya ada seperangkat solusi untuk tujuan ganda kasus, yang tidak bisa dibandingkan satu sama lain. Untuk solusi seperti itu, yang disebut Solusi optimal pareto atau solusi non-didominasi, tidak ada peningkatan yang mungkin dalam fungsi obyektif apa pun tanpa mengorbankan setidaknya satu dari tujuan lainnya fungsi.
Optimasi kombinatorial mengandung banyak masalah dengan fitur yang berbeda dan properti. Meskipun masalah ini sangat berbeda satu sama lain, masalah dapat dicirikan sebagai salah satu dari jenis berikut:
• Untuk menentukan permutasi beberapa item yang terkait dengan masalah.
• Untuk menentukan kombinasi beberapa item.
• Untuk menentukan permutasi dan kombinasi beberapa item.
• Salah satu subjek di atas mengalami kendala.
Inti dari masalah penjadwalan proyek yang dibatasi sumber daya dan perutean kendaraan dan masalah penjadwalan adalah untuk menentukan permutasi dari beberapa item yang tunduk beberapa kendala. Inti dari masalah penjadwalan mesin paralel adalah untuk menentukan baik permutasi dan kombinasi item tunduk pada batasan tertentu.
Ciri umum masalah adalah jika permutasi dan / atau kombinasi bisa ditentukan, solusi kemudian dapat dengan mudah diturunkan dengan prosedur khusus masalah. Jadi pendekatan umum untuk menerapkan algoritma genetika untuk masalah ini adalah sebagai berikut:
• Gunakan algoritma genetika untuk mengembangkan permutasi dan / atau kombinasi yang tepat
barang yang sedang dipertimbangkan.
• Kemudian gunakan pendekatan heuristik untuk membangun solusi sesuai dengan permutasi
dan kombinasi.
Sementara sebagian besar penelitian telah pergi ke GAs menggunakan crossover dan mutasi tradisional operator, beberapa telah menganjurkan merancang operator baru untuk setiap tugas, menggunakan pengetahuan domain. Ini membuat setiap GA lebih banyak tugas spesifik (kurang kuat), tetapi mungkin meningkatkan kinerja secara signifikan. Di mana GA sedang dirancang untuk menangani dunia nyata masalah, dan harus bersaing dengan teknik penelusuran dan pengoptimalan lainnya, penggabungan pengetahuan domain sering masuk akal. Beberapa peneliti berpendapat bahwa pengetahuan khusus masalah dapat berguna dimasukkan ke dalam operasi crossover. Pengetahuan domain dapat digunakan untuk mencegah kromosom yang jelas tidak benar, atau yang akan melanggar batasan masalah, dari yang pertama diproduksi tempat. Ini menghindari membuang waktu mengevaluasi orang-orang seperti itu, dan menghindari perkenalan pemain miskin ke dalam populasi.
Dalam skema hybrid, GAs digunakan untuk mendekati nilai optimal, kemudian konvensional skema optimasi seperti pencarian serakah, pencarian gradien atau pendakian bukit stochastic dapat digunakan untuk menjadi lebih dekat dengan nilai optimal. Algoritma genetika mungkin juga mengembangkan spesies untuk masing-masing yang dapat diterapkan optimasi konvensional. Di gradien seperti bitwise (G-bit) peningkatan untuk satu atau lebih kromosom yang sangat sesuai, ubah setiap bit satu per satu untuk melihat apakah kebugarannya membaik, jika demikian, ganti yang asli dengan kromosom yang berubah. Juga mengubah pasangan atau kembar tiga bit dapat dicoba tetapi dalam ledakan kombinatorial. Skema hibrida dapat diwakili dengan gambar berikut :
Sebuah kromosom adalah rangkaian simbol, dan, secara tradisional, simbol-simbol ini telah ada digit biner, sehingga setiap simbol memiliki kardinalitas 2. Huruf kardinalitas lebih tinggi telah digunakan dalam beberapa penelitian, dan beberapa percaya bahwa mereka memiliki kelebihan. Goldberg berpendapat bahwa secara teoritis, representasi biner memberikan jumlah terbesar schemata, dan karenanya memberikan tingkat tertinggi paralelisme implisit. Tapi Antonisse menafsirkan schemata berbeda, dan menyimpulkan bahwa, sebaliknya, kardinalitas tinggi abjad berisi lebih banyak schemata daripada yang biner.
Goldberg kini telah mengembangkan teori, yang menjelaskan mengapa representasi kardinalitas tinggi dapat berkinerja baik. Teorinya tentang abjad virtual mengatakan bahwa setiap simbol menyatu dalam beberapa generasi pertama, hanya menyisakan sejumlah kecil kemungkinan nilai-nilai. Dengan cara ini, setiap simbol secara efektif hanya memiliki kardinalitas rendah. Empiris studi dari huruf kardinalitas tinggi biasanya menggunakan kromosom di mana masing-masing simbol mewakili integer, atau angka floating-point. Sebagaimana Davis tunjukkan, masalah parameter sering numerik, jadi mewakili mereka secara langsung sebagai angka, bukan dari bit-string, tampak jelas, dan mungkin memiliki kelebihan. Satu keuntungannya adalah kita dapat lebih mudah mendefinisikan operator crossover dan mutasi yang berarti dan spesifik.
Masalah optimasi multi-tujuan telah menerima penelitian bentuk minat sejakawal 1960-an. Dalam masalah optimasi multi-tujuan, beberapa fungsi obyektifperlu dioptimalkan secara bersamaan. Dalam kasus berbagai tujuan, memang adabelum tentu ada solusi yang terbaik sehubungan dengan semua tujuan karenadiferensiasi antara tujuan. Suatu solusi mungkin yang terbaik dalam satu tujuan tetapi yang terburuk di tempat lain. Oleh karena itu, biasanya ada seperangkat solusi untuk tujuan ganda kasus, yang tidak bisa dibandingkan satu sama lain. Untuk solusi seperti itu, yang disebut Solusi optimal pareto atau solusi non-didominasi, tidak ada peningkatan yang mungkin dalam fungsi obyektif apa pun tanpa mengorbankan setidaknya satu dari tujuan lainnya fungsi.
Optimasi kombinatorial mengandung banyak masalah dengan fitur yang berbeda dan properti. Meskipun masalah ini sangat berbeda satu sama lain, masalah dapat dicirikan sebagai salah satu dari jenis berikut:
• Untuk menentukan permutasi beberapa item yang terkait dengan masalah.
• Untuk menentukan kombinasi beberapa item.
• Untuk menentukan permutasi dan kombinasi beberapa item.
• Salah satu subjek di atas mengalami kendala.
Inti dari masalah penjadwalan proyek yang dibatasi sumber daya dan perutean kendaraan dan masalah penjadwalan adalah untuk menentukan permutasi dari beberapa item yang tunduk beberapa kendala. Inti dari masalah penjadwalan mesin paralel adalah untuk menentukan baik permutasi dan kombinasi item tunduk pada batasan tertentu.
Ciri umum masalah adalah jika permutasi dan / atau kombinasi bisa ditentukan, solusi kemudian dapat dengan mudah diturunkan dengan prosedur khusus masalah. Jadi pendekatan umum untuk menerapkan algoritma genetika untuk masalah ini adalah sebagai berikut:
• Gunakan algoritma genetika untuk mengembangkan permutasi dan / atau kombinasi yang tepat
barang yang sedang dipertimbangkan.
• Kemudian gunakan pendekatan heuristik untuk membangun solusi sesuai dengan permutasi
dan kombinasi.
Sementara sebagian besar penelitian telah pergi ke GAs menggunakan crossover dan mutasi tradisional operator, beberapa telah menganjurkan merancang operator baru untuk setiap tugas, menggunakan pengetahuan domain. Ini membuat setiap GA lebih banyak tugas spesifik (kurang kuat), tetapi mungkin meningkatkan kinerja secara signifikan. Di mana GA sedang dirancang untuk menangani dunia nyata masalah, dan harus bersaing dengan teknik penelusuran dan pengoptimalan lainnya, penggabungan pengetahuan domain sering masuk akal. Beberapa peneliti berpendapat bahwa pengetahuan khusus masalah dapat berguna dimasukkan ke dalam operasi crossover. Pengetahuan domain dapat digunakan untuk mencegah kromosom yang jelas tidak benar, atau yang akan melanggar batasan masalah, dari yang pertama diproduksi tempat. Ini menghindari membuang waktu mengevaluasi orang-orang seperti itu, dan menghindari perkenalan pemain miskin ke dalam populasi.
Dalam skema hybrid, GAs digunakan untuk mendekati nilai optimal, kemudian konvensional skema optimasi seperti pencarian serakah, pencarian gradien atau pendakian bukit stochastic dapat digunakan untuk menjadi lebih dekat dengan nilai optimal. Algoritma genetika mungkin juga mengembangkan spesies untuk masing-masing yang dapat diterapkan optimasi konvensional. Di gradien seperti bitwise (G-bit) peningkatan untuk satu atau lebih kromosom yang sangat sesuai, ubah setiap bit satu per satu untuk melihat apakah kebugarannya membaik, jika demikian, ganti yang asli dengan kromosom yang berubah. Juga mengubah pasangan atau kembar tiga bit dapat dicoba tetapi dalam ledakan kombinatorial. Skema hibrida dapat diwakili dengan gambar berikut :
No comments:
Post a Comment