13-ma'ruza. Genetik algoritmlar

Mutatsiyalash operatsiyasi. Endi mutatsiyalashning

M (k)
ota-ona juftligi

sohasiga ta'siri ko'rib chiqiladi. Mutatsiyalash operatori
P_m ehtimol bilan tasodifiy

ravishda xromosomaning ma'lum bir yoyidagi 0 qiymatini 1 ga va aksincha 1 qiymatini 0 ga o'zgartiradi. Korinib turibdiki, ushbu operatsiyadan so'ng xromosomaning joylaridagi barcha 0 va 1 lari o'zgarishsiz qolgandagina sxema mutatsiyalash natijasida omon qoladi.

Demak
M (k)  S
populyatsiyasi to’plamidan olingan va S sxemaga tegishli

bo'lgan xromosoma ushbu S sxemada shunda va faqat shundagina qoladi, agarda S sxemani joylaridagi doimiy 0 va 1 lariga mos keluvchi xromosomaning joylaridagi 0 va 1 laridan birortasi ham mutatsiyalash jarayonida o'zgarmasdan qolsa. Bunday

hodisaning amalga oshish ehtimolligi
(1 P )^{h(S )} ga teng bo’ladi. Ushbu natijani

m
quyidagi xulosa shaklida ifodalash mumkin.

M (k)  S OOP to’plamidan olingan ba’zi bir xromosomalarning
^{mutatsiyalash operatsiyasidan keyin} S ^{sxemaga tegishli bo'lish ehtimoli}

m
(1 P )^{h(S )}
ifoda bilan aniqlanadi. Ushbu qiymat mutatsiyalashdan keyingi “omon qolish” ehtimoli deb ataladi.
(13.20)
S ^sxemaning

Agar mutatsiylash ehtimoli
P_m kichik ( P_m
 1) bo'lsa, u holda (13.20) ifoda

^{bilan aniqlangan mutatsiyalashdan so'ng} S ^{sxemaning “omon qolish” ehtimoli}

taxminan quyidagi ifodaga teng deb taxmin qilinishi mumkin
1  P_m  h(s)

(13.21)

Agar
M (k)  S
^{populyatsiyasi to’plamidan olingan xromosoma} S

sxemaga mos keladigan avlodni beradigan bo'lsa, u holda ushbu xromosoma

P(k  1)  S
^{ga (yangi populyatsiyaga mos keladigan} S
sxemaga) tegishli

bo'lishini hisobga olganda (13.18) - (13.21) ifodalarda keltirilgan seleksiyalash, chatishtiruv va mutatsiyalashning birgalikdagi ta'sirining samarasi quyidagi ko'payish (reoroduksiya) sxemasining qurilishiga olib keladi [13]:

En^ (S, k  1) n^ (S, k) ^{F (S, k) }1  P


d (s) <sub>(1  P

)</sub>h( S )
(13.22)




F (k) ^ c ^{l 1 } m
(13.22) ifodadagi bog’liqlik ma'lum bir sxemaga mos keladigan
xromosomalar soni joriy populyatsiyadan keyingi populyatsiyaga o’tishda qanday o'zgarishini ko'rsatadi. Ushbu o'zgarish (13.22) ifodaning o'ng tomonida ko'rsatilgan

uchta omil tufayli yuzaga keladi, xususan:
F(S, k)
F(k) ^{MFning o'rtacha}

c
qiymatining rolini aks ettiradi, 1  P  d (s)
(l 1)
-chatishtiruvning ta’sirini

m
^{ko’rsatadi va} (1 P )^{h(S ) - mutatsiyalashning ta'sirini ko'rsatadi. Ushbu omillarning} har birining qiymati qanchalik katta bo'lsa, kelgusi populyatsiyada
^{xromosomalarning} S ^{sxemaga mos kelishlarini kutilgan soni shuncha katta bo'ladi.}
(13.21) ifodani e’tiborga olib, (13.22) ifodani quydagicha ifodalash mumkin

En^ (S, k  1) n^ (S, k) ^{F (S, k) }1  P ^{d (s)}  P h(s)^


(13.23)




F (k) ^ c ^{l 1} m ^
Katta populyatsiyalar uchun (13.23) ifodani quyidagicha approksimatsiy
qilish mumkin

n^ (S, k  1)  n^ (S, k) ^{F (S, k) }1  P ^{d (s)}  P h(s)^


(13.24)




F (k) ^ c ^{l 1} m ^{
(13.23) va (13.24) formulalardan kelib chiqadiki, keyingi avloddagi} S
sxemaga mos keladigan kutilayotgan xromosomalar soni ushbu sxemaga tegishli bo'lgan xromosomalarning haqiqiy soniga, sxemaning nisbiy moslanuvchanligiga hamda sxemaning tartibi va qamroviga bog'liqdir. Shunisi e'tiborga loyiqki, o'rtacha darajadan yuqoriroq hamda kichik tartibli va qamrovli sxemalar keyingi populyatsiyalarda ularning avlodlari sonining ko'payishi bilan tavsiflanadi. Ushbu o'sish ko’rsatkichli xarakterga ega bol’ib, u (13.15) ifodadan kelib chiqadi. Katta populyatsiyalar uchun (13.15) ifodani rekkurent bo’g’lanish ko’rinishga almashtirish mumkin [16]

n^ (S, k 1)  n^ (S, k) ^{F (S, k)}
F (k)
(13.25)

^Agar S
^{sxema o'rtacha darajadan}  %
yuqori moslanuvchanlikga ega deb

taxmin qilinsa, ya'ni

u holda (13.24) ifodani

F(S, k)  F(k)   F(k)^{, (13.26)}
k  o^{dan boshlanganda  vaqt bo’yicha o'zgarmaydu}

degan taxmin bilan (13.23) tengsizlikka almashtirganda quyidagi hosil qilinadi:
n^ (S, k)  n^ (S,0)(1  )^k ,

  (F(S, k)  F(k))/ F(k),

(13.27)

^{ya’ni o'rtacha ko'rsatkichdan yuqori bo'lgan sxema uchun} 
bo’ladi.

• 
  0 ^{va aks holda}   0
  

Tenglik (13.27) geometrik progressiyani tavsiflaydi. Bundan kelib chiqadiki, sxemalarning ko'payish jarayonida o’rtachadan yaxshiroq (yomonroq) sxemalar GAning navbatdagi iteratsiyalarida eksponent ravishda o’sib (kamayib) borish tartibida tanlanadi. Ta’kidlash mumkinki (13.15), (13.22) - (13.25) bog'liqliklar MF faqat musbat qiymatlarni oladi degan taxminga asoslangan. (13.22) - (13.24) ifodalardan olingan yakuniy natijalarni teorema shaklida shakllantirish mumkin. Bu GAlarning asosiy teoremasi bo’lib, u sxema haqidagi teorema deb nomlanadi [4].
Sxema haqidagi teorema. O'rtacha darajadan yuqori bo'lgan kichik tartibli sxemalar o’zining kichik qamrovi va MF bilan GAning keyingi avlodlarida o'zlarining namunalari sonini o’sishini yaqqol ko’rsatishini shakllantiradi.
Keltirilgan sxemalar to’g’risida teoremaning bilvosita natijasi sifatida g'ishtchalar (yoki qurilish bloklari haqida) gipotezasi deb nomlangan quyidagi farazni keltitish mumkin [14, 16], ya’ni GA moslanuvchanligi o'rtacha darajadan yuqori bo’lgan hamda kichik tartibli va kichik qamrovli yaxshi sxemalarni birlashtirib deyarli optimal natijaga erishishga intiladi. Bunday sxemalar g’ishtchalar (yoki qurilish bloklari) deyiladi.
Sxemalar haqidagi teorema asosida qurilish bloklari farazi shuning uchun taklif qilindiki, bunda chatishtiruv jarayonida ma’lumotlarni almashishda qatnashadigan kichik tartibli va kichik qamrovli sxemalar yordamida GAlar qidiruv fazosini tadqiq qiladi.
So'nggi yigirma yil ichida ushbu farazni qo'llab-quvvatlash uchun GAlarni qo'llash bo'yicha ko'plab maqolalar nashr etildi. Agar u to'g'ri deb hisoblansa, unda kodlash muammosi GA uchun hal qiluvchi ahamiyatga ega va kodlash kichik qurilish bloklari konseptsiyasini ifodalashi kerak bo'ladi. GAlarni boshqa an'anaviy usullarga nisbatan aniq ustunligini beradigan sifat, shubhasiz, juda ko'p sonli turli xil sxemalarni qayta ishlashga imkoniyat yaratadi.
13.6-misolni e’tiborga olib, quyidagi misolda GA asosida sxemalarni ishlash jarayoni tahlili keltiriladi [17].