допустимой области. Тем самым будет обеспечиваться двойная сходимость к лучшим точкам. Ниже приводится алгоритм СПА с адаптивным учетом ограничений. 1. Задаются начальные значения компонент векторов вероятностей К = \ p î ^ P n \ ро = { р \>->Р~Л гДе P Î и P i вероятности присвоения единичного значения компоненте х,вектора X , i = 1 2. Случайным образом (в соответствии с Рк+) k =0,R, где R параметр метода, задаваемый заранее, инициализируется Н векторов X hk, = 1 , Я , и в соответствии с Рк~ еще Н векторов Х к, h =H +1,2H. 3. Вычисляются соответствующие значения функции /(X*) и ограничений. 4. В случае нарушения каким либо вектором Хк хотя бы одного из ограничений ХкХ ^ и /(Х*) = f{X k~\ если нетто Хк=Хк* и /(ХД) =/(Х £). 5. Из векторов Хк4по критерию выбирается лучший Х^. 6. Если /(Х^) = 0,,то переходим к 2. 7. Находим из множества векторов Х к~ вектор, наиболее близкий по расстоянию к Х \ и обозначим его как Х'к . 8. В соответствии с компонентами вектора Х*к меняются компоненты вектора Рк по следующему правилу: -если 4 = 1, то р;к = /v +fi*; -если х,;=0,то p;t =p;k-h-. В соответствии с компонентами вектора Х'к~ меняются компоненты вектора Рк"по следующему правилу: -если xik~ 1, то pijk = pijk+h ; -если xik-=0, то р-к = р'к+/Г, 9. к=к+1 и пп. 2-8 повторяются R раз. 6 7 |
6. Пункты 2-5 повторяются R раз. 7.3а решение задачи принимается вектор X*, определяемый из условия z(X') «шх1ш(х5ах = тах£(й")) (при к-м повторении п.4) так как решается к—1,г задача максимизации. Схема алгоритма СПА с адаптивным учетом ограничений выглядит следующим образом. 1. Задаются начальные значения компонент векторов вероятностей Р, ~ \Рч>Р\г*"‘>Рщ >Рц>—’Ртк. \ Ро = {рП’Рп>—’Р щ ’Рг1>—>Рткт}' ПД6 p tj И Рц вероятности присвоения единичного значения компоненте х0 вектора X, i=l,m,j=l,k,;. 2. Случайным образом (в соответствии с Рк ) к = О,R, где R параметр метода, задаваемый заранее, инициализируется Н векторов Хк , = 1, Н , и в соответствии с Рк еще Н векторов Хк, h =Н +1,2Я ,. 3. Вычисляются соответствующие значения функции f ( X k) и ограничений. 4. В случае нарушения каким либо вектором Х к хотя бы одного из ограничений X hk=Xhkи /С О = /(* £ '), если нетто X hk=Xhk* и f(X>t ) =f(X*;). 5. Из векторов Х к*по критерию выбирается лучший Х'к. 6. Если f ( X ’k) = 0,, то переходим к 2. 7. Находим из множества векторов Х к~ вектор, наиболее близкий по расстоянию к Х\ и обозначим его как Х'к . 8. В соответствии с компонентами вектора Х\ меняются компоненты вектора Рк по следующему правилу: -если X ’jk=1, то Р;к = pïJk+h+; -если Х'1)к=0, то Р;к =Р;кГ ;. В соответствии с компонентами вектора Х'к~ меняются компоненты вектора Рк~по следующему правилу: -если л£= 1,то +Л+; 126 -если * ;;-0 ,т о р~к = р ‘*+/Г, где Ъ =И = -----. К*п 9. к=к+1 и П. 2-8 повторяются К раз. 10. За решение задачи принимается вектор /(Х у )= тах/(Х])к), к =0,К. Так как величина шагов И' и к+в алгоритме СПА обратно пропорциональна произведению Яп, то при больших размерностях (и>50) адаптация в алгоритме СПА практически отсутствует, и алгоритм вырождается в случайный перебор. Для нашей задачи так же характерны большие размерности, как, впрочем, и недостаток априорной и апостериорной информации. В такой ситуации эффективен алгоритм, реализующий идею случайного поиска с возвратом (СПВ). Схема его работы следующая. 1. Задаются начальные значения компонент векторов вероятностей Д = \рн,Рп>~’Рщ>Рп>"’Р»кЛ гДе Рц вероятность присвоения единичного значения компоненте х1} вектора X, / = 1,т, ] = 1,к1;. 2. Случайным образом (в соответствии с Рк) инициализируется Н векторов хЦ. 3. Вычисляются соответствующие значения функции /(X*) и ограничений. 4. В случае нарушения каким либо вектором Х ьк хотя бы одного из ограничений / (Хкк) = / (Хнк),. 5. Определяется лучшее значение функционала шах/ (Хк) , если 1=0; Хк = Л= 1,Я шахСД,,,/ (Xк)), если />0; Ч 6. Если / к ^ ,, то /=0. 7. / = / +1, и в соответствии с компонентами вектора Х\ меняются компоненты вектора Ркпо следующему правилу: 127 |