13-ma'ruza. Genetik algoritmlar

7. Genetik algoritmlar haqidagi asosiy teorema

GAning ishlashini yaxshiroq tushunish uchun sxema tushunchasidan foydalaniladi va GAlar bilan bog'liq bo'lgan va sxema teoremasi deb nomlangan asosiy teorema shakllantiriladi [13-17]. Ba'zi umumiy xususiyatlarga ega, ya'ni bir- biriga o'xshash bo'lgan xromosomalar to'plamini aniqlash uchun sxema tushunchasi kiritildi. Agar allellar 0 yoki 1 qiymatlarni qabul qilsa (ikkilik alfavitga

ega bo’lgan xromosomalar qaralsa), u holda bu sxema ba'zi oldindan belgilangan joy(joy)larda 0 yoki 1 qiymatlardan iborat xlorosomalar to’plamini ifodalaydi.
Sxemalar ko'rib chiqayotganda kengaytirilgan 0,1,  alfavitdan foydalanish
qulay bo’lib, unda 0 va 1 ga qo'shimcha ravishda har qanday etarli, ya’ni 0 yoki 1 qiymatni bildiruvchi qo'shimcha * belgi kiritiladi. Ma'lum bir joydagi * belgisi "ahamiyatsiz" degan ma'noni anglatadi. Masalan,
1 01 1001,1101
 0 11 00011,00111,10011,10111
Xromosoma ushbu sxemaga tegishli deb hisoblanadi, agarda har bir
^{j ( j  1,2,...l, bu erda} l ^{- xromosomaning uzunligi) - joy (lokus) uchun} xromosomaning j - joyini egallagan belgi sxemaning j - joyini egallagan *
belgiga mos kelsa, ya’ni * belgiga 0 ham va 1 xam mos kelsa. Xuddi shunday xromosoma sxemaga mos keladi va xromosoma sxemani ifodalaydi degan tasdiq xam o’rinli hisoblanadi. Ta’kidlash mumkinki, agar sxemada mta * belgilar
mavjud bo'lsa, unda ushbu sxema 2^m ta xromosomalarni o'z ichiga oladi. Bundan
tashqari ^L uzunlikga ega bo’lgan har bir xromosoma 2^L ta sxemalarga tegishli

bo’ladi. 13.10 va 13.11-jadvallarda mos ravishda 2 va 3 uzunlikdagi xromosomalar tegishli bo'lgan sxemalar ko'rsatilgan.
13.10-jadval. 2 uzunlikdagi xromosomalar tegishli bo'lgan sxemalar.

Holatlar	Sxemalar
	1	2	3	4
00	**	*0	0*	00
01	**	*1	0*	01
10	**	*0	1*	10
11	**	*1	1*	11

13.11-jadval. 3 uzunlikdagi xromosomalar tegishli bo'lgan sxemalar.

Holatlar	Sxemalar
	1	2	3	4	5	6	7	8
000	***	**0	*0*	0**	*00	0*0	00*	000
001	***	**1	*0*	0**	*01	0*1	00*	001
010	***	**0	*1*	0**	*10	0*0	01*	010
011	***	**1	*1*	0**	*11	0*1	01*	011
100	***	**0	*0*	1**	*00	1*0	10*	100
101	***	**1	*0*	1**	*01	1*1	10*	101
110	***	**0	*1*	1**	*10	1*0	11*	110
111	***	**1	*1*	1**	*11	1*1	11*	111

Demak 2 uzunlikdagi xromosomalar 4 ta turli sxemalarga va 3 uzunlikdagi xromosomalar 8 ta turli sxemalarga mos keladi.
GA eng moslanuvchanlik xromosomalar transformatsiyasi prinsipiga
asoslanadi. Aytaylik P(0) - xromosomalarning boshlang'ich populyatsiyasini va
^{P(k) - algoritmning} k ^{-iteratsiyasida populyatsiyani anglatsin. Har bir}
P(k)(i  1,2,...) populyatsiyadan eng yaxshi moslanuvchanlikga ega bo'lgan
xromosomalar tanlov usuli bilan tanlanadi va ular M (k) - OOPga kiritiladi. Undan

keyin
M (k)
populyatsiyadagi xromosomalarni ota-ona juftligiga birlashishi va P_c

ehtimollik bilan ChOni bajarilishi, shuningdek P_m
ehtimollik bilan mutatsiyalash

operatsiyasini bajarilish natijasida
M (k)
populyatsiyadagi xromosomalarning

avlodlarini o'z ichiga oluvchi yangi
P(k 1) populyatsiya shakllantiriladi.

Shuning uchun yaxshi echimni ifodalovchi har qanday sxema uchun ushbu sxemaga mos keladigan xromosomalar sonining iteratsiyalar soni k ning oshishi bilan oshishi maqsadga muvofiqdir.
GAda sxemalarni o’zgartirishga 3 ta omil ta'sir qiladi: xromosomalarni seleksiyalash, chatishtiruv va mutatsiyalash. Ularning har birining ta'sirini alohida bir sxema bo'yicha kutiladigan namunalar sonini ko'paytirish nuqtai nazaridan tahlil qilinadi.
Qaraladigan sxema S bilan belgilanadi va ushbu sxemaga mos keladigan

P(k)
populyatsiya xromosomalari soni
n^ (S, k) bilan belgilanadi. Shuningdek

n^ (S, k) ⁿⁱ mumkin.
P(k)  S
to'plamning elementlari soni (ya'ni asosiy) deb hisoblash

Endi GAda sxemalarni o’zgartirishga ta'sir qiladigan xromosomalarni
seleksiyalash, chatishtiruv va mutatsiyalash operatsiyalarini birma-bir qarab chiqish mukin.

1. 
   Xromosomalarni seleksiyalash. Bu operatsiyaning bajarilishi natijasida
   

P(k) populyatsiyadagi xromosomalar (13.4) ifoda bilan aniqlangan ehtimollik

bilan
M (k)
ota-ona juftligiga nusxalanadi.
F (S, k)
^bilan S ^{sxemaga mos}

keluvchi
P(k)
populyatsiyadagi xromosomlarning moslanuvchanlik

^{funksiylarining o’rtacha qiymati belgilanadi. Agar} S ^{sxemaga mos keluvchi P(k)}

populyatsiyada xromosomlar soni
P(k) : S
 x₁ ,..., x _

n ( S ,k )
^{bo’lsa, u holda har} S ^{sxemaga mos keluvchi har bir xromosomaning sifatini} (yaroqliligini)
_l 

f (x_i )  _ x_ik
k 1
(i  1, n^ (S, k))

hisoblash mumkin, bunda
l^ (l^  l) ^- S ^{sxemaga mos keluvchi xromosomaning}

uzunligi bo’lib, bu uzunlik xromosomadagi doimiy 0 va 1 lar soni bilan belgilanadi.

^Endi S ^{sxemaga mos keluvchi} umumiy bahosi (yig’indisi)
P(k)
populyatsiyada xromosomlarning

F(S, k) 
n^ ( S ,k )
_ f (x_i )
n^ (S, k) ^{. (13.12)}

aniqlanadi, bunda
deb ataladi.
F (S, k)
i1
qiymat S sxemaning k-iteratsiyadagi moslanuvchanligi

N quvvatga ega bo’lgan
P(k)
populyatsiyadagi xromosomalar

moslanuvchanlik funksiylarining yig’indisini
N ( k )
Q(k)
bilan belgilasak, u holda

Q(k) 

i1
f (x_i ) . (13.13)

k -iteratsiyadagi
P(k)
populyatsiyada xromosomalar moslanuvchanlik

funksiylarning o’rtacha qiymatini aniqlanadi


F(k)
bilan belgilanadi va u quyidagicha

F (k ) 
¹ Q(k ) . (13.14)
N

Aytaylik
x^{( k ) - M (k)}
OOPning elementi bo’lsin. Har bir
x^{(k )}  M (k)
va har

r

r
bir i  1,..., n^ (S, k)
bo’lganda
(k )

x
r
 x_i
bo’lish ehtimoli
f (x_i ) /
f (k) munosabat

bilan aniqlanadi. Shuning uchun M (k) populyatsiyada kutiladigan xromosomalar

soni x_i
ga teng va u quyidagini tashkil qiladi

_N f (x_i ) _
Q(k)
f (x_i ) _.
F (k)

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

olinishi kutiladigan xromosomalar soni (13.12) dan quyidagicha aniqlanadi

n^ ( S ,k )