|
В2„ = {X :х, е Я2,у = 1,и}; = {0,1}; О с г В 2*некоторое подмножество множества булевых переменных, определяемое заданной системой ограничений, выглядит следующим образом. ¡.Задаются начальные значения компонент вектора вероятностей Р° = , где р] = = 1} вероятность присвоения единичного значения у-й (у = 1,«) компоненте векторах е £>. 2.Случайным образом (в соответствии с распределением вероятностей Рк, к = 1,Л-1), независимо выбираются г векторов Х е й , / = 1,г. 3.Вычисляются соответствующие значения функционала /(X'),/ = 1,г . 4.Выбираются требуемые (по конкретному алгоритму) значения функционала из совокупности /(X '),/ = 1,г . 5.По результатам п.4 изменяются (в соответствии с правилом конкретного алгоритма) компоненты вектора вероятностей Рк. 6.Пункты 2-5 повторяются Л раз. 7.3а решение задачи принимается вектор X*, определяемый из условия /(Х*) = шах/1^ах(/Лах=шах/(X'))(при к-м повторении п.4) так как решается кш1,Я Ы\,г задача максимизации. Базовым алгоритмом схемы МИВЕР является случайный поиск с адаптацией (СПА). Его недостатком при решении задач условной оптимизации (с ограничениями) является то, что точки, в которых ограничения нарушаются, в процессе поиска не участвуют. Нами предлагается вместо одного вектора вероятностей, поощрающего только точки из допустимой области, рассматривать два один для поощрения допустимых дочек, а другой для поощрения точек не принадлежащих допустимой области, но по расстоянию наиболее близких к лучшим точкам f •Вг -» Я1поле действительны х чисел, 6 6 |
алгоритм определяется как алгоритм со следующими “удобными” для нас свойствами. 1. Он обычно находит хорошее, хотя не обязательно оптимальное решение. 2. Простота реализации эвристического алгоритма по сравнению с любым известным точным алгоритмом (гарантирующим оптимальное решение) не вызывает сомнения. Понятие “хороший” и “обычно” в первом свойстве меняются от задачи к задаче. Поэтому если для решения задачи все известные точные алгоритмы требуют непозволительно больших затрат машинного времени, то мы можем охотно принять любое приближенное (субоптимальное) решение, которое может быть получено за разумное время. С другой стороны, уже имея быстрое, близкое к оптимальному решение, мы можем стремиться все же к точному решению. При решении рассматриваемой задачи апробировались два эвристических алгоритма дискретной оптимизации схемы МИВЕР: случайный поиск с возвратом (СПВ) и случайный поиск с адаптацией (СПА) [85]. Метод изменяющихся вероятностей (МИВЕР) [85] представляет семейство алгоритмов, имеющих общую схему. В самом общем виде эта схема применительно выглядит следующим образом. 1. Задаются начальные значения компонент вектора вероятностей Р° = {р" рйп}, где р) = Р{х) = 1} вероятность присвоения единичного значения у'-й (у = 1,и) компоненте вектора^ е О. 2. Случайным образом (в соответствии с распределением вероятностей Рк, к = 1,й -1), независимо выбираются г векторов X е Э , / = 1,г. 3. Вычисляются соответствующие значения функционала х(Х'\ \ 1,г. 4. Выбираются требуемые (по конкретному алгоритму) значения функционала из совокупности %(Х‘), 1= 1,г. 5. По результатам п.4 изменяются (в соответствии с правилом конкретного алгоритма) компоненты вектора вероятностей Р*. 125 |