MÖvzu 12: genetik alqoritmləR



Yüklə 45.98 Kb.
tarix26.02.2017
ölçüsü45.98 Kb.
MÖVZU 12: GENETİK ALQORİTMLƏR
Plan

1. Genetik alqoritm anlayışına giriş

2. Əsas tərif və anlayışlar

3. GA-nın işinin əsas prinsipləri


1. Genetik alqoritm anlayışına giriş

Məlumdur ki, optimizasiya məsələləri minimumun (maksimumun) tapılmasından ibarətdir. Belə funksiya məqsəd adlanır. Qayda olaraq, məqsəd funksiya – giriş parametrlərdən asılı olan funksiyadır. Optimizasiya üsullarının bir sırası mövcuddur. Şərti olaraq bütün optimizasiya üsullarını törəmə anlayışını (qradiyent metodlar) istifadə edən metodlar və stoxastik metodlarına ayrılır. Onların köməyilə məqsəd funksiyasının ekstremal qiymətinin tapmaq olar, lakin əminliklə demək olmur ki, qlobal ekstremumun qiyməti alınmışdır.

Qlobal yerinə lokal ekstremumun tapılması vaxtından əvvəl yığılma adlanır. Bu problemdən başqa hesablama prosesi zamanı problemi də durur.

Bu problemlərin həlli üçün yeni optimizasiya alqoritmlərin axtarışı aparılır. Con Holland tərəfindən nisbətən yaxınlarda (1975) təklif edilmiş genetik alqoritmlər Ç. Darvinini təbii seçim prinsiplərinə əsaslanır.


2. Əsas tərif və anlayışlar

Genetik alqoritmlərdə tətbiq edilən əsas anlayışları nəzərdən keçirək.

Vektor – nizamlanmış ədədlər toplusudur.

Bul vektoru – ikielementli (bul) çoxluqdan qiymətlərini qəbul edən vektordur.

Hemminq məsafəsi – bul vektorları üçün istifadə edilir və vektorların fərqli komponentlərinin sayına bərabərdir.

Hemminq fəzası – Hemminq məsafəsi (metrikası) ilə bul vektorlarının fəzasıdır. n-ölçülü bul vektorları təsadüfündə baxılan fəza hemminq metrikası ilə olan n-ölçülü kubun zirvələr toplusu kimi nəzərdən keçirilir. Iki zirvə arasında məsafə til boyu ölçülən və bu zirvələri birləşdirən ən qısa məsafə ilə müəyyən olunur.

Xromosom – müəyyən ədədlər vektorudur. Əgər bu vektor 0 və 1 ibarət olan binar sətirlə təqdim edilibsə, məsələn100011101, onda o ikilik kodlaşdırılma və ya Qrey kodu asitəsilə alınmışdır.

İndividuum (genetik kod, nümayəndə) – xromosomlar toplusudur. Adətən nümayəndə bir xromosomdan ibarətdir, sonradan nümayəndə və xromosom identik anlayışlar kimi təqdim ediləcək.

Məsafə - binar xromosomlar arasında hemminq məsafəsidir.

Krossinqover (krossover) – öz hissələri ilə mübadilə aparan xromosomlar arasında əməliyyatdır. Məsələn, 1100&1010 −→ 1110&1000.

Mutasiya – xromosomda bir və ya bir neçə pozisiyaların təsadüfi dəyişməsi. Məsələn, 1010011 −→ 1010001.

İnversiya – xromosomda və ya onun fraqmentində bitlərin ardıcıllıqlarının dəyişilməsi. Məsələn, 1100 −→ 0011.

Populyasiya – individuumlar toplusu.

Yararlılıq – meyar ya funksiyadır ki, onun ekstremumu tapılmalıdır.

Lokus- genin xromosomda olan pozisiyasıdır.

Allel – ardıcıl gedən topludur.

Epistaz – digər yerdə olan genin qiymətindən asılı olaraq individuumun yararlığına genin təsiri. Əgər genin mövcudluğu digər lokusdakı genə təsir göstərirsə o, epistatik (ingibir) sayılır. Genin ona qarşı qeyri-alleal olan genlərə təsiri hipostaz, təsirə malik olan gen isə hipostatik adlanır.

Bu təriflərdən məlum olur ki, GA-in terminologiyası genetik və süni anlayışların sintezini təşkil edir. Bioloji siatemlərdə tam genetik paket genotip adlanır. Süni sistemlərdə tam genetik paket struktur adlanır. Riyazi modelləşdirmədə baxılan struktur alternativ həll və ya nöqtə adlanan parametrlər çoxluğu ilə dekodlaşdırılır. Parametrlərin bütün qiymətləri həllər fəzasını təşkil edir. Süni genetik sistemdə ədədi və qeyri-ədədi parametrlərdən istifadə mümkündür.

Bioloji terminologiya ilə desək, xromosom genlər vasitəsilə təşkil edilib. Genetikada hər lokusla genetik funksiya bağlıdır. Bunun üçün də ixtisaslaşdırılmş genlər haqqında danışmaq olar. Məsələn, heyvan gözünnün geni 10 lokusda yerləşib, yənin gözlərin mavi rəngi 10 allallıq qiymətə məxsusdur. GA terminologiyasında deyirlər ki, sətirlər funksiyanın qiymətləri ilə təşkil ediib.
3. GA-in əsas iş prinsipləri

1. n-xromosomdan ibarət ilkin populyasiyanın yaradılması

2. Hər xromosom üçün onun yararlılığını hesab edirik

3. Seçım metodlarından istifadə edərək valideyn xromosomların cütlüyünü seçirik

4. p ehtimalıyla iki valideynin krossoverini keçirərək iki övlad yaradırıq

5. pm ehtimalıyla övladların mutasiyasını aparırıq

6. n-xromosomdan ibarət populyasiyanın yeni nəsiini yaratmayana kimi 3-5 addımları təkrarlayırıq

7. Prosesin qurtarma meyarı əldə edilməyənə kimi 2-6 addımları təkrarlayırıq



Misal. Diofant tənlikləri.

Tənik: a+2b+3c+4d=30.

Tənliyin kökləri [1;30] parçasında yerləşir, a,b,c,d-ın 5 təsadüfi qiymətini götürürük. 1 nəsil:

(1,28,15,3)

(14,9,2,4)

(13,5,7,3)

(23,8,16,19)

(9,13,5,2)

Yararlılıq (yaşamaq) əmsalını hesablamaq üçün hər həlli ifadəyə salaq. Alınmş qiymətdən 30-a qədər məsafə lazım olan qiymətdir.

|114-30|=84

|54-30|=24

|56-30|=26

|163-30|=133

|58-30|=28

30-a daha kiçik qiymətlər yaxındır, ona görə onlar daha arzu olunandır. Yəni yüksək qiymətlərin yaşamaq əmsalı aşağı olacaq. Hər xromosomun seçim ehtimalını hesablayaq. Həll ondan ibarətdir ki, bunun üçün əmsalların əks qiymətlərini götürüb faizləri hesablamaq gərəkdir (əmsalların əks qiymətlərinin cəmi – . 0.135266).

(1/84)/0.135266 = 8.80%

(1/24)/0.135266 = 30.8%

(1/26)/0.135266 = 28.4%

(1/133)/0.135266 = 5.56%

(1/28)/0.135266 = 26.4%

1/84+1/24+1/26+1/133+1/28=0.135266

Sonra bir övladı olan 5 valideyn cütlüyünü seçək:

3-1, 5-2, 3-5, 2-5, 5-3

Krossoverdən istifadə edək:

Х.-ata: a1 | b1,c1,d1 Х.- ana: a2 | b2,c2,d2 Х.-övlad: a1,b2,c2,d2 or a2,b1,c1,d1

Х.- ata: a1,b1 | c1,d1 Х.- ana: a2,b2 | c2,d2 Х.- övlad: a1,b1,c2,d2 or a2,b2,c1,d1

Х.- ata: a1,b1,c1 | d1 Х.- ana: a2,b2,c2 | d2 Х.- övlad: a1,b1,c1,d2 or a2,b2,c2,d1

Eyni hərəkəti övladlarla edək:

Х.- ata: (13 | 5,7,3) Х.- ana: (1 | 28,15,3) Х.- övlad: (13,28,15,3)

Х.- ata: (9,13 | 5,2) Х.- ana: (14,9 | 2,4) Х.- övlad: (9,13,2,4)

Х.- ata: (13,5,7 | 3) Х.- ana: (9,13,5 | 2) Х.- övlad: (13,5,7,2)

Х.- ata: (14 | 9,2,4) Х.- ana: (9 | 13,5,2) Х.- övlad: (14,13,5,2)

Х.- ata: (13,5 | 7, 3) Х.- ana: (9,13 | 5, 2) Х.- övlad: (13,5,5,2)

Övladların yaçamaq əmsalını hesablayaq:

(13,28,15,3) — |126-30|=96

(9,13,2,4) — |57-30|=27

(13,5,7,2) — |57-30|=22

(14,13,5,2) — |63-30|=33

(13,5,5,2) — |46-30|=16

Orta yararlılıq əmsalı 38.8, halbuki vakideynlərdə 59.4 bərabər idi.


Misal. f(~x)~=~2x^2+~1funksiyasının maksimumunun tapılması, burada x – tam ədəddir və [0;31] parçasında ikilik sistemdə yazılan qiymətini alır. Yaşama funksiyası kimi yuxarıdak funksiya çıxış edir, onda chi, i=1,...,N xromosomunun yaşamı f(x) funksiyası ilə təyin olunur. Fenotipləri chi* işarə edək. Qoy bu xromosomlar seçilib:


ch_{1}~=~10011

ch_{2}~=~00011

ch_{3}~=~00111

ch_{4}~=~10101

ch_{5}~=~01000

ch_{6}~=~11101

Onların fenotipləri:


{ch_{1}}^*~=~19

{ch_{2}}^*~=~3

{ch_{3}}^*~=~7

{ch_{4}}^*~=~21

{ch_{5}}^*~=~8

{ch_{6}}^*~=~29

Yararlılıq funksiyası:


f(ch_{1})~=~723

f(ch_{2})~=~19

f(ch_{3})~=~99

f(ch_{4})~=~883

f(ch_{5})~=~129

f(ch_{6})~=~1683

Krossover p=1 olmaqla bu cütlüklər üçün yerinə yetirilir:

(ch_{1}~-~ch_{4})~,~(ch_{4}~-~ch_{6})~,~(ch_{6}~-~ch_{6})

Burunci cütlük üçün krossover nöqtəsi 3, ikinci və üçüncü cütlük üçün krossover nöqtəsi 2-dir.



скрещивание хромосом

скрещивание хромосом

Mutasiya ehtimalı p_{m}~=~0 olduqda, yeni populyasiyaya bu xromosomlar daxil edilir:




ch_{1}~=~10001

ch_{2}~=~10111

ch_{3}~=~10101

ch_{4}~=~11101

ch_{5}~=~11101

ch_{6}~=~11101

Dekodlaşdırma nəticəsində

{ch_{1}}^*~=~17

{ch_{2}}^*~=~23

{ch_{1}}^*~=~21

{ch_{4}}^*~=~29

{ch_{5}}^*~=~29

{ch_{6}}^*~=~29

Yeni populyasiyanın yayarlılıq funksiyası:

f(ch_{1})~=~579

f(ch_{2})~=~1059

f(ch_{3})~=~883

f(ch_{4})~=~1683

f(ch_{5})~=~1683

f(ch_{6})~=~1683

Yayarlılıq funksiyasının orta qiyməti 589-dan 1262-ə qalxmışdır.
: images -> muhazireler
muhazireler -> 1. F. Listin məhsuldar qüvvələr nəzəriyyəsi Y. Şumpeterin sahibkar-novator nəzəriyyəsi Q. Bekkerin insan kapitalı nəzəriyyəsi
muhazireler -> MÖvzu 8: BİLİKLƏRİn təQDİm ediLMƏSİNİn produksion modeli Plan
muhazireler -> Азярбайъан Дювлят Игтисад Университети
muhazireler -> 1. Əmək hüququnun anlayışı və mənbələri. Kollektiv müqavilə və saziş. Məşğulluğun və işədüzəltmənin təmin edilməsi
muhazireler -> Mövzu Firmanın (müəssisənin) inkişafı: məqsəd, mühit və təsir amilləri. Kursun predmeti və vəzifələri
muhazireler -> Азярбайжан дили və Nİtq məDƏNİYYƏTİ
muhazireler -> 1. Hüququn anlayışı. Dövlət və hüququn qarşılıqlı əlaqəsi. Hüquq normaları
muhazireler -> 1. Mülki hüququn anlayışı və sistemi. Mülki qanunvericilik. Mülki hüquq münasibətlərinin anlayışı, növləri və məzmunu




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2019
rəhbərliyinə müraciət

    Ana səhifə