İstifadə olunan ixtisarların siyahısı

11.4. Genetik alqoritmlər
Genetik alqoritmlər (GA) müxtəlif tip məsələlərin (kombinator, məhdudluqlarla və məhdudsuzluqlarla verilən ümumi məsələlərin və s.) həlli üçün universal optimallaşdırma metodlarıdır. Genetik alqoritmlər geniş məkanda birkriteriyalı və çoxkriteriyalı axtarış imkanlarına malikdirlər.

GA təbii təkamül proseslərini modelləşdirən təkamül alqoritmlərinin bir növüdür. Bu alqoritmlər təbiətdə təbii təkamülə əsaslanırlar və onların əsas mexanizmlərindən istifadə edirlər. Çoxalma cütünü modelləşdirən axtarış alqoritmlərinə genetik alqoritmlər deyilir. Çoxalma cütü varislərin yaradılması üçün iki valideyn sətrin birləşdirilməsi ilə xarakterizə olunur. Bu cür birləşmə cütləşmə adlanır.

GA ilə iş zamanı məsələnin həlli binar, tamədədli və ya həqiqi ədədli kodlaşdırma ilə ifadə olunan sətir şəklində təsvir olunmalıdır. Sətirlər sabit və ya dəyişən uzunluqlu ola bilər, konteksdən asılı kodlaşdırmadan da istifadə edilə bilər.

Genetik alqoritmin genetik proqramdan (GP) əsas fərqi həll ağaclarından istifadə edilməsidir. Bu zaman genetik proqramda məsələnin genetik təsvirinə ehtiyac olmur. Bu cür sxem verilənlərin sturukturlarının təsvirində çeviklik yaradır, lakin həllin həcmi çox böyük alına bilər. Bu deyilənlər təkamül proqramları üçün də doğrudur.

Keçən əsrin 70-ci illərində Holland baza və ya standart genetik alqoritm təklif etmişdir. Aşağıda həmin alqoritm ümumiləşdirilmiş şəkildə verilmişdir.

1-ci addım. Məsələnin genetik təsviri.

2-ci addım. Fərdlərin ilkin populyasiyasının yaradılması.

3-cü addım. Orta yararlığın hesablanması. Hər bir fərd üçün yararlıq dərəcəsinin normallaşdırılmış qiymətinin hesablanması.

4-cü addım. Hər bir fərdə normallaşdırılmış yararlığa mütənasib ehtimalın təyin edilməsi.

5-ci addım. Alınmış paylanmalardan istifadə edərək ehtimallardan N sayda vektorun seçilməsi. Bununla da seçilən valideynlər yığımı formalaşdırılır.

6-cı addım. Həmin yığımdan ixtiyari olaraq N/2 sayda cütlüyün formalaşdırılması.

7-ci addım. Yeni populyasiya formalaşdırmaq üçün hər bir cütlüyə cütləşmənin, mütasiyanın və digər genetik operatorların tətbiqi.

8-ci addım. 3-cü addıma qayıdış.

Baxılan baza genetik alqoritmi sonradan ardıcıl və paralel modifikasiya üsulları ilə təkmilləşdirilmişdir. Ardıcıl modifikasiya üsulları fərdlərin secim sxemlərinin müxtəlif formalarını almaq üçün istifadə edilir.

Göründüyü kimi, baza alqoritmi sinxronlaşdırlmış ardıcıl alqoritmdir. Genetik alqoritmin tətbiqi ilə varisləri formalaşdırmaq məqsədilə ardıcıl olaraq daha yaxşı fərdlər cütləri seçilir. Bu isə böyük həcmli verilənlərdə axtarış vaxtını xeyli axtarır. Bu problemin həlli paralel genetik alqoritm vasitəsilə əldə edilir. GA-ın istənilən ardıcıl modifikasiyası paralel modifikasiyaya çevrilə bilər.

Parallelləşdirmə dərəcəsinə görə genetik alqoritmlərin aşağıdakı tiplərini ayırırlar: 1)populyasiya əsasında qurulan GA; 2)altpopulyasiya əsasında qurulan GA; 3)fərdlər əsasında qurulan GA.

1-ci halda bütöv populyasiya ilə işləyən GA-nın standart strukturu saxlanır. Parallelləşdirmə cütləşmə və mutasiya mərhələlərində reallaşdırılır.

2-ci halda fərdlərlə müəyyən tezliklə mübadilə vasitəsilə müstəqil rəqabət aparan altpopulyasiyalardan istifadə edilir. Bu zaman hər bir prosessor bloku öz altpopulyasiyası ilə ardıcıl genetik alqoritmi yerinə yetirir. Burada məqsəd bütün yararlıq dərəcələrinin ümumi qiymətlərini maksimuma çatdırmaqdır.

3-cü halda hər bir prosessor elemntində (xanada) daima saxlanan fərdlər sətri olur. Fərdlər cütləri seçir və digər fərdlərlə onların yaxın ətrafında birləşirlər.

Genetik alqoritmin səmərəliliyi genetik operatorların tətbiq ehtimalından, onların tipindən və populyasiyanın ölçüsündən xeyli asılıdır. Son illər genetik alqoritmlərin nəzəriyyəsinin və praktiki tətbiqinin inkişafı sahəsində aparılan işlərin sayı xeyli artmışdır. Həmin tədqiqatların nəticələri göstərir ki, genetik alqoritmlər digər metodlarla və texnologiyalarla inteqrasiya şəraitində daha geniş tətbiq oluna bilərlər. Genetik alqoritmlərin qeyri-səlis məntiq metodları ilə və həmçinin neyron sistemləri ilə inteqrasiyasının səmərəliliyi artıq sübuta yetirilmişdir.