Табу търсене
Табу търсене (на английски: tabu search), е метаевристичен метод за търсене, който използа методи за локално търсене и математическа оптимизация, създаден от Фред Глоувър през 1986 г.[1] и формализиран през 1989 г.[2][3] Може да се използва за решаването на задачи от областта на комбинаторната оптимизация, където се търси оптимална наредба и избор измежду алтернативи.
При търсенето в локално пространство се взимат кандидат-решенията на задачата и се търсят по-добри решения в тяхното непосредствено съседство (т.е. решения, които с много малка точност са идентични с потенциалните). Методите за локално търсене обаче имат склонност да попадат в субоптимални области на пространството или „плата“, където много от съседните решения са идентични.
Табу търсенето подобрява изпълнението на локалното търсене, като облекчава основното му правило.
- На всяка стъпка, ако не може да се намери подобряващо решение (т.е. алгоритъмът потенциално е попаднал в локален оптимум), методът допуска „влошаващ“ решението ход.
- В допълнение се въвеждат „забрани“ (откъдето и терминът „табу търсене“), които не позволяват на метода да се връща към вече обходени решения от пространството.
Реализацията на табу търсене използва структури памет, които описват обходените решения или зададените от потребителя набори от правила.[2] Ако едно потенциално решение е било вече обходено, или ако не удовлетворява някое от правилата, зададени от потребителя, то се отбелязва като „табу“ („забранено“), така че алгоритъмът да не се връща постоянно към него.
Източници[редактиране | редактиране на кода]
- ↑ Fred Glover. Future Paths for Integer Programming and Links to Artificial Intelligence // Computers and Operations Research 13 (5). 1986. DOI:10.1016/0305-0548(86)90048-1. с. 533–549.
- ↑ а б Fred Glover. Tabu Search – Part 1 // ORSA Journal on Computing 1 (2). 1989. DOI:10.1287/ijoc.1.3.190. с. 190–206.
- ↑ Fred Glover. Tabu Search – Part 2 // ORSA Journal on Computing 2 (1). 1990. DOI:10.1287/ijoc.2.1.4. с. 4–32.