Metasezgisel

Metasezgisel (metaheuristic), arama uzayını yerel optimumların ötesinde dolaşmak üzere tasarlanmış stratejik üst-çerçeve algoritmaları için kullanılan şemsiye terimdir. Terim Glover'ın 1986 tarihli çalışmasında (tabu search çerçevesinde) ortaya atılmış ve 1990'larda OR literatüründe standartlaşmıştır. Başlıca metasezgisel aileler şunlardır: (1) tabu search (Glover 1989) — yerel arama hareketlerini bir tabu listesiyle yasaklayarak döngüye girmeyi engeller; (2) simulated annealing (Kirkpatrick, Gelatt ve Vecchi 1983) — fizikten esinlenen sıcaklık parametresiyle olasılıksal kötüleşmeye izin verir; (3) genetic algorithm (Holland 1975) — popülasyon, seçilim, çaprazlama ve mutasyon ile evrimsel arama yapar; (4) variable neighborhood search (Mladenović ve Hansen 1997) — çoklu komşuluk yapıları arasında sistematik geçiş; (5) GRASP (Feo ve Resende 1995) — randomize-greedy yapım + yerel arama; (6) ant colony optimization (Dorigo 1992) ve particle swarm (Kennedy ve Eberhart 1995). Hibrit metasezgiseller (matheuristic) son 20 yılda öne çıkmıştır — MIP solver'ı bir metasezgiselin alt-problem çözücüsü olarak kullanır. Metasezgisellerin parametre ayarı (irofi: tabu liste uzunluğu, soğutma şeması, popülasyon boyutu, mutasyon oranı) kalite-süre dengesini büyük ölçüde belirler. Standart referanslar Glover ve Kochenberger (2003), Talbi (2009) ve Gendreau ve Potvin (2010) Handbook of Metaheuristics.