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
| Это значение и соответствующий вектор запоминается. 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 |