Лекции.Орг


Поиск:




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




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

(4.3.1)

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

 

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

 

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

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





Поделиться с друзьями:


Дата добавления: 2015-02-12; Мы поможем в написании ваших работ!; просмотров: 520 | Нарушение авторских прав


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

Лучшие изречения:

В моем словаре нет слова «невозможно». © Наполеон Бонапарт
==> читать все изречения...

266 - | 241 -


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

Ген: 0.007 с.