Xl Туполевские чтения : всероссийская (с международным участием) молодежная научная конференция. Казань, 8-10 октября 2003 г., тезисы докладов. Т. 3

Случайный поиск граничных точек в задаче условной псевдобулевой оптимизации И.С. Масич Научный руководитель: А.Н. Антамошкин, д.т.н., профессор Сибирский государственный аэрокосмический университет им. М.Ф. Решетнева Рассматривается класс задач условной оптимизации следующего вида [СЧЛ") -> тал. где ССА") И А{Х) - МОНОТОННО возрастающие от Х° € В'; псев- j добулевые функции. Эта задача является ЛТ'-полной задачей, |/)(A)<W. .j.g gg нельзя решить никаким известным полиномиальным алгоритмом. Показано, что решением задачи является точка, принадлежа­ щая подмножеству граничных точек. Регулярные алгоритмы для решения рассматриваемой задачи при высокой размерности имеют довольно боль­ шую трудоемкость, поэтому исследуются алгоритмы случайного поиска для нахождения приближенного решения задачи. Ранее был построен следующий алгоритм случайного поиска гранич­ ных точек. Поиск начинается из начальной точки Х°. Алгоритм на каждом шаге случайно выбирает точку е0,(Х,)г\0,(Х'')п{Х s : А(,Х)<Н) (О,(А") - множество точек, отличающихся от X значением к компонент). Если таких нет,то фаничная точка найдена. Трудоемкость алгоритма Т = где L - количество 1.0 2 граничных точек, которое планируется найти. Следует отметить, что эти найденные точки могут и совпадать. Предлагается алгоритм случайного поиска граничных точек, учиты­ вающий значения целевой функции и ограничения при случайном выборе на каждом шаге следующей точки. Следующая точка на /-ом шаге выбирается в соответствии с вектором вероятностей Р'" ={р[" Р7-,), P'L" • где \ах,)/А(Х^). А(Х,)<Н. ' • i o . AiX,)>H. ' = Граничные точки, обнаруженные с помощью этого алгоритма будут в среднем более близки к истинному решению, чем граничные точки, най­ денные предыдущим алгоритмом. Это позволяет использовать меньшее число повторений L при той же надежности. Также предлагается подход, позволяющий исключить повторение граничных точек, найденных алгоритмом. 14