Приближенные методы решения задач ЦП (Локальный перебор)

Локальный поиск основан на старейшем методе оптимизации - методе проб и ошибок. Рассмотрим задачу

Приближенные методы решения задач ЦП (Локальный перебор) - student2.ru Приближенные методы решения задач ЦП (Локальный перебор) - student2.ru (4.3.1)

где Приближенные методы решения задач ЦП (Локальный перебор) - student2.ru - целевая функция, Приближенные методы решения задач ЦП (Локальный перебор) - student2.ru - допустимое множество. Обозначим Приближенные методы решения задач ЦП (Локальный перебор) - student2.ru - окрестность точки Приближенные методы решения задач ЦП (Локальный перебор) - student2.ru . Понятие окрестности в задачах ЦП тесно связано с понятием “естественного” возмущения допустимого решения. Выбор возмущения основывается на специфике решаемой задачи. На рис.1. изображен путь в задаче коммивояжера и возмущение, внесенное заменой двух дуг этого пути.

Приближенные методы решения задач ЦП (Локальный перебор) - student2.ru

Рис.1. Смена двух дуг пути в ЗК.

Окрестность в ЗК можно определить как набор путей, получаемых из имеющегося пути Приближенные методы решения задач ЦП (Локальный перебор) - student2.ru заменой двух его произвольных дуг. В ЗК имеется возможность организовать замену Приближенные методы решения задач ЦП (Локальный перебор) - student2.ru , Приближенные методы решения задач ЦП (Локальный перебор) - student2.ru и т.д. дуг, что определяет размер окрестности.

Рассмотрим схему алгоритма локального поиска для задачи (4.3.1).

Наши рекомендации