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[1][2] 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.[3][4] 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.[5]
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.[6] Bir çox metaevristika təsadüfi optimallaşdırmanın (ing. stochastic optimization) 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.[7] 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.[8] 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.[9][10] Metaevristik optimallaşdırma üzrə ədəbiyyat icmalı göstərir ki, “metaevristika” terminini ilk dəfə Fred Qlover işlətmişdir.[11]
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.[12][13] 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.[14] 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.[15]
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ışı (ing. Tabu Search) 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.
- ↑ Socha, Krzysztof; Dorigo, Marco. "Ant colony optimization for continuous domains". European Journal of Operational Research (ingilis). 185 (3). 2008: 1155–1173. doi:10.1016/j.ejor.2006.06.046.
- ↑ Nissen, Volker; Krause, Matthias, Reusch, Bernd (redaktor), "Constrained Combinatorial Optimization with an Evolution Strategy", Fuzzy Logik, Berlin, Heidelberg: Springer Berlin Heidelberg, 1994, 33–40, doi:10.1007/978-3-642-79386-8_5, ISBN 978-3-540-58649-4, İstifadə tarixi: 24 avqust 2024
- ↑ Schwefel, Hans-Paul. Evolution and optimum seeking. Sixth-generation computer technology series. New York: Wiley. 1995. ISBN 978-0-471-57148-3.
- ↑ Eberhart, R.; Kennedy, J., "A new optimizer using particle swarm theory", Conf. Proc. MHS'95, IEEE, 1995, 39–43, doi:10.1109/MHS.1995.494215, ISBN 978-0-7803-2676-7
- ↑ Colorni, Alberto; Dorigo, Marco; Maniezzo, Vittorio, Varela, F.; Bourgine, P. (redaktorlar ), "Distributed Optimization by Ant Colonies", Conf. Proc. of ECAL91 - European Conference on Artificial Life, Amsterdam: Elsevier Publ., 1991, 134–142, ISBN 9780262720199
- ↑ Raidl, Günther R., Almeida, Francisco; Blesa Aguilera, María J.; Blum, Christian; Moreno Vega, José Marcos (redaktorlar ), "A Unified View on Hybrid Metaheuristics", Hybrid Metaheuristics, Lecture Notes in Computer Science, Berlin, Heidelberg: Springer Berlin Heidelberg, 4030, 2006, 1–12, doi:10.1007/11890584_1, ISBN 978-3-540-46384-9, İstifadə tarixi: 24 avqust 2024
- ↑ D, Binu. "RideNN: A New Rider Optimization Algorithm-Based Neural Network for Fault Diagnosis in Analog Circuits". IEEE Transactions on Instrumentation and Measurement. 68 (1). 2019: 2–26. Bibcode:2019ITIM...68....2B. doi:10.1109/TIM.2018.2836058.
- ↑ Pang, Shinsiong; Chen, Mu-Chen. "Optimize railway crew scheduling by using modified bacterial foraging algorithm". Computers & Industrial Engineering (ingilis). 180. 1 iyun 2023. doi:10.1016/j.cie.2023.109218. ISSN 0360-8352.
- ↑ Glover, Fred; Sörensen, Kenneth. "Metaheuristics". Scholarpedia (ingilis). 10 (4). 2015: 6532. doi:10.4249/scholarpedia.6532. ISSN 1941-6016.
- ↑ Birattari, Mauro; Paquete, Luis; Stützle, Thomas; Varrentrapp, Klaus. "Classification of Metaheuristics and Design of Experiments for the Analysis of Components". 2001.
- ↑ Cantú-Paz, Erick. Efficient and Accurate Parallel Genetic Algorithms. Genetic Algorithms and Evolutionary Computation. 1. Boston, MA: Springer US. 2001. doi:10.1007/978-1-4615-4369-5. ISBN 978-1-4613-6964-6.
- ↑ Sudholt, Dirk, Kacprzyk, Janusz; Pedrycz, Witold (redaktorlar ), "Parallel Evolutionary Algorithms", Springer Handbook of Computational Intelligence (ingilis), Berlin, Heidelberg: Springer, 2015, 929–959, doi:10.1007/978-3-662-43505-2_46, ISBN 978-3-662-43504-5, İstifadə tarixi: 4 sentyabr 2024
- ↑ Khalloof, Hatem; Mohammad, Mohammad; Shahoud, Shadi; Duepmeier, Clemens; Hagenmeyer, Veit, "A Generic Flexible and Scalable Framework for Hierarchical Parallelization of Population-Based Metaheuristics", Proc. of the 12th Int. Conf. on Management of Digital EcoSystems (MEDES'20) (ingilis), ACM, 2 noyabr 2020, 124–131, doi:10.1145/3415958.3433041, ISBN 978-1-4503-8115-4
- ↑ Goldberg, D.E. Genetic Algorithms in Search, Optimization and Machine Learning. Kluwer Academic Publishers. 1989. ISBN 978-0-201-15767-3.
- ↑ Mercer, R.E.; Sampson, J.R. "Adaptive search using a reproductive metaplan". Kybernetes. 7 (3). 1978: 215–228. doi:10.1108/eb005486.
- Sörensen, Kenneth; Sevaux, Marc; Glover, Fred. A History of Metaheuristics (PDF) // Martí, Rafael; Panos, Pardalos; Resende, Mauricio (redaktorlar ). Handbook of Heuristics. Springer. 16 yanvar 2017. ISBN 978-3-319-07123-7.
- Ashish Sharma (2022), Nature Inspired Algorithms with Randomized Hypercomputational Perspective. Information Sciences. https://doi.org/10.1016/j.ins.2022.05.020.
- EU/ME forum for researchers in the field.
- Metaheuristics.jl Source of some implementations.