Şema (genetik algoritmalar) - Schema (genetic algorithms)

Bir şema , genetik algoritmalar alanında kullanılan ve belirli dizgi konumlarında benzerlikler içeren bir dizi alt kümesini tanımlayan bilgisayar biliminde kullanılan bir şablondur . Şemalar özel bir silindir setleri durumudur ; ve böylece bir topolojik uzay oluşturur .

Açıklama

Örneğin, 6 uzunluğundaki ikili dizeleri düşünün. 1 ** 0 * 1 şeması, 6 uzunluğundaki tüm sözcüklerin kümesini birinci ve altıncı konumlarda 1'ler ve dördüncü konumda 0 ile açıklar. * Bir joker simgedir, yani 2, 3 ve 5 konumlarının 1 veya 0 değerine sahip olabileceği anlamına gelir . Bir şemanın sırası , şablondaki sabit konumların sayısı olarak tanımlanırken, tanımlayıcı uzunluk mesafedir. ilk ve son belirli pozisyonlar arasında. 1 ** 0 * 1 sırası 3'tür ve tanımlayıcı uzunluğu 5'tir . Bir şemanın uygunluğu, şema ile eşleşen tüm dizelerin ortalama uygunluğudur. Bir dizenin uygunluğu, probleme özgü bir değerlendirme işlevi tarafından hesaplandığı şekliyle kodlanmış problem çözümünün değerinin bir ölçüsüdür. ${\ displaystyle \ delta (H)}$

Uzunluk

Çağrılan bir şemanın uzunluğu, şemadaki toplam düğüm sayısı olarak tanımlanır. aynı zamanda eşleşen programlardaki düğüm sayısına eşittir . ${\ displaystyle H}$ ${\ displaystyle N (H)}$ ${\ displaystyle N (H)}$ ${\ displaystyle H}$

Bozulma

Şema H ile eşleşen bir bireyin çocuğu kendisi H ile eşleşmiyorsa , şemanın bozulmuş olduğu söylenir .

Şemanın yayılması

İçinde evrimsel işlem gibi genetik algoritma ve genetik programlama , yayılma aşağıdaki göre bir kuşak özelliklerinin miras belirtmektedir. Örneğin, bir şema, mevcut nesildeki bireyler onunla eşleşirse ve sonraki nesildekiler de eşleşirse yayılır. Gelecek nesildekiler, ona uyan ebeveynlerin çocukları olabilir (ama olmak zorunda değil).

Genişletme ve Sıkıştırma Operatörleri

Son zamanlarda şema, düzen teorisi kullanılarak incelenmiştir .

Şema için iki temel operatör tanımlanmıştır: genişletme ve sıkıştırma. Genişletme, bir şemayı temsil ettiği bir dizi kelimeye eşlerken, sıkıştırma bir şema üzerinde bir dizi kelimeyi eşler.

Aşağıdaki tanımlarda , bir alfabeye belirtir uzunluğunun tüm kelimeleri gösterir alfabesi üzerinde , alfabe gösterir ekstra sembolüyle . alfabe üzerindeki tüm uzunluk şemasını ve boş şemayı gösterir . ${\ displaystyle \ Sigma}$ ${\ displaystyle \ Sigma ^ {l}}$ ${\ displaystyle l}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle \ Sigma _ {*}}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle *}$ ${\ displaystyle \ Sigma _ {*} ^ {l}}$ ${\ displaystyle l}$ ${\ displaystyle \ Sigma _ {*}}$ ${\ displaystyle \ epsilon _ {*}}$

Herhangi şema için aşağıdaki operatör denilen ait haritalar, kelimelerin belirli bir kısmının : ${\ displaystyle \ in \ Sigma _ {*} ^ {l}}$ ${\ displaystyle {\ uparrow} s}$ ${\ displaystyle genişletme}$ ${\ displaystyle s}$ ${\ displaystyle s}$ ${\ displaystyle \ Sigma ^ {l}}$

{\ displaystyle {\ uparrow} s: = \ {b \ in \ Sigma ^ {l} | b_ {i} = s_ {i} {\ mbox {veya}} s_ {i} = * {\ mbox {her biri için }} i \ in \ {1, ..., l \} \}}

Alt simge , bir sözcük veya şemadaki konumdaki karakteri belirtir . O zaman ne zaman . Daha basitçe ifade etmek gerekirse, içindeki semboller ile sembollerin değiş tokuşu yapılarak yapılabilen tüm kelimelerin kümesidir . Örneğin eğer, için , ve sonra . ${\ displaystyle i}$ ${\ displaystyle i}$ ${\ displaystyle s = \ epsilon _ {*}}$ ${\ displaystyle {\ uparrow} s = \ emptyset}$ ${\ displaystyle {\ uparrow} s}$ ${\ displaystyle \ Sigma ^ {l}}$ ${\ displaystyle *}$ ${\ displaystyle s}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle \ Sigma = \ {0,1 \}}$ ${\ displaystyle l = 3}$ ${\ displaystyle s = 10 *}$ ${\ displaystyle {\ uparrow} s = \ {100,101 \}}$

Tersine, herhangi biri için biz tanımlamak denilen ait haritalar, hangi bir şemaya üzerinde : ${\ displaystyle A \ subseteq \ Sigma ^ {l}}$ ${\ displaystyle {\ downarrow} {A}}$ ${\ displaystyle sıkıştırma}$ ${\ displaystyle A}$ ${\ displaystyle A}$ ${\ displaystyle \ in \ Sigma _ {*} ^ {l}}$

{\ displaystyle {\ downarrow} A: = s}

nerede olduğunu uzunlukta bir şema şekilde pozisyonda sembolü de şu şekilde belirlenir: eğer herkes için daha sonra başka türlü . Eğer o zaman . Bu operatörün tüm öğeleri yığdığı düşünülebilir ve bir sütundaki tüm öğeler eşdeğerse, o konumdaki sembol bu değeri alır, aksi takdirde bir joker karakter sembolü vardır. Örneğin, izin ver o zaman .

{\ displaystyle s}

{\ displaystyle l}

{\ displaystyle i}

{\ displaystyle s}

{\ displaystyle x_ {i} = y_ {i}}

{\ displaystyle x, y \ A’da}

{\ displaystyle s_ {i} = x_ {i}}

{\ displaystyle s_ {i} = *}

{\ displaystyle A = \ emptyset}

{\ displaystyle {\ downarrow} A = \ epsilon _ {*}}

{\ displaystyle A}

{\ displaystyle s}

{\ displaystyle A = \ {100.000.010 \}}

{\ displaystyle {\ downarrow} A = ** 0}

Şemalar kısmen sipariş edilebilir . Herhangi biri için eğer ve sadece eğer diyoruz . O şöyle bir olan kısmi sıralama gelen schemata bir dizi refleksivite , antisimetrikliğin ve geçişlilik ait alt küme ilişkisi. Örneğin ,. Bunun nedeni . ${\ displaystyle a, b \ in \ Sigma _ {*} ^ {l}}$ ${\ displaystyle a \ leq b}$ ${\ displaystyle {\ uparrow} a \ subseteq {\ uparrow} b}$ ${\ displaystyle \ leq}$ ${\ displaystyle \ epsilon _ {*} \ leq 11 \ leq 1 * \ leq **}$ ${\ displaystyle {\ uparrow} \ epsilon _ {*} \ subseteq {\ uparrow} 11 \ subseteq {\ uparrow} 1 * \ subseteq {\ uparrow} ** = \ emptyset \ subseteq \ {11 \} \ subseteq \ { 11,10 \} \ subseteq \ {11,10,01,00 \}}$

Sıkıştırma ve genişletme operatörleri bir Galois bağlantısı oluşturur ; burada alt eşleşme ve üst eşleşme. ${\ displaystyle \ downarrow}$ ${\ displaystyle \ uparrow}$

Şematik Tamamlama ve Şematik Kafes

Bir küme için , A'nın her bir alt kümesindeki sıkıştırmayı hesaplama sürecini, yani gösterilen şematik tamamlanma sürecini diyoruz . ${\ displaystyle A \ subseteq \ Sigma ^ {l}}$ ${\ displaystyle \ {{\ downarrow} X | X \ subseteq A \}}$ ${\ displaystyle A}$ ${\ displaystyle {\ mathcal {S}} (A)}$