Итеративно локално търсене

Итеративното локално търсене (на английски: Iterated local search) е прост, но мощен метаевристичен алгоритъм. При него се прилага локално търсене към начално кандидат-решение докато не бъде открит локален оптимум и след това се извършва т.нар. „пертурбация“ на решението и локалното търсене започва наново. Значението на пертурбацията е в диверсифицирането на решенията и недопускане алгоритъмът за търсене да се „забие“ в локален оптимум, който е субоптимален спрямо глобалния. От една страна, твърде слабата пертурбация може да не успее да извади системата от областта на последно открития локален оптимум, от друга – твърде силната може да накара алгоритъмът да се държи като алгоритъм за локално търсене със случайни условия за рестарт.

Итеративното локално търсене „изстрелва“ решението извън региона на привличане на последния открит локален оптимум.

Локалното търсене е ефективно, когато е способно да открие добър локален оптимум, т.е. регион на привличане (basin of attraction) към локално оптималното решение. Когато пространството на търсене е голямо и/или регионът на привличане към добрия локален оптимум е малък, простият алгоритъм за локално търсене със случайни стартове е почти неприложим. Въвеждането на пертурбацията се изисква, за да се генерира нова стартова точка за локалното търсене, такава че да е различна от текущо достигнатия локален оптимум, но същевременно и по-близка до текущата от начална точка, генерирата по напълно случаен начин. Въвеждането на критерии за предпочитание на решението действа като „противотежест“ на стъпката на пертурбацията, като на база характеристиките на новия локален оптимум дава обратна връзка (оценка) за резултата от пертурбацията.

Контролни параметри

При проектирането на алгоритъм за итеративно локално търсене, има няколко контролни параметъра (още „степени на свобода“) в избора на начално решение, стъпка на пертурбацията и критерии за предпочитание на решението.

• Началното решение следва да се конструира бързо и да е добра отправна точка за локалното търсене. Най-бързият начин за генериране на начално решение е на случаен принцип, но това е най-лесният вариант при задачи, в които няма удовлетворяване на ограничения. При задачи с удовлетворяване на ограничения, конструирането на допустимо решение изисква допълнителни проверки относно ограниченията.

• Пертурбацията обикновено е недетерминирана, с цел да се избегне зациклянето. Първана и най-важната ѝ характеристика е силата на пертурбацията, λ, условно орпеделена като количеството промени, с които новото решение се различава от текущото (т.е. разстоянието между двете, в зависимост как е определено пространството на решенията). Този параметър може да е константен или променлив. В първия случай разстоянието е постоянно без значение от размера на пространството на решенията и проблема. В общия случай, по-ефективни са алгоритмите с променлива сила на пертурбацията, тъй като експериментално е открито, че при повечето задачи колкото по-голямо е пространството на търсене, толкова по-голяма трябва да бъде силата на пертурбацията.
  Втората характеристика на пертурбацията се заключава в избора на механизъм за извършване на пертурбацията. Този механизъм отново може да е случаен, или пертурбацията може да се извършва по детерминиран или недетерминиран метод.

• Третата важна характеристика е критерият за предпочитание на решение (acceptance criterion). Два противоположни по смисъл примера за критерии са: (1) предпочитане на новия локален оптимум само в случай на регистрирано подобрение на решението, и (2) предпочитане на новото решение винаги, във всички случаи. Между тези две крайности също съществуват различни възможности.

Реализацията на алгоритъма за итеративно локално търсене зависи от това как тези няколко контролни параметъра ще бъдат определени във всеки отделен случай. Изборът на подходяща сила на пертурбацията λ е от ключово значение за изпълнението на алгоритъма. Стойността на параметъра λ намалява по време на процеса на търсене, т.е. в началото на търсенето има голяма диверсификация на решенията, и постепенно по пътя на търсене, се засилва интензификацията. Следователно с избора на подходяща λ се постига динамично равновесие между диверсификацията и интензификацията като двата основни компонента на всеки метаевристичен алгоритъм.

Източници

• Behrouz Afshar-Nadjafi, “An Iterated Local Search Algorithm for Estimating the Parameters of the Gamma/Gompertz Distribution,” Modelling and Simulation in Engineering, vol. 2014, Article ID 629693, 7 pages, 2014. doi:10.1155/2014/629693

Вижте също

• Итерация