Genetic Algorithms: An Overview

download html download

Overview

Munculnya komputer elektronik bisa dibilang merupakan perkembangan paling revolusioner dalam sejarah sains dan teknologi. Aktivitas komputasi termotivasi secara biologis ini telah meleleh dan memudar selama bertahun-tahun, namun sejak awal 1980an mereka semua mengalami kebangkitan di komunitas riset komputasi. Yang pertama telah berkembang ke dalam bidang jaringan syaraf tiruan, yang kedua menjadi pembelajaran mesin, dan yang ketiga menjadi apa yang sekarang disebut "perhitungan evolusioner," yang merupakan contoh genetika yang paling menonjol.

1.1 SEJARAH SINGKAT KOMPUTASI EVOLUSI

Pada tahun 1960, Rechenberg (1965, 1973) memperkenalkan "strategi evolusi" (Evolutionsstrategie dalam bahasa Jerman asli), sebuah metode yang ia gunakan untuk mengoptimalkan parameter bernilai nyata untuk perangkat seperti airfoil. Gagasan ini dikembangkan lebih lanjut oleh Schwefel (1975, 1977). Bidang strategi evolusi tetap merupakan area penelitian yang aktif, kebanyakan berkembang secara independen dari bidang algoritma genetika (walaupun baru-baru ini kedua komunitas telah mulai berinteraksi). (Untuk tinjauan singkat strategi evolusi, lihat Kembali, Hoffmeister, dan Schwefel 1991.) Fogel, Owens, dan Walsh (1966) mengembangkan "pemrograman evolusioner," sebuah teknik di mana kandidat solusi untuk tugas yang diberikan diwakili sebagai mesin negara-terbatas , Yang berevolusi dengan mengubah secara acak diagram transisi negara mereka dan memilih yang paling tepat. Formulasi agak lebih luas.

Pengenalan algoritma berbasis populasi di Belanda dengan crossover, inversi, dan mutasi merupakan inovasi besar. (Strategi evolusi Rechenberg dimulai dengan "populasi" dua individu, satu orang tua dan satu keturunan, keturunannya menjadi versi mutakhir dari orang tua; banyak populasi individu dan crossover tidak digabungkan sampai kemudian. Pemrograman evolusioner Fogel, Owens, dan Walsh Juga hanya menggunakan mutasi untuk memberi variasi.) Selain itu, Belanda adalah orang pertama yang mencoba menerapkan evolusi komputasi pada pijakan teoritis perusahaan (lihat Holland 1975). Sampai saat ini, dasar teoritis ini, berdasarkan gagasan "skema", adalah dasar dari hampir semua karya teoretis berikutnya mengenai algoritma genetika.

1.2 PERILAKU EVOLUSI

Banyak masalah komputasi memerlukan program komputer agar adaptif untuk terus berkinerja baik dalam lingkungan yang terus berubah. Ini ditandai oleh masalah dalam kontrol robot di mana robot harus melakukan tugas di lingkungan yang bervariasi, dan dengan antarmuka komputer yang harus disesuaikan dengan keistimewaan pengguna yang berbeda. Masalah lain mengharuskan program komputer menjadi inovatif  untuk membangun sesuatu yang benar-benar baru dan asli, seperti algoritma baru untuk menyelesaikan tugas komputasi atau bahkan penemuan ilmiah baru. Akhirnya, banyak masalah komputasi memerlukan solusi kompleks yang sulit diprogram dengan tangan. Contoh yang mencolok adalah masalah menciptakan kecerdasan buatan.

Dalam perhitungan evolusioner, aturan biasanya "seleksi alam" dengan variasi karena crossover dan / atau mutasi; Perilaku yang diharapkan untuk muncul adalah desain solusi berkualitas tinggi untuk masalah yang sulit dan kemampuan untuk menyesuaikan solusi ini dalam menghadapi lingkungan yang terus berubah.

1.3 TERMINOLOGI BIOLOGI

 Semua organisme hidup terdiri dari sel-sel, dan setiap sel mengandung satu atau lebih kromosom yang sama - senar DNA - yang berfungsi sebagai "cetak biru" untuk organisme. Kromosom secara konseptual dapat dibagi menjadi gen-masing-masing mengkodekan protein tertentu. Setiap gen terletak pada lokus tertentu (posisi) pada kromosom. Banyak organisme memiliki beberapa kromosom di setiap sel. Koleksi lengkap bahan genetik (semua kromosom disatukan) disebut genom organisme. Istilah genotipe mengacu pada kumpulan gen tertentu yang terkandung dalam genom. Dua individu yang memiliki genom identik dikatakan memiliki genotipe yang sama. Genotip tersebut memunculkan, di bawah perkembangan janin dan kemudian, ke fenotip organisme - ciri fisik dan mentalnya, seperti warna mata, tinggi badan, ukuran otak, dan kecerdasan. Organisme yang kromosomnya tersusun dalam pasangan disebut diploid; Organisme yang kromosomnya tidak berpasangan disebut haploid.

 Dalam algoritma genetika, istilah kromosom biasanya mengacu pada solusi kandidat untuk masalah, sering dikodekan sebagai string bit. "Gen" adalah bit tunggal atau blok pendek dari bit yang berdekatan yang menyandikan elemen tertentu dari solusi kandidat (misalnya, dalam konteks optimasi fungsi multiparameter, bit yang mengkodekan parameter tertentu dapat dianggap sebagai gen). Alel dalam string bit adalah 0 atau 1; Untuk alfabet lebih besar, alel lebih mungkin dilakukan pada setiap lokus. Crossover biasanya terdiri dari pertukaran materi genetik antara dua orang tua singlechromosome haploid. Mutasi terdiri dari membalik bit pada lokus yang dipilih secara acak (atau, untuk huruf yang lebih besar, mengganti simbol pada lokus yang dipilih secara acak dengan simbol baru yang dipilih secara acak).

1.4 PENCARIAN RUANG LINGKUNGAN DAN KECELAKAAN

Gagasan mencari di antara kumpulan solusi kandidat untuk solusi yang diinginkan sangat umum dilakukan dalam ilmu komputer sehingga diberi nama sendiri: mencari di "ruang pencarian". Disini istilah "ruang pencarian" mengacu pada beberapa koleksi solusi kandidat untuk sebuah masalah dan beberapa gagasan tentang "jarak" antara solusi kandidat. Sebagai contoh, mari kita ambil salah satu masalah yang paling penting dalam bioengineering komputasi: masalah yang disebutkan di atas dari rancangan protein komputasi.

1.5 ELEMENTS OF GENETIC ALGORITHMS

Examples of Fitness Functions
Salah satu aplikasi GA yang umum adalah optimasi fungsi, dimana tujuannya adalah untuk menemukan seperangkat nilai parameter yang memaksimalkan, katakanlah, fungsi multiparameter yang kompleks.Sebagai contoh sederhana, seseorang mungkin ingin memaksimalkan fungsi satu dimensi bernilai riil:

Operator GA
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 direproduksi.

Crossover Operator ini secara acak memilih lokus dan menukar urutan sebelum dan sesudah lokus tersebut Antara dua kromosom untuk menciptakan dua keturunan. Misalnya, senar 10000100 dan  11111111 bisa jadi Menyeberang setelah lokus ketiga di masing-masing menghasilkan dua keturunan 10011111 dan 11100100.  Crossover Operator kira-kira meniru rekombinasi biologis antara dua organisme kromosom tunggal (haploid).

Mutasi Operator ini secara acak membalik beberapa bit dalam kromosom. Misalnya, string 00000100 Mungkin bermutasi di posisi kedua untuk menghasilkan 01000100. Mutasi dapat terjadi pada setiap posisi bit dalam sebuah string Dengan probabilitas tertentu, biasanya sangat kecil (misalnya 0,001). 

1.6 ALGORITMA GENETIK SEDERHANA 

Mengingat masalah yang didefinisikan dengan jelas untuk dipecahkan dan representasi string sedikit untuk solusi kandidat, GA sederhana bekerja sebagai berikut:
 1. Mulailah dengan populasi kromosom n l-bit yang dihasilkan secara acak (kandidat solusi untuk perampok).
 2. Hitung kebugaran ƒ (x) setiap kromosom x pada populasi.
 3. Ulangi langkah berikut sampai n keturunan telah dibuat:   
   A. Pilih sepasang kromosom induk dari populasi saat ini, probabilitas seleksi menjadi fungsi peningkatan kebugaran. Seleksi dilakukan "dengan penggantian," artinya kromosom yang sama bisa dipilih lebih dari satu kali untuk menjadi orang tua.      B. Dengan probabilitas p ("probabilitas crossover" atau "crossover rate"), menyeberang pasangan pada titik yang dipilih secara acak (dipilih dengan probabilitas seragam) untuk membentuk dua keturunan. Jika tidak ada crossover yang terjadi, bentuk dua keturunan yang merupakan eksemplar tepat dari masing-masing orang tua. (Perhatikan bahwa di sini tingkat crossover didefinisikan sebagai probabilitas bahwa dua orang tua akan menyeberang dalam satu titik saja. Ada juga versi crossover "multi-point" dari GA dimana tingkat crossover untuk sepasang orang tua adalah jumlah Titik dimana terjadi crossover) c      C. Mutasi dua keturunan di setiap lokus dengan probabilitas  (Probabilitas mutasi atau mutasi), dan menempatkan kromosom yang dihasilkan pada populasi baru. Jika n aneh, satu anggota populasi baru dapat dibuang secara acak.

 4. Ganti populasi saat ini dengan populasi baru.
 5. Pergi ke langkah 2.

Populasi awal (acak) mungkin terlihat seperti ini:

Begitu sepasang orang tua dipilih, dengan probabilitas mereka menyeberang untuk membentuk dua keturunan. Jika mereka tidak menyeberang, maka keturunannya adalah salinan pasti dari setiap orang tua. Misalkan, pada contoh di atas, orang tua B dan D menyeberang setelah posisi bit pertama membentuk keturunan E = 10110100 dan F = 01101110, dan orang tua B dan C tidak menyeberang, malah membentuk keturunan yang merupakan salinan B dan C. Selanjutnya, setiap keturunan mengalami mutasi pada masing-masing lokus dengan probabilitas. Sebagai contoh, anggaplah keturunan E bermutasi di lokus keenam untuk membentuk E '= 10110000, keturunan F dan C tidak bermutasi sama sekali, dan keturunan B bermutasi pada lokus pertama untuk membentuk B' = 01101110. Populasi baru akan menjadi pengikut: 

1.7 ALGORITMA GENETIKA DAN METODE PENCARIAN TRADISIONAL

      Mencari data tersimpan Di sini masalahnya adalah untuk secara efisien mengambil informasi yang tersimpan dalam memori komputer. Misalkan Anda memiliki database nama dan alamat yang besar yang tersimpan dalam beberapa cara yang diperintahkan. Apa cara terbaik untuk mencari rekaman yang sesuai dengan nama belakang? "Binary search" adalah salah satu metode untuk menemukan rekaman yang diinginkan secara efisien.

     Mencari jalan menuju sasaran Di sini masalahnya adalah untuk secara efisien menemukan serangkaian tindakan yang akan berpindah dari keadaan awal yang diberikan ke tujuan yang telah ditentukan. Bentuk pencarian ini sangat penting bagi banyak pendekatan dalam kecerdasan buatan.

     Algoritma pencarian yang dibahas dalam kebanyakan konteks AI adalah metode untuk menemukan jalan terbaik (di sini, yang terpendek) dengan mudah dari keadaan awal ke keadaan sasaran. Algoritma tipikal adalah "pencarian mendalam-pertama," "cabang dan ikatan," dan "A *.

 

Gambar 1.2: 8-teka-teki. (A) Masalahnya adalah untuk menemukan urutan pergerakan yang akan pergi dari keadaan semula ke negara dengan ubin dalam urutan yang benar (goal state). (B) Sebuah pohon pencari parsial untuk 8-teka-teki.  

   

    Mencari solusi Ini adalah kelas pencarian yang lebih umum daripada "mencari jalan menuju sasaran." Idenya adalah untuk secara efisien menemukan solusi untuk masalah dalam ruang besar solusi kandidat. Ini adalah jenis masalah pencarian yang algoritma genetika digunakan. Jelas ada perbedaan besar antara jenis pencarian pertama dan kedua. Yang pertama menyangkut masalah di mana seseorang perlu menemukan informasi (mis., Nomor telepon) dalam kumpulan informasi yang tersimpan secara eksplisit.  

      GA adalah metode umum untuk memecahkan masalah "mencari solusi" (seperti juga teknik yang terinspirasi evolusi lainnya, seperti strategi evolusi dan pemrograman evolusioner). Pendakian bukit, simulasi anil, dan pencarian tabu adalah contoh metode umum lainnya. Beberapa di antaranya mirip dengan metode "cari jalan menuju sasaran" seperti cabang dan cabang dan A *. Untuk deskripsi metode pencarian ini dan yang lainnya lihat Winston 1992, Glover 1989 dan 1990, dan Kirkpatrick, Gelatt, dan Vecchi 1983. Pendakian bukit "Pendakian pendakian", misalnya, bekerja sebagai berikut:1. Pilih solusi kandidat (mis., Dikodekan sebagai string kecil) secara acak. Panggil string saat ini string.2. Secara sistematis mutasi setiap bit pada string dari kiri ke kanan, satu per satu, merekam kebugaran mutan satu bit yang dihasilkan.3. Jika salah satu mutan satu bit yang dihasilkan memberikan peningkatan kebugaran, kemudian atur string saat ini ke mutan satu-bit yang menghasilkan peningkatan kebugaran tertinggi ("kenaikan paling curam").4. Jika tidak ada peningkatan kebugaran, simpan string saat ini ("puncak bukit") dan lanjutkan ke langkah 1. Jika tidak, lanjutkan ke langkah 2 dengan string arus baru.5. Bila sejumlah evaluasi fungsi kebugaran telah dilakukan, kembalikan puncak bukit tertinggi yang ditemukan. 

 1.9 DUA CONTOH SINGKAT

 Menggunakan GAs untuk Mengembangkan Strategi untuk Dilema Tawanan Dilema

Contohnya : 
       Dua individu (panggil mereka Alice dan Bob) ditangkap karena melakukan kejahatan bersama dan ditahan di sel terpisah, tanpa ada kemungkinan komunikasi di antara mereka. Alice ditawari kesepakatan berikut: Jika dia mengaku dan setuju untuk bersaksi melawan Bob, dia akan menerima hukuman percobaan dengan masa percobaan, dan Bob akan dipecat selama 5 tahun. Namun, jika pada saat bersamaan Bob mengaku dan setuju untuk bersaksi melawan Alice, kesaksiannya akan didiskreditkan, dan masing-masing akan menerima 4 tahun karena mengaku bersalah. Alice diberi tahu bahwa Bob ditawari kesepakatan yang sama persis. Baik Alice maupun Bob tahu bahwa jika tidak bersaksi melawan yang lain, mereka dapat dihukum hanya dengan biaya lebih rendah yang akan mereka dapatkan masing-masing 2 tahun di penjara. Haruskah Alice "membelot" melawan Bob dan berharap untuk hukuman yang ditangguhkan, mempertaruhkan hukuman 4 tahun jika Bob cacat? Atau haruskah dia "bekerja sama" dengan Bob (walaupun mereka tidak bisa berkomunikasi), dengan harapan dia juga akan bekerja sama sehingga masing-masing hanya akan mendapatkan 2 tahun, sehingga mempertaruhkan pembelotan Bob yang akan mengirimnya pergi selama 5 tahun?

    Sebuah "permainan" terdiri dari setiap pemain yang membuat keputusan (sebuah "langkah"). Hasil yang mungkin dari game tunggal dirangkum dalam matriks hasil seperti yang ditunjukkan pada gambar 1.3. Di sini tujuannya adalah untuk mendapatkan banyak poin (berlawanan dengan beberapa tahun penjara) mungkin. (Pada gambar 1.3, hasil masing-masing dapat diinterpretasikan sebagai 5 dikurangi jumlah tahun penjara). Jika kedua pemain bekerja sama, masing-masing mendapat 3 poin. Jika pemain A cacat dan pemain B bekerja sama, maka pemain A mendapat 5 poin dan pemain B mendapat 0 poin, dan sebaliknya jika situasinya terbalik. Jika kedua pemain cacat, masing-masing mendapat 1 poin. Apa strategi terbaik yang digunakan untuk memaksimalkan hasil sendiri? 

Gambar 1.3: Matriks pembayaran untuk Dilema Tawanan (diadaptasi dari Axelrod 1987). Dua angka yang diberikan di setiap kotak adalah hadiah untuk pemain A dan B dalam situasi yang ditentukan, dengan gaji pemain A tercantum pertama di setiap pasangan.

   Setelah dua turnamen, Axelrod (1987) memutuskan untuk melihat apakah GA bisa mengembangkan strategi untuk memainkan game ini dengan sukses. Isu pertama adalah mencari tahu bagaimana cara mengkodekan strategi sebagai string. Begini cara pengkodean Axelrod bekerja. Misalkan memori dari masing-masing pemain adalah satu game sebelumnya. Ada empat kemungkinan untuk game sebelumnya:•CC (kasus 1),•CD (kasus 2),•DC (kasus 3),•DD (kasus 4),Dimana C menunjukkan "bekerja sama" dan D menunjukkan "cacat." Kasus 1 adalah ketika kedua pemain bekerja sama dalam game sebelumnya, kasus 2 adalah saat pemain A bekerja sama dan pemain B membelot, dan seterusnya. Strategi hanyalah sebuah aturan yang menentukan suatu tindakan dalam masing-masing kasus ini. Misalnya, TIT UNTUK TAT seperti yang dimainkan oleh pemain A adalah sebagai berikut:•Jika CC (kasus 1), maka C.•Jika CD (kasus 2), maka D.•Jika DC (kasus 3), maka C.•Jika DD (kasus 4), maka D.Jika kasusnya dipesan dengan cara kanonik ini, strategi ini bisa dinyatakan kompak seperti CDCD string. Untuk menggunakan string sebagai strategi, pemain mencatat pergerakan yang dilakukan pada game sebelumnya (misalnya CD), menemukan nomor kasus i dengan melihat kasus tersebut dalam tabel kasus pesanan seperti yang diberikan di atas (untuk CD, i = 2), dan memilih huruf di posisi ke-i dari string sebagai kepindahannya di game berikutnya (untuk i = 2, langkahnya adalah D). Turnamen Axelrod melibatkan strategi yang mengingat tiga pertandingan sebelumnya. Ada 64 kemungkinan untuk tiga pertandingan sebelumnya:•CC CC CC (kasus 1),•CC CC CD (kasus 2),•CC CC DC (kasus 3),♦saya•DD DD DC (kasus 63),•DD DD DD (kasus 64).Dengan demikian, strategi dapat dikodekan dengan string 64 huruf, misalnya, CDCCCDDCC CDD .... Karena menggunakan strategi tersebut membutuhkan hasil dari ketiga game sebelumnya, Axelrod benar-benar menggunakan string 70 huruf, di mana enam huruf tambahan mengodekan tiga game hipotetis sebelumnya yang digunakan oleh strategi untuk memutuskan bagaimana cara melangkah dalam game sebenarnya.

Host dan Parasit: Menggunakan GAs to Evolve Sorting Networks

     Tujuan pemilahan adalah menempatkan elemen dalam struktur data (mis., Daftar atau pohon) dalam beberapa urutan tertentu (mis., Numerik atau abjad) dalam waktu minimal. Salah satu pendekatan khusus untuk pemilahan yang dijelaskan dalam buku Knuth adalah jaringan pemilahan, perangkat yang dapat diparalelkan untuk menyortir daftar dengan jumlah elemen n tertentu.

 

Gambar 1.4 menampilkan satu jaringan semacam itu (sejenis "Batcher" -melihat Knuth 1973) yang akan mengurutkan daftar n = 16 elemen (e 0 -e).

       Setiap garis horizontal mewakili salah satu elemen dalam daftar, dan setiap tanda panah vertikal merupakan perbandingan yang harus dibuat di antara dua elemen. Misalnya, kolom paling kiri dari panah vertikal menunjukkan bahwa perbandingan harus dibuat antara e 15 0 dan e 1, antara e, dan seterusnya. Jika elemen yang dibandingkan berada di luar urutan yang diinginkan, mereka akan bertukar. Gambar 1.4: "Batcher sort" n = 16 menyortir jaringan (diadaptasi dari Knuth 1973). Setiap garis horisontal 2 dan e 3 mewakili elemen dalam daftar, dan setiap panah vertikal mewakili perbandingan yang harus dibuat di antara dua elemen. Jika elemen yang dibandingkan rusak, mereka ditukar. Perbandingan di kolom yang sama bisa dibuat secara paralel. Untuk mengurutkan daftar elemen, satu membuat daftar dari kiri ke kanan melalui jaringan, melakukan semua perbandingan (dan swap, jika perlu) yang ditentukan di setiap kolom vertikal sebelum melanjutkan ke berikutnya.

Perhatikan bahwa di bawah pengkodean Hillis, GA tidak dapat menemukan jaringan dengan perbandingan kurang dari 60. 

 

Gambar 1.5: Rincian representasi genotipe jaringan pemilahan yang digunakan dalam percobaan Hillis. (A) Contoh genotipe untuk jaringan pemilahan individu, yang terdiri dari 15 pasang kromosom 32 bit. (B) Contoh bilangan bulat yang dikodekan oleh satu kromosom tunggal. Kromosom yang diberikan di sini mengkodekan bilangan bulat 11,5,7,9,14,4,10, dan 9; Setiap pasangan bilangan bulat yang berdekatan ditafsirkan sebagai perbandingan. (C) Contoh perbandingan yang dikodekan oleh pasangan kromosom. Pasangan yang diberikan di sini berisi dua posisi homozigot dan dengan demikian mengkodekan total enam perbandingan yang akan dimasukkan dalam fenotip: (11,5), (7,9), (2,7), (14,4), (3, 12), dan (10,9).

 

      Dalam eksperimen Hillis, populasi awal terdiri dari sejumlah genotipe yang dihasilkan secara acak, dengan satu ketentuan yang patut dicatat: Hillis mencatat bahwa sebagian besar jaringan sortir 16 elemen yang dikenal dimulai dengan pola perbandingan 32 yang sama, jadi dia menetapkan delapan kromosom pertama Pasangan di setiap individu untuk (homozigot) mengkodekan perbandingan ini.

     Gambar 1.6: Ilustrasi rekombinasi diploid seperti yang dilakukan pada eksperimen Hillis. Berikut genotipe individu terdiri dari 15 pasang kromosom (demi kejelasan, hanya satu pasangan untuk setiap induknya yang diperlihatkan). Sebuah titik crossover dipilih secara acak untuk masing-masing pasangan, dan sebuah gamet dibentuk dengan mengambil kodon sebelum titik crossover pada kromosom pertama dan kodon setelah titik crossover pada kromosom kedua. 15 gamet dari satu orang tua dipasangkan dengan 15 gamet dari induk lainnya untuk membuat individu baru.

1.10 BAGAIMANA ALGORITMA GENETIKA BEKERJA?

   F(x) / di mana ƒ (x) adalah kebugaran x dan adalah kebugaran rata-rata populasi pada waktu t. Kemudian, dengan asumsi x ada pada populasi pada waktu t, membiarkan x Î H menunjukkan "x adalah turunan dari H," dan (untuk saat ini) mengabaikan efek crossover dan mutasi, kita memiliki

 

(1.1) menurut definisi, karena Û ( H, t) = (£ ƒ (x)) / m (H, t) untuk x pada populasi pada waktu t. Jadi, meskipun GA tidak menghitung Û (H, t) secara eksplisit, peningkatan atau penurunan contoh skema dalam populasi bergantung pada kuantitas ini.

    Crossover dan mutasi dapat menghancurkan dan menciptakan contoh H. Untuk saat ini mari kita sertakan hanya efek destruktif dari crossover dan mutation - yaitu yang mengurangi jumlah kejadian H. Termasuk efek ini, kita memodifikasi sisi kanan dari persamaan 1.1 untuk diberikan. Batas bawah pada E (m (H, t + 1)). Biarkan p menjadi Probabilitas bahwa crossover satu titik akan diterapkan pada sebuah string, dan misalkan sebuah instance dari skema H dipilih sebagai induk.

  Dimana d(H) adalah panjang H dan l adalah panjang string bit di ruang pencarian. Yaitu, perpindahan silang yang terjadi dalam menentukan panjang H dapat menghancurkan H (yaitu, dapat menghasilkan keturunan yang bukan contoh H), jadi kita melipatgandakan pecahan senar H yang ditempati oleh probabilitas crossover untuk mendapatkan batas atas pada Kemungkinan itu akan hancur. (Nilai adalah batas atas karena beberapa crossover di dalam posisi yang ditentukan oleh skema tidak akan menghancurkannya, misalnya, jika dua ikatan identik saling silang.) 

Dimana o (H) adalah urutan H (yaitu, jumlah bit yang ditentukan dalam H). Artinya, untuk setiap bit, probabilitas bahwa bit tidak akan bermutasi adalah 1? P, jadi probabilitas bahwa tidak ada bit skema H yang didefinisikan yang akan dimatikan adalah kuantitas ini dikalikan dengan sendirinya o (H) kali. Singkatnya, probabilitas bertahan hidup di bawah mutasi lebih tinggi untuk skema tingkat rendah.
 
Efek pengganggu ini dapat digunakan untuk mengubah persamaan 1.1: (1.2)