13-ma'ruza. Genetik algoritmlar

Chatishtiruv - bu operatsiyaning bajarilishda seleksiyalash natjasida tanlab olingan xromosomalar ichidan tasodifiy ravishda juftli chatishtirish uchun

xromosomalarning tasodifiy soni saralab olinadi. Bu son oldindan berilgan ^P_c

chatishtirish ehtimolining qiymatiga bog`liq. Masalan, agar
^{Pc  0.25} va

populyatsiya kattaligi 16 ga teng bo`lsa, u holda har bir generatsiyada aynan 4 ta xromosoma chatishtiruv operatsiyasi(ChO)da qatnashadi. ChO quyidagicha

bajariladi: agar chatishtirishga tasodifiy ravishda
^xm va
^xk xromosomalar tanlab

^{olingan bo`lsa va xromosoma uzunligi</sup> l <sup>ga teng bo`lsa, u holda tasodifiy sonlar}

x
datchigi j(1  j  l) tasodifiy sonni chiqaradi ( ^j - chatishtirish nuqtasi). Shu

nutqadan xromosomalar kesiladi va
'

x
_m va
^' avlodlarni( ^x va
^x_k - ota-

k

m
onalardan) olish uchun ularning o`ng qismlari o`rnilari almashtiriladi.
Faraz qilaylik
x_m  (1101101)
x_k  (1110010)

va tasodifiy son
j  3 . Unda chatishtirish natijasida
^x_m va ^x_k
avlodlari

m

x
^'  (110 : 0010)

k

x
^'  (111:1101)
ko`rinishni oladi.
Shu operatsiyani boshqa tanlangan juftlar uchun bajarib, chatishtirish jarayoni tugatiladi. Olingan yangi avlodlarni, ota-onalari bilan birga yangi populyatsiya tarkibiga kiritadi.
Seleksiyalash yo'li bilan tanlangan xromosomalarga genetik operatorlarni qo'llash oldingi bosqichda yaratilgan OOPdan naslning yangi populyatsiyasini shakllantirishga olib keladi.
Klassik GAda ikkita asosiy genetik operator ishlatiladi: chatishtiruv operatori va mutatsiyalash operatori. Ammo shuni ta'kidlash kerakki, mutatsiyalash operatori chatishtiruv operatoriga nisbatan ikkinchi darajali rol o'ynaydi. Bu shuni anglatadiki, klassik GAda chatishtiruv deyarli har doim amalga oshiriladi, mutatsiyalash esa juda kam uchraydi. Odatda chatishtiruv ehtimoli ancha yuqori

(odatda
0.5  P_c (x_i )  1
) va mutatsiyalash ehtimoli esa juda kichik (ko'pincha

1. 
    P_m (x_i )  0.1) bo’ladi. Bu mutatsiyalashlar nihoyatda kam uchraydigan tirik organizmlar olamiga o'xshashlikdan kelib chiqadi [17].
   

Chatishtiruv operatori. Chatishtiruvning birinchi bosqichida ota-onalar populyatsiyasidan juft xromosomalar tanlanadi. Bu vaqtincha populyatsiya bo'lib, seleksiyalash natijasida tanlangan va naslning yangi populyatsiyasini shakllantirish uchun chatishtiruv va mutatsiyalash operatorlari tomonidan keyingi o'zgarishlarga mo'ljallangan xromosomalardan iborat bo’ladi. Ushbu bosqichda OOPdan

xromosomalar juftlarga birlashtiriladi. Bu chatishtiruv
P_c (x_i ) ehtimoli bo'yicha

tasodifiy ravishda amalga oshiriladi. Bundan keyin shu tarzda tanlangan har bir ota- ona juftligi chatishtiruv nuqtasini aniqlash uchun xromosomadagi gen(lokus)ning ^{joylashuvini almashtiradi. Agar har bir ota-onaning xromosomasi} l ^{ta genlardan iborat bo'lsa, u holda chatishtiruv nuqtasi} l ^{sonidan kichik natural son bilan}

ifodalanadi. Shuning uchun chatishtiruv nuqtasini belgilash
[1, l 1]
oraliqdan

tasodifiy sonni tanlashga keltiriladi. Ota-ona xromosomalarining juftligini chatishtiruv natijasida quyidagi juft avlodlar olinadi [17]:

1. 
   xromosomasi 1 dan I _k
   

gacha bo'lgan joylarda birinchi ota-onaning

^{genlaridan va ( I} _k ^{+1) dan} l ^{gacha joylarda ikkinchi ota-onaning genlaridan iborat} bo'lgan avlod;

2. 
   xromosomasi 1 dan I _k
   

gacha bo'lgan joylarda ikkinchi ota-onaning

^{genlaridan va ( I} _k ^{+1) dan} l ^{gacha joylarda birinchi ota-onaning genlaridan iborat} bo'lgan avlod;
Chatitiruv operatorining ishlashi 13.2, 13.5, 13.6, 13.9 - misollar bilan
namoyish etiladi.

6. 
   Mutatsiyalash - bu yangi populyatsiyaning shakllantirish bo’lib, u tabiiy genetik mutatsiyalashga o`xshash bo’ladi. Bu operatsiya xromosomaning bir genini (bitini) o`zgartiradi. Mutatsiyalash ehtimoli ^P_m tasodifiy ravishda oldindan beriladi. Bu son mutatsiyalash uchun mo`ljallangan xromosomalar sonini belgilaydi. Masalan,
   

agar
P_m  0,05
va populyatsiya kattaligi 20 ga teng bo`lsa, u holda mutatsiyalashda

2. 
   xromosoma
   

(20 * 0,05  1)
qatnashadi. Agar mutatsiyalash uchun

x_k  (1110010)
xromosoma tanlangan bo`lsa, u holda
j(1 
j  l)
tasodifiy

sonni chiqaradi. Uning qiymati bo`yicha 1 dan 0 ga yoki 0 dan 2 ga o`zgariladigan

xromosoma genining tartibi belgilanadi. Masalan, agar
j  1
bo`lsa, u holda

x
xromosomaning faqat birinchi genining qiymati 1dan 0ga o`zgariladi va natijada