13-ma'ruza. Genetik algoritmlar

Ikkilik kodlash. Ikkilik kodlash eng qadimgi shakli bo'lib, tarixiy jihatdan ko'plab GAlar bunday kodlashdan (ba'zida noto'g'ri) ko’p hollarda qaralyotgan muammoga bog’liq bo’lmagan holda foydalanganlar. Bu erda genotip oddiygina ikkilik raqamlar qatoridan, ya'ni nollar va birlar to'plamidan iborat bo’lgan. Muayyan masala uchun qatorning uzunligini va uning fenotipga talqin qilinishini aniqlash kerak bo’lgan. Ko'rib chiqilayotgan masalada "genotip - fenotip" akslantirishni tanlashda kodlash barcha mumkin bo'lgan barcha bitli satrlari muammoning echimlaridan birini tashkil etadigan holatga mos kelishiga ishonch hosil qilishingan va aksincha barcha mumkin bo'lgan echimlar bunday kodlash bilan ifodalanishi mumkin bo’lgan.
Aytaylik echimlarni qidiruv fazosida mumkin bo'lgan echimlarning vektori

1

2
x^→  D ^{berilgan bo'lsin ( D - echimlarni izlsh fazosi). x→  (x , x ,..., x ) vektorning har}

i
n

bir komponentini manfiy bo'lmagan


_i [0, K_i ], i  1, n
butun son ( K  ^{i }

o'zgaruvchining mumkin bo'lgan barcha diskret qiymatlari soni) yordamida kodlash mumkin bo’lsin.

2

1

n
Ikkilik B  0,1 alfavitni kiritamiz. Butun sonli   ( ,  ,...,  ) vektorni
1

2


^{B  0,1 alfavitda aks ettirish uchun ikkilik belgilarning shunday}  ^{maksimal sonini}

aniqlash kerakki, u
[0, K_i ]
sohadan olingan ixtiyoriy
_i qiymatni ikkilik kodga

^{akslantirish uchun etatli bo’lsin. Aniqlangan}  ^{parametr quyidagi tengsizlikni} qanoatlantiradi

bunda

K  max K_i (1  i  n) .
K  2^
, (13.1)

U holda
_i (0  _i  2 )
uchun
_i



l
 __i i 1

 2^{ i , (13.2)}






yozish mumkin, bu erda ikkilik so'zning uzunligi.
_i ^{- ikkilik son (0 yoki 1);}  ^{- butun}
_i sonni kodlovchi

13.1-misol.

_i  19
sonni xromosoma qatori sifatida tasvirlaylik.
_i  19


sonini ikkilik kodda ifodalash uchun (13.1) va (13.2) formulalarni e’tiborga olgan

holda
  5
aniqlaymiz, chunki
2^  2⁵  32 . (13.2) formula bo'yicha quyidagini

hosil qilamiz:

U holda kodli satr quyidagicha bo’ladi:

1

0

0

1

1

Gen sifatida, ya'ni individual xususiyatlarni shakllantirish uchun asosiy bo'lgan irsiy materialning birliklari sifatida odatdagi ikkilik kodda x o'zgaruvchi

i

i
bilan boshqariladigan butun sonli  kodning tayinlangan qiymatini aniqlaydigan

i
e ( ) ning ikkilik kombinatsiyalarini qaraymiz. Bu holda ko’rinishda bo’ladi:
e ( )
quyidagi



k
Bitta ^t xromosoma n ta gen bilan tavsiflanadi va ularning har biri tegishli
boshqariladigan o'zgaruvchining butun sonli kodini shakllantirish uchun javobgar hisoblanadi. Bu holda xromosomani quyidagi E (X) shaklida aniqlash mumkin (13.1-jadval):
13.1-jadval. Xromosomaning tasvirlanishi.

 1 i	…	 1 0	 2 i	…	 2 0	…	…	…	 n i	…	 n 0
e0 (1 )			e0 ( 2 )			…			e0 (n )
1-gen			2-gen			…			n-gen
1-lokus			2-lokus			…			n-lokus
Xromosoma

Yuqorida ta'kidlab o'tilganidek, ma'lum bir genning xromosomada joylashgan joyi lokus deb ataladi va bir xil lokusda (joyda) joylashgan bir xil genning muqobil shakllari allellarni aniqlaydi.

O'z joylarida o'ziga xos allel qiymatlarini o'z ichiga olgan xromosoma genotipni (genetik kodni) aniqlaydi, unda ajdodlardan olingan va keyinchalik avlodlarga etkaziladigan individ haqida barcha irsiy genetik ma'lumotlar mavjud bo’ladi. Barcha ruxsat berilgan genotiplarning cheklangan to'plami genofondni tashkil qiladi.
Shunday qilib xromosoma tayinlangan uzunlikdagi bitli qator hisoblanadi. Bu holda qatorning har bir qismiga gen mos keladi. Qator ichidagi genning uzunligi bir xil yoki har xil bo'lishi mumkin. Masalan, har biri to'rtta element genomi bilan kodlangan beshta xususiyatli obyekt uchun xromosomalarning umumiy uzunligi 5 x 4 = 20 bit bo'ladi:

Ikkilik qatorlar (xromosomalar) uchun n bitlardan foydalanganda satrning ikkilik kodidan o'nlik qiymatiga o'tkazilish quyidagi formula bo'yicha amalga oshiriladi

x  a
 decimal (100...010) ^bi

• 
  a_{i ,}
  

i i 2ⁿ  1

bunda a_i
va b_i
- i - xususiyatning quyi va yuqori chegaralari; decimal(100...010₂)- -

ikkilik qatorning o'nlik qiymati.
Greya usuli bilan kodlash. So'nggi yillarda GA-da Greya kodidan foydalanish tendentsiyasi kuzatilmoqda, bu esa xemmingli siljishni tuzatish imkoniyatini kafolatlaydi. Ushbu usul bilan standart usulda butun sonlarni kodlovchi

ikkilik qator
s₁ ,..., s₂
tegishli
g₁ ,..., g₂
satrga quyidagicha aylantiriladi:


g  ^s1
k _s
, если
 s , если
k  1
k  1

 k 1 k
^{bu erda}  ^{belgi ikki modul bo’yicha yig'ishni bildiradi (ya'ni}
0  0  0; 0 1  1; 1 0  1; 11  0;).
Teskari almashtirish quyidagi ifoda bilan aniqlanadi:
k
s_k  _ g _j ,
j 1
bu erda yig'indi 2 modul bo’yicha olinadi.
13.2-jadvalda ikkilik kod va Greya kodi yordamida 0 dan 7 gacha bo'lgan butun sonlarni kodlash natijalari taqqoslash uchun ko'rsatilgan.
13.2-jadval. Ikkilik va Greya kodlarni taqqoslash.

Butun	0	1	2	3	4	5	6	7
Binarli kod	000	001	010	011	100	101	110	111
Greya kodi	000	001	011	010	110	111	101	100

Ta’kidlaymizki, qo'shni butun sonlarni kodlaydigan qatorlar orasidagi Xemming masofasining minimal qiymati 1 ga teng bo’ladi.
Butun sonli kodlash. Ikkilik kodlash har doim ham eng mos kodlash usuli hisoblanmaydi, masalan turli xil genlar qiymatlar to’plamidan bittasini qabul qilishi mumkin bo'lgan holatlar bo’lishi mumkin. Butun sonli kodlash butun son qiymatlarini qabul qiladigan o'zgaruvchilar to'plamining optimal qiymatlarini topish

masalasini hal qilishda afzalroq hisoblanadi. Izlanadigan qiymatlar cheksiz bo'lishi mumkin (har qanday butun songa ruxsat beriladi) yoki chekli to'plam bilan chegaralangan bo'lishi mumkin. Misol sifatida chekli to'plam bilan chegaralangan holatga {Shimol, Sharq, Janub, G'arb} larni ifodalovchi {0, 1, 2, 3} qiymatlar to'plami bilan chegaralangan kvadrat panjarada yo'lni topish masalasini keltirish mumkin. Bunday holatda butun sonli kodlashni quyidagicha tasvirlash mumkin

1

2

3

4

2

3

1

4

3

4

Har qanday holatda ham butun sonli kodlash ikkilik kodalshga nisbatan afzalroq hisoblanadi.
Haqiqiy sonli kodlash. Ko'pincha mumkin bo'lgan echimni namoyish etishning eng to'g'ri usuli - bu haqiqiy sonlar qatori hisoblanadi. Bu holat genlar diskret emas, balki uzluksiz taqsimlash bilan aniqlanadigan miqdorlarni ifoda etganda yuzaga keladi. Kompyuterda bunday haqiqiy sonlarning aniqligi ularni amalga oshirish imkoniyatlari bilan cheklangan, shuning uchun ular qo’zg’aluvchi nuqtali sonlar sifatida qaraladi. Bunday holda k genlardan iborat genotip vektor hisoblanadi va u quyidagicha tasvirlanadi

0.1

0.2

0.3

0.4

0.2

0.3

0.1

0.4

0.3

0.4

Shuningdek, haqiqiy sonli kodlashda butun sonli kodlashdagi kabi kodlashtirirish va dekodlashtirish operatsiyalaridan voz kechiladi hamda topilgan echimning aniqligi ham oshadi. Boshlang’ich populyatsini shakllantirishga misol sifatida 13.6 - rasmni keltirish mumkin: