|
10. За решение задачи принимается вектор f (X**) = шах/ (Х*к), к = 0,/?. Так как величина шагов К и Л+ обратно пропорциональна произведению Ял, то при больших размерностях (н>50) адаптация в алгоритме СПА практически отсутствует, и алгоритм вырождается в случайный перебор. Для нашей задачи так же характерны большие размерности, как, впрочем, и недостаток априорной и апостериорной информации. В такой ситуации эффективен другой алгоритм схемы МИВЕР, реализующий идею случайного поиска с возвратом. 1. Задаются начальные значения компонент векторов вероятностей Ро= {рГ>-..,К}> гДе А вероятность присвоения единичного значения компоненте х, вектора X, / = 2. Случайным образом (в соответствии с Рк) инициализируется Н векторов Х ик. 3. Вычисляются соответствующие значения функции /( Х к) и ограничений. 4. В случае нарушения каким либо вектором ХЦ хотя бы одного из ограничений /(Х к) =/(Х к), 5. Определяется лучшее значение функционала шах/(Х к) , если /=0; Л = Л = 1,Я ш ах(/ь „ / № Л)), если />0; 6. Если /* 7. / = / +1, и в соответствии с компонентами вектора Х\ меняются компоненты вектора Ркпо следующему правилу: 0, если х] \ а Л'*,/ /; рк/ ' “ I 1,если х/= 1с Ч 6 8 |
-если * ;;-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. Если / к 7. / = / +1, и в соответствии с компонентами вектора Х\ меняются компоненты вектора Ркпо следующему правилу: 127 |