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

Вид материала

Документы

Подобный материал:

• Приближенные методы решения уравнений, 78.01kb.
• Доклады по секции «Оптимальное управление», 22.31kb.
• Задачи и их решение Стандартные и нестандартные задачи Задачи «на работу» Задачи «на, 157.13kb.
• Урок математики в 4 классе по теме «алгебраические и арифметические методы решения, 9.7kb.
• Рабочая программа дисциплины «Методы решения оптимизационных задач в бизнесе» Рекомендуется, 114.73kb.
• 1 Общая характеристика оптимизационных задач и методов их решения, 47.12kb.
• Календарно-тематическое планирование элективного курса " методы решения физических, 107.87kb.
• Название дисциплины, 13.55kb.
• Васильев Ф. П. Численные методы решения экстремальных задач, 148.71kb.
• В. М. Трембач московский авиационный институт (технический университет) методы и средства, 32.06kb.

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

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

(1)

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

2 3




1 4




6 5

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

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

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

Алгоритм локального поиска.

1. Задать начальное приближение x⁰  F , и систему окрестностей N(x)  F для x  F Положить k=0.
   
2. Найти точку минимума функции c(x) в окрестности N(x^k).
   
3. Если, то { положить и перейти на п.2.}, иначе {останов}.
   

На практике бывает полезно осуществить локальный поиск из нескольких начальных точек. Поиск по окрестности в п.2. алгоритма может производится не полностью, а до первого улучшения уже имеющегося решения. В случае больших окрестностей и сложностью задания правил перебора точек окрестности возможна организация случайного перебора точек окрестности.