MÖvzu 12: genetik alqoritmləR

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. p_m 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. funksiyası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 ch_i, i=1,...,N xromosomunun yaşamı f(x) funksiyası ilə təyin olunur. Fenotipləri ch_i* işarə edək. Qoy bu xromosomlar seçilib:


Onların fenotipləri:


Yararlılıq funksiyası:


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

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ı olduqda, yeni populyasiyaya bu xromosomlar daxil edilir:

Dekodlaşdırma nəticəsində

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

Yayarlılıq funksiyasının orta qiyməti 589-dan 1262-ə qalxmışdır.