Проверяемый текст
Ковалев, Игорь Владимирович. Система мультиверсионного формирования программного обеспечения управления космическими аппаратами (Диссертация 1997)
[стр. 107]

107 7.3а решение задачи принимаегся вектор А*, определяемый из условия ;rCT) = mhlzL-Jt=l,K Случайный поиск с возвратом Так как величина шагов К и /г+ обратно пропорциональна произведению Rn, то при больших размерностях (и>50) адаптация в алгоритме СПА практически отсутствует, и алгоритм вырождается в случайный перебор.
Для нашей задачи так же характерны большие размерности, как, впрочем, и недостаток априорной и апостериорной информации В такой ситуации кажется эффективным алгоритм, реализующий идею случайного поиска с возвратом (СПВ).
Рассмотрим его работу при решении задачи x(x)-^extr’ XeS S={XeD\ fx.=m}.
j=i 1.При отсутствии априорных сведений о задаче Р° = 1—,К ,—L 1=0, к=0 \п п\ (здесь I номер координаты; к номер этапа поиска).
2.
Случайным образом (в соответствии с распределением
Рк, к = 0,1,К ), независимо выбираются г векторов Хе S, i = 1,г.
3.
Вычисляются %(Х'), i = 1,г.
4.Определяется лучшее значение функционала / = 0 _ J ,=v %к~ mm(Zi_1,Z(Xi),Z>0 Если %к < , то 1=0.
5.1 = 1 + 1,е = Е[1/т] (здесь через Е[а ] обозначается целая часть числа а), 0, х.
= leXk,j = 1-е-, 1, Xj =lc Jf*,j *l-e-, —,x, = l
[стр. 158]

Это значение и соответствующий вектор запоминается.
5.
Адаптация сводится к изменению компонент вектора вероятностей на последующих этапах поиска в зависимости от предыдущих.
На &-м этапе поиска компоненты вектора Pk определяются по правилу (7 ~ 1, гс): Р% + h+, если Xj ~ 1 С Xk nin] Р3 к + h~, если х3 = 1 С Xk nin, где h+ ~ (n — т)/(птй), h~ — \J(Rny (81) 6.
Пункты 2-5 повторяются R раз.
7.
За решение задачи принимается вектор X*, определяемый из условия Д‘) = min XmmХарактерными особенностями данной модификации алгоритма по срав нению с первоначальным вариантом алгоритма являются: в соответствии с (81) реализуется идея поощрения единичных компонент наилучшего вектора за счет его нулевых компонент, что позволяет избавиться от недостатков СПА (СПА не дает возможности получить удовлетворительные решения при т близких п); в соответствии с условием (75), требующим выполнения всех задач области применения первого этапа ТЦУ (аналогично — для второго и т.д.), в п.2 алгоритма МСПА при программной реализации учитывается, что независимый выбор г векторов должен осуществляться по группам версий программных модулей одного функционального назначения, тем самым сокращается время перебора (затраты машинного времени) и учитывается априорная информация, характерная для нашей модели.
Так как величина шагов h+ и h~ в (81) обратно пропорциональна произведению 77п, то при больших размерностях (п > 50) адаптация в алгоритме МСПА практически отсутствует, и алгоритм вырождается в случайный перебор.
В такой ситуации эффективен алгоритм, реализующий идею случайного поиска с возвратом (СПВ) [101].
Рассмотрим его работу при решении поставленных задач исследования (см.разд.
3.5).
1.
При отсутствии априорных сведений о задаче р =
{1/п,..., 1/п}, I — 0, к = 0; (здесь также I номер координаты; к номер этапа поиска).
2.
Случайным образом (в соответствии с распределением
к = 0, ...,77) выбирается г векторов Хг £ Р, i = 1, г.
158

[Back]