13-ma'ruza. Genetik algoritmlar

13-ma'ruza uchun topshiriqlar va mashqlar

 16 sonni xromosoma qatori sifatida tasvirlang?

2. 
   
   
   _i
   

 1010101
xromosoma qatorini o’nlik son ko’rinishda tasvirlang?

2. 
   0 dan 15 gacha butun sonlar bilan ifodalangan xromosomalarning ikkilik tizimda kodlangan ifodasini aniqlang?
   
3. 
   0 dan 15 gacha butun sonlar bilan ifodalangan xromosomalar uchun quyidagi topshiriqlarni bajaring:
   
   1. 
      uning ikkilik tizimda kodlangan ifodasini aniqlang;
      
   2. 
      har bir xromosomaning qiymatini hisoblang;
      
   3. 
      xromosomalarning boslang’ich populyatsiyasining umumiy bahosini hisoblang;
      

3. 
   har bir xromosomaning ”Omon qolish” ehtimolini hisoblang;
   
4. 
   har bir xromosomaning kumulyativ ”Omon qolish” ehtimolini hisoblang.
   

2. 
   Aytaylik, xromosomalar 12 ta gendan iborat bo’lsin va boshlang’ich populyatsiyada tasodifiy ravishda 10 ta xromosoma tanlangan bo’lsin:
   

x₁  [111 0 111 0 11 0 1]; x₆  [0 1 0 1 0 111 0 1 0 1];
x₂  [1 0 11 0 0 1111 0 1]; x₇  [11 0 0 11 010 0 1 0];

x₃  [0 111 0 111 0 1 0 1];
x₄  [0 0 1 0 1 0 1 0 1 0 01];
x₈  [1 0 1 0 11 0 111 0 1];
x₉  [0 11011 0 1111 0].

x₅  [0 0 0 0 1 0 1 0 0 0 01];
^x10
 [0 10011 0 110 0 0].

Ushbu xromosomalar ustida baholash, seleksiyalash, chatishtiruv va mutatsiylash amallarini bajaring.

2. 
   Berilgan
   

f (x)  2x²  3 (0  x  31)
funksiyaning optimal qiymatini ikkilik

kodlashni qo’llab qidirish jarayonini GA yordamida ko’rsating.

2. 
   Bir o’zgaruvchi maqsad funksiya
   

f (x)  2x³ 10x²  3x  6
ifoda bilan berilgan

bo’lsin.
x [5, 20]
oralig'ida maqsad funksiyasining maksimal va minimal

echimni genetik algoritm yordamida aniqlang.

^8. f (x)  x²  3 (0  x  31)
funksiyaning optimal qiymatini ikkilik kodlashni

qo’llab minimumini qidirish jarayonini GA yordamida ko’rsating.

9. 
   f (x)  1 x (0  x  31) funksiyaning optimal qiymatini ikkilik kodlashni qo’llab
   

maxsimumini qidirish jarayonini GA yordamida ko’rsating.

9. 
   13.12-jadvalda bitta o'zgaruvchili funksiyalarning ekstremumini aniqlashni dasturlash tillaridan birida oddiy GA dasturiy ta'minotini amalga oshiring.
   

13.12-jadval
Variant	Funksiya ko’rinishi	Echimni izlash oralig’i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

9. 
   S 110110 sxema berilgan bo’lsin. Ushbu sxemaga mos keladigan barcha mumkin bo’lgan xromosomolarni aniqlang?
   

9. 
   

S  010110
sxema berilgan bo’lsin. Ushbu sxemaga mos keladigan

barcha mumkin bo’lgan xromosomolarni aniqlang?

9. 
   ^Aytaylik l 10^{uzunlikga 9 ta} S ^{sxema berilgan bo’lsin:}
   

S₁  (10 1 0  0 1);
S₂  (0 1 0  011);
S₃  (11 011);

S₄  (1010 ); S₅
 (0);
S₆  ();

S₇  (1); S₈
 (1010100111);
S₉  (1111111111).

^{Har bir} S ^sxemaning
h(S )
tartibi va
d (S) qamrovini aniqlang.

9. 
   Yuqoridagi 5-misolda keltirilgan xromosomalar orasidan S  101 sxemaga mos keladigan xromosomalarni tanlab oling. Talab qilinadi:
   
   1. 
      S ^{xemaga mos tanlab olingan xromosomalarning} k  0 ^qadamdagi
      

boshlang’ich
P(0)
populyatsiyada
F (S,0)
moslanuvchanlik funksiyasi,

moslanuvchanlik funksiylarining
Q(0)
yig’indisi va moslanuvchanlik

funksiylarning


F(0)
o’rtacha qiymatlarini hisoblang.

2. 
   5-misolda
   

P(0)
populyatsiyada tasodifiy ravishda tanlangan boshlang’ich

x₁ , x₂ , x₃ , x₄ , x₅ , x₆ , x₇ , x₈ , x₉ , x₁₀
xromosomalar uchun (13.3) ko’rinishda

hisoblangan ^F moslanuvchanlik funksiyasi, moslanuvchanlik funksiylarining

Q(0)
yig’indisi va moslanuvchanlik funksiylarning


F(0)
o’rtacha

qiymatlarini hisoblang.

3. 
   14.3)
   

P(0)
populyatsiyada
S  101
sxemaga mos keluvchi

xromosomalarning moslanuvchanlik funksiylarining


F(0)
o’rtacha qimatini

ushbu populyatsiyada tanlangan boshlang’ich
x₁ , x₂ , x₃ , x₄ , x₅ , x₆ , x₇ , x₈

xromosomalarning moslanuvchanlik funksiylarining bilan taqqoslang va xulosa chiqaring.


F(0)
o’rtacha qimati

9. 
   Xromosomalarni chatishtirish maqsadida 5-misolda berilgan xromosomalardan
   

tasodifiy ravishda 5 ta

1

9
^x va x ; x va x ; x va x ; x va x ; x va x ^ juftlik tanlangan
3 1 6 2 3 7 8 7

bo’lsin. 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  5 , to’rtinchi

x₇ va x₈
juftlik uchun
I _k  7
va beshinch
x₇ va x₉
juftlik uchun
I _k  8

chatishtiruv nuqtalari belgilangan bo’lsin.
Talab qilinadi:

1. 
   Tanlangan har bir juftlik uchun belgilangan chatishtiruv nuqtasida ChOni qo’llab 5 ta avlodlar juftligiga mos keladigan yangi
   

x^ , x^ , x^ ,
x^ , x^ , x^ , x^ ,
x^ , x^ , x^
xromosomalarni hosil qiling.

1 2 3
4 5 6 7
8 9 10

2. 
   Hosil qilingan yangi 10 ta xromosomalardan S  101
   

sxemaga mos keladigan xromosomalarni aniqlang va xromosomalrning
k 1

qadamdagi
P(1)
populyatsiyada
F (S,1)
moslanuvchanlik funksiyasi,

moslanuvchanlik funksiylarining
Q(1)
yig’indisi va moslanuvchanlik

funksiylarning


F (1)
o’rtacha qiymatlarini hisoblang.

3. 
   14-misolning 14.1-bosqichida
   

P(0)
populyatsiyada

S  101
sxemaga mos keluvchi xromosomalarning

moslanuvchanlik funksiylarining


F(0)
o’rtacha qimatini 15-misolning 15.2 -

bosqichida
P(1) populyatsiyada
S  101^{sxemaga mos keluvchi}

xromosomalarning moslanuvchanlik funksiylarining bilan taqqoslang va xulosa chiqaring.

13-ma’ruza uchun testlar

F (1)
o’rtacha qimatini

1. 
   Genetik algoritmlar g'oyasi ………………. tomonidan XX asrning
   

………………………. boshlarida taklif qilingan.

1. 
   J. Xolland; 60-yillari oxiri 70-yillari;
   
2. 
   D. E. Goldberg; 60-yillari oxiri 70-yillari;
   
3. 
   A. Frazier; 50-yillari oxiri 60-yillari;
   
4. 
   M. Konrad; 70-yillari oxiri 80-yillari.
   
1. 
   Genetik algoritm - bu algoritmi.
   
   1. 
      evristik qidiruv; b) evristik qo’shish;
      

c) jadvalli o’chirish; d) minimumni qidiruv.

3. 
   ……………………- bu tabiatdagi tabiiy seleksiyalashga o'xshash mexanizmlardan foydalanib, kerakli parametrlarni tasodifiy tanlab olish, birlashtirish va o'zgartirish orqali optimallashtirish va modellashtirish muammolarini hal qilish uchun ishlatiladigan evristik qidiruv algoritmi.
   
   1. 
      Genetik algoritm; b) Evolyutsion dasturlash;
      

c) Evolyutsion strategiyalar; d) Genetik dasturlash.

4. 
   Evolyutsiyani simulyatsiya qilish bo'yicha birinchi ish
   

…………………………..tomonidan amalga oshirilgan.

1. 
   1954 yilda Baricelli; b) 1964 yilda Frazer;
   

c) 1970 yilda Barnell; d) 1973 yilda Krosbi.

5. 
   .. - bu cheklangan xromosoma (zot)lar to'plami.
   
   1. 
      Populyatsiya; b) Alel; c) Gen; d) Genotip.
      
6. 
   …………….- bu irsiy ma'lumotlarning tashuvchisi.
   
   1. 
      Xromosoma; b) Alel; c) lokus; d) Genotip.
      
7. 
   ……….. - bu genotipning atomar elementi, xususan xromosomalar hisoblanadi..
   
   1. 
      Gen; b) Xromosoma; c) lokus; d) Individ.
      
8. 
   …………… operator - bu avlodni olish uchun zarur bo'lgan bir yoki bir nechta ota-onalarga nisbatan tartiblangan harakatlar ketma-ketligi.
   
   1. 
      Genetik; b) Evolyutsion; c) Strategik; d) Individual.
      
9. 
   ……………. - xromosomalar to'plami.
   
   1. 
      Individ; b) Alel; c) lokus; d) Gen.
      
10. 
    …. - bu ma'lum bir individning xromosomalar to'plami hisoblanadi.
    
    1. 
       Genotip; b) Individ; c) Alel; d) lokus.
       
11. 
    …………..- bu ma'lum bir genotipga mos keladigan qiymatlar to'plami, ya'ni. masala parametrlarining dekodlangan tuzilmasi yoki to'plami..
    

1. 
   Fenotip; b) Individ; c) Alel; d) Genotip.
   
1. 
   …………- bu ma'lum bir genning qiymati, shuningdek xususyatning qiymati yoki xususiyatning bir varianti sifatida aniqlanadi.
   
   1. 
      Allel; b) Fenotip; c) Individ; d) Genotip.
      
2. 
   …………. - bu ma'lum bir genning xromosoma(zanjir)da joylashgan joyini ko’rsatadi..
   
   1. 
      Lokus; b) Allel; c) Fenotip; d) Individ.
      
3. 
   …………………………….. - bu genetikaga xos bo’lib, u populyatsiyadagi muayyan individlarning jismoniy tayyorgarligini baholash va eng munosiblarini tirik qolish evolyutsion prinsipiga muvofiq ular orasida eng munosibini tanlashga imkon beradi.
   
   1. 
      Moslanuvchanlik funksiyasi; b) Genetik operator; c) Fenotip; d) Individ.
      
4. 
   Xromosomalarning boshlang'ich populyatsiyasini yaratish - bu moslanuvchanlik funksiyasi parametrlarining qiymatlari ………….……….va ushbu parametr qiymatlari uchun moslanuvchanlik funksiyasi qiymati holat.
   
   1. 
      tasodifiy tanlangan; topilgan; b) tasodifiy tanlangan; topilmagan;
      

c) tasodifiy tanlanmagan; topilgan; d) tasodifiy tanlanmagan; topilmagan.

16. 
    Genetik algoritmning asosiy bloklari ketma-ketligi to’g’ri keltirilgan javobni ko’rsating?
    
    1. 
       Initsializatsiyalash, baholash, seleksiyalash, chatishtiruv, mutatsiyalash;
       
    2. 
       baholash, seleksiyalash, chatishtiruv, initsializatsiyalash, mutatsiyalash;
       
    3. 
       seleksiyalash, initsializatsiyalash, baholash, chatishtiruv, mutatsiyalash;
       
    4. 
       mutatsiyalash, initsializatsiyalash, baholash, seleksiyalash, chatishtiruv.
       
17. 
    Initsializatsiyalash - tasodifiy ravishda ………….
    
    1. 
       dastlabki xromosomalarning populyatsiyasini shakllantirish;
       
    2. 
       olingan xromosomalarning yaroqliligini aniqlash;
       
    3. 
       yaroqli baholash qiymatlariga ega bo`lgan xromosomalar tanlab olish;
       
    4. 
       xromosomalarning tasodifiy sonini saralab olish.
       

18. Baholash -…………………….....................................................

1. 
   olingan xromosomalarning yaroqliligini aniqlash;
   
2. 
   dastlabki xromosomalarning populyatsiyasini shakllantirish;
   
3. 
   yaroqli baholash qiymatlariga ega bo`lgan xromosomalar tanlab olish;
   
4. 
   xromosomalarning tasodifiy sonini saralab olish.
   

19. Seleksiyalash -…………………………………………………………

1. 
   yaroqli baholash qiymatlariga ega bo`lgan xromosomalar tanlab olish;
   
2. 
   dastlabki xromosomalarning populyatsiyasini shakllantirish;
   
3. 
   olingan xromosomalarning yaroqliligini aniqlash;
   
4. 
   xromosomalarning tasodifiy sonini saralab olish.
   

20. 
    Chatishtiruv -
    
    1. 
       xromosomalarning tasodifiy sonini saralab olish;
       
    2. 
       dastlabki xromosomalarning populyatsiyasini shakllantirish;
       
    3. 
       olingan xromosomalarning yaroqliligini aniqlash;
       
    4. 
       yaroqli baholash qiymatlariga ega bo`lgan xromosomalar tanlab olish. 21. Mutatsiyalash -……………………………………………………....
       

1. 
   xromosomaning bir genini(bitini) o`zgartiradi;
   
2. 
   dastlabki xromosomalarning populyatsiyasini shakllantirish;
   
3. 
   olingan xromosomalarning yaroqliligini aniqlash;
   
4. 
   yaroqli baholash qiymatlariga ega bo`lgan xromosomalar tanlab olish.
   

22. 
    …………….. - xromosoma kodi qismlarini kelish tartibini o'zgartirish bo’lib, bunda tasodifiy ravishda xromosoma kodidagi qo’shni bitlar orasida uzilish nuqtasi tanlanadi.
    
    1. 
       Inversiyalash; b) Mutatsiyalash; c) Chatishtiruv; d) Seleksiyalash.
       
23. 
    Har bir xromosomaning sifati qaysi formula bilan baholanadi?
    

1. 
   f (x_i )  _ x_ik ^{; b)}
   

k 1



F  _ f (x_ik ) ^{; c)}
k 1



f (x_i )  1/ _ x_ik ^{; d)} F 
k 1



f (x_i ) / _ x_ik ^.
k 1

22. 
    Populyatsiyaning umumiy bahosi qaysi formula bilan baholanadi?
    

1. 
   F  _ f (x_i ) ^{; b)}
   

i 1



f (x_i )  _ x_ik ^{; c)}
k 1



F  1/ _ x_ik ^{; d)} F 
k 1



f (x_i ) / _ x_ik ^.
k 1

22. 
    Har bir xromosomaning ”Omon qolish” ehtimoli qaysi formula bilan baholanadi?
    

1. 
   P_c (x_i ) 
   

f (x_i ) / _ f (x_i ) ^{; b)}
i 1
n



P_c (x_i )  _ f (x_i ) ^;
i1
n

^c) P_c (x_i ) 
f (x_i )  _ f (x_i ) ^{; d)}
i 1
P_c (x_i ) 
f (x_{i 1} ) / _ f (x_{i 1} ) ^.
i 1

22. 
    Har bir xromosomaning kumulyativ deb ataladigan”Omon qolish” ehtimoli qaysi formula bilan baholanadi?
    

1. 
   P_kum (x_i )  _ P_c (x_i ) ^{; b)}
   

i 1
i
P_kum (x_i ) 



f (x_i )_ P_c (x_i ) ^;
i 1
i

^c) P_kum (x_i ) 
f (x_i ) / _ P_c (x_i ) ^{; d)}
i 1
P_kum (x_i ) 
f (x_i )  _ P_c (x_i ) ^.
i 1

22. 
    Xromosomalarni seleksiyalashning ruletni tanlash usulida belgilangan har bir xromosomaga foizda ifodalangan g'ildirak sektori qaysi formulaga muvofiq hisoblanadi?
    

a) q(x_i )  P_c (x_i ) 100% ; b) q(x_i )  P_kum (x_i ) 100% ;
c) q(x_i )  P_c (x_i ) /100% ; d) q(x_i )  P_kum (x_i ) /100% .

22. 
    ………………. masala prametrlarining berilgan boshlang’ich qiymatlarini emas, balki ularning kodlashtirilgan qiymatlarini qayta ishlaydi.
    
    1. 
       Genetik algoritmlar; b) An'anaviy optimallashtirish usullari;
       

c) Ekspert tizimlar; d) Dinamik programmalashtirish.

22. 
    ………………. echimni bitta nuqtadan emas, balki ularning ma'lum bir populyatsiyasidan qidirishni amalga oshiradi.
    
    1. 
       Genetik algoritmlar; b) An'anaviy dasturlash;
       

c) Ekspert tizimlar; d) Chiziqli programmalashtirish.

22. 
    ………………. maqsad funksiyasining hosilalari yoki boshqa qo'shimcha ma'lumotlaridan emas, balki faqat maqsad funksiyasining o’zidan foydalanadi.
    
    1. 
       Genetik algoritmlar; b) Statistik usullar;
       

c) Noravshan tizimlar; d) Chiziqli programmalashtirish.

22. 
    ………………. seleksiyalashda deterministik qoidalarni emas, balki ehtimolli qoidalarni qo’llaydi.
    
    1. 
       Genetik algoritmlar; b) Analitik usullar;
       

c) Mulohazalar mantiqi; d) Chiziqsiz programmalashtirish.

22. 
    Genetik algoritmlarda ba'zi umumiy xususiyatlarga ega, ya'ni bir-biriga o'xshash bo'lgan xromosomalar to'plamini aniqlash uchun qaysi tushunchadan foydalaniladi?
    
    1. 
       Sxema; b) Alel; c) Lokus; d) Fenotip.
       
23. 
    Sxemalar ko'rib chiqayotganda qaysi alfavitdan foydalaniladi? a) 0,1, ; b) 0,1; c) 0, ; d) 1, .
    

22. 
    

S 1101
sxemaga mos keladigan mumkin bo’lgan barcha barcha

xromosomalar to’plami to’gri ko’rsatilgan javoni ko’rsating?
a) S  11 01  11001,11101; b) S  11 01  11001,11001; c) S  11 01  11101,11100; d) S  11 01  11 01,11101.

22. 
    S 11101 ^{sxemaga mos keladigan mumkin bo’lgan barcha xromosomalar} to’plami to’gri ko’rsatilgan javoni ko’rsating?
    

a) S  111 01  1011001,1011101, 1111001, 1111101;
b) S  111 01  1111001,1011101, 1111001, 1111101;
c) S  111 01  1111001,1011101, 01111001, 1011101;
d) S  111 01  1111001, 0111101, 1111001, 1111101.

22. 
    Agar S sxemada m ta * belgilar mavjud bo'lsa, unda ushbu sxema nechta xromosomalarni o'z ichiga oladi.
    

1. 
   2^m ; b)
   

2^S ; c)
2^{2 m} ; d)
S  2^m .

22. 
    Qaysi shart bajarilsa xromosoma S sxemaga tegishli bo’ladi?
    
    1. 
       S sxemadagi * belgiga xromosomaning 0 qiymati ham va 1 qiymati xam mos kelsa;
       
    2. 
       S sxemadagi * belgiga xromosomaning 0 qiymati yoki 1 qiymati mos kelsa;
       
    3. 
       S sxemadagi * belgiga xromosomaning faqat 0 qiymati mos kelsa;
       
    4. 
       S sxemadagi * belgiga xromosomaning faqat 1 qiymati mos kelsa.
       

22. 
    

P(k)
populyatsiyada S sxemaga mos keluvchi xromosomlar soni qaysi

formula bilan aniqlanadi?
_l 
_l 

1. 
   f (x_i )  _ x_ik
   

k 1
(i  1, n^ (S, k)) ^{; b)}
f (x_i ) 
f (x_i )_ x_ik
k 1
(i  1, n^ (S, k)) ^;

_l  _l 

^c) f (x_i )  1/ _ x_ik
k 1
(i  1, n^ (S, k))^{; d)}
f (x_i )  S _ x_ik
k 1
(i  1, n^ (S, k)) ^.

22. 
    ^P(k) populyatsiyada S sxemaga mos keluvchi xromosomlarning umumiy bahosi qaysi formula bilan aniqlanadi?
    

1. 
   F(S, k) 