Реферат: 2 Приближенные методы решения задач цп ( Локальный перебор )
2.7. Приближенные методы решения задач ЦП ( Локальный перебор ).
Локальный поиск основан на старейшем методе оптимизации - методе проб и ошибок. Рассмотрим задачу
(1)
где c(x) - целевая функция, F- допустимое множество. Обозначим N(x) F - окрестность точки x F. Понятие окрестности в задачах ЦП тесно связано с понятием “естественного” возмущения допустимого решения. Выбор возмущения основывается на специфике решаемой задачи. На рис.1. изображен путь в задаче коммивояжера и возмущение, внесенное заменой двух дуг этого пути.
2 3
1 4
6 5
рис.1. Смена двух дуг пути в ЗК.
Окрестность в ЗК можно определить как набор путей, получаемых из имеющегося пути S заменой двух его произвольных дуг. В ЗК имеется возможность организовать замену 2-х, 3-х и т .д. дуг, что определяет размер окрестности.
Рассмотрим схему алгоритма локального поиска для задачи (1).
Алгоритм локального поиска.
Задать начальное приближение x0 F , и систему окрестностей N(x) F для x F Положить k=0.
Найти точку минимума функции c(x) в окрестности N(xk).
Если, то { положить и перейти на п.2.}, иначе {останов}.
На практике бывает полезно осуществить локальный поиск из нескольких начальных точек. Поиск по окрестности в п.2. алгоритма может производится не полностью, а до первого улучшения уже имеющегося решения. В случае больших окрестностей и сложностью задания правил перебора точек окрестности возможна организация случайного перебора точек окрестности.
еще рефераты
Еще работы по разное
Реферат по разное
Секция “Краевые задачи в физике и химии твердого тела”
18 Сентября 2013
Реферат по разное
Применение алгоритмов адаптивной маршрутизации в протоколе igrp
18 Сентября 2013
Реферат по разное
Наталья Алексеевна
18 Сентября 2013
Реферат по разное
Название рабочей группы
18 Сентября 2013