13-ma'ruza. Genetik algoritmlar

13.4-misol. Ko`p ekstremalli masalaning global opitmumini qidirsh misolini

ko`rib chiqaylik.
f (x)  x sin(10x)  1
ko`rinishdagi funksiya berilgan bo`lsin

(13.9-rasm). [-1,2] interval
f (x)
funksiyani maksimallashtiradigan

f (x₀ ) 
f (x),
x [1,2]) , x  x₀
o`zgaruvchini topish talab etiladi.

13.9-rasm.
f (x)  x sin(10x)  1
funksiya grafigi.

Bu funksiyaning ekstremumlarini topish uchun uning birinchi hosilasini olib, uni nolga tenglashtirish kerak
f ^' (x)  sin(10x) 10x  cos(10x)  0

yoki
tg (10x)  10x _.
Bu tenglamaning cheksiz ko`p yechimlari mavjud:

_{x } 2i 1 _{ }
ⁱ 20 ⁱ
i  1,2, uchun,

x₀  0,
x  ^{2i  1}   ,
ⁱ 20 ⁱ


i  1,2, uchun,

bu yerda ^i
- moddiy sonlarniyu 0 ga yaqinlashib kamayib ketadigan ketma-ketlikni

ifodalaydigan koeffisiyent ^{(i  1,2......... va i  1,2, uchun)} .

f (x)
funksiyasi ⁱ
- toq bo`lganda
^x_i uchun lokal maksimumga,
ⁱ - juft

bo`lganda ^x_i
uchun esa - lokal minimumga etib oladi.

Berilgan
x  [1,2]
intervalda
f (x)
funksiyaning maksimumi

^x19
 ³⁷  
₂₀ 19
 1,85  ₁₉
uchun hosil qilinadi. Bu yerda
f (x₁₉
)  f (1.85)  2.85

Ushbu masalani yechish uchun qo`llanilgan GAda parametrlarni kodlash uchun 22 bit tanlangan. Bu qo`yilgan yechimning aniqligi bilan belgilangan (o`nlik
verguldan keyin 6 razryad). Shuning uchun uzunligi 3ga teng bo`lgan ^{x  [1,2]}
interval 3·1000000 ga ekvivalent qismlarga bo`lingan. Yuqorida keltirilgan yechim ko`rib chiqilgan GA protseduralarining bajarilishi natijasida topiladi.

13.5-misol. Bir o’zgaruvchi maqsad funksiya
f (x)  2510x  46x²  x³
ifoda

bilan berilgan bo’lsin.
x [10, 53]
oralig'ida maqsad funksiyasining maksimal va

minimal qiymatini topish talab qilinadi.

1. Klassik optimallashtirish nazariyasidan foydalangan holda echimni aniqlash.

Shubhasiz, bu maslani matematik tahlil usullari yordamida echish mumkin.
Bu holda echimni topish algoritmi quyidagi bosqichlardan iborat:

1. 
   Birinchi hosilani aniqlash:
   

f ^(x)  10 92x  3x^{2 .}

2. 
   10  92x  3x²  0 kvadrat tenglamaning ildizlarini aniqlash:
   

x₁  30.558 , x₂  0.109 .

3. 
   Ikkinchi hosilani aniqlash:
   
4. 
   Ekstremum turini aniqlash:
   

f ^(x)  92  6x .

1
f ^(x ) 

2
f ^(x ) 
f ^(30.558)  92  6  30.558  91.348  0  min imum ;
f ^(0.109)  92  6  0.109  91.348  0  maksimum .

5. 
   Ekstremum nuqtalarida boshlang’ich funksiya qiymatlarini aniqlash:
   

1
f (x )  f (30.558)  251030.558 4630,558²  30.558³  14089^;

2
f (x )  f (0.109)  2510 0.109 46 0.109²  0.109³  25.5^.

6. 
   Funksiya qiymatlarini oraliq chegaralarida aniqlash:
   

f (10)  2510(10)  46(10)²  (10)³  5675^;
f (53)  251053 4653²  53³  20218^.

7. 
   Maqsad funksiyasining maksimal va minimal qiymatlarini aniqlash:
   

x  53 da
y_max  max( 14089, 25.5,  5675, 20218)  20218;

x  30.558 da
y_min  min( 14089, 25.5,  5675, 2021)  14089.

Hisoblash natijalari 13.10- asmdagi funksiya grafigi bilan tasvirlangan.

13.10-rasm.
f (x)  2510x  46x²  x³
funksiyasining
x [10, 53] oralig'idagi

grafigi.

2. GA yordamida echimni aniqlash.

Matematik tahlil usullari yordamida aniq echimni osongina topish mumkinligiga qaramay, quyida maqsad funksiyasining maksimal qiymatini hisoblashning bitta iteratsiyasi misolida GA yordamida masalaning echimini aniqlash keltirilgan.
Masalani (xromosomani) echish variantini berilgan oraliqda x ning butun sonli qiymatiga mos keluvchi bitli qator ko’rinishda ifodalash mumkin. Shunday qilib, gen - bu qatorning alohida bitta biti, xromosoma - bu 6 bitlik ketma-ketlik, genotip bitta xromosomadan iborat (genotip = xromosoma), fenotip - bu bitli qatorni o’nlikdagi ko’rinishi minus 10 dan iborat, ya’ni (x_i -10 ).
Aytaylik populyatsiya o’lchovi 4 ta xromosomani tashkil etsin, chatishtiruvlar soni - 2 ta, mutatsiyalashlar soni avlod uchun 1 ta nasldan iborat bo’lsin. Mutatsiyalash jarayoni satrning bitlaridan tasodifiy tanlangan bittasini teskariga aylantirishdan iborat.
Bu holda echimni topishning GA quyidagi bosqichlardan iborat:

1. 
   Dastlabki populyatsiyaning xromosomalari tasodifiy hosil qilinadi (13.6- jadval).
   

13.6-jadval. Seleksiyalash.

Xromosoma	Xromosomalarni ifodalash		Fenotip (xi)10 -10 )	Maqsaq funksiya qiymati f (x)  2510x  46x^2 x^3
	Bitli	O’nli
x1	011011	27	17	f (17)  8186
x2	100010	34	24	f (24)  12407
x3	000100	4	-6	f (6)  1355
x4	111001	57	47	f (47)  2704
O`rtacha qiymat - Fo'r  F 4				-4811
Maksimal qiymat - f max (x)				f (47)  2704
Minimal qiymat - fmin (x)				f (24)  12407
4 Yig`indi - ^F^ ^f^(^xi ^) i1				-19244

2. 
   Birinchi iteratsiya - bu chatishtiruv operatori. Chatishtiruv uchun tasodifiy ravishda ikkita juftlik (x₁, x₂) va (x₂, x₄) tanlangan bo’lsin. Har bir juftlikda qismqatorlarga bo'linish boshqa juftlikdan mustaqil va tasodifiy ravishda sodir bo'ladi. Avlodlar bir ota-onaning chap qismqatorini ikkinchisining o'ng qismqatorini birlashtirish orqali hosil qilinadi (13.7-jadval).
   

13.7-jadval. Birinchi iteratsiya - chatishtiruv.

Chatishtiruv juftliklari	Ota-ona			Avlod
	Tanlan- gan nuqta	Xromosoma	Bitli ifodasi		Xromosoma	Bitli ifodasi
x1 va x2	j=2	x1	01 | 1011		x5	01| 0010
	j=2	x2	10 | 0010		x6	10| 1011
x2 va x4	j=4	x2	1000 | 10		x7	1000| 01
	j=4	x4	1110 | 01		x8	1110| 10

3. 
   Birinchi iteratsiya - mutatsiyalash operatori. Mutatsiyalash uchun x₇ avlod tasodifiy tanlanadi va undagi inversiya uchun j=3 bit (razryad) tasodifiy tanlanadi. Natijada, x₇ avlod(xromosoma)ning kodi x₇ =100001 dan x₇ =101001 ga o'zgaradi.
   
4. 
   Birinchi iteratsiya - reduksiyalash operatori. Ota-onalar va avlodlardan eng yaxshi xromosomalarni seleksiyalashda populyatsiya sonini hisobga olgan holda maqsad funksiyasining maksimal qiymati bo’yicha amalga oshiriladi (13.8-jadval).
   

13.8-jadval. Birinchi iteratsiya - reduksiyalash.

Xromosoma	Xromosomalarni ifodalash		Fenotip (xi)10 -10 )	Maqsaq funksiya qiymati f (x)  2510x  46x^2 x^3
	Bitli	O’nli
Ota-onalar
x1	011011	27	17	f (17)  8186
x2	100010	34	24	f (24)  12407
x3	000100	4	-6	f (6)  1355
x4	111001	57	47	f (47)  2704
O`rtacha qiymat - Fo'r  F 4				-4811
Maksimal qiymat - f max (x)				f (47)  2704
Minimal qiymat - fmin (x)				f (24)  12407
4 Yig`indi - ^F^ ^f^(^xi ^) i1				-19244