книги из ГПНТБ / Большие системы и управление
..pdf150
Рис.27. Блок-схема алгоритма решения задачи коммивояжера по методу статистических испытаний, часть I
151
152
М - постоянная (число интервалов), используемая для построе ния функции распределения длины пути; с - постоянная, опреде ляемая приближенно как разность между точной верхней и нижней границей длины пути:
c = s u p * { i ( | 0 } - |
; |
|
ре ТС |
ре71 |
* |
- параметр програшш |
(Л = I соответствует |
случаю, когда осу |
ществляется локальная оптимизация, при > = |
0 локальная опти |
|
мизация не производится). Блок 2 соответствует началу цикла по числу испытаний. Блок 3 подготавливает величины к, х , /? , не
обходимые для получения случайной выборки (запись а |
озна |
||
чает замену |
величины ь величиной а ) • |
В блоке 4 осуществляет |
|
ся получение |
случайного числа £ е [о, 0 * |
имеющего равномерный |
|
закон распределения. Блок 5 является логическим блоком, позво ляющим установить место номера каждого пункта в перестановке
fi^ = [б0 , Ь(2\ Ь('*\. . . , 6^, ZTJ ,блок 7 - ' блоком приформирования оче
редного номера пункта в выборке. Оператор А}(р*1к) по номеру отыскивает Ъ к в последовательности р и приформировывает к вы борке очередной элемент. Пооле перехода к блоку 9 выборка при обретает законченный вид. Оператор А2 (В) осуществляет "вычерки-
Рис.29. Изменение времени счета в зависимости от числа испытаний
153
ванне” выбранного пункта из последовательности ц и "склеива ние" оставшихся членов последовательности. В блоке 9 оператор
А) вычисляет протяженность маршрута ^ (<*}в соответ ствии с матрицей кратчайших расстояний А . Логический блок 10 осуществляет проверку, производится (л Ф 0) локальная оптимиза ция или не производится (Л = 0) .
I
1500
1400
1300
20 |
200 |
400 |
600 |
800 |
1000 |
N |
Рис *30. Изменение длины маршрута в зависимости от числа испы тании; /7 = 6, П - Ю
Рис.31. Изменение длины маршрута в зависимости от числа испы
таний; /7 = 2 0 |
|
|
Блоки I I - 14 подготавливают исходные |
данные для |
построе |
ния функции распределения длины пути I . |
В блоках 17 |
и 18 вы |
бираются минимальная протяженность и соответствующий ей маршрут.
154
Блок 19 дозволяет установить, все ли пути в окрестности слу чайной выборки получены. Операторы блока 20 вычисляют очеред ной путь в окрестности выборки |д ^ . Блок 21 проверяет конец цикла по числу испытаний. Блок 22 вычисляет математическое ожи
дание Л7 [£] и дисперсию В Щ длины ^ути . Блок 23 - |
блок печа |
ти результатов (печатаются длина минимального пути, |
минимальг- |
ный путь гистограмма, Л7[£]и D [ l\ ), |
|
Рис.32. Изменение длины маршрута в зависимости от числа испы тании; п = 15
На ри с.29 показано изменение времени счета на ЦШ М-20 в
зависимости от |
числа испытаний (N) при различном |
количестве |
|
пунктов обхода |
(/?). |
|
|
Рис.30 иллюстрирует изменение длины маршрута |
в зависимо |
||
сти от числа испытаний для |
л = 6 и л = 10 . |
|
|
Аналогичные зависимости |
показаны-на рис.31 и 32. Эти зави |
||
симости свидетельствуют о том, что время расчетов прямо пропор
ционально числу |
испытаний при |
заданном числе пунктов обхода п . |
||
При |
л = 6 оптимальное решение |
получено для числа |
испытаний |
|
N = |
800, £ = 15 |
сек. По методу динамического программирования |
||
решение этой задачи заняло 3 мин. Таким образом, |
выигрыш во |
|||
времени в данном |
случае значителен - время счета |
получается |
||
в .12 раз меньше, чем по методу динамического программирования. Для получения оптимального решения с возрастанием л число испытаний растет как nl . Метод статистических испытаний гаран
155
тирует оптимальность решения с некоторой вероятностью. Рассмот рим основную идею определения числа испытаний в зависимости от гарантийной вероятности (Рг ) получения оптимального решения [23].
В области [^Функция принимает М значений, и су ществует точка р Qe VL такая, что
г(Ио) = min I ( p j . Hi6 **.
Будем считать известной вероятность Р (р -) того, что р,-ееть точка максимума:
P(\4) = P\yi = Yo' ] ^P( Vi ) = l-
Так как в одном испытании может быть выбрана только одна точка вероятностно ae (p;)f т .е . один из возможных об ходов, то после N1независимых выборок вероятность того, что точка ц- будет выбрана хотя бы один раз, составит
pi ( Ni) = 7“ |
|
. |
(18) |
Совокупность вероятностей 2e(p L)определяет процедуру |
поиска |
||
оптимальной точки. Имеет место равенство |
|
||
E * |
( |
h i ) = / - |
<19> |
1 = 1 |
|
|
|
Вероятность того, что после |
/У, испытаний получим оптималь |
||
ное решение, составит: |
|
|
|
P ( n ,) = £ |
4 |
|
(2°) |
1=1 |
|
|
|
Выражение (20) позволяет |
определить число испытаний |
Н ^ е с |
|
ли задаться гарантийной вероятностью Рг получения оптимального решения. Так, если P ( p i ) = ^ » то число испытаний N , необхо
димое для выбора р- точки, можно определить по формуле
/V. -
и) In (? -эе (рг))
Оптимальную процедуру поиска ( т . е . вероятности з е ( р * ) , достав
156
ляющие максимум функции р ( /V;) при заданном числе испытаний /V,), можно подучить с помощнэ метода неопределенных множителей Лагранжа из условия максимума P(/v7) при ограничении (19)* После проведения необходимых вычислений получаются для оптимальных
ж (fj L) следующие выражения:
М- 1 |
( t = / , 2 , . . . , М). |
э е ( ^ ) = |
|
Е |
V i |
i=i |
т о |
Следует отметить, что метод ненаправленного поиска ( т . е . |
|
перебора вариантов, при котором подозреваемые на глобальный |
|
экстремум точки выбираются в области случайным образом по рав-^ н(мерному закону) малоэффективен для задач большой размерности* Поэтому для оптимизации используется часто сочетание метода случайного поиска с градиентными методами, а также различные методы направленного поиска. К последним относится метод после довательно улучшаемых гипотез С24]» сущность которого заключа ется в следующем. Строится аналитически исходная вероятностная гипотеза о принадлежности каждой точки из области поиска к об ласти допустимых решений и о наличии в этой точке глобального экстремума. В соответствии с построенной исходной вероятност ной гипотезой организуется поиск глобального экстремума, при чем в окрестности глобального экстремума плотность случайно выбираемых точек будет наибольшей.
После проведения некоторого количества испытаний целесо образно уточнить исходную априорную вероятностную гипотезу, используя апостериорную информацию.
В применении к решению задачи коммивояжера идею метода по следовательно улучшаемых гипотез можно реализовать при построе нии начальной априорной гипотезы. Интервал (ОД) разбивается на подынтервалы так, что координаты концов подынтервалов обра зуют последовательность
|
г = ^ii + ? Iе ’ ' " |
’ ^in ~ п-1 + Яьп ' |
||
Числа |
рассчитываются по формуле |
|
||
Ч |
|
|
|
|
(V |
|
П |
(21) |
|
яя |
G ; |
= £ а |
||
Ч |
||||
|
|
<Г7 |
|
|
157
Здесь поощрение уменьшения по индексу J ставится в зависимо сти от маршрута обхода 1( ц) •
Начальный пункт i Q фиксирован* Используя равномерный закон
распределения, выбирается некоторый элемент |
• Столбец с |
номером l0 в матрице А вычеркивается. Элементы0 |
пересчиты |
ваются по формулам (2 1 ) с учетом выбранного столбда.-Затем в строке с номером j , используя равномерный закон распреде^ ления, находится элемент (jfj tj н« Процесс продолжается до полно
го вычеркивания столбцов. По выбранным элементам и матрице А строится Z( Поиск прекращается, если последующие выборки не приводят к уменьшению Z (p ) .
Применение метода приводит к лучшим результатам по сравне нию с методом ненаправленного поиска.
|
|
ЛИТЕРАТУРА |
|
I* Т р и у с |
Е .Б ., |
Задачи математического |
программирова |
ния транспортного |
типа, |
"Советское радио", М, |
1967. |
2 . Б е р ж К ., Теория графов и ее применения, Изд. иностр.
лит., 1962.
3. |
Г и л л |
А., |
Введение |
в теорию конечных автоматов, "На |
|||
ука", |
1966. |
|
|
|
|
|
|
4. |
З у х о в и ц к и й |
С.И., Р а д |
ч и к |
И.А., |
Матема |
||
тические методы сетевого планирования, "Наука", |
1965. |
|
|||||
5 . |
Б р е х о в |
А.М., Применение методов сетевого |
планиро |
||||
вания и управления в судостроении, Судпромгиз, 1967. |
|
||||||
6. |
Ф о р д |
Л. , |
Ф а л к е р с о н |
Д ., Потоки е |
сетях, |
||
"Мир", |
1966. |
|
|
|
|
|
|
7 . Ч е р н е ц к и й |
В.И ., |
Б а к у р а д з е Д .В ., |
|||||||
П а н ф и л о в |
И.В., |
Г р и г о р ь е в а |
Л.И ., |
С о |
|||||
б о л е в с к и й |
М.Й., |
Сетевые методы и их реализация на |
|||||||
ЭВМ, ЛЕЙКА им. А.Ф.Можайского, 1966. |
|
|
|
||||||
8. S h r o c K |
& . R . j A l q o r l t m s a n d |
analog compu |
|||||||
t e r s |
f o r |
m o s t |
r e l i a b l e |
r o u t e |
t h r o u g h a |
n e t w -огк, |
|||
D p e r a t . |
R e s . v. |
72 7 1964, |
N 4 . |
|
|
|
|
||
9. |
|
Ю д и н |
Д .Б ., |
Г о л ь ш т е й н |
Е .Г ., |
Задачи и ме |
|||
тоды линейного программирования,- "Советское радио", |
1961. |
||||||||
10. |
Р е й н ф е л ь д |
й .Р . .и Ф о г е л ь |
У ., |
Математи |
|||||
ческое |
программирование, |
Изд. |
иностр. |
ли т., I960. |
|
||||
11. |
К а н т о р о в и ч |
Л .В ., |
Г а |
в у р и н |
М.К., Приме |
||||
нение математических методов |
в вопросах анализа грузопотоков, |
||||||||
Сб. "Проблемы повышения эффективности работы транспорта", Изд. АН СССР, 1949.
158
12. Я к о в л е в а М.А., Задача* о минимуме транспортшах затрат"• Сб. "Применение математики в экономических иссле дованиях", Соцэкгиз, 1959.
13.К а р п Р.М ., Заметка о приложении теории графов к программированию, Кибернетический сборник Л 4, Изд. иностр.
14.М у д р о в В.И ., Один способ решения задачи комми вояжера с помощыз целочисленного линейного программирования,
"Вычислительная математика и математическая физика", т .З , 1963, Л 6.
15 . H e l d М. a n d \ K a r p R . M . , А В у па mi с P r o g
r a m m i n g |
A p p r o a c h |
to |
S е д и е n c i g |
P r o b l e m s |
Opera |
||
t i o n s |
R e s |
. , |
10, 1962. |
|
|
|
|
16. |
K a r p |
R.L< |
a n d |
T h o m p s o n |
G. L . , A |
H e u r i s |
|
t i c A p p r o a c h to T r a v e l i n g S a l e s m a n P r o b l e m s ,
M a n a g e m e n t |
S c i |
10, |
196b* |
17. G o т о |
г у |
R. F |
1 O u t l i n e o f an a l g o r i t h m |
f o r i n t e g e r s o l u t i o n s to l i n e a r , p r o g r a m s . B u l l .
A m e n |
M a t h . S o c . , |
1958, 6 b , N5. |
|
18. |
К о р б у т |
А.А., Целочисленные задачи линейного про- |
|
граши^ования, Сб. "Экономико-математические методы", вып.2 , |
|||
19. |
M i l l e г |
С, Е. |
7 Ти с н е г А . W. , L e m l i n R. A., |
I n t e g e r p r o g r a m m i n g |
f o r m u l a t i o n o f t r a v e l l i n g |
s a l e s m a n p r o b l e m s , |
0. A s s o c . C o m p u t M a c h i n e r y ? |
7 , N b , |
1960. |
|
|
|
|
20. |
X e |
д л и |
Дж., |
Нелинейное |
и динамическое программи |
рование, "Мир", 1967. |
|
|
|||
21. |
Е в |
с т и г |
н е |
е в В.А ., |
Об оптимальном весе эле |
ментов сети, |
"Проблемы кибернетики, |
1966, Л 17. |
|||
2 2 mR e i t e r S . , S h e r m a n G . 7 d i s c r e t e o p t i m i s i n g , J o u r n a l o f t h e S o c i e t y f o r I n d u s t r i a l
A p p l i c a t i o n s o f M a t h e m a t i c e , 1965,September,v*13,4oS*
23. Б а к у р а д з е Д .В ., Метод априорной гипотезы его применения в некоторых задачах оптимизации. "Математиче ское моделирование на электронных вычислительных машинах про цессов организации планирования управления" (пособие для ис-
Жваний и проектирования под редакцией В.И. Чернецкого), им. А.Ф.можайекого, 1967.
24.Ч е р н е ц к и й В.И ., Метод последовательно ул шенных гипотез для решения задач выбора оптимальных парамет
ров систем управления. "Математическое моделирование", ЛБИКА им. А.Ф.Можайского, 1967.
25. |
С а й р е з Д ., М о р т о н , Обслуживание многок |
нальных систем как стохастический аналог задачи коммивояжера,
159
" Экспресс-информация, Техническая кибернетика", 1966, Л 48*
2§. З а й ч и к МД., Метод решения класса целочисленных распределительных задач, ж. "Экономика и математические мето ды", 1966, №2.
27. 3 а р е м б а И.И., Исследование операций, часть П, Некоторые математические методы, ЛВИКА им. А.Ф. Можайского, 1967.