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

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

(4.3.1)

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

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

Окрестность в ЗК можно определить как набор путей, получаемых из имеющегося пути заменой двух его произвольных дуг. В ЗК имеется возможность организовать замену , и т.д. дуг, что определяет размер окрестности.

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

Дата добавления: 2015-02-12; просмотров: 399 | Нарушение авторских прав | Изречения для студентов

Читайте также:

ПОЧЕМУ МОГУТ ВОЗНИКНУТЬ ССОРЫ МЕЖДУ СУПРУГАМИ, В ТО ВРЕМЯ КАК ИХ ОТНОШЕНИЯ КАЖУТСЯ ПРОЧНЫМИ

Почему все попытки создания мегагосударств XX столетия провалились

Знаете ли вы? Почему вы не становитесь копией своей матери

ПОЧЕМУ ПСИХИЧЕСКИ ЗДОРОВЫМ ЛЮДЯМ МОЖЕТ ПОНАДОБИТЬСЯ КОНСУЛЬТАЦИЯ СПЕЦИАЛИСТА

Рекомендуемый контект:

Поиск на сайте:

© 2015-2021 lektsii.org - Контакты - Последнее добавление