К.ф.-м.н. Масич И.С.

Сибирский государственный аэрокосмический университет

имени академика М.Ф. Решетнева, Россия

Методы определения свойств алгоритмически заданных псевдобулевых функций

В работе описаны некоторые возможные направления решения проблемы идентификации свойств псевдобулевых функций, имеющих алгоритмическое задание, т.е. сопоставления функции с одним из рассматриваемых классов псевдобулевых функций. Построена процедура идентификации свойств модальности и монотонности путем аппроксимации функций задачи квадратичными полиномами и исследования свойств полученных полиномов.

Поисковые методы оптимизации, т.е. методы оптимизации, не требующие явного задания целевых функций и ограничений (в виде алгебраических выражений), развиваются в двух основных направлениях. Первое – разработка и совершенствование так называемых адаптивных поисковых методов, включающих в себя эволюционные и генетические алгоритмы, поиск табу, алгоритм имитации отжига и т.д. Эти алгоритмы не учитывают свойств входящих в постановку задачи функций и поэтому пригодны для решения произвольных задач оптимизации. Второе направление – построение и исследование поисковых алгоритмов для конкретных классов задач. Такие алгоритмы должны в наибольшей степени учитывать свойства выделенных классов задач, это могут быть как точные, так и приближенные алгоритмы, как регулярные, так и стохастические.

Так, в [1] была проведена классификация псевдобулевых функций и построены точные алгоритмы решения произвольных классов задач безусловной псевдобулевой оптимизации, в том числе и неулучшаемые. В [2] разработан и обоснован существенно не улучшаемый алгоритм условной псевдобулевой оптимизации. Построены полиномиальные приближенные алгоритмы решения различных классов задач условной псевдобулевой оптимизации [3].

При решении практических задач, сводящихся к задачам псевдобулевой оптимизации с алгоритмически заданными функциями, в отдельных частных случаях свойства функций можно идентифицировать исходя из некоторых априорных сведений. Но во многих встречающихся на практике задачах принадлежность функции к какому-либо классу вовсе не очевидна, поэтому необходимо проводить идентификацию свойств функций посредством осуществления пробных шагов. Только после этого возможно применение соответствующего поискового алгоритма.

Один из подходов к идентификации свойств псевдобулевых функций основан на применении регулярного алгоритма оптимизации строго монотонных псевдобулевых функций [1]. Подход заключается в многократном применении регулярного алгоритма из различных стартовых точек. Если во всех случаях алгоритм выдаст одну и ту же точку, являющуюся точкой оптимума, то более вероятно, что проверяемая функция является унимодальной и строго монотонной. Очевидно, при увеличении числа прогона алгоритма из различных стартовых точек вероятность этого растет. Если алгоритм выдаст две разные точки, то функция не является унимодальной строго монотонной.

К сожалению, данный подход позволяет лишь проверить гипотезу о том, что функция является строго монотонной. Точный алгоритм оптимизации монотонных псевдобулевых функций имеет экспоненциальную оценку трудоемкости сверху [1], поэтому проверка гипотезы о монотонности функции (имеющей множества постоянства) подобным образом является чрезмерно трудоемкой процедурой.

Предлагается следующий подход для идентификации свойств псевдобулевых функций. Неявно заданная функция f(X) аппроксимируется функцией g(X), заданной алгебраическим выражением. Затем по виду функции g(X) определяется ее принадлежность к одному из классов.

Рассмотрим квадратичную псевдобулевую функцию

. (1)

Функция (1) в общем случае является полимодальной псевдобулевой функцией, т.е. может иметь несколько локальных максимумов (минимумов).

Предложено два способа квадратичной аппроксимации псевдобулевых функций. При аппроксимации необходимо вычислить значение функции в точке .

Разработана процедура, позволяющая из значений коэффициентов квадратичной функции устанавливать свойства унимодальности, монотонности (строгой монотонности), определять количество локальных оптимумов для полимодальной функции. Полинома второй степени достаточно для корректного определения рассматриваемых свойств. В частности, если исходная функция является монотонной, то и полученный квадратичный полином будет являться монотонной функцией.

С помощью квадратичной аппроксимации возможно также определение других свойств псевдобулевых функций, например, таких как субмодулярность, супермодулярность, полярность, унимодулярность, которые описаны в [4].

После того, как все функции идентифицированы, задачу можно решать соответствующим алгоритмом [1-3].

Литература

1. Антамошкин А.Н. Регулярная оптимизация псевдобулевых функций. – Красноярск: Изд-во Красноярского ун-та, 1989, 284 с.

2. Antamoshkin A.N., Masich I.S. Unimprovable algorithm for monotone pseudo-Boolean function conditional optimization. Engineering & automation problems (Проблемы машиностроения и автоматизации), v. 6, N. 1, 2008, 71-75.

3. Масич И.С. Приближенные алгоритмы поиска граничных точек для задачи условной псевдобулевой оптимизации. Вестник СибГАУ, 1(8), 2006, с. 39-43.

4. Boros E., Hammer P.L. Pseudo-Boolean Optimization. Discrete Applied Mathematics 123(1-3), 2002, pp. 155-225.