13-ma'ruza. Genetik algoritmlar

Baholash - olingan xromosomalarning moslashuvchanlik darajasini, ya’ni ularning yaroqliligini aniqlashdir. Bular xromosomalarning sifatini (yaroqliligini)

baholash(masalan, optimallashtiriladigan)da
f (x)
funksiyani optimallashtirish

nuqta(xromosoma)lardagi
f (x₁ ),
f (x₂ ),...,
f (x_n )
qiymatlarini


l
f (x_i )  x_ik (i  1, n)
k 1

hisoblash yo`li bilan aniqlanadi, bunda
populyatsiyaning umumiy bahosi (yig’indisi)
n
l xromosomaning uzunligi. Keyin

F  _ f (x_i )
i 1
(13.3)

hisoblanadi, bu yerda
f (x_i )  x_i
xromosomaning sifatini baholash funksiyasi.

Populyatsiyada xromosomalar moslanuvchanlik funksiylarning o’rtacha

qiymatini
^Fo 'r
bilan belgilanadi va u quyidagicha aniqlanadi

F_{o 'r}  F n
Bundan keyin (13.3)ni hisobga olib har bir xromosomaning ”Omon qolish”
ehtimoli

hisoblanadi.
P_c (x₁ ) 
f (x₁ ) F ;
P_c (x₂ ) 
f (x₂ ) F ;
... ;
P_c (x_n ) 
f (x_n ) F
(13.4)

Keyin (13.4) nisobga olib har bir xromosomaning kumulyativ deb ataladigan
”Omon qolish” ehtimoli - yaroqliligini baholash

P_kum (x₁ )  P_c (x₁ );
amalga ohiriladi.
P_kum (x₂ )  P_c (x₁ )  P_c (x₂ ); . . . ;



P_kum (x_n )  _ P_c (x_i )
i 1
(13.5)

Topilgan baholash qiymatlari oldingi popultsiya xromosomalarining tegishli baholashlar qiymatlari bilan solishtiriladi. Agar ularning farqi kichik(berilgan mumkin bo`lgan doirada) bo`lsa, u holda qidirish jarayoni to`xtatiladi. Bunday holat, qoida bo`yicha, qandaydir bir nechta, yoki oldindan berilgan generatsiyalar sonidan keyin kelib chiqadi. Aks holda navbatdagi seleksiyalash blokiga o`tiladi.
Populyatsiyada xromosomalarning yaroqliligini baholash ushbu populyatsiyaning har bir xromosomasi uchun MFni hisoblashdan iborat. Ushbu funksiya qiymati qanchalik katta bo'lsa, xromosomaning sifati shunchalik yuqori bo'ladi. MFning shakli hal qilinayotgan masalaning mohiyatiga bog'liq. MF har doim manfiy bo'lmagan qiymatlarni qabul qiladi va qo'shimcha ravishda optimallash masalasini hal qilish uchun ushbu funksiyani maksimal darajaga ko'tarish talab qilinadi deb taxmin qilinadi. Agar MFning asl shakli ushbu shartlarni qondirmasa, unda tegishli almashtirishlar amalga oshiriladi (masalan, funksiyani

minimallashtirish masalasini osongina maksimallashtirish masalasiga keltirish mumkin).

3. 
   Algoritmni to'xtatish shartini tekshirish. GAni to'xtatish sharti uning o'ziga xos qo'llanilishiga bog'liq. Optimallashtirish muammolarida, agar MFning maksimal (yoki minimal) qiymati ma'lum bo'lsa, u holda algoritm kutilgan optimal qiymatga talab qilingan aniqlikda ershgandan keyin to'xtashi mumkin. Algoritmni to'xtatish uning bajarilishi oldin erishilgan qiymatning yaxshilanishiga olib kelmasa ham sodir bo'lishi mumkin. Algoritm ma'lum bir belgilan vaqtdan keyin yoki ma'lum bir qator takrorlashni bajargandan so'ng to'xtatishi mumkin. Agar to'xtash sharti bajarilgan bo'lsa, u holda "eng yaxshi" xromosomani seleksiyalashning yakuniy bosqichiga o'tish amalga oshiriladi, aks holda keyingi seleksiyalash (tanlov) bosqichga o’tadi [17].
   
4. 
   Seleksiyalash - bu tabiiy genetik tanlashga o`xshash. Seleksiyalash natijasida yuqori yaroqli baholash qiymatlariga ega bo`lgan xromosomalar tanlab olinadi, chunki ularning ”Omon qolish” imkoniyati ko`proq bo`ladi.
   

P
Seleksiyalashni o`tkazish uchun tasodifli sonlar datchigi ^0,1 intervaldan ^r₁

tasodifiy sonni chiqaradi. Agar uning qiymati
k kum
 r₁
^{ Pk 1} intervalda bo`lsa, unda

kum
navbatdagi generatsiyaga
i

x
k 1
( ⁱ -generatsiya tartibi) xromosoma tanlab olingan deb

hisoblanadi. Ushbu tasodifiy soni bilan protsedura ⁿ marta takrorlanadi va natijada
navbatdagi generatsiyada ⁿ ta xromosomalar tanlab olinadi. Bu holatda yuqoriroq
yaroqli baholash qiymatlariga ega bo`lgan xromosomalarning yangi generatsiyada bir nechta nusxalari bo`lishi mumkin, kichik qiymatlarga ega bo`lganlarining esa - bitta ham nusxasi bo`lmasligi mumkin.
Xromosomalarning tanlovi keyingi populyatsiya uchun naslni, ya’ni keying avlodni yaratishda ishtirok etadigan xromosomalarning tanlanishidan (ikkinchi bosqichda hisoblangan MF qiymatlari asosida) iborat. Bunday tanlov tabiiy tanlanish prinsipiga muvofiq amalga oshiriladi, ya’ni unga ko'ra MFning eng yuqori qiymatiga ega bo'lgan xromosomalar yangi xromosomalarni yaratishda ishtirok etishda eng katta imkoniyatlariga ega bo’ladi. Seleksiyalashning turli xil usullari mavjud. Eng mashxur usullardan biri - bu mashhur qimor o'yiniga o'xshashligi bilan nom olgan ruletni tanlash (roulette wheel selection) usuli hisoblanadi. Har bir xromosomani ruletka g'ildiragi sektori bilan bog'lash mumkin, uning qiymati ushbu xromosomaning MF qiymatiga mutanosib ravishda o'rnatiladi. Shuning uchun, MF qiymati qanchalik katta bo'lsa, rulet g'ildiragidagi sektor shunchalik katta bo'ladi. Barcha rulet g'ildiragi ko'rib chiqilayotgan populyatsiyaning barcha xromosomalarining MF qiymatlari yig'indisiga mos keladi. (13.4) ifodani e’tiborga

olib belgilangan har bir


x_i (i  1, n)
xromosomaga (bu erda n-populyatsiyalar sonini

bildiradi) quyidagi formulaga muvofiq foizda ifodalangan g'ildirak sektori mos
keladi [17]:

q(x_i )  P_c (x_i ) 100%
, (13.6)

Xromosomani seleksiyalash ruletni burish natijasida ifodalanishi mumkin, chunki "g'olib" (ya'ni tanlangan) xromosoma ushbu g'ildirakning tashlab yuborilgan sektoriga tegishli. Shubhasiz, sektor qanchalik katta bo'lsa, mos keladigan

xromosoma "g'alaba qozonishi" ehtimoli katta bo’ladi. Shuning uchun berilgan xromosomani seleksiyalash ehtimoli uning MF qiymatiga mutanosib bo’ladi. Agar rulet g'ildiragining butun atrofi raqamli [0,100] oraliq sifatida ifodalangan bo'lsa, u holda xromosomani seleksiyalash [a,b] oraliqdan raqamni tanlash bilan aniqlanishi mumkin, bu erda a va b mos ravishda g'ildirakning ushbu sektoriga mos keladigan ^{aylana qismining boshi va oxirini bildiradi, bunda} 0  a  b  100^{. Bunday holda rulet} g'ildiragi bilan tanlash g'ildirak atrofidagi ma'lum bir nuqtaga mos keladigan [0,100] oraliqdagi raqamni tanlashga mos keladi. Boshqa seleksiyalash usullari 14- ma’ruzada qaraladi.
Seleksiyalash jarayoni natijasida ota-ona populyatsiyasi (OOP) yaratiladi.

5.