А. А. ЛИПАТОВ
РосНИИ искусственного интеллекта, Москва
МЕТОД НЕТОЧНОЙ ЛОКАЛИЗАЦИИ РЕШЕНИЙ НЕДООПРЕДЕЛЁННОЙ СИСТЕМЫ ОГРАНИЧЕНИЙ
В докладе предлагается метод локализации корней недоопределённых систем ограничений, основанный на совместном применении метода недоопределённых вычислений и эвристики случайного поиска. Метод позволяет сократить время и трудоёмкость поиска решения по сравнению с методом, применяемым в настоящее время в программных средствах, реализующих недоопределённые вычисления.
Решение сложных вычислительных задач из области экономики, финансов, управления проектами, конструирования и др. часто требует применения комбинации различных вычислительных методов. Важное место среди них занимают методы, позволяющие решать задачи с недоопределёнными данными, в частности метод недоопределённых вычислений (Н-вычислений) [1]. Следует, однако, отметить, что пространство решения, получаемое с помощью метода интервальных Н-вычислений, в общем случае имеет вид многомерного параллелепипеда, внутри которого лежит тело решения произвольной формы. В то же время, для практических целей часто требуется найти хотя бы одно точное решение, причем иногда требуется найти минимальные или максимальные значения некоторых переменных. В недоопределённом решателе UniCalc [2] реализован алгоритм локализации корней системы ограничений, основанный на рекурсивном делении интервалов переменных и применении метода Н-вычислений [3]. Однако, для областей решения, содержащих большое или бесконечное число корней, их поиск требует длительного времени. Для сокращения длительности пользователю необходимо проводить анализ системы ограничений [4]. Таким образом, разработка методов локализации корней является актуальной задачей.
В работе [5] предложено совместно использовать методы Н-вычислений и случайного поиска для решения задач оптимизации. Однако, данная комбинация методов может применяться для решения задач локализации корней недоопределённой системы ограничений и в других областях. Рассмотрим следующую задачу. Имеется набор ограничений произвольного вида R над некоторым набором переменных X. Необходимо найти корень системы ограничений, соответствующий минимальному значению переменной xÎX.
С помощью метода Н-вычислений для системы ограничений R, если она совместна, находится её область решения A. Пользователь исследует область решения, выявляя дополнительные ограничения на значения переменных из X, приводящие к её сужению. Для этого могут использоваться средства интерактивной компьютерной графики [6].
Затем порождается набор случайных точек BÌA. Выбирается точка aÎB с минимальным значением x. С помощью метода Н-вычислений проверяется, удовлетворяет ли набору ограничений R окрестность *a точки a. Для точки a = (a1, …, an) окрестность *a = ([a1Lo, a1Hi], …, [anLo, anHi]), где aiLo = ai – D×ai, aiHi = ai + D×ai для i = 1, …, n, и 0,01 ≤ D ≤ 0,1. Если *a не удовлетворяет ограничениям, то выбирается точка bÎB\a с минимальным значением x. Этот процесс продолжается до тех пор, пока не будет найдена окрестность, удовлетворяющая всем ограничениям из R.
Далее для нахождения точных значений в данной окрестности используется встроенный в решатель UniCalc алгоритм поиска корней.
Данный метод реализован в экспериментальной программе, интегрированной в состав программного комплекса с решателем UniCalc и средствами интерактивной компьютерной графики. Проводились эксперименты по решению с помощью данного комплекса задач из области управления проектами. Предложенный метод позволяет сократить время локализации корня за счёт уменьшения числа итераций Н-вычислений по сравнению с существующим алгоритмом и исключает необходимость анализа системы ограничений.
Список литературы
1. Нариньяни в системах представления и обработки знаний // Изв. АН СССР. Техн. Кибернетика. 1986. №5. С. 3‑28.
2. Babichev A. B., Kadyrova O. B., Kashevarova T. P., Leshchenko A. S., Semenov A. L. UniCalc, A Novel Approach to Solving Systems of Algebraic Equations // Numerical Analysis with Automatic Result Verifications: Proc. / Intern. Conf., Lafayette, Louisiana, USA, February-March, 1993. – Interval Computations. 1993. №. 2. Pp. 29-47.
3. , Семенов вопросы сходимости метода недоопределенных вычислений // Проблемы представления и обработки не полностью определенных знаний. - РосНИИ ИИ, Москва - Новосибирск, 1996. С. 31-37.
4. Кашеварова системы UniCalc для решения задач математического моделирования. - Новосибирск, 19с. (Препр. / РАН. ИСИ; № 64).
5. Разработка требований к автоматизированной системе оценки и управления инвестиционными проектами. В кн. Экономические и информационно-аналитические основы управления инвестиционными проектами: монография. - М.: Издательство Московского психолого-социального института; Воронеж: издательство НПО «МОДЭК», 2004 – 295 с.
6. , Липатов данных в технологиях интервальных расчетов // Информационные технологии. 2001. № 8. С. 11-16.
