Metaevristik

Kompüter elmi və riyazi optimallaşdırmada metaevristik alqoritm — optimallaşdırma və ya maşın öyrənməsi problemi üçün kifayət qədər yaxşı həll tapa, yarada, tənzimləyə və ya seçə bilən (tam axtarış alqoritminin qismən forması olan) bir evristikanı müəyyənləşdirmək və ya qurmaq məqsədilə hazırlanmış yüksək səviyyəli prosedur və ya evristikadır. Metaevristikalar, tam şəkildə sadalamaq və ya araşdırmaq üçün həddindən artıq böyük olan həll məkanının yalnız bir alt çoxluğunu nümunələndirir. Onlar həll edilən optimallaşdırma problemi haqqında nisbətən az fərziyyə irəli sürdüyündən, müxtəlif məsələlərdə tətbiq oluna bilər.  Bu yanaşma, dəqiq və ya digər (təxmini) metodlar mövcud olmadıqda və ya məqsədəuyğun olmadıqda, məsələn, hesablamanın çox uzun çəkməsi və ya əldə olunan həllin çox qeyri-dəqiq olması hallarında xüsusi maraq kəsb edir.

Optimallaşdırma alqoritmləri və iterativ metodlarla müqayisədə metaevristikalar bəzi problemlər sinfi üzrə qlobal optimal həll tapılacağına zəmanət vermir. Bir çox metaevristika təsadüfi optimallaşdırmanın () müəyyən formalarını tətbiq edir, belə ki, tapılan həll yaradılmış təsadüfi dəyişənlər toplusundan asılı olur. Kombinator optimallaşdırmada NP-tam sinfinə aid olan çoxlu məsələlər mövcuddur və bu səbəbdən nisbətən aşağı mürəkkəblik dərəcəsindən sonra belə onları qəbul edilə bilən vaxt ərzində dəqiq həll etmək mümkün olmur.Metaevritikalar isə tez-tez təxmini metodlara, iterativ üsullara və sadə heuristikalara nisbətən daha az hesablamalı resurs tələb etməklə yaxşı həllər təqdim edir. Bu, davamlı və ya qarışıq-tam ədədi optimallaşdırma sahəsinə də aiddir. Beləliklə, metaevristikalar optimallaşdırma məsələlərinin həlli üçün faydalı yanaşmalardır. Bu mövzuda bir sıra kitablar və icmal məqalələri nəşr edilmişdir. Metaevristik optimallaşdırma üzrə ədəbiyyat icmalı göstərir ki, “metaevristika” terminini ilk dəfə Fred Qlover işlətmişdir. 

Metaevristikalar haqqında ədəbiyyatın böyük hissəsi eksperimental xarakter daşıyır və alqoritmlərlə aparılmış kompüter təcrübələrinə əsaslanan empirik nəticələri təsvir edir. Lakin qlobal optimal həllin tapılması və yaxınlaşma (convergence) kimi mövzuları əhatə edən bəzi formal nəzəri nəticələr də mövcuddur. Bundan əlavə, “heç bir üstünlük yoxdur” (no-free-lunch) teoremləri də qeyd olunmalıdır; bu teoremlərə görə, hər hansı bir verilmiş problem üçün bütün digər metaevristikalardan üstün olan universal bir metaevristika mövcud ola bilməz.

Xüsusən minilliyin əvvəllərindən bəri, yenilik və praktiki səmərəlilik iddiaları ilə çoxlu metaevristik metodlar dərc edilmişdir. Bu sahədə yüksək keyfiyyətli tədqiqatlar mövcud olsa da, son dövrlərdə nəşr olunan işlərin əksəriyyəti zəif keyfiyyətli olmuşdur; bu cür işlərin çatışmazlıqları sırasına qeyri-müəyyənlik, konseptual izahın azlığı, zəif eksperimentlər və əvvəlki ədəbiyyata biganəlik daxildir.

 Tarixi 
Metaevristik yanaşmaların inkişafı riyaziyyat, əməliyyatlar tədqiqi, süni intellekt və kompüter elmlərinin kəsişməsində formalaşmışdır. Bu sahənin tarixi 20-ci əsrin ortalarından başlayaraq bir neçə əsas mərhələ ilə izah olunur.

Metaevristiklərin nəzəri əsasları 1950–60-cı illərdə əməliyyatlar tədqiqi və optimallaşdırma metodlarının inkişafı ilə qoyuldu. Bu dövrdə Monte-Karlo üsulları, təkrarlanan axtarış və stoxastik optimallaşdırma kimi yanaşmalar hələ “metaevristik” termini işlədilməsə də, sonrakı metodlara zəmin yaratdı. 1953-cü ildə Metropolis alqoritmi və 1965-ci ildə Təqlidi soyutma (Simulated Annealing) ideyalarının riyazi əsası qoyuldu. Evristik (problemə uyğun təxmini) axtarış anlayışı əməliyyatlar tədqiqində geniş istifadə olunurdu.

1970-ci illərdə təkamül prinsipinə əsaslanan alqoritmlər – Genetik alqoritmlər (John Holland, 1975) və Evrim strategiyaları – metaevristiklərin yeni mərhələsini başlatdı. 1983-cü ildə Fred Qlover tərəfindən hazırlanan Tabu axtarışı () böyük təsir göstərdi və 1986-cı ildə “metaheuristic” termini məhz Qlover tərəfindən irəli sürüldü. 1980-ci illərin sonlarında Təqlidi soyutma sənaye optimallaşdırmasında geniş tətbiq olundu. Bu mərhələdə əsas ideya hər hansı bir tək metodun deyil, müxtəlif problem sahələrində işləyən “yuxarı səviyyəli” axtarış strategiyasının qurulması idi.

1990-cı illər metaevristiklərin “qızıl dövrü” hesab olunur. Çoxsaylı yeni alqoritmlər təklif edildi:

 Hissəcik sürüsü optimallaşdırması (PSO) – Kennedy və Eberhart, 1995
 Karınca koloniyası optimallaşdırması (ACO) – Dorigo, 1996
 Differensial evolyusiya, Arı koloniyası, Harmony search və s.

Bu metodlar mühəndislik, logistika, qraf planlaşdırma və maşın öyrənməsi kimi müxtəlif sahələrdə geniş tətbiq olundu. Paralel hesablama və paylanmış sistemlərin inkişafı daha böyük axtarış məkanlarını araşdırmağa imkan verdi.

Son onilliklərdə metaevristiklərin tətbiq sahəsi sürətlə genişlənmişdir: böyük verilənlər, dərin öyrənmə, bioinformatika, enerji şəbəkələri və s. Lakin bu dövrdə yüzlərlə “yeni” alqoritm təqdim olunmuş, onların bəziləri əvvəlkilərin sadə variasiyaları olmuşdur. Tədqiqatçılar sahədəki problemlərə diqqət çəkirlər:

No-Free-Lunch teoremləri göstərir ki, bütün problemlər üçün universal ən yaxşı metaevristik mövcud deyil. Bəzi məqalələrdə zəif eksperimentlər və əvvəlki ədəbiyyata istinadın azlığı müşahidə olunur. Buna baxmayaraq, metaevristik alqoritmlər hələ də kombinator optimallaşdırma, qarışıq-tam ədədi proqramlaşdırma və davamlı optimallaşdırma problemlərində əsas yanaşmalardan biri kimi qalır.

Metaevristik alqoritmlərin tarixi 70 ildən artıq tədqiqat və tətbiq mərhələlərini əhatə edir. Stoxastik axtarışın erkən ideyalarından başlayaraq genetik və sürü əsaslı üsullara qədər inkişaf edən bu metodlar bu gün də böyük miqyaslı və mürəkkəb optimallaşdırma problemlərinin həllində mühüm rol oynayır.

 İstinadlar 

 Ədəbiyyat 

 Ashish Sharma (2022), Nature Inspired Algorithms with Randomized Hypercomputational Perspective. Information Sciences. https://doi.org/10.1016/j.ins.2022.05.020.

 Xarici keçidlər 
EU/ME forum for researchers in the field.
Metaheuristics.jl Source of some implementations.

Kateqoriya:Kompüter elmləri və cəmiyyət