4. Operator Lanjutan dan Teknik di Genetik Algoritma
4.1 Pendahuluan
Dalam bab sebelumnya kita telah berurusan dengan operator genetik sederhana: reproduksi, menyeberang dan mutasi. Dalam bab ini kita mempertimbangkan operator alam dan fenomena-ena untuk meningkatkan kekokohan algoritma genetika sederhana. Operator tingkat rendah seperti dominasi, inversi, rekaman, penghapusan, segregasi dan diploidy dis-degil di sini. Juga, operator-tingkat yang lebih tinggi seperti niche dan spesiasi yang diinduksi. optimasi multi-tujuan dan teknik berbasis pengetahuan juga dipertimbangkan untuk diskusi dalam bab ini.
4.2 Diploidy, Dominasi dan penundaan
Sampai sekarang, kami telah dianggap hanya genotipe yang paling sederhana yang ada di alam, kromosom haploid atau tunggal. Sebuah kromosom haploid hanya berisi satu set gen yaitu, satu alel untuk menempati setiap lokus. Sifat terdiri dari banyak organisme haploid, tetapi kebanyakan dari mereka cenderung bentuk kehidupan yang tidak rumit. Ketika alam ingin membangun kehidupan yang lebih kompleks atau hewan untuk mengandalkan, struktur kromosom mendasari-ing lebih kompleks diperlukan dan ini dicapai dengan diploid atau kromosom ganda. Dalam bentuk diploid, genotipe yang membawa satu atau lebih pasang kromosom, masing-masing berisi informasi untuk fungsi yang sama. Pertimbangkan struktur kromosom diploid mana huruf yang berbeda mewakili alel yang berbeda (nilai fungsi gen dif-ferent):
P q r s t
P Q R S t
Alel merupakan milik gen tertentu. Setiap lokus dari surat Repre-sents satu alel. Huruf besar dan huruf kecil yang disebutkan di atas mewakili alel alternatif di posisi itu. Awalnya, di alam masing-masing alel dapat mewakili sifat fenotipik berbeda. Misalnya Q dapat mewakili gen berambut abu-abu dan q mungkin gen berambut hitam. Pendekatan ini meskipun tidak banyak skema fromhaploid bervariasi, salah satu perbedaan adalah hidup. Saat ini, sepasang gen ada yang menjelaskan fungsi masing-masing; harus ada beberapa aspek untuk memutuskan mana dari dua nilai untuk memilih karena, misalnya, fenotip tidak mungkin memiliki keduanya berambut berambut hitam abu-abu pada saat yang sama.
Pendekatan dasar untuk menghilangkan konflik ini redundansi adalah melalui ge-netic disebut dominasi. Pada lokus, telah mencatat bahwa salah satu alel (disebut alel dominan) akan diutamakan di atas alel alternatif lain (disebut alel resesif). Dapat dikatakan, sebagai alel dominan jika dinyatakan ketika dipasangkan dengan beberapa alel lainnya. Mengekspresikan berarti kejadiannya di fenotip.
Dalam contoh di atas, jika diasumsikan bahwa semua huruf besar yang dominan dan semua huruf kecil yang resesif, fenotipe diungkapkan oleh contoh kromosom ditulis sebagai,
P q r S t
→ P Q R S t
p Q R S t
Gen dominan selalu diungkapkan pada setiap lokus dan gen resesif hanya diungkapkan ketika hadir sesuai dengan resesif lain. Gen dominan diekspresikan ketika heterozigot (campuran, Pp → P) atau homozigot (SS → S) dan gen resesif menyatakan hanya ketika homozigot (tt → t).
Setelah dominasi menyeberang, kromosom menjadi metode PQRST. Dengan demikian dominasi adalah operator genetik yang digunakan untuk menghitung fenotip alel nilai mungkin pada posisi gen, satu dominan dan yang lain resesif menyediakan mekanisme untuk mengingat materi genetik yang sebelumnya berguna dan untuk melindunginya dari menghilang itu diadakan di penundaan (ditangguhkan) telah belum ditemukan sangat berguna dalam genetik algoritma spekulasi. Ini dapat membantu jika lingkungan berubah dari waktu ke waktu yaitu, perubahan kebugaran atau perubahan kendala.
Dominasi dan diploidy dapat hanya diimplementasikan dalam algoritma genetika. Asumsikan 3 alel,
0: mengkode gen 0
1: resesif mengkode gen 1
2: dominan mengkode gen 1.
Di atas memberikan peta dominasi berikut (Gambar. 4.1).
Rasio fenotip untuk dominan dari 3-1 dicapai untuk alel pasangan 0 dengan 1, dan 0 dengan 2. Dominasi dapat berkembang melalui substitusi alel dari 1 untuk 2 dan sebaliknya.
0
1
2
0
0
0
1
1
0
1
1
2
1
1
1
Gambar. 4.1 Dominance map
kromosom diploid meminjamkan keuntungan kepada individu di mana lingkungan dapat berubah selama periode waktu. Memiliki dua gen memungkinkan dua solusi yang berbeda untuk diingat, dan diteruskan kepada keturunannya. Salah satunya akan dominan (yakni, yang akan dinyatakan dalam fenotip), sementara yang lain akan resesif. Jika kondisi lingkungan berubah, dominasi bisa bergeser, sehingga gen lainnya dominan. Pergeseran ini dapat berlangsung jauh lebih cepat daripada yang mungkin jika evolusi mekanisme-anisms harus mengubah gen. Mekanisme ini sangat ideal jika lingkungan secara teratur beralih antara dua negara (misalnya, es usia, non es usia). Keuntungan utama dari diploidy yang memungkinkan keragaman yang lebih luas dari alel untuk disimpan dalam populasi, dibandingkan dengan haploidy. Saat alel berbahaya, tetapi berpotensi berguna masih bisa dipertahankan, tetapi dalam posisi resesif. mekanisme genetik lainnya bisa mencapai efek yang sama. Misalnya, kromosom mungkin berisi beberapa varian gen. Epistasis (dalam arti masking) dapat digunakan untuk memastikan bahwa hanya salah satu varian dinyatakan dalam setiap individu tertentu. Situasi seperti ini terjadi dengan produksi hemoglobin. gen yang berbeda kode untuk produksi selama tahap-tahap perkembangan yang berbeda. Selama tahap janin, satu gen diaktifkan untuk memproduksi hemoglobin, sementara nanti gen yang berbeda diaktifkan. Ada berbagai metafora biologis dapat kita gunakan untuk menginspirasi pengembangan kami GAs.
Dalam GA, diploidy mungkin berguna dalam aplikasi on-line di mana sistem dapat beralih di antara negara-negara yang berbeda. Diploidy melibatkan overhead yang signifikan dalam GA. Serta membawa dua kali informasi genetik banyak, kromosom juga harus membawa informasi dominasi.
4.3 Multiploid
Sebuah algoritma genetika multiploid menggabungkan beberapa kandidat untuk setiap gen dalam genotipe tunggal, dan menggunakan beberapa bentuk mekanisme dominasi untuk menentukan pilihan masing-masing gen aktif dalam fenotip. Di alam kita menemukan bahwa banyak organ-isme memiliki genotipe poli-ploid, yang terdiri dari beberapa set kromosom dengan beberapa mekanisme untuk menentukan gen diekspresikan yaitu, dominan pada setiap lokus. Mekanisme ini tampaknya untuk memberikan sejumlah keuntungan pada sebuah sistem, terutama dengan meningkatkan keragaman populasi; Saat gen yang tidak terpakai tetap dalam genotipe mul-tiplied, terpendam, tetapi terlindung dari kepunahan sampai mereka bisa menjadi berguna nanti.
Sebuah genotipe multiploid, ditunjukkan pada Gambar. 4.2, berisi p kromosom, masing-masing panjang L, dan masker yang menentukan mana dari kromosom p memiliki gen dominan pada posisi tertentu dalam kromosom. Informasi ini diterjemahkan untuk menghasilkan fenotipe sebagai berikut:
Gambar. 4.2 Multiploid Type 1
Gambar. 4.3 Multiploid Type 2
Nilai alel dari pada lokus i dalam topeng menunjukkan bahwa gen-i di chro-mosome dengan indeks menjadi gen i dari fenotip. Panjang masker dapat lebih pendek dari panjang kromosom, seperti pada Gambar. 4.3.
Pada Gambar. 4.3, jika panjang topeng adalah m dan panjang kromosom L, maka gen pada lokus 'i' di masker dengan nilai 'a' menunjukkan bahwa i-th set / m consecu-wakil-gen L di dalam kromosom -th yang dominan.
4.4 Inversi dan Memanggil Kembali
Inversi adalah penataan kembali unary operator, genetik. algoritma genetika sederhana menggunakan pilihan stokastik, 1-point menyeberang, dan mutasi untuk meningkatkan jumlah blok bangunan dalam populasi dan bergabung kembali mereka untuk lebih baik membangun-ing blok. Blok bangunan yang sangat cocok, orde rendah, pendek mendefinisikan skema panjang, skema pengkodean yang dipilih harus sesuai dengan ini. Bisakah kita mencari skema encoding yang lebih baik ketika mencari untuk membangun blok? Untuk menjawab pertanyaan ini, operator inversi diciptakan.
Operator inversi adalah mekanisme alam primer recode masalah. Dalam operator dalam-versi, dua poin yang dipilih sepanjang kromosom, kromosom dipotong pada titik-titik dan titik akhir dari bagian dipotong, akan kembali berpengalaman (diaktifkan, bertukar). Untuk membuat jelas, mempertimbangkan kromosom dengan panjang 8 di mana dua poin terbalik yang dipilih secara acak (poin 2 dan 6 dilambangkan dengan karakter):
1 1 ∧ 0 1 1 1 ∧ 0 1
Menggunakan Operator inversi, string menjadi,
1 1 1 1 1 0 0 1
Jadi dalam poin inversi yang ditentukan, beralih antara kromo-somes berlangsung.
Operator inversi juga dapat digunakan untuk representasi diperpanjang seperti yang diberikan oleh,
1
2
3
4
5
6
7
8
1
1 ∧ 0
1
1
1 ∧ 0
1
poin inversi dipilih secara acak (ditunjukkan oleh operator) dan kromo-beberapa sekarang menjadi,
1 2 6 5 4 3 7 8
1 1 1 1 1 0 0 1
nomor posisi semula dipertahankan dalam kromosom karena kebugaran func-tion dihitung dengan menggunakan nomor posisi, yaitu, kita bergerak posisi relatif dari gen untuk memeriksa blok bangunan potensial yang berbeda tetapi gen yang akan digunakan dalam fungsi kebugaran sama seperti sebelumnya inversi dan tetap sama setelah inversi operasi juga.
Harapannya adalah bahwa inversi akan mengurangi panjang mendefinisikan skema yang sangat cocok sehingga mereka bertahan hidup Crossover lebih. Inversi ditemukan untuk memperluas ruang pencarian. Inversi belum muncul berguna dalam praktek, mungkin karena kasus uji tidak sedang cukup keras (GA konvensional tanpa inversi bekerja dengan baik).
Inversi adalah solusi dari Holland, dimaksudkan untuk membawa alel co-disesuaikan pada lokus yang jauh lebih dekat bersama-sama pada kromosom. Interpretasi biologis operator inversi adalah bahwa ia mempertahankan disequilibria linkage karena seleksi dalam menghadapi gangguan oleh crossover. Dua lokus dalam suatu populasi berada dalam kesetimbangan linkage jika distribusi frekuensi alel pada satu lokus independen dari distribusi frekuensi alel pada lokus lainnya.
Algoritma dasar untuk inversi dapat diberikan sebagai berikut:
Data: l- length of chromosome
i1 ← random integer between 0 and l inclusive;
i2 ← random integer =i1 between 0 and ; inclusive; if i1 > i2 then
swap i1 and i2; end
for I=i1 to [(i1+i2-1)/2] do
swap allele and index at locus I with allele and index at locus.
i1+i2-1-I; end
Dengan demikian indeks diperlukan untuk setiap lokus untuk melestarikan arti dari locus inde-penden dari posisinya pada kromosom. Inversi berlebihan dengan operator seperti UX (Uniform Crossover), yang tidak memiliki bias posisi.
Ada beberapa operator penataan lainnya, yang menjadi variasi pada inversi. Mereka:
inversi linier.
Liner + end inversi.
inversi terus menerus.
inversi massa.
inversi linier adalah inversi, yang telah dibahas sebelumnya. Linear + end inversi adalah inversi linier dengan probabilitas tertentu (0,75). Ketika linear inversi tidak dilakukan, akhir inversi akan dilakukan dengan probabilitas yang sama (0,125) di kedua ujung kiri atau kanan string. Linear + end inversi meminimalkan milik inversi linier mengganggu alel hadir di dekat pusat string tidak proporsional dengan yang alel hadir di dekat ujung. Dalam modus inversi terus menerus, inversi diaplikasikan dengan probabilitas inversi tertentu, Pi, untuk masing-masing individu baru dan ketika dibuat. Dalam modus inversi massal tidak ada inversi berlangsung sampai populasi baru diciptakan, setelah itu, satu-setengah dari populasi ditemukan untuk menjalani inversi identik.
Fitur inversi dan crossover digabungkan bersama-sama untuk menghasilkan operator tunggal, yang mengarah pada pengembangan dari operator penataan lainnya. Pada inversi combin-ing dan Crossover, operator penataan kembali dirumuskan adalah:
Sebagian cocok Crossover (PMX).
Agar Crossover (OX).
Siklus Crossover (CX).
4.4.1 Sebagian cocok Crossover (PMX)
Dalam Crossover Sebagian cocok, dua string selaras, dan dua titik crossover dipilih seragam secara acak sepanjang string. Dua titik crossover memberikan pilihan yang cocok, yang digunakan untuk mempengaruhi lintas melalui operasi pertukaran posisi-oleh-posisi.
Pertimbangkan dua string:
Parent A
4
8
7
3
6
5
1
10
9
2
Parent B
3
1
4
2
7
9
10
8
6
5
Dua titik crossover dipilih secara acak, dan PMX hasil oleh bursa posisi bijaksana. Di antara titik-titik crossover gen bisa ditukar yaitu, 3 dan 2, 6 dan 7, 5 dan 9 tempat pertukaran. Ini adalah dengan pemetaan orangtua B untuk orangtua A. Sekarang pemetaan orangtua A ke orangtua B, 7 dan 6, 9 dan 5, 2 dan 3 tempat pertukaran. Jadi setelah PMX, keturunan yang dihasilkan sebagai berikut:
Child A
4
8
6
2
7
9
1
10
5
3
Child B
2
1
4
3
6
5
10
8
7
9
dimana setiap anak mengandung informasi pemesanan sebagian ditentukan oleh masing-masing orang tuanya. PMX dapat diterapkan untuk masalah dengan representasi permutasi.
4.4.2 Orde Crossover (OX)
Urutan Crossover dimulai dengan cara yang mirip dengan PMX. Tapi bukannya menggunakan pertukaran titik-demi-titik sebagai PMX tidak, order crossover berlaku geser gerak untuk mengisi lubang yang ditinggalkan oleh mentransfer posisi dipetakan.
Pertimbangkan kromosom induk,
Parent A
4
8
7
3
6
5
1
10
9
2
Parent B
3
1
4
2
7
9
10
8
6
5
Pada pemetaan induk B dengan orang tua A, tempat 3,6 dan 5 yang tersisa dengan lubang.
Child B
H 1 4 2 7 9 10 8 H H
Lubang ini sekarang diisi dengan gerakan geser yang dimulai dengan titik potong kedua.
Child B
2 7 9 H H H 10 8 1 4
Lubang-lubang tersebut kemudian diisi dengan bagian pencocokan diambil dari induk A. Dengan demikian melakukan operasi ini, keturunan yang dihasilkan menggunakan rangka crossover seperti yang diberikan di bawah ini.
Child A
3
6
5
2
7
9
1
10
4
8
Child B
2
7
9
3
6
5
10
8
1
4
Dari contoh, dapat dicatat bahwa PMX cenderung menghormati posisi mutlak sementara OX cenderung menghormati posisi relatif.
4.4.3 Siklus Crossover (CX)
Siklus Crossover berbeda dari PMX dan OX. Siklus melakukan rekombinasi di bawah kendala bahwa setiap gen berasal dari orang tua atau yang lain.
4.5 Niche dan Spesiasi
Masalah abadi dengan Algoritma Genetika adalah bahwa konvergensi prematur, yaitu, genotipe non-optimal mengambil alih populasi yang mengakibatkan setiap individu menjadi baik identik atau sangat sama, konsekuensi dari yang merupakan populasi yang tidak mengandung keragaman genetik yang cukup untuk berkembang lebih lanjut.
Hanya meningkatkan ukuran populasi mungkin tidak cukup untuk menghindari masalah ini, sementara setiap peningkatan ukuran populasi akan dikenakan biaya dua kali lipat dari kedua waktu com-putation ekstra dan generasi yang lebih untuk berkumpul di suatu solusi optimal.
Algoritma genetik kemudian, menghadapi masalah yang sulit. Bagaimana bisa suatu populasi menjadi en-couraged untuk berkumpul di sebuah solusi sementara tetap mempertahankan keanekaragaman? Jelas, mereka operator, yang menyebabkan konvergensi, Crossover yaitu dan reproduksi, harus diubah entah bagaimana.
Masalah lain yang sering digunakan sebagai kritik terhadap Algoritma Genetika adalah waktu yang terlibat dalam menurunkan solusi. Tidak seperti metode yang lebih deterministik seperti Neural Networks, mendaki bukit, metode berbasis aturan dll, Algoritma Genetika mengandung derajat besar keacakan dan tidak ada jaminan untuk berkumpul di solusi dalam waktu yang tetap. Hal ini tidak biasa bagi sebagian besar berjalan tidak menemukan solusi yang optimal.
Untungnya, karena sifatnya, Algoritma Genetik sejajar inheren, yaitu individu dapat dievaluasi secara paralel sebagai kinerja mereka jarang, jika pernah, af-fects yang individu lain. Fase reproduksi, namun, yang umumnya melibatkan seksual bebas-untuk-semua, di mana individu-individu dari panah penduduk sekitar dalam hiruk-pikuk gila berlomba-lomba dengan satu sama lain dalam upaya untuk kawin sesering possi-ble, merupakan hambatan serius dalam Algoritma Genetika tradisional. Kebugaran setiap individu harus diketahui, dan, meskipun besar dan tidak diragukan lagi sabar semangat hadir dalam populasi, hanya satu reproduksi / Crossover dapat terjadi pada suatu waktu. Sebuah metode yang bisa menghindari semacam ini bottleneck akan meminjamkan sendiri sangat baik untuk pelaksanaan pada mesin paralel, dan karenanya mempercepat seluruh proses.
Hal ini ditunjukkan dalam bagian ini bagaimana relung digunakan untuk memecahkan masalah multimodal dan unimodal.
Secara umum metode yang diadopsi untuk memecahkan masalah di atas dibahas mengizinkan evolusi individu, yang mengisi berbeda relung lingkungan, dengan individu sejenis berkumpul bersama-sama. Nama biologi yang benar untuk kelompok-kelompok seperti dalam ekotipe, tetapi mereka cenderung disebut spesies yang berbeda dalam Algoritma Genetika. Penggunaan kata "spesies" tidak sepenuhnya benar, sebagai individu masing-masing spesies mungkin bebas kawin dengan satu sama lain. Namun, demi konsistensi, spesies kata akan digunakan dengan arti biasanya dihubungkan dengan dalam Algoritma Genetika. Dalam bidang ini, ceruk biasanya mengacu pada apa yang membuat kelompok tertentu yang unik, misalnya memiliki tingkat kebugaran umum, genotipe dll, sementara spesies mengacu pada individu dalam kelompok itu.
4.5.1 Niche dan Spesiasi di Multimoda Masalah
Misalkan fungsi kebugaran multimodal yaitu beberapa puncak sebuah GA akan cenderung con-ambang ke salah satu puncak, terutama jika salah satu puncak lebih fit daripada yang lain.
Mungkin, satu suka untuk mengidentifikasi konvergensi puncak ke beberapa puncak simultan-menerus. A 'niche' dapat dianggap sebagai salah satu puncak dan 'spesies' adalah kumpulan dari anggota populasi cocok untuk niche tertentu.
Kita mungkin ingin GA untuk membuat sub-populasi yang stabil (spesies) yang sangat cocok digunakan untuk relung. Pertimbangkan contoh mesin slot dua bersenjata, jika satu orang memainkan mesin slot dua bersenjata, ia akan mencoba setiap lengan untuk sementara waktu untuk melihat yang memiliki hasil yang lebih besar, dan kemudian bermain lengan yang selama sisa waktu. Dalam hal ini, adalah mungkin untuk menurunkan rumus untuk berapa banyak untuk bermain di setiap lengan sebelum memilih yang lengan untuk memainkan sisa waktu untuk hasil keseluruhan yang optimal.
Sekarang anggaplah bahwa sekelompok orang yang semua bermain mesin slot dua bersenjata yang sama dan bahwa lengan kelompok bermain, kita harus berbagi kemenangan mereka dan juga untuk lengan juga. Para pemain diperbolehkan untuk beralih kelompok untuk meningkatkan pangsa mereka. Jika orang M bermain benar-benar,
M = M1 + M2
fi =arm I Payoff
dan
Kemudian orang-orang membentuk kelompok di setiap lengan diberikan oleh,
f1 / M1 = f2 / M2
Sesuatu yang mirip dengan ini dapat diimplementasikan dalam GA selama 'crowding' dan teknik 'shar-ing' seperti yang dibahas di bawah ini.
Algoritma genetik menggunakan panmictic diterapkan untuk fungsi multimodal menghadapi dua masalah utama, yang pertama adalah yang mendistribusikan individu merata di semua puncak dalam larutan seperti pada Gambar. 4.4.
Setiap puncak dalam lanskap solusi dapat dilihat sebagai ceruk lingkungan yang terpisah. Sebuah keberhasilan penerapan algoritma genetika untuk masalah seperti ini harus menghasilkan beberapa individu yang tersebar di masing-masing relung lingkungan. Apa cara yang lebih baik untuk melakukan ini daripada untuk mengizinkan evolusi beberapa spesies dalam lingkungan, masing-masing mengkhususkan diri dalam niche tertentu sendiri?
Menggunakan relung dan spesies dalam aplikasi seperti ini dapat meminjamkan arti yang lebih biologis untuk spesies kata. Masalah kedua sekarang muncul sebagai orang tua dari spesies berbeda-ing, yaitu dari relung lingkungan yang berbeda cenderung menghasilkan unviable chil-anak dan sebagainya, orang tua menempati relung yang berbeda harus berkecil hati dari kawin. Gambar. 4.5 di bawah mengilustrasikan masalah.
Gambar. 4.4 Fungsi multimodal solusi lanskap
Gambar. 4.5 Hasil kemungkinan kawin orang tua dari puncak berbeda adalah hal ini, di mana keturunan yang dihasilkan muncul dalam palung antara orang tua nya
4.5.1.1 Menyisihkan
Masalah pertama ditangani oleh [DeJong 75] untuk mencegah genotipe tunggal mendominasi populasi. Dengan memastikan bahwa individu yang baru lahir akan menggantikan satu bahwa itu adalah sekutu genotip mirip dengan itu, Menyisihkan mencoba untuk mempertahankan keseimbangan populasi-tion. Mekanisme untuk penggantian ini cukup sederhana: satu secara acak memilih CF individu dan, melalui perhitungan Hamming jarak, memutuskan pada korban yang cocok.
Sebuah keuntungan dari Menyisihkan adalah bagaimana beberapa individu harus diperiksa ketika memilih korban, untuk CF biasanya 2 atau 3. Penggantian ini dari tindakan individu yang sama 'untuk mencegah satu genotipe dari mengambil alih populasi sepenuhnya, memungkinkan, relung mungkin kurang fit lain untuk membentuk dalam populasi utama.
Crowding tidak secara eksplisit membuat ceruk, juga tidak membuat upaya terkonsentrasi untuk mendorong mereka, melainkan memungkinkan mereka untuk membentuk.
4.5.1.2 Sharing
Sebuah pendekatan yang agak berbeda diadopsi dalam skema Sharing, dalam indi-individu-dalam suatu populasi yang menggunakan Berbagi sumber daya wajah terbatas karena mereka berusaha untuk kebugaran. Untuk membuat hidup lebih sulit bagi mereka, individu-individu dari niche lingkungan yang sama, dalam hal ini genotipe sekutu yang sama, lebih cenderung untuk mencari tempat yang sama untuk sumber daya, sehingga memiliki waktu lebih sulit daripada individu yang unik.
Dalam cara yang mirip dengan yang Menyisihkan, dominasi populasi oleh geno-jenis tunggal tidak disarankan oleh menghukum individu yang terlalu mirip dengan sebagian besar penduduk.
Sharing, bagaimanapun, tidak sesederhana menghitung sebagai Menyisihkan, dan merupakan masalah yang sangat spesifik sebagai salah satu harus tahu terlebih dahulu berapa banyak puncak ada dalam lanskap solusi. Berbagi tidak mendorong pembentukan relung dan, untuk mencegah prospek buruk individu dari relung yang berbeda, perkawinan seperti pada Gambar. 4.5 di atas, menggunakan bentuk kawin dibatasi.
Mendefinisikan fungsi berbagi berdasarkan kesamaan,
Share (kesamaan)
Kesamaan (x, x) = l chrom,
Kesamaan (x, ~x) = 0
(Atau) dasar kesamaan pada fenotipe (nilai dikodekan) daripada genotipe.
Share (kesamaan (x, x)) = 1,0,
Share (kesamaan (x, y)) = 0,0
∀x, y, dengan kesamaan (x, y) ⇐cut off nilai.
Yang lebih mirip dua kromosom, semakin mereka harus berbagi nilai kebugaran mereka. Setiap kromosom x memiliki faktor share dihitung untuk itu,
Share faktor (x) = Sum lebih y di share populasi (kesamaan (x, y))
Kebugaran kromosom dihitung ulang dengan membagi kebugaran aslinya oleh faktor sahamnya,
kebugaran baru (x) = kebugaran (x) faktor / share (x)
Dalam arti, kromosom yang sama bermain lengan yang sama dari mesin slot k-bersenjata sehingga kami memaksa mereka untuk berbagi hasil dan sub-populasi lainnya (spesies) dapat mengembangkan sekitar puncak lainnya (niche).
Meskipun Menyisihkan jauh lebih sederhana daripada Sharing, baik dalam perhitungan dan exe-cution, yang terakhir telah terbukti jauh lebih efektif di daerah fungsi multimodal sebagai kekuatan bukan lembut persuasi digunakan oleh Menyisihkan tidak bisa mencegah sebagian besar individu dari berakhir hanya pada satu atau dua puncak karena beberapa individu yang diperiksa setiap kali. Berbagi, di sisi lain, agresif mendorong pengembangan ceruk baru dan akibatnya mendistribusikan individu di semua puncak dalam lanskap. Imbalannya adalah sederhana; Crowding murah dan sederhana, sedangkan Sharing relatif mahal belum berhasil.
4.5.2 Niche dan Spesiasi di unimodal Masalah
Penggunaan relung di masalah multimodal adalah pemetaan sangat sederhana, dengan evo-tu jaman revolusi dari spesies yang berbeda untuk masing-masing puncak dalam lanskap solusi. Pemetaan ini tidak begitu mudah dalam masalah unimodal yang biasanya hanya berisi satu puncak, atau setidaknya mengandung satu puncak yang lebih tinggi dari yang lain.
Semua pendekatan untuk masalah unimodal, yang melibatkan niching, usaha untuk mempertahankan populasi yang seimbang, baik melalui kawin dibatasi untuk mencegah tidak pantas orang tua kawin, atau melalui metode pengganti yang menghambat pengambilalihan populasi oleh genotipe tunggal.
Beberapa metode, yang tidak secara ketat menggunakan ceruk, tetapi yang melakukan meniru operasi mereka untuk beberapa derajat, ada. Ada beberapa metode pengganti, yang memastikan bahwa orang yang baru lahir cukup berbeda dari sisa populasi akan-kedepan memungkinkan mereka masuk, misalnya Clone Pencegahan, Steady State Algoritma Genetika (SSGA). Ada juga skema seleksi khusus, yang beroperasi dengan cara yang sama dengan kawin dibatasi, dijelaskan di atas, bahwa calon orang tua diperbolehkan untuk memenuhi ritual suami-istri mereka hanya jika mereka memenuhi kriteria tertentu. Pembatasan kawin tidak mengizinkan evolusi relung yang berbeda, tetapi biasanya memaksa orang tua untuk datang dari relung yang berbeda, sehingga memungkinkan setiap niche untuk mengerahkan pengaruh pada evolusi.
pencegahan Clone dan SSGA beroperasi dalam cara yang mirip dengan yang Menyisihkan bahwa sebelum seorang individu diizinkan masuk ke penduduk, itu dibandingkan dengan orang lain untuk memverifikasi keunikannya. Sementara Menyisihkan memeriksa hanya beberapa individu setiap kali, ini metode lain menjamin keunikan dengan membandingkan individu baru untuk setiap individu lain dalam populasi. Seperti yang Menyisihkan, mereka tidak mencoba untuk secara eksplisit membuat ceruk atau spesies, tetapi berusaha untuk mencegah dominasi populasi oleh spesies tunggal.
Sayangnya, kedua metode dikenakan biaya overhead yang tinggi, sebagai membandingkan dari individu-als adalah hal yang mahal. Hal ini juga adil untuk mengatakan bahwa klon, kehadiran yang dapat menghambat evolusi, tidak selalu menyebabkan bencana, dan di wajah bahkan kadang-kadang dapat membantu evolusi langsung.
ESHELMAN mengambil pandangan yang sama, ketika ia menyarankan penggunaan Pencegahan Incest, yang hanya berkecil klon, masih memungkinkan mereka untuk memasuki populasi. pencegahan inses mencoba untuk "menjodohkan" orang tua dengan maksud keturunan mereka mengambil gen terbaik dari orang tua mereka. Ini adalah dengan mengawinkan berbeda orang tua yang penyelam-sity disimpan dalam populasi dan evolusi demikian semakin diizinkan.
Sebagai populasi berkembang, individu yang menjadi lebih dan lebih mirip, sehingga menjadi lebih sulit untuk menemukan orang tua yang cocok. Untuk menghindari situasi di mana tidak ada orang tua seperti dalam suatu populasi, ada satu set ambang perbedaan, yang bisa santai jika ada beberapa kesulitan dalam memilih orang tua. Hal ini diasumsikan bahwa kesulitan akan timbul jika tidak ada perubahan pada populasi orang tua, dan, sebagai pencegahan incest digunakan dengan elitisme, yaitu daftar orang tua dipertahankan mana individu hanya dapat memasukkan jika kebugaran mereka cukup tinggi, itu adalah sepele peduli untuk melacak perubahan.
Sekali lagi, spesies yang berbeda tidak secara eksplisit diciptakan, tidak dijamin untuk tampil, tetapi jika mereka melakukannya, pencegahan Incest mendorong kawin antar-spesies, sebagai kebugaran lahan-scape dalam fungsi unimodal cenderung seperti itu dari Gambar. 4.4.
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
Begitu seorang individu diuji mencoba untuk memasuki populasi induk, sebagai de-jelaskan di atas, langkah ini hanya berhasil jika orang tersebut adalah bugar daripada anggota fit setidaknya dari populasi induk. Setelah semua individu baru telah diuji, satu memeriksa untuk melihat apakah populasi induk telah berubah. Populasi tidak berubah akan menyebabkan ambang perbedaan yang dikurangi.
The DIFFERENT () tes hanya menghitung jarak Hamming antara par-Ent dan memastikan bahwa, jika mereka berkembang biak, perbedaan akan berada di atas ambang batas. Seperti dapat dilihat dari langkah terakhir dalam algoritma, adalah mungkin untuk lari untuk mengakhiri untuk alasan lain selain tercapainya beberapa kriteria akhir. Dalam hal ini adalah com-mon untuk "reinitialize" penduduk oleh mutasi yang terbaik individu melakukan ditemui sejauh ini.
4.5.2.2 Algoritma Pygmy
Meskipun pencegahan incest menghindari biaya pencegahan clone, masih ada biaya untuk menemukan beberapa yang memuaskan setiap kali kawin yang akan dilakukan. Untuk mengurangi biaya sebanyak mungkin metode lain, Algoritma Pygmy telah disarankan, yang tidak secara eksplisit mengukur perbedaan antara orang tua, tetapi hanya menunjukkan bahwa orang tua itu memilih berbeda.
Algoritma Pygmy biasanya digunakan pada masalah dengan dua atau lebih membutuhkan-KASIH, misalnya evolusi solusi yang harus efisien dan singkat. Relung digunakan dengan memiliki dua fungsi kebugaran terpisah, sehingga menciptakan dua spesies. Individu dari setiap spesies yang kemudian dipandang sebagai jenis kelamin yang berbeda, dan ketika orang tua sedang dipilih untuk penciptaan individu baru, salah satu yang diambil dari masing-masing spesies dengan tujuan setiap orang tua mengerahkan tekanan dari fungsi fitness-nya.
Biasanya, ada satu fungsi utama kebugaran, mengatakan efisiensi, dan sekunder re-quirement seperti sesak. Sangat individu efisien maka akan memasuki ceruk pertama, sementara individu yang tidak cocok dengan niche ini menjalani tes kebugaran kedua, yang hanya fungsi fitness aslinya dimodifikasi untuk menyertakan persyaratan sekunder. Individu-individu kemudian berusaha untuk bergabung dengan niche kedua, dan kegagalan untuk mencapai hasil ini dalam kematian dini untuk individu yang bersangkutan.
Penggunaan dua relung mempertahankan populasi yang seimbang dan memastikan bahwa individ-uals yang cocok di kedua persyaratan diproduksi. Berikut ini adalah kode semu untuk Algoritma Pygmy
REPEAT
FOR EACH INDIVIDUAL DO
TEST INDIVIDUAL WITH MAIN FITNESS FUNCTION
. ENTER PARENT POPULATION #1
IF UNSUCCESSFUL
TEST INDIVIDUAL WITH 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
Setiap niche diimplementasikan sebagai terpisah, kelompok elitis, karena elitis na-ture setiap niche, yang mempertahankan individu pada lanskap solusi yang mirip dengan Gambar. 4.4, ada banyak tekanan pada orang yang baru lahir untuk muncul antara orang tua, dan dengan demikian mengungguli mereka. Hal ini juga mungkin, tentu saja, bahwa seorang anak dapat diberkahi dengan karakteristik terburuk dari induknya. Seorang anak seperti ini akan disingkirkan oleh Algoritma Pygmy tetapi orang tua, karena mereka memiliki potensi untuk menghasilkan anak-anak yang baik dipertahankan, hidup lebih lama anak malang mereka.
Sebagai Algoritma Genetika berasal langsung dari metode alami, mungkin un-mengherankan bahwa ada begitu banyak manfaat yang bisa diperoleh dari menyalin alam sekali lagi. Berbeda relung dan spesies dapat berkembang dan dipertahankan dalam sejumlah cara, mulai dari model desentralisasi sedekat mungkin dengan alam, dengan metode yang sangat terkendali.
Yang paling penting, setelah sub-populasi telah membentuk ceruk lingkungan mereka, mereka dapat dihukum banyak kegunaan. Beberapa solusi dapat dipertahankan dalam populasi pada suatu waktu, beragam individu dan, memang spesies dengan mudah dapat dibujuk untuk hidup berdampingan satu sama lain, sehingga mengurangi tekanan terhadap konvergensi prematur.
4.5.3 Dibatasi Kawin
Tujuan dari kawin dibatasi adalah untuk mendorong spesiasi, dan mengurangi produksi-tion dari lethals. Sebuah mematikan adalah anak dari orang tua dari dua relung yang berbeda. Meskipun setiap orang tua mungkin sangat cocok, kombinasi kromosom mereka mungkin sangat tidak layak jika jatuh di lembah antara dua maxima. Nature menghindari forma-tion dari lethals dengan mencegah perkawinan antara spesies yang berbeda, menggunakan berbagai teknik. (Sebenarnya, ini adalah definisi biologis utama dari spesies-satu set individu yang mungkin berkembang biak bersama untuk menghasilkan keturunan yang layak.)
Filosofi umum kawin dibatasi membuat asumsi bahwa jika dua orang tua yang sama (yaitu, dari niche yang sama) yang dikawinkan, maka keturunannya akan serupa. Namun, hal ini akan sangat tergantung pada coding skema-khususnya keberadaan blok bangunan, dan epistasis rendah. Di bawah crossover dan mutasi operator konvensional, dua orang tua dengan genotipe yang sama akan selalu menghasilkan keturunan dengan genotipe yang sama. Namun dalam kromosom yang sangat epistatik, tidak ada menjamin bahwa keturunan ini tidak akan kebugaran rendah, yaitu lethals. Kesamaan genotipe tidak menjamin kesamaan fenotipe. Efek ini membatasi penggunaan kawin dibatasi.
4.6 Beberapa Micro-operator
Beberapa operator tingkat rendah mikro telah diusulkan untuk digunakan dalam genetik pencarian algo-rithm. Beberapa operator mikro yang akan dibahas dalam bagian ini adalah sebagai berikut:
Pemisahan.
Translokasi.
Duplikasi.
Penghapusan.
diferensiasi seksual.
4.6.1 Pemisahan dan Translokasi
Mempertimbangkan proses pembentukan gamet ketika ada lebih dari satu pasang kromosom pada genotipe. Crossover terjadi sebagai ditangani di bab sebelumnya dan ketika itu adalah untuk membentuk gamet, kami secara acak memilih salah satu dari masing-masing kromosom haploid. Proses seleksi acak ini disebut sebagai segregasi yang mengganggu menghubungkan apapun, yang mungkin ada di antara gen pada kromosom yang berbeda. Hal ini ditemukan bahwa segregasi memanfaatkan organisasi yang tepat dari kromosom dan penting untuk dicatat bahwa bagaimana kromosom menjadi diselenggarakan dengan cara yang tepat. Untuk tujuan ini, operator translokasi digunakan. Operator translokasi dapat dianggap sebagai operator crossover yang interchromosomal. Operator ini dapat diimplementasikan dengan menghubungkan alel dengan nama gen mereka, sehingga seseorang dapat mengidentifikasi makna yang dimaksudkan ketika mereka beringsut dari kromosom ke kromosom oleh operator translo-kation.
4.6.2 Duplikasi dan Penghapusan
Ada juga sepasang operator tingkat rendah untuk melakukan pencarian algoritma genetika. duplikasi Intrachromosomal melakukan dengan menduplikasi gen tertentu dan menempatkannya bersama dengan nenek moyang pada kromosom. Penghapusan melakukan dengan menghapus duplikat gen dari kromosom. Tingkat mutasi dapat secara efektif dikendalikan oleh operator tersebut. Ketika tingkat mutasi tetap konstan dan salinan intrachromosomal duplikasi penyebab 'k' dari gen tertentu, maka efektif mutasi prob-kemampuan untuk gen ini dikalikan dengan 'k'. Di sisi lain, ketika penghapusan terjadi, tingkat mutasi yang efektif akan menurun.
4.6.3 Penentuan Seksual
Asal skema kawin, kami telah diizinkan setiap individu untuk kawin dengan yang lain, dan produk genetik yang dihasilkan dibagi sehingga mereka telah memastikan genotipe yang layak. Penentuan jenis kelamin ditangani secara berbeda pada spesies yang berbeda, tetapi contoh manusia sudah cukup untuk memahami tekad seksual. Seks adalah de-termined pada manusia oleh salah satu dari 23 pasang kromosom manusia. Wanita memiliki dua sama X dan kromosom X dan laki-laki memiliki dua X berbeda dan Y chro-mosomes. Selama proses gametogenesis, laki-laki membentuk sperma (yang membawa X atau kromosom Y) dan perempuan memiliki telur (yang hanya membawa X kromosom). Pada pembuahan, kromosom X yang diproduksi oleh perempuan dikombinasikan dengan baik X atau Y-kromosom yang dihasilkan oleh betina. Dengan demikian metode penentuan seks di hu-man sederhana. Menerapkan strategi yang sama untuk penentuan seks di GA pencarian. Pembentukan perbedaan jenis kelamin secara efektif membagi spesies menjadi dua atau lebih kelompok. Hal ini memungkinkan laki-laki dan perempuan untuk mengkhususkan, sehingga melampirkan berbagai perilaku yang diperlukan untuk bertahan hidup lebih luas daripada yang dengan populasi com-bersaing dari tunggal. Penelitian di bawah penentuan jenis kelamin dan perbedaan buatan pencarian algoritma genetika masih berlangsung.
4.7 Non-biner Representasi
Sebuah kromosom adalah urutan simbol, dan, secara tradisional, simbol-simbol ini telah digit biner, sehingga masing-masing simbol memiliki kardinalitas 2. abjad kardinalitas tinggi telah digunakan dalam beberapa penelitian, dan beberapa percaya mereka memiliki keunggulan. Gold-berg berpendapat bahwa secara teoritis, representasi biner memberikan jumlah terbesar dari schemata, dan menyediakan tingkat tertinggi paralelisme implisit. Tapi Antonisse menafsirkan schemata berbeda, dan menyimpulkan bahwa, sebaliknya, alfabet berkardinalitas tinggi mengandung lebih schemata dari yang biner.
Goldberg kini telah mengembangkan teori, yang menjelaskan mengapa berkardinalitas tinggi rep-resentations dapat melakukan dengan baik. Teorinya dari huruf maya mengatakan bahwa setiap simbol konvergen dalam beberapa generasi pertama, hanya menyisakan sejumlah kecil kemungkinan nilai. Dengan cara ini, setiap simbol efektif hanya memiliki kardinalitas rendah. studi empiris dari alfabet berkardinalitas tinggi telah biasanya digunakan kromosom mana setiap simbol mewakili integer, atau angka floating-point. Seperti yang ditunjukkan Davis keluar, parameter prob-lem sering numerik, sehingga mewakili mereka langsung sebagai angka, bukan bit-string, tampak jelas, dan mungkin memiliki keunggulan. Satu keuntungan adalah bahwa kita dapat lebih mudah menentukan bermakna, masalah spesifik crossover dan mutasi opera-tor. Berbagai operator real-nomor dapat dengan mudah dibayangkan, misalnya:
operator kombinasi
Rata-rata-rata mengambil aritmatika dari dua gen orang tua.
Geometris rata-mengambil akar kuadrat dari produk dari dua nilai.
Ekstensi-mengambil perbedaan antara dua nilai, dan menambahkannya ke yang lebih tinggi, atau kurangi dari bawah.
operator mutasi
Acak pengganti-ganti nilai dengan satu random
Merayap-menambah atau mengurangi kecil, jumlah yang dihasilkan secara acak.
Geometris merayap-kalikan dengan jumlah acak dekat satu.
Untuk kedua operator creep, jumlah secara acak mungkin memiliki berbagai distribusi; seragam dalam kisaran tertentu, eksponensial, Gaussian, binomial, dll Janikow & Michalewicz membuat perbandingan langsung antara biner dan floating-point representasi, dan menemukan bahwa versi floating-point memberi lebih cepat, lebih konsisten, dan hasil yang lebih akurat.
4.8 Multi-Objective Optimization
Masalah optimasi multi-tujuan telah menerima minat penelitian bentuk sejak awal 1960-an. Dalam masalah optimasi multi-tujuan, fungsi objektif beberapa perlu dioptimalkan secara bersamaan. Dalam kasus beberapa tujuan, ada tidak selalu ada solusi yang terbaik terhadap semua tujuan karena diferensiasi antara tujuan. Sebuah solusi mungkin yang terbaik dalam satu tujuan tetapi terburuk di negara lain. Oleh karena itu, biasanya ada satu set solusi untuk multiple-tujuan kasus, yang tidak hanya dapat dibandingkan satu sama lain. Untuk solusi tersebut, yang disebut solusi optimal Pareto atau solusi non-didominasi, tidak ada perbaikan mungkin dalam fungsi tujuan apapun tanpa mengorbankan setidaknya salah satu fungsi tujuan lainnya.
Jadi dengan menggunakan konsep Pareto-optimalitas kita dapat menemukan satu set solusi yang semua kompromi optimal antara tujuan yang saling bertentangan. Pareto-optimalitas adalah konsep yang digunakan ekonomi, teori permainan, dll Sebuah solusi Pareto-optimal adalah salah satu yang tidak didominasi oleh solusi lain yakni adalah satu di mana tidak ada tujuan dapat ditingkatkan tanpa kerusakan di salah satu atau lebih dari yang lain tujuan.
Dalam beberapa tahun terakhir, telah terjadi perkembangan yang luas dalam menerapkan genetik al-gorithms untuk memecahkan masalah optimasi multi-tujuan, yang dikenal sebagai optimasi multi-tujuan evolusi atau optimasi multi-tujuan genetik. Dasar fea-membangun struktur dari algoritma genetika adalah beberapa pencarian terarah dan global, di mana populasi solusi potensial dipertahankan dari generasi ke generasi. Pendekatan populasi ke populasi yang bermanfaat dalam eksplorasi solusi Pareto-optimal. Masalah utama dalam memecahkan masalah optimasi multi-tujuan dengan menggunakan algoritma genetika adalah bagaimana menentukan nilai fitness dari individu sesuai dengan beberapa tujuan.
4.9 Kombinatorial Optimasi
Optimasi kombinatorial berisi tubuh besar masalah dengan berbeda fea-tulisan dan properti. Meskipun masalah ini sangat berbeda satu sama lain, masalah dapat dicirikan sebagai salah satu jenis berikut:
Untuk menentukan permutasi dari beberapa item yang terkait dengan masalah tersebut.
Untuk menentukan kombinasi dari beberapa item.
Untuk menentukan baik permutasi dan kombinasi beberapa item.
Salah satu dari subjek di atas kendala.
Inti dari masalah sumber daya terbatas proyek penjadwalan dan kendaraan kemenangan-ing dan masalah penjadwalan adalah untuk menentukan permutasi dari beberapa item dikenakan beberapa kendala. Inti dari masalah mesin-penjadwalan paralel untuk de-tukan baik permutasi dan kombinasi item tunduk pada batasan tertentu. Sebuah fitur umum dari masalah adalah bahwa jika permutasi dan / atau kombinasi dapat ditentukan, solusi kemudian dapat dengan mudah diturunkan dengan proce-dure masalah spesifik. Jadi pendekatan umum untuk menerapkan algoritma genetika untuk masalah ini adalah sebagai berikut:
Menggunakan algoritma genetika berkembang permutasi dan / atau kombinasi yang tepat dari item dalam pertimbangan.
Kemudian gunakan pendekatan heuristik untuk membangun solusi sesuai dengan permutasi dan kombinasi.
4.10 Teknik Pengetahuan Berdasarkan
Sementara sebagian besar penelitian telah pergi ke GAs menggunakan crossover dan mutasi-tion operator tradisional, beberapa telah menganjurkan merancang operator baru untuk setiap tugas, menggunakan pengetahuan domain. Hal ini membuat setiap GA lebih tugas tertentu (kurang kuat), tetapi dapat meningkatkan kinerja secara signifikan. Dimana GA sedang dirancang untuk mengatasi masalah dunia nyata, dan harus bersaing dengan teknik pencarian dan optimasi lainnya, penggabungan pengetahuan domain sering masuk akal. Beberapa peneliti berpendapat bahwa pengetahuan masalah spesifik dapat berguna dimasukkan ke crossover op-timbangkan. pengetahuan domain dapat digunakan untuk mencegah kromosom jelas tidak layak, atau mereka yang akan melanggar kendala masalah, dari yang diproduksi di tempat pertama. Hal ini untuk menghindari membuang-buang waktu mengevaluasi individu tersebut, dan menghindari memperkenalkan berkinerja buruk dalam populasi.
Misalnya, seorang peneliti yang dirancang Crossover analog untuk tugas di generasi lintasan robot. informasi lokal ini digunakan dalam kromosom (yaitu, val-ues dari hanya beberapa gen) untuk memutuskan mana situs Crossover akan tertentu untuk menghasilkan keturunan layak. pengetahuan domain juga dapat digunakan untuk merancang operator perbaikan lokal, yang memungkinkan eksplorasi yang lebih efisien dari ruang pencarian di sekitar baik poin. Hal ini juga dapat digunakan untuk melakukan inisialisasi heuristik penduduk, sehingga pencarian yang dimulai dengan beberapa poin yang cukup baik, daripada satu set acak. Goldberg menjelaskan teknik untuk menambahkan pengetahuan diarahkan crossover dan mutasi. Dia juga membahas hibridisasi GAs dengan teknik pencarian lainnya. algoritma genetika murni hanya menggunakan encoding dan fungsi tujuan. Ini dapat membantu untuk digunakan dalam informasi spesifik masalah. Berbagai metode untuk menggabungkan informasi spesifik masalah dengan algoritma genetika adalah sebagai berikut:
skema hybrid
Pengetahuan diarahkan operator
komputer paralel.
In hybrid skema GAs digunakan untuk mendekati nilai optimal, maka skema optimasi konvensional seperti pencarian serakah, pencarian gradien atau stochastic mendaki bukit-ing dapat digunakan untuk menjadi lebih dekat dengan nilai optimum. Algoritma genetika juga dapat mengembangkan spesies yang masing-masing optimasi konvensional dapat diterapkan. Dalam gradien seperti bitwise (G-bit) perbaikan untuk satu atau lebih tinggi kromosom fit, mengubah setiap bit satu per satu untuk melihat apakah kebugaran membaik, jika demikian, menggantikan asli dengan kromosom diubah. Juga mengubah pasangan atau kembar tiga bit bisa dicoba tetapi dalam ledakan kombinatorial. Skema hybrid dapat direpresentasikan menggunakan skema seperti ditunjukkan pada Gambar. 4.6.
Jadi dari Gambar. 4.6, dapat dicatat bahwa algoritma genetika memilah puncak dan teknik pencarian lokal yang digunakan untuk memanjat bukit. Mengingat Crossover heuristik serakah untuk Traveling masalah salesman, jika kromosom yang permutasi dari angka kota, maka Crossover normal dapat menghasilkan kromosom tidak layak. Hal ini dilakukan oleh,
Start at a random city X and go to the closest city to X using the parent’s tours; repeat
Jadi algoritma genetika sekarang pasti tidak buta seperti itu menggunakan PMX de-jelaskan lebih mudah. Pengetahuan diarahkan operasi ditemukan untuk digunakan,
menghasilkan sistem Steiner
menghitung melestarikan mutasi dan crossover yang
tujuan diarahkan mutasi
Menggunakan komputer paralel Algoritma Genetika, operasi master / slave adalah per-terbentuk. Guru melakukan seleksi dan kawin dan budak dievaluasi kebugaran chro-mosomes baru. Guru menunggu semua budak untuk menyelesaikan atau master dapat menyerahkan pekerjaan baru sebagai setiap budak selesai. Jadi pada mesin paralel optimasi konvensional dapat dilakukan pada setiap spesies pada CPU sendiri. Hal ini ditunjukkan pada Gambar. 4.7.
Teknik berbasis pengetahuan ini berkembang dengan pengembangan perangkat keras dan perangkat lunak.
Download HTML disini