13-ma'ruza. Genetik algoritmlar

13.2-misol. Berilgan
f (x)  x² , 0  x  31
(13.8-rasm) funksiyaning

optimal qiymatini GA yordamida qidirish jarayonini namoyish qilaylik.

13.8-rasm.
f (x)  x²
funksiyaning grafigi.

Misolda x o`zgaruvchi (xromosoma, individ)lar ikkilik bit satrlar ko`rinishida kodlanadi. Ularning uzunligi 5 ramzga teng: 0(00000) va 31(11111). Bu yerda

x  x₁ , x₂ ,..., x₃₂
o`zgaruvchilar masalaning parametrlari (qidirish doiraning

nuqtalari), ularning (0,1,2,…,31) qiymatlar to`plami esa qidirish doirasi va shu bilan birga masalaning mumkin bo`lgan yechimlari bo`ladi. Genotip bir xromosoma bilan ifodalangan. x parametrlarning 32 qiymatlaridan har biri masalaning yechimi (fenotipi) bo`ladi. Xromosomalar 5 gen(bit)lardan iborat. Ularning aniq
joy(lokus)dagi qiymatlari allellarni anglatadi. Populyatsiyadagi bo`lak
xromosomalarning moslanuvchanlik darajasi ularga muvofiq bo`lgan ^x
o`zgaruvchilar qiymatlari, ya’ni aniq genotiplarga muvofiq bo`lgan fenotiplari bilan

belgilanadigan
F (x)
funksiyasining qiymati orqali baholanadi.

Dastlabki populyatsiya uchun, masalan, 5 genlardan iborat bo`lgan ixtiyoriy to`plamdagi 4 ta xromosomani olamiz:

x₁  01101;
x₂  11000 ;
x₃  01000 ;
x₄  10011.

Bu esa masalaning yechimini topish jarayoni (uning kattaligi 32 ga teng) 4 nutqadan baravar boshlanishini anglatadi.
Tanlab olingan xromosomalarning yaroqlilik darajalarini topish uchun

ularning qiymatlariga muvofiq bo`lgan hisoblaymiz. Natijada
f (x)
funksiyaning qiymatlarini

f (x₁ ) 
f (01101)₂ 
f (13)₁₀
 13²  169;
f (x₂ ) 
f (11000)₂ 
f (24)₁₀
 24²  576;

f (x₃ ) 
f (01000)₂ 
f (8)  8²  64;
f (x₄ ) 
f (10011)₂ 
f (19)  19²  361.

10

10

4

baholashlarni hosil qilamiz. Aniqlangan qiymatlar asosida populyatsiyaning umumiy bahosi (yig’indisi)
F  _ f (x_i )  169  576  64  361  1170
i 1

hisoblanadi. Bundan
F_o'r  F
4  293 kelib chiqadi. Keyin (13.4) ifodaga asosan

barcha xromosomalarning ”Omon qolish” ehtimolini

P_c (x₁ ) 
P_c (x₃ ) 
f (x₁ )
f (x₃ )
F  169 1170  0.14;
F  64 1170  0.05;
4
P_c (x₂ ) 
P_c (x₃ ) 
f (x₂ )
f (x₂ )
F  576 1170  0.49;
F  361 1170  0.31

hisoblab olamiz. Bundan
F  _ P_c (x_i )  1 ^va
i 1
F_o'r  F
4  293
kelib chiqadi. Undan

keyin (13.5) ifodaga asosan har bir xromosomaning ”Omon qolish” ehtimoli -
kumulyativ (yaroqlilik) ehtimoli

P_qum (x₁ )  _ P_c (x _j )  0.14;
j 1
3



P_qum (x₂ )  _ P_c (x _j )  0.14  0.49  0.63;
j 1

P_qum (x₃ )  _ P_c (x _j )  0.14  0.49  0.05  0.68;
j 1

4



P_qum (x₄ )  _ P_c (x _j )  0.14  0.49  0.05  0.31  0.99
j 1
hisoblanadi.
Dastlabki populyatsiyaning yaroqliligini baholash natijalari (seleksiyalash- reproduksiya) 13.3-jadvalda keltirilgan.

13.3-jadval. Seleksiyalash (reproduksiyalash)

Xromosom a	Boshlang`ic h populyatsiy a	xi ning o’nli qiymat i	f (x)  x^2		PS (xi )		Pqum (xi )		Seleksiyalashda n keyingi sonlar
x1	01101	13	169		0,14		0,14		1
x2	11000	24	576		0,49		0,63		2
x3	01000	8	64		0,06		0,68		0
x4	10011	19	361		0,31		0,99		1
O`rtacha qiymatlar - Fo 'r				293		0,25				1
Maksimal qiymatlar - f max (x)				576		0,49				2
Yig`indilar - F				1170		1				4

Seleksiyalash uchun 0 va 1 oralig`idan 4 ta tasodifiy sonni tanlab olamiz. Faraz qilaylik biz 0,1; 0,25; 0,5; 0,8 sonlarini tanlab oldik. Ularni jadvalda ko`rsatilgan kumulyativ ehtimollar bilan solishtirib quyidagilarni hosil qilamiz:

qum
0.1  P¹ ;
1

P
qum
 0.25  P² ;
1

P
qum
 0.5  P² ;
3

P
qum
 0.8  P⁴ .

qum

qum

qum
Bu tengsizliklarning o`ng tomonlarini tahlil qilsak, quyidagini ko`ramiz: 1- va 4- xromosomalar yangi generatsiyada bitta joydan olib seleksiyalashdan o`tdi; 2- xromosoma(eng yuqori yaroqliligi bilan) ikki joyni (nusxani) oldi; 3- xromosoma

esa seleksiyalashdan o`tmadi (”Omon qolishmadi”), chunki
^{P2  0,63} va

qum

qum
P³  0,69
o`rtasida seleksiyalash uchun tanlab olingan tasodifiy son yo`q va

shuning uchun ularning orasida tegishli tengsizlik mavjud emas. Bu ko`rsatgichlar 13.3-jadvalning oxirgi ustunida keltirilgan.
Bundan keyin ChO bajariladi. Misol uchun 1ga teng bo`lgandagi
chatishtiruv ehtimoli ^(P_c ^{ 1)} ni olsak, u holda chatishtiruv jarayonida 4*1 = 4

xromosomalar qatnashadi. Ularni hamda tegishli juftlarni va nutqalarini tasodifiy ravishda tanlab olaylik.
^j - chatishtiruv

Faraz qilaylik x₁ va x₂ - xromosomalarni
j  4
nuqtada, x₃ va x₄ -

xromosomalar esa -
j  2
nutqada chatishtirish rejalashtirilgan bo’lsin. U holda

chatishtirish nuqtalarini quyidagicha belgilaymiz:

x₁  0110 | 1;
x₂  1100 | 0;
x₃  01 | 000;
x₄  10 | 011.

Seleksiyalash, chatishtiruv va yangi populyatsiyaning yaroqlilik darajasini baholash operatsiyalari natijalari 13.4-jadvalda keltirilgan.
13.4-jadval. Chatishtiruv.

Xro- mo- soma	Tanlan- gan nuqta	Seleksiyal ash-dan keyingi populyat- siya	Chatishtiruv uchun xromosoma- lar juftligi	Chatishtiruv- dan keyingi yangi populyatsiya	xi ning o’nli qiymati	f(x)=x^2 qiymati
x1	j=4	0110|1	x1 va x2	0110|0	12	144
x2	j=4	1100|0	x1 va x2	1100|1	25	625

x3	j=2	11|000	x3 va x4	11|011	27	729
x4	j=2	10|011	x3 va x4	10|000	16	256
O`rtacha qiymat - Fo 'r							439
Maksimal qiymat - f max (x)							729
Yig`indi - F							1754

13.3 va 13.4-jadvallarni solishtirsak yangi populyatsiyaning yaroqlilik darajasi oshganligini (1170 dan 1754 gacha) ko`ramiz.
Mutatsiyalash operatsiyasini o`tkazish uchun mutatsiyalash ehtimolini,

masalan,
P_m  0,05
ga teng qiymatida beraylik. Bunda 20 ta bitlar ichidan faqat

20•0,05=1 - bir bit o`zgariladi. Masalan, u 4 - xromosoma(satr) 3 - bit bo`lsin. Unda

mutatsiyalash natijasida o`zgatirilgan olamiz.
x₄^

 100100

ko`rinishdagi xromosomani

^{Masalan, 11011 xromosomasi uchun} j  3 ^{tanlanadi va uchinchi bit qiymatini}
teskariga almashtirgandan so'ng yangi 11111 xromosoma olinadi. Bizning misolimizning davomi 13.5-jadvalda mutatsiyalash keltirilgan bo’lib, genetik

operatorlardan foydalanish natijasida optimal echim
x  31
topilgan.

13.5-jadval. Mutatsiyalash.

Xromo- soma	Chatishtiruvdan keyingi yangi populyatsiya	Mutatsiyalashdan keyingi yangi populyatsiya	xi ning o’nli qiymati	f(x)=x^2 qiymati
x1	0110|0	01100	12	144
x2	1100|1	11001	25	625
x3	11|011	11111	31	961
x4	10|000	10000	16	256
O`rtacha qiymat - Fo 'r				496.5
Maksimal qiymat - f max (x)				961
Yig`indi - ^F				1986

Qaralgan misol sun'iy ravishda tanlanganligi sababli, biz bitta ketma-ketlikda optimal echimni topdik. Umumiy holda GA qidiruv jarayonining oxiri mezonlari bajarilguncha va masalaning echimi sifatida qabul qilingan so'nggi olingan avlodda eng yaxshi xromosoma aniqlanguniga qadar davometadi.