13-ma'ruza. Genetik algoritmlar

13.9-misol. Aytaylik 13.6-misolda 12 ta gendan iborat xromosomalar boshlang’ich populyatsiya 8 xromosomani o’z ichiga olgan bo’lsin:

x₁  [111 0 0110 0101];
x₂  [0 0110 0111010];
x₃  [011101110 011];
x₄  [0 010 0 01010 0 0];
Quyidagi
x₅  [010 0 0110 010 0];
x₆  [010 0110 0 0101];
x₇  [1 01011011011];
x₈  [0 0 0 01011110 0].
(13.28)

S₀  [         11]
sxemani qaraladi va ushbu sxemada GA bajarilishi jarayonida qatnashchilar (genlar) soni va MF qanday o’zgarishi ko’rib chiqiladi.
^S ₀ ^{sxemaning uzunligi (genlar soni)} l 12^{ga teng bo’lib, uning tartibi}

(13.16) ifodaga asosan
h(S₀ )  l  l_ (S₀ )  12 10  2
va qamrovi (13.17)

ifodaga asosan populyatsiyadan
d(S₀ )  l_o'ng (S₀ )  l_chap (S₀ )  12 11 1. Boshlang’ich 8 ta
S ₀ sxemaga quyidagi ikkita xromosomalar mos keladi:

x₃  [0 111 0 111 0 0 11];
x₇  [1 0 1 0 11 0 11 0 11];
(13.29)

Eslatib o'tish joizki chatishtiruv va mutatsiyalash ehtimollari mos ravishda

P_c  1 va
P_m  0
teng deb hisoblanadi.
S ₀ sxemaning
P(0)
boshlang'ich

populyatsiyada
F (S₀ ,0)
moslanuvchanligini (13.12) formulaga asosan aniqlash

uchun avvalo
P(0)
populyatsiyadagi
S ₀ sxemaga mos keluvchi
x₃ va x₇

xromosomalar uchun
f (x₃ )  8
va f (x₇ )  8
moslanuvchanlik qiymatlari

aniqlanadi. Ushbi qiymatlarni (13.12) formulaga qo’yib
P(0)
populyatsiyada

F (S₀ ,0)
moslanuvchanlik quyidagcha aniqlanadi:
2

F (S₀ ,0)  _
i1
f (x_i )
2  (8  8) / 2  8 .

N ^{=2 quvvatga ega bo’lgan}
P(0)
populyatsiyada
S ₀ sxemaga mos keluvchi

x₃ va
x₇ xromosomalar moslanuvchanlik funksiylarining
Q(0)
yig’indisi (13.13)

formulaga asosan aniqlanadi:



2



Q(0)  _ f (x_i )  8  8  16 .
i1

k  0-iteratsiyadagi
P(0)
populyatsiyada
x₃ va
x₇ xromosomalar

moslanuvchanlik funksiylarining aniqlanadi:


F(0)
o’rtacha qiymati (13.14) formulaga asosan

F (0)  ¹ Q(0)  ¹ 16  8
2 2

Endi
P(0)
populyatsiyada 13.6-misolda GAning initsializatsiyalash

bosqichida xromosomalarning boshlang'ich populyatsiyasini tanlashni amalga

oshirish natijasida tanlangan boshlang’ich
x₁ , x₂ , x₃ , x₄ , x₅ , x₆ , x₇ , x₈
xromosomalar

uchun


f (x_i )(i  1,8)
MFning qiymatlari hisoblanadi:

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

Aniqlangan


f (x_i )(i  1,8)
funksiyaning qiymatlari (13.12) formulaga

qo’yib quyidagi aniqlanadi:



F (S₀ ,0)  _ f (x_i )
i1

8 (7  5  8  3  4  5  8  5) / 8  46  8  5.75 .

N ^{=8 quvvatga ega bo’lgan}
P(0)
populyatsiyada
x₁ , x₂ , x₃ , x₄ , x₅ , x₆ , x₇ , x₈

xromosomalar moslanuvchanlik funksiylarining asosan aniqlanadi:
Q(0)
yig’indisi (13.13) formulaga

8
Q(0)  _ f (x_i )  7  5  8  3  4  5  8  5  46 .
i1

k  0^{-iteratsiyadagi}
P(0)
populyatsiyada
x₁ , x₂ , x₃ , x₄ , x₅ , x₆ , x₇ , x₈

xromosomalar moslanuvchanlik funksiylarining formulaga asosan aniqlanadi:


F(0)
o’rtacha qiymati (13.14)

F (0)  ¹ Q(0)  ¹ 46  5.75.

Demak


P(0)
8 8
populyatsiyada S ₀ sxemaga mos keluvchi


x₃ va x₇

xromosomalarning moslanuvchanlik funksiylarining


F(0)  8
o’rtacha qimati

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

xromosomalarning moslanuvchanlik funksiylarining qimatidan katta bo’layapti.


F(0)  5.75
o’rtacha

Chatishtiruv - genetik operatorlarni qo’llashni amalga oshirish. Endi

keyingi k  1 qadamda (13.28) ko’rinishdagi populyatsiyadan ChOni qo’llab yangi

xromosomalarni hosil qilish va ular orasidan seleksiyalash amalga oshiriladi.
S ₀ sxemaga mos keladiganlarini

Faraz qilaylik seleksiyalash jarayonida (13.28) ko’rinishda tanlangan 8 ta
xromosomalarning birortasi ham mutatsiyalashga uchramasin va ularning hammasi chatishtiruv uchun mo'ljallangan xromosomalar populyatsiyasini tashkil qilsin. Bu

esa chatishtiruv ehtimolini
P_c (x_i )  1
va mutatsiyalash ehtimoli
P_m (x_i )  0

ekanligini 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₇ .

Bu juftliklar uchun 13.6-misolda chatishtiruv nuqtalarini tanlash va chatishtiruv jarayoni 13.12-rasmda ko’rsatilgandek amalga oshiriladi va natijada 8 ta yangi xromosomalar hosil bo’ladi:

1
x^  [0 0 1111 0 11 0 11];

2
x^  [1 0 1 0 0 0 111 0 1 0];
x^  [0 111 0 111 0 0 1 0];

5

6
x^  [0 0 10 0 0 1 0 1 0 0 1];

7
(13.30)

3
x^  [111 011 0 11 0 11];
x^  [0 111 0 1 0 11 0 11];

4

8
x^  [1 0 1 0 0 11 0 0 1 0 1]; x^  [1 0 1 0 1111 0 0 11].

(13.30) ko’rinishdagi xromosomalar orasidan 4tani tashkil etadi:
S ₀ sxemaga mos keladiganlari

1
x^  [0 01111 011 011];
x^  [0111 01 011 011];



7

8
(13.31)

3
x^  [111 011 011 0 11];
x^  [1 01 01111 0 011].

S ₀ sxemaning
k 1
qadamdagi
P(1)
populyatsiyada
F (S₀ ,1)

moslanuvchanligini (13.12) formulaga asosan aniqlash uchun avvalo P(1)

populyatsiyadagi
^{S sxemaga mos keluvchi (13.31)dagi} x^ , x^ , x^ , x^

⁰ 1 2 3 4

xromosomalar uchun
f (x^ )  8,
f (x^ )  9,
f (x^ )  8,
f (x^ )  8 ^{moslanuvchanlik}

1

3

7

8
qiymatlari hisoblanadi. Ushbi qiymatlarni (13.12) formulaga qo’yib P(1)

populyatsiyada
F (S₀ ,1) moslanuvchanlik quyidagcha aniqlanadi:
4

F (S₀ ,1)  _
i1
f (x_i )
2  (8  9  8  8) / 4  8.25. .

N ^{=4 quvvatga ega bo’lgan}
P(1)
populyatsiyada
S ₀ sxemaga mos keluvchi

x^ , x^ , x^ , x^
xromosomalar moslanuvchanlik funksiylarining
Q(1)
yig’indisi

1 2 3 4
(13.13) formulaga asosan aniqlanadi:
4

Q(1)  _
i1
f (x_i )  8  9  8  8  33..

P(1)
populyatsiyada
x^ , x^ , x^ , x^
xromosomalar moslanuvchanlik

1 2 3 4

funksiylarining


F (1)
o’rtacha qiymati (13.14) formulaga asosan aniqlanadi:
F (1)  ¹ Q(1)  ¹ 33  8.25

Endi
k 1
4 4
qadamda P(1) populyatsiyada (13.30)dagi

x^ , x^ , x^ , x^ , x^ , x^ , x^ , x^{ xromosomalar uchun}
1 2 3 4 5 6 7 8

1
f (x^ )  8,
f (x^ )  6,
f (x^ )  9,
f (x^ )  6,
f (x^ )  7,
f (x^ )  4,
f (x^ )  8,
f (x^ )  8

2

3

4

5

6

7

8
moslanuvchanlik qiymatlari hisoblanadi. Ushbi qiymatlarni (13.12) formulaga

qo’yib
P(1)
populyatsiyada
8
F (S₀ ,1)
moslanuvchanlik quyidagcha aniqlanadi:

F (S₀ ,1)  _
i1
f (x_i )
8  (8  6  9  6  7  4  8  8) / 8  7.

N =8 quvvatga ega bo’lgan
P(1)
populyatsiyada
x^ , x^ , x^ , x^ , x^ , x^ , x^ , x^

1 2 3 4 5 6 7 8

xromosomalar moslanuvchanlik funksiylarining asosan aniqlanadi:
Q(1)
yig’indisi (13.13) formulaga

8
Q(1)  _ f (x_i )  8  6  9  6  7  4  8  8  56.
i1

P(1)
populyatsiyada
x^ , x^ , x^ , x^ , x^ , x^ , x^ , x^
xromosomalar

1 2 3 4 5 6 7 8

moslanuvchanlik funksiylarining aniqlanadi:


F (1)
o’rtacha qiymati (13.14) formulaga asosan

F (1)  ¹ Q(1)  ¹ 56  7.
8 8

Demak yangi
P(1)
populyatsiyada
^{S sxemaga mos keluvchi} x^ , x^ , x^ , x^

⁰ 1 2 3 4
^{xromosomalarni moslanuvchanlik funksiylarining o’rtacha qimati} F(1)  8.25
ushbu populyatsiyada chatishtiruv natijasida hosil qilingan
x^ , x^ , x^ , x^ , x^ , x^ , x^ , x^{ xromosomalarni moslanuvchanlik funksiylarining}
1 2 3 4 5 6 7 8

o’rtacha qimati


F(1)  7 ^{dan katta bo’layapti. Bundan tashqari yangi}
P(1)

populyatsiyada
^{S sxemaga mos keluvchi} x^ , x^ , x^ , x^
xromosomalarni

⁰ 1 2 3 4

moslanuvchanlik funksiylarining qiymati
F (S₀ ,1)  8.25
P(0)
populyatsiyada S ₀

sxemaga mos keluvchi
x₃ , x₇
xromosomalarni moslanuvchanlik funksiylarining

qiymati
F (S₀ ,0)  8 dan katta, ya’ni
F (S₀ ,1)  8.25  F (S₀ ,0)  8
bo’layapti

hamda
S ₀ sxemaga mos keluvchi yangi
P(1)
populyatsiyaning quvvati
N  4 ⁽

x^ , x^ , x^ , x^
xromosomalardan iborat) oldingi
P(0)
populyatsiyaning quvvati

1 2 3 4

N  2 ^{( x}₃ ^{, x}₇
xromosomalardan iborat)dan katta, ya’ni
N  4  N  2 ^{bo’layapti.}

Sxemalarni qayta ishlashga bag'ishlangan 13.9-misoldan quyidagi xulosalar chiqarish mumkin [17]. Ushbu misollar GAlarning asosiy teoremasi - sxema haqidagi teoremasini aks ettiradi. U kichik tartibli va kichik qamrovli sxemaga ishlov berishga ta'sir qiladi.