13-ma'ruza. Genetik algoritmlar



i1
^{f (xi )}  n^ (S, k)
F (k)
F (S, k)



F (k)

Agarda
M (k)
populyatsiyasidagi har bir xromosoma bir vaqtda
P(k)

populyatsiyaga ham tegishli bo’lsa, u holda
P(k)  S
to'plamni tashkil etuvchi

xromosomalar
M (k)
populyatsiyasiga kiritish uchun
P(k)  S
to'plamdan tanlab

olingan xromosomalar hisoblanadi.

Aytaylik
^{b(S, k)-} S ^{sxemaga mos keluvchi (ya’ni}
P(k)  S
to’plam

elementlari soni)
M (k)
populyatsiyasidagi xromosomalar soni bo’lsin. U holda

^{yuqoridagi mulohazalardan quyidagi xulosaga kelinadi, ya’ni} S ^{sxemaga mos}

keluvchi
M (k)
populyatsiyasida kutiladigan xromosomalar sonining
b(S, k)

qiymati quyidagi ifoda bilan aniqlanadi
Eb(S, k)  n^ (S, k) ^{F (S, k) . (13.15)}
F (k)
^{Bundan kelib chiqadiki, agar} S ^{sxema MF qiymati o'rtacha qiymatdan yuqori} bo'lgan xromosomalarni o’z ichiga olsa (ya'ni, S sxemaning k -iteratsiyadagi

moslanuvchanligi
P(k)
populyatsiyadagi xromosomalar MFning o'rtacha

qiymatidan katta bo'lib chiqsa, ya’ni
F(S, k)
F(k)  1
bo’lsa), u holda S

sxemaga mos keladigan sxemaga mos keladigan
M (k)
P(k)
^{populyatsiyadan kutilgan xromosomalar soni} S
populyatsiyadagi xromosomalar sonidan ko'proq

bo'ladi. Shuning uchun ta’kidlash mumkinki - seleksiyalash (tanlash) moslanuvchanligi "o'rtacha darajadan yaxshiroq" bo'lgan sxemalarning tarqalishiga va "yomonroq" moslanuvchanlikga ega bo'lgan sxemalarning yo'qolishiga sabab bo'ladi.
M (k) populyatsiyasidagi xromosomalarda chatishtiriv va mutatsiyalash
genetik operatorlarining ta'sirini tahlil qilishga o'tishdan oldin S sxemani tartibi va qamrovi tushunchalari aniqlanadi [17]. Buning uchun ^L bilan xromosomalarning S sxemaga mos keladigan uzunligi belgilanadi.
Sxema tartibi. S sxemaning tartibi ^{h(S )} bilan belgilanadi va u S
sxemadagi doimiy joylar soni, ya'ni ^0,1, ^ alfavitdagi nollar va birlar soni bilan
^{aniqlanadi. Agar} S ^{sxemaning 0,1,  alfavitida}  ^{lar sonini l}_ ^{(S ) bilan}

belgilasak, u holda S sxemani
h(S )
tartibini quyidagicha aniqlash mumkin

h(S)  l  l_ (S) . (13.16)

13.7-misol. Aytaylik bo’lsin:
l  6
uzunlikga ega bo’lgan S sxemalar berilgan

S₁  (10 1 0);
S₂  (011 0);
S₃  (1 1 0);
S₄  (10 );

S₅  (1 ); S₆  ().
U holda (13.16) ifodadan foydalanib har bir S sxemaning tartibi quyidagicha aniqlanadi:

h(S₁ )  (10 1 0)  4; h(S₂ )  (011 0)  4; h(S₃ )  (1 1 0)  3;
h(S₄ )  (10 )  2; h(S₅ )  (1 )  1; h(S₆ )  ()  0.
^Demak S ^{sxemaning h(S ) tartibi har doim 0, L intervaldagi butun son} hisoblanadi.
^{Sxema qamrovi.} S ^{sxema qamrovi deganda sxemaninig uzunligi d (S)
tushuniladi va u 0,1,  alfavitdan iborat} l ^uzunlikdagi S ^{sxemaning 0 yoki 1}
bilan tugagan ong oxirgi joyi bilan 0 yoki 1 bilan boshlangan chap joyi orasidagi masofa (farq) bilan aniqlanadi.
^{Agar 0,1,  alfavitdan iborat} l ^uzunlikdagi S ^{sxemaning 0 yoki 1 bilan}

tugagan ong oxirgi joyini
l_o'ng (S)
^{bilan va} S ^{sxemaning 0 yoki 1 bilan boshlangan}

chap joyini
l_chap (S)
^{bilan belgilasak, u holda} S ^sxemani
d (S)
qamrovini

quyidagicha aniqlash mumkin
d(S)  l_o'ng (S)  l_chap (S)

(13.17)

13.8-misol. Aytaylik berilgan bo’lsin:
l  [3,6]
oraliqdagi uzunlikga ega S sxemagalar

S₁  (110);
S₂  (0 1);
S₃  (10  01);
S₄  (); S₅  (1);

S₆  (0);
Sx₇  (10100);
S₈  (0000);
S₉  (1111).

^{U holda (13.17) ifodadan foydalanib har bir} S ^{sxemaning qamrovi} quyidagicha aniqlanadi:
d (S₁ )  (110)  4 1  3; d (S₂ )  (0 1)  4  2  2;d (S₃ )  (10  01)  6  2  4;
d (S₄ )  ()  0  0  0; d (S₅ )  (1)  11  0; d (S₆ )  (0)  4  4  0;

d (S₇ )  (10100)  5 1  4; d (S₈ )  (0000)  4 1  3;
d (S₉ )  (1111)  4 1  3.

^Demak S ^{sxemaning d (S)}
qamrovi har doim 0, l 1 intervaldagi butun

son ifodalanadi. Ta’kidlash mumkinki, agar S sxema faqat doimiy 0 va 1 lardan iborat bo’lsa, u holda ushbu sxemaning qamrovi ( l 1) ga teng bo’ladi (13.8-

misolda
d (S₈ ) va
^{d (S}₉ ⁾ larga qarang). Shuningdek, S sxema faqat bitta doimiy 0

yoki 1 dan iborat bo’lsa, u holda ushbu sxemaning qamrovi 0 ga teng bo’ladi (13.8-

misolda
d (S₅ ) va
^{d (S}₆ ⁾ larga qarang). Xulosa qiladigan bo’lsak S sxemaning

qamrovi unda mavjud bo'lgan ma'lumotlarning mazmunini tavsiflaydi.

2. 
   Chatishtiruv operatsiyasi (ChO). GAdagi sxemalarni qayta ishlashga chatishtiruv operatsiyasining ta'siri haqida fikr yuritiladi. Avvalo shuni ta'kidlash mumkinki chatishtiruv jarayonida ba'zi sxemalar boshqalariga qaraganda yo’qolib
   

ketishga ko’proq duchor bo’ladi. Masalan,
S₁  1   0  va
S₂   01 

sxemalarni hamda ikkala sxemaga ham mos keladigan
x  [1001101]
xromosoma

ko'rib chiqiladi. Ko'rinib turibdiki
S ₂ sxemaning “omon qolish” imkoniyati S₁

sxemaga nisbatan ko’proq, chumki
S₁ sxemaning 1, 2, 3, 4 va 5 chatishtiruv

nuqtalarida "bo'linish" ga ko'proq moyillik mavjud bo’lib, bu bo’linish
S ₂ sxemada

faqat 3 chatishtiruv nuqtasini tanlaganda amalga oshadi. Shuning uchun ikkala

sxemaning ham qamroviga asosiy e’tibor qaratiladi, chunki sxemalar qamrovi chatishtiruv jarayoniga muhim ta’sir korsatadi.

ChOning
M (k)
populyatsiyasiga ta'sirini tahlil qilish jarayonida
P(k)  S

^{OOP to'plamidan olingan va} S ^{sxemaga mos keladigan ma'lum bir xromosoma}

ko'rib chiqiladi. Ushbu xromosomaning chatishtiruv uchun tanlanish ehtimoli
P_c ga

^{tengdir. Agar ushbu xromosoma avlodlaridan birortasi ham} S ^{sxemaga tegishli} bo'lmasa, u holda bu chatishtiruv nuqtasi ushbu sxemaning birinchi va oxirgi doimiy belgilari (0 yoki 1) o'rtasida bo'lishi kerak. Buning amalga oshish ehtimoli d (S) /(l 1) ga tengdir. Bundan quyidagi xulosalar chiqarish mumkin.
M (k)  S OOP to’plamidagi ba'zi xromosomaning chatishtiruv uchun
^{tanlanishi va uning avlodlaridan birortasi ham} S ^{sxemaga tegishli emasligi ehtimoli} yuqoridan

_P d (S)
(13.18)

c (l 1)
^{qiymat bilan chegaralangan bo’ladi. Ushbu qiymat} S ^{sxemani “omon qolmaslik} (yo’qolish)” ehtimoli deb ataladi.
M (k)  S populyatsiyasi to’plamidagi ba'zi xromosomaning chatishtiruv
uchun tanlanishi va chatishtiruv natijasida uning avlodlaridan ehg kamida bittasi S
sxemaga tegishli bo’lishligi ehtimoli quyidan

1  P
d (S)
(13.19)

c (l 1)
qiymat bilan chegaralangan bo’ladi. Ushbu qiymat S sxemani “omon qolishlik (yashahlik)” ehtimoli deb ataladi.
^{Ko'rinib turibdiki, agar berilgan xromosoma} S ^{sxemaga tegishli va u chatishtiruv uchun tanlangan bo'lsa hamda ikkinchi ota-ona xromosomasi ham} S sxemaga tegishli bo'lsa, u holda ularni ikkalasining avlodlari ham S sxemaga tegishli bo'ladi. (13.18) va (13.19) - ifodalar natijalari sxemani “yo'q qilish” yoki

“omon qolish” ehtimolligini baholashda S sxemani qamrovi ko’rsatkichi dolzarbligini tasdiqlaydi.
^{d (S)} ning

3.