13-ma'ruza. Genetik algoritmlar

Avlodlar

x5	010010	18	8	f (8)  2327
x6	101011	43	33	f (33)  13802
x7	101001	41	31	f (31)  14080
x8	111010	58	48	f (48)  5113

O`rtacha qiymat - Fo'r  F 4	-6274
Maksimal qiymat - f max (x)	f (48)  5113
Minimal qiymat - fmin (x)	f (31)  14080
8 Yig`indi - ^F^ ^f^(^xi ^) i4	-25096

Shunday qilib, birinchi iteratsiya natijalariga ko'ra optimal echimni (ikkinchi iteratsiya) izlashni davom ettirish uchun quyidagi populyatsiya olinadi (13.9-jadval).
13.9-jadval. Ikkinchi iteratsiya.

Xromosoma	Xromosomalarni ifodalash		Fenotip (xi)10 -10 )	Maqsaq funksiya qiymati f (x)  2510x  46x^2 x^3
	Bitli	O’nli
x3	000100	4	-6	f (6)  1355
x4	111001	57	47	f (47)  2704
x5	010010	18	8	f (8) -2327
x8	111010	58	48	f (48)  5113
O`rtacha qiymat - Fo'r  F 4				1034
Maksimal qiymat - f max (x)				f (48)  5113
Minimal qiymat - fmin (x)				f (8)  2327
4 Yig`indi - ^F^ ^F^(^xi ^) i1				4135

Bitta iteratsiyada populyatsiya sifati sezilarli darajada oshdi. Agar boshlang'ich populyatsiyada maqsad funksiyasining o'rtacha qiymati -4811 va uning minimal qiymati -12407 tashkil qilgan bo'lsa, u holda birinchi iteratsiyadan keyin populyatsiyada o'rtacha qiymat 1034 ga, minimal qiymati esa -2327 ga teng

bo’ldi. Optimal echim
f (53)  20218
bo’lganda (analitik echimga qarang) maksimal

qiymat
f (47)  2704
dan
f (48)  5113
gacha oshdi. Shunday qilib, ushbu misol

umuman populyatsiyani yaxshilash jarayonini va eng yaxshi echimni aniq aks ettiradi.

6. Klassik genetik algoritmning bajarilishini tasvirlash

4 - paragrafda tasvirlangan klassik GAning ishlash jarayonini sodda misol yordamida ko'rib chiqamiz [15]. Buning uchun klassik GAning 13.7-rasmda keltirilgan blok-sxemasidan foydalanamiz.

Maksimal birliklar soniga ega bo'lgan xromosomalarni topishdan iborat bo'lgan juda soddalashtirilgan va ancha sun'iy misolni ko'rib chiqamiz.

13.6-misol. Aytaylik, xromosomalar 12 ta gendan iborat bo’lsin va populyatsiya 8 xromosomani o’z ichiga olsin. Tushunarliki eng yaxshi xromosoma 12 ta birlik(gen)dan iborat bo’ladi. GA yordamida ushbu masalani echish jarayoni qanday bajarilishining bosqichlarini ketma-ket ko'rib chiqamiz.

1. 
   Initsializatsiyalash - xromosomalarning boshlang'ich populyatsiyasini seleksiyalashni amalga oshiradi. 12 bit uzunlikdagi 8 ta ikkilik ketma-ketlikni tasodifiy ravisрda dastlabki xromosomalar(bit satrlar, string-xromosomlar, xromosomalar)ning populyatsiyasini shakllantirishdan iborat. Bunga, masalan, tanga tashlash orqali erishish mumkin (96 martadan tanganing "gerb" tomoni tushsa 1 qiymat va "raqam" tomoni tushsa 0 qiymat yoziladi). Shunday qilib, boshlang'ich populyatsiyani shakllantirish mumkin [17]:
   

x₁  [111 0 0 11 0 0 1 0 1];
x₂  [0 0 11 0 0 111 0 1 0];
x₃  [0 111 0 111 0 0 11];
x₄  [0 0 1 0 0 0 1 0 1 0 0 0];
x₅  [0 1 0 0 0 11 0 0 1 0 0];
x₆  [0 1 0 0 11 0 0 0 1 0 1];
x₇  [1 0 1 0 11 0 11 0 11];
x₈  [0 0 0 0 1 0 1111 0 0].

(13.7)

2. 
   Baholash - populyatsiyada xromosomalarning yaroqliligini baholashni amalga oshiradi. Bu bosqichda qaralayotgan misolda eng ko'p birlarni o'z ichiga olgan xromosomani topish masalasi echiladi. Shuning uchun MF xromosomadagi birlar sonini aniqlaydi. MFni F bilan belgilaymiz. U holda (13.7) ko’rinishda hosil qilingan boshlang’ich populyatsiyadan har bir xromosoma uchun F funksiyaning qiymatlari quyidagicha aniqlanadi:
   

f (x₁ )  7;
f (x₅ )  4;
f (x₂ )  6;
f (x₆ )  5;
f (x₃ )  8;
f (x₇ )  8;
f (x₄ )  3;
f (x₈ )  5.
(13.8)

x₃ va x₇
xromosomalar eng katta qiymatlarga ega bo’lgan moslanuvchanlik

funksiyalari bilan tavsiflanadi. Ushbu populyatsiyada ular masalani echishda eng yaxshi nomzodlar hisoblanadi. Agar GAning blok-sxemasiga muvofiq (13.1-rasm) algoritmni to'xtatish sharti bajarilmasa u holda keyingi qadamda (13.7) ko’rinishdagi populyatsiyadan yangi xromosomalarni seleksiyalash amalga oshiriladi.

3. 
   Seleksiyalash-xromosomalarni tanlashni ta’minlaydi. Xromosomalarni tanlash ruletka usuli yordamida amalga oshiriladi. (13.3), (13.4) va (13.5) formulalar asosida (13.7) ko’rinishdagi boshlang’ich populyatsiyadan foizlarni
   

q(x₁ )  15,22%;
q(x₅ )  8,70%;
q(x₂ )  13,04%;
q(x₆ )  10,87%;
q(x₃ )  17,39%;
q(x₇ )  17,39%;
q(x₄ )  6,52%;
q(x₈ )  10,87%.
(13.9)

hisoblaymiz va foizlarda hosil qilingan qiymarlarga ruletka g’ildiraklarining mos sektorlarini hosil qilamiz (13.11-rasm).
Ruletka g'ildiragi bilan jarayonni amalga oshirish g'ildirakdagi tegishli sektorni ko'rsatadigan [1,100] intervaldan raqamni, ya’ni aniq xromosamani tasodifiy tanlashga keltiriladi. Aytaylik, quyidagi 8 ta raqam
79 44 9 74 44 86 48 23.
tasodifiy tanlangan bo’lsin. Bu raqamlar xromosomalarni tanlashni anglatadi va

ularga mos ravishda 8 ta tanlanadi.
x₇ x₃
x₁ x₇
x₃ x₇
x₄ x₂
xromosoma

13.11-rasm. 13.6-misolda seleksiyalashni amalga oshirish uchun ruletka g’lidiraklaridan foydalanish.

Ko'rinib turibdiki x₇
xromosoma uch marta va
x₃ xromosoma ikki marta

tanlangan. Ta’kidlaymizki, (13.8) formulada aynan x₇
va x₃
xromosomalarning MF

eng katta qiymatlarga ega. Shu bilan birga eng past MF qiymatiga ega bo'lgan x₄
xromosoma ham tanlangan. Shu tarzda tanlangan barcha xromosomalar ota-ona birlashmasiga (roditelskiy pulga) kiritilgan.

4. 
   Chatishtiruv - genetik operatorlarni qo’llashni amalga oshiradi. Faraz qilaylik seleksiya jarayonida tanlangan xromosomalarning birortasi ham mutatsiyalashga uchramayapti va ularning hammasi chatishtiruv uchun mo'ljallangan xromosomalar populyatsiyasini tashkil qiladi. Bu chatishtiruv
   

ehtimolini
P_c (x_i )  1
va mutatsiyalash ehtimoli
P_c (x_i )  0
anglatadi. Aytaylik

ushbu xromosomalardan tasodifiy ravishda ota-onalarning juftliklari shakllantirilgan bo’lsin [17]:

x₂ va
x₇ ;
x₁ va
x₇ ;
x₃ va
x₄ ;
x₃ va
x₇ .

Tasodifiy ravishda birinchi
x₂ va x₇
juftlik uchun
I _k  4 , ikkinchi
x₁ va x₇

juftlik uchun
I _k  3 , uchinchi
x₃ va x₄
juftlik uchun
I _k  11 va to’rtinchi
x₂ va x₇

juftlik uchun
^I _k ^{ 5} chatishtiruv nuqtalari tanlangan bo’lsin.

Bu holda chatishtiruv jarayoni 13.12-rasmda ko’rsatilgandek amalga oshiriladi. Chatishtiruv operatorining bajaruilshi natijasida 4 ta avlodlar juftligi hosil bo’ladi.

13.12-rasm. 13.6 -misolda xromosomalarni chatishtiruv jarayoni.

Agar chatishtiruv uchun xromosomalar juftligini tasodifiy tanlashda
x_{3 ni} x₄

bilan hamda
^x₃ ni
^x₇ bilan birlashtirish o’rniga
^x₃ ni
^x₃ bilan hamda
^x₄ ni
^x₇ bilan

birlashtirilganda va boshqa juftliklar o'zgarmasdan qoldirilgan bo’lsa, u holda
^x₃ ni

^x₃ bilan chatishtiruv natijasi tasodifiy tanlanadigan chatishtiruv nuqtalaridan qat'iy
nazar ikkita bir xil xromosomalarga olib kelar edi. Bu ota-onalariga o’xshash (bir xil) ikkita avlodni hosil bo'lishini anglatadi. Ta’kidlaymizki, bunday holat MFning qiymati eng yuqori ko'rsatkichiga ega bo'lgan xromosomalar uchun o’rinli bo’ladi va shuning uchun aynan shunday xromosomalar yangi populyatsiyaga o'tish uchun eng katta imkoniyatga ega bo’ladi.

5. 
   Mutatsiyalash-yangi populyatsiyalarning shakllanishini amalga oshiradi. 13.12-rasmda keltirilgan ChOning bajarilishi natijasida quyidagi avlodlar populyatsiyasini hosil qilamiz: